CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 6 of 8 · 2 min read

Metadata store

Tables, shards and listing.

Tables. A small bucket table (bucket id, name, owner). A larger object table (bucket id, name, object id, size, version and so on). If there are 1 million customers with 10 buckets of 1 KB records, the bucket table is 10 GB, small enough for one server with read replicas.

Sharding the object table. It does not fit in one database. Sharding by bucket id makes hot shards, since one bucket may hold billions of objects. Sharding by object id spreads load, but lookups by name become hard. The book shards by a hash of the pair (bucket name, object name), because most requests give the name.

Listing. Object stores use prefixes, which are leading parts of names that look like folders, but are only strings. Listing by prefix with a delimiter such as / shows the objects directly under the prefix and rolls up deeper names into common prefixes.

A worked example (made up). A bucket holds CA/LA/a, CA/SF/b, NY/NYC/c and top.txt. Listing the top level with / as delimiter returns the object top.txt and the common prefixes CA/ and NY/. Listing prefix CA/ returns CA/LA/ and CA/SF/.

With one database, this is a simple query. When sharded, an object under one prefix may sit on any shard, so the service must ask all shards, merge, sort and page. Paging then needs one offset per shard, which is awkward. The book's practical answer is a separate listing table, sharded by bucket id, because listing speed is rarely a priority in object storage.

Versioning. With versioning on, an upload of an existing name does not overwrite. A new row is added with the same name and a new version id (a time-based id). The current version is the newest. A delete adds a delete marker, a new empty version, so a GET returns "not found" but the older versions remain and can be restored.

Read it as

A delete marker is a sticky note on the top of a stack of papers saying "withdrawn". The papers beneath are still there.

Check yourself: 1. Why is sharding by bucket id a poor choice? 2. What is a prefix? 3. What does a delete do when versioning is on?