Partition the data to scale.
Replicate it to survive.

Partitioning (sharding) splits one dataset across many machines so each holds a slice — it scales capacity and throughput. Replication copies the same data onto several machines — it provides fault tolerance and read scaling. They're orthogonal, and production systems combine them: shard the data into N partitions, then keep R replicas of each partition.

The partitioning strategy decides which node owns a given key.

Plain hashing — node = hash(key) % N — has a fatal flaw: change N (add or lose a machine) and almost every key remaps, forcing a full reshuffle. That's what consistent hashing fixes.

Map both keys and nodes onto a circular hash space (a ring). A key is owned by the first node found clockwise from its position. When a node joins, it takes over only the keys between it and its predecessor; everyone else is untouched. When a node leaves, only its keys move to the next node.

One refinement matters in practice: virtual nodes. Each physical machine is placed at many points on the ring, so load is even and removing a node spreads its keys across all survivors rather than dumping them on one neighbour.

The savings are dramatic and measurable. The naive scheme hash(key) mod N remaps almost every key the instant N changes; consistent hashing moves only the new node's share:

That gap is the difference between a resharding storm and a quiet rebalance. The runnable version below counts the moved keys both ways.

Even spread depends entirely on the shard key. A bad key creates a hot partition — one shard drowning in traffic while others idle. A celebrity user on a "shard by user_id" scheme is the canonical example.

When a single key is unavoidably hot, the fixes are: add a random suffix to fan it across sub-partitions, cache it separately, or give it dedicated capacity. The shard key is the one decision that most often makes or breaks the design.

Every workable scheme puts a layer of indirection between keys and machines: keys map to partitions, partitions map to nodes, and rebalancing moves whole partitions. A key never changes partition, so nothing is rehashed. The schemes differ in how partitions are created:

The risky part is deciding when to move. Rate-limit automatic rebalancing or keep a human approving it: an overloaded node answers slowly, a failure detector declares it dead, its partitions land on the others, they slow down too, and one hot node becomes a cascading outage. Every client or router must also agree which node owns a partition right now, so many systems keep that map in ZooKeeper or etcd.

Resharding a live system

Changing the shard key or shard count of an application-sharded database, say from 8 MySQL shards to 64, is a migration rather than a rebalance. The safe order is the same everywhere:

Capture changes from the old shards' replication log (change data capture) rather than dual-writing from application code, which can fail halfway through a request. Backfill with upserts that never overwrite a newer version, so the copy and the live stream can't clobber each other. Verify with row counts, per-range checksums and shadow reads that compare old and new answers. Shift reads gradually, flip writes in one short pause per key range, and keep replicating back into the old shards until you're sure you won't roll back. Vitess runs this sequence for MySQL as its Reshard workflow. Done by hand, the classic bug is a write that lands on an old shard after the flip. Size the new layout with the sharding planner.

Partitioning by primary key makes lookups by that key cheap. Everything else (all orders with status = 'failed', all users in one city) needs a secondary index, and the index has to be partitioned too. There are two ways to do it:

MongoDB, Cassandra and Elasticsearch index locally: writes stay inside one partition and reads pay for it. A query on the indexed field fans out to every partition and waits for all of them, so the slowest one sets its latency. The arithmetic is unforgiving: if each partition answers within 10 ms 99% of the time, a query that needs all 20 finishes within 10 ms only 0.99^20 ≈ 82% of the time.

A global index flips the trade. Entries for status = 'failed' live on one index partition, so the read touches one place, but one row write may now change index partitions on several machines. Doing that synchronously takes a distributed transaction, so most systems update global indexes asynchronously. DynamoDB offers both: a local secondary index shares the table's partition key and supports strongly consistent reads, while a global secondary index has its own partition key and supports only eventually consistent reads.

Decision rule: if most queries include the partition key, index locally and keep fan-out queries rare and paginated. If a lookup by another field is on the hot path, use a global index and design for the lag, since a user who just wrote a row may not find it through the index yet.

Asynchronous replication introduces replication lag: a follower can be behind the leader, so a read from it may be stale. That silently breaks read-your-writes — a user edits their profile, then sees the old value. The fix is to route a user's reads to the leader (or a caught-up follower) for a short window after they write.

Single-leader replication is simple until the leader dies. Failover has three steps, and each one has a trap:

Discarded writes can do damage outside the database. Designing Data-Intensive Applications recounts a GitHub incident in which an out-of-date MySQL follower was promoted and reused auto-increment keys the old leader had already handed out; because Redis also stored those keys, some private data was shown to the wrong users.

Split brain is worse: the old leader was only partitioned or paused, and both sides keep accepting writes that will conflict. Two defenses work together. Elect leaders by majority, so only one side of a partition can elect anyone (the mechanics are on the consensus page). And fence the old leader: each new leader gets a higher epoch number, replicas and storage reject anything stamped with an older one, and the old leader steps down when it sees the higher number. Cruder fencing, known as STONITH ("shoot the other node in the head"), cuts the old leader's power or network through the infrastructure. A lease alone isn't enough, because a leader paused past its lease doesn't know it paused. The same idea protects distributed locks as fencing tokens.

Leaderless stores in the Dynamo family, such as Cassandra and Riak, let any replica take a write. With N replicas, a write waits for W acknowledgements and a read asks R replicas. If W + R > N, every read set overlaps every write set, so a read reaches at least one replica holding the latest acknowledged write. That is not linearizability; the quorum math and the five ways it fails in production are on the CAP page. This section covers what keeps replicas converging.

Sloppy quorums and hinted handoff. When a partition cuts a client off from some of a key's N home replicas, a strict quorum returns an error. A sloppy quorum instead accepts the write on whichever reachable nodes it can find, and each stand-in keeps a hint saying where the write belongs, delivering it when the home replica returns. Writes stay available, but reads of the home replicas can miss them until then, so W + R > N no longer guarantees overlap. Riak enables sloppy quorums by default. Cassandra stores hints but never counts them toward a quorum; only its ANY consistency level accepts a hint as the write.

Repair. Replicas still drift, for example when a node stays down longer than hints are kept. Read repair fixes the keys people read: the coordinator spots a stale version among its R replies and writes the newer one back. Anti-entropy fixes the rest: a background process compares replicas range by range using Merkle trees and streams only the ranges that differ.

Concurrent writes. Two clients write one key at nearly the same moment, replicas receive the writes in different orders, and something has to pick the final value:

Version vectors compare counter by counter. [A:2, B:1] is at or ahead of [A:1, B:1] on every counter, so it replaces it. [A:2, B:0] and [A:1, B:1] are each ahead on one, so neither happened first: keep both. A cart that merges siblings by set union never loses an added item, although a removed item can come back unless removals are recorded as tombstones. Try both in the vector clocks lab and the CRDT lab.