Hash the servers too

Consistent hashing starts with one move. Stop hashing keys onto servers, and hash both keys and servers into the same space.

Take the whole range a hash can produce and bend it into a circle, so the top wraps back round to zero. Each of your servers hashes, by its name, to a point on that circle. Each key hashes to its own point. A key belongs to the first server you meet walking clockwise from where the key landed.

The growth scenario runs differently now. Adding a server drops one new point onto the circle.

The only keys whose clockwise-next server changed are the ones sitting in the arc between the new point and the one before it. The new server takes that arc from its neighbour, and nothing else moves at all. With 10 servers that is about a tenth of your keys, which is the theoretical minimum, since a new server has to own something.

Removing one is the mirror image. Its arc slides onto the neighbour clockwise of it, and every other key stays exactly where it was.

The blast radius, compared

Compare the two blast radii side by side. Remainder maths at 10 servers: add one, 90 percent of keys move. The ring at 10 servers: add one, 9 percent move.

That single property turns resizing your cluster from a scheduled catastrophe into a routine Tuesday. It is why the idea spread from a 1997 paper about caching web pages into essentially every distributed datastore built since.

Written out, it is smaller than its reputation. Keep your server positions in a sorted array and hash your key. Binary search for the first position at or after it, wrapping to the start if you run off the end. Thirty lines in most languages.

The subtle problems are not in the lookup. They are all in how evenly the load spreads, which is the next lesson.

the shape of it

step 1 of 3

A key belongs to the first node clockwise from its hash, so adding a node claims only the arc behind it.

the whole ring, in about fifteen lines

Java

// Servers and keys are hashed into the same space. A key belongs
// to the first server clockwise from where it lands.
TreeMap<Long, String> ring = new TreeMap<>();

void addServer(String name) {
  for (int i = 0; i < 128; i++) {          // virtual nodes, for even spread
    ring.put(hash(name + ":" + i), name);
  }
}

String serverFor(String key) {
  Long at = ring.ceilingKey(hash(key));    // walk clockwise
  if (at == null) at = ring.firstKey();    // past the end, wrap to the start
  return ring.get(at);
}

// Add a server and only the keys in its arcs move. With ten servers
// that is about a tenth of them, not ninety percent.

Worked example

After election night, Jonas rebuilds placement on a ring. Each of his 10 cache nodes hashes to a position on the 2^32 circle, and the client binary-searches a sorted array of those positions per lookup, adding about a microsecond, which is nothing next to a 300-microsecond network hop. Two months later Black Friday planning calls for 2 more nodes. He adds them one at a time during lunch, watching the dashboards: each addition moves roughly 1/11th and then 1/12th of keys, the hit rate dips from 96 to about 88 for six minutes, and MySQL load bumps from 380 to 700 queries per second, well inside its 4,000 capacity. No maintenance window, no incident channel. The same operation that once caused a 25-minute brownout is now something he does without telling anyone, which is the whole point.

The Hash Ring

Hash the servers too

The blast radius, compared

Worked example