Consistent Hashing: Distributing Data at Scale
This article explains consistent hashing as a fundamental technique to address the scalability issues of naive hashing approaches like `hash % N` in distributed systems. It highlights how simple modulo hashing leads to a catastrophic remapping of nearly all data when servers are added or removed, causing thundering herd problems and outages. Consistent hashing elegantly solves this by mapping both data keys and servers onto a circular hash space, ensuring only a small, localized portion of the keyspace is affected during scaling operations.
Read original on Dev.to #systemdesignThe Problem with Naive Hashing (hash % N)
When distributing data across `N` servers (e.g., for caching or sharding), a common but flawed initial thought is to use `hash(key) % N` to determine which server holds the data. This approach seems straightforward but introduces significant problems at scale. The core issue arises when the number of servers, `N`, changes.
Catastrophic Cache Invalidation
As demonstrated by Facebook's Memcached experience, changing `N` (e.g., adding a single server) causes approximately `N/(N+1)` of all keys to remap to different servers. For a system with 100 servers, adding one more means ~99% of keys will now resolve to a different server. This results in a massive wave of cache misses, known as a "thundering herd," where origin databases are overwhelmed, potentially leading to partial or full outages.
Consistent Hashing to the Rescue
Consistent hashing provides an elegant solution to the data remapping problem. Instead of simply relying on the number of active servers, it maps both the servers and the data keys onto a continuous circular hash space (often referred to as a "hash ring"). This space typically ranges from 0 to 2³²-1 or 0 to 2⁶⁴-1.
When a server is added or removed, only the keys in the immediate vicinity of that server's position on the ring are affected and need to be remapped. This significantly reduces the impact, typically limiting key remappings to roughly `1/N` of the total keys, preventing the cascading failures seen with naive hashing. Implementations often use "virtual nodes" to improve distribution and balance load more evenly across the physical servers.