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.
- 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.
- 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.
- 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¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:d977498ef4fd · see in the full table