How do I locate a key reliably?


Since this is a database, I am assuming we need to always be able to retrieve a key’s value once it is set in this DB. With consistent hashing, our request can be served from a node which doesn’t have that key.

e.g. Say application writes key “Image-1792-Location” with value “”.
This is written in S1.
Now a new node (S3) is added.
Request for key “Image-1792-Location” goes to S3.

Obviously S3 won’t find the key. Should S3 now query S1 to find the data? Also, do we remove the key from S1 and add it to S3?


I would say that it works in a similar manner as hashmap with open addressing when there is a collision.


Hi, As the key “Image-1792-Location” will be present on multiple shards depending on the replication factor(3). Besides that the hash value of the three diff hash functions for the key will be pointing to three different locations on the ring. So,assuming replication factor is 3 and key “Image-1792-Location” is added to following shards S1, S2, S4. Suppose, if new machine S3 is added adjacent to S1 and the hash function values are now pointing to S1 S2 S3 shards, then It can get the key from other shards and update it in S3 and remove that key from S4 as it is adjacent to S1.

Instead of using three different hash functions, you can use one hash function value. Based on where this hash value falls on the ring you can consecutively add to three shards to keep multiple copies.