Consistent Hashing for Distributed Caching and Databases

The Challenge of Scaling with Hashing

In distributed systems, data is often partitioned across multiple servers using a hash function. A common naive approach is `hash(key) % N`, where `N` is the number of servers. While simple, this method suffers significantly when the number of servers `N` changes. Adding or removing a single server can cause almost all keys to remap to new servers, leading to massive data migration and cache invalidations, which can cripple system performance and availability.

Introduction to Consistent Hashing

Consistent hashing is an algorithm designed to minimize the number of keys that need to be remapped when nodes are added or removed from a distributed hash table. Instead of mapping keys directly to server indices, it maps both servers and keys to a continuous hash ring (or circle). Each server is responsible for a segment of the ring, handling all keys that fall within its segment.

Virtual Nodes for Load Balancing

To achieve better load distribution and mitigate hotspots, consistent hashing employs the concept of "virtual nodes" (or "vnodes"). Each physical server is assigned multiple points on the hash ring. This means that if a physical server goes down, its load is distributed more evenly among many remaining servers, instead of overloading just one neighbor. Virtual nodes also help in distributing data more uniformly across the ring, reducing the impact of non-uniform hash distributions.

Applications in Real-World Systems

• Cassandra & DynamoDB: Use consistent hashing to distribute data across nodes, providing high availability and scalability.
• Discord: Employs consistent hashing for stateful services, ensuring efficient routing and minimal disruption during scaling events.
• CDN Caching: Often used to distribute content among cache servers, ensuring that a specific piece of content consistently maps to the same cache server, while minimizing invalidations during cache cluster changes.