Consistent Hashing

How to spread keys over a changing set of servers so that adding or removing one moves only a small share of them: the hash ring, virtual nodes, replication, and the main alternatives.

Overview

When data or traffic is spread over many servers, every request needs a rule that says which server owns a key. The obvious rule is to hash the key and take the remainder after dividing by the number of servers. It works until that number changes. Add or lose one server and almost every key gets a new owner. In a cache, that turns almost every cached item into a miss at the same moment.

Consistent hashing is a rule for which adding or removing a server moves only a small share of the keys, about one server's worth. It was introduced for web caching in a 1997 paper by David Karger and five co-authors; two of them, Tom Leighton and Daniel Lewin, went on to launch Akamai in 1998. Today the same idea places data in Cassandra, picks servers in memcached clients built on the ketama library, and keeps requests on the same backend in load balancers such as NGINX, HAProxy and Envoy.

This chapter builds the idea step by step: why modulo hashing fails, how the ring works, why virtual nodes are needed, how copies are placed on a ring, and the four alternatives interviewers like to ask about: rendezvous hashing, jump consistent hash, Maglev hashing and bounded loads.

What you will be able to do

  • Work out how many keys move when a server joins or leaves, with modulo hashing and with a ring.
  • Explain the clockwise lookup, and why virtual nodes are needed for even load.
  • Place replicas on a ring without putting two copies on one machine.
  • Choose between a ring, rendezvous hashing, jump hash, Maglev and fixed hash slots, and say why.
  • Explain why spreading keys evenly does not stop one hot key from overloading a server.

Key concepts

  • Modulo hashing
  • Hash ring
  • Virtual nodes
  • Joins and leaves
  • Replication on the ring
  • Rendezvous hashing
  • Jump consistent hash
  • Maglev hashing
  • Bounded loads

Interview questions

  • Why not just use hash(key) mod N? How many keys move when you add a server?
  • Walk me through a lookup on a consistent hash ring. What data structure do you use?
  • What are virtual nodes, and how many would you use?
  • A node on the ring fails. What happens to its keys and its traffic?
  • How do you replicate data on a consistent hash ring?
  • Compare consistent hashing with rendezvous hashing and jump consistent hash.
  • One key gets 100 times more traffic than any other. Does consistent hashing help?
  • How do load balancers use consistent hashing?
  • Do Redis Cluster and DynamoDB use consistent hashing?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio