Section 5: Small Records, Enormous Bytes - Data Modeling

Executive Summary: Section 4's verbs read and write two stores with opposite shapes. The index holds four small record kinds, bucket, object, multipart upload and tombstone, range-partitioned on (bucket_id, key); an object record is ~200 B, so 10 trillion of them make 2 PB of index, ~12 PB of SSD, ~40,000 partitions of ~50 GB. The data layer holds two large kinds, the stripe (15 fragments of 64 MB under RS(10,5), encoded in 640 KB groups) and the journal extent (3 replicas, one per AZ); ~1.6 billion stripes carry the exabyte. The index never holds bytes or per-piece checksums, and the extent list rides with the object because every read arrives as a key.

The interviewer circles the verbs still on the board from Section 4. "Every one of these touches storage. Show me the records, and tell me which store each one lives in."

You: "Two stores, two shapes. The index is small-and-many: trillions of ~200 B records, ordered by key. The data layer is large-and-few: a billion-odd immutable stripes. Bytes never enter the index; the data layer sees keys only inside the index's own opaque log and table streams."

The Index Layer: Four Record Kinds

bucket            (bucket_id PK, name, owner, policy, region, cluster_home, created)
object            ((bucket_id, key) PK, version_id, size, etag, checksum, content_type,
                   user_metadata <= 2 KB, storage_class, wrapped_data_key, created, modified,
                   flags, extents [(stripe_or_extent_id, offset, length)]  -- or manifest_ref)
multipart_upload  ((bucket_id, key, upload_id) PK, initiated, parts {part_no -> etag, size, extents})
tombstone         ((bucket_id, key) PK, version_id, deleted_at, extents_to_reclaim)

Bucket. Owner, the policy the front-end evaluates, and the cluster home that pins its data to one of the region's ten storage clusters. Few, rarely changed, cached on every front-end: control plane.

Object. The record everything waits on. The index is range-partitioned on (bucket_id, key) (D2), so a bucket's keys sit in sorted order and a prefix LIST is one range scan. Ordered LIST and per-key throttling both need a range-ordered index (Section 8), and hash partitioning gives up both; a hot prefix is handled by splitting the range, never by re-hashing.

Here is where N6's ~200 B comes from, for a typical single-extent object:

Times N1: 10^13 × 200 B = 2 PB, which becomes ~12 PB of SSD with three replicas and 2× LSM amplification, in **40,000 partitions of ~50 GB** over ~1,000 partition servers.

The wrapped data key sits in the record on purpose (D10): a random AES-256-GCM key per object, wrapped by the bucket's KMS key. A GET already reads the record, so unwrapping costs one cached KMS call and no second lookup. A single region-wide key was rejected for the rotation cost Section 2 priced; customer-managed keys are the same field with a different wrapping key.

Multipart upload. The in-flight record for Initiate → UploadPart → Complete, keyed under the same (bucket_id, key) prefix as the eventual object, so Complete is a single-partition write. Each part adds a part_no → (etag, size, extents) entry; Complete validates the client's part list and writes the object record with a manifest, the ordered part list, in place of an extent list (D7). No bytes move, and the ETag is the hash of the part ETags plus the part count, the not-an-MD5 that Section 4 defended. The rejected server-side re-copy would double every large object's write bandwidth for nothing a reader can observe.

Tombstone. A DELETE writes a tombstone over the key and carries the old extent list forward (D6). The bytes are untouched; the compactor reclaims them when a stripe's dead ratio justifies a rewrite (Section 9). The rejected in-place free-list reclamation would turn every DELETE into a data-layer write and every stripe into something that can be left half-updated. Only the lag is tuned.

Priya's clip-00123/0001.jpg is one record with a one-entry extent list, right at the 200 B average; clip-00123.mp4 is one record whose manifest has ten rows, one per 48 MB part, and the 10,000-part ceiling (N10) means even a 5 TB object resolves from one record.

How the four index record kinds relate, and where they point into the data layer:

Quick check before moving on: