This article is shared from huawei cloud community “16 Illustrations | Consistent Hashing Algorithm” by Xiao Lin Coding.

How are requests allocated?

Behind most websites is certainly not only a server to provide services, because the amount of concurrency and data are limited, so will use multiple servers to form a cluster to provide services.

But the problem is, how do you distribute requests from clients now that there are so many nodes?

In fact, this problem is “load balancing problem”. There are many algorithms to solve the load balancing problem. Different load balancing algorithms correspond to different allocation policies and adapt to different service scenarios.

The simplest way to do this is to introduce an intermediate load balancing layer that “takes turns” forwarding requests from the outside world to the internal cluster. For example, if the cluster has three nodes and three external requests, each node will process one request, thus achieving the purpose of allocating requests.

Considering the hardware configuration, each node can we introduce weights, the hardware configuration is better node set higher weight value, and then according to the weight value of each node, according to certain proportion distribution on different nodes, more requests for better hardware configuration node, this algorithm is called weighted polling.

The weighted polling algorithm uses scenarios that are built on the premise that each node stores the same data. So, every time a request is made to read the data, access to any node will get the result.

However, weighted polling algorithms cannot handle “distributed systems” where each node stores different data.

When we want to increase the capacity of the system, we will horizontally slice the data to different nodes for storage, that is, distribute the data to different nodes. For example, in a distributed KV (key-valu) cache system, it should be determined on which or which nodes a key should be obtained, not that any access to a node can get the cache result.

Therefore, we need to think of a load balancing algorithm that can handle distributed systems.

What’s the problem with using hashing?

Some of you might think of it quickly: hashing. Because the hash of the same keyword is calculated with the same value each time, a key can be determined to a node, which can meet the load balancing requirements of distributed systems.

The simplest way of hash algorithm is to carry out modulus operation, such as distributed system has three nodes, based on the hash(key) % 3 formula to map the data.

If the client wants to retrieve data for the specified key, the node can be located by using the following formula:

hash(key) % 3
Copy the code

If the value obtained by the above formula is 0, it means that the key needs to be fetched from the first node.

However, there is a fatal problem. If the number of nodes changes, that is, when the system is being expanded or scaled down, the data that has changed the mapping relationship must be migrated. Otherwise, the data cannot be queried.

For example, suppose we have A distributed KV cache system composed of three nodes A, B and C, and map the data based on the calculation formula Hash (key) % 3. Each node stores different data:

Select * from key-01; select * from key-02; select * from key-03; After the hash() function computs the values of the three keys, hash(key-01) = 6, hash(key-02) = 7, and hash(key-03) = 8 respectively. Then modulo these values.

Through this hash algorithm, each key can be located to the corresponding node.

When three nodes can no longer meet business requirements, we add a node, and the number of nodes changes from 3 to 4, which means the change of cardinality in the modular hash function, which will lead to the change of most mapping relations, as shown in the following figure:

For example, hash(key-01) % 3 = 0 becomes hash(key-01) % 4 = 2. When querying key-01 data, node C is addressed, but key-01 data is stored on node A, not node C. Therefore, data cannot be queried.

Similarly, if we reduce the size of a distributed system, such as removing a node, we may not be able to query the data due to the change of cardinality in the modulus hash function.

To solve this problem, we need to migrate the data. For example, when the number of nodes changes from 3 to 4, we need to re-map the data and nodes based on the new calculation formula Hash (key) % 4.

Assuming that the total number of data is M, the hash algorithm needs to migrate all data in the worst case when the number of nodes changes, so its data migration scale is O(M), so the data migration cost is too high.

Therefore, we should think of a new algorithm to avoid excessive data migration when the distributed system is expanded or scaled down.

What’s the problem with using consistent hashing?

Consistent hashing algorithm can solve the problem of excessive data migration when the distributed system expands or shrinks.

The uniform hash algorithm also uses modulo, but unlike the hash algorithm, which modulo the number of nodes, the uniform hash algorithm modulo 2^32, which is a fixed value.

We can organize the value of the uniform hash algorithm into a circle, just like a clock. The circle of a clock can be understood as a circle composed of 60 points. Here we imagine the circle as a circle composed of 2^32 points, which is called a hash ring, as shown below:

Consistency hashing takes two steps:

  • Step 1: Perform hash calculation for storage nodes, that is, perform hash mapping for storage nodes, for example, hash based on the IP address of the node.
  • Step 2: Hash map the data when storing or accessing the data;

So, consistent hashing refers to mapping both “storage nodes” and “data” to one end-to-end hash ring.

So the question is, how do you find the node where the data is stored when you hash it and get a result?

The answer is that the resulting value of the mapping goes clockwise to the first node where the data is stored.

For example, three nodes are hashed to the position shown below:

Then, the key-01 to be queried is hashed to determine the location of the key-01 mapping in the hash ring, and then the first node is found clockwise from this location, which is the node storing the key-01 data.

For example, for the key-01 mapping in the following figure, node A is the first node to be found clockwise.

Therefore, when we need to read or write the specified key value, we need to use the following two steps to address:

  • First, the key is hashed to determine the position of the key on the ring.
  • Then, walking clockwise from this position, the first node you encounter is the node where the key is stored.

Given the consistent hash addressing, let’s see, will there be a lot of data migration if we add or subtract a node?

Suppose the number of nodes increases from 3 to 4, and the new node D is hashed and mapped to the position shown in the following figure:

As you can see, key-01 and key-03 are not affected. Only key-02 needs to be migrated.

Suppose the number of nodes is reduced from 3 to 2, for example by removing node A:

As you can see, key-02 and Key-03 are not affected. Only key-01 needs to be migrated to node B.

Therefore, in a consistent hash algorithm, if a node is added or removed, only the nodes that are clockwise adjacent to the node on the hash ring are affected, and other data is not affected.

The maps of the three nodes in the above diagrams are spread out in the hash ring, so it looks like requests are “balanced” to each node.

However, the consistent hash algorithm does not guarantee that the nodes are evenly distributed across the hash ring, which can lead to the problem that a large number of requests are concentrated on one node.

For example, the mapping position of the three nodes in the following image is on the right half of the hash ring:

At this point, more than half of the data will be addressed to node A, which is where the majority of the requests will be. This is not going to work.

In addition, in the case of uneven node distribution, the adjacent nodes on the hash ring are easily affected by the disaster recovery and capacity expansion, and are prone to avalanche chain reaction.

Pictured above, for example, if the node A is removed, after the node A downtime, according to the rules of consistent hashing algorithm, the data should be on all migrated to the adjacent node B, in this way, node B the amount of data, traffic will increase rapidly, many times, once the new pressure than the node B processing capacity limit, It causes node B to collapse, triggering an avalanche of reactions.

Therefore, although the consistent hash algorithm reduces the amount of data migration, it has the problem of uneven node distribution.

How to improve balance through virtual nodes?

In order to solve the problem that nodes can be distributed unevenly in the hash ring, it is necessary to have a large number of nodes, the more nodes, the more evenly distributed nodes in the hash ring.

But the problem is, in reality we don’t have that many nodes. So at this point we add virtual nodes, which means making multiple copies of a real node.

Instead of mapping real nodes to hash rings, virtual nodes are mapped to hash rings and virtual nodes are mapped to real nodes, so there is a “two-tier” mapping.

For example, set three virtual nodes for each node:

  • Node A is numbered as virtual node A-01, A-02, and A-03
  • Nodes B are numbered as virtual nodes B-01, B-02, and B-03
  • Nodes C are numbered as virtual nodes c-01, C-02, and C-03

When virtual nodes are introduced, instead of only having three nodes in the hash ring, there are nine virtual nodes mapped to the hash ring, making the number of nodes in the hash ring three times larger.

As you can see, when you have a lot of nodes, the distribution of nodes is relatively uniform. At this point, if an access request is addressed to the virtual node “A-01”, then through the virtual node “A-01” to find the real node A, so that the request can access the real node A.

For your convenience, each real node contains only three virtual nodes, so the balancing effect is very limited. In actual projects, the number of virtual nodes will be much larger. For example, in Nginx’s consistent hash algorithm, each real node with a weight of 1 contains 160 virtual nodes.

In addition, virtual nodes not only improve node balance, but also improve system stability. When nodes change, different nodes share the changes of the system, so the stability is higher.

For example, when a node is removed, multiple virtual nodes of the corresponding node are removed. The next virtual node of these virtual nodes in the clockwise direction may correspond to different real nodes, that is, these real nodes share the pressure caused by node change.

In addition, with virtual nodes, the weight of nodes with better hardware configuration can be increased. For example, more VIRTUAL machine nodes can be added to nodes with higher weight.

Therefore, the consistent hashing method with virtual nodes is suitable not only for scenarios where the hardware configuration of nodes is different, but also for scenarios where the node size changes.

conclusion

Different load balancing algorithms apply to different service scenarios.

Strategies such as rotation training can only be applied to the scenario where the data of each node is the same, and data can be requested when visiting any node. This does not apply to distributed systems, because distributed systems mean that data is horizontally shred across different nodes. When accessing data, you must address the node where the data is stored.

Although the hash algorithm can establish the mapping relationship between data and nodes, every time the number of nodes changes, all data needs to be migrated in the worst case, which is too troublesome, so it is not suitable for the scene of the number of nodes changes.

In order to reduce the amount of data migrated, the consistent hashing algorithm appears.

Consistent hashing refers to the mapping of “storage nodes” and “data” to the same end to end hash ring. If a node is added or removed, only the node’s clockwise successor on the hash ring is affected, and other data is not affected.

However, the consistent hash algorithm cannot evenly distribute nodes, and a large number of requests are concentrated on one node. In this case, the cascading effect of disaster recovery and capacity expansion is easy to occur.

In order to solve the problem that the consistent hash algorithm cannot evenly distribute nodes, it is necessary to introduce virtual nodes and make multiple copies of a real node. Instead of mapping real nodes to hash rings, virtual nodes are mapped to hash rings and virtual nodes are mapped to real nodes, so there is a “two-tier” mapping.

The introduction of virtual nodes improves node balance and system stability. Therefore, the consistent hashing method with virtual nodes is suitable not only for scenarios where the hardware configuration of nodes is different, but also for scenarios where the node size changes.

Click to follow, the first time to learn about Huawei cloud fresh technology ~