Partitioning: consistent hashing and hash slots

Spreading the cache over many machines

The primer lists three options once one machine is not enough:

1. Each machine has its own cache. Simple, "although it will likely result in a low cache hit rate".
2. Each machine has a copy of the cache. Simple, but "an inefficient use of memory".
3. Shard the cache across machines. More complex, but "likely the best option". Pick the machine with machine = hash(query), and preferably consistent hashing.

Why not hash mod N?

$\text{hash}(k) \bmod N$ spreads keys evenly, but changing $N$ moves almost everything. When one server of 10 fails, a key stays put only if $h \bmod 10 = h \bmod 9$, which is true for 1 key in 10. So 90% of keys move to a different server and miss at once. Adding 2 servers to 10 moves about 83% of keys.

Consistent hashing

libketama, the Memcached client library from Last.fm, describes the method:

• "Hash each server string to several (100-200) unsigned ints". These points sit on a circle "that goes from 0 to 2^32".
• "To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum." Past the last point, wrap to the first.
• "If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers." A new server takes keys only from the arcs where its points land: about $1/(N+1)$ of all keys, and every moved key moves to the new server.
• Servers can be weighted "by adding more or less points to the continuum", for example in proportion to memory.

Why many points per server. With one point each, arc lengths vary widely. In the visual's measurements, the busiest of 4 servers holds about 1.9 times its fair share, and with 10 servers about 3.7 times. With 100 to 200 points per server, the busiest holds within about 4–13% of its fair share.

Redis Cluster: 16,384 hash slots

Redis Cluster does not use a ring. Its specification:

• Each primary owns a set of slots. Resharding moves whole slots between nodes.
• Hash tags: if a key contains {…} with something inside, only that part is hashed. {user:1001}.profile and {user:1001}.orders land in the same slot, so multi-key commands work across them.
• The spec reports that "CRC16 behaved remarkably well in distributing different kinds of keys evenly across the 16384 slots".

The routing visual (lesson 4) computes real slots with Redis's CRC16.