Consistent Hashing

When a node is added or removed from the ring, only the keys that hash to the segment between that node and its predecessor are remapped. This is in stark contrast to traditional modulo-based hashing, where adding a single server (changing the denominator N) forces a reassignment of nearly all keys, causing a massive resharding event. In a system with K keys and N nodes, consistent hashing requires only K/N keys to be moved on average, providing linear scalability with minimal overhead.

The core data structure is a virtual circle (ring) representing the entire output range of a hash function (e.g., 0 to 2^128 - 1). Both nodes and keys are hashed onto this ring. A key is assigned to the first node encountered when moving clockwise from the key's position. This creates a deterministic, order-preserving mapping. The ring is often implemented using a sorted data structure like a balanced binary search tree or a skip list to allow O(log N) lookups for finding a key's successor node.

To combat uneven load distribution caused by random node placement on the ring, the concept of virtual nodes is used. Instead of a single point, each physical node is represented by multiple, smaller Vnodes scattered across the ring. This provides several key benefits:

• Load Balancing: Smoothes out the statistical distribution of keys.
• Flexible Weighting: Nodes with higher capacity can be assigned more Vnodes.
• Graceful Handling of Heterogeneity: Accommodates servers of differing performance profiles.
• Faster Rebalancing: Failure of a physical node disperses its load across many successors.

A naive consistent hash ring can still create hotspots if a small subset of keys is accessed far more frequently. Advanced implementations enforce bounded load. The algorithm tracks the current load (e.g., requests per second, connections) of each node. When a request arrives for a key, the system iterates clockwise from the key's hash, skipping nodes that are at or over capacity, until it finds an eligible node. This provides deterministic fallback and prevents overloading a node simply because it owns popular keys.

This is a formal guarantee of the algorithm: when a new node is added to the system, keys are only moved from existing nodes to the new node; keys are never moved between existing nodes. This monotonicity is crucial for caching systems, as it ensures that the vast majority of cached data remains valid and accessible after a scaling event. It directly enables horizontal scaling without a corresponding spike in cache misses or database load, which would occur with a total reshuffle.

Given a stable ring membership, the mapping from any key to its responsible node is deterministic. Any client with knowledge of the ring can independently compute where a key lives, enabling client-side load balancing and reducing latency by removing a central coordinator. In the event of a node failure, the key's request simply wraps around the ring to the next live node. This built-in failover mechanism makes the system highly available, as traffic is automatically redirected without requiring a complex consensus protocol to reconfigure the entire cluster.

The overarching process of distributing network traffic or computational workload across multiple servers or resources. Core objectives are to optimize resource utilization, maximize throughput, minimize response time, and avoid overloading any single node. This is the parent category for all specific algorithms, including consistent hashing.

The core data structure used in consistent hashing. Both servers (nodes) and requests (keys) are mapped onto a fixed, circular numerical space (e.g., 0 to 2^128 - 1).

• Node Placement: Each server is assigned one or more random positions on the ring via a hash function.
• Key Assignment: A request is hashed to a point on the ring and is then handled by the first node encountered when moving clockwise. This ring abstraction is what minimizes reorganization during scaling events.

A critical enhancement to basic consistent hashing used to ensure an even workload distribution. Instead of a single point, each physical server is represented by multiple points (e.g., 100-1000) on the hash ring.

• Improves Balance: Mitigates the uneven distribution (load skew) that can occur if nodes are randomly placed.
• Facilitates Weighting: Allows a more powerful server to be assigned more virtual nodes, proportionally increasing its share of the workload.

The broader database architecture pattern where a dataset is split into smaller, manageable pieces called shards or partitions, each stored on a different server. Consistent hashing is the preferred algorithm for determining which partition a piece of data belongs to because:

• Minimal Data Movement: Adding/removing a storage node only requires moving the data owned by that specific node, not reshuffling the entire dataset.
• Deterministic Location: Any key can be instantly located by computing its hash and finding the responsible node on the ring.

An alternative to consistent hashing that achieves similar goals without a ring structure. For a given request key, the algorithm:

1. Computes a weighted score (hash) for the combination of the key and each available server.
2. Selects the server with the highest resulting score.

• Advantage: Provides a more perfectly uniform distribution of load.
• Disadvantage: Adding/removing a server requires re-evaluating all keys, as the "highest score" for each key may change, leading to more reorganization than consistent hashing.

The mechanism by which systems in a distributed architecture automatically find and communicate with available service instances. Consistent hashing often works in tandem with service discovery:

• Dynamic Node Sets: A service discovery registry (e.g., Consul, etcd, Zookeeper) maintains the live list of backend servers.
• Hash Ring Population: The load balancer or client library uses this list to build or update its hash ring. When a server is added or removed from the registry, the ring is updated, and consistent hashing ensures minimal disruption to existing mappings.