Consistent Hashing: The Secret Sauce of Scalable Distributed Systems

Consistent Hashing is a cornerstone of modern distributed systems, enabling seamless scalability with minimal disruption. It ensures that data is evenly distributed across nodes, minimizes the redistribution of keys during scaling, and optimizes resource utilization.

Why Consistent Hashing is a Game-Changer

Imagine a scenario where your system adds or removes servers (nodes) dynamically. In traditional hashing methods (e.g., modulo hashing), such changes lead to almost all keys being remapped, resulting in massive data movement, increased latency, and potential downtime.

Traditional Hashing Problem

Scenario:

• Initial nodes: 3 (hash(key) % 3).
• New nodes added: 1 (total 4, hash(key) % 4)

Impact:

• Almost every key gets remapped, leading to a redistribution storm.

Consistent Hashing Solution

With consistent hashing:

• Nodes and keys are hashed and placed on a circular “hash ring.”
• A key is assigned to the next node in the clockwise direction.
• Adding or removing a node affects only a small subset of keys, minimizing redistribution.

How Consistent Hashing Works

1. Nodes on a Ring: Each node is hashed and placed on a circular hash ring using a hash function.

Node A -> Hash(Node A) 
Node B -> Hash(Node B) 
Node C -> Hash(Node C)

2. Keys on the Ring: Keys are also hashed and placed on the same ring.

Key 1 -> Hash(Key 1) 
Key 2 -> Hash(Key 2)

3. Mapping Keys to Nodes: A key is assigned to the next node clockwise on the ring. If no node is found clockwise, the key wraps around to the first node.

4. Adding/Removing Nodes:

• Adding: Only keys between the new node and its predecessor are affected.
• Removing: Only keys mapped to the removed node are reassigned.

Code Implementation: Consistent Hashing in JavaScript

Here’s how to build consistent hashing with and without virtual nodes.

Without Virtual Nodes

const crypto = require("crypto");

// Hash function
function hash(value) {
  return parseInt(crypto.createHash("sha256").update(value).digest("hex").slice(0, 8), 16);
}
// Consistent Hashing Class
class ConsistentHashing {
  constructor(nodes = []) {
    this.ring = new Map(); // Hash ring
    this.nodeHashes = [];  // Sorted node hashes
    // Initialize with given nodes
    nodes.forEach(node => this.addNode(node));
  }
  // Add a node to the ring
  addNode(node) {
    const nodeHash = hash(node);
    this.ring.set(nodeHash, node);
    this.nodeHashes.push(nodeHash);
    this.nodeHashes.sort((a, b) => a - b);
  }
  // Remove a node from the ring
  removeNode(node) {
    const nodeHash = hash(node);
    this.ring.delete(nodeHash);
    this.nodeHashes = this.nodeHashes.filter(hash => hash !== nodeHash);
  }
  // Get the node responsible for a key
  getNode(key) {
    const keyHash = hash(key);
    for (const nodeHash of this.nodeHashes) {
      if (keyHash <= nodeHash) {
        return this.ring.get(nodeHash);
      }
    }
    // Wrap around to the first node
    return this.ring.get(this.nodeHashes[0]);
  }
}
// Example Usage
const nodes = ["NodeA", "NodeB", "NodeC"];
const ch = new ConsistentHashing(nodes);
console.log(ch.getNode("Key1")); // Node responsible for Key1
console.log(ch.getNode("Key2")); // Node responsible for Key2
ch.addNode("NodeD");
console.log(ch.getNode("Key1")); // Minimal redistribution

Advantages of Consistent Hashing

1. Minimal Data Movement: Adding or removing a node redistributes only a small subset of keys, reducing overhead.
2. Load Balancing: Ensures an even distribution of keys across nodes, especially when combined with virtual nodes.
3. Scalability: Handles dynamic scaling seamlessly, making it ideal for modern distributed systems.

With Virtual Nodes

Inconsistent hashing without virtual nodes may result in uneven distribution of keys, causing hotspots. Virtual nodes solve this by hashing each physical node multiple times onto the ring.

Benefits of Virtual Nodes

• Improved Balance: More even key distribution across all nodes.
• Reduced Hotspots: Eliminates imbalances due to node placement.

Real-World Applications

1. Distributed Caching Systems:

• Memcached, Redis: Evenly distribute cached data across servers.

2. Distributed Databases:

• Cassandra, DynamoDB: Ensure efficient key-value storage and retrieval.

3. Load Balancers:

• Route client requests to backend servers with minimal disruption.

Key Takeaways

• Consistent Hashing is essential for scalable, efficient distributed systems.
• It minimizes the disruption caused by scaling while ensuring balanced workloads.
• Real-world applications span caching, databases, and load balancing, making it a cornerstone of modern tech stacks.

With Consistent Hashing, you can build systems that scale effortlessly while maintaining optimal performance. Whether you’re designing a caching layer, a database, or a load balancer, consistent hashing ensures you’re prepared to handle the demands of distributed architectures. 🚀