Stack Overflow
Stack Overflow

Questions tagged [consistent-hashing]

Consistent Hashing, a process discovered by Karger et al. at MIT, is a special kind of hashing such that when a hash table is resized only K/n keys need to be remapped unlike normal hashing techniques

Definition

Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped.

Consistent hashing is used in many places. The most famous being OpenStack's Object Storage component called as Cinder

Source

Wikipedia page on Consistent Hashing

126 questions
25
votes
4 answers

How should I use Guava's Hashing#consistentHash?

I'm looking into using a consistent hash algorithm in some java code I'm writing. The guava Hashing library has a consistentHash(HashCode, int) method, but the documentation is rather lacking. My initial hope was that I could just use…
GamingBuck
  • 508
  • 1
  • 5
  • 7
19
votes
2 answers

consistent hashing vs. rendezvous (HRW) hashing - what are the tradeoffs?

There is a lot available on the Net about consistent hashing, and implementations in several languages available. The Wikipedia entry for the topic references another algorithm with the same goals: Rendezvous Hashing This algorithm seems simpler,…
Peter Friend
  • 750
  • 1
  • 7
  • 17
15
votes
2 answers

Memcache Consistent Hashing, Cluster, PHP code, Ketama and all about it

I have been trying for the whole day to understand and code for Memcache with PHP but I am getting confused at few points. I have gone through many articles and almost every SO questions related this but could not find exact answers. 1) What would…
user2925077
13
votes
7 answers

Same consistent-hashing algorithm implementation for Java and Python program

We have an app that the Python module will write data to redis shards and the Java module will read data from redis shards, so I need to implement the exact same consistent hashing algorithm for Java and Python to make sure the data can be…
superche
  • 753
  • 3
  • 9
  • 21
11
votes
2 answers

does redis cluster use consistent hashing

I'm using redis cluster 3.0.1. I think redis cluster use consistent hashing. The hash slots are similar to virtual nodes in consistent hashing. Cassandra's data distribution is almost the same as redis cluster, and this article said it's consistent…
bylijinnan
  • 756
  • 3
  • 11
  • 27
11
votes
2 answers

Memcached consistent hashing not working with 3 of 4 servers down

Story I have 3 memcached servers running where I shutdown the one or the other to investigate how PHP-memcached behaves upon a server not beeing reachable. I have defined 4 servers in PHP, 1 to simulate a server that is mostly offline (spare…
Daniel W.
  • 31,164
  • 13
  • 93
  • 151
11
votes
5 answers

How does consistent hashing work?

I am trying to understand how consistent hashing works. This is the article which I am trying to follow but not able to follow, to start with my questions are: I understand, servers are mapped into ranges of hashcodes and the data distribution is…
zengr
  • 38,346
  • 37
  • 130
  • 192
11
votes
2 answers

MessageDigest hashes differently on different machines

I'm having a problem with MessageDigest returning different hash values on different computers. One computer is running 32-bit Java on Windows Vista and the other is running 64-bit Java on Mac OS. I'm not sure if it is because MessageDigest is…
Chris Dutrow
  • 48,402
  • 65
  • 188
  • 258
10
votes
2 answers

Hashing VS Indexing

Both hashing and indexing are use to partition data on some pre- defined formula. But I am unable to understand the key difference between the two. As in hashing we are dividing the data on the basis of some key value pair, similarly in Indexing…
coolDude
  • 407
  • 1
  • 7
  • 17
8
votes
2 answers

Producer work consistently hashing to consumers via a message queue?

I have a producer that I want to distribute work consistently across consumers by consistent hashing. For example, with consumer nodes X and Y, tasks A, B, C should always go to consumer X, and D, E, F to consumer Y. But that may shift a little if Z…
Bluu
  • 5,226
  • 4
  • 29
  • 34
8
votes
1 answer

How to handle recovery memcached nodes when using spymemcached & HashAlgorithm.KETAMA_HASH

I am using spymemcached & HashAlgorithm.KETAMA_HASH to connect to a pool of memcached of 5 nodes. My understanding is when we use a consistent hashing algorithm like, when a node is down, we don't need to worry as the key will be re-distributed…
Howard
  • 19,215
  • 35
  • 112
  • 184
8
votes
1 answer

Do any hashtables (in-memory, non-distributed) use consistent hashing?

I'm not talking about distributed key/value systems, such as typically used with memcached, which use consistent hashing to make adding/removing nodes a relatively cheap procedure. I'm talking about your standard in-memory hashtable like python's…
John Hart
  • 5,718
  • 2
  • 20
  • 12
7
votes
4 answers

Programming language to choose for implementing distributed message passing algorithms

Basically, I would want to implement the following algorithms and analyze how the system built using these algorithms behave under different conditions. Gossip protocol Multiple paxos Consistent hashing My interest here is in these algorithms. I…
user855
  • 19,048
  • 38
  • 98
  • 162
7
votes
1 answer

How to add partition to Kafka topic and keep same-key message in same partition？

It is common to require ordering in same partition of given Kafka topic. That is, messages with same key should go to same partition. Now, if I want to add new partition in a running topic, how to make it and kept the consistency? To my…
Morgan Cheng
  • 73,950
  • 66
  • 171
  • 230
7
votes
1 answer

Horizontally scaling out or sharding Python-RQ or Redis with Python

Trying to horizontally scale out the Redis instance working as the task server for Python-RQ. As far as I know, the best way to do this would be to add sharding logic (most likely using Consistent Hashing) into a custom ConnectionPool and / or…
Juan Carlos Coto
  • 11,900
  • 22
  • 62
  • 102
1
2 3
…
8 9