说说分布式缓存一致性hash算法 ？

分析&回答

Hash 算法评估

• Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
• Hash 算法的另一个指标是平衡性 (Balance)，定义如下：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

consistent hashing （一致性hash）算法的原理

一致性hash算法通过构造一个长度为2^{32的整数环（首 0 、尾 2}32-1 相接的圆环），根据节点名的hash值将缓存服务器节点放置在这个环上，然后计算要缓存的数据的key的hash值，顺时针找到最近的服务器节点，将数据放到该服务器上。

有Node0,Node1,Node2三个节点，假设Node0的hash值是1024,key1的hash值是500，key1在环上顺时针查找，最近的节点就是Node0。

当服务器集群又开始扩容，新增了Node3节点，从三个节点扩容到了四个节点。

 
 Node3加到了Node2和Node1之间，除了Node2到Node3之间原本是Node1的数据无法再命中，其它的数据不受影响，3台扩容到4台可命中率高达75%，

而且集群越大，影响越小，100台服务器增加一台，命中率可达到99%。

查找不小于查找树的最小值是用的二叉查找树实现的。

但是这样子还是会存在一个问题，就是负载不均衡的问题，当Node3加到Node2和Node1之间时，原本会访问Node1的缓存数据有50%的概率会缓存到Node3上了，这样Node0和Node2的负载会是Node1和Node3的两倍。

要解决一致性hash算法带来的负载不均衡（平衡性）问题，可通过将每台物理服务器虚拟成一组虚拟缓存服务器，将虚拟服务器的hash值放置在hash环上，KEY在环上先找到虚拟服务器节点，然后再映射到实际的服务器上。

这样在Node0,1,2虚拟节点都已存在的情况下，将Node3的多个虚拟节点分散到它们中间，多个虚拟的Node3节点会影响到其它的多个虚拟节点，而不是只影响其中一个，这样将命中率不会有变化，但是负载却更加均衡了而且虚拟节点越多越均衡。

反思&扩展

一致性哈希基本成为了分布式系统组件的标准配置，例如Redis的各种客户端都提供内置的一致性哈希支持。