Consistent Hashing
The obvious way to spread keys over servers is to hash the key and take the remainder. It works perfectly until the number of servers changes, and then it comes apart: change the divisor and most keys get a different answer at once, which for a cache means most of what was cached has to be fetched again in the same minute the pool grew. Karger and his co-authors put the keys and the servers on the same ring instead, and gave a key to the first server clockwise of it. Adding a server then takes an arc, and only the keys inside that arc move. This page counts the ones that move, on a thousand actual keys, two different ways.
One more server, and almost everything stays put
1 Keys and servers placed on one ring by the same hash
A thousand keys and a handful of servers, hashed into the same space of positions. A server puts several points on the ring rather than one, for a reason the last panel measures.
1000 keys and 5 servers on one ring of 4294967296 positions, placed by the same hash. Each server puts 200 points on it, so the ring holds 1000. A key belongs to the first point at or after it, and the ring wraps.
| position | server | point |
|---|---|---|
| 16951555 | echo | 45 |
| 22095772 | alpha | 91 |
| 34206755 | echo | 21 |
| 35169222 | alpha | 41 |
| 41116742 | echo | 157 |
| 42162980 | alpha | 192 |
| 43060035 | alpha | 98 |
| 44832477 | echo | 52 |
| 46706340 | charlie | 106 |
| 51139190 | echo | 69 |
| 52883764 | echo | 84 |
| 53268525 | alpha | 114 |
2 A server added, and the keys that actually moved counted rather than estimated
MeasuredOne more server joins
205 keys had to move, which is of them
205 of 1000 keys moved when echo joined, which is 20.5%. An even share would be 200. Counted twice and both routes said 205. Every one of them went to echo and none moved between the servers that were already there.
Counted twice on purpose. Once by asking every key who owned it before and who owns it now, and once by walking the arcs the new server took and counting the keys that fall inside them. Those are different pieces of code with no line in common, and a page whose central number came from a single function would have nothing to say when that function was wrong.
3 The same keys under modulo hashing, where almost all of them move
The same keys, under key mod n
| scheme | keys moved | share |
|---|---|---|
| the ring | 205 | 20.5% |
| key mod n | 773 | 77.3% |
| an even share | 200 | 20.0% |
Going from 4 servers to 5 changes the divisor, so under key mod n almost every key gets a different answer. That is not a cache miss, it is 773 objects that have to be fetched again.
4 The load each server ends up with, and what virtual nodes do to the worst one
What each server ends up holding
| server | keys | share |
|---|---|---|
| alpha | 194 | 19.4% |
| bravo | 228 | 22.8% |
| charlie | 194 | 19.4% |
| delta | 179 | 17.9% |
| echo | 205 | 20.5% |
5 servers, 200 points each: busiest 228, quietest 179, a spread of 1.27. Spread is the busiest divided by the quietest. Fewer points means a lumpier ring, and lumps are servers holding several times their share.
Before the new server joins, with 4 servers: at one point each the spread is 99.1, at 200 it is 1.21. The fairness is bought with ring entries: 1000 of them once the new server is on, each one state every client has to hold and sort.
Set each server to one point and watch the table come apart. A handful of random positions on a ring do not carve it into equal arcs, and the server that happens to sit just after a long gap holds several times its share. The fix is to give every server many points, so the arcs it owns are many small ones and the lumps average out. Switching the hash to plain FNV-1a shows the other assumption: the guarantee is about a hash that scatters, and this one places keys that differ in their last character a fixed distance apart, so the ring goes lumpy again even with two hundred points each.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| adding a fifth server to four moves a fifth of the keys, near enough | yes | 205 of 1000 keys moved. A fifth would be 200, so this is 205: the share is what the hash function happened to do, not a law |
| and the count is the same whether you diff the owners or walk the new arcs | yes | checked adding a node to pools of one, two, three and four |
| every key that moved, moved TO the new server and nowhere else | yes | no key ever moves from one old server to another old server, which is the property the 1997 paper calls monotonicity |
| modulo hashing moves almost every key instead | yes | 773 of 1000 move under key mod n, against 205 on the ring: 77 per cent against 21 |
| removing a server moves its keys and touches nobody else's | yes | each of four servers removed from a pool of five in turn, and each time exactly the keys it was holding moved |
| one point per server on the ring is badly unfair, and more points fix it | yes | four servers, one point each: the busiest holds 694 keys and the quietest 7, a spread of 99.1. The same four servers at 200 points each: 270 against 223, a spread of 1.21. Spread here means the busiest divided by the quietest. |
| every key tested has exactly one owner, including the ones past the last point | yes | 1,000 keys at each of 5 virtual-node settings, and the ring wraps rather than ending. That is a measurement on a thousand keys, not a proof about all of them |
| and the fairness is paid for in ring entries a lookup has to search | yes | 5 points on the ring at one per server, 1000 at 200. Every one of them is state each client has to hold and sort |
| and none of this survives a hash with a pattern in it | yes | with the finalizer the busiest of four servers holds 270 keys and the quietest 223. With plain FNV-1a, whose last step leaves consecutive keys a fixed distance apart, it is 433 against 136. Same ring, same number of points, same keys |
What is real here, and what is not
The number is counted, not K over n
The share of keys that move is printed beside what an even share would be, and they are not the same. On a thousand keys going from four servers to five, an even share is 200 and what actually moves is whatever the hash function did to those particular keys. Rounding the measurement to the formula would be quoting the theory and calling it a measurement.
Counted twice, by code with nothing in common
Once by diffing who owned each key before and after, and once by walking the arcs the new server claimed and counting the keys inside them, wrap included. Both numbers appear in the checks below and have to agree. A single function producing the page's headline number is a page with no way to notice that function being wrong.
The hash is FNV-1a with a finalizer, and both are on the page
Plain FNV-1a xors the last byte in and multiplies once, so for two keys sharing a prefix the difference between their hashes is the difference between the two xored values, multiplied by the prime. For a run of keys like these that lands them on a short arithmetic ladder rather than scattered. Its keys come out as an arithmetic progression rather than as scattered points, and the ring goes visibly lumpy. The finalizer, built from the same constant this file already uses, mixes the high bits down over the low ones twice. Both are selectable because the ring's guarantees assume a hash that scatters, and that assumption is worth being able to switch off.
Servers are equal, and real ones are not
Every server here gets the same number of points on the ring. Real pools are heterogeneous and the usual answer is to give a bigger machine proportionally more points, which is the same mechanism doing a second job. Nothing here weights them.
One replica per key, so nothing is fault tolerant
A key belongs to the first point clockwise and that is the end of it. Systems built on this commonly walk further round the ring to place copies on the next few distinct servers, which is where the mechanism stops being about cache placement and starts being about durability. That is a different page.
The paper is about more than the ring
Consistent hashing is one half of the 1997 paper and the random trees in its title are the other, which is a scheme for spreading the load of a hot page across a tree of caches. Only the hashing half is here, and it is the half that got built into everything afterwards.
Sound: no
The measurement is a count of keys and a ratio of loads. Neither is a duration and there is no rhythm here to carry at true scale.
Sources
- Karger, Lehman, Leighton, Panigrahy, Levine and Lewin, Consistent Hashing and Random Trees, STOC '97 — the paper, including the definition of monotonicity that the second check on this page tests.
- Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007 — where the ring is used in production, and where the reason for giving each server many points rather than one is written down.
- Logical Art, the studio this belongs to.