Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to understand consistency hash". The content of the explanation is simple and clear, and it is easy to learn and understand. let's follow the editor's train of thought to study and learn "how to understand consistency hash".

1st Skill: hash algorithm

Grouping

Han Xin's 1st Skill hash algorithm: take the soldier's serial number num value as a hash value, and then always count the group N to do the remainder operation, the result is between 0 and N-1, the soldier belongs to that group.

As shown in the figure below, each soldier has a six-digit hash value (also known as a number), which is then divided into three groups by Korean Credit. For example, the soldiers numbered 123456 in the first group are divided by 3, and the remainder is 0, so they are assigned to the first group.

Hash algorithm

Look for soldiers.

Now that we have divided into groups, how to find the soldier numbered 666666 if we want to find it? First divide 666666 by 3 to get the remainder 0, which means that it is in the first group, and then go to the first group to find it.

Some friends here may ask, why not put all the soldiers in one group?

Because a group is too large, it affects the speed of the march. Mapping to the Internet architecture is to reduce the load pressure on a single node by increasing the number of nodes.

Hash grouping malpractice

After seeing this 1st Skill, Liu Bang shouted:

General Han is really good.

The hash algorithm looks perfect, so what if I give you another 500 soldiers and you need to be divided into four groups?

At this time, Han Xin's deputy general spoke:

It's not easy. Wouldn't it be all right to use 4 more to take the rest?

After touching his chin and thinking for a moment, Liu Bang said to the vice general:

This plan works, but many soldiers are regrouped and newly established team friendships are broken down.

Let's see why Liu Bang thinks the plan is not feasible.

For example, the soldiers with the number 3 originally assigned to a group, when divided into four groups, are calculated by the formula: 3% 43.Therefore, they will be assigned to the fourth group.

And so on, you will find that many soldiers have been reassigned, and only a small number of them will not change the grouping, for example, 1pd2 and 12 will not be reassigned.

Han Xin nodded to Liu Bang and said to the master:

My lord, you are right. This is the weakness of my 1st Skill.

But I have another skill: consistent hash.

2nd Skill: consistent hash hash ring

The consistent hashing algorithm also uses modular operations, but it is different from the hashing algorithm:

Hash algorithm: modular operation is performed on the number of nodes.

Consistent hashing algorithm: modular operation is performed on 2 ^ 32.

You can imagine that the consistent hash algorithm makes the entire hash space into a virtual circle, that is, the hash ring.

As shown in the following figure, map three groups to a hash ring with a fixed size of 2 ^ 32. The three groups divided the whole ring into three regions, CmurA (first group), Amurb (second group) and Bmurc (third group). As shown in the following figure:

Divide into three groups

The first group is responsible for storing the data that falls within the Cmura interval.

The second group is responsible for storing the data in the Amurb interval.

The third group is responsible for storing the data that fall within the BMY C range.

Soldier assignment

Suppose the soldier number 9527, after hashing, falls into the Cmura area. As shown in the following figure:

The position where the soldier stood

The second step is to ask the soldier to move forward clockwise, and the first node A he encounters is his group. As shown in the following figure:

Encounter the first node clockwise

Increase grouping

At present, when there are three nodes, it is assumed that the soldier number 89757 is assigned to the BMY C area (the third group) after hashing, that is, it belongs to the C node control. As shown in the following figure:

Belong to C node

Back to the question just asked by Liu Bang, if the group is divided into four groups, how to allocate soldiers.

As shown in the following figure, by adding a node D, the original area BMY C becomes the area BMY D (group 3) and DMel C (group 4).

Add D node

So which node does this soldier belong to? As shown in the following figure, the soldier walks forward clockwise, first to the D node, so it belongs to the D node control. Although still in the third group, the soldier's leader has changed: from C to D.

The leader has changed.

Judging from the above changes, only part of the data in the BMY C area will be migrated: the data between BMY D will be migrated from the C node to the D node.

Other data is not affected and does not need to be migrated. And the more nodes you have, the less data you need to migrate. This is the more the better.

After watching it, Liu Bang praised Han Xin:

Thanks to the general, Xiao he chased you under the moon, it was worth it!

Hash ring defect

After seeing the hash ring painted by Han Xin, Xiao he felt that something was wrong. After thinking for a moment, he said to Han Xin:

General, the nodes on your hash ring are not evenly distributed. You see, the areas of the third and fourth groups are so small.

Xiao he is right that this problem does exist. When it comes to the Internet architecture, there are the following problems:

The distribution of nodes is uneven, which leads to the uneven access of business to nodes.

Han Xin's eyes are full of admiration, and he who knows me is like Xiao he. Then he said with confidence:

You're right, but I have another skill, virtual node mapping.

3rd Skill: virtual node

Generally, there are more virtual nodes than physical nodes, and they are relatively evenly distributed on the hash ring. As shown in the following figure, 12 virtual nodes N1~N12 are relatively evenly distributed on the virtual nodes. If a soldier belongs to one of the N2/N3/N4, it will be remapped to node A, and so on, N5/N6/N7 belongs to the virtual node mapping of node B.

Virtual node

Let's take a look at the question raised by Xiao he, the real Bmurd region is relatively small, after using virtual nodes, N5/N6/N7 belongs to B node, N8/N9/N10 belongs to D node, they get the same number of virtual nodes, and the area is roughly the same. Therefore, the distribution of soldiers is more uniform.

Thank you for your reading. the above is the content of "how to understand consistent hash". After the study of this article, I believe you have a deeper understanding of how to understand consistent hash. the specific usage still needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.