Consistent Hashing¶

The setup¶

You have data (lots of keys), and you have several servers. You need a simple rule that answers one question: which server should hold this key?

The rule must satisfy three things: 1. Every client that asks the question gets the same answer, without talking to each other. 2. The rule works with just the server list and the key -- no central coordinator. 3. When you add or remove a server, almost all keys stay where they are.

Consistent hashing is that rule.

Why the obvious approach breaks¶

The first idea everyone has is modulo (divide and take the remainder):

server = hash(key) % number_of_servers

Say you have 4 servers. A key with hash value 17 goes to server 17 % 4 = 1.

This works fine -- until you change the number of servers.

Here is the problem with real numbers. You add a fifth server. Now the same key goes to 17 % 5 = 2. Different server. The data is not there. Miss.

Let's count how much damage this causes:

• A key stays on the same server only if hash(key) % 4 happens to equal hash(key) % 5.
• Out of every 20 possible hash values (0 through 19), only 4 give the same result with both % 4 and % 5. Those are: 0, 1, 2, 3. That's 4 out of 20 = 20% stay, 80% move.
• The general formula: going from N servers to N+1, about 1/(N+1) of keys stay put. The rest move.

hash=17, 4 servers -> server 1
hash=17, 5 servers -> server 2      MOVED

hash=23, 4 servers -> server 3
hash=23, 5 servers -> server 3      stayed (got lucky)

hash=0,  4 servers -> server 0
hash=0,  5 servers -> server 0      stayed (small values survive)

hash=12, 4 servers -> server 0
hash=12, 5 servers -> server 2      MOVED

What this means in production:

• Cache servers: 80% of lookups miss at once. All those missed requests slam the database behind the cache in the same moment. This flood is called a thundering herd.
• Sharded storage (data split across servers, each server holding a slice): you must copy 80% of the data across the network to put it on the right server again.
• Sticky sessions (user tied to one server for their login state): users land on a different machine and lose their session.

And you pay this cost even for a single server reboot.

What's the best we could hope for? If one server out of N leaves, only its own share of keys (total_keys / N) must move -- those keys have nowhere to stay. Everything else should remain still. This property is called minimal disruption.

Modulo misses it by a factor of N. Instead of moving 1/N of keys, it moves nearly all of them.

The ring: the core idea¶

Karger and colleagues at MIT published the fix in 1997, originally for CDN caching. It later became the foundation of Akamai, Amazon's Dynamo, Cassandra, and most memcached clients.

How it works, step by step¶

Step 1: Make a circle from the hash range.

Your hash function produces numbers from 0 to some maximum (say 0 to 4,294,967,295 for a 32-bit hash). Imagine bending this number line into a circle, so the maximum wraps around and sits right next to 0. This circle is called the ring.

Step 2: Place the servers on the circle.

Hash each server's name. The resulting number tells you where that server sits on the ring.

hash("server-A") = 1000     -> position 1000 on the ring
hash("server-B") = 3500     -> position 3500 on the ring
hash("server-C") = 7200     -> position 7200 on the ring

Step 3: Place each key on the same circle.

Hash the key. Its number is its position on the ring.

Step 4: Walk clockwise to find the owner.

From the key's position, walk clockwise around the circle. The first server you bump into owns that key.

                 0 (top of circle)
                     |
          keyD   .--- ---.   A
               /           \
        C     |             |    keyA
              |             |
               \           /   B
                 '--- ---'
                    keyB
                keyC

  Walk clockwise from each key:
  keyA -> hits B first   (B owns keyA)
  keyB -> hits C first   (C owns keyB)
  keyC -> hits C first   (C owns keyC)
  keyD -> hits A first   (A owns keyD)

Why adding a server now moves almost nothing¶

Add server E between B and C on the ring:

  Before:                        After:
  keyA -> B                      keyA -> B       (same)
  keyB -> C                      keyB -> E       (moved to E)
  keyC -> C                      keyC -> C       (same)
  keyD -> A                      keyD -> A       (same)
                                          ^
                                 only keyB moved -- it was between B and E

The new server E "steals" keys only from the arc just before it (keys between B and E that used to go to C). Nothing else on the ring changes. Only keys that fall in E's new arc move. Everything else stays.

Removing a server is the mirror: its keys flow to the next server clockwise. Nobody else moves.

This is minimal disruption, and it comes naturally from the circle geometry. No coordination needed. Every client that knows the server list builds the same ring and reaches the same answer independently.

Virtual nodes: fixing the uneven spread¶

The problem with the plain ring¶

If you put just 5 servers at random positions on the circle, they won't be evenly spaced. One server might own a huge arc and another a tiny one:

A |------| B |--| C |----------------------| D |---| E |-----|
   17%      8%              41%               11%     23%

Server C owns 41% of all keys. It handles 5x the load of server B. It will run out of resources first.

Also, when a server dies, its entire load goes to just one neighbor (the next server clockwise). One server suddenly gets double the traffic.

The fix: put each server on the ring many times¶

Instead of placing server A at one position, place it at 160 positions using names like:

hash("server-a#0")   -> position 412
hash("server-a#1")   -> position 8891
hash("server-a#2")   -> position 22340
...
hash("server-a#159") -> position 4293001100

Each of these positions is a virtual node (also called vnode). The server's total load is the sum of 160 small arcs scattered around the ring, instead of one big (or small) arc.

Why this fixes the balance problem: Think of it like throwing darts at a board. If you throw 5 darts, they might cluster. If you throw 800 darts (5 servers x 160 virtual nodes), they spread out much more evenly. Mathematically, the unevenness shrinks in proportion to 1 / sqrt(V), where V is the number of virtual nodes per server. At V=160, the spread is about 8% of the average.

Real-world virtual node counts:

Two bonuses from virtual nodes:

1. Weighting by capacity. A server with twice the RAM gets twice the virtual nodes, so it owns twice the keys. Simple.
2. Spread-out failure recovery. When a server dies, its 160 arcs are scattered around the ring, so its load gets picked up by many different surviving servers instead of one unlucky neighbor.

The cost: the ring now holds servers x virtual_nodes entries, all kept in memory.

How lookup works in code¶

Store the ring as a sorted list of (position, server_name) pairs. To find which server owns a key:

1. Hash the key to get a position.
2. Binary search the sorted list for the first position >= the key's hash.
3. If you fall off the end of the list, wrap to index 0 (that's the circle wrapping around).

This runs in O(log(servers x virtual_nodes)) time. With 100 servers and 160 vnodes each, that's log2(16000) = about 14 comparisons. Fast.

type Ring struct {
    positions []uint32          // sorted list of positions on the ring
    owners    map[uint32]string // maps each position to its server name
    vnodes    int               // virtual nodes per server
}

func (r *Ring) Add(server string) {
    for i := 0; i < r.vnodes; i++ {
        p := hash32(fmt.Sprintf("%s#%d", server, i))
        r.positions = append(r.positions, p)
        r.owners[p] = server
    }
    slices.Sort(r.positions)
}

func (r *Ring) Get(key string) string {
    if len(r.positions) == 0 {
        return ""
    }
    h := hash32(key)
    i := sort.Search(len(r.positions), func(i int) bool {
        return r.positions[i] >= h
    })
    if i == len(r.positions) { // past the end, wrap to start
        i = 0
    }
    return r.owners[r.positions[i]]
}

For replication (storing copies of data on multiple servers): keep walking clockwise and collect the next R servers, but skip positions that belong to a physical server you already picked. If you don't skip, your three "replicas" could all be virtual nodes of the same physical machine -- so you'd have three copies on one box instead of three. For rack-aware or zone-aware placement, apply the same walk with a longer skip rule (skip servers in racks or zones you already used).

Picking the right hash function¶

The ring is a data structure. The hash function is what makes it work well or badly.

What you need from the hash function¶

1. Even spread. Output values must cover the full range evenly. If some ranges are more likely than others, some servers will be permanently overloaded.
2. Good avalanche. Changing one small thing in the input should completely change the output. Without this, server-a#1 and server-a#2 land near each other on the ring, and your 160 virtual nodes clump into a few clusters instead of spreading out.
3. Same result every time, everywhere. Same input must give the same output on every machine, every process, every restart, every language, every version. This is the requirement that trips people up the most. It has nothing to do with speed or quality.
4. Fast. You call it on every request.
5. Not necessarily cryptographic (resistant to deliberate attacks). You usually don't need to defend against someone crafting malicious inputs. Exception: when untrusted users choose the keys (see hash flooding below).

The common choices¶

Never use your language's built-in hash¶

This is the most common production bug in consistent hashing.

• Python: hash("abc") gives a different result every time you restart the program. Python randomizes its hash seed by default (PYTHONHASHSEED). Two clients build different rings and silently send keys to the wrong servers. Your cache hit rate drops and nothing errors out.
• Java: String.hashCode() is stable across restarts, but it is a weak function that clusters badly on similar strings.
• Go: The internal map hash is randomized per process and not even accessible to you.

Use a specific library function (like MurmurHash3 or xxHash). Write the function name in your config file, not just in code.

Hash flooding: when attackers choose the keys¶

If users control the keys (URLs, usernames, HTTP headers), an attacker can calculate keys that all land in the same arc on the ring. Every request hits one server. That server goes down. This is a denial-of-service attack that needs very little traffic to work.

The fix: use a keyed hash like SipHash with a secret shared across your servers. Without the secret, the attacker can't predict where keys will land.

Alternatives to the ring¶

The ring is not the only way to get minimal disruption, and it's often not the best.

Rendezvous hashing (highest random weight, HRW)¶

Skip the ring entirely. For each key, compute a score against every server and pick the server with the highest score:

def pick(key, servers):
    return max(servers, key=lambda s: hash64(f"{key}:{s}"))

A worked trace. Four servers, two keys, real scores from a hash (small numbers here for readability, but any hash function behaves the same way):

key "user:0":  A=640  B=949  C=333  D=468   -> winner B
key "user:1":  A=94   B=831  C=976  D=434   -> winner C

Now remove server C:

key "user:0":  A=640  B=949  D=468          -> winner B   (unchanged -- C was never the winner for this key)
key "user:1":  A=94   B=831  D=434          -> winner B   (MOVED -- C was the winner, so its keys fall to whoever scored second)

Only user:1 moves, and only because C actually owned it. Every other key's ranking among the remaining servers is untouched -- no ring, no virtual nodes, same minimal disruption as before.

How it achieves minimal disruption: When you remove a server, only the keys where it was the winner are affected. For those keys, the second-place server takes over. Every other key keeps the same winner.

Advantages over the ring: - Near-perfect balance with no virtual nodes and no ring in memory. - Weighting by capacity uses a clean formula: -weight / log(uniform01(hash)), take the max. Intuition: uniform01(hash) turns the hash into a random number between 0 and 1, and dividing a bigger weight into a small negative log shrinks the result less on average -- so a heavier server's score is bigger (less negative) more often, and it wins more ties without ever needing extra virtual copies of itself.

Disadvantage: Lookup costs O(N) because you score every server. Fine for 10 to 100 servers. Wasteful at 10,000 (a tree variant reduces this to O(log N)).

Rule of thumb: If your server count is small, rendezvous hashing is usually the better choice. Less code, better balance.

Jump consistent hash¶

Published by Lamping and Veach at Google in 2014. Maps a key to a bucket number from 0 to N-1 with perfect balance, zero memory, and about O(ln N) time.

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = -1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1));
  }
  return b;
}

What the loop is doing: b is "the last bucket number accepted so far." Each pass, the key is scrambled (key = key * big_odd_number + 1) and the scrambled value decides whether to jump forward to a new candidate bucket j. Different keys scramble differently and land on different final buckets b, but the same key run against the same num_buckets always produces the same b. No table is stored anywhere -- the arithmetic itself reproduces the ring's "walk forward until you hit a new owner" behavior.

A worked trace (real output of the function above, on pre-hashed 64-bit keys):

key         bucket@4   bucket@5
user:1      0          0            same
user:3      2          2            same
user:5      3          3            same
user:0      1          1            same
user:6      1          4            MOVED

Going from 4 buckets to 5, only user:6 moves -- straight into the new bucket 4. Nothing else changes. That is exactly the guarantee the algorithm gives: adding bucket N only ever steals keys away from the others, it never reshuffles keys between the buckets that already existed.

The big catch: Buckets are numbered 0, 1, 2, ..., N-1. You can only add or remove the last bucket. If server 3 out of 10 dies, you can't just remove bucket 3 -- the scheme can't express that. Use it only for sharding where you grow and shrink the count from the end, not for a set of machines that fail in random order.

Maglev hashing¶

Google's software load balancer, published 2016. Build a lookup table of fixed size M (a prime number, commonly 65,537). Each server generates a preference order for the table positions. Servers take turns claiming their next preferred free slot until the table is full.

• Lookup is one array access: table[hash(key) % M]. That's O(1), no searching.
• Balance is nearly perfect because the table is filled by turn-taking rather than by random placement.
• Disruption on change is small but not minimal. A few extra keys move compared to a ring.
• Rebuilding the table costs O(M log M), so it fits a load balancer that rebuilds when servers change, not a client that rebuilds constantly.

Envoy offers both ring_hash and maglev. Maglev is the better default there.

Consistent hashing with bounded loads¶

Published by Mirrokni, Thorup, and Zadimoghaddam in 2016.

The problem it solves: Consistent hashing balances the key space (how many keys each server owns), not the traffic (how many requests those keys get). One viral key can overload one server while the rest sit idle.

The fix: Set a hard cap on each server: no server may handle more than (1 + e) times the average load. If a key hashes to a server that's already full, keep walking clockwise until you find one with room. This guarantees no server is overwhelmed, and you still move few keys when membership changes.

Used by HAProxy (hash-balance-factor) and Vimeo, who reported it significantly reduced their backend load.

Multi-probe and anchor hashing¶

• Multi-probe consistent hashing (2015): Instead of placing V virtual nodes per server on the ring, place each server once and hash each key k times, taking the closest result. Same balance, much less memory: O(N) instead of O(N x V).
• AnchorHash (2019): Achieves minimal disruption and full balance while supporting arbitrary removal and re-addition of servers, with much less memory than virtual nodes.

Quick decision guide¶

Common mistakes¶

• Rings that disagree. Every client must use the same hash function, same virtual node count, same naming format (a#1 vs a-1 vs a:1), and same server list. One mismatched client writes to a server nobody else reads. Nothing errors out. You just see a cache hit rate that's quietly too low. Fix: put ring parameters in shared config and log the ring's checksum at startup.
• Unstable server identity. If you use the server's IP address as its ring key, a new IP after a restart moves that server's entire arc. Use a stable id instead.
• Flapping membership. A server that leaves and rejoins every 30 seconds moves total_keys / N keys each time, both ways. Add a grace period before removing a server from the ring.
• Cold start after a change. Minimal disruption still means total_keys / N keys move. For a cache, that's total_keys / N misses arriving all at once. Warm the new server first, or add it during low traffic.
• Hot keys stay hot. Consistent hashing decides where a key goes, not how much traffic it gets. One popular key still hits one server. Fix: use bounded loads, or split the key into copies (key#0 through key#9) and read from a random copy.
• Replicas on the same machine. When walking clockwise for replicas, skip virtual nodes that belong to a physical server you already picked. Otherwise, your three "replicas" could all live on the same box.

Glossary¶

• Hash function -- turns any input into a fixed-size number. Same input always gives the same number.
• Avalanche -- changing one bit of input changes about half the output bits. Means similar inputs produce very different outputs.
• Keyed hash -- a hash that also takes a secret, so nobody can predict its output without knowing the secret.
• Minimal disruption -- when one server out of N leaves, only its own share (about 1/N of keys) changes owner. Everything else stays.
• Ring / hash space -- the hash output range bent into a circle, so the largest value wraps back to zero.
• Virtual node (vnode) -- one of several ring positions that all belong to the same physical server.
• Sharding -- splitting data across servers, each server owning a slice.
• Thundering herd -- many clients hitting the same backend at the same moment because a cache layer went cold.
• Hash flooding -- an attack where someone crafts inputs so they all land on one server.
• HRW (highest random weight) -- rendezvous hashing: score every server for each key, pick the server with the highest score.
• Permutation -- a reordering of a list. In Maglev, each server generates its own private order for claiming table slots.