Comment by vlovich123
8 hours ago
I would get rid of consistent hashing and ketama for a better system which works save an additional 600TiB.
You use the first N bits of your key hash to pick the server partition so it’s a reasonable number (eg 128 servers per partition). Then use high quality precomputed hashes (first 64 bits of sha256) for the server name as N in H(K + N). Use wymum from wyhash as the H so that you do o(n) integer multiplications while retaining a result that’s still a good hash statistically.
Now you’re using a tournament hash, the small N means O(N) vs O(N log N) doesn’t matter, and also this O(N) is also going to be much less CPU than computing 160 hashes per key as they do now, so much less latency added per request.
I think they do only a hash per request. The 160*weight hashes were done per server (per feature set), to partition the hash space. Per request you do a single hash and then a lower_bound on a sorted map to find the serving server (again, on the ring appropriate for the features required by the request, so likely a hash map lookup first)