Hanxin's trick: consistent hashing

This is Wukong's first  78  Original articles

author | Wukong chat structure

source |  Wukong chat structure （ID：PassJava666）

Please contact authorization for reprint （ WeChat ID：PassJava）

Han Xin's idiom of ordering soldiers comes from Huai'an folklore . Often with the more the better . The more the moral, the better . Let's take a look at the dialogue between lord Liu Bang and General Han Xin .

Liu bang ：“ How much do you think I can lead ？”

Han xin ：“ Up to 100000 .”

Liu bang Puzzling questions ：“ How about you ？”

Han xin Proudly say ：“ The more the better , More is better ！

If Liu Bang gave Han Xin a thousand soldiers now , It needs to be roughly evenly divided into three groups . The soldier's number is six digits , from 1-100000 Random allocation . For example, the value of the first soldier is 245, The number of the second soldier is 82593, Other soldiers are similar . So how to distribute the soldiers ？

Liu bang ： General Han , You see how these soldiers are distributed ？

Han xin ： It's not easy , my A skill You can get .

A skill ： The hash algorithm

grouping

One of Hanxin's skills The hash algorithm ： Put the soldier's number num Make a hash value , And then do the number of groups with the total N Do the surplus operation , The result is 0 To N - 1 Between , This soldier belongs to that group .

As shown in the figure below , Every soldier has a six man hash value （ It can also be called a number ）, Then Han Xin divided it by 3 The remainder is assigned to three groups . For example, the number in the first group is 123456 Our soldiers , Divide 3 after , to be divisible by , Remainder is 0, So it's assigned to the first group .

The hash algorithm

Find the soldiers

Now it's divided into groups , If you want to find the number 666666 How do you find your soldiers ？ First of all, will 666666 Divide 3, Get the remainder 0, Explain in the first group , Then go to the first group to find it .

Here are some friends who may ask , Why not put all the soldiers in one group ？

Because a group is too big , Affect the speed of March . Mapping to the Internet Architecture , It is to reduce the load pressure of single node by increasing nodes .

The disadvantages of hash grouping

After Liu Bang saw this skill , shout loudly ：

General Han is really powerful .

The hash algorithm looks perfect , Then I'll give you another 500 soldiers , It needs to be divided into four groups ？

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

It's not easy , Reuse 4 I'll take the rest ？

Liu Bang felt his chin and thought for a moment , To the deputy general ：

This plan is feasible , But a lot of soldiers have been regrouped , The team friendship just established is broken down .

Let's take a look at why Liu Bang thinks the plan is not feasible .

For example, the number originally assigned to a group is 3 Our soldiers , When divided into four groups , Calculate by formula ：3%4=3, So it's going to be assigned to group four .

By analogy , You'll find a lot of soldiers reassigned , Only a small number don't transform the grouping , such as 1,2,12 It won't be regrouped .

Han Xin nodded to Liu Bang , Said to the Lord ：

Lord , You are right , This is one of my skills weaknesses Where .

But I have another skill ： Consistent Hashing .

2. Skills ： Consistent Hashing

Hash loop

The consistent hashing algorithm also uses modular operations , But it's different from hashing ：

• The hash algorithm ： Modulo the number of nodes .

• Consistent hash algorithm ： Yes 2^32 To perform modular operations .

You can imagine , Consistent hash algorithm , It is a virtual circle formed by the whole hash value space , That is to say Hash loop .

Here's the picture , hold 3 Groups are mapped to a fixed size of 2^32 In the hash ring of . The three groups divide the whole ring into three regions ,C-A（ The first group ）、A-B（ The second group ）、B-C（ The third group ）. As shown in the figure below ：

Divide into three groups

• The first group is responsible for the storage of C-A Data in the interval .

• The second group is responsible for the storage of A-B Data in the interval .

• The third group is responsible for the storage of B-C Data in the interval .

The soldiers were assigned

Suppose the number is 9527 Our soldiers , After hashing , Fall on C-A Area . As shown in the figure below ：

Where the soldiers stand

The second step , Let the soldier go clockwise , The first node encountered A That's his group . As shown in the figure below :

The first node is encountered clockwise

Add groups

At present, when there are three nodes , Suppose the number is 89757 After hashing the soldiers , Assigned to B-C Area （ The third group ）, It belongs to C Node control . As shown in the figure below ：

Belong to C node

Back to the question Liu banggang asked , If the group becomes four , How to allocate soldiers .

As shown in the figure below , Add a node D, The original area B-C It became a region B-D（ The third group ） and D-C（ Group 4 ）.

increase D node

So which node does this soldier belong to ？ As shown in the figure below , The soldier walked forward clockwise , Go ahead to D node , So it belongs to D Node control . Although still in the third group , But the leader of this soldier has changed ： from C Turned into D.

The leader has changed

From the changes above , Only B-C Part of the data in the region will be migrated ：B-D Data between will be generated by C node transfer To D node .

and Other data is not affected , There's no need to migrate . And the more nodes , The less data needs to be migrated . That's the more the better ~

After Liu Bang saw it , Praise Han Xin ：

I'm a great general , Xiao He was chasing you under the moon , The value of ！

Hash ring defect

After Xiao he saw the hash ring painted by Han Xin , I think something's wrong , After thinking for a moment , To Han Xin ：

The general , The distribution of nodes in your hash ring It's not even ah , You see, the area of group 3 and group 4 is so small .

Xiao He is right , There is a problem , Put it in the Internet Architecture , There are the following problems ：

The nodes are unevenly distributed , This leads to the uneven access of services to nodes .

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

You're right , But I have another skill , Virtual node mapping .

Three skills ： Virtual node

Generally, there are more virtual nodes than physical nodes , And relatively evenly distributed on the hash ring . As shown in the figure below ,12 Virtual nodes N1~N12, Relatively evenly distributed on virtual nodes . If a soldier belongs to N2/N3/N4 One of them , Will be re mapped to A node , By analogy ,N5/N6/N7 Belong to B Virtual node mapping of nodes .

Virtual node

Let's take a look at the question raised by Xiao He , Actual B-D The area is relatively small , After using the virtual node ,N5/N6/N7 Belong to B node ,N8/N9/N10 Belong to D node , They get the same number of virtual nodes , And the regions are roughly equal . So the distribution of soldiers is relatively even .

After Xiao he saw Han Xin's three skills , Direct call ： Wonderful zai zai ！

summary

This article through the story of Han Xin's ordering soldiers , Then Liu Bang is derived from the story 、 Han xin 、 Xiao He's dialogue , Let's talk about the grouping of soldiers . Now let's make a summary of the knowledge points in the story ：

• Hash algorithm will bring about the problem of adding or deleting nodes , Data migration The problem of too much .

• Consistent hash algorithm Reduce It reduces the amount of data migration .

• Fewer nodes , Each node in the hash ring actually occupies an interval of different sizes , Finally, it leads to the access of business to nodes The heat and cold are uneven .

• introduce Virtual node mapping It solves the problem of uneven distribution .

• node The more when , Use hash When the algorithm , The data that needs to be migrated is The more , And using consistent hashing , The migrated data is The less .

• Consistent hashing is essentially a Routing addressing Algorithm , Suitable for simple routing scenarios .

• Consistent hash algorithm is often used in load balancing architecture design .

The cover image comes from the glory of the king .

- END -

Previous recommendation

Four ： Use dynamic diagrams to explain distributed Raft

3、 ... and ： Zhugeliang VS Pang Tong , Take the distributed Paxos

Two ： Use Taijiquan to teach distributed theory , It is really comfortable ！

One ： Talk about distributed algorithms in Three Kingdoms , Comfortable, right ？‍

Author's brief introduction ：8 Years of Internet experience , Good at architecture design 、 Distributed 、 Microservices . Written a set SpringCloud Practical course , Self developed PMP Brush topic small program and Java Brush topic small program . reply pdf receive .

I'm Wukong , Try to be strong , Become a super Saiya ！

This article is from WeChat official account. - Wukong chat structure （PassJava666）.
If there is any infringement , Please contact the [email protected] Delete .
Participation of this paper “OSC Source creation plan ”, You are welcome to join us , share .