Consistent Hashing Proofs

This excerpt presents a derivation of the formulas used in consistent hashing to distribute workload among servers. The author aims to make the material accessible to readers with varying backgrounds. The piece is a companion to a blog post on the subject, and it includes a primer on consistent hashing.

The main focus is on deriving an approximation for the error in workload distribution in a system with N servers and K hashes per server, which is very close to 1/K when N is large. The author notes that the actual error is typically around 1% for N ≥ 50.

To arrive at the formula, the author begins with a simpler case of a single server with one hash in a consistent hashing setup with at least one more server. The distribution of workload for the server is represented geometrically as the length of a segment on a number line between 0 and 1, where the fraction of the work handled by the server is equal to the length of its segment.

The author then discusses how the region assigned to the server varies and stays independent of the total number of hashes. The circular nature of the hash domain is highlighted, as it simplifies the understanding of the hash space.

The author admits to having struggled with understanding the consistency hashing concepts and the limited resources available online, which motivated them to create this derivation. The goal is to provide a clear and approachable explanation of the subject matter, enabling readers to understand the implications for workload distribution in consistent hashing systems.