Design a Consistent Hashing
To achieve horizontal scaling, it is important to distribute requests/data efficiently and evenly across servers. Consistent hashing is a commonly used technique to achieve this goal.
Rehashing Problem
If you have N cache servers, a common way to balance the load is to use the following hash method:
serverIndex = hash(key) % N, where N is the size of the server pool.
Supose:
Server0
Server1
Server2
Server4
To fetch server where a key is stored, we perform hash(key) % 4. For instance, hash(key0) % 4 = 1 means a client must contact server 1 to fetch the cached data.
This approach works well when the size of the server is fixed, and the data distribution is even. However, problems arise when new servers are added, or existing servers are removed. For example, if server 1 goes offline, the size of the server pool becomes 3. Using the same hash function, we get the same hash value for each key, but since the number of servers is reduced by 1, we get different serverIndex from modular operation.
This causes most keys to be redistributed. This means that when server 1 goes offline, most cache clients will connect to the wrong servers to fetch data, which will cause a storm of cache misses.
Consistent hashing is an effective technique to mitigate this problem.
Consistent Hashing With Physical Servers
Consisntet hasing with physical servers is inefficient and has two main issues:
- Non-uniform key distribution on the ring
- Non-uniform size of partitions
These problems can be much mitigated using virtual nodes.
Consistent Hashing With Virtual Nodes
As the number of virtual nodes increases, the distribution of keys becomes more balanced. This is because the standard deviation gets smaller with more virtual nodes, leading to balanced data distribution. Standard deviation measures how data are spread out. The outcome of an experiment carried out by online research [2] shows that with one or two hundred virtual nodes, the standard deviation is between 5% (200 virtual nodes) and 10% (100 virtual nodes) of the mean. The standard deviation will be smaller when we increase the number of virtual nodes. However, more spaces are needed to store data about virtual nodes. This is a tradeoff, and we can tune the number of virtual nodes to fit our system requirements.