Consistent hashing is a distributed partitioning algorithm used to distribute data or requests across a cluster of servers
Design Rationale
The basic steps to implement consistent hashing are:
-
Map servers and keys on to the ring using a distributed hash function.
-
To find out which server a key is mapped to, go clockwise from the key position until the first server on the ring is found.
Brute Force Approach
A naive way to implement consistent hashing is by allocating an array of size equal to
the hash space (e.g., 2^32 if a 32-bit hash function) and putting keys and servers directly at
their hashed locations.
To find the server responsible for a key, we first hash the key and then start scanning right
from its hashed position until we encounter the first server. If we reach the end of the
array without finding a server, we wrap around to index 0 and continue searching.
The approach is very easy to implement but it requires huge memory to hold such a large
array. For 2^32 hash space, it requires 4 Billion * 8 bytes ~ 32 GB of memory. Additionally,
most of these slots would remain empty because the number of servers is usually in the
hundreds or thousands.
To locate the owner of a key, we may need to scan a large portion of the hash space before
finding the next server. In the worst case, the lookup complexity becomes O(hash_space).
Optimized Approach
A better way of implementing this is by using two arrays, one to hold the servers,
called nodes and another one to hold the positions of the servers in the hash space,
called keys.
There is a one-to-one correspondence between the two arrays. The server
nodes[i] is present at position keys[i] in the hash space. Both the arrays are kept
sorted as per the keys array.
keys = [100, 500, 1000]
nodes = [ A, B, C ]
Because the keys array is sorted, we can efficiently locate the next server using binary
search. Instead of scanning the ring sequentially, we repeatedly halve the search space until
we find the smallest position greater than or equal to the key's hash. This reduces the
lookup complexity from O(hash_space) to O(log N), where N is the number of servers.
Low-Level Design
The key idea is:
keys[i] -> Hash position on the ring
nodes[i] -> Server at that position
Both arrays remain sorted according to keys.
Node
public class Node {
private final String id;
private final String host;
public Node(String id, String host) {
this.id = id;
this.host = host;
}
public String getId() {
return id;
}
public String getHost() {
return host;
}
@Override
public String toString() {
return id;
}
}
Hash function
public interface HashFunction {
long hash(String key);
}
public class DefaultHashFunction implements HashFunction {
@Override
public long hash(String key) {
// keep all hash values in the expected range: [0, 2^32) instead of [-2^31, 2^31)
return Integer.toUnsignedLong(key.hashCode());
}
}
Consistent Hash Ring
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ConsistentHashRing {
private final HashFunction hashFunction;
private final List<Long> keys;
private final List<Node> nodes;
public ConsistentHashRing(HashFunction hashFunction) {
this.hashFunction = hashFunction;
this.keys = new ArrayList<>();
this.nodes = new ArrayList<>();
}
public void addNode(Node node) {
long hash = hashFunction.hash(node.getId());
int idx = Collections.binarySearch(keys, hash);
// if hash is not found, insert at the position where it would be inserted to keep the array sorted
// java returns (-(insertionPoint) - 1) if the hash is not found
if (idx < 0) {
idx = -(idx + 1);
}
keys.add(idx, hash);
nodes.add(idx, node);
}
public void removeNode(Node node) {
long hash = hashFunction.hash(node.getId());
int idx = Collections.binarySearch(keys, hash);
if (idx >= 0) {
keys.remove(idx);
nodes.remove(idx);
}
}
/*
1. Hash the key.
2. Find its position on the ring.
3. Move clockwise.
4. Return the first server encountered.
*/
public Node getNode(String key) {
if (keys.isEmpty()) {
return null;
}
long hash = hashFunction.hash(key);
/*
* Find the position of the key in the sorted server hash list.
*
* If the exact hash exists, binarySearch returns its index.
*
* Example:
* keys = [100, 500, 1000]
* hash = 500
*
* Returns:
* idx = 1
*/
int idx = Collections.binarySearch(keys, hash);
/*
* If the key hash does not exactly match a server position,
* binarySearch returns:
*
* -(insertionPoint) - 1
*
* Example:
* keys = [100, 500, 1000]
* hash = 700
*
* insertionPoint = 2
* binarySearch returns -3
*
* Recover the insertion point:
*
* idx = -(-3 + 1) = 2
*
* This gives us the index of the first server
* clockwise from the key.
*/
if (idx < 0) {
idx = -(idx + 1);
}
/*
* Handle ring wrap-around.
*
* Example:
* keys = [100, 500, 1000]
* hash = 1500
*
* insertionPoint = 3
*
* There is no server after 1500, so we wrap
* around to the first server in the ring.
*/
if (idx == keys.size()) {
idx = 0;
}
return nodes.get(idx);
}
public void printRing() {
System.out.println("Hash Ring:");
for (int i = 0; i < keys.size(); i++) {
System.out.println(
keys.get(i) + " -> " + nodes.get(i));
}
}
}
Sample Usage
public class Main {
public static void main(String[] args) {
HashFunction hashFunction =
new DefaultHashFunction();
ConsistentHashRing ring =
new ConsistentHashRing(hashFunction);
ring.addNode(
new Node("A", "10.0.0.1"));
ring.addNode(
new Node("B", "10.0.0.2"));
ring.addNode(
new Node("C", "10.0.0.3"));
ring.printRing();
System.out.println(
"user123 -> "
+ ring.getNode("user123"));
System.out.println(
"user456 -> "
+ ring.getNode("user456"));
}
}
Limitations
Consistent hashing distributes data based on distance between neighboring servers. If server hashes happen to cluster together, the distribution becomes uneven.