Details
-
Improvement
-
Resolution: Won't Fix
-
Minor
-
techdebt-backlog
-
Security Level: Public
-
None
Description
The current code implements Ketama which builds a sorted list of 100 or 160 hash points per server, and then performs a logarithmic search for the server with the closest point.
Consider the following alternative: Given N servers, create an array of N*(N-1) entries, and fill it with servers in such a way that each server appears (N-1) times, and adjacent server pairs occur exactly once. For example, for N=3 with servers A,B,C, one possible arrangement is servers := [ A, B, C, A, C, B ]
When mapping a key, calculate its hash as usual, then use s = servers[ hash(key) % N*(N-1) ] to determine the mapping.
When a server fails, remap keys to the next server in the array: e.g. when B fails, the array is modified to [ A, C, C, A, C, A ]. Assuming a uniform key hash function, this guarantees an even redistribution of keys
The mapping function is simpler and more performant than the Ketama approach, while also exhibiting better cache locality.
Using 8 bits per server, this approach would only require 65K to support up to 256 servers.
Weighted consistent hashing can be implemented in a similar fashion, varying the frequency of servers in the array according to their weight.