[concurrent programming] consistency hash

        Considering that every node of the distributed system may fail , And new nodes are likely to be added dynamically , How to ensure that the system can still provide good services when the number of nodes changes , It's worth considering , Especially when designing distributed cache system , If a server fails , For the whole system, if we do not use the appropriate algorithm to ensure the consistency , Then all data cached in the system may fail （ That is, because the number of system nodes becomes smaller , The client needs to recalculate an object when requesting it hash value （ Usually related to the number of nodes in the system ）, because hash The value has changed , So it's very likely that the server node where the object is stored... Can't be found ）, So consistency hash It's very important , Well distributed cahce Consistency in the system hash The algorithm should satisfy the following aspects ：

• Balance (Balance)

        Balance means that hash results can be distributed to all buffers as much as possible , This allows all buffer space to be used . Many hash algorithms can satisfy this condition .

• monotonicity (Monotonicity)

        Monotonicity means that if something has already been hashed into the corresponding buffer , There are new buffers added to the system , Then the hash result should be able to ensure that the original allocated content can be mapped to the new buffer , Instead of being mapped to other buffers in the old buffer collection . Simple hash algorithm often can not meet the monotonicity requirements , Like the simplest linear hash ：x = (ax + b) mod (P), In the upper form ,P Indicates the size of all buffers . It's not hard to see. , When the buffer size changes ( from P1 To P2), All the original hash results will change , Thus, it does not meet the requirement of monotonicity . The change in hash results means that when the buffer space changes , All mapping relationships need to be updated in the system . And in the P2P In the system , Changes in buffering are equivalent to Peer Join or exit the system , The situation is P2P It happens frequently in the system , Therefore, it will bring great calculation and transmission load . Monotonicity is that hash algorithm can deal with this situation .

• Dispersion (Spread)

        In a distributed environment , The terminal may not see all the buffers , But only part of it . When the terminal wants to map the content to the buffer through the hash process , Because different terminals may see different buffer ranges , This leads to inconsistent hash results , The end result is that the same content is mapped to different buffers by different terminals . This situation should be avoided , Because it causes the same content to be stored in different buffers , Reduce the efficiency of system storage . Dispersion is defined as the severity of the above . A good hash algorithm should be able to avoid inconsistencies as much as possible , That is to minimize the dispersion .

• load (Load)

        The load problem is actually looking at decentralization from another perspective . Since different terminals may map the same content to different buffers , So for a particular buffer , It can also be mapped to different content by different users . It's the same as dispersion , This situation should also be avoided , So a good hash algorithm should be able to reduce the load of buffer as much as possible .

• Smoothness (Smoothness)

        Smoothness refers to the consistency between the number of cache servers and the number of cache objects .