This post is an introduction to consistent hashing, an algorithm for designing a hash table such that only a small portion of keys has to be recomputed when the table's size changes. Motivating use case Suppose we're designing a caching web proxy, but the expected storage demands are higher than what a single machine can handle. So we distribute the cache across multiple machines. How do we do that? Given a URL, how do we make sure that we can easily find out which server we should approach for ...