Consistent hashing


Suppose a hash table needs to be resized.

In that case the hash function changes, since it maps to a larger set.

Classically, hash functions used use modular operations.

This means nearly all keys will be remapped.

How consistent hashing helps

We hash server ids, forming circle.

Whenever we insert new server, we only move blobs which are smaller than server ID.

OR if new server ID is largest, thanks to circle, we can just move largest blob from smallest of server IDs into it.


VNode is used as a virtual mapping. It reduces variance. It points to actual real label, since real labels might have skew.