Consistent Hashing

The primary advantage of consistent hashing is its ability to minimize data movement when the hash ring changes. When a node is added or removed, only the keys mapped to the segment of the ring between that node and its immediate predecessor are remapped. This is in stark contrast to traditional modular hashing (hash(key) % N), where a change in the number of nodes N causes nearly all keys to be remapped, leading to massive data shuffling and cache invalidation.

Consistent hashing visualizes the output range of a hash function as a fixed circular space or ring. Both data keys and nodes are mapped onto 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 abstraction decouples the node count from the hash space, allowing nodes to occupy arbitrary positions. The size of the hash space (e.g., 0 to 2^160 - 1) is typically much larger than the number of nodes, ensuring a relatively even distribution.

To combat non-uniform data distribution and load imbalance 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 points (Vnodes) scattered across the ring.

• Benefits:
  • Load Balancing: Distributes a physical node's ownership of the ring across many smaller segments, smoothing out hot spots.
  • Proportional Capacity: Nodes with higher capacity can be assigned more Vnodes to handle a larger share of the data.
  • Graceful Handling of Heterogeneity: Accommodates nodes with different performance characteristics.

Consistent hashing enables horizontal scaling with predictable performance. The lookup operation for a key is deterministic: hash the key, find its position on the ring, and locate the next node. In a well-implemented system with a sorted list of node positions or a structure like a binary search tree, this lookup can be performed in O(log N) time, where N is the number of virtual nodes. This efficiency remains stable as the cluster grows or shrinks.

The structure inherently supports fault tolerance. When a node fails (is removed from the ring), the load it managed is seamlessly transferred to its immediate successor node on the ring. Client requests that previously mapped to the failed node will now find the successor, ensuring service continuity. This provides graceful degradation rather than a complete system failure. Recovery involves redistributing the data from the successor back to a replacement node when it joins.

Consistent hashing is a foundational algorithm for distributed caching and storage systems where load distribution and minimal disruption are paramount.

• Distributed Caches: Memcached, Redis Cluster, and Varnish use it to distribute key-value pairs across a pool of servers.
• Content Delivery Networks (CDNs): Used to route client requests to the nearest or most appropriate edge server.
• Distributed Databases: Apache Cassandra, DynamoDB, and Riak employ consistent hashing (often with Vnodes) to partition data across the cluster.
• Load Balancers: For directing persistent client sessions to the same backend server.

A predetermined algorithm that determines which items to remove from a cache when it reaches its capacity limit. Consistent hashing determines where data lives; the eviction policy determines what gets removed from that location.

• Purpose: Maximize cache hit rate and system performance.
• Common Algorithms: LRU, LFU, ARC, and TTL-based expiration.
• Interaction with Hashing: The policy operates locally on each node in the hash ring after consistent hashing assigns keys.

A probabilistic, memory-efficient data structure used to test set membership. In distributed caches using consistent hashing, Bloom filters can prevent expensive network calls for non-existent keys.

• Mechanism: Returns either 'definitely not in set' or 'possibly in set' with a configurable false-positive rate.
• Use Case: Placed in front of cache clusters to quickly filter out requests for keys that were never stored, reducing load.
• Trade-off: Uses minimal memory but cannot confirm a key's presence definitively.

An imbalance in the distribution of data or load across partitions or nodes in a distributed system. While consistent hashing aims for uniform distribution, real-world access patterns can cause hotspots.

• Cause: Non-uniform key popularity or poor hash function choice.
• Problem: Leads to hot nodes, uneven load, and degraded parallel performance.
• Mitigation: Techniques like virtual nodes in consistent hashing help distribute load more evenly.

A performance issue where a cache miss or node failure causes a sudden, simultaneous surge of requests to a backend resource (like a database) from many clients. Consistent hashing can influence this during node failures.

• Scenario: When a node leaves the ring, its keys are reassigned to its successor. If those keys are popular, the successor node may be overwhelmed.
• Solution: Implement request coalescing or background warm-up to mitigate the spike in load on the new node.

A consistency model for distributed data stores where all replicas will converge to the same state given enough time without new updates. This is a common trade-off in systems using consistent hashing for scalability.

• Context: When a node joins/leaves a consistent hash ring, key ownership changes propagate asynchronously.
• Implication: Clients may temporarily read stale data from an old node before the membership change is fully recognized.
• Benefit: Enables high availability and partition tolerance, as per the CAP theorem.

A high-performance storage engine data structure that batches writes in memory before merging them to disk. LSM Trees are often the underlying storage layer for persistent systems built on consistent hashing.

• Mechanism: Uses an in-memory memtable and sorted, immutable SSTable files on disk.
• Synergy with Hashing: Consistent hashing distributes LSM Tree instances across a cluster (e.g., in databases like Apache Cassandra).
• Advantage: Provides very high write throughput, which complements the scalable data placement of consistent hashing.