一致性哈希算法

一致性哈希算法主要应用于Redis分布式缓存

问题引出

在单节点的情况下，Redis缓存不用担心命中率的问题，但是一旦上升到分布式的架构中，可能会造成一台机器有缓存而另一台机器没有缓存的情况，基于此使用一致性Hash算法可以有效地解决在分布式存储结构下动态增加和删除节点后尽量有多的请求命中原来的服务器节点。

解决问题

哈希算法

场景描述：假设有3个redis节点用于存储数据，这3台Redis节点的编号是0，1，2。如果希望将数据均匀的存储在这3个节点上，可以采用对数据的key进行Hash计算，将Hash计算后的结果对redis节点的数量进行取模运行，通过取模后的结果，决定将数据存在哪一个Redis节点上。hash（key）% N

当下次访问这个数据时，只需要再次对数据的key进行Hash计算，即可得出数据在哪个redis上，然后从对应的redis节点上获取数据。

存在的问题：当增加redis节点或者当部分redis节点挂掉后，再进行hash计算然后对节点的数量取模时，就无法找到对应的数据，造成大量的缓存同时失效。

为了能够尽量使得Redis宕机的情况下缓存命中率损耗最小

一致性哈希!

一致性Hash算法是对232取模。 Hash（服务器的IP地址）% 232 (余数：0~232-1），将232个数想象成由（0~232-1）共232个点组成的圆环，把这个圆环称为Hash环。

当存储数据的时候，对数据的key进行相同的哈希算法，将数据映射到哈希环上

如图有三台服务器，三台服务器A，B，C上分别缓存了数据a，b，c，即使这时结点B宕机了，对于缓存数据b也会存储到服务器A上而不用像哈希算法那样再哈希导致缓存失效。

如果使用之前的hash算法对服务器的数量取模，那么当服务器的数量发生改变时，就会找不到数据，所有的缓存将会同时时间失效。而使用一致性Hash算法，服务器数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存会失效。

一致性哈希的问题

以上都是理想状态下，服务器的分布很散列但是由于哈希算法设计的很简单无法保证数据散列，所以再绝大多数情况下，这三台服务器在哈希环上的映射很接近，更接近于图中的这种情况，大量的缓存存储在一台服务器上

Hash环的偏斜问题

假设在理想的情况下，3台服务器将会均匀的映射在Hash环上，但是现实可能是3台服务器在Hash环上的映射的位置挨的比较近。那么，将会有很多数据被存储在某一台服务器上。这样，其它服务器并没有得到平均的充分的利用。如果此时，那个节点出现故障，造成的损失也是最大的。

解决方法

使用虚拟节点，虚拟节点是实际节点在Hash环上的一个复制品，一个实例节点可以对应多个虚拟节点。引入虚拟节点后，节点在Hash环上的分布就变得均衡了。虚拟节点越多，Hash环上的节点就越多，数据被均匀分布的概率就越大。