What is Consistent Hashing?
Consistent hashing is a way of organizing keys within a hash table so that when the keys or nodes in the table change, the keys are reassigned to different nodes with minimal effort. This is beneficial in distributed systems where keys or nodes may frequently change, as it helps to evenly distribute the keys and minimizes the need to recalculate hashes when changes are made.
Try it out:
How it works
Consistent hashing utilizes a hash function to assign keys to integers, and these integers are subsequently mapped to nodes in the hash table through the use of a circular data structure. When a new node is added to the table, only a small portion of keys need to be reassigned to the new node, rather than every key in the table. Conversely, when a node is removed from the table, only the keys originally mapped to that node need to be remapped to a different node.
Visually
Example case
Try entering the following values and nodes to see how consistent hashing works:
Step 1: On Enter value input box - enter each value separately and click "Hash value" button:
"a", "b", "c", "j", "k", "l", "v", "w", "x", "y", "z"
Step 2: On Enter Node Position input box - enter the number "6" and click "Add Node" button:
As you can see, only the values at node position "6" (or index "5" in the diagram) of the hash table are reassigned to the new node. the other values remain in their original positions.
i.e.
"v", "w", "x", "y", "z"
are rehashed. After rehashing, some values might
remain in the same
node while others will be moved to the new node.
The other nodes will not be affected by this rehashing process. Hence, Consistent Hashing.
Hash Table
| Value | Hash |
|---|
The table above shows the key value mappings of the hash table and how they are affected by the addition of a new node. Only the values at the affected range will be rehashed but not the rest of the values in the other nodes.