Do I understand correctly, that they spent memory storing largish N hash values per server, so that request hash determines which server to send request to using closest higher value of all server hashes?
That in effect boils down to consistently selecting server S with probability P, where P is function of weight and total number of servers?
Surely there must be better way to select server with a given probability without storing a massive lookup table of hashes? Randevouz hashing of some sorts
Plus it's limited to 65k entries. Perhaps a btree where parent nodes sum the weights of child nodes would work well. Using the input hash scaled by total weight, a binary search lookup would compute the partial sums for comparison on the fly. Adding/removing a node would only update the ~8 parents when the btree order is 4. Eytzinger layout and struct-of-arrays could be used to improve cache locality during lookup. This does mean an add/remove could drastically change the overall mapping, perhaps that's why consistent hashing is used instead.
nopurpose · · focus · HN ↗
That in effect boils down to consistently selecting server S with probability P, where P is function of weight and total number of servers?
Surely there must be better way to select server with a given probability without storing a massive lookup table of hashes? Randevouz hashing of some sorts
QuaternionsBhop · · focus · HN ↗