What is the consistent HASH algorithm?

What is the consistent HASH algorithm?

The consistent HASH algorithm is a special HASH algorithm. The purpose is to solve the problem of distributed caching. When removing or adding a server, the existing service can be changed as little as possible. Mapping relationship between requests and servers handling the requests.

Hash algorithm adaptation conditions

Balance

Balance means that the hash result can be distributed to all buffers as much as possible , so that all buffer space can be utilized. Many hashing algorithms can satisfy this condition.

Monotonicity(Monotonicity)

Monotonicity means that if some content has been distributed to the corresponding buffer through hashing, and a new buffer is added to the system, then the hash The result should be able to ensure that the original allocated content can be mapped to the new buffer and will not be mapped to other buffers in the old buffer set. (This translation information has a negative value. Consistent hashing tries to protect the allocated content from being remapped to the new buffer when the buffer size changes.)

Dispersion( Spread)

In a distributed environment, the terminal may not see all the buffers, but only a part of them. When a terminal hopes to map content to a buffer through the hashing process, the buffer range seen by different terminals may be different, resulting in inconsistent hash results. The final result is that the same content is mapped to different buffers by different terminals. in the buffer. This situation should obviously be avoided, because it causes the same content to be stored in different buffers, reducing the efficiency of system storage. Dispersion is defined as the severity of the above occurrences. A good hash algorithm should be able to avoid inconsistencies as much as possible, that is, reduce dispersion as much as possible.

Load

The load problem is actually looking at the dispersion problem from another angle. Since different terminals may map the same content to different buffers, a specific buffer may also be mapped to different content by different users. Like dispersion, this situation should be avoided, so a good hashing algorithm should minimize the load on the buffer.

Recommended tutorial: "PHP Tutorial"

The above is the detailed content of What is the consistent HASH algorithm?. For more information, please follow other related articles on the PHP Chinese website!