Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Consistent hashing

Distribute keys across nodes so that adding or removing a node moves only ~1/N of the keys, not nearly all of them: why hash mod N reshuffles, the ring, virtual nodes, replicas along the ring, and how fixed slots and rendezvous hashing keep the same promise.

Four nodes become five

A cache tier spreads its keys over four nodes with the simplest rule there is, hash(key) % 4. Traffic grows, a fifth node joins, and the rule becomes hash(key) % 5. Here is what happens to five keys:

  • user:17 hashes to 2,941: node 1 before, node 1 after.
  • user:42 hashes to 7,330: node 2 before, node 0 after.
  • cart:9 hashes to 5,218: node 2 before, node 3 after.
  • session:3 hashes to 1,467: node 3 before, node 2 after.
  • price:88 hashes to 9,104: node 0 before, node 4 after.

Four of the five moved, and that is not bad luck. A key keeps its node only when its hash leaves the same remainder divided by 4 as divided by 5, which happens for one hash value in five. Going from N nodes to N + 1 moves about N keys out of every N + 1: 80% here, about 91% going from 10 nodes to 11. Losing a node, planned or not, reshuffles the same way.

In a cache, a key on the wrong node is a miss. Say the tier serves 50,000 reads a second at a 95% hit rate, with reads spread evenly over the keys, so the database sees 2,500. After the fifth node joins, only the keys that stayed put, one in five, can still hit: the hit rate falls to about 19%, and the database is asked for about 40,500 reads a second, sixteen times its usual load, until the cache refills. What the tier needed was for the new node to take its fair share, a fifth of the keys, and for every other key to stay put.

Hash the nodes too

Consistent hashing gets there by no longer computing the node from the node count. Take the hash function's whole output range, say 0 to 2³² − 1, and bend it into a circle, the ring. Each node gets a position on it, usually a hash of its name or address. Each key is hashed onto the same ring and belongs to the first node clockwise from it, so every node owns the arc between its predecessor and itself.

Now add a node. It lands between two existing nodes and takes over only the keys on the arc between its predecessor and itself, keys that used to belong to its successor. Nothing else changes owner. Remove a node and its arc passes to its successor, again leaving every other key alone. The mapping depends on where the nodes sit, not on how many there are, so a membership change moves roughly 1/N of the keys instead of nearly all of them.

Router hashes keys onto a ring of cache nodes

With one token per node, adding Cache D takes a slice from ONE neighbor; with virtual nodes it takes a small slice from every node — either way only ~1/N of the keys move.

Fewer keys moving does not mean none. A joining node owns its arc at once but holds none of its keys: in a cache they are misses until warmed, and in a store they must be streamed from the previous owner first, or reads come back empty. Every client or router also needs the same list of nodes, or two of them send the same key to different places; that list comes from a configuration service or a membership protocol like the one in Gossip Protocol. With the handoff and the shared list in place, the ring keeps churn cheap wherever a key must keep reaching the same server: distributed caches, sharded WebSocket and session tiers, load balancers that pin each client to one backend (what pinning costs: Load balancing & horizontal scaling).

One point per node is lumpy

The diagram draws the ideal: three caches with a third of the ring each. The ring promises that few keys move; it does not promise equal shares. With one position per node, the arcs are as uneven as random points make them: put three nodes at random positions and the largest arc averages about 61% of the ring, and in roughly half of such rings one node owns 60% or more, so a 60/30/10 split is ordinary. And when a fourth node joins, it takes its whole share from one neighbor: about 1/N of the keys on average, but it can be far more or far less, depending on where it lands.

Virtual nodes fix both. Each physical node takes many positions on the ring, often called tokens, and owns the small arc ending at each of them. Its share becomes the sum of many small arcs, and such sums even out; a bigger machine can take more tokens, and so a bigger share. When a node joins, its tokens land all around the ring and it takes a thin slice from every node; when one leaves, its keys spread over all the others instead of landing on a single successor.

Copies go clockwise

The ring also says where a key's replicas go. With replication factor R, a key is stored on the first R nodes clockwise from it, the scheme of Amazon's Dynamo design and of Cassandra. With virtual nodes, the walk skips tokens that belong to a physical node already chosen, so the R copies land on R different machines, and rack- or zone-aware placement skips further, so that losing one rack or zone does not take every copy. When a node dies, the next nodes clockwise already hold copies of its keys and can keep serving them; once the node is declared gone for good, not just unreachable, the cluster streams a new copy to restore R. Replication & read replicas takes it from there: how reads and writes across those copies agree.

The same promise without a ring

Fixed hash slots, as in Redis Cluster, hash every key into one of 16,384 slots and keep a table of which node owns each slot; the slot count never changes, so adding a node means handing it some slots, and the cost is a table of slot owners that every node, and every client that caches it, must keep current. Rendezvous hashing scores every node for each key with hash(key, node_id) and picks the highest; a departing node's keys go to their runners-up and nothing else moves, at the cost of one score per node on every lookup. Score by a node's position in a list instead of a stable ID, and a removal renumbers every node after it and reshuffles their keys: modulo hashing's problem again.

All three only decide placement. The ring spreads keys, not load: a key a hundred times hotter than the rest still burns its node, and Hot keys & cache stampedes has the defenses. Which value to hash, and what that does to range queries, is the business of Sharding & partitioning.

The number to check

One number says whether a design for the Consistent Hashing challenge works: how many keys change hands when a node joins. Label each node with its arc, add one, and mark what moves. A good run shows only ~1/N of the keys moving — from one neighbor with single tokens, or a thin slice from every node with virtual nodes. In Distributed Cache the same number decides whether a scale-out empties the cache, and Distributed Key-Value Store adds replicas along the ring.

Practice this