Consistent hashing defined
Consistent hashing is a method of evenly distributing hashed values across a hash table with a predefined number of keys. The idea is that the hash table is represented as a circular ring (a.k.a. hash ring).
How does it work?
The aforementioned hash ring will have a predefined number of slots. The number of values you expect to hold within the hash table should be taken into consideration when choosing the upper bound. There is debate as to what percentage of your hash table’s available slots you should try to keep free and the number varies depending on what problem is being solved and with which solution you are using to solve the problem. But generally, you should strive to have no more than 50%-70% of the available slots in the hash table filled at any one time, to ensure optimum performance.
For example, if we want to store ~500k-700k keys our hash table will need to hold 1,000,000 keys. This would mean our hash table will have an upper-bound upperBound = 1000000 equal to 1,000,000. The table would have slots ranging from 0 ... (upperBound - 1), note the -1 is to account for zero indexing. This ensures that the upper-bound will be the upper-most slot available in the hash table before we loop back to zero and restart back at the beginning of the ring.
These slots are available to hold hashed keys. The specific hashing algorithm can vary and is not the topic of this post so I will not elaborate on the hashing function itself, suffice it to say that the hashed keys are to generated by the hashing function and those keys are stored within the slots of the hash table.
What problem does it solve?
Consistent hashing is employed to help evenly spread the load across distributed servers with a heavy consideration taken to account for the possibility (or probability) that the number of available servers may change.
In more static design patterns a value may be mapped to a server in a static manner. Consider the following example:
A system is designed to have 10 cache servers (nServers = 10) that will serve requests for our cached data based on a resource id. The resource id, in this scenario will be the key. We would use the following calculation to determine which server will hold the cached value and in turn handle the request: cacheServer = key % nServers. This method is simple and easy to understand… cached ids [0 … 99,999] are to be stored on server 1 while server 2 would hold keys [100,000 … 199,999] and so on.
The problem with this sort of design is that when the number of available servers change, the implementation breaks due to the fact that the hashed keys may no longer reside on the server that they were originally mapped to. Additionally there is a high computational cost associated with the re-hashing the keys in order to ensure they are assigned and cached on the proper server once re-calculated to account for the new number of available servers (especially at scale).
The need to re-hash and reassign a large number of keys is mitigated when using the consistent hashing design pattern for distributed caches or load balancers.
In summary
With consistent hashing each server is assigned a segmented range of the hash ring… each server will cache all values starting at the previous server’s range +1 … up to the index of its own range. The hash ring is always traversed in a clockwise direction beginning at the given key until the next server in the ring has been reached… that server will be the one that holds the cached data. Should any server be added or removed, there is no need to re-hash the entire hash table, instead we follow the same formula as described above; Start at the key to resolve and traverse clockwise until we reach a server, that will be the server that serves the data for the given key, as illustrated below.
Consistent Hashing Illustration
- The red lines indicate the start and end indexes.
- The green lines represent servers in the hash ring.
- The space between the green lines is the range of key slots.
- Note that resolution is always in a clockwise direction.
Comments are closed.