Consistent hashing maps keys to servers while limiting which keys change primary owner as servers join or leave. Adding a server only reassigns keys to that server, and removing one only reassigns the keys it owned. A distributed cache for instrument-level volatility surfaces can add capacity while leaving unaffected surfaces on the servers that already hold them. The cache can then look up each original key in a local hash table. Karger et al., Consistent Hashing and Random Trees, §4.1.
A new server takes one arc
The ring implementation puts key hashes and server positions in the same fixed circular space. To route consistently, routers share a hash function and ring configuration. In the example below, each key goes to the first server clockwise at or after its hash. If the hash lies above the highest server position, wrap to the lowest position. DeCandia et al., Dynamo, §§4.2–4.3.
Take a fictional ring of integer positions 0–99, with one primary owner per key and distinct server positions. Start with nodes at 20, 60 and 90, then add a node at 40 while keeping the old positions fixed. The new node takes the hashes in , all of which previously reached 60. Hash 20 still lands on its own node, hash 41 still reaches 60, and hash 99 still wraps to 20.
| Sample hashes | Owner before | Owner after |
|---|---|---|
| 5, 20, 91, 99 | 20 | 20 |
| 21, 39, 40 | 60 | 40 |
| 41, 59, 60 | 60 | 60 |
| 61, 90 | 90 | 90 |
The blue arc excludes position 20 and includes 40. Only this arc switches owners when node 40 joins.
Three of the 12 sample keys change owner. Across the full ring, 20 of 100 positions change owner, so a uniformly distributed key hash has a 20% chance of moving in this example. Removing node 40 again gives that arc back to its clockwise successor, 60.
For lookup, a binary search over sorted positions finds the first position at or above the key hash in time. In Python, use
bisect_left and wrap to the first entry if it returns the list length. Python documentation for bisect_left.The SelfMadeQuant lesson on Python’s built-in data structures explains the cost of searching and updating sorted lists. The full lesson requires membership.
Balance depends on the workload
After the change, node 20 owns 30 positions and node 40 owns 20. Giving each server several ring positions, or tokens, lets it act as several virtual nodes. This spreads its share across multiple arcs and can make ownership more even. A heavily requested instrument still routes to one primary, even if every server owns the same number of positions. A cache can fetch or recompute entries on demand after they move. A persistent store needs to make the records available to their new owners, for example by transferring them during the change. DeCandia et al., Dynamo, §4.2 on virtual nodes and §4.9 on transferring keys.