Spanner holds the data Zanzibar needs to decide whether a person is allowed an action: the namespace configurations, the relation tuples and the changelog.
A changelog row is keyed by a random shard ID, a timestamp and an update ID.
A relation tuple is keyed by five parts:
- The shard ID. It is usually the object ID hashed into a bucket, and the bucket is a database, so everyone on one document is in one place.
- The object ID and the relation. This order keeps all the people with edit access on one document together.
- The user and the commit timestamp.
For a very large group, such as a YouTube video that a million people can view, the shard ID is computed on object and user, because the read asks whether one user has access. A small object keeps the object ID, so one query goes to one shard.
Inside a shard the rows are sorted on a composite key. Hashing reaches the shard in constant time, and a binary search finds the viewers in logarithmic time.