HackerPapers

arXiv:1406.2294cs.DS

A Fast, Minimal Memory, Consistent Hash Algorithm

John Lamping, Eric Veach

Abstract

We present jump consistent hash, a fast, minimal memory, consistent hash algorithm that can be expressed in about 5 lines of code. In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes. Its main limitation is that the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 5 identifiable commenters in 5 comments across 5 threads, from Jun 2017 to Sep 2026. Found in 4 HN submissions from Aug 2014 to Mar 2019. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Saving another 100TB of RAM 1 comment

    • Anyone have an idea how it behaves differently from google's jump hash algorithm? The cool thing about google's one is it's so short I can include it in a HN comment: int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { int64_t b = 1, j = 0; while (j < num_buckets) {…

      cyberpunkView on HNParent context

  2. Overflow in consistent hashing (2018) 1 comment
  3. S2: Computational geometry and spatial indexing on the sphere 1 comment

    • Worth noting that this library is by the extraordinary genius Eric Veach, whose PhD thesis marked the beginning of modern rendering, besides also developing the core of Google's AdSense, and co-inventing jump consistent hash: https://arxiv.org/abs/1406.2294

      pixelpoetView on HNParent context

  4. Consistent Hashing for Dummies 1 comment

    • I hadn’t heard of the “Jump Consistent Hashing” algorithm that this article uses. The original paper is much more informative than the article: https://arxiv.org/abs/1406.2294

      orasisView on HNParent context

  5. When Simple Wins: Power of 2 Load Balancing 1 comment

    • You're kind of right. You can also use something like jump consistent hash [0] which only requires you to have a consistent ordering of the hosts where you're sending the information. We (Facebook) use something similar for our caches. It requires a linear array of hosts but…

      alexgartrellView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.