Consistency, replication, sharding, consistent hashing
Everything below is about one situation: one machine is no longer enough. A single server has a ceiling — so much CPU, so much RAM, so much disk, so many requests per second. There are exactly two ways past that ceiling, and you should be able to name both on demand.
- Vertical scaling (scale up): buy a bigger machine — more cores, more RAM. Dead simple, no code changes, but it has a hard limit (the biggest box money can buy) and that one box is still a single point of failure — if it dies, everything dies.
- Horizontal scaling (scale out): buy more machines and spread the work across them. No hard ceiling, and you can lose one machine without losing the system — but now you have many machines that must coordinate, and that coordination is where all the hard problems (and this whole lesson) come from.
The instant you go horizontal you do two things to your data: you make copies of it (replication) and you split it across machines (sharding / partitioning). The rest of this lesson is the menu of techniques for doing that well, in the order you'd actually reach for them, plus the traps.
📖 Walk me through it — plain English
This lesson is about what happens when one computer is no longer enough. Once your data is too big or too busy for a single machine, you make copies of it (called replication) and you split it across many machines (called sharding or partitioning). The moment you do that, you inherit a pile of hard questions, and these are exactly the questions a senior design interview keeps poking at.
The first big idea is the CAP theorem. Imagine your machines occasionally can't talk to each other — the network cable is cut, a data center drops off. That break is called a partition (the P). During a partition you must pick one of two behaviors. Either you keep refusing to answer until everyone agrees again, which gives you Consistency (the C: every reader sees the latest write, never stale data) — that is a "CP" system like Spanner or Zookeeper. Or you keep answering anyway and sort out the disagreements later, which gives you Availability (the A: the system always responds) — that is an "AP" system like Cassandra or DynamoDB. You cannot have both during the break. The practical note in the lesson matters: cable cuts are rare, so most days a system behaves fine on every axis — the C-vs-A choice only reveals itself when something fails.
Everyday analogy. Think of two bank tellers in two towns sharing one customer ledger. Normally they phone each other after every transaction so both ledgers match. Now the phone line goes dead (a partition). Teller A has two choices. Option one: "I won't touch any account until the line is back" — nobody gets wrong balances, but customers are turned away. That is choosing Consistency (CP). Option two: "I'll keep serving people and we'll reconcile the two ledgers tonight" — everyone gets served, but for a while the two ledgers disagree. That is choosing Availability (AP). Same dilemma, exactly.
The consistency models are just how strict that "everyone sees the latest write" promise is. Strong / linearizable means a read always reflects the newest committed write (great, but slow across continents). Eventual means replicas drift apart briefly and quietly converge later (fine for a social feed where seeing a like one second late is harmless). Read-your-writes is a gentle middle: you always see your own edit immediately, even if other people see it a moment later. Replication strategies are about who is allowed to accept a write: one boss machine (leader-follower, simple, followers serve possibly-stale reads), several bosses (multi-leader, fast in many regions but you must resolve conflicting edits), or no boss at all (leaderless / Dynamo-style, where the client writes to several copies and reads from several copies; the rule W + R > N — writes touched plus reads touched exceeds total replicas — guarantees at least one copy you read is fresh).
Sharding is splitting the data itself across machines. Range sharding ("keys A–M here, N–Z there") is handy for range scans but risks a hot shard if everyone wants the same range. Plain hash sharding does hash(key) % N where N is the number of machines — spreads evenly, but if N changes (you add a machine) almost every key suddenly maps somewhere new and must be physically moved. That last problem is why consistent hashing exists, and it's worth tracing slowly.
Picture a clock face, 0 to 360 degrees, that wraps around (this circle is the "ring"). You hash each machine to a point on the ring, and you hash each key to a point too. A key belongs to the first machine you hit walking clockwise from the key's position. Let's place two nodes and two keys:
Why this is the win. With plain hash(key) % N, bumping N from 2 to 3 reshuffles almost every key. With the ring, adding Node C only steals the keys that sit in the arc just before it — here just k2 — and every other key stays exactly where it was. In general, adding or removing one node out of N relocates only about K/N of the K total keys, instead of nearly all of them. That is why consistent hashing is the default for key-value stores like Cassandra and DynamoDB: you can grow or shrink the cluster with minimal data shuffling. (Real systems also give each node several positions on the ring — "virtual nodes" — so the load splits more evenly, but the walk-clockwise rule is exactly the same.)
The concepts every senior design round circles back to.
The toolbox: every scaling primitive, defined
Before the deep dives, here's the whole vocabulary in one place. In an interview you'll layer several of these together; knowing the precise job of each is what separates a confident answer from arm-waving. Each term is defined inline — no outside reading required.
- Load balancer: a box that sits in front of a pool of identical servers and spreads incoming requests across them, so no single server is overwhelmed and a dead server can be skipped. It's the front door of horizontal scaling. How it picks a server is the algorithm: round-robin hands requests out in rotation (1, 2, 3, 1, 2, 3…) — simple and fair when requests cost about the same; least-connections sends the next request to whichever server currently has the fewest open connections — better when some requests are long-running and others are quick. (Others you may hear: weighted round-robin for unequal machines, and IP-hash to pin a given client to the same server.)
- Stateless service: a server that keeps no per-user memory between requests — everything it needs arrives in the request or is fetched from a shared store (database, cache). This is the precondition for load balancing: if any server can handle any request, the load balancer is free to send a user's next request anywhere. The opposite, a stateful server (e.g. one that holds your login session in its own local RAM), forces "sticky sessions" and breaks the moment that server dies — push that state into a shared store instead.
- Caching layer: a fast in-memory store (Redis, Memcached) placed in front of a slow backend to serve hot, frequently-read data without touching the database. A cache turns thousands of identical reads into one. It trades freshness for speed: cached data can go stale, so you set a TTL (time-to-live) or invalidate on write.
- CDN (content delivery network): a globally-distributed cache for static assets (images, CSS, JS, video). It stores copies near your users so a request from Tokyo is served from a Tokyo edge node instead of crossing an ocean to your origin server. It both speeds up users and offloads bandwidth from your servers.
- Read replicas: read-only copies of your database kept in sync with the primary. Most apps read far more than they write, so you point all writes at the primary and fan reads out across replicas — multiplying read throughput. The cost is replication lag: a replica may be a few milliseconds behind, so a read right after a write can show stale data (this is exactly why read-your-writes consistency matters).
- Replication: keeping multiple copies of the same data on different machines so that (a) reads scale and (b) the data survives a machine failure. Read replicas are one use; cross-region disaster recovery is another.
- Sharding / partitioning: splitting one large dataset into disjoint pieces (shards) on different machines so each machine holds and serves only its slice. This is how you scale writes and total data size past one machine — replication alone can't, since every replica still holds the whole dataset.
- Shard key: the field you choose to decide which shard a row lives on (e.g.
user_id). Picking it well is the whole game: a good shard key spreads load evenly and keeps related data together; a bad one creates a hot shard that everyone hammers. - Consistent hashing: the ring scheme from the walkthrough above — hash both keys and nodes onto a circle and assign each key to the next node clockwise — so adding or removing a node moves only ~K/N keys. The standard way to assign shards to nodes when the node count changes over time.
- Virtual nodes (vnodes): give each physical machine many positions on the ring instead of one. With one position per node, an unlucky hash can leave one node owning a huge arc (uneven load); with, say, 100 positions per node the arcs even out statistically, and when a node leaves, its load is shared smoothly across all survivors rather than dumped on a single neighbor. The interactive viz below uses this idea.
- Message queue: a buffer (Kafka, SQS, RabbitMQ) that sits between a producer and a consumer. Instead of the web server doing slow work inline, it drops a job on the queue and replies immediately; a worker pulls jobs at its own pace. This smooths load: a traffic spike piles up in the queue and drains gradually, so your workers run at a steady rate instead of being crushed.
- Single point of failure (SPOF): any one component whose failure takes down the whole system. The goal of replication, load balancing, and multiple availability zones is to eliminate SPOFs — every critical piece should have a standby.
- Database scaling: the umbrella for all of the above applied to the data tier — add caching, then read replicas, then sharding — because the database is almost always the first thing to fall over under load.
The order to apply these
Interviewers love to see you reach for the cheapest sufficient fix first. There's a near-universal escalation ladder — climb it only as far as the numbers force you:
- Scale up first. Bigger machine. Zero complexity. Often buys you a year.
- Add a cache. Most read traffic is for the same hot data. A Redis layer can absorb 90%+ of reads before touching the DB.
- Put static assets on a CDN. Cheap, instant win for global users, and it offloads your origin.
- Make services stateless + add a load balancer. Now you can run many identical app servers and add more on demand.
- Add read replicas. When reads still dominate, fan them out across replicas; keep writes on the primary.
- Add a message queue. Move slow, spiky, or non-urgent work (emails, image processing, analytics) off the request path to smooth load.
- Shard the database. The last resort and the most complex. Do this only when one primary can no longer hold the data or absorb the writes — and use a good shard key + consistent hashing.
Notice the shape: every step before sharding is reversible and low-risk; sharding changes your data model and is hard to undo. That ordering — caches and replicas before partitioning — is itself a senior signal.
Under a network Partition, you can have either Consistency or Availability — not both.
- CP systems: Spanner, HBase, Zookeeper. Refuse writes on partition.
- AP systems: Cassandra, DynamoDB (eventual). Accept writes, reconcile later.
- Practical reality: partitions are rare. Most systems are CA or CP day-to-day; the choice surfaces during failure.
A partition here means the machines can't all talk to each other — a cut link or a dropped data center splits the cluster into groups that can't sync. Consistency means every read returns the latest committed write (never stale); availability means every request gets a non-error response. CAP says: when the network splits, a node that can't reach its peers must either refuse to answer (preserving consistency) or answer with possibly-stale data (preserving availability). It can't do both, because it has no way to know what the unreachable peers have written.
- Strong (linearizable): reads see the most recent committed write. Costly across regions.
- Sequential / causal: writes seen in a consistent order; weaker but easier to scale.
- Eventual: all replicas converge eventually. Best for high-write systems where staleness is tolerable (DNS, social feeds).
- Read-your-writes: a user sees their own writes immediately — even if everyone else sees them later.
A consistency model is the promise the system makes about how fresh a read can be. It's a spectrum, not a switch: strong is the strictest and slowest (a read may have to wait for replicas across the planet to agree); eventual is the loosest and fastest (replicas drift apart for milliseconds, then quietly catch up); the middle options let you keep some guarantee cheaply. You pick the weakest model your product can tolerate — a bank balance wants strong, a like-count is happy with eventual.
- Leader-follower (single leader): all writes to leader; followers replicate. Simple. Followers can serve reads (stale).
- Multi-leader: writes accepted at multiple regions. Faster cross-region writes, but conflicts need resolution (last-write-wins, CRDTs).
- Leaderless (Dynamo-style): client writes to N replicas, reads from R, needs W + R > N for consistency. Used by Cassandra, DynamoDB.
Replication = keeping copies of the same data on several machines. The strategies differ only in who may accept a write. One leader is simplest but the leader is a write bottleneck and a SPOF (followers must be promoted if it dies). Multiple leaders unlock fast local writes in every region but force you to resolve two regions editing the same row at once. Leaderless drops the leader entirely: the client itself talks to several replicas. The quorum rule W + R > N (you write to W copies, read from R copies, out of N total) works because any read set and any write set must then overlap in at least one node — and that shared node is guaranteed to hold the newest write.
- Range: split by key range. Good for range queries. Risk: hot ranges.
- Hash: hash(key) % N. Even distribution. Cost: rebalancing on resize is brutal.
- Consistent hashing: hash both keys and nodes to a ring. Adding/removing a node moves only ~K/N keys. The right default for KV stores.
Sharding splits the data itself so each machine owns a disjoint slice — that's how you scale writes and total size past one box. The shard key is the field that decides the slice. Range sharding keeps neighboring keys together (great for "give me all of January") but invites a hot shard when one range is far busier than the rest (e.g. sharding by timestamp means all of today's writes hit one shard). Plain hash sharding scatters keys evenly so no range is hot — but as the next section shows, it falls apart when the node count changes. Consistent hashing keeps the even spread while making resize cheap.
Why consistent hashing beats modulo hashing
This is the single most-asked detail in scaling rounds, so let's nail the why, not just the what. The naive scheme is modulo hashing: shard = hash(key) % N, where N is the number of machines. With N = 3, key k goes to machine hash(k) % 3. Even distribution, trivial to compute. The problem is the % N — the answer depends on N, and the day you add or remove a machine, N changes for every key at once.
Concretely: a key whose hash is 100, with N going from 3 → 4. Before: 100 % 3 = 1 (machine 1). After: 100 % 4 = 0 (machine 0). The key moved — and so do almost all of them. Adding one machine to a 3-node modulo cluster relocates roughly 3/4 of all keys, even though you only changed the cluster by one node. For a cache, that means a near-total cache miss storm; for a database, a massive, slow physical data migration. Removing a node is just as brutal.
Consistent hashing fixes this by removing N from the key's formula. A key's position on the ring is just hash(key) — it never changes. Only the nodes' positions matter, and a node sits at a fixed point too. When you add a node, it claims exactly the arc of keys between itself and the previous node clockwise; nothing else moves. When you remove a node, its arc spills onto the next node clockwise; again nothing else moves. So a single add/remove relocates only ~K/N keys (K total keys, N nodes) instead of nearly all K. That's the entire reason Cassandra, DynamoDB, and most consistent caches use it.
Virtual nodes patch the one weakness. With one ring position per machine, the arcs are uneven (some machines randomly own a much bigger slice) and a departing node dumps its whole arc on a single neighbor. Giving each machine many positions (vnodes) makes the arcs average out and spreads a departing node's load across all survivors. The walk-clockwise rule is identical — there are just more dots on the ring.
Trace this yourself in the interactive ring below: add a node and watch that only the keys in its new arc light up as moved; every other key stays put. That visual is the K/N argument.
Each key walks clockwise to the next node. Add/remove a node — most keys stay put.
Pitfalls that sink answers
Reaching for sharding or microservices when one well-tuned box with a cache would do. Distributed systems cost you complexity, latency, and bugs forever. Climb the ladder only as far as your numbers demand, and say so out loud.
A shard key that concentrates traffic — sharding by timestamp (everything writes to "today"), or by a celebrity user whose row gets all the reads. One shard melts while the rest idle. Fix with a higher-cardinality key, salting, or splitting hot keys.
Storing sessions or in-progress data in a server's local RAM. It forces sticky sessions, defeats the load balancer, and loses data when the server dies. Push all state into a shared store (Redis, DB) and keep app servers disposable.
A lone primary DB, a single load balancer, one availability zone. You scaled the app tier but left a chokepoint that takes everything down. Replicate or pair every critical component, and name where the standby lives.
Takeaway: scaling is a ladder, not a leap. Go vertical until it hurts; then cache, CDN, statelessness + load balancer, read replicas, and a queue to smooth load — and only then shard. Sharding needs a shard key that spreads load and consistent hashing (with virtual nodes) so resizing the cluster moves ~K/N keys instead of all of them, which is exactly the win modulo hashing can't give you. Whenever you split or copy data, the CAP theorem decides your behavior under a partition, and your consistency model sets how fresh reads must be. Watch for the four traps: premature scaling, hot shards, stateful servers, and hidden SPOFs.
Go deeper (optional): the canonical reference is Martin Kleppmann's Designing Data-Intensive Applications (the replication, partitioning, and consistency chapters map directly onto this lesson), and Amazon's original Dynamo paper for consistent hashing, vnodes, and quorum reads in the wild.