Problem RestatementProblem
Amazon asked: design a metadata service that must be globally consistent. Think of the service that stores which buckets exist and who owns them, or which files live where, for a storage system used from many regions. Linearizable means the system behaves like one single copy: once a write is acknowledged, every later read, from any region, sees it (no stale reads), and conflicting writes are ordered.
RequirementsRequirements
- Operations: create, read, update and delete metadata entries (small records), plus conditional updates (compare-and-set).
- Linearizable reads and writes for correctness (e.g., two users can't both create bucket "photos").
- Survive the loss of a machine, a zone, or a whole region.
- Scale to billions of entries and high request rates.
Core Building Block: Consensus Groups
- A consensus group (Raft or Paxos) is a small set of replicas (e.g., 5) that agree on the order of writes. A write is committed when a majority (3 of 5) has it. Any majority overlaps any other, so no committed write can be lost or contradicted.
- Place replicas across regions (e.g., 2 in us-east, 2 in eu-west, 1 in ap-south), so losing one region still leaves a majority.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Clients in any region"] --> RT["Router - which shard owns this key?"]
RT --> G1["Shard 1 - Raft group across 3 regions"]
RT --> G2["Shard 2 - Raft group across 3 regions"]
RT --> G3["Shard N - Raft group"]
G1 --> L1["Leader - us-east"]
G1 --> F1["Follower - eu-west"]
G1 --> F2["Follower - ap-south"]
DIR[("Shard directory - itself a consensus group")] --> RTScaling: Partition into Many Groups
- One consensus group can't hold billions of entries or handle all traffic. So range-partition keys into shards, each its own consensus group (as Spanner, CockroachDB and TiKV do).
- A directory (also replicated with consensus) maps key ranges to shards. Shards split when they grow or get hot, and move between machines.
- Cross-shard operations (rare for metadata) use two-phase commit on top of consensus groups.
Deep Dive — Paying for global consistency on readsDeep dive
Writes need a majority across regions, which costs a cross-region round trip. Reads are far more frequent, and how they are served is where the design is won or lost.
Route every read through consensus
Treat a read like a write: propose it, get a majority, then answer.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
R["Read: who owns bucket X?"] --> L["Leader"]
L --> Q["Round trip to a majority across regions"]
Q --> LAT["80-150 ms for a metadata lookup"]
LAT --> HOT["Reads outnumber writes 100:1 - the quorum is saturated"]It is correct and it prices every read at the cost of a write. Since metadata is read constantly — every request touches it — this makes the consensus group the bottleneck for the entire storage system.
Read from any follower
Followers hold a copy, so send reads to the nearest one. Latency drops to a local round trip and read capacity scales with replicas.
It is also no longer linearizable. A follower can be behind the leader, so a client that just created a bucket may read a follower that has not seen it — "I created it and it doesn't exist" — which is precisely the anomaly a globally consistent metadata service exists to prevent.
Leader leases, placed where the writes are
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
W["Writes for shard S"] --> LP["Leader placed in the region those writes come from"]
LP --> NEAR["One round trip to the nearest majority"]
RD["Read in the leader's region"] --> LEASE{"Leader holds a valid lease?"}
LEASE -->|"yes"| LOCAL["Answer locally - linearizable, no round trip"]
LEASE -->|"no"| QUORUM["Fall back to a quorum read"]
RF["Read at a follower"] --> IDX["Ask the leader for the current commit index"]
IDX --> WAIT["Wait until caught up, then answer"]
WAIT --> OK["Linearizable, at the cost of one small round trip"]- A leader lease means the leader knows no other node can be elected for the next few seconds, so it can answer reads from local state and still be linearizable. This is the single biggest win: reads in the leader's region cost nothing.
- Place the leader where the writes originate. Shard by the entity — bucket metadata near its owner — so the common write path is one round trip to the nearest majority rather than across the planet.
- Follower reads can be linearizable too, if the follower asks the leader for the current commit index and waits until it has applied up to it. That is one small round trip instead of a full quorum, and it lets read capacity scale without giving up the guarantee.
The honest summary for the interview: global consistency has a floor set by the speed of light, and the design's job is to make sure most operations do not pay it — by moving leaders to the traffic and by making local reads provably safe rather than merely fast.
Failures
- A follower down → no effect (the majority remains).
- The leader down → the group elects a new leader in seconds, and clients retry via the router.
- A whole region down → groups with a majority outside it continue. Leaders in that region are re-elected elsewhere, and latency may rise for its users.
- A network partition → only the side with a majority can accept writes (consistency over availability, the "CP" choice).
Wrap-UpWrap-up
Store metadata in range-partitioned shards, each replicated by its own consensus group (Raft/Paxos) with replicas spread across regions, so any majority can commit and a region can be lost. Route keys through a consensus-backed directory, split and move shards as they grow, place leaders near their writers, and serve linearizable reads from leaseholders or caught-up followers (with bounded-staleness reads when allowed). Accept cross-region write latency as the cost of global consistency.