Shulou(Shulou.com)05/31 Report--

This article mainly explains "what is the principle of consistent hashing algorithm". Interested friends may wish to take a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what is the principle of consistent hashing algorithm"?

The hash algorithm maps a binary value of any length to a shorter fixed-length binary value, which is called a hash value. A hash is the only and extremely compact numerical representation of a piece of data. If you hash a plaintext and change even one letter of the paragraph, the subsequent hash will produce a different value. It is computationally impossible to find two different inputs that hash the same value, so the hash of the data can verify the integrity of the data. It is generally used for fast search and encryption algorithms. [1]]

It's a little difficult to understand, but it doesn't matter, use a simple hash algorithm to understand the above paragraph:

Int plusHash (String key, int cnt)

{

Int hash, i

For (hash = key.length (), I = 0; I

< key.length(); i++) hash += key.charAt(i); return (hash % cnt ); } 上面这段算法，通常称之为加法hash，输入：key=zhuganglie，cnt=23，输出：22 看看这段代码，基本上上面那段不太好理解的内容就相对容易一些了。 一致性哈希提出了在动态变化的Cache环境中，重点解决单调性的问题，单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 （请注意，以上是网上大多数技术文的说法，也不知道是来自于哪位大神的翻译，按照我的理解，所谓单调性应该指的是，当有新的缓冲区加入系统中的情况下，应该尽量保证原有已分配内容，不会被重新映射到新的缓冲区中去） 实际场景：现有n台服务器，构成一个服务器集群，现有算法是通过hash(obj) % n，来找到某一个请求对应的服务器，如果某一台服务器宕机了，就变成了 hash(obj) % n-1 ，显而易见，这时候会发生大量的访问错误，如果避免这种情况。 所谓一致性哈希，一致性究竟体现在什么地方，假设我们目前有4个对象和4个cache server，对这8个对象，采用统一的hash值空间，假定为1024。将此1024个值空间，想象成为一个环形结构。而4个对象和4个cache server，分别落在这1024个值当中的不同位置。

As shown in the figure above, the torus is a value space of 1024. We put the four server and obj1~obj4 objects of s1~s4 into this value space, and then find the cache server for each obj in a clockwise direction.

The corresponding result is obj1~s2,obj2~s3,obj3~s4,obj4~s1.

Consider several situations:

1. Remove: S3 failed, the image above looks like this, and the new correspondence looks like this:

Obj1~s2,obj2~s4,obj3~s4,obj4~s1 . We see that only the mapping of obj2 has changed.

2. Add: add a new S5, and the new structure is shown below. In this case, the mapping relationship will not even change. If there is an obj between S3 and S5, only this part of the obj mapping relationship has changed.

As we can see here, there is a good solution to the monotonous problem.

In the next step, we also need to solve the problem of data skew. We have five real servers above, and then we further extreme the situation. We only have two real servers. We cannot guarantee that the hash values of all data objects are evenly distributed on the ring, so there will be the problem of data skew. In order to solve this problem, we also need another concept, virtual node.

First of all, there is a picture with only two real servers, and we can see that the data tilt is quite serious.

Then we remove two real servers from the ring structure and replace them with eight virtual servers, which alternately belong to two real servers. In this way, the problem of data skew has been greatly alleviated.

At this point, I believe you have a deeper understanding of "what is the principle of consistent hashing algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.