0) Problem Restatement
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.
1) Requirements
- 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.
2) 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.
Architecture Diagram
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")] --> RT3) Scaling: 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.
4) Latency Trade-offs (the key discussion)
- Every write needs a majority, which means cross-region round trips (tens to 100+ ms). That's the price of global consistency.
- Leader placement: put each shard's leader in the region where most of its writes come from (e.g., bucket metadata near its owner). Writes then need one round trip to the nearest majority.
- Reads:
- Leader reads with a lease: the leader knows no one else can be leader for a few seconds, so it can answer reads locally, which is linearizable and fast in the leader's region.
- Follower reads: a follower asks the leader for the current commit index (or waits until it has caught up), then answers. Still linearizable, it saves bandwidth, and it's local when caught up.
- Bounded-staleness reads ("up to 5 seconds old") for callers that don't need the latest, which are served locally with no coordination.
- Spanner's approach: synchronized clocks with known error bounds (TrueTime) give every transaction a global timestamp, so reads at a timestamp can be served by any up-to-date replica.
5) 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).
6) Wrap-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.