An overview of the

There is a scenario where the key should be routed to a service provided by multiple server groups. If you use the most general method, key%N(N is the number of servers), this seems fine at first glance, but when the number of servers sent increases or decreases, the allocation method is changed to key%(N+1) or key%(n-1). There will be a lot of key failure migration, and if the back-end keys correspond to stateful storage data, this will undoubtedly lead to a lot of data migration between servers, resulting in service instability. In order to solve the class problem, the consistent hash algorithm came into being.

1. Features of the consistent hash algorithm

In distributed caching, a good hash algorithm should satisfy the following criteria:

  • Balance Means that nodes in a cluster should be as balanced as possible through algorithm allocation.

  • Monotonicity means that when the cluster changes, keys that have been allocated to the old node are still allocated to the old node as much as possible to prevent massive data migration. In this case, it is difficult to meet the requirements of ordinary hashing, while the consistent hash algorithm can keep the number of keys migrated to a low level.

  • Dispersity (Spread) Dispersity mainly applies to the same key. When operations are performed on different clients, the number of cache clusters obtained by clients may be inconsistent, resulting in the mapping of keys to different nodes, which may cause data inconsistency. A good hash algorithm should avoid fragmentation as much as possible.

  • The Load applies to a cache. The same cache may be mapped to different keys, causing the status of the cache to be inconsistent.

In principle, the consistent hash algorithm has a reasonable solution to all the above problems.

2. Consistency hash

The core idea of consistent hash is to hash the key and round it according to certain rules to get the value between 0 and 2^32-1. The size of the ring is 2^32, and the integer value calculated by the key is the key position on the hash ring. How to map a key to a node is divided into two steps. In the first step, the key of the service is calculated according to the hash algorithm to obtain the position of the service on the consistent hash ring. The second step is to calculate the position of the cache key on the hash ring in the same way. In the clockwise direction, find the first service key that is greater than or equal to the position of the hash ring, so as to obtain the server to which the key needs to be allocated.

As shown in the figure, each key is allocated to each NODE according to the hash algorithm. When a NODE fails, such as NODE 2, the key on NODE 2 will be allocated to the adjacent nodes in the Hash ring, while the positions of other keys remain unchanged.

Virtual nodes improve balance

As can be seen above, because only three nodes, there are some nodes location surrounded by a large number of hash point leading to assigned to the node to the key are much more than other nodes, it will bring each node in the cluster load imbalance, in order to solve this problem, the introduction of virtual node, that is, a real node corresponding to multiple virtual node. When the cache key is mapped, the corresponding virtual node is first found and then the corresponding real node is mapped. As shown in the following figure, two virtual nodes are created for each node to improve balance.

3. Compare the consistent hash algorithm with other algorithms

There are several solutions to the node allocation problem of caching class data keys in a cluster: simple hashing, slot mapping, and consistent hash.

  • For hash moduling, there is no problem with equalization, but if a new node is added to the cluster, there will be N/(N+1) data efficiency, and the higher the N value, the higher the failure rate. This is clearly unacceptable.

  • Slot mapping Redis uses this algorithm. The idea is to compute the key value (crc16, CRC32, hash) to get an integer value, and then compute the value with a fixed number of slots. Each node processes fixed slots. When obtaining the node where the key resides, you need to calculate the mapping between the key and slot, and then locate the node based on the mapping between slot and node. In this case, only the key corresponding to a certain slot needs to be migrated each time a node is added, but the key value of the slot does not take effect. In this way, the real efficiency is reduced to 1/(N+1). However, the disadvantage of this approach is that all nodes need to know the slot and node mapping. If the client does not save the slot and node mapping, it needs to implement the redirection logic.

  • Consistent hash As described above, the failure rate of a new node is only 1/(N+1), which minimizes the real efficiency through consistent hash. At the same time, compared with the way of slot mapping, there is no need to lead the slot to do the intermediate corresponding, which simplifies the implementation to the maximum extent.

4. Implement consistent Hash algorithm based on Golang

Golang is used here to realize consistent hash. Considering that in actual use scenarios, machine configurations among service nodes may be different, the logic of virtual node redistribution based on node weight is provided, so as to make nodes with high weight bear more keys and nodes with low weight bear less keys as much as possible. Of course, there are many things involved in the calculation of weights here, see the code: hashring

5. To summarize

This paper analyzes the principle of consistent hash and compares it with other distributed cluster allocation algorithms. From the perspective of distributed cache, two famous distributed storage systems redis and memcached respectively use slot mapping and consistent hash. Due to the different algorithms, The sequence of actions triggered by node changes in a cluster is also different, each with its own considerations.

6. Reference

Consistent Hasing

Redis Cluster