Maglev Hashing Algorithm: An implementation in Rust

An implementation of the Maglev consistent hashing algorithm as described in the Google paper

What is consistent hashing?

Hashing in general could be loosely defined as assigning a set of keys to a set of buckets. In general, hashing algorithms aim to ensure that all buckets are assigned an equal number of keys, and that the the keys are spread evenly amongst the buckets.

The guarantees of a traditional hashing algorithm are not enough when trying to use hashing to assign keys amongst a set of distributed servers as buckets. The issues being that resizing buckets can heavily rearrange the assignment of keys. In a distributed system, since the buckets are servers, which are not-unlikely to go down, using traditional hashing in a fault tolerant system would mean a lot of network calls to re-arrange buckets and bring the distributed systems to a stable state.

Consistent hashing algorithms are designed to ensure minimal distruption in the distribution of keys on resizing buckets. To quote wikipedia:

..when a hash table is resized, only n/m keys need to be remapped on average where nis the number of keys and m is the number of slots

How does Maglev hashing work?

For each bucket(server) we generate a preference list for keys. The preference list is essentially just a random permutation of array (0..M -1) for M keys.

This preference list is then used to assign a bucket to each key. The assigment loops through each preference list, picking up a key that hasn't been assigned yet, and assigns it to the owner of the current preference list.