Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web

By David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, Daniel Lewin. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “Relatedly, many data structures, systems, and networking applications use different variants of hashing—consistent [49], asymmetric [73], weighted [72], multi-choice [9, 61], cuckoo [8, 63], and others [18, 34]—to achieve the same goal.”
Don't settle for eventual: scalable causal consistency for wide-area storage with COPS (2011, methodology): “For scalability, our implementation partitions the keyspace across a cluster’s nodes using consistent hashing [27], through other techniques (e.”
Privacy and accountability for location-based aggregate statistics (2011, background): “Assuming system membership is public, anyone can compute which K clients are assigned to an aggregate id using consistent hashing [23]; this approach is a standard distributed systems technique with the property that, roughly, load is balanced among clients and clients are assigned to aggregates in ”
PeerReview: practical accountability for distributed systems (2007, methodology): “In peer-to-peer systems, we use consistent hashing [29] to map witnesses to nodes; in this case, each node acts as a witness for the k nodes whose node identifiers are closest to its own.”
Big data related technologies, challenges and future prospects (2015, background): “There have been considerable discussions from both industry and academia on the definition of big data [10, 11].”
Site Reliability Engineering: How Google Runs Production Systems (2016, background): “Proposed in 1997, consistent hashing [Kar97] describes a way to provide a mapping algorithm that remains relatively stable even when new backends are added to or removed from the list.”
TAO: Facebook's Distributed Data Store for the Social Graph (2013, background): “Shards are mapped onto cache servers within a tier using consistent hashing [15].”
Web-scale multi-task feature selection for behavioral targeting (2012, background): “The latter, when used in storage rather than caching mode, allows us to spread the data evenly and to retain it in memory since it uses consistent hashing [8].”
Wide-area cooperative storage with CFS (2001, methodology): “tion doesn’t produce perfect load balance; the maximum stor age burden is likely to be about log(N) times the average due to irregular spacing between server IDs [12].”
UbiCrawler: a scalable fully distributed Web crawler (2004, methodology): “Recently, a new hashing technique called consistent hashing [14, 15] has been proposed for the implementation of a system of distributed web caches (a different approach to the same problem can be found in [10]).”
Beacon vector routing: scalable point-to-point routing in wireless sensornets (2005, methodology): “We propose to use the beacons as a set of storage nodes, by using consistent hashing [14] to provide a mappingH : nodeid 7→ beaconid, from node ids to the set of beacons.”
Parameter Server for Distributed Machine Learning (2013, methodology): “Different to performing key discovery and routing as [18], we use a DHT for assignment and we store the mapping from key segments to nodes in Paxos [19], as implemented in Zookeeper.”
Democratizing Content Publication with Coral (2004, background): “Then, upon reaching a cluster of collocated machines, hashing schemes [11, 32] map requests to specific machines to increase capacity.”
The Snowflake Elastic Data Warehouse (2016, methodology): “To improve the hit rate and avoid redundant caching of individual table ﬁles across worker nodes of a VW, the query optimizer assigns input ﬁle sets to worker nodes using consistent hashing over table ﬁle names [31].”