redis(七)：redis分布式算法

1.传统分布式算法

假设有4个redis节点，分别是redis0，redis1，redis2，redis3；有20个数据，这20个数据需要尽可能均匀地存储在这4个redis节点上。传统的做法是：将这20个数据（key）进行hash运算（如果是string类型，可以直接哈希。如果是文件，可以对唯一的文件名进行哈希），hash后的值和4（节点数量）进行取余运算，算出来是什么结果就落在哪个节点上。比如经过hash取余运算后结果为0，就存储在redis0节点；结果为1，存储在redis1节点；结果为2，存储在redis2节点，以此类推......

读取数据的时候，根据数据（key）进行hash运算，然后和节点数进行取余，就能得出数据存储在哪个节点了，进而读出数据。

这种算法能够使各个redis节点比较均匀地分担压力，和HashMap和类似。

不过这种算法有很致命的弱点。

如果增加redis节点或者删除redis节点（这种情形很常见），因为节点数量改变了，所以会导致数据（key）进行hash后和节点数取余的结果发生改变，不能定位到之前的redis节点，无法从缓存中读取数据，这时就会直接从DB中读取，会造成redis穿透，甚至系统奔溃。

一般在redis节点改变的时候，会在极短的时间内将缓存中的数据在redis节点之间进行重分配。比如之前存储在redis1节点的data5需要移动到redis0节点，之前存储在redis2节点的data6移动到redis1节点。数据量越大，这种算法导致移动的数据就会越多，所花费的时间也会越长（如果在重分配的这段时间内，如果访问数据，缓存是失效的，需要从DB中读取，所以时间越短越好）。

数据命中：即节点数量改变后不受影响的数据（少部分数据在节点数量改变前和改变后key的hash值取余后，值没发生变化）。

这种算法数据命中率很低。

2.Consistent Hashing

Consistent Hashing称之为一致性hash算法。

redis分布式算法，最常用的就是一致性算法。Consistent Hashing的核心是环形hash空间

2.1环形hash空间

传统的redis算法，只是对数据进行hash运算，而在环形hash空间中，对节点也进行hash运算（对节点的ip，port这些唯一性信息进行hash运算）。

环形hash空间是一个首尾相连的数据结构，取值从0~2^32-1，大量的数据和少量的redis节点进行hash运算后都会落在这个环上。每个数据顺时针寻找，总会找到一个离它最近的redis节点，这个数据就存储到离它最近的redis节点中。

查找数据，也是根据数据（key）的hash值和redis节点hash值在圆环中进行比较，找顺时针最近的节点。

原理如下图：

上图共有三个redis节点，根据hash后的值进行顺时针查找，redis1节点存储d1，redis2节点存储d2，redis3节点存储d3。

数据比较均匀地存储在了各个redis节点中。

优势：redis节点增加或删除时，只会影响hash环中离它最近的数据，其他数据不受影响，这些数据缓存依然有效。避免了redis穿透以及大规模的数据重分配，数据的命中率很高。

有些文章说Consistent Hashing对数据（key）和redis节点hash后，和2^32-1进行取余运算进而确定在环中的位置。我觉得这种意义不大，毕竟大于2^32-1的hashcode很少（视具体算法），取余后的值仍然是hashcode本身。

2.2.hash倾斜性

redis节点（节点ip）进行hash运算后落在hash环上时，不能保证100%的均匀性，因为节点数量一般都很少（和2^32相比），因此节点hash后落在环上时，很有可能几个节点之间的距离很近，那么数据落在这两个节点之间的可能性就越小。因为是环形结构，几个节点之间的距离很小，就必然存在几个距离很大的节点，那么大部分的数据会落在距离大的节点区间中，如下图：

3个redis节点，5个数据。这三个节点在hash环中离得特别近。顺时针查找，d2,d3,d4,d5都落在了redis1节点中，d1落在了redis3中，reids2一个数据都没有。

这种情况和分布式的初衷是相违背的，各个节点之间并没有比较均匀地分配压力。

对于hash倾斜性，Consistent Hashing引入了虚拟节点的概念，大量的虚拟节点hash后会相对均匀地分布在hash环上（数量越多，就越均匀一些）。数据（key）hash后不是直接查找redis节点的hash，而是虚拟节点的hash。这样，数据（key）就和虚拟节点建立映射关系，虚拟节点经过一系列的hash运算后，指向真实的redis节点，这样各个redis节点尽可能均匀地存储数据。

参考博客：http://www.zsythink.net/archives/1182/

感谢作者！