Consistent Hashing

Keys and nodes are hashed onto the same ring, and each key belongs to the first node clockwise from it. A node's place on the ring depends only on its own name, so adding a node takes over only the arcs just before its positions, and removing one hands its arcs to the next node: every other key stays where it is. Below, add and remove nodes, and give each node more positions on the ring to even out the load.

the hash ring, 1 token per nodeN3N1N2N4Node 1: 48%Node 2: 4%Node 3: 19%Node 4: 29%ticks are node tokens; a key goes clockwise to the next oneAppNode 1 48% of ringNode 2 4% of ringNode 3 19% of ringNode 4 29% of ring

The ring in the panel is the hash space, starting at the top and running clockwise. Coloured arcs show which node owns each stretch; the small dots inside are the 40 sample keys. Add or remove a node and the keys that change owner glide to their new node, ringed so you can count them. A node turns red when it serves well above its share of requests.

What a resize moves, and how even the ring is
KB

  1. 1. Total data

    users x data per user = 500M x 10 KB = 4.66 TB

  2. 2. Adding one node with hash mod N

    about N / (N + 1) of the data moves: 4.35 TB

  3. 3. Adding one node on the ring

    the new node takes about its fair share, 1 / (N + 1), and only that moves: 318 GB

  4. 4. How even the ring is

    with T random tokens per node, a node's share typically differs from its fair share by about 1 / √T: ±25% with 16 tokens
  5. One token per node moves little data but leaves some nodes with twice their share. Many tokens per node fix the balance and spread a new node's intake across all the others, at the cost of a bigger ring to keep track of.
Where these formulas come from

Step 1 is the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1, whose consistent hashing chapter this page follows. Step 2 follows from how modulo behaves. Step 3 assumes the new node's tokens claim its fair share, which is what many tokens per node make likely. Step 4 is a statistical rule of thumb: a node's share is the sum of T random arcs, and the relative spread of such a sum shrinks like 1 / √T. It is an approximation, not an exact bound; the ring above shows real values for the 40-key scene.

Limits of consistent hashing

Few tokens, uneven nodes

Random positions make random arc sizes. With one token per node, one node can own twice its share while another owns almost nothing. Virtual nodes are the standard fix.

One hot key is still one node

The ring spreads different keys. Every request for the same key still goes to the same node, so a celebrity or a viral item needs caching or deliberate splitting.

Range queries scatter

Like any hash placement, the ring breaks key order: neighbouring ids land on different nodes, so a range query must ask every node.

More tokens, more neighbours

Each token gives a node more neighbours on the ring. With replication, that means each node shares data with more of the others, and more failure combinations matter.

How Dynamo and Cassandra use the ring

Amazon's Dynamo paper made the ring with virtual nodes well known; Cassandra is built on the same design.

Amazon Dynamo: the ring and virtual nodes

A key is placed by "walking the ring clockwise to find the first node with a position larger than the item's position." The advantage: "departure or arrival of a node only affects its immediate neighbors". The paper names the problem the scene shows, that random positions lead "to non-uniform data and load distribution", and the fix: each node gets "multiple positions (henceforth, tokens) in the ring."

Apache Cassandra: tokens per node

Cassandra "maps every node to one or more tokens on a continuous hash ring", noting that with plain modulo "adding a single node might invalidate almost all of the mappings." Its docs explain that "uneven token ranges lead to uneven request load", and warn that "The more tokens you have, the higher the probability of an outage." The num_tokens setting defaults to 16 in the 5.0 configuration reference, down from the 256 once needed with random tokens.
Sources and credibility

The Dynamo paper is a peer-reviewed paper by Amazon engineers (SOSP 2007); the Cassandra pages are the Apache project's official documentation. Quoted phrases are short attributed quotations; everything else is described in our words.