Consistent hashing

You have a pool of servers (cache nodes, shards) and a stream of keys. Each key must always go to the same server, and the pool will change as servers fail and are added. The obvious rule breaks when the pool changes. Consistent hashing is the rule that does not.

Crux: place both servers and keys on the same circle, and give each key to the first server clockwise. When a server joins or leaves, only the keys next to it move, about 1/N of them.

The problem with mod N

The obvious rule is server = hash(key) mod N, where N is the number of servers. It spreads keys evenly and needs no lookup table. It breaks when N changes.

A key stays on its server only if k mod N equals k mod (N+1). Take twelve keys, 0 to 11, going from 3 servers to 4:

key   0  1  2  3  4  5  6  7  8  9 10 11
mod 3 0  1  2  0  1  2  0  1  2  0  1  2
mod 4 0  1  2  3  0  1  2  3  0  1  2  3
stay  ✓  ✓  ✓  ·  ·  ·  ·  ·  ·  ·  ·  ·     3 stay, 9 move

Over a long run of keys, a fraction 1/(N+1) stay and N/(N+1) move. From 3 to 4 that is 3/4 (75%). From 9 to 10 it is 9/10 (90%).

For a cache, a moved key is a miss: adding one server makes most of the cache useless at once, and the database takes the whole load (the stampede from the caching lesson). For shards, a moved key is data that must be copied.

The hash ring

Treat the output of a hash function as a position on a circle. A common choice is the range 0 to 2^32 − 1 (about 4.3 billion), joined end to start, but the size is not important.

• 1. Place the servers. Hash each server's name or address to get its position on the ring.
• 2. Place the key. Hash the key to get a position.
• 3. Walk clockwise from the key to the first server. That server owns the key.

To look a key up, keep the servers' positions in a sorted list and use a binary search for the first position at or after the key's hash, wrapping to the start if there is none. That costs O(log N) and the list is tiny: a thousand servers is a thousand numbers.

Adding and removing a server

• Add a server. It lands somewhere on the ring and takes over the keys between its anticlockwise neighbour and itself. Everything else stays put.
• Remove or lose a server. Its keys go to the next server clockwise. Nothing else moves.

With K keys and N servers, the average number of keys that move is about K / N. For 3 servers going to 4, that is about one quarter of the keys, against three quarters with mod N.

Virtual nodes

One position per server has two problems. With few servers, the arcs between them are very different in size, so one server can own far more than its share. And when a server dies, all of its keys land on its one neighbour, which may fall over in turn.

The fix is virtual nodes (vnodes). Hash each server many times (for example, server-A#1, server-A#2, ... up to 100 or 200 positions, a typical range but a tunable setting). Every position on the ring belongs to a real server.

• Evenness. With many points per server, the share each owns is close to 1/N. The spread shrinks roughly with the square root of the number of vnodes, so more vnodes means better balance.
• Failure. A dead server's keys scatter over all the others, not onto one neighbour.
• Different sizes. A server with twice the capacity gets twice the vnodes.
• The cost. A bigger ring to store and search, and more bookkeeping when data moves (a server has many small slices to hand over).

Replication on the ring

Systems in the Dynamo family, such as Cassandra, do more than assign one owner. A key is stored on its owner and on the next R − 1 distinct servers clockwise (R is the replication factor, often 3). If the owner fails, the next one already has the data. With vnodes, "distinct servers" matters: skip any vnodes that belong to a server already chosen.

Where you meet it

• Distributed caches with client-side routing, so adding a node loses only a slice of the cache.
• Dynamo-style and wide-column databases (the Dynamo paper, and Cassandra, which follows it) to place data and replicas.
• Load balancing with stickiness: send the same user or object to the same server so its local cache stays warm, with little reshuffling when servers change.
• Content delivery: choose which cache server holds which object.

Some systems choose another approach to the same problem. Redis Cluster divides keys into 16,384 fixed hash slots and maps slots to nodes, so adding a node moves whole slots. Rendezvous (highest random weight) hashing gives each key a score per server and picks the highest, which also moves about 1/N of keys with no ring. The shared idea: when the pool changes, move as little as possible.

Hot spots are a different problem

Two kinds of imbalance get confused.

• Uneven key spread. Servers own unequal slices of the ring. Virtual nodes fix this.
• Uneven traffic. One key (a celebrity, a flash sale) draws a huge share of requests. Hashing cannot help: that key has exactly one owner.

For the second kind, choose by what is hot:

• Read replicas or extra cache copies of the hot key. Adds read capacity; writes still go to the owner.
• Key salting. Store the key as key#0 to key#9, so ten servers share the writes. Reads must fetch all ten and combine them.
• Adaptive rebalancing. The system notices a busy server and moves slices off it. It works and adds operational machinery and extra data movement at the worst time.

How much data actually moves

Not as much as the ring picture suggests. A failure is usually handled by replication: the next replicas already hold the data and take over without copying anything. Data really moves when membership changes on purpose (adding capacity, replacing a node), and then it streams in the background while the old owner keeps serving until the new one has caught up.

When not to bring it up

• A fixed set of servers that never changes does not need it.
• A managed database already does placement for you: say which database you chose and that it handles partitioning, and spend the time elsewhere.
• Do not draw a ring for every problem. Use it when a pool changes and moves are expensive.
• Go deep only when the question is building the infrastructure (a distributed cache, a database, a broker). Otherwise name it in a sentence and move on.

If you do go deep, five points cover it: why mod N fails, the ring and the clockwise rule, virtual nodes for balance, what happens on add and on failure, and how hot keys are handled separately.

Common mistakes

• Using hash mod N for something that will grow.
• One position per server, then surprise when load is lopsided.
• Forgetting that a dead server's load shifts to its neighbour, which can cascade.
• Thinking the ring balances load by itself. It balances keys. A hot key still lands on one server.
• Treating a hot key and an uneven ring as the same problem.
• Claiming no data moves. Some does, and it must be copied while serving traffic.

Check yourself

• Out of 12 keys, how many change server when mod 3 becomes mod 4, and what fraction in general from N to N+1?
• Describe how a key is assigned on a ring, in three steps.
• Why is O(log N) lookup enough, and what is the data structure?
• What problem do virtual nodes solve, and what do they cost?
• When a server dies, where do its keys go with and without vnodes?
• Name one other way to reduce data movement when a pool changes.
• A single celebrity key overloads one server on a ring with 200 vnodes each. Why did vnodes not help, and what would?