CS Fundamentals Trainer · Guides

Consistent hashing

Why hash mod N breaks when servers change, how the ring and virtual nodes fix it, with code and alternatives.

14 min read

Consistent hashing is a way to decide which server owns which key, so that when servers join or leave, only a small share of the keys has to move. It sits underneath caches, databases, load balancers and CDNs, and it is a staple of system design interviews. The idea is small enough to implement in thirty lines, and this guide does that in four languages.

1. The problem: spreading keys over servers

You have a cache or a database too big for one machine, so you split the keys over N servers. You need a rule that, given a key, always names the same server, from any client, without asking anyone. The obvious rule is:

server = hash(key) mod N

It spreads keys evenly and costs nothing. Its flaw appears the moment N changes.

What happens when N changes

Add a fifth server to four, and hash(key) mod 4 becomes hash(key) mod 5. For most keys the answer changes. I measured it with 100 000 keys:

The larger the cluster, the worse it gets: nearly all keys move for a single added machine. In a cache, that is a sudden wall of misses that lands on your database. In a database, it is a massive data migration. The ideal is that a new server takes only its fair share (1/(N+1) of the keys) and nothing else moves. Consistent hashing achieves that [1].

2. The ring

Picture the output range of the hash function, say 0 to 2^32 − 1, bent into a circle, so the largest value is next to 0. Then:

1. Place each server on the ring by hashing its name (or address).
2. Place each key on the ring by hashing the key.
3. A key belongs to the first server found going clockwise from the key's position (wrapping around at the end).

Diagram: A ring with three servers and four keys (read clockwise)

Reading the picture: the keys at 25 and 40 go clockwise to the next server, B at 55. The key at 70 goes to C at 90. The key at 95 passes the end of the ring and wraps around to A at 10. Every server owns the stretch of the ring that lies between its predecessor and itself.

Adding and removing servers

Now add a server D at position 80:

Diagram: Adding Server D at 80 takes keys only from its neighbour

Only the keys between 55 and 80 (here, the key at 70) change owner, from C to D. Every other key stays where it was. If a server leaves, only its keys move, to the next server clockwise. With N servers, the expected share that moves is about 1/N. In my run, adding an 11th server to a ring of 10 moved 8.9 % of the keys, against the ideal 9.1 %; and every key that moved went to the new server and nowhere else.

3. Uneven load and virtual nodes

There is a catch. With one point per server, servers land at random places on the circle, and the gaps between them are very uneven. One server may own a gap three times larger than another's. I measured the load for 10 servers and 100 000 keys:

The fix is virtual nodes ("vnodes"): each server is placed on the ring many times, under names such as server-a#0, server-a#1, server-a#2... Its share becomes the sum of many small, random gaps, and sums of many small random pieces are close to even. A hundred to a few hundred points per server is common. Virtual nodes have a second benefit: when a server leaves, its load spreads over many other servers instead of falling entirely on one neighbour (which might then fail too, and so on). They also let you give a bigger machine more points than a smaller one, proportionally to its capacity.

The cost is memory and lookup time: 100 servers with 200 points each is 20 000 entries. Looking up a key is a binary search over a sorted array, which is fast (about 15 steps).

4. A working implementation

The ring is a sorted array of positions. A lookup hashes the key and finds the first position greater than it with binary search; if there is none, it wraps to the first entry. Four versions follow (pick a language on the tabs; your choice is remembered). All use SHA-256 as the hash and keep its first 8 bytes (6 in JavaScript, to stay within what a number holds exactly). A fast non-cryptographic hash is fine too, as long as it spreads values well.

import bisect
import hashlib


def h(s):
    return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")


class Ring:
    def __init__(self, vnodes=150):
        self.vnodes = vnodes
        self.hashes = []           # sorted positions on the ring
        self.owner = {}            # position -> server

    def add(self, server):
        for i in range(self.vnodes):
            pos = h(f"{server}#{i}")
            self.owner[pos] = server
            bisect.insort(self.hashes, pos)

    def remove(self, server):
        for i in range(self.vnodes):
            pos = h(f"{server}#{i}")
            del self.owner[pos]
            self.hashes.remove(pos)

    def get(self, key):
        if not self.hashes:
            raise LookupError("no servers")
        i = bisect.bisect_right(self.hashes, h(key)) % len(self.hashes)   # % wraps around
        return self.owner[self.hashes[i]]

type Ring struct {
	vnodes int
	hashes []uint64          // sorted positions on the ring
	owner  map[uint64]string // position -> server
}

func NewRing(vnodes int) *Ring {
	return &Ring{vnodes: vnodes, owner: map[uint64]string{}}
}

func hash(s string) uint64 {
	sum := sha256.Sum256([]byte(s))
	return binary.BigEndian.Uint64(sum[:8])
}

func (r *Ring) Add(server string) {
	for i := 0; i < r.vnodes; i++ {
		pos := hash(fmt.Sprintf("%s#%d", server, i))
		r.owner[pos] = server
		r.hashes = append(r.hashes, pos)
	}
	sort.Slice(r.hashes, func(a, b int) bool { return r.hashes[a] < r.hashes[b] })
}

func (r *Ring) Remove(server string) {
	kept := r.hashes[:0]
	for _, pos := range r.hashes {
		if r.owner[pos] == server {
			delete(r.owner, pos)
			continue
		}
		kept = append(kept, pos)
	}
	r.hashes = kept
}

// Get returns the server that owns key, or "" when the ring is empty.
func (r *Ring) Get(key string) string {
	if len(r.hashes) == 0 {
		return ""
	}
	x := hash(key)
	i := sort.Search(len(r.hashes), func(i int) bool { return r.hashes[i] > x })
	if i == len(r.hashes) {
		i = 0 // wrap around
	}
	return r.owner[r.hashes[i]]
}

const crypto = require("node:crypto");

// 48 bits are plenty, and a JavaScript number holds them exactly
const h = (s) => crypto.createHash("sha256").update(s).digest().readUIntBE(0, 6);

class Ring {
  constructor(vnodes = 150) {
    this.vnodes = vnodes;
    this.points = []; // { pos, server }, sorted by pos
  }

  add(server) {
    for (let i = 0; i < this.vnodes; i++) {
      this.points.push({ pos: h(`${server}#${i}`), server });
    }
    this.points.sort((a, b) => a.pos - b.pos);
  }

  remove(server) {
    this.points = this.points.filter((p) => p.server !== server);
  }

  get(key) {
    if (this.points.length === 0) throw new Error("no servers");
    const x = h(key);
    let lo = 0;
    let hi = this.points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid].pos > x) hi = mid;
      else lo = mid + 1;
    }
    return this.points[lo % this.points.length].server; // % wraps around
  }
}

using System.Buffers.Binary;
using System.Security.Cryptography;
using System.Text;

public sealed class Ring
{
    private readonly int _vnodes;
    private readonly List<(ulong Pos, string Server)> _points = new();   // sorted by Pos

    public Ring(int vnodes = 150) => _vnodes = vnodes;

    private static ulong Hash(string s) =>
        BinaryPrimitives.ReadUInt64BigEndian(SHA256.HashData(Encoding.UTF8.GetBytes(s)));

    public void Add(string server)
    {
        for (int i = 0; i < _vnodes; i++) _points.Add((Hash($"{server}#{i}"), server));
        _points.Sort((a, b) => a.Pos.CompareTo(b.Pos));
    }

    public void Remove(string server) => _points.RemoveAll(p => p.Server == server);

    public string Get(string key)
    {
        if (_points.Count == 0) throw new InvalidOperationException("no servers");
        ulong x = Hash(key);
        int lo = 0, hi = _points.Count;
        while (lo < hi)
        {
            int mid = (lo + hi) / 2;
            if (_points[mid].Pos > x) hi = mid; else lo = mid + 1;
        }
        return _points[lo % _points.Count].Server;     // % wraps around
    }
}

These are sketches: a real one protects the ring with a read-write lock (reads are far more common than changes), and swaps in a whole new ring instead of editing the live one. Remove is linear in the number of points, which is fine for a handful of changes a day.

Try it yourself: add 10 servers, map 100 000 keys, add an 11th server and count how many keys changed owner. You should see about 9 %, and every changed key should now belong to the new server.

5. Replication: more than one owner

Real systems keep several copies of each key. With a ring, the natural rule is: the owner is the first server clockwise, and the replicas are the next servers clockwise after it, skipping virtual nodes that belong to a server already chosen (otherwise two copies could land on the same machine). Amazon's Dynamo calls this the preference list [2]. Cassandra works the same way. If a server dies, the next one in the list already has a copy and takes over, and the ring gives each remaining server a small, equal share of the extra work.

6. When the ring is not the answer

Consistent hashing has several relatives, and knowing why they exist is a good interview answer.

Note that none of them fixes a hot key: if one key gets half of all requests, whoever owns it is overloaded, however well the keys are spread. For that you replicate the key, cache it in front, or split it into several keys.

7. Where you meet it

• Distributed caches: memcached clients commonly use a ring (known as ketama) so that losing a cache node does not empty the whole cache.
• Databases: Dynamo, Cassandra, and Riak partition data on a ring.
• Load balancing: sending the same user or key to the same backend (so its local cache is warm), without keeping a table of assignments.
• CDNs and object stores: choosing which node stores which object.
• Sharding in your own app: a library decides which database holds a customer. URL shorteners and caches use it for this.

8. Questions interviewers like to add

"Why not just keep a table of key → server?"

A table works when the number of keys is small, but then it is itself a big shared piece of state that every client needs and that must stay consistent. Hashing needs no shared state beyond the list of servers.

"How do clients learn that a server joined?"

The server list has to reach every client: through a coordination service (ZooKeeper, etcd, Consul), a gossip protocol (Dynamo and Cassandra), or a config pushed out. For a short time clients may disagree about the ring. A read can then go to the old owner and miss. That is acceptable for a cache. For a database, the system must hand data over carefully: copy first, switch ownership after.

"What happens to the data on a server that is removed?"

On a crash, replicas have it. On a planned removal, the departing server streams its ranges to the new owners before leaving. When a server is added, it must fetch its ranges from the current owners, and until it has them the old owners still answer.

"How many virtual nodes?"

Enough that the spread is acceptable: 100 to 200 per server gives load within about 10 % of average in my test. More points even out load further, at the price of memory, slower rebuilds, and more rebalancing work when a node joins or leaves. Weight them by machine size.

"How do you handle a server that is slow, not dead?"

The ring does not know about health. Add health checks and remove failing servers from the ring (or skip them and use the next replica). To avoid flapping, require several failed checks before removal.

9. Things to mention in an interview

• Start with hash mod N and show why it breaks: nearly everything moves.
• Draw the ring and say a key goes to the next server clockwise.
• Say that only about 1/N of the keys move when a server changes.
• Bring up uneven spread yourself, and fix it with virtual nodes and weights.
• Mention replication along the ring, and how clients find out about changes.
• Name an alternative (rendezvous, jump hash, hash slots) and when you would prefer it.

Quick recap

1. hash(key) mod N moves almost every key when N changes.
2. A ring assigns each key to the next server clockwise; adding or removing a server moves only about 1/N of the keys.
3. One point per server gives uneven load; 100 to 200 virtual nodes per server make it nearly even.
4. Lookup is a binary search over a sorted array of positions.
5. Replicas are the next distinct servers along the ring.
6. Rendezvous hashing, jump hash, hash slots and Maglev solve the same problem with different trade-offs.
7. A hot key is not a hashing problem; cache or split it.

Sources

1. Karger et al., Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997. The original idea.
2. DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. The ring, virtual nodes, and preference lists.
3. Wikipedia, Rendezvous hashing. Thaler and Ravishankar's highest random weight scheme.
4. Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm, 2014. Jump consistent hash.
5. Redis documentation, Redis cluster specification. The 16 384 hash slots.
6. Mirrokni, Thorup and Zadimoghaddam, Consistent Hashing with Bounded Loads, 2016.
7. Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016.

Practise this topic: Resilience & Scalability Data scaling Resilience & Scalability Load balancing Distributed Systems & Messaging

More guides