Consistent Hashing and Random Trees¶
Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 654-663.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Hashing
- And consistent hashing minimises remapping when the codomain itself changes as servers are added or removed, a trick that generalizes to any bucket-with-membership scheme.
This sourceIntroduces consistent hashing, which minimizes remapping when the codomain (set of nodes) changes.
Supported in partVerified against the publisher's abstract
The abstract states a consistent hash changes minimally as the range changes, supporting the remapping half; it does not support the bucket-with-membership generalization.
“Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes.”
- And consistent hashing minimises remapping when the codomain itself changes as servers are added or removed, a trick that generalizes to any bucket-with-membership scheme.
- Load Balancing
- Policies range from round-robin and weighted round-robin to least-connections, least-response-time, and consistent hashing; the same pattern appears in database sharding, distributed task queues, and content-delivery networks that steer users to the least-congested edge node.
This sourceACM. Introduces consistent hashing as a stateless-deterministic routing rule that spreads load across a changing pool of nodes with minimal remapping; the basis for CDN edge steering and distributed-cache request routing.
Supported in partVerified against the publisher's abstract
The abstract establishes consistent hashing as a load-spreading caching scheme; it says nothing of round-robin, least-connections, sharding, task queues, or CDN edge steering.
“Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes.”
- Policies range from round-robin and weighted round-robin to least-connections, least-response-time, and consistent hashing; the same pattern appears in database sharding, distributed task queues, and content-delivery networks that steer users to the least-congested edge node.
- Sharding
- The deterministic partition function hashes the key onto a ring and assigns it to the next node clockwise — a stable, routable mapping: any client computes
hash(userID)locally and contacts exactly the owning shard with no fan-out, which is precisely the routability-without-consulting-all-shards that buys the scaling and distinguishes sharding from load balancing.This sourceIntroduces consistent hashing and virtual nodes, bounding key migration when nodes are added and smoothing load skew — the canonical partition-function-and-rebalancing result.
Supported in partVerified against the publisher's abstract
The abstract states consistent hashing and that users need no current or consistent view of the network, but never mentions a ring, clockwise assignment, client-local hash lookup, or any contrast with load balancing.
“Through the development of good consistent hash functions, we are able to develop caching protocols which do not require users to have a current or even consistent view of the network.”
- The deterministic partition function hashes the key onto a ring and assigns it to the next node clockwise — a stable, routable mapping: any client computes
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 3 of 3 citations: 3 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:d977498ef4fd · see in the full table