Consistent Hashing

When a node (server) is added or removed from the ring, consistent hashing only requires reassigning the keys that were mapped to the affected node. The majority of keys retain their existing assignments. This is in stark contrast to traditional modulo-based hashing, where a change in the number of nodes (n) causes nearly all keys to be remapped, leading to massive data movement and cache invalidation. For a system with K keys and N nodes, only roughly K/N keys need to be moved on average when a node fails or is added.

The algorithm visualizes a hash space as a fixed circular ring, or continuum. Both nodes and data keys are hashed onto points on this ring using the same hash function (e.g., SHA-1). A key is stored on the first node encountered when moving clockwise around the ring from the key's position. This ring abstraction is the core data structure that enables the algorithm's stability and distribution properties. The ring is typically implemented using a sorted data structure for efficient lookups, such as a balanced binary search tree or a skip list.

To prevent uneven data distribution (load imbalance) where a few nodes can become hotspots, consistent hashing uses virtual nodes (vnodes). Instead of a single point on the ring, each physical node is represented by multiple, randomly distributed virtual points. This technique has two key benefits:

• Smoother Distribution: It statistically distributes the ownership of the hash space more evenly among physical nodes.
• Weighted Capacity: The number of vnodes assigned to a physical node can be proportional to its capacity (e.g., a server with 2x the RAM gets 2x the vnodes), allowing for heterogeneous infrastructure.

The structure of the hash ring provides inherent fault tolerance. If a node fails, the load is automatically transferred to its successor node on the ring. This failover is deterministic and immediate from the perspective of the hashing algorithm. Systems built on consistent hashing, like DynamoDB and Cassandra, often replicate each piece of data to the N successor nodes on the ring (a strategy known as replication factor). This ensures data remains available even if a primary node fails, without requiring a complete cluster reconfiguration.

Given a key, any client in the system can independently and deterministically compute which node is responsible for it, as long as it knows the hash function and the current set of nodes on the ring. This eliminates the need for a central coordinating service or a mapping table for every key lookup, which would become a scalability bottleneck. Clients can cache the ring structure and update it only when node membership changes, enabling extremely fast, direct routing of requests.

Consistent hashing is the backbone of many large-scale distributed systems:

• Distributed Caches: Memcached and Redis Cluster use it to partition data across cache servers, minimizing cache misses during scaling events.
• NoSQL Databases: Amazon DynamoDB, Apache Cassandra, and Riak use it for data partitioning and replication.
• Content Delivery Networks (CDNs): Used to route client requests to the appropriate edge server.
• Load Balancers: Modern L7 load balancers use it for persistent session affinity (sticky sessions), ensuring a user's requests are routed to the same backend server.

A networking device or software component that distributes incoming client requests across a pool of backend servers. Consistent hashing is a key algorithm used by stateful load balancers to ensure requests from the same user are routed to the same server, which is critical for maintaining session state or cache locality.

• Stateless vs. Stateful: Stateless balancers (e.g., round-robin) treat each request independently. Stateful balancers use hashing for session persistence.
• Use Case: In a distributed cache like Redis Cluster, a load balancer using consistent hashing directs a key's read/write operations to the specific node responsible for that key's hash range.

The practice of splitting a large database or dataset into smaller, more manageable pieces called shards, which are distributed across multiple nodes. Consistent hashing provides the underlying mechanism for determining which shard owns a given piece of data.

• Key-Based Partitioning: A partition key (e.g., user ID) is passed through a hash function. The output determines the target shard.
• Minimal Reorganization: When a shard is added or removed, consistent hashing minimizes the amount of data that must be moved, redistributing only the keys adjacent to the change on the hash ring, rather than the entire dataset.

A decentralized distributed system that provides a lookup service similar to a hash table, where (key, value) pairs are stored across a network of nodes. Consistent hashing is the core algorithm that defines the structure and routing of many DHTs, such as Chord and Apache Cassandra's ring topology.

• Decentralized Routing: Each node in the DHT is responsible for a range of keys on the hash ring. Nodes know about their neighbors, enabling efficient key location in O(log N) hops.
• Fault Tolerance: The ring structure allows the system to handle node failures by reassigning the failed node's key range to its successor.

A technique that enhances consistent hashing by assigning multiple, smaller hash ranges (virtual nodes) to a single physical node. This improves load distribution and speeds up recovery during cluster changes.

• Balancing Load: Without vnodes, a powerful physical node has the same responsibility as a weaker one. Vnodes allow the powerful node to host more virtual nodes, taking on a proportionally larger share of the data.
• Faster Rebalancing: When a node fails, its many vnodes are redistributed across many other physical nodes in parallel, speeding up recovery compared to moving one large contiguous hash range.

An alternative to consistent hashing where a client computes a weighted score for each node using a hash function combining the desired key and the node identifier. The client then selects the node with the highest score.

• Client-Side Decision: The mapping is computed by the client, eliminating the need for a central directory or a shared ring structure.
• Load Distribution: Provides excellent load distribution and minimizes data movement when nodes are added (only the keys that now hash to the new node move). However, all clients must know the full node membership list.

The algorithm a cache uses to decide which items to remove when it reaches its capacity limit. In a distributed cache using consistent hashing, eviction policies operate locally on each node.

• Local vs. Global Policy: Each node manages only the keys in its assigned hash range. Common policies include:
  • LRU (Least Recently Used): Discards the least recently accessed items.
  • LFU (Least Frequently Used): Discards the least frequently accessed items.
  • TTL (Time-To-Live): Automatically expires items after a set duration.
• The choice of eviction policy significantly impacts the cache hit rate and overall system performance.