Section 7: Any Row in Three Hops - Deep Dive: Tablet Location, Assignment & the Master

Executive Summary: The control plane answers two questions without carrying a byte of user data: where does this row live? and who may serve it? Location is a three-level hierarchy. A Chubby file points at the root tablet, the root indexes 8 METADATA tablets, and those index all ~1 million user tablets in ~1 GB of in-memory rows, so a cold client reaches any row in 3 round trips and a warm one in zero. Assignment rides on Chubby: each tablet server locks its own file in a servers directory, and the master deletes that file before reassigning anything. The master polls at ~1,000 RPC/s, restarts in four steps, and fails over in ~20 s while every assigned tablet keeps serving. Splits, about one a minute, are the one change a tablet server starts, and they commit in METADATA before the master hears of them.

Interviewer: "A million tablets on a thousand servers, and they keep moving. Maya's front-end wants her row. Who tells it which server to call? The master?"

You: "Not for lookups. At a peak of 2 M ops/s, asking the master for directions would put the machine we promised never touches data in front of all of it. Location is data, so I store it in Bigtable itself, in a table called METADATA, and the client walks it like a B+-tree. The master only decides who serves what, and makes sure one server at a time believes it does."

Three Hops to Any Row

1. A Chubby file holds the location of the root tablet.
2. The root tablet is the first tablet of METADATA, with one row per other METADATA tablet. It never splits, and that rule alone caps the tree at three levels.
3. Each METADATA tablet holds one row per user tablet, keyed by an encoding of table ID and end row. The row carries the serving location, the SSTable list and redo points needed to load the tablet, and an event log ("server X began serving") kept for debugging.

Why the end row? Tablets tile the key space without gaps, so the tablet holding com.cnn.www is the one with the smallest end row at or after it. A lookup is "seek to the first METADATA key ≥ (Webtable, com.cnn.www)", one seek in a sorted map.

From Section 3: ~1 KB per METADATA row × 1 M tablets ≈ 1 GB, split at 128 MB into 8 METADATA tablets, so the root holds 8 rows. The ceiling is 128 MB / 1 KB = 2^17 rows per METADATA tablet, and the root addresses 2^17 of those: 2^34 ≈ 17 billion tablets, about 2^63 bytes ≈ 8 EiB at our 0.5 GB average. (The paper, with 128 MB tablets, quotes 2^61 bytes.)

Key Insight: METADATA is an ordinary Bigtable table whose location data sits in an in-memory locality group. It inherits splitting, GFS durability and crash recovery from the same machinery as user data, and no lookup waits on a disk. There are exactly two special cases: the root never splits, and its address lives in Chubby.

Quick check before moving on: