In a hash-partitioned cluster, plain hash(key) mod N remaps almost every key when N (the node count) changes. Explain how consistent hashing arranges nodes and keys on a ring to avoid this, and why adding or removing one node only affects a small fraction of keys.

## The problem: modulo hashing reshuffles everything The problem consistent hashing solves is **data movement on cluster resize**. With naive modulo hashing, a key's partition is computed as `hash(key) mod N`, where `N` is the current node count. This ties partition ownership directly to the total number of nodes. If you go from 4 nodes to 5, the divisor changes, and for almost every key, `hash(key) mod 4` and `hash(key) mod 5` give different answers — so roughly (N-1)/N of all keys change owners on a single node addition. In a large cluster, adding one node to relieve load would trigger a near-total data reshuffle, exactly the opposite of what you want when scaling incrementally. ## The ring and the ownership rule Consistent hashing fixes this by decoupling 'where does this key go' from 'how many nodes are there.' 1. Both nodes and keys are hashed into the same fixed output space, conventionally visualized as a **ring** — the integers from 0 to some maximum, wrapping back to 0. 2. Each node is hashed (using its ID, IP, or a node-specific token) to get one or more positions on this ring. 3. Each key is likewise hashed to a position. Ownership follows a simple rule: a key belongs to the **first node encountered walking clockwise** from the key's position. Each node owns the **arc** stretching counter-clockwise from itself back to the previous node — a contiguous range of hash-space defined structurally by ring position, not by the total node count. ## What a membership change actually moves The payoff shows up at membership changes. - **A new node joins.** It becomes responsible for the arc between itself and the next node counter-clockwise; those keys — and only those keys — move to the new node. Every other node's arc and every other key's ownership is untouched. - **A node leaves.** Symmetrically, its arc is handed to the next node clockwise, and nothing else moves. In both cases, the expected fraction of keys that move is roughly 1/N, a dramatic improvement over modulo hashing's near-total reshuffle. | Scheme | Keys moved by one node addition | |---|---| | naive modulo hashing | roughly (N-1)/N of all keys | | consistent hashing | roughly 1/N | ## The trade-off The trade-off consistent hashing introduces is **implementation complexity**: - You need to maintain ring topology (which node owns which arc) and propagate changes (gossip protocols, a coordination service like ZooKeeper, or a control-plane store). - You also inherit a subtler cost: because each physical node gets only one (or a few) random positions, arc sizes are not guaranteed to be even. With a small number of nodes, random placement can easily produce one node with a much larger arc than another — that node then serves proportionally more data and traffic. This uneven-load problem directly motivates **virtual nodes** (multiple ring positions per physical node), a distinct mitigation covered separately. ## Failure modes in operation Operationally, a healthy consistent-hashing cluster losing or gaining a node causes a brief, bounded burst of data transfer and a short window where requests for keys in the affected arc may hit the 'old' owner until the ring update propagates — the classic source of transient inconsistency during a rebalance if clients haven't yet learned the new ring layout. A common failure mode is **ring divergence**: if different nodes or clients have stale or conflicting views of ring membership (e.g., during a network partition), they can disagree about who owns a given key, leading to split-brain writes to the same logical key on two different nodes. ## Where it shows up in real systems A widely known real-world usage: - **Amazon's Dynamo paper** (the design basis for Cassandra and Riak) popularized consistent hashing with virtual nodes specifically to support incremental cluster growth and shrinkage without full-cluster rebalances, while also using it to place replicas (the N nodes clockwise from a key's position) — so the same ring structure that decides primary ownership also decides where replicas live. - **Cassandra's token ring** is a direct descendant of this design, where each node is assigned one or more tokens (ring positions), and adding a node means it claims a slice of token ranges from its neighbors and streams that data over.