Consistent Hashing

When a node is added or removed from the ring, consistent hashing only requires reassigning the keys that were mapped to the affected node's segment of the hash ring. This is in stark contrast to traditional hashing, where a change in the number of slots (mod N) causes nearly all keys to be remapped, leading to massive data movement and cache invalidation.

• Key Benefit: Enables elastic scaling of distributed caches (like Redis Cluster) and storage systems (like Amazon DynamoDB) without service disruption.
• Example: In a 100-node cluster, adding a 101st node requires moving only ~1% of the total keys, not 99%.

Basic consistent hashing can lead to uneven load distribution if nodes are mapped to uneven segments of the ring. This is solved using virtual nodes (vnodes).

• Each physical node is assigned multiple random positions (vnodes) on the hash ring.
• This statistically distributes the key space more evenly across physical machines.
• Practical Impact: Prevents hotspots where a single node becomes overloaded. Systems like Apache Cassandra heavily rely on vnodes for balanced data distribution and simplified operations like adding new datacenters.

The hash ring abstraction provides inherent fault tolerance. If a node fails, the system can route requests to the successor node on the ring.

• Failover Mechanism: Client libraries or routing layers automatically detect the failure and skip to the next live node in the clockwise direction.
• Data Replication: To protect against data loss, keys are typically replicated to the N successor nodes on the ring (where N is the replication factor). This ensures data is available even if a primary node fails.
• Use Case: Foundational for distributed hash tables (DHTs) like Chord and Kademlia, which underpin peer-to-peer networks.

Any client or node can independently determine which node owns a given key using the same hash function and ring logic, without consulting a central directory.

• Deterministic Lookup: hash(key) -> position on ring -> clockwise walk to first node.
• Eliminates Single Point of Failure: No central coordinator is needed for routing decisions, enhancing system resilience.
• Architectural Impact: This property is critical for content delivery networks (CDNs). Edge servers can independently determine which origin server or cache holds a specific piece of content.

Consistent hashing is not an end-user feature but a core architectural primitive enabling several foundational distributed systems.

• Load Balancers: Used in maglev hashing (Google) for stable mapping of connections to backend servers.
• Distributed Caching: Memcached and Redis Cluster use it to partition the key space across instances.
• Object Storage: Systems like Amazon Dynamo and Riak use it for data partitioning and replication.
• Stream Processing: Apache Kafka uses it to assign topic partitions to consumers in a consumer group.

Understanding what consistent hashing solves highlights its value.

• Traditional Modulo Hashing: server = hash(key) mod N. If N changes (node added/removed), almost all keys map to a new server (N vs N+1). This causes a stampeding herd problem as caches are invalidated globally.
• Consistent Hashing: Maps both keys and nodes to a fixed ring. A node change only affects keys in the immediate arc between it and its predecessor on the ring.
• The Trade-off: Introduces slight load imbalance (solved by vnodes) and more complex implementation, but provides massive operational stability during cluster resizing.

A database partitioning technique that horizontally splits a large dataset into smaller, more manageable pieces called shards, each hosted on a separate server. This is the primary problem consistent hashing solves by determining which shard (node) is responsible for a given piece of data.

• Key Use: Enables horizontal scaling of databases by distributing load.
• Challenge: Requires a partitioning key and a strategy to map data to shards, which is where consistent hashing provides stability during cluster resizing.

A decentralized distributed system that provides a lookup service similar to a hash table, where (key, value) pairs are distributed across many nodes. Consistent hashing is the core algorithm used by many DHTs (like Chord, Kademlia) to assign keys to nodes and route requests efficiently.

• Key Feature: No central coordinator; nodes cooperate to store and retrieve data.
• Mechanism: Each node becomes responsible for a range of hash space, enabling peer-to-peer discovery and storage.

The process of distributing network or application traffic across multiple servers to ensure no single node becomes a bottleneck. Consistent hashing is used in stateful load balancing to direct client requests for the same session or data to the same backend server, minimizing cache misses and data movement.

• Stateless vs. Stateful: Round-robin is stateless; consistent hashing enables sticky sessions.
• Benefit: Provides predictable mapping, which is crucial for caching layers (e.g., CDNs, proxy caches).

The technique of copying and maintaining database objects across multiple nodes to improve availability, fault tolerance, and read performance. Consistent hashing determines the primary node for a data item, and replication strategies define how many and which replica nodes receive copies.

• Common Strategy: The successor nodes on the consistent hash ring often serve as natural replicas.
• Challenge: Ensuring consistency between replicas during writes, often handled by protocols like Raft or Paxos.

A refinement to basic consistent hashing where each physical node is represented by multiple virtual nodes (or tokens) placed at different points on the hash ring. This technique solves the problem of uneven data distribution (load imbalance) that can occur with heterogeneous hardware or simple node assignment.

• Key Benefit: Allows a more powerful physical node to host more virtual nodes, leading to a proportionally larger share of the hash ring and data.
• Result: Enables fine-grained control over the data distribution and capacity planning.

An alternative to consistent hashing, also known as HRW Hashing. For a given key, the algorithm computes a weighted score (hash) for each node in the cluster and selects the node with the highest score. The primary advantage is that it minimizes data movement when a node fails—only keys owned by the failed node need reassignment.

• Comparison to Consistent Hashing: More computationally expensive per lookup (O(n)) but provides perfect minimal disruption on node failure.
• Use Case: Often preferred in smaller, stable clusters where optimal distribution is critical.