最近看到了Redis Cluster，里面使用到了Hash slot来保证动态增加减少Redis 实例所带来的缓存失效问题，那今天就记录一下Hash slot相关的知识。
简单的Hash（余数算法）会带来什么问题？
我们现在有这么一个hash函数MyHash：
func MyHash1(n int) int {return (n % 3) + 1 // 3代表盒子的个数}复制
现在我们有3个盒子，盒子的编号分别为1,2,3：
然后我们有5个红球，编号分别为1,2,3,4,5：
我们分别将球的编号作为参数传给上面的函数，得到的返回值就是球要放入的盒子的编号，那我们最终将球放入盒子后的结果就是这样的：
MyHash1(1) = (1 % 3) + 1 = 2 所以1号球应该放入2号盒子MyHash1(2) = (2 % 3) + 1 = 3 所以2号球应该放入3号盒子MyHash1(3) = (3 % 3) + 1 = 1 所以3号球应该放入1号盒子MyHash1(4) = (4 % 3) + 1 = 2 所以4号球应该放入2号盒子MyHash1(5) = (5 % 3) + 1 = 3 所以5号球应该放入3号盒子复制
现在我们增加一个盒子，那么我们的hash函数就需要修改为：
func MyHash2(n int) int {return (n % 4) + 1 // 4代表盒子的个数}复制
现在我们用MyHash2计算出球应该属于的盒子，然后到对应的盒子中找球：
假如我要找编号为2的球的盒子：MyHash(4) = (4 % 4) + 1 = 1 到1号盒子里面找4号球这时你会惊奇的发现，4号球根本不在1号盒子里。。。。复制
这时假如我们把红球比作缓存的话，那么就出现了缓存失效的问题了。
一致性Hash算法？
一致性Hash在一定程度上解决了上面简单的hash会出现的缓存失效问题。那它是怎么解决的呢？为什么又说是一定程度上解决呢？接下来我们来分析一下一致性Hash。
一致性Hash 是一个环，环上有2^32-1个点，你看这点，你根本数不过来。。。我们还拿刚刚那个例子来进行画图说明，不过这次要引入一个带洞洞的呼啦圈了（没有画出2^32次方个洞洞哈，太难画了😅）：
接着我们需要重新写一个MyHash3方法，用来做后面的Hash函数：
// 这里我是这么写MyHash3方法的func MyHash3(boxName string) uint32 {// 我们用到一个crc32的方法计算一个字符串的整数值return crc32.ChecksumIEEE([]byte(boxName)) & ((1 << 32) - 1)}复制
然后我们将上面的3个盒子使用MyHash3计算出3个编号，根据编号将盒子先对应到呼啦圈的洞洞上面去，假设对应完了之后如图所示：
好，盒子就这样被挂到了呼啦圈上，接着我们看5个红球是如何放到盒子里面的：
首先我们还是使用MyHash3方法对球的编号进行Hash运算，得到一个呼啦圈上的位置
然后沿着呼啦圈进行顺时针旋转，将刚刚得到的球在呼啦圈上对应的位置移动到离它最近的一个盒子的位置
将球放入刚刚找到的盒子里面
重复上面的步骤，就可以将球都放入到对应的盒子中了，假设最后的情况如图所示：
找对应的球的时候，我们也是通过同样的方式来进行寻找就行了。比如，我们要找1号球在哪里，我们就可以通过MyHash3("球3")找到环上的一个编号，然后顺时针方向，找到2号盒子，在里面就能取到3号红球了。
接着我们看一下，如果我们加入一个新的盒子，盒子4，会发生什么情况，假如盒子4通过MyHash3("盒子4")，挂到了环上的这个位置，如图：
这时我们通过MyHash3("球1")，如果得到它的位置是在3号盒子和4号盒子之间，那么顺时针找盒子，就会找到4号盒子，然后到4号盒子里面拿球，会发现4号盒子里面没有1号球，这时就会出现简单Hash中的缓存失效问题。但是我们找2、3、4、5号球，依然不受影响，所以受影响的部分只有3号盒子和4号盒子之间的位置的球，这就是为什么说一致性Hash在一定程度上解决了缓存失效的问题。
Hash slot？
那么Hash slot又是个什么样的算法呢？Hash slot 是Redis cluster 使用的方案，它比一致性Hash要简单。
Hash slot 算法，首先预定了16384个槽[0-16383]，然后将这16384个槽进行分配，假设我们有三台Redis主节点，那么经过平分后，就会变成如图所示的结果：
node1负责[0-5460]的槽
node2负责[5461-10922]的槽
node3负责[10923-16383]的槽
然后采用CRC16(key) % 16384的Hash方法来确定数据应该缓存的槽，在根据槽找到对应的缓存node，然后将数据放到对应的node上面。
如果我们要增加一个node，那我们就需要从现有node中分一部分槽出来给新node，然后将对应的缓存数据也转移到新node上。如果要减少一个node，那就需要将这个node上的槽和槽对应的数据分配给留下的node上面。
推荐阅读：
1. Redis(版本4.0)日记20210801--简单动态字符串
2. Redis(版本4.0)日记20210730--数据类型和底层编码
