Theory
Consistent Hashing
📋 Overview
Consistent Hashing is a specialized distributed hashing scheme that allows for the scaling of clusters (caches, databases) with minimal data movement. In a traditional hash(key) % N scheme, adding or removing a node causes almost all keys to remap, leading to a "cache miss storm" or massive data migration. Consistent Hashing solves this by mapping both keys and nodes to a circular "Hash Ring," ensuring that only a small fraction of keys ($1/N$) need to be moved when the cluster size changes.
🏗️ Core Principles & Characteristics
- The Hash Ring: A conceptual circular space (typically $0$ to $2^{32}-1$) where both servers and data keys are hashed.
- Clockwise Assignment: A key is assigned to the first server it encounters when moving clockwise around the ring.
- Virtual Nodes (VNodes): To prevent "hotspots" where one physical server handles too much data, each physical server is represented by multiple virtual points on the ring.
- Independence of N: The mapping of keys is largely independent of the number of servers, making the system "elastic."
⚖️ Trade-offs: Pros & Cons
- Pros:
- Elastic Scalability: Easily add or remove nodes without bringing down the system or overloading the origin.
- Load Balancing: Virtual nodes ensure an even distribution of data even with heterogeneous hardware.
- Fault Tolerance: If a node fails, its load is automatically and evenly distributed among all other nodes, not just one neighbor.
- Cons:
- Complexity: Managing the ring and virtual node metadata is more complex than simple modulo hashing.
- Lookup Overhead: Finding the correct node requires a binary search ($O(\log VNodes)$) rather than a constant time $O(1)$ calculation.
- Cascading Failures: Without enough VNodes, a single node failure can still overwhelm the next node in the ring.
🌍 Real-World Implementation
- Amazon Dynamo & Apache Cassandra: Use consistent hashing to partition data across large clusters.
- Akamai & Cloudflare: Use it for load balancing requests across global edge servers to ensure the same user hits the same cache.
- Discord: Uses consistent hashing to distribute users across "gateway" servers to maintain WebSocket connections.
- Memcached: Clients (like Ketama) implement consistent hashing to manage cache pools.
💡 Interview "Gotchas" & Tips
- Why Virtual Nodes? This is a favorite follow-up. Answer: "They solve the data skew problem and ensure that when a node fails, its load is split across all remaining nodes rather than just the immediate neighbor."
- Replication: How do you handle HA? "Instead of storing data on just one node, store it on the next $K$ unique physical nodes encountered clockwise on the ring."
- Data Migration: When a node is added, it only "steals" keys from its immediate counter-clockwise neighbor. All other nodes remain unaffected.
- Complexity of finding the node: In code, this is usually implemented using a TreeMap (Java) or Sorted Dictionary to find the "ceiling" of the key's hash.
📐 Suggested Architecture Primitives
- Hash Function: MurmurHash3 or MD5 (uniform distribution).
- Sorted Data Structure: (TreeMap/Binary Search Tree) to represent the ring.
- Membership Protocol: (Gossip Protocol) for nodes to stay updated on the ring's state.
- VNode Factor: Typically 100-200 virtual nodes per physical machine.
Canvas