SYSTEM DESIGN:Lesson 12: Replicating and Sharding a KV Store

One Redis box is not a distributed system

"We ran everything on a single Redis instance in ap-south-1. It worked until Diwali sale prep — 40 lakh session keys, one node out of memory, and checkout started failing for users in Bangalore and Mumbai at the same time."

A key-value store looks simple: SET user:4821:cart {...} and GET user:4821:cart. The hard part starts when one machine cannot hold all keys, one network partition can lose writes, and a single crash takes down every cart in the country.

This chapter is about making KV storage distributed: replication for durability and read scale, sharding for write scale and capacity, quorum rules for consistency, and the CAP trade-offs you will defend in interviews.

If you have not covered the data layer basics yet, read Data Layer Scaling first — read replicas and sharding intro live there. This chapter goes deeper on KV-specific patterns: leader-follower replication, quorum reads/writes, and consistent hashing.

Three replicas, three opinions on what the value should be

Quorum is democracy for databases. Sometimes the minority was right.

Why replicate a KV store?

Replication means keeping copies of the same key-value data on multiple nodes. You replicate for two reasons: durability (disk dies, data survives elsewhere) and read throughput (spread GET traffic across replicas).

Leader-follower replication in a distributed KV store

The common pattern is leader-follower (primary-replica):

Write:  Client → Leader → append to WAL → replicate to Followers → ACK client
Read:   Client → any Follower (or Leader if you need freshest value)

Redis with read replicas works exactly like this. DynamoDB, Cassandra, and Riak use different replication topologies — but the interview story starts with leader-follower because it is easy to draw on a whiteboard.

Replication lag is real. A user updates their Swiggy cart on the leader, immediately refreshes, and hits a follower that has not caught up — empty cart flash for 100ms. For shopping carts, that is annoying. For UPI ledger balances, it is unacceptable. Route strong-consistency reads to the leader.

Quorum reads and writes

Leader-follower replication is simple but the leader is a single point of failure for writes. Quorum-based replication (used in Dynamo-style systems) writes to N replicas and requires W successful writes and R successful reads such that R + W > N.

N = 3 replicas (common default)
W = 2  → write succeeds when 2 of 3 nodes confirm
R = 2  → read fetches from 2 nodes, returns latest timestamp

R + W = 4 > N = 3  →  guaranteed overlap → no stale read after confirmed write

In an interview, say: "For a session store I might use W=1, R=1 and accept eventual consistency. For a distributed lock or inventory count, I want W=2, R=2 with N=3." The numbers change; the principle does not.

Vector clocks and conflict resolution: when two writes land on different replicas during a partition, you get conflicting versions. Dynamo-family stores attach timestamps or vector clocks and use last-write-wins or application-level merge. Know that quorum prevents stale reads after a successful write — it does not prevent write-write conflicts during partitions.

Sharding: split keys across nodes

Replication copies the same data. Sharding splits different keys across nodes. User 4821 lives on Shard A. User 9102 lives on Shard B. Each shard is an independent KV store holding a subset of the keyspace.

Consistent hashing ring for KV store sharding

Naive sharding — hash(key) % N — breaks when you add or remove a node. Almost every key moves. Cache invalidation nightmare.

Consistent hashing maps keys and nodes onto a ring. Adding one node only moves keys in its neighbourhood — roughly 1/N of keys, not all of them.

Ring: 0 ─────────────────────────────────────────── 2^32-1

Nodes:     N1          N2              N3
Keys:   user:100   order:55      session:8821

Lookup: hash("session:8821") → walk clockwise → first node ≥ hash → N3

Virtual nodes (vnodes) place multiple points per physical node on the ring so load stays balanced. Without vnodes, one unlucky node might own half the ring if hashes cluster.

Hot keys are the sharding problem nobody warns you about until production. One IPL fantasy contest ID gets 50 lakh reads per minute — every request hits the same shard. Fix: local cache on app servers, read replicas for that shard, or split the hot key into contest:123:shard-0 through contest:123:shard-7.

CAP theorem in plain language

When a network partition happens — Mumbai AZ loses connectivity to Hyderabad — a distributed KV store cannot simultaneously guarantee Consistency (every read sees the latest write) and Availability (every request gets a response). You pick one.

Every real distributed system is partition-tolerant — networks fail. The interview question is never "CP or AP?" It is: "For this specific key, do I pause writes or return possibly stale data?"

Indian payment context: NPCI infrastructure leans CP for settlement — you would rather reject a transaction than double-spend. A food delivery ETA cache leans AP — showing yesterday's prep time is better than a 503 error page.

Failure handling: nodes die at 2 AM

Production KV stores must handle failures without human intervention.

Leader failure:

1. Followers detect missed heartbeats (e.g., 5 seconds)
2. Raft/Paxos election → new leader chosen
3. Uncommitted writes either replay from WAL or return error to client
4. Clients retry with exponential backoff

Follower failure: reads reroute to healthy replicas. Writes continue on leader. Replace dead node, backfill from snapshot + WAL.

Network partition:

• CP system: minority partition stops accepting writes (split-brain prevention)
• AP system: both partitions accept writes → conflicts on heal → merge strategy needed

Hinted handoff (Dynamo pattern): if the target node is down, a neighbour node temporarily stores writes and forwards them when the node returns. Keeps availability without losing data.

Anti-entropy (Merkle tree comparison) runs in the background to fix drift between replicas. You do not rely on it for real-time consistency — it is a repair mechanism, not a read path.

A realistic KV evolution story

How a session store for an Indian e-commerce app might grow:

Stage 0 — Single Redis: 50 GB RAM, 100k keys, fine for MVP.

Stage 1 — Redis + read replicas: GET traffic 10× write traffic. Add 2 replicas. Session reads spread across three nodes.

Stage 2 — Redis Cluster (sharded): Keyspace exceeds 50 GB. 6 primary shards + 6 replicas. Consistent hashing built into Redis Cluster.

Stage 3 — Multi-region: Users in India + Middle East. ap-south-1 primary, me-south-1 replica. Cross-region replication lag 80–150ms — design reads accordingly.

Notice: you add replication before sharding if reads are the bottleneck. You shard when memory or write throughput exceeds one node. Same pattern as Postgres, different tooling.

Common mistakes in KV interviews

Mistake 1 — treating Redis as durable storage.

Redis with AOF/RDB can survive restarts, but it is not a substitute for replication and backup strategy. If the only copy of payment state lives in one Redis box, you do not have a distributed system — you have a prayer.

Mistake 2 — sharding before replicating.

A single shard with no replica is one disk failure away from data loss. Replicate first, then shard when capacity demands it.

Mistake 3 — ignoring hot keys.

Consistent hashing gives even distribution in theory. In practice, one viral product drop sends every request to the same key. Always mention hot-key mitigation.

Mistake 4 — wrong CAP answer.

Saying "we will be fully consistent and fully available" signals you have not operated a distributed system. Pick the trade-off per use case and explain why.

Mistake 5 — no client retry logic.

Leader election takes 5–30 seconds. Clients that fail immediately on timeout will cascade. Idempotent writes + exponential backoff are part of the design.

Interview talking points

When asked "design a distributed KV store":

1. Clarify — read/write ratio, value size, consistency per key type, durability SLA
2. Estimate — total keys × avg value size → storage; peak QPS → node count
3. Replication — leader-follower for simplicity, quorum for partition tolerance
4. Sharding — consistent hashing + vnodes; name your shard key (user_id, not timestamp)
5. Failures — leader election, hinted handoff, anti-entropy
6. CAP — state which operations are CP vs AP and why

Draw the ring. Write N/W/R on the board. Mention one hot-key fix. You are ahead of candidates who only say "use Redis Cluster."

Practice with hands-on labs

Theory without simulation is forgettable. These labs let you break replicas and shards safely:

• Consistency Lab — feel the difference between strong and eventual consistency on reads
• Sharding Lab — pick a shard key, watch hot tenants overload one node

Run the consistency lab with W=1, R=1 vs W=2, R=2. Then open the sharding lab and add a node — watch how few keys move with consistent hashing vs hash-mod-N. That contrast sticks in interviews.

What comes next: unique IDs

Distributed KV stores need keys. Sharding uses hash(key) — but who generates unique keys for new records across datacenters without collisions?

The next chapter covers auto-increment pitfalls, UUID trade-offs, and why every Indian startup eventually asks "should we use Snowflake IDs?"

Continue here: Counting Without Collisions.