Technologies referenced in this case study: Cassandra · DynamoDB · PostgreSQL · ZooKeeper & etcd · Kafka

Related: Consistency Models · Consistent Hashing · Sharding · Distributed Consensus · Database Sharding · Degraded Mode

How to Use This Case Study#

Organized for interview use first, reference second. Read front-to-back once, then return to individual sections before a loop.

Without an explicit consistency contract:
t=0:       User updates shipping address in us-east (leader)
t=+5ms:    Write acked after local commit only (async replication)
t=+40ms:   User's next page load is routed to a us-west follower (lag: 900ms)
t=+40ms:   Page shows the OLD address. User re-submits the edit.
t=+2s:     Order placed. Fulfillment reads from a follower that is 30s behind
           after a replication stall. Package ships to the old address.
t=+3 days: Support ticket. Nobody can reproduce it. "Eventual consistency."

With an explicit contract (read-your-writes + leader-read for money paths):
t=0:       Same edit. Response carries a commit token (LSN 88121934).
t=+40ms:   Follower sees token > applied LSN → waits up to 50ms or proxies to leader.
t=+40ms:   User sees the new address. No re-submit.
t=+2s:     Order service reads with 'linearizable' flag → leader. Correct address.
           Replication lag is a dashboard number, not a customer-facing bug.

Executive Summary

If you only read one section, read this. Every decision in the case study follows from the contrast and the fault lines below.

What This Interview Actually Tests#

A replicated data store is not a "how do I copy bytes" question. Everyone can draw a leader and two followers.

It is an anomaly-budgeting question that tests:

• Whether you name the consistency guarantee per operation instead of per system
• Whether you know which anomaly each topology exposes (stale read, lost update, write skew, resurrected delete)
• Whether you can state an RPO and RTO in numbers and name who signed off on them
• Whether failover is designed as the most dangerous routine operation you run — because it is

The key insight: Replication is a contract about which lies the system is allowed to tell, to whom, for how long. Staff engineers write that contract down; Senior engineers discover it in a post-mortem.

The L5 vs L6 Contrast — Start Here#

The Staff Positions#

The Three Intents#

Three intents produce three incompatible stores. Name one before drawing a box.

🎯 Staff Move: "I'll design for user-facing read scale with a system-of-record core: single leader per shard, Raft inside the home region, async followers in other regions, and read-your-writes via commit tokens. The few operations that need linearizability — uniqueness checks, balance mutations — go to the leader. I'm deliberately not building multi-leader; if product needs writes during a regional partition, that's a separate conversation about which data types can merge."

The Five Fault Lines#

In the Wild: Real Production Systems#

Why this section belongs here: Naming the real design and the real reason it was built that way shows you have studied operational reality, not a textbook diagram.

Amazon Dynamo — Always-Writable Shopping Cart#

Amazon's 2007 Dynamo paper describes a leaderless, consistent-hashing store built so that the shopping cart would always accept writes, even during failures. It used tunable N/R/W quorums, sloppy quorums with hinted handoff to keep writing when preferred replicas were down, vector clocks to detect concurrent versions, and Merkle trees for anti-entropy. Conflicting cart versions were returned to the application, which merged them — the paper notes that deleted items could reappear as a result.

Staff insight: Dynamo is the canonical example of choosing an intent first. "Add to cart must never fail" was a business decision, and the resurrected-item anomaly was the explicitly accepted cost. Cassandra and DynamoDB are descendants, but DynamoDB (the service) hides most of this behind a single-leader-per-partition design — which tells you how much operational pain the original model carried.

Google Spanner — Paying Latency for External Consistency#

Spanner replicates each data split with Paxos across zones or regions and uses TrueTime — GPS and atomic clocks exposing an explicit uncertainty interval, typically a few milliseconds — to assign commit timestamps. Transactions "commit-wait" out the uncertainty before becoming visible, giving external consistency (linearizability for transactions) globally.

Staff insight: Spanner shows linearizability is purchasable, and shows the price: commit-wait of roughly the clock uncertainty (single-digit ms) plus a cross-region Paxos round (tens of ms) on multi-region configurations. When an interviewer says "can't we just have strong consistency everywhere?", the answer is "yes — here is the latency bill and the hardware bill."

Facebook TAO / Memcache — Regional Leader with Read-Your-Writes Patches#

Facebook's published TAO and memcache papers describe a design where one region is the leader for a given shard's writes, other regions hold async replicas and caches, and writes are forwarded to the leader region. To avoid users seeing their own writes disappear, the memcache design used "remote markers" to route a user's reads for recently written keys to the leader region until replication caught up.

Staff insight: At the largest scale, the answer was not stronger replication; it was a session guarantee patched on top of async replication for the one anomaly users actually notice — not seeing their own write. That is the exact Staff default in this case study.

What Interviewers Probe#

System Architecture Overview#

Reading the diagram: Writes always go to the shard leader in the home region and commit when 2 of 3 in-region replicas persist them (2–4ms). Remote regions receive the log asynchronously (lag p99 < 1s). Reads carry the session's commit token: a remote follower serves the read only if it has applied at least that LSN, otherwise it waits briefly or proxies to the leader. Linearizable reads go to the leader holding a valid lease. The failover controller owns epochs in etcd; anti-entropy catches the divergence read repair never sees.

Quick-Reference: The 30-Second Cheat Sheet#

Key Numbers Worth Memorizing#

Interview Walkthrough

The most common mistake: Candidates spend 20 minutes on partitioning schemes and storage engines (LSM vs B-tree) and never reach the question the interviewer cares about — what users observe while replicas disagree, and what happens during failover. Compress the basics to 10–12 minutes.

Phase 1: Requirements & Framing (2–3 minutes)#

State the functional scope in one sentence:

"A key-value / document store with get, put, conditional put, and delete, replicated across three availability zones in a home region and readable from two other regions."

Then spend the time on the non-functional contract — this is where the design is decided:

"Three questions shape everything. First, what's the durability promise — can we lose any acknowledged write? Second, which reads must be fresh? Third, must writes succeed in a region that's partitioned from the home region? I'll assume: zero acked-write loss for a region-internal failure, a few seconds of RPO for losing a whole region, read-your-writes for users, and writes may fail on the minority side of a partition."

Commit to numbers:

"Targets: write p99 < 10ms in the home region, read p99 < 5ms from local region replicas, 99.99% read availability, 99.95% write availability, RPO = 0 for AZ loss, RPO ≤ 5s for region loss, RTO ≤ 30s for leader loss and ≤ 15 min for region evacuation."

🎯 Staff Move: Say the RPO and RTO in seconds and say who has to sign off on them. "RPO ≤ 5s on region loss means a customer can lose their last few seconds of edits in a regional disaster. Product and legal sign that, not the database team."

Phase 2: Core Entities & API (1–2 minutes)#

• Record: key, value, version (per-key monotonic or HLC), tombstone flag
• Shard / Range: key range → replica set → leader, epoch
• Commit token: (shard_id, log_index) returned on every write

PUT    /kv/{key}   body, If-Match: <version>          → 200 { version, commit_token }
GET    /kv/{key}?consistency=linearizable|session|eventual
       X-Commit-Token: <token>                         → 200 { value, version, served_by, staleness_ms }
DELETE /kv/{key}   If-Match: <version>                 → 200 { commit_token }

🎯 Staff Move: "Consistency level is a parameter on the read API and a documented field in each calling team's API spec. It's not a cluster-wide config. And every response returns staleness_ms so callers can see the lie they were told."

Phase 3: High-Level Architecture (≤5 minutes)#

Walk the flow in 90 seconds:

1. Key hashes to a range; the router caches the range → leader map (epoch-versioned, from etcd).
2. Writes go to the leader, append to the Raft log, commit on 2 of 3 in-region acks (2–4ms), return a commit token.
3. The log ships asynchronously to remote-region followers.
4. Reads: linearizable → leader with valid lease; session → any replica whose applied index ≥ token; eventual → nearest replica.
5. Anti-entropy runs in the background; failover controller owns epochs.

🎯 Staff Move: "This is the reasonable design. What makes it production-grade is three things: what a read sees during lag, what happens during failover, and how divergence is detected when nobody reads the data. Which do you want first?"

Phase 4: Transition to Depth (1 minute)#

"The topology is table stakes. The decisions that matter are: (1) where the linearizability boundary is and what it costs, (2) how failover avoids split brain and accounts for lost writes, and (3) what we do if product later demands writes during a region partition. I'd start with failover — it's where replicated stores actually lose data."

Phase 5: Deep Dives (25–30 minutes)#

Pattern for each: state the tradeoff → pick a position → quantify → name who pays.

Deep dive A: Failover without split brain (6–8 min)

"Leader loss detection: followers stop receiving heartbeats; after the election timeout — 3–5 seconds in-region — a follower with an up-to-date log starts an election for term T+1 and wins with a majority. The old leader, if it's merely paused, still believes it's leader. Two defenses: leader leases — the old leader stops serving linearizable reads when its lease (shorter than the election timeout, minus a clock-drift margin) expires; and fencing — every write carries the term, and replicas reject terms lower than the highest they've seen. A GC-paused leader that wakes up at term 41 cannot commit, because no majority accepts term 41 anymore."

"In-region RPO is zero: the new leader has every majority-committed entry by construction. Cross-region is different: if the entire home region is lost, remote followers are up to lag behind. At p99 lag < 1s we lose ≤ 1s of writes; during a replication stall we could lose minutes. That's why cross-region promotion is human-gated: someone must decide that losing the tail is better than waiting."

Deep dive B: Read-your-writes across regions (5–7 min)

"Every write returns (shard, log_index). The client library stores the max per shard in the session cookie. A remote follower receiving a read with token 88,121,934 checks its applied index. If it's caught up, serve. If not: wait up to 50ms, then proxy to the leader region (+80ms). At p99 lag of 1s, about 1–3% of post-write reads take the slow path — we measure it as session.token_wait_ms and session.leader_proxy_rate."

"Monotonic reads come free with the same token: the client never accepts a replica older than its high-water mark, so it can't see time go backwards when the load balancer bounces it between replicas."

Deep dive C: The quorum trap and conflict resolution (5–7 min)

"If the interviewer pushes toward leaderless: R+W>N guarantees that a read quorum intersects the write quorum of a completed write. It does not make concurrent operations linearizable, and with sloppy quorums during partitions the intersection doesn't hold at all. And once two writers can write the same key, I need a conflict policy. LWW with wall clocks silently drops the write with the smaller timestamp — with 20ms skew, a write made 15ms later can lose. For a cart I'd use an observed-remove set CRDT; for counters a PN-counter; for arbitrary documents, version vectors with siblings returned to the app for merge. Each has a product owner who must accept its semantics."

Deep dive D: Anti-entropy (3–5 min)

"Read repair fixes divergence only on keys that are read. Cold keys need scheduled Merkle-tree comparison: each replica builds a hash tree per range, compares roots, and descends only into differing subtrees — for 1 billion keys with a depth-15 tree we exchange ~32K leaf hashes to localize differences. It must complete within the tombstone GC window, or a replica that missed a delete will resurrect the data after the tombstone is purged elsewhere."

Phase 6: Wrap-Up (2–3 minutes)#

"Replication is a contract about which anomalies users can see. I put linearizability only where uniqueness and money live, session guarantees where users would notice, and eventual everywhere else — each with a published staleness number. The organizational point: consistency level is part of each team's API contract, reviewed like a schema change, and failover is rehearsed quarterly because a path we exercise twice a year is a path that doesn't work."

"What I'd build later: a multi-writer tier restricted to CRDT types for the two or three products that truly need partition-tolerant writes, and follower reads with bounded staleness (AS OF 10s) for analytics."

🎯 Staff Move: End on ownership and rehearsal, not on another component.

Common Timing Mistakes#

1. The Staff Lens#

1.1 Why This Problem Exists in Staff Interviews#

Replicated stores sit under every other system the company runs. A Senior engineer can make one correct; a Staff engineer decides which anomalies the whole product is allowed to expose and makes sure somebody owns each one. The question also reveals operational scar tissue fast: anyone who has lived through a failover that lost data answers differently from someone who has read about it.

The five behaviors interviewers listen for:

1. Consistency named per operation, with a reason
2. RPO/RTO stated in numbers with a named approver
3. Failover walked through with fencing
4. Quorum arithmetic stated precisely (overlap, not linearizability)
5. Anti-entropy and deletes handled explicitly

1.2 The L5 vs L6 Contrast — Visual#

1.3 The Staff Question That Cuts Through Everything#

"The leader in us-east just stopped responding. Walk me through the next 60 seconds. Which writes are lost, which reads are wrong, who finds out, and how does the old leader learn it's no longer leader?"

A candidate who answers with terms, leases, fencing, and a number for lost writes has operated one of these. A candidate who says "we promote a replica" has not.

2. Problem Framing & Intent#

2.1 The Three Intents — Explained#

System of record → consensus, linearizable, write-unavailable on the minority

• Constraint: an acknowledged write is never lost; invariants (uniqueness, non-negative balance) never violated
• Mechanism: Raft/Paxos per shard, majority commit, leader leases, conditional writes (If-Match)
• Failure mode: the side of a partition without a majority rejects writes — a deliberate CP choice
• Who pays: users on the minority side see errors; the business pays in availability, not correctness

User-facing read scale → leader + async followers + session guarantees

• Constraint: local-region reads under 5ms; a user must see their own edits; others may lag
• Mechanism: commit tokens, monotonic reads, bounded-staleness follower reads
• Failure mode: stale reads for other users during lag; RPO of seconds on region loss
• Who pays: product owns the "others see it up to 1s late" decision; SRE owns the lag alert

Always-writable → multi-leader / leaderless + merge

• Constraint: writes accepted locally in every region, even when regions can't talk
• Mechanism: CRDTs, version vectors, hinted handoff, Merkle anti-entropy
• Failure mode: concurrent updates produce conflicts; resolution semantics become product behavior
• Who pays: product and end users — "the item I removed came back" is a merge semantic, not a bug

2.2 When NOT to Build a Replicated Data Store#

• When a managed service already fits. DynamoDB, Spanner, Aurora, Cosmos DB, and managed Cassandra encode years of failover hardening. Building your own replication layer is a 5–10 engineer, multi-year commitment. See Build vs Buy.
• When the data is derivable. Caches, search indexes, and materialized views can be rebuilt from a source of truth; replicate the source, not the derivative.
• When single-node + backups meets the RPO. A PostgreSQL primary with one sync standby and PITR backups gives RPO ≈ 0 and RTO of minutes for most internal tools. Don't build Raft for a 50 GB admin database.
• When you need global linearizable writes across continents for everything. That is not a replication design; that is a product requirement to challenge. Cross-continent consensus costs 150–200ms per write.

2.3 What the Interviewer Leaves Underspecified#

Staff engineers surface these. Senior engineers assume them away.

2.4 Precise Terminology#

🎯 Staff Insight: If the interviewer says "strong consistency," ask: "Do you mean linearizable single-key operations, serializable multi-key transactions, or just that users see their own writes? Those are three different systems with three different latency bills."

3. The Fault Lines#

Each fault line has a technical axis and an organizational axis. The organizational one — who approved the anomaly, who gets paged when users see it — is what the interviewer is scoring.

3.1 Fault Line 1: Leader-Based vs Leaderless#

The tension: A single leader per key makes conflicts impossible but makes failover a dangerous event. Leaderless removes failover but makes conflicts a permanent, everyday event.

L6 answer: "Single leader per shard is my default because it moves conflict resolution from every product team to one place — the log. I accept a 3–10 second write outage per shard on leader loss, which is rare and bounded. I'll only go multi-writer for data types that merge mathematically, and I'll say out loud that uniqueness constraints — usernames, seat assignments — can never be multi-writer."

When to deviate: Offline-first clients (mobile, collaborative editing — see Collaborative Editing), presence and counters across regions, or a business mandate that a region must keep taking writes while isolated.

🧭 Principal Move: "I'd make multi-writer an opt-in tier that only accepts registered CRDT types. If your data isn't one of those types, the platform won't let you replicate it multi-leader. That removes an entire class of incidents from 30 teams at once."

3.2 Fault Line 2: Synchronous vs Asynchronous Replication#

The tension: Every synchronous acknowledgment is a round trip added to every write. Every asynchronous one is data you can lose.

The Staff position is layered: majority in-region, async cross-region, and an explicit statement of the region-loss RPO.

L6 answer: "Commit on 2 of 3 in the home region: RPO zero for losing any single AZ, 2–4ms p99. Cross-region is async, so a full regional loss can drop up to the current lag. I'll alert at 5 seconds of lag, page at 30, and report rpo.unreplicated_writes so the RPO is a measured number, not a hope."

When to deviate: Regulated ledgers where RPO=0 for region loss is a legal requirement — then pay cross-region majority for that small dataset only (typically < 1% of total data), e.g., using a 5-replica group across 3 regions with the leader near the writers.

🎯 Staff Insight: "Semi-sync with a single designated follower is a trap. If that follower stalls, either writes stall or the system silently degrades to async — MySQL semi-sync does exactly this after a timeout. Majority of N ≥ 3 degrades gracefully; one designated follower does not."

3.3 Fault Line 3: Read Consistency Level#

The tension: Fresh reads come from the leader (one region, one node, capacity-limited). Scalable reads come from followers (stale). Session guarantees sit between them.

L6 answer: "Three tiers exposed as an API parameter. The default for user-facing reads is session, which means users never see their own write vanish and never see time go backward. Only operations that enforce an invariant pay for linearizable."

Who pays: Product pays in "another user may see my change up to 1s late." SRE pays in keeping lag inside the published bound. The platform pays in leader capacity for linearizable reads — budget roughly 5–10% of reads to be linearizable; if it's 50%, the leader is the bottleneck and you need to revisit.

🎯 Staff Move: "Linearizable reads via leader lease are only safe if the lease is shorter than the election timeout minus the maximum clock drift. With a 9s election timeout and a 500ms drift bound, I'd set the lease at 8s. If the platform can't bound drift, use Raft ReadIndex — one heartbeat round per read batch — instead of leases."

3.4 Fault Line 4: Conflict Resolution#

The tension: The moment two replicas accept writes for the same key independently, you must pick a winner or a merge. Every choice is a product decision disguised as a database setting.

L6 answer: "Per data type. Profile fields: LWW on HLC — overwrite semantics, concurrent edits within a second are rare and the loser is explainable. Cart: OR-set CRDT, add-wins, which means a remove concurrent with an add loses — product signs off on that. Counters: PN-counter. Balances: never multi-writer; single-writer routed to the home region."

🎯 Staff Insight: "'Last write wins' is a euphemism for 'some acknowledged writes are silently discarded.' If you choose it, name the discard rate. For 1M writes/day to the same keys from two regions with ~20ms skew, the number of concurrent-within-skew writes is the number you're throwing away — measure it with a conflict.lww_discards counter."

3.5 Fault Line 5: Failover Authority#

The tension: Automatic failover gives fast RTO and risks split brain or promoting a replica that is missing data. Human-gated failover is safe and slow — and humans at 3am make bad calls under pressure.

L6 answer: "In-region: automatic, consensus-driven, because a majority vote cannot produce two leaders in the same term. Cross-region: human-gated with a 5-minute decision SLO and a pre-computed lost-write estimate on the dashboard, because promoting the remote region is a one-way decision that forks history — when the old region returns, its unreplicated tail must be reconciled or discarded."

🧭 Principal Move: "GitHub's 2018 incident is the case study: a 43-second network partition led automation to promote a primary in another region, and the writes on both sides meant about 24 hours of degraded service while data was reconciled. The lesson isn't 'disable automation' — it's that cross-region promotion must check replication position and require the old side to be fenced first."

4. Failure Modes & Operational Reality#

4.1 Split Brain After a Paused Leader#

t=0:       Leader L1 (term 41) enters 12s stop-the-world GC pause
t=+5s:     Followers' election timeout fires; F2 wins term 42 with majority
t=+5.1s:   New writes go to F2 (term 42). Router map updated to epoch 42.
t=+12s:    L1 wakes. Still believes it is leader for term 41.
t=+12.01s: Stale router instance (cache TTL 30s) sends a write to L1.
           L1 appends locally, sends AppendEntries(term 41).
           Followers reply: term 42 > 41 → reject. L1 steps down.
           Client gets error → retries → routed to F2. No divergence.
Without fencing (watchdog failover, no terms):
t=+12.01s: L1 accepts and acks the write locally. Two leaders.
t=+14min:  Reconciliation discovers 3,400 conflicting rows.

Detection: raft.leader_count_per_shard > 1 (should be impossible — page immediately), raft.term_changes_per_hour, router.stale_epoch_rejections. Blast radius: One shard per paused leader; with fencing, zero data divergence; without, every write in the overlap window. Mitigation: Terms on every message; storage rejects stale terms; leases shorter than election timeout. Prevention: GC tuning (pause p99 < 200ms), lease + fencing verified in chaos tests (Jepsen-style) before every major release. Owner: Storage platform team.

4.2 Replication Lag Spiral#

t=0:       Analytics team launches a backfill: 40K writes/s to 200 shards
t=+2min:   eu-west followers' apply thread saturates; lag climbs 0.4s → 8s
t=+4min:   Session reads from EU exceed token; 60% proxy to us-east (+85ms)
t=+5min:   us-east leaders now serve 3× read load; CPU 85%; write p99 3ms → 40ms
t=+7min:   Write latency slows apply further (shared disk). Lag 45s.
t=+8min:   Page: replication.lag_seconds > 30 on 140 shards

Detection: replication.lag_seconds (warn 5s, page 30s), session.leader_proxy_rate (warn at 5%), leader CPU. Blast radius: All cross-region session reads; eventually all writes via leader overload. Mitigation: Throttle the backfill (per-tenant write rate limit); cap proxy rate — when > 20% of session reads would proxy, return stale-but-flagged data with staleness_ms or degrade the feature. See Degraded Mode. Prevention: Bulk writes go through a separate low-priority class with admission control; parallel apply per shard. Owner: Platform owns throttling; the analytics team owns their backfill schedule.

4.3 Resurrected Deletes (Zombie Data)#

t=0:        User deletes account data (GDPR request). Tombstone written W=2 of 3.
t=0:        Replica C is down for a disk replacement — misses the tombstone.
t=+11 days: gc_grace (10 days) expires; A and B compact the tombstone away.
t=+12 days: C rejoins. Anti-entropy compares A vs C: C has the row, A has nothing.
            Repair copies the row BACK to A and B. The data is alive again.
t=+40 days: Privacy audit finds the "deleted" user's records. Regulatory exposure.

Detection: antientropy.last_full_repair_age_days per range (must be < gc_grace), node.downtime_seconds > gc_grace → block rejoin. Blast radius: Every delete made while a replica was offline longer than the GC window. Mitigation: A node offline longer than gc_grace must be wiped and rebuilt, never rejoined. Prevention: Full repair cycle every 7 days on a 10-day grace; automation that refuses stale rejoin. Owner: Storage platform; privacy/legal is a stakeholder in the SLO.

4.4 Silent Divergence (The Failure Nobody Pages For)#

A replica's disk returns a corrupted block; checksums at the page level catch it on read — but only for data that's read. A bug in a schema migration writes different defaults on leader vs followers for 2 hours. Nothing is down. Nothing alerts. Three months later a failover promotes that follower and customer-visible values change.

Detection: Periodic cross-replica checksum of ranges (antientropy.divergent_ranges, target 0), row-count comparisons per shard, sampled read-compare (read 0.1% of keys from two replicas and compare, emit consistency.sample_mismatch_rate). Owner: Platform; the finding triggers an incident even with no user impact.

🎯 Staff Insight: "The dangerous replication failures are silent. I'd rather have a nightly job that says 'range 4412 differs between replicas' than find out during failover."

4.5 Operational Reality Matrix#

5. Evaluation Rubric#

5.1 Level-Based Signals#

5.2 Strong Hire Signals#

5.3 Lean No-Hire Signals#

5.4 Common False Positives#

• Recites Raft in detail: Knowing AppendEntries fields ≠ knowing where linearizability is needed.
• Name-drops CAP: "It's CP" says nothing about latency (PACELC) or which operations.
• Draws five regions active-active: Complexity is not a signal; ask what happens to a uniqueness check.
• Knows Cassandra consistency levels: Tuning knobs without a product rationale is Senior.

6. Interview Flow & Pivots#

6.1 Typical 45-Minute Shape#

6.2 How Interviewers Pivot — And What They're Testing#

6.3 What to Deliberately Skip#

6.4 Follow-Up Questions to Expect#

1. "Is R=2, W=2, N=3 linearizable? Prove or disprove."
2. "The leader was paused for 15 seconds. What does it do when it wakes?"
3. "How do you give read-your-writes to a user who switches from phone to laptop?"
4. "Two regions accept a write to the same key 5ms apart. Which wins, and does anyone find out?"
5. "How do you detect that two replicas silently disagree?"
6. "How long can a replica be offline before it can't safely rejoin?"
7. "What's your RPO for losing us-east entirely, and who approved it?"

7. Active Drills#

Drill 1: The Opening#

Prompt: "Design a replicated key-value store for our product."

Drill 2: The Quorum Question#

Prompt: "N=3, W=2, R=2. Is that strongly consistent?"

Drill 3: Make Read-Your-Writes Concrete#

Prompt: "A user edits their profile on their phone, then opens the laptop. What do they see, and how?"

Drill 4: The Leader Went Quiet#

Prompt: "The leader for shard 7 stops heartbeating. Walk me through the first 30 seconds."

Drill 5: Hot Shard#

Prompt: "One celebrity account's shard leader is at 95% CPU. What do you do?"

Drill 6: Multi-Region Writes Request#

Prompt: "Product wants EU users to write with EU latency, even if the transatlantic link fails."

Drill 7: Build vs Buy#

Prompt: "Should we build this or use a managed database?"

Drill 8: Changing Consistency Without an Outage#

Prompt: "We want to move the orders service from follower reads to linearizable reads. How?"

Drill 9: Cost#

Prompt: "Replication is 40% of our storage bill. Cut it."

Drill 10: Multi-Region Expansion#

Prompt: "We're adding ap-southeast. What changes?"

8. Deep Dive Scenarios#

Deep Dive 1: Peak Traffic — The Lag Spiral on Launch Day#

Context: A major product launch drives write volume to 3× normal. Remote-region replication lag climbs to 40 seconds. EU users are complaining that their changes "disappear" and support tickets are spiking. The on-call escalates to you.

Questions to Surface First:

• Are session tokens being honored, or is the EU path falling back to eventual reads under load?
• Is lag caused by ship (network), apply (CPU/disk), or leader-side backlog?
• What fraction of session reads are now proxying to us-east, and what is that doing to leader CPU?
• Is any non-launch workload (backfill, reindex) contributing?

Typical L5 Approach: Scales up the EU replicas, increases apply threads, and monitors lag until it recovers. Correct mechanics, but misses why users saw their writes disappear — lag alone shouldn't cause that if read-your-writes is working.

Staff Approach: Treats "writes disappear" as a session-guarantee violation, not a lag problem. Discovers the proxy path had a circuit breaker that, above 30% proxy rate, fell back to local eventual reads silently. Fixes the degraded mode to return an explicit "saving…" state instead of stale data, throttles non-critical writers, and adds apply parallelism.

Principal Approach: Asks why the platform lets a degraded mode silently break a published guarantee. Mandates that every consistency tier has a declared degraded behavior (error, wait, or flagged-stale) visible in the API response, and introduces launch-readiness reviews that include replication headroom for any launch forecast > 2× baseline.

Key Takeaway: "Lag is a capacity problem. Users seeing their own writes vanish is a contract violation. Page on the second, not the first."

What clears the Staff bar:

• Separates lag from guarantee violation
• Finds the silent degraded mode
• Assigns the degraded-mode decision to product, in advance

Deep Dive 2: Silent Divergence Found During Failover#

Context: A planned failover of shard group 12 to a new AZ completes cleanly. Within an hour, customers report account settings reverting to values from two months ago. No alert fired during the failover.

Questions to Surface First:

• Did the promoted replica actually have the same data as the old leader? When was it last verified?
• Was there a schema migration or bug window in the past two months affecting only some replicas?
• Is the old leader still intact? Can we diff?
• How many other shard groups have never been cross-verified?

Typical L5 Approach: Fails back to the old leader, restores the missing values from backup, and adds a pre-failover check comparing row counts. Fixes the incident; row counts would not have caught value-level divergence.

Staff Approach: Fails back, then diffs old leader vs promoted replica by range using Merkle hashes to find every divergent key. Finds a migration two months ago that applied a default only on the leader (statement-based replication of a non-deterministic function). Adds continuous checksum comparison and blocks failover to any replica whose range hashes haven't matched within 24 hours.

Principal Approach: Treats "replicas can silently disagree" as an org-level integrity risk, not one team's bug. Bans non-deterministic statement-based replication in the platform, requires row-based or log-based replication, and makes antientropy.divergent_ranges = 0 a precondition for any planned failover org-wide.

Key Takeaway: "A replica you've never verified is a backup you've never restored. Verify continuously or find out during failover."

What clears the Staff bar:

• Uses value-level verification, not row counts
• Finds the process root cause (non-deterministic migration)
• Makes verification a failover precondition

Deep Dive 3: Large Customer Onboarding With a Residency Requirement#

Context: Sales signs an enterprise customer 4× larger than any existing tenant. Contract terms: data must stay in the EU, RPO = 0 for region loss, and 99.99% write availability. They go live in 6 weeks.

Questions to Surface First:

• RPO=0 for region loss requires synchronous cross-region replication — within the EU, which regions? What's the RTT between them?
• 99.99% write availability plus RPO=0 across regions is a CAP-shaped promise — who approved it?
• Will this tenant share shards with others? What's their per-key write hotspot profile?
• Does the contract have penalties? What's the dollar exposure?

Typical L5 Approach: Provisions EU shards for the tenant, enables synchronous replication to a second EU region, load-tests, and ships. Delivers the letter of the contract, but under a regional partition the tenant's writes block — breaking 99.99% writes — and nobody told sales.

Staff Approach: Designs a 5-replica Raft group across 3 EU regions (e.g., Frankfurt, Ireland, Paris; 10–25ms RTT) so any single region can fail with RPO=0 and writes continue — the majority survives. Write p99 becomes ~25–35ms; the customer is told. Dedicated shards for isolation. Surfaces to sales that "99.99% writes and RPO=0" is only achievable with a 3-region footprint and costs ~2.2× a standard tenant.

Principal Approach: Treats this as a pricing and contract-governance gap. Creates a "sovereign strict" tier in the platform menu with a list price, a published latency, and a pre-approved architecture, and requires that sales contracts reference tiers rather than raw RPO/SLA numbers — so the next deal can't promise a combination the platform can't deliver.

Key Takeaway: "RPO=0 for region loss and high write availability together require at least three regions. Say the latency and the price before the contract is signed."

What clears the Staff bar:

• Translates contract language into topology and latency
• Knows 2 regions can't give both RPO=0 and availability under partition
• Pushes the decision back upstream to sales/legal

Deep Dive 4: Post-Mortem — The Cart That Lost Items#

Context: After a multi-region rollout of the cart service to active-active, customers report items vanishing from carts at a rate of ~0.3% of carts per day. The team uses LWW with server wall-clock timestamps.

Questions to Surface First:

• What's the clock skew distribution across regions?
• How often do two regions write the same cart within the skew window (mobile + web, retries)?
• Is "vanishing" a lost add, or a resurrected remove?
• What's the revenue impact of a lost cart item?

Typical L5 Approach: Tightens NTP, adds a node-ID tiebreak, and moves on. Reduces the rate but concurrent writes within the remaining skew are still silently discarded.

Staff Approach: Measures conflict.lww_discards and confirms they match the report rate. Replaces whole-cart LWW with an OR-set CRDT of line items (add-wins), quantity as a per-item PN-counter, and product sign-off that a concurrent remove + add results in the item present. Lost adds drop to zero.

Principal Approach: Uses this as the forcing function to publish the platform's conflict-resolution standard: wall-clock LWW is prohibited for any user-generated collection; multi-writer tier accepts only registered CRDT types; any team enabling multi-region writes goes through a design review with a data-type checklist.

Key Takeaway: "LWW on a collection is a bug with a probability. Replicate sets as sets."

What clears the Staff bar:

• Quantifies the discard rate and ties it to the symptom
• Picks CRDT semantics per field, not per object
• Uses single-homing as a fast, safe stopgap

Deep Dive 5: Multi-Region Expansion — From One Region to Three#

Context: The company runs everything in us-east with 3-AZ replication. Leadership wants a second and third region within 12 months for disaster recovery and latency.

Questions to Surface First:

• Is the goal DR (RPO/RTO for regional disaster), latency for remote users, or data residency? Each implies a different topology.
• Which services can tolerate async RPO, and which need synchronous?
• Has the org ever done a regional evacuation? What breaks outside the database — DNS, config, secrets, queues?
• What's the budget? Three regions is ~2.5–3× infrastructure cost.

Typical L5 Approach: Sets up async replicas of every database in two new regions, adds DNS failover, and declares DR done. Nothing proves failover works, and every service's RPO is whatever the lag happens to be.

Staff Approach: Phases it: (1) read replicas in region 2 with measured lag and session tokens; (2) monthly failover drills of non-critical shards; (3) geo-homing of shards whose writers are local; (4) region 3. Each service declares its tier and RPO; the dashboard shows real lag against declared RPO.

Principal Approach: Frames the program as an org capability, not a database project. Builds the evacuation playbook across all dependencies (identity, config, queues, caches), sets a target "region evacuation in < 30 min" validated by quarterly game days, and ties every team's tier declaration to their incident budget. Stops any service without a declared tier from being deployed to the new region.

Key Takeaway: "A second region is not DR until you have failed over to it on purpose. Budget the drills, not just the replicas."

What clears the Staff bar:

• Asks which of DR, latency, residency is the goal
• Phases the rollout with drills before commitments
• Declared vs measured RPO per service

9. Level Expectations Summary#

After studying this case study, you should be able to:

• State a consistency guarantee per operation and justify each with a latency number and a named owner
• Explain precisely why R+W>N is overlap, not linearizability, with a counterexample
• Walk a leader failover second by second, including terms, leases, fencing, and the no-op commit
• Quote an RPO for node, AZ, and region loss and name who approved each
• Implement read-your-writes across devices with commit tokens and bound its cost
• Pick a conflict-resolution strategy per data type and say what users will observe
• Explain why anti-entropy must finish inside the tombstone GC window
• Describe how the platform, not each team, should own these decisions at org scale

The Bar for This Question#

Mid-level (L4): Draws leader + followers, knows async vs sync replication, reads from replicas for scale. Can describe failover as "promote a replica." Rarely mentions anomalies unless prompted.

Senior (L5): Chooses a reasonable topology, knows quorum arithmetic, mentions replication lag and eventual consistency, handles failover with automation. The design works on the happy path and for single-node failures. Gaps: consistency is global rather than per operation, quorum overlap is confused with linearizability, split brain and RPO are hand-waved, deletes and silent divergence are not addressed.

Staff+ (L6): Starts from the anomaly contract. Linearizable where invariants live, session guarantees where users would notice, eventual elsewhere — each with a number. Failover is fenced, majority-elected, RPO-accounted and rehearsed. Conflicts are resolved per data type with product sign-off. Anti-entropy and tombstones are explicit. Ownership is split cleanly: platform owns mechanics, product owns chosen anomalies. The interviewer should learn something from the answer.

10. Staff Insiders: Controversial Opinions#

10.1 "Eventual Consistency" Is Not a Design — It's an Absence of One#

The Staff position: Replace "eventual" with a named, measured guarantee: session consistency with p99 lag < 1s, or bounded staleness ≤ 10s. If you can't state the bound, you can't alert on it.

Why this matters in interviews: Saying "eventual consistency is fine here" without a bound is the single most common L5 tell in this question.

10.2 Multi-Leader Replication Is Usually a Latency Optimization Wearing a Resilience Costume#

The Staff position: Default to single-leader with geo-partitioned homes. Use multi-writer only for data types that merge mathematically.

Why this matters in interviews: Proposing active-active for everything reads as not having debugged a conflict in production.

10.3 Automatic Cross-Region Failover Does More Harm Than Good for Most Companies#

The Staff position: Automate in-region (consensus makes it safe). Gate cross-region on a human with a 5-minute decision SLO and a pre-computed RPO estimate — unless you rehearse automatic cross-region failover monthly.

Why this matters in interviews: Saying "we'd make it automatic" without fencing and RPO guards is a red flag; saying "human-gated, here's why and here's the decision SLO" is a Staff-level signal.

10.4 Your Replication Is Only As Good As Your Last Verified Failover#

The Staff position: Continuous Merkle verification plus scheduled failovers. Treat "last successful failover > 90 days ago" as an incident-worthy risk.

Why this matters in interviews: It shows you think about the system after it's built.

10.5 Most Teams Should Never See a Quorum Knob#

The Staff position: The platform exposes named tiers with guarantees; knobs are internal.

Why this matters in interviews: Moving from "which setting" to "which contract" is the L6 → L7 bridge.

11. The Principal Lens (L7)#

Why L7 Sees This Problem Differently#

At Staff level, the replicated data store is one system to get right. At Principal level, it is the substrate under 50–200 services, each of which will independently choose a database, a replication mode, and a set of anomalies — usually without writing any of it down. The Principal problem is not "design the replication"; it is "make sure the company's aggregate anomaly exposure is chosen, priced, and tested, and that the number of distinct replication stacks the org must operate stays small enough to operate well."

The Org-Level Fault Line#

One storage platform with a consistency menu vs every team choosing its own database.

🧭 Principal Move: "I'd support three stores on the paved road — a consensus-replicated KV/SQL store, a managed wide-column store for write-heavy AP workloads, and object storage — each with named tiers. Anything else requires an exception with its own on-call and its own failover drill evidence."

Cost Model#

Assumptions: cloud list-ish prices, NVMe-backed instances at ~$0.10–0.15/GB-month effective for replicated storage, cross-region transfer ~$0.02/GB, fully loaded engineer $300K/year ($25K/month). Figures are order-of-magnitude.

The step from small to medium is dominated by copies (3 → 7–9) and transfer; the step to large is dominated by people — the platform team is often a bigger line item than the storage premium over a managed service.

The 3-Year Evolution Path#

One-Way Doors vs Two-Way Doors#

The Standard I'd Write#

RFC: Data Replication and Consistency Standard (v1)

Scope: All persistent stores holding customer or financial data.

MUST:

1. Every store MUST declare, per API operation, a consistency tier: strict (linearizable), session, bounded(Δ), or eventual.
2. Every store MUST publish RPO and RTO for node, AZ, and region loss, approved by the product owner.
3. Leader failover MUST use epoch/term fencing enforced by storage, not by a health checker.
4. Wall-clock last-write-wins MUST NOT be used for financial data or user-generated collections.
5. AP stores MUST complete full anti-entropy repair within 70% of the tombstone GC window.
6. Replication lag and unreplicated-write metrics MUST be emitted in the standard names.

SHOULD: use the paved-road stores; run a failover drill at least quarterly; verify replica checksums before planned failovers.

Exceptions: Filed with the storage architecture group; require an owning on-call rotation and drill evidence; expire after 12 months.

Success metrics: % of services with declared tiers (target 100% in 2 quarters); failover drill success rate ≥ 95%; declared-vs-measured RPO breaches = 0; number of distinct replication stacks in production (target ≤ 3).

What I'd Tell the VP#

Our data is copied across multiple machines and locations, but today nobody can tell you how much we'd lose in a regional outage or how long we'd be down — the answer differs per team and has never been tested end to end. I want every service to declare that promise in plain numbers, and I want us to prove it by failing over on purpose each quarter. Most of our data doesn't need expensive global guarantees; we'll reserve those for money and identity and save on the rest. This needs a platform team of about four people over the next year and roughly a 15% increase in storage spend for the second region. The payoff is that a regional outage becomes a 30-minute planned procedure rather than a multi-day incident.

Principal Interview Signals#

Staff answers that L7 interviewers find insufficient:

• A flawless single-store design that ignores the other 40 stores in the org with different guarantees
• "We'll make failover automatic" without an org-wide drill program or success metric
• Naming who pays without pricing it — "product accepts staleness" with no dollar or SLO attached

Appendices

Appendix A: Consistency Mechanics in Depth#

A.1 Leader Leases for Linearizable Reads#

on_become_leader(term):
    lease_expiry = now_monotonic() + LEASE - MAX_DRIFT   # e.g. 9s - 0.5s
    append(no_op, term)                                  # commit prior-term entries

on_heartbeat_majority_ack(sent_at):
    lease_expiry = sent_at + LEASE - MAX_DRIFT

read_linearizable(key):
    if now_monotonic() < lease_expiry and commit_index_applied():
        return local_read(key)
    else:
        idx = read_index_round()        # one heartbeat round to a majority
        wait_until_applied(idx)
        return local_read(key)

Why it's right: a new leader cannot be elected until followers' election timeouts expire, which is longer than the lease. Why it's wrong if misconfigured: if MAX_DRIFT understates real clock drift, a paused-then-resumed leader can serve a stale read inside what it thinks is a valid lease.

A.2 Quorum Arithmetic#

Overlap holds only with strict quorums on the designated preference list; sloppy quorums break it.

A.3 Hybrid Logical Clocks#

send_or_local_event():
    pt = physical_now()
    l_new = max(l, pt)
    c = (c + 1) if l_new == l else 0
    l = l_new
    return (l, c)

receive(msg_l, msg_c):
    pt = physical_now()
    l_new = max(l, msg_l, pt)
    if l_new == l == msg_l:   c = max(c, msg_c) + 1
    elif l_new == l:          c = c + 1
    elif l_new == msg_l:      c = msg_c + 1
    else:                     c = 0
    l = l_new

HLCs preserve causality (if A happened-before B, ts(A) < ts(B)) while staying within clock skew of physical time — which makes LWW deterministic and causally safe, but still lossy for truly concurrent writes.

Appendix B: Data Model and Keys#

B.1 Record Layout#

B.2 Commit Token Format#

base64(shard_id:u32 | term:u32 | log_index:u64) — 16 bytes, opaque to clients, comparable per shard. Session store holds max token per (user, shard) with 60s TTL.

Appendix C: Conflict Resolution — Quick Comparison#

C.1 Anti-Entropy With Merkle Trees#

build_tree(range, depth=15):         # 32,768 leaves
    for each key in range:
        leaf[hash(key) % 2^depth] ^= hash(key, version, value)
    internal nodes = hash(children)

repair(replica_a, replica_b, range):
    if a.root == b.root: return
    descend only into differing children
    for each differing leaf: stream keys in that leaf bucket, reconcile by version

Throttle to 10–50 MB/s per node; stagger per range so each range is fully repaired every 7 days on a 10-day GC window.

Appendix D: API Contract and Client Behavior#

Clients retry writes on leader-change errors with jittered backoff (base 50ms, cap 2s) and the same idempotency key. Without jitter, a leader election on a hot shard produces a synchronized retry storm at the new leader.

Appendix E: Observability#

E.1 Core Metrics#

replication.lag_seconds{shard,region}           # applied-time lag
replication.lag_bytes{shard,region}             # log backlog
rpo.unreplicated_writes{shard,region}           # writes not yet in remote region
raft.leader_elections_total{shard}
raft.leader_count_per_shard                     # must be 1
session.leader_proxy_rate
session.token_wait_ms
conflict.lww_discards{table}
antientropy.divergent_ranges
antientropy.last_full_repair_age_days
consistency.sample_mismatch_rate

E.2 Critical Alerts#

E.3 Control Plane vs Data Plane#

The data plane (leaders, followers, router) must keep serving if the control plane (etcd shard map, failover controller) is unavailable — routers cache the map and followers keep replicating. The control plane being down should block rebalancing and cross-region promotion, never reads and writes.

Appendix F: Scale Evolution#

F.1 What Works at Each Scale#

F.2 What You Don't Build on Day One#

• Multi-leader replication
• Automatic cross-region failover
• Custom consensus implementation (use etcd/Raft libraries or a managed store)
• Per-key consistency configuration (per-operation tiers are enough)
• Global linearizable writes

Appendix G: Multi-Tenancy and Cost Fairness#