HackerPapers

arXiv:1503.04988cs.DS

Perfect Consistent Hashing

Matthew Sackman

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Consistent Hashing functions are widely used for load balancing across a variety of applications. However, the original presentation and typical implementations of Consistent Hashing rely on randomised allocation of hash codes to keys which results in a flawed and approximately-uniform allocation of keys to hash codes. We analyse the desired properties and present an algorithm that perfectly achieves them without resorting to any random distributions. The algorithm is simple and adds to our understanding of what is necessary to create a consistent hash function.

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

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2015 to Dec 2015.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. GoshawkDB: A distributed, transactional, fault-tolerant object store 1 comment

    • I don't think that's the problem though. The problem that I'm thinking of is that when a cluster grows in size, due to the use of consistent hashing, there'll be a set of objects that need to move between nodes. Calculating and achieving that movement is what concerns me. The…

      msackmanView on HNParent context

Submitted to Hacker News

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