Design a Distributed Key-Value Store

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Track Opener: What Is a Key-Value Store?

You Already Use One: the Hashmap

You have written this line a hundred times (pseudocode):

textCopy
sessions["sess_7f3a"] = { "user_id": 1001, "cart_items": 3 }

That is a key-value store. A Python dict or a Java HashMap hashes the key to find a slot in an array, so a lookup takes about the same short time whether the map holds ten entries or ten million. We call that O(1) on average.

A key-value store is the same idea offered as a service over the network. You give it a key and a value; later you give it the key and get the value back. Redis, Amazon DynamoDB and Apache Cassandra all work this way at their core.

What teams keep in one:

What they have in common: the caller always knows the exact key, and it wants the answer fast.

What Changes When the Hashmap Spans Many Machines

On one machine, several hard problems are free:

Every problem in the three rounds is one of these four: surviving crashes, holding more than one machine can, keeping copies in agreement, and answering while machines fail.

The Question the Whole Track Answers

When the network between our machines breaks, a copy on one side can't learn about writes on the other side. At that moment we have two choices:

• Answer anyway with what we have, and risk returning an old value (we stay available).
• Refuse to answer until the copies can talk again (we stay consistent).

We can't have both while the network is broken. This is the core of the CAP theorem. So the question is:

We can't have perfect consistency and perfect availability when the network breaks. So which do we give up, when, and who chooses?

The answer gets sharper every round:

• Round 1: we pick once, for the whole cluster.
• Round 2: each request picks.
• Round 3: each table picks, per region.

---

Round 1 · Mid-level · "A KV Store for One Product Team"

~35 min · SDE II (L5) · 1 region, 3 AZs · ~10K QPS peak · ~1 TB · 99.9%

R1.1 Establish Design Scope

The interviewer says: "Design a key-value store." That's all. Before we draw anything, we ask questions. Each answer changes the design, so we say what it changes out loud.

Out of scope for this round:

• Secondary indexes ("find users by email"). They need a second data structure kept in sync with the first. The team only looks up by key.
• Range scans. They need keys kept in sorted order across machines. We just said no.
• Multi-key transactions ("move an item from cart A to cart B, all or nothing"). They need a commit protocol across machines, such as two-phase commit. Nobody asked for it.

R1.2 Functional Requirements, Derived Step by Step

We read the problem one phrase at a time and turn each phrase into an operation:

That's the whole list for this round: three operations plus TTL.

Not yet: batch operations (many keys in one call), choosing consistency per request, and conditional writes ("write only if nobody changed it"). We don't need them at this scope, so we don't build them.

What Is a "Value"?

The store treats a value as bytes. It never looks inside. But the caller's data has a shape, and that shape decides where the rules about the data live.

Structured values follow a fixed schema: the same fields, the same types, every time.

textCopy
Key:   "user:1001"
Value: { id: INT64, email: STRING, status: ENUM, updated_at: TIMESTAMP }

Some databases enforce such a schema themselves. A relational table does, and so does a Cassandra CQL table with typed columns. Amazon DynamoDB does not: it types only the key attributes (the partition key and optional sort key), and every other attribute on an item is free-form. That makes DynamoDB items semi-structured, even when every item happens to look the same. Our store enforces no schema at all, so when a team wants structured values, the schema lives in the client, for example as a Protocol Buffers or Avro format that the writer checks before it calls put.

Semi-structured values carry their own field names, and two values under the same kind of key can have different fields:

textCopy
Key:   "product:88213"
Value: { "title": "Running Shoe", "price": 89.99, "attributes": { "color": "red", "size": "10" } }

Key:   "product:88214"
Value: { "title": "Espresso Machine", "price": 349.00, "attributes": { "wattage": 1350 }, "warranty_years": 2 }

That is flexible, but every value repeats its field names (more bytes), and readers must cope with missing or unknown fields.

What both cost in our store: put replaces the whole value. To change one field of a 2 KB profile, the client reads the value, changes the field, and writes all 2 KB back, with a new version. An engine that stores each field separately, as Cassandra does with its per-column cells, can update one field alone. Ours can't, and at this scope we accept that.

R1.3 Non-Functional Requirements: the Questions

We state each quality in words first. The numbers come in R1.7, once we have a design to attach them to.

• Availability: survive a node loss. When one machine dies, every key must still be readable and writable. Hardware fails every day at fleet scale.
• Latency: fast enough to sit on every page load. A page may make several calls to the store. If each takes 50 ms, the page is slow.
• Durability: an acknowledged write is never lost. Once we say "OK", the data must survive a crash. Otherwise callers can't trust the "OK".
• Scalability: add machines, get more capacity. When data or traffic doubles, we add machines. We don't redesign.
• Consistency: eventual is fine. If a reader sees an old value for a moment, nothing breaks. All copies must agree eventually.

How availability and consistency pull against each other. We will keep several copies of every key. To be available, we want to answer even when some copies can't be reached. To be consistent, we want every answer to reflect the latest write, which means checking with enough copies. The more copies we wait for, the more consistent the answer and the more likely a slow or dead copy blocks us. Every design choice below sits somewhere on that line.

R1.4 The API

Three HTTP endpoints. The key is part of the URL.

Write a value

httpCopy
PUT /v1/kv/session:7f3a9c HTTP/1.1
Content-Type: application/json

{
  "value": { "user_id": 1001, "device": "ios", "cart_items": 3 },
  "ttl_seconds": 86400
}

jsonCopy
{ "key": "session:7f3a9c", "version": "1773648000123456" }

Read a value

httpCopy
GET /v1/kv/session:7f3a9c HTTP/1.1

jsonCopy
{
  "key": "session:7f3a9c",
  "value": { "user_id": 1001, "device": "ios", "cart_items": 3 },
  "version": "1773648000123456",
  "ttl_remaining_seconds": 86120
}

Delete a value

httpCopy
DELETE /v1/kv/session:7f3a9c HTTP/1.1

jsonCopy
{ "key": "session:7f3a9c", "deleted": true, "version": "1773648005000000" }

Every response carries a version. Clients should treat it as an opaque token and only compare it for equality. In this round it's the time at which the write was accepted. It will matter a lot later.

Why PUT and not POST? In HTTP, POST /things means "server, create a thing and pick its ID." Here the client already owns the key, so it addresses the resource directly: PUT /v1/kv/{key}. PUT is also idempotent: sending the same PUT twice leaves the same result as sending it once. That matters because networks time out after the server has already done the work. With PUT, the client simply retries. With a create-style POST, a retry could create a duplicate.

Status codes

Recap

• Three operations: put, get, delete, plus an optional TTL.
• Values up to 100 KB; the store treats them as opaque bytes.
• About 10K requests per second at peak, 80% reads, one region with 3 AZs.
• It must survive losing a machine and never lose an acknowledged write.
• Stale reads are acceptable; copies must agree eventually.

Let's build it, starting with the dumbest version that works.

R1.5 Design Evolution: From One Hashmap to a Replicated Store

Every step below follows the same pattern: a problem, your turn to think, the answer, and what the answer costs us. The cost is always the next problem.

Step 1.0: The Baseline

One server. One hashmap in memory. An HTTP handler in front of it.

Synthesizing vector architecture diagram...

What's good about it: it's simple, every read and write takes microseconds, and there is exactly one copy, so it can never disagree with itself. For a prototype, this is the right answer.

Everything that follows exists because this server will crash, fill up, and one day not come back.

Step 1.1: Surviving a Restart

The WAL gives us the durability promise from R1.3: once we reply "OK", the write is on disk.

Synthesizing vector architecture diagram...

The order matters. The server writes the log and forces it to disk before it touches memory or answers. If the server dies after the fsync, replay restores the write. If it dies before, the client never got an "OK", so nothing was promised.

Primitive: Write-Ahead Log & LSM-Trees

Step 1.2: The Data No Longer Fits in Memory

All disk writes in an LSM tree are sequential: WAL appends, MemTable flushes and compaction output. The disk never updates a record in place.

Synthesizing vector architecture diagram...

Writes flow down the left: WAL and MemTable, then a flush to Level 0, then compaction into bigger levels. Below Level 0, files in one level never overlap, so a key can be in at most one file per level. Reads check the MemTable, then ask each file's Bloom filter before touching the disk.

We use leveled compaction: each level is about 10 times larger than the one above, and within a level (below Level 0) each key lives in at most one file. A read then checks at most one file per level, and Bloom filters keep actual disk reads close to one.

Why 10 bits per key gives about 1%: the best number of bits per key for a false-positive rate p is -ln(p) / (ln 2)^2. For p = 0.01: 4.605 / 0.4805 ≈ 9.6 bits, which we round up to 10 bits, or 1.25 bytes per key.

Primitives: Write-Ahead Log & LSM-Trees · Bloom Filters · Drill: WAL/LSM compaction storm

Step 1.3: One Machine Isn't Enough

With 4 machines going to 5, hash % N moves a key unless hash % 4 == hash % 5, which holds for only 4 of every 20 hash values: 20% stay, 80% move. With consistent hashing, only the keys the new machine takes over move: about 1/5 = 20%.

Synthesizing vector architecture diagram...

Read it as a circle. Each key's hash lands between two tokens and belongs to the next token clockwise. Each node owns several tokens scattered around the ring, so adding a node steals a little from many others.

How many tokens per node? Cassandra used 256 for years. Since Cassandra 4.0 the default is 16, together with a token allocator that places them evenly. We use the same idea: a modest number of tokens, placed on purpose rather than at random.

Primitives: Consistent Hashing · Database Sharding & Partition Keys · Drill: Consistent hashing vnode skew

Step 1.4: Who Knows Where a Key Lives?

Synthesizing vector architecture diagram...

Solid lines are requests. Dotted lines are gossip. Routers keep a local copy of the ring and never ask anyone on the request path.

Primitives: Gossip Protocol & Failure Detection · API Gateway & Reverse Proxy · Drill: Gossip failure detector flapping

Step 1.5: A Machine Died and Took Its Keys With It

Synthesizing vector architecture diagram...

The walk skips B1 because AZ-b already has a copy on B2. The result is one copy per AZ, no matter how tokens happen to fall on the ring. Cassandra does the same with its NetworkTopologyStrategy, treating each AZ as a rack.

Step 1.6: When Is a Write Done?

Why the sets must overlap. Three nodes. A write lands on two of them. A read asks two of them. Two plus two is four, but there are only three nodes, so at least one node is in both sets. This is the pigeonhole principle.

Where this guarantee stops. "The read quorum overlaps the write quorum" is not the same as linearizability, the guarantee that the system behaves like one single copy where every read sees every write that finished before it. Cases the overlap doesn't cover:

• Two concurrent writes to the same key: both may succeed, and the newer timestamp wins. One update is silently lost.
• A write that failed after reaching only one replica: the client got an error, but a later read may or may not see the value.
• Clock trouble: in this round the version is the router's clock at write time. If one router's clock runs ahead, its writes "win" against writes that really came later.

That's acceptable here, because the requirement is eventual consistency. We promise less than we deliver most of the time, and we're honest about the cases above.

Synthesizing vector architecture diagram...

The router sends to all three at once, not to two. That way a slow node never delays the reply: the first two ACKs are enough.

Primitive: Distributed Consensus (Raft & Paxos) (leaderless quorums vs leader-based replication)

Round 1 Step Summary

R1.6 Architecture v1

Now the concepts get AWS names.

Synthesizing vector architecture diagram...

Follow a write from the top. The NLB spreads connections over six routers, two per AZ. A router hashes the key, finds the preference list (one node per AZ, for example A1, B2, C2), sends the write to all three, and answers after two ACKs. Each storage node runs the WAL-plus-LSM engine from steps 1.1 and 1.2 on an EBS gp3 volume. New SSTables are copied to S3, because a whole-cluster disaster (a bad bug, an operator mistake) is something replicas can't protect against.

Tracing one write: PUT cart:1001

1. The client's connection lands on a router through the NLB.
2. The router computes MurmurHash3("cart:1001"), walks the ring, and gets the preference list [B2, A1, C1].
3. It stamps the write with its clock as the version and sends it to all three.
4. Each replica appends to its WAL, fsyncs (group commit), inserts into its MemTable, and ACKs.
5. After two ACKs, the router returns 200 OK with the version.

Tracing one read: GET cart:1001

1. The router finds the same preference list.
2. It asks two replicas: the one in its own AZ (cheaper and faster) plus one other.
3. Each replica checks its MemTable, then Bloom filters, then reads at most a few 4 KB blocks.
4. If the two versions differ, the router returns the newer one.

Backups. Each new SSTable is uploaded to S3 once; SSTables never change, so backup is incremental by nature. We also force a MemTable flush at least every 10 minutes, so the backup is never far behind. S3 is designed for 11 nines (99.999999999%) of object durability. That number belongs to S3, not to our cluster.

R1.7 Numbers

We now put numbers on the requirements and check that the design fits them.

Targets

Traffic

We assume each daily user causes about 35 key-value operations a day: a session check per page view, cart reads, profile reads.

Storage

About 50 keys per user (session, cart, profile, preferences, flags):

Fleet

We choose 6 storage nodes, 2 per AZ, each an r7g.xlarge (Graviton, 4 vCPU, 32 GiB) with a 750 GB gp3 volume: 4.5 TB ÷ 6 = 750 GB.

Why not 3 big nodes, one per AZ? It would work. But when a node dies, its replacement must copy all its data from peers before it serves. At a throttled 100 MB/s:

• 1.5 TB per node: 1,500,000 MB ÷ 100 MB/s = 15,000 s ≈ 4.2 hours running on two copies.
• 750 GB per node: 7,500 s ≈ 2.1 hours.

Smaller nodes also mean a node loss touches half the keys instead of all of them. Six nodes is the smallest fleet that gets both.

Disk I/O per node at peak (pessimistic: we count every replica write as one disk operation, though group commit merges many):

When one node dies, its reads move to the replicas of its ranges in the other two AZs, and its writes simply aren't made. The survivors stay well under the baseline.

Memory per node

That fits in 32 GiB with plenty left for the OS page cache.

Network at peak: writes in 2,000 × 2 KB = 4 MB/s (32 Mbps), reads out 8,000 × 2 KB = 16 MB/s (128 Mbps), cross-AZ replication 2,000 × 2 KB × 2 copies = 8 MB/s (64 Mbps). Small.

Routers: 6 Fargate tasks (1 vCPU, 2 GB), two per AZ, about 1,700 requests/s each at peak.

Rough monthly cost (us-east-1 on-demand list prices; check the AWS Pricing Calculator before quoting):

Cross-AZ traffic is billed at $0.01 per GB in each direction, so $0.02 for every GB that crosses. CloudWatch and KMS add a little on top.

R1.8 Trade-Offs

Storage engine: LSM tree vs B+ tree vs in-memory

We pick the LSM tree because 20% of our traffic is writes and the data is bigger than RAM. A B+ tree is a fine choice for read-mostly data. At 1 TB, keeping everything in RAM costs far more for no requirement we have.

Request routers vs a smart client

A smart client library could hold the ring and talk to storage nodes directly, saving the extra hop (~0.3 ms). We choose routers because clients in any language then work over plain HTTP, and ring changes, auth and rate limits live in one place we deploy. We give up that 0.3 ms.

Leaderless vs leader-based replication

In a leader-based design, one replica per key range takes all writes and copies them to followers. Reads from the leader are consistent. But when the leader dies, writes to its range stop until a new leader is elected (seconds). In our leaderless design, any two of three replicas accept a write, so one dead node blocks nothing, at the price of copies that can disagree for a while. Our requirements chose availability and accept eventual consistency, so leaderless fits.

Our first consistency stance: we favor availability. As long as two of a key's three replicas are up, every request succeeds. Reads may be stale in the edge cases listed in step 1.6, and we tell callers so.

R1.9 Failure Modes

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance · Drill: Circuit breaker cascading thread stall

R1.10 Pillar Check

About IAM at the router. A service we build can't check an AWS SigV4 signature by itself, because it never sees the caller's secret key. A common pattern: the caller signs an STS GetCallerIdentity request and sends it to our router unsent; the router forwards it to STS, which replies with the caller's IAM role. The router caches that answer for the connection and checks the role against the table's allow list. HashiCorp Vault's AWS auth works this way.

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Asks scoping questions first, and says what each answer changes.
• Derives put / get / delete / TTL from the problem, and names what's out of scope.
• Builds up from one server, and gives a reason for every component: WAL, LSM, consistent hashing, replication, quorums.
• Explains W + R > N and why W = 2, R = 2 survives one node loss.
• Does back-of-the-envelope math and uses it to size the fleet.
• Names at least one cost of each choice.

Follow-up questions

1. "Why not R = 1 if eventual consistency is fine?" Answer: R = 1 would meet the requirement and cut read latency and load. We chose R = 2 because at this scale it costs little, and it means a client that just wrote usually reads its own write back, which session code tends to assume. If read load became the bottleneck, R = 1 is the first dial to turn, and we'd tell callers reads can be staler.

2. "What happens when the MemTable is full and the flush is slow?" Answer: the full MemTable becomes read-only and a new one takes writes while the old one flushes. If flushes keep falling behind, memory fills, so the engine must slow incoming writes (backpressure) rather than run out of memory.

3. "A key was written with TTL 1 hour. What does 'expire' mean on disk?" Answer: nothing is deleted at the hour mark. Reads check the expiry time and return 404 once it's past. Compaction drops the expired value later, when it rewrites that file. (Round 2 refines this: with deletes in play, an expired value is handled like a tombstone.)

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "It Becomes the Company-Wide Platform"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · 250K QPS peak · 103.5 TB provisioned · 99.99%

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built a key-value store for one product team: 10M daily users, about 10K requests per second at peak, about 1 TB of data, one region with three AZs, 99.9% availability, and eventual consistency. Each storage node writes to a write-ahead log and an LSM tree: a MemTable in memory, flushed to sorted SSTable files with Bloom filters, merged by leveled compaction. Keys are spread with consistent hashing and virtual nodes. Stateless routers hold the ring, which they learn by gossip, and send every write to three replicas, one per AZ. A write succeeds after two acknowledgments and a read asks two replicas, so W + R > N. Six storage nodes, six routers, about $2,100 a month. Two costs are still open: the quorum is one fixed setting for everyone, and two concurrent writes to the same key silently collide."

Architecture v1, compact

textCopy
 services ──► NLB ──► 6 routers (ECS Fargate, 2 per AZ)
                         │  MurmurHash3(key) → ring → preference list (1 node per AZ)
                         │  write to all 3, reply after W=2 ACKs · read R=2
             ┌───────────┼───────────┐
          AZ-a         AZ-b        AZ-c
         A1  A2       B1  B2      C1  C2      6 × r7g.xlarge, 750 GB gp3 each
          └── WAL → MemTable (64 MB) → SSTables + Bloom filters (leveled) ──► S3 backups
              ring + liveness shared by gossip (phi-accrual failure detector)

Round 1 step summary

Open costs: the fixed quorum; concurrent writes collide silently; the version is a router's wall-clock time.

R2.1 The Scope Raise

Interviewer: "Your store worked so well that every team in the company wants it. We're at 200M daily users, about 250K requests per second at peak. Values can be up to 1 MB now."

Candidate: "Does it still live in one region?"

Interviewer: "Yes. But it must survive losing an entire AZ, not just a node, and the target is 99.99%. Reads should be under 3 ms at P95 and 8 ms at P99."

Interviewer: "Also, teams keep asking for three things. Batch calls, because they fetch 50 keys per page. A choice of consistency per request: the feed team wants speed, the billing team wants the latest value. And 'only write if the version is still 4', so two workers don't overwrite each other."

Interviewer: "Last thing. Hundreds of teams share this now. One team's bug can't take down everyone else."

Scope change

The "Not yet" list from R1.2 is now mandatory: batch operations, per-request consistency, and conditional writes. And a new one: tenant isolation.

R2.2 What Breaks in the Round 1 Design

Before fixing anything, we say what fails and in what order we'll fix it.

The order we fix it in: consistency choices first (2.1–2.3), because they change the API. Then failure handling (2.4–2.6), then isolation (2.7). Sizing comes after the design, in R2.6.

R2.3 New Requirements and API Additions

Each new requirement changes the contract before it changes the internals.

Tables and tenants in the path. Every key now lives in a named table, and each table belongs to one team (a tenant). A table has quotas and settings.

httpCopy
PUT /v1/tables/carts/kv/cart:1001 HTTP/1.1
Content-Type: application/json
X-Consistency-Level: QUORUM
X-Idempotency-Key: a8f9c1d2-7e3b-4a55-8c01-9876543210ab

{ "value": { "items": ["book"] }, "ttl_seconds": 2592000 }

Table settings, as the platform stores them:

jsonCopy
{
  "table": "carts",
  "tenant": "checkout-team",
  "conflict_mode": "siblings",
  "conditional_writes": false,
  "default_consistency": "QUORUM",
  "quota": { "reads_per_sec": 20000, "writes_per_sec": 5000 },
  "max_value_bytes": 1048576,
  "sloppy_quorum": false
}

Consistency per request. A header, with the table's default when it's missing:

Conditional writes. Standard HTTP preconditions:

httpCopy
PUT /v1/tables/jobs/kv/job:5521 HTTP/1.1
If-Match: "4"
Content-Type: application/json

{ "value": { "state": "RUNNING", "worker": "w-17" } }

• If-Match: "4": write only if the current version is 4. Otherwise 412 Precondition Failed.
• If-None-Match: *: write only if the key doesn't exist yet (create-only). Otherwise 412.

This is why we never needed POST to create a key: "create only if absent" is a precondition on PUT, not a different verb.

Batch operations.

httpCopy
POST /v1/tables/profiles/kv:batch-get HTTP/1.1
Content-Type: application/json
X-Consistency-Level: ONE

{ "keys": ["user:10928", "user:10929", "user:10930"] }

jsonCopy
{
  "records": [
    { "key": "user:10928", "value": { "tier": "enterprise" }, "version": "1773648000123456789-0003" },
    { "key": "user:10929", "value": { "tier": "free" }, "version": "1773647990000000000-0000" }
  ],
  "unprocessed_keys": ["user:10930"]
}

httpCopy
POST /v1/tables/profiles/kv:batch-write HTTP/1.1
Content-Type: application/json

{
  "request_items": [
    { "put_item": { "key": "user:10931", "value": { "tier": "pro" } } },
    { "delete_item": { "key": "user:10932" } }
  ]
}

jsonCopy
{
  "unprocessed_items": [
    { "put_item": { "key": "user:10931" }, "reason": "PARTITION_THROTTLED", "retry_after_ms": 25 }
  ]
}

• Limits: up to 100 keys per batch-get; up to 25 items or 16 MB per batch-write (the same limits DynamoDB uses for BatchGetItem and BatchWriteItem).
• Partial success: the keys in one batch live on many different nodes. Some may time out or be throttled. We return what worked and list the rest as unprocessed_*, and the client retries only those, with backoff.
• Not atomic: each item commits on its own. All-or-nothing across keys would need a transaction protocol such as two-phase commit, which stays out of scope. See Two-Phase Commit & Saga.

Why POST only for batches. A batch is an action on many resources, not a replacement of one resource, so PUT doesn't describe it. 100 keys don't fit comfortably in a URL (proxies and load balancers often cap URLs at 2–8 KB), and a body on GET has no defined meaning in HTTP, so many proxies drop it. POST with a body models "do this action on these keys and tell me which ones worked."

Idempotency key. A plain PUT is safe to retry. A conditional one isn't: if the first attempt succeeded and the reply was lost, the retry sees version 5, not 4, and fails with 412 even though the write happened. The X-Idempotency-Key lets the router recognize the retry and return the first result. REL 3 · REL 4

Status codes, updated

R2.4 Design Evolution: Hardening the Platform

Step 2.1: Teams Need Different Consistency

Primitive: Distributed Consensus (Raft & Paxos)

Step 2.2: Two Writes Collided

Synthesizing vector architecture diagram...

Each write increments its own replica's counter. The first version is ahead on A1, the second on B1, so neither happened before the other. LWW would keep one; sibling mode keeps both and lets the client decide.

The rest of the path uses HLC too. Tombstones and read repair compare HLC timestamps. Keep clocks tight anyway: Amazon Time Sync on every node, an alarm at 10 ms of drift, and a node that drifts past 50 ms stops taking writes.

Go deeper: the vector-clock dominance rule

A clock V1 dominates V2 if V1[k] >= V2[k] for every replica k, and V1[k] > V2[k] for at least one. If neither dominates, the versions are concurrent. A record in sibling mode looks like this:

jsonCopy
{
  "key": "cart_84920",
  "siblings": [
    { "value": ["book"],        "vector_clock": { "node-A1": 4, "node-B1": 2 } },
    { "value": ["pen"],         "vector_clock": { "node-A1": 3, "node-B1": 3 } }
  ]
}

The client sends back the clocks it read (its context) with its next put, so the store knows that write has seen both siblings and can replace them.

Drill: Clock skew in ID generation (the same clock-going-backwards failure, in another system)

Step 2.3: Only Write If the Version Is Still 4

Synthesizing vector architecture diagram...

Worker 1's proposal loses because the replicas promised a higher ballot to worker 2. When worker 1 retries, it reads version 5, the condition "version is 4" is false, and its caller gets 412 Precondition Failed. Exactly one worker owns the job.

Primitive: Distributed Consensus (Raft & Paxos) · Drill: Distributed lock fencing token

Step 2.4: A Replica Is Down for Ten Minutes

Step 2.5: Replicas Drift Apart Silently

Synthesizing vector architecture diagram...

Start at the roots: they differ, so something below differs. The left halves hash to the same value on both nodes, so keys 0..128 are identical and are skipped without sending one key. Only the right half is synced, or split further in a deeper tree. Nodes that differ in a few keys exchange a few hashes plus those keys.

Why the digest read also saves money. The router sends the full read to the replica in its own AZ and the digest to a replica in another AZ. Only a 32-byte hash crosses AZs. If the digest replica turns out to be newer, the router fetches the full value from it: one extra round trip, only on a mismatch. COST 8

Step 2.6: How Do You Delete in a System That Never Forgets?

Step 2.7: One Tenant or One Key Is Hammering Us

Primitives: Distributed Rate Limiting · Distributed Cache Patterns & Eviction · Database Sharding & Partition Keys · Drills: Sharding tenant hotspot · Caching a hot product page

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Follow a request from the top. Route 53 resolves our endpoint name to the NLB (an alias record). The NLB spreads connections over about 30 router tasks in three AZs. A router enforces the table's quota, may answer a hot read from its 200 ms micro-cache, and otherwise hashes the key with MurmurHash3 and finds the preference list: one node in each AZ panel. Each storage node runs the engine panel: WAL, MemTable, SSTables with Bloom filters, a capped hint store and the Merkle repair job. New SSTables and WAL segments go to S3; metrics and traces go to CloudWatch and X-Ray.

Trace: a QUORUM write where one replica is down

Synthesizing vector architecture diagram...

The client gets its answer at step 7, as soon as two replicas ACK. The hint is saved after that and doesn't count toward W; it only shortens how long Rep3 stays stale.

Trace: a QUORUM read with read repair

Synthesizing vector architecture diagram...

The full value comes from the replica in the router's own AZ; only a hash crosses AZs. The router answers at step 6 and repairs Rep2 afterwards, so repair never adds latency to the read. The concession: with repair in the background, two back-to-back quorum reads can see the new value and then the old one (no monotonic reads), which is why Cassandra 4.0 made read repair blocking. We accept that for speed; tables that need monotonic reads can ask for blocking repair.

Hedged reads. A quorum read is only as fast as the slower of its two replicas. If the second answer hasn't arrived within 5 ms (a threshold we set near the 98th percentile of a single replica read, above the 3 ms read P95 target), the router sends the same read to the third replica and uses the first two answers. About 4% of reads hedge (the slower of two replicas passes the 98th percentile with probability 1 − 0.98² ≈ 4%), and read P99 stays near the threshold plus one replica read, about 6–8 ms. Writes don't need hedging: they already go to all three.

Go deeper: the per-operation execution matrix

Go deeper: the SSTable byte layout

textCopy
+------------------------------------------------------------------------------+
| Data block 0 (4 KB)  | ZSTD-compressed [KeyLen | Key | ValLen | Val | TS | Ver]
| Data block 1 (4 KB)  | ...
| ...                  |
+------------------------------------------------------------------------------+
| Bloom filter block   | bit array, m = 10 bits/key, k = 7 hash functions
| Index block          | sparse index: first key of each block → byte offset
| Meta index block     | pointers to the Bloom filter, stats and compression info
| Footer (fixed size)  | magic number | index offset | meta index offset
+------------------------------------------------------------------------------+

A reader opens the footer first, finds the index, binary-searches it for the one 4 KB block that could hold the key, and reads only that block. k = 7 hash functions is the best choice for 10 bits per key: (m/n) × ln 2 = 10 × 0.693 ≈ 7. Because SSTables never change after they're written, they're safe to cache, to share between readers without locks, and to back up incrementally.

R2.6 Numbers and Cost

Same method as R1.7, about 25 times bigger.

Traffic

Storage (3-year horizon)

The average record is smaller than Round 1's 2 KB because most of the new keys from other teams are small: flags, counters, sessions. We size on uncompressed bytes. ZSTD block compression usually shrinks JSON values 2–4 times, so compression is headroom, never something we depend on.

Network at peak

Memory

Why not cache the whole working set? If 20% of keys get 80% of reads, that's 4 billion keys, about 4.6 TB of RAM. Too expensive. The hottest 2% catches most of those reads.

Fleet

The 250 MB/s is for compaction's large sequential reads and writes. A quick check: each node takes in 50,000 × 3 × 1.15 KB ÷ 72 ≈ 2.4 MB/s of new data at peak. Leveled compaction rewrites data about 10–30 times, so about 24–72 MB/s of compaction writes plus a similar amount of reads, under the 150 MB/s compaction cap we set in R2.8. 250 MB/s also stays within the instance's baseline EBS bandwidth; throughput bought above what the instance can push is paid for and never used.

The 60% rule: why a 2.3× margin and not 1.2×. When an AZ goes dark, every key still has two replicas, but all the load that three AZs shared now lands on two: each surviving node's load rises 1.5 times. To survive that without launching anything (static stability), we run at no more than 60% at peak, because 60% × 1.5 = 90% still fits. REL 10

Checking the disks for an AZ loss at peak, with 48 surviving nodes:

The same pattern holds for CPU: at normal peak each node handles about (200,000 × 2 + 50,000 × 3) ÷ 72 ≈ 7,600 replica operations a second. We confirm with a load test that this keeps an r7g.2xlarge under 60% busy before we commit to the fleet; if it doesn't, CPU, not disk, sets the node count.

Monthly cost (one region, us-east-1 on-demand list prices; check the AWS Pricing Calculator before quoting exact figures):

About 60% of the bill is the storage fleet. The fleet runs 24/7 at a steady size, so a 3-year Compute Savings Plan takes roughly 40–50% off that line. COST 7 Spot Instances are never used for storage nodes: a 2-minute reclaim notice is shorter than a safe node drain.

Which numbers changed the design? The AZ-loss rule set the IOPS margin and the router count. The 1 MB value limit is why batch writes cap bytes (16 MB) as well as items (25 × 1 MB would be 25 MB). The fleet size (72) comes from disk, not from traffic. The per-key traffic of a viral key, not the total, forced step 2.7.

R2.7 Trade-Offs

Our CAP / PACELC stance: PA/EL. PACELC extends CAP: if there's a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

• During a partition (P): say AZ-c is cut off. Each key has two replicas on the side with AZ-a and AZ-b, so that side keeps serving QUORUM and ONE. The AZ-c side has one replica per key, so it serves ONE but returns 503 for QUORUM. We stay Available for any caller who accepts ONE; callers who asked for QUORUM get consistency or an error.
• Else (E), in normal operation: by default we favor Latency (parallel sends, hedged reads, no leader), unless the caller asks for QUORUM or a conditional write.
• Quorum overlap is not linearizability. Concurrent writers can still race under LWW, and sloppy-quorum tables lose even the overlap. True compare-and-set goes through the Paxos path.

Five decisions, defended on performance, cost and maintainability (the method is in the Trade-Off Analysis Playbook):

The DynamoDB estimate, derived (provisioned capacity with auto scaling at a 70% target, us-east-1 list prices; reserved capacity would lower it):

Two facts matter as much as the price. DynamoDB's maximum item size is 400 KB, so our 1 MB values would need to be split or stored in S3 with a pointer. And if the interviewer asks how DynamoDB works inside: it uses one leader per partition, elected with Multi-Paxos, and B-tree storage, not leaderless quorums. Our design follows the Dynamo paper and Cassandra, not DynamoDB.

R2.8 Failure Modes

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance · Reliability background: Reliability playbook

R2.9 Production Gotchas

1. The tombstone death spiral

• Symptom: a table's read P99 goes from 5 ms to seconds, and its disk usage keeps growing even though the team says it's deleting data.
• Cause: a queue-like pattern (insert, read, delete) or very short TTLs create millions of tombstones. Reads must step over them across many SSTables until gc_grace_seconds passes and compaction removes them. Lowering gc_grace_seconds without checking the repair schedule makes deleted keys reappear.
• Fix: keep gc_grace_seconds above the invariant from step 2.6 (3 days here, not the 10-day default some systems ship with); trigger a tombstone compaction when more than 20% of an SSTable is tombstones; move queue workloads to SQS or Kinesis.

2. Last-write-wins on wall-clock time

• Symptom: occasional lost updates nobody can reproduce.
• Cause: one node's clock drifted 50 ms ahead (NTP trouble, a paused VM), so its writes beat newer writes from healthy nodes.
• Fix: HLC timestamps (step 2.2); Amazon Time Sync on every node; alarm at 10 ms of drift and stop writes from a node past 50 ms; sibling mode or conditional writes where a lost update matters.

3. Unbounded retries

• Symptom: a short compaction stall turns into a full outage.
• Cause: callers retry 503s immediately and without limit, multiplying traffic several times over, exactly when the cluster is weakest.
• Fix: full-jitter exponential backoff in the SDK, circuit breakers that open when errors pass 10%, and a retry budget (retries at most 10% of requests) so retries can never multiply load.

4. Oversized MemTables

• Symptom: nodes get killed for running out of memory, or pause for seconds; the failure detector marks healthy nodes dead.
• Cause: someone raised the MemTable to 512 MB on a 16 GB node to cut flushes; several flush at once and memory runs out (on a JVM engine, long garbage-collection pauses too).
• Fix: cap total MemTable memory at 25% of RAM, with 64–128 MB per MemTable.

5. A sloppy quorum mistaken for strong consistency

• Symptom: a team reads right after a successful QUORUM write and gets the old value, during a node failure.
• Cause: the table had sloppy quorum on. The write's two ACKs came from a home replica and a stand-in node outside the preference list; the read asked two home replicas. The sets didn't overlap.
• Fix: sloppy quorum only as an explicit per-table setting labeled "eventual"; strict quorums (hints don't count toward W) for tables that promise read-your-writes.

R2.10 Pillar Check

Security in detail. Callers prove their IAM identity (the router verifies it through STS, as in Round 1; alternatively, VPC Lattice with IAM auth policies could front the routers in place of the NLB). IAM doesn't evaluate permissions for the actions of a service we built, so the router checks per-table permissions for GetItem, PutItem and DeleteItem in a policy store such as Amazon Verified Permissions. Multi-tenant tables add a rule that limits a caller to keys starting with its tenant ID, the same idea as DynamoDB's dynamodb:LeadingKeys condition. Storage nodes sit in private subnets; their security group admits only the routers and each other. Other teams reach the store through a PrivateLink endpoint, which an NLB-fronted service supports. TLS 1.3 from clients to routers; mutual TLS between routers and nodes and between nodes (gossip, hints, repair). EBS volumes and S3 backups are encrypted with KMS; tables holding personal data get their own customer-managed key, so access can be revoked and audited per table. EBS encryption calls KMS when a volume is attached, not on every I/O, so it doesn't add request latency. More on KMS envelope encryption in the Operational Excellence & Security playbook.

Operations in detail.

Every request carries a trace ID through router and replicas, sampled at 1% into X-Ray, and per-partition request counts are logged so hot keys can be found after the fact. OPS 4 · REL 6

Deploys respect quorum: one node at a time, one AZ at a time, never two replicas of the same range down together. The first node in each AZ is a canary that bakes for 30 minutes and rolls back automatically if its P99 or error rate moves. Conflict mode, hedging threshold and compaction rate are runtime settings, so a bad value is reverted in seconds. Monthly AWS Fault Injection Service experiments stop a node, pause I/O on a volume, and cut an AZ off, while dashboards confirm the SLOs held. OPS 6 · REL 8 · REL 12

Backups: each new SSTable goes to S3 once, from one replica per range. WAL segments ship every 60 seconds from all three replicas, because a write acknowledged by W = 2 may be missing from any single one; that interval is the backup RPO. Uploads use an S3 gateway endpoint, which is free and keeps backup traffic off NAT gateways. Backups are copied to a second region and encrypted with KMS. Once a week, a job restores a random table into a scratch cluster and compares row counts and checksums, because an untested backup is not a backup. REL 9

R2.11 Round 2 Rubric and Follow-Ups

What a strong senior (L6) answer adds over L5

• Starts with "what breaks" and fixes it in a stated order.
• Offers consistency per request and explains exactly where W + R > N stops (not linearizable, sloppy quorum breaks it).
• Handles conflicts with HLC and knows when vector clocks and siblings are worth it; knows compare-and-set needs consensus.
• Explains hints, read repair and Merkle anti-entropy, and the tombstone gc_grace_seconds rule.
• Sizes the fleet for an AZ loss (the 60% rule) and checks the disks after the loss.
• Volunteers the monthly cost, the DynamoDB alternative, and the concession behind each choice.

Follow-up questions

1. "Two clients increment the same counter under eventual consistency. How do you avoid losing updates?" Answer: store it as a PN-counter CRDT (conflict-free replicated data type). Each replica keeps its own running total of increments and of decrements. Merging two copies takes, for each replica, the larger of the two totals, so merges can happen in any order, any number of times, and all copies converge without locks. The counter's value is the sum of increments minus the sum of decrements. If the counter needs a strict limit, such as stock that must not go below zero, use a conditional write through the Paxos path instead.

2. "Why leveled compaction instead of size-tiered for this workload?" Answer: size-tiered compaction merges files of similar size, so several overlapping files can exist per tier and a read may check 4–8 files. Leveled compaction keeps each key in at most one file per level below L0, so a read checks about one file per level, 4–5 in total, and Bloom filters keep actual disk reads near one. That protects the 8 ms read P99. The price is more compaction writes (10–30× write amplification), which our 250 MB/s per node covers (R2.6).

3. "The budget is cut by 30%. What do you change first?" Answer: 30% of ≈ $39K is about $11.7K. A 3-year Savings Plan takes roughly $9–11K off the $22.5K instance line, and ZSTD on replication traffic saves about $1K more; together that's close to the target without changing the design. If more is needed, moving from EBS to instance-store NVMe removes most of the $10K EBS line, though storage instances with local NVMe (such as r7gd or i4g) cost more per hour, which gives part of it back, and node replacement gets slower (R2.7). We would not cut the AZ headroom: that's what the 99.99% target pays for.

Interview gotchas from this round's wrong answers

---

Round 3 · Architect · "It Goes Global"

~45 min · Principal (L7) · multi-region active-active · 1B MAU · ~1M QPS peak across regions · 99.999% for top-tier tables

R3.0 Where We Left Off

What the candidate says in the first 60 seconds of Round 3, and everything you need if you start here.

Round 2 in 60 seconds. "We run the company-wide key-value platform in one region across three AZs: 200M daily users, 250K requests per second at peak, 23 TB of data provisioned as 103.5 TB, 99.99% availability. 72 Graviton storage nodes, 24 per AZ, each with an LSM engine on 1.5 TB of gp3 at 6,000 IOPS, and about 30 stateless routers. Every key has three replicas, one per AZ. Callers pick consistency per request: ONE, QUORUM or LOCAL_QUORUM. Conflicts resolve by last-write-wins on a hybrid logical clock, or by vector-clock siblings for tables that opt in; conditional writes go through Paxos. Missed writes are caught up by hints, read repair and Merkle anti-entropy; deletes are tombstones kept 3 days. We run at 60% at peak so losing an AZ fits. It costs about $39K a month. Our stance is PA/EL: under a partition, ONE keeps working everywhere and QUORUM works on the majority side; in normal operation we favor latency. Two costs are open: the whole platform lives in one region, so one region is one blast radius; and we have no answer for data residency or restoring a table to a point in time."

Architecture v2, compact

textCopy
 services ─► Route 53 ─► NLB ─► ~30 routers (Fargate, 3 AZs)
                                  quotas · micro-cache · HLC · Paxos for conditional writes
                                  MurmurHash3 → preference list (1 node per AZ) · W/R per request
        ┌─────────────────────────┼─────────────────────────┐
     AZ-a: 24 nodes           AZ-b: 24 nodes           AZ-c: 24 nodes     r7g.2xlarge · 1.5 TB gp3 · 6,000 IOPS
        └── WAL → MemTable → SSTables (leveled, Bloom) · hints (3 h) · Merkle repair (6 h) · tombstones (3 d)
            ──► S3: SSTables + WAL every 60 s (copied to a 2nd region) · CloudWatch + X-Ray

Rounds 1–2 step summary

R3.1 The Scope Raise

Interviewer: "The company is now global. 1 billion monthly users on every continent, and every product runs on your store. Peak is around a million requests per second, summed across regions."

Interviewer: "Users in Tokyo are complaining that every call takes 150 ms. And leadership wants 99.999% for the tables behind login and payments, which means surviving the loss of a whole region."

Candidate: "Does every table need that?"

Interviewer: "No. Let each team choose how much data it can lose and how long it can be down. But some tables hold EU customers' personal data and must stay in the EU. And after last quarter's incident, where a bad script corrupted a table, teams want to restore a table to how it looked at a point in time."

Scope change

RPO (recovery point objective) is how much recent data we may lose, measured in time. RTO (recovery time objective) is how long recovery may take.

R3.2 What Breaks in the Round 2 Design

The order we fix it in: geography and replication first (3.1–3.2), then residency (3.3), then disaster recovery and restore (3.4), then blast radius (3.5), then the question of whether we should run this at all (3.6).

R3.3 New Requirements and API Additions

Global table configuration. A table now says where it lives and how it recovers:

jsonCopy
{
  "table": "profiles",
  "tenant": "identity-team",
  "regions": ["us-east-1", "eu-west-1", "ap-northeast-1"],
  "conflict_mode": "lww",
  "write_mode": "multi_region",
  "dr_tier": "active_active",
  "rpo_target_seconds": 1,
  "rto_target_seconds": 180,
  "pitr": { "enabled": true, "retention_days": 7 }
}

A table that needs compare-and-set across the world gets a home region, where all its writes go:

jsonCopy
{
  "table": "payment_idempotency",
  "regions": ["us-east-1", "eu-west-1", "ap-northeast-1"],
  "write_mode": "home_region",
  "home_region": "us-east-1",
  "conditional_writes": true,
  "dr_tier": "active_active"
}

A residency table is pinned to its jurisdiction, backups included:

jsonCopy
{
  "table": "eu_customer_pii",
  "regions": ["eu-west-1"],
  "residency": "EU",
  "backup_regions": ["eu-central-1"],
  "kms_key_region": "eu-west-1",
  "dr_tier": "backup_restore",
  "rpo_target_seconds": 60,
  "rto_target_seconds": 14400,
  "pitr": { "enabled": true, "retention_days": 35 }
}

Placement can also go one level finer, by key prefix inside a table ("placement_rules": [{ "key_prefix": "eu:", "regions": ["eu-west-1"] }]). That keeps one table for a global product but makes the replicator check every key against the rules. We offer it, and recommend separate tables when a team can split its data cleanly.

Consistency levels on a multi-region table

A request in the wrong region. If a caller in us-east-1 asks for a key in eu_customer_pii, the router doesn't proxy it: proxying would move EU personal data through the US. It answers:

httpCopy
HTTP/1.1 421 Misdirected Request
Content-Type: application/json

{ "error": "TABLE_NOT_IN_REGION", "table": "eu_customer_pii", "regions": ["eu-west-1"] }

The SDK reads table placement at startup, so in practice callers go to the right regional endpoint directly.

Point-in-time restore. Restore always creates a new table, so a restore can never overwrite live data by mistake (DynamoDB's PITR works the same way):

httpCopy
POST /v1/tables/orders:restore HTTP/1.1
Content-Type: application/json

{
  "restore_to_time": "2026-09-24T14:04:59Z",
  "target_table": "orders_restored_0924",
  "target_region": "us-east-1"
}

httpCopy
HTTP/1.1 202 Accepted
Content-Type: application/json

{
  "restore_id": "rst_8c21",
  "status": "RUNNING",
  "earliest_restorable_time": "2026-09-17T14:05:00Z",
  "latest_restorable_time": "2026-09-24T15:40:00Z"
}

The caller polls GET /v1/restores/rst_8c21 until the status is COMPLETED, checks the new table, then swaps its application over or copies back the rows it needs. latest_restorable_time trails "now" by up to the 60-second WAL shipping interval.

R3.4 Design Evolution: Going Global

Step 3.1: Users Are Far Away and a Region Can Die

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active

Step 3.2: Two Regions Changed the Same Key

Drill: Replication multi-region consistency

Step 3.3: This Data May Not Leave the Country

Step 3.4: A Region Is Gone. Now What?

The region evacuation procedure (practiced quarterly, see R3.9):

1. Detect: Route 53 health checks fail for us-east-1; the cross-region replication-lag alarm fires in the surviving regions.
2. Traffic moves on its own: latency routing stops answering with us-east-1; callers land in eu-west-1 and ap-northeast-1.
3. Confirm capacity: both survivors were sized for this (R3.6). Check routers are scaling and quota alarms are quiet.
4. Home-region tables: fence us-east-1 for those tables (bump their epoch), promote eu-west-1 as home. Their writes resume there.
5. Tables pinned to us-east-1: start restores from their backup region, in order of tier and business priority.
6. Tell callers what to expect: reads may be up to the replication lag behind; some single-region tables are down.
7. Failback, later: the recovered region rejoins by cross-region anti-entropy first, and only then gets traffic back from Route 53. Home tables move back only on purpose, never automatically.

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active · REL 13

Step 3.5: One Bad Deploy Took Down Everything

Synthesizing vector architecture diagram...

Each wave reaches more of the fleet only after the previous one has run under real traffic without alarms. A bug that shows up in wave 1 has hit one cell in one region.

Primitive: Circuit Breaker, Bulkhead & Fault Tolerance (a cell is a bulkhead at fleet scale) · OPS 6 · REL 10

Step 3.6: Should We Even Run This Ourselves?

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Start at the top. Route 53 answers each caller with its nearest healthy region. Inside a region, the NLB feeds a thin cell router, which sends each table's requests to the one cell that holds it. Each cell is the full Round 2 design. Global tables replicate asynchronously between the matching cells of the three regions (drawn for cell 1; the others work the same way). EU-pinned tables live only in eu-west-1, and their backups go only to eu-central-1.

Trace: a write that replicates to another region

Synthesizing vector architecture diagram...

The caller's answer (step 4) doesn't wait for other regions. The streamer ships in the background and moves its checkpoint only after each peer region confirms. The time between steps 4 and 8 is the replication lag, and it's the RPO of an active-active table.

Trace: a region failover

Synthesizing vector architecture diagram...

Detection takes about 30 seconds and callers follow within their DNS TTL, so active-active tables are back in 1–3 minutes. Writes that reached us-east-1 but weren't shipped yet (about the last second) are missing from the other regions. If us-east-1 comes back with its disks, they ship then and conflict rules merge them; if its data is gone, they're lost. That window is the RPO.

R3.6 Numbers and Cost

Traffic

Every product now uses the store, so each daily user causes about twice Round 2's operations.

The regions peak at different hours of the UTC day, so the whole world never hits 1M at the same moment. But each region must be sized for its own peak, so capacity adds up to about 1M.

Data

Fleet per region

The fleet is sized by disk again. Is it big enough for traffic, including a region failover? Two checks for us-east-1, our busiest region.

Writes applied in a region are its own writes plus the global-table writes replicated in from the other two. Average global-table writes elsewhere: eu-west-1 120K × 20% × 80% = 19.2K/s, ap-northeast-1 the same.

Both stay under Round 2's per-node load at peak (6,000-IOPS disks, about 7,600 replica operations a second), which we already sized at 60%. So the region-loss headroom costs no extra storage nodes: the fleet was bigger than traffic needed because of disk. The same check for eu-west-1 or ap-northeast-1 taking half of us-east-1's peak (500K) gives about 41% disk and 6,400 replica operations per node. Losing an AZ at normal peak still fits too (the same method as R2.6 gives about 58% disk use on the 120 surviving nodes). The router tier, which is sized by traffic, is where failover capacity costs money: 66 tasks in us-east-1 (sized for 550K) and 60 each in the other two (sized for 500K, their peak plus half of us-east-1's 400K).

Cross-region replication

At peak hours it's higher; if all regions peaked together, 2.5 times the average (≈ 2.9 Gbps) is the ceiling.

A 12-hour split between regions leaves each streamer replica holding unsent mutations. us-east-1's global writes are 25.6K/s × 1.15 KB ≈ 29.4 MB/s, spread over 180 nodes: about 0.16 MB/s per node. The commit log is kept until both destination checkpoints pass it, so the backlog is about 7 GB per node after 12 hours. We keep up to 24 hours of backlog on a dedicated volume; beyond that, the cross-region Merkle comparison takes over.

Monthly cost, worldwide (us-east-1 list prices used for every region as a floor: other regions list higher; check the AWS Pricing Calculator):

Where the cross-AZ figure comes from: each region applies its own writes plus the global writes from the other two. us-east-1 applies 32K + 19.2K + 19.2K = 70.4K/s on average; each other region 24K + 25.6K + 19.2K = 68.8K/s.

Compared with Round 2's ≈ $39K: traffic grew 4×, provisioned storage 7.8×, cost about 7.6×. This is a storage-bound fleet, so cost follows the number of copies we keep. The biggest new line is cross-region transfer, but the biggest increase is the storage fleet, because global tables now exist three times. The obvious levers: a 3-year Savings Plan takes roughly 40–50% off the $169K instance line COST 7, and ZSTD on the replication stream roughly halves the transfer lines.

Active-active vs active-passive, in numbers. Storage nodes plus EBS cost about ($56.3K + $25.2K) ÷ 60 TB ≈ $1.36K per raw TB per region copy per month. The global tables hold 55.2 TB.

Because the fleet is sized by disk, a warm standby saves less than people expect: it still needs every byte on disk. It saves more only if the standby uses denser storage (fewer, bigger nodes) and accepts that scale-up takes longer. So the real money decision is how many regions each table lives in, table by table.

Availability. 99.999% allows about 5.26 minutes of downtime a year. Two independent regions each at 99.99% would, on paper, both be down only 0.0001 × 0.0001 = 0.00000001 of the time. Real outages are rarely independent: a bad deploy, a shared config, or a global dependency hits every region at once. That's why cells and waves (step 3.5) matter more than the multiplication. Only tables on the active-active tier can meet 99.999%; tables that choose a cheaper tier accept a lower target, in writing.

R3.7 Trade-Offs

Closing the loop on the track's question. In Round 1 we chose availability once, for everyone. In Round 2 each request chose. Now:

• Each table chooses its regions, its conflict rule and its recovery tier.
• In each region, the same table can behave differently: a home-region table accepts writes only in its home. During a split between regions, a global LWW or CRDT table keeps accepting writes everywhere (PA), while a home-region table refuses writes outside its home (PC). In normal operation, local quorums keep latency low (EL), while home-region writes from far away pay for consistency with latency (EC).

So the honest answer to "consistent or available?" is: per table and per region, chosen by the team that owns the data, with the cost written down.

R3.8 Failure Modes

Drills: Replication multi-region consistency · Raft split brain (why the old home region must be fenced before a new one takes writes)

R3.9 Runbook and Incident Response

Golden signals, per region and per cell OPS 8 · REL 6

Incident flow SEC 10

Synthesizing vector architecture diagram...

The first question is always the blast radius. Cells, AZs and regions each have a prepared response, so the on-call engineer picks one instead of inventing one.

Game days. Monthly, AWS Fault Injection Service stops nodes, pauses EBS I/O and cuts an AZ off in one region, while dashboards confirm the SLOs held. Quarterly, we evacuate a whole region during business hours and fail back. Anything that didn't go to plan gets a blameless Correction of Error (COE) with owners and dates. OPS 11 · REL 12

Restore testing. Weekly, an automated job restores a random table to a random point in time into a scratch cell, in a different region from the source, and compares row counts and checksums against the source at that time. This also proves the KMS keys and cross-region backup copies work. REL 9

Go deeper: CLI playbook

Plain commands an on-call engineer runs, one at a time. Replace the IDs with real ones.

textCopy
# 1. Storage node health in one region
aws ec2 describe-instances --region eu-west-1 --filters Name=tag:Service,Values=kvstore-storage --query "Reservations[].Instances[].[InstanceId,State.Name]"

# 2. A node's engine metrics: look for compaction_backlog, l0_tables, hints_pending, streamer_backlog_bytes
curl -s http://storage-node-01.kv.internal:8080/metrics

# 3. Route 53 health check status for a regional endpoint
aws route53 get-health-check-status --health-check-id 1a2b3c4d-5e6f-7a8b-9c0d-111122223333

# 4. Replication lag for the last 15 minutes (query defined in the JSON file)
aws cloudwatch get-metric-data --region us-east-1 --metric-data-queries file://replication-lag-query.json --start-time 2026-09-24T14:00:00Z --end-time 2026-09-24T14:15:00Z

# 5. Raise IOPS on a saturated gp3 volume, with no downtime
#    (a volume allows at most 4 modifications in any 24 hours, so raise it well above need)
aws ec2 modify-volume --volume-id vol-0a1b2c3d4e5f67890 --iops 10000

# 6. Newest WAL segments for a table in its backup bucket (backup freshness)
aws s3 ls s3://kv-backups-eu-central-1/eu_customer_pii/wal/ --recursive --region eu-central-1

# 7. Start a game-day experiment from a prepared template
aws fis start-experiment --experiment-template-id EXT1a2b3c4d5e6f7

To force a tombstone compaction on a delete-heavy table, the node's admin API takes:

httpCopy
POST /admin/compact HTTP/1.1
Host: storage-node-01.kv.internal:8080
Authorization: Bearer <operator token>
Content-Type: application/json

{ "table": "user_profiles", "force_tombstone_purge": true }

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Turns "survive a region" into a per-table decision with a price, instead of one answer for all data.
• Thinks in blast radius: cells, waves, fencing, and failures that hit every region at once.
• Knows where DNS failover stops and what else a failover needs (capacity, quotas, keys, home-region promotion).
• Prices the whole fleet, finds what drives the cost (copies of data, not traffic), and says which lever moves it.
• Makes build vs buy an organizational decision (team, on-call, features), not a technical preference.
• Sets the rules other teams follow: table tiers, residency placement, default consistency levels.

Follow-up questions

1. "A user updates their email in Europe, then their next request lands in the US and shows the old email. What do you do?" Answer: first, keep each caller sticky to one healthy region, which removes most cases. For flows that must read their own writes, the SDK sends back the version it last wrote. A router whose replica is older than that either waits a few hundred milliseconds for replication or forwards the read to the region that took the write. We don't make every read cross-region; only the reads that ask for it pay.

2. "eu-west-1 is down. Legal says EU data can't leave the EU. What happens to EU customers?" Answer: tables pinned to eu-west-1 are unavailable until eu-west-1 returns or we launch a cluster in eu-central-1 and restore them from the backups we keep there, which takes hours. That was the table owners' choice when they picked the backup-and-restore tier. If that downtime isn't acceptable, the fix is a second EU region running active-active for those tables, and we can price it: about $1.36K per raw TB per month for the extra copy, plus transfer.

3. "Cut the global bill by 30%." Answer: 30% of ≈ $306K is about $92K. A 3-year Savings Plan on the steady storage fleet saves roughly $68–84K of the $169K instance line. The rest comes from copies: moving global tables that don't need a Tokyo copy from 3 regions to 2 saves about $1.36K per raw TB per month. We'd leave cells, AZ headroom and the top-tier tables alone, since those are what the 99.999% target pays for.

---

Track Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening a round: "Before I design, let me ask a few scoping questions."
• When the scope is raised: "Here's what breaks in the current design, and here's the order I'll fix it in."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels