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

What is a consistent hash? In view of this problem, this article introduces the corresponding analysis and answers in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible way.

Consistent hash algorithm, proposed by MIT in 1997, is a special hash algorithm, which aims to solve the problem of distributed cache when removing or adding a server. the mapping between existing service requests and processing request servers can be changed as little as possible.

Consistent hash algorithm, which was proposed by MIT in 1997, is a special hash algorithm to solve the problem of distributed cache. When removing or adding a server, you can change the mapping between the existing service request and the processing request server as little as possible. Consistent hash solves the problem of dynamic scaling of simple hash algorithm in distributed hash table (Distributed Hash Table,DHT).

Brief introduction:

Consistent hashing algorithm was proposed in Consistenthashingandrandomtrees in 1997, and it is widely used in distributed systems. Consistent hash is a hash algorithm, which can change the mapping relationship between the existing service request and the processing request server as little as possible when removing or adding a server, so as to meet the requirements of monotonicity as much as possible. In an ordinary distributed cluster, there can be an one-to-one correspondence between the service request and the processing request server, that is to say, the mapping relationship between the fixed service request and the processing server, and a request is processed by a fixed server. This approach cannot load balance the entire system and may cause some servers to be too busy to process new requests. While other servers are too idle, the resource utilization of the overall system is low, and when a server in the distributed cluster goes down, it will directly lead to some service requests can not be processed.

Further improvement can use the hash algorithm to map the relationship between the service request and the processing server to achieve the purpose of dynamic allocation. The hash algorithm is used to transform the service request, and the converted result carries on the modular operation to the server node value, and the value after taking the module is the request processing server corresponding to the service request. This method can deal with node failure. When a distributed cluster node goes down, the service request can be redistributed to other available servers through the hash algorithm. The situation in which the request cannot be processed is avoided.

But the defect of this method is also obvious. if the data corresponding to the service request is stored in the server, then if the hash value of the request is recalculated, it will cause a large number of requests to be redirected to different servers and invalidate the data to be used by the request. this situation is very bad in distributed systems. A well-designed distributed system should have good monotonicity, that is, the addition and removal of servers will not cause a large number of hash relocations, and consistent hashes can solve this problem.

The consistent hash algorithm maps the whole hash space to a virtual ring, and the range of the whole hash space is 0: 232-1. The whole space is organized clockwise. Zero 232-1 coincides in the direction of zero. Next, use the following algorithm to map the service request, use the hash algorithm to calculate the corresponding hash value, and then look it up clockwise along the circle according to the location of the hash value. The first server encountered is the corresponding processing request server. When a new server is added, the data affected is only the data between the newly added server and the previous server in its ring space (that is, the first server encountered counterclockwise). Nothing else will be affected. To sum up, the consistent hashing algorithm only needs to relocate a small part of the data in the ring space for the increase or decrease of nodes, so it has good fault tolerance and scalability.

Features:

Scalability. The consistent hash algorithm ensures that the change of data storage is the least when adding or decreasing servers, and greatly saves the cost of data movement compared with the traditional hash algorithm.

Better adapt to the rapid growth of data. Using consistent hashing algorithm to distribute data, when the data is growing, some virtual nodes may contain a lot of data, resulting in uneven distribution of data on the virtual nodes. At this time, the virtual nodes containing a lot of data can be split. This split only divides the original virtual node into two, and there is no need to re-hash and partition all the data. After the virtual node is split, if the load of the physical server is still uneven, it is only necessary to adjust the storage distribution of some virtual nodes between the servers. In this way, the number of physical servers can be dynamically expanded as the data grows, and the cost is much less than the traditional hashing algorithm to redistribute all data.

This is the end of the answer to the consistent hash question. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.

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.