The Ring: Consistent Hashing, and Why hash % N Ruins Your Day

You have a fleet of cache servers and you need to decide which server owns which key. The obvious answer is server = hash(key) % N. It is fast, it is balanced, and it is a trap.

The trap springs the day you change N. Go from 4 servers to 5 and the modulus shifts under almost every key: hash % 4 and hash % 5 agree for only a small fraction of inputs. So adding one server remaps roughly 80% of your keys to different servers. Every one of those is now a cache miss, all at the same moment, and your origin database gets the full unfiltered load right when you were trying to scale up to handle more of it. The same disaster happens when a server dies. hash % N makes membership changes maximally disruptive.

Put the servers on a circle

Consistent hashing fixes this with a change of mental model. Instead of buckets numbered 0 to N-1, imagine the hash space (say, all 64-bit values) bent into a ring. Hash each server to a point on the ring. To find a key's owner, hash the key to a point and walk clockwise to the first server you hit, wrapping around the end if you run off it.

The payoff is local change. When you add a server, it lands somewhere on the ring and takes over only the arc between it and the previous server clockwise. Every key on every other arc stays exactly where it was. Add or remove a node and you move about 1/N of the keys, not 80% of them. The blast radius of a membership change shrinks to a single arc.

Virtual nodes, so the load is even

One ring point per server is not enough, because random points leave uneven gaps, and a server that happens to own a big arc gets hammered. The fix is virtual nodes: place each real server at many points on the ring (say 100), each from a slightly different hash like hash("cache-2#37"). With a hundred small arcs each, every real server ends up owning roughly its fair share, and removing a server scatters its keys across many neighbors instead of dumping them all on one.

pub struct Ring {
    replicas: usize,
    ring: Vec<(u64, String)>, // (hash, node), kept sorted by hash
    nodes: HashSet<String>,
}

impl Ring {
    pub fn add(&mut self, node: &str) {
        if !self.nodes.insert(node.to_string()) { return; }
        for i in 0..self.replicas {
            let h = hash(&format!("{node}#{i}"));
            self.ring.push((h, node.to_string()));
        }
        self.ring.sort_by_key(|&(h, _)| h); // keep the ring ordered
    }
}

Lookup is a binary search

Because the ring is a Vec sorted by hash, "the first node clockwise from a key" is just a binary search for the first entry whose hash is greater than the key's hash, wrapping to index 0 if there is none:

pub fn get(&self, key: &str) -> Option<String> {
    if self.ring.is_empty() { return None; }
    let h = hash(key);
    let idx = self.ring.partition_point(|&(kh, _)| kh < h) % self.ring.len();
    Some(self.ring[idx].1.clone())
}

partition_point is the standard library's clean way to say "find the boundary in a sorted slice," and the % len is the wraparound that closes the circle. O(log n) per lookup, where n is the number of virtual nodes.

Where you have already met this

Consistent hashing is the sharding strategy behind memcached client libraries, Amazon's Dynamo and its descendants (Cassandra, Riak), and many load balancers and CDNs deciding which cache node serves a given URL. Anywhere a set of servers comes and goes and you want key-to-server assignment to stay stable across those changes, this is the tool.

The one idea to keep

The whole technique is a reframe: stop numbering your buckets and start placing both keys and servers in the same space, then assign each key to its nearest server. Numbered buckets make membership changes global. A shared ring makes them local. Add virtual nodes for balance, sort the ring for fast lookup, and a fleet that grows and shrinks stops taking your cache hit rate down with it.

Build it yourself. Solve the Consistent Hashing challenge on barehands and get graded on correctness and speed. No crates, just the standard library.