一致性hash

一致性hash思想

一般的hash算法对资源做缓存，出现扩容或者缩小容量时，需要对所有资源hash重新计算存储位置，导致缓存失效。
一致性hash通过将hash区间[0,Ineteger.MAX_VALUE](即0~(2^32)-1)通过存储位置划分为不同的区间，将区间的hash值按照顺时针转动找到存储位置。当出现增加存储节点或者删除存储节点时，受影响部分只有删除或者增加的区间。

一致性hash算法

假设hash值区间是[0, 50000]，有4个存储节点key1~key4，hash(key1)=10000...

如图所示：
Key1存储hash值为(40000,50000]和(0,10000]的资源
Key2存储hash值为(10000,20000]的资源
Key3存储hash值为(20000,30000]的资源
Key4存储hash值为(30000,40000]的资源
当增加节点key5时，
Key1存储hash值为(40000,50000]和(0,10000]的资源
Key5存储hash值为(10000,15000]的资源
Key2存储hash值为(15000,20000]的资源
Key3存储hash值为(20000,30000]的资源
Key4存储hash值为(30000,40000]的资源
受影响的只有key2。反过来，删除key5，受影响也只有key2

平衡性

key1~key4如果删除其中key1和key2，key1和key2的全部资源都放到key3，出现这样情况导致大部分数据都存在key3，只有(30000,40000]的资源存在key4，导致失衡。
将节点虚拟化几个节点，环绕在整个环上

如图所示，如果删除节点key1和key2
Key4存储hash值为(30000,40000]的资源
Key4-1存储hash值为(40000,50000]和(0,15000]的资源
Key3-1存储hash值为(15000,25000]的资源
Key3存储hash值为(25000,30000]的资源
相对上一张图删除key1和key2影响小很多，虚拟节点还可以继续增加，环绕环形上更多，更加平衡。

优点很明显，更多虚拟节点更加平衡；相对来说缺点，每删除一个节点，受影响的节点也更多。

参考

[1] https://zh.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C
[2] https://blog.csdn.net/cywosp/article/details/23397179
[3] https://www.cnblogs.com/xrq730/p/5186728.html