Consistent Hashing

Back to Study

Consistent Hashing

When data is spread across multiple servers, something has to decide which server owns a given key. The obvious answer is to hash the key and take it modulo the number of servers. That answer works right up until the number of servers changes, at which point it fails badly enough to take a system down.

The obvious approach: hash(key) % N

Distributing 8 keys across 4 servers with hash(key) % N

Four servers, eight keys. Hash each key, take the result modulo 4, and that index is the server that owns it. This is genuinely good at the one job it was given: keys land evenly, lookups are O(1), and there is no bookkeeping to maintain. As long as N never changes, nothing is wrong with it.

Why it falls apart the moment N changes

N sits in the denominator. Change it and you change the answer for almost every key at once, not just the keys that lived on the server that left.

Take the same 8 keys and lose one server, so N goes from 4 to 3. Five of the eight keys relocate, and only two of those were on the server that actually died. The other three moved for no reason beyond the arithmetic shifting under them. At real scale this approaches every key moving.

For a cache that means a near total miss storm: every relocated key is now looked up on a server that has never seen it, and the whole load lands on the database at once. For a sharded datastore it means physically moving most of your data. All triggered by something as routine as one machine rebooting.

The fix: put servers and keys on the same ring

Consistent hashing removes N from the arithmetic entirely.

Hash into a fixed circular space, say 0 to 2^32 - 1, with the end wrapping back around to the start. That space never resizes, because its size is not derived from the number of servers.

Step 1: place the servers

Servers hashed onto a fixed circular hash space

Each server is hashed by something stable about it, usually its name or IP address, and that hash is its position on the ring. Nothing about this depends on how many servers exist.

Step 2: place the keys and walk clockwise

A key is owned by the first server found walking clockwise

Keys are hashed into the same space. A key belongs to the first server found walking clockwise from where the key landed. That is the entire lookup rule. Each server effectively owns the arc that ends at its own position.

Step 3: watch what happens when a server leaves

Removing a server only reassigns the arc it owned

Only the arc belonging to the departed server is reassigned, and it goes to that server's clockwise neighbour. Every key outside that arc keeps exactly the same answer, because the ring positions of all the other servers never moved.

Instead of remapping nearly everything, you remap roughly 1/N of the keys, and only the ones that genuinely have to move. Adding a server is the mirror image: the new server takes a slice out of one neighbour's arc, and nothing else is disturbed.

Virtual nodes

A ring with one point per server has a real weakness. With only a few servers their positions are effectively random, so the arcs between them come out wildly uneven. One server can own a far larger slice than another purely by luck of where its hash landed. Remove a server and its entire arc lands on a single neighbour, which can then buckle under the doubled load.

The standard fix is virtual nodes: place each physical server at many points on the ring, each derived from a different hash, such as server1-a, server1-b, and so on.

Each server placed at many scattered points on the ring

Lookup does not change at all; keys still walk clockwise to the nearest point. But now each physical server owns many small scattered arcs instead of one large contiguous one. Two things improve at once:

  • The share per server evens out as the number of virtual nodes grows.
  • When a server leaves, its many small arcs are spread across all the remaining servers rather than dumped on one unlucky neighbour.

The tradeoff is memory, since you store a few hundred ring entries per server instead of one. That is a trivial price for the balance it buys. For a sense of real world scale, Discord's own open source ring library defaults to 512 virtual nodes per physical node (see sources below).

A real system: Discord

Discord is a useful example because they published how they do it and then open sourced the library.

How Discord maps a guild to a node using a consistent hash ring

In simple terms:

  1. Every Discord server (called a guild internally) has to live somewhere specific, because one place needs to be responsible for ordering its messages and fanning them out.
  2. Discord hashes the guild_id onto a consistent hash ring. The ring says which machine owns that guild.
  3. That machine runs a single process for the guild. All of that guild's traffic flows through it, so message ordering comes for free: one process handling everything naturally serializes it.
  4. Your session, the process behind your WebSocket connection, subscribes to that guild process and receives what it publishes.

The payoff is the same property as before. When Discord adds or loses a machine, only the guilds sitting in the affected arcs have to move. Every other guild never notices. With hash % N, every guild on the platform would relocate at once, which at their size is not a recoverable event.

One confusing detail worth separating

Discord's public bot API shards with plain modulo: (guild_id >> 22) % num_shards. That is documented in their developer docs and is a different mechanism from the internal ring. It is also a neat illustration of the cost, because changing a bot's shard count forces every shard to reconnect. The >> 22 simply drops the timestamp bits out of a snowflake ID so the spread is even.

Has Discord changed any of this?

Checked while writing this, and the answer has two halves:

  • The consistent hashing itself is unchanged and still current. Discord's ex_hash_ring library is published at version 6.0, and its README still describes it as production ready, actively maintained, and in use at Discord.
  • The message storage did change. Discord migrated messages from Cassandra to ScyllaDB, completing in May 2022, going from 177 Cassandra nodes down to 72 ScyllaDB nodes. This changed the database, not the technique: Cassandra and ScyllaDB are both Dynamo style stores that partition data across a token ring of their own. Messages are partitioned by channel plus a static time bucket.
  • A caution on dates: several secondary articles date the migration to 2023, because that is when Discord gave the conference talk about it. Discord's own post says the migration finished in May 2022.

Where else this shows up

Consistent hashing appears wherever a set of machines owns partitioned data and that set is expected to change:

  • Distributed caches. The original 1997 paper was motivated by web caching, which is where the technique comes from.
  • Dynamo style databases. Cassandra, ScyllaDB, Riak and DynamoDB all place nodes on a token ring and assign partitions by walking it.
  • CDN and load balancer routing, where you want the same client or object to keep landing on the same edge node so its cache stays warm.
  • Sharded application state, like Discord's guilds above, or any system where a logical entity must have exactly one owner at a time.

The common thread is that it turns "a machine went away" from a global event into a local one. That is the difference between a routine server replacement and an outage.

Implementing it in your project

A consistent hash ring takes a few lines with a sorted map. In Java, a TreeMap keeps ring positions sorted, and ceilingEntry finds the first server clockwise:

class HashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private static final int VIRTUAL_NODES = 100;

    void addServer(String server) {
        for (int i = 0; i < VIRTUAL_NODES; i++) ring.put(hash(server + "#" + i), server);
    }

    void removeServer(String server) {
        for (int i = 0; i < VIRTUAL_NODES; i++) ring.remove(hash(server + "#" + i));
    }

    String serverFor(String key) {
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
        return (e != null ? e : ring.firstEntry()).getValue(); // wrap around past the top
    }

    private static long hash(String s) { /* a well-mixed 64-bit hash, e.g. from MurmurHash3 */ }
}

In Python, the same idea uses a sorted list of positions and bisect to find the next one. Use a well-mixed hash function rather than String.hashCode(), whose output for similar strings is poorly spread. In practice, most teams use the hashing built into their data store (Cassandra, DynamoDB, Redis Cluster clients) rather than writing their own ring.

Sources and credibility

Everything above is written from scratch and no text is reproduced from these sources. They are listed so the claims can be checked, and grouped by how directly they come from the systems described.

Primary (the organisation's own material, highest confidence)

Academic (the origin of the idea)

  • Karger, Lehman, Leighton, Panigrahy, Levine and Lewin, Consistent Hashing and Random Trees, ACM STOC, 1997. The paper that introduced consistent hashing, in the context of distributed web caching.

Secondary (useful context, verify before relying on)

  • ScyllaDB's talk pages and assorted engineering write ups covering the Discord migration. These are accurate on the broad shape but several misstate the migration date as 2023, which is the conference date rather than the migration date.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Where a specific number is quoted, such as the 512 virtual node default or the 177 to 72 node reduction, it is a factual figure attributed to the primary source above rather than copied prose.