Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web

✨ Summary

Summary

The paper addresses Web “hot spots,” in which many clients simultaneously request data from one server, potentially overwhelming both the server and nearby network infrastructure. It proposes two related mechanisms: random cache trees for request coalescing and load distribution, and consistent hashing for maintaining useful object-to-cache assignments as caches join, leave, or appear differently to different clients.

Random cache trees associate each page with a separate balanced tree whose non-root nodes are mapped randomly to caches. Requests travel from randomly selected leaves toward the page’s home server. Caches combine simultaneous requests, forward at most a bounded number of requests from each tree node, and retain a page after it has been requested a configurable number of times. Using a different random tree for each page prevents a single cache from becoming the root or an upper-level node for too many pages. The analysis gives high-probability bounds on cache load and storage, while request latency is proportional to the tree height, approximately logarithmic in the number of caches for a fixed branching factor. The paper also argues that pipelining makes the added delay less significant for large objects.

Consistent hashing is formulated as a mapping that assigns objects to a changing set of buckets. Its central properties are balance, monotonicity, spread, and load. Monotonicity ensures that adding buckets moves an object only when necessary and does not move it between existing buckets. Spread limits the number of distinct caches to which an object may be assigned across inconsistent client views, while load limits the number of objects that may be assigned to any one cache. The construction uses multiple random points for each bucket in a shared interval, producing a ring-like assignment with logarithmic spread and load under the paper’s assumptions. The authors also show an equivalent formulation using a random permutation of buckets for each object.

The two techniques are combined so that clients need to know only a constant fraction of the active caches. The paper further adapts the scheme to hierarchical latency models represented by ultrametrics, discusses cache and server failures, and extends the static batch analysis to requests arriving over time. Important limitations include the assumptions of largely immutable page content, adversaries that cannot observe protocol randomness or adapt to delays, and simplified timing and failure models. Server failures are not solved by the basic protocol; the paper suggests information-dispersal techniques for that case.

Influence

The paper became a foundational reference for later distributed storage and peer-to-peer systems. Amazon’s Dynamo paper explicitly cites it as reference [10] and uses consistent hashing for data partitioning, including multiple ring positions per physical node—later commonly called virtual nodes—to improve load distribution and incremental scalability. (cdn.amazon.science) Chord also explicitly cites the paper and uses consistent hashing to assign keys to peer-to-peer nodes while limiting key movement when nodes join or leave. (people.csail.mit.edu) Apache Cassandra’s architecture documentation describes a Dynamo-style consistent-hash ring and virtual nodes for partitioning and scaling storage clusters. (cassandra.apache.org) Subsequent research continues to treat consistent hashing as a standard dynamic allocation method while addressing its load-imbalance limitations; for example, Google’s work on bounded-load consistent hashing provides stronger maximum-load guarantees and reports deployment in Google Cloud Pub/Sub. (research.google)