前言
分布式缓存常见的寻址算法如下：
- hash算法
- 一致性hash
- hash slot
其中redis使用hash slot方法进行寻址，也就是大名鼎鼎的槽位定算法，本文逐一介绍各算法的实现，并重点刨析redis使用的hash slot算法
hash算法
这个是简单的，和hashmap原理类似，都是通key进行hash运算后取模计算具体该存入集群中哪个节点
比如目前有三个节点，通过hashcode % 3运算就可以得到0，1，2范围内的一个数，就可以定位这个数据存入哪个节点了
image.png
但hash算法一个非常不好的弊端是不利于扩展，比如新增一个节点，所有的key存放位置都要重新计算，因此没增加一个节点就涉及到所有节点的数据迁移，非常麻烦
一致性hash
这是一个经典的寻址算法，它的出现就是为了解决普通hash算法扩展节点造成数据大面积迁移的弊端，但也想对复杂
它的算法是这样的，生成一个n个位置的圆环，其中n的数量一般远大于实际集群节点数量，可以把每个位置叫做一个槽位，每个节点对n取模计算出一个所在槽位，同理每个key也对n取模计算一个槽位，如下
image.png
图上，key2运算后与节点3结果一致，自然存储到节点3上，但key1算出的槽位上并无节点对应怎么办？此时就会顺时针查找第一个有节点绑定的槽位，因此最终存储在了节点1上
这么做这么复杂有什么好处？如上述所说是为了避免大范围的数据迁移，此时我们再新增一个节点试一下
image.png
上图新增了节点4，此时数据如何迁移？按顺时针的规则，原本槽位4，5，6，7都要存到节点1上，现在的变化是槽位4，5存到节点4上，槽位6，7依然存在节点1上，其它节点不用变，因此只需把节点1上的数据迁移一部分给节点4，扩展就实现了，比较完美解决了大面积的数据迁移
那么一致性hash算法有啥弊端不？回到第一张图三个节点，key取模结果为4，5，6，7的数据都存再了节点1，而只有8会存到节点2上，答案显然：不公平，节点1承受了太多而节点2承受的太少
但这个问题是可以解决的，解决的方案叫做：虚拟节点，即一个节点虚拟多个id通过hash取模可以得到多个位置，每个节点随机得次数大了，当然就尽量减少了不公平的出现，如下图
image.png
当然还要保证每个节点所占的位置不能冲突， 这方法很多不细说
综上所属，一致性hash的解决方案近乎完美了，目前它的确定就只有一个：过于复杂
槽位定算法 Hash slot
Redis当然不会选择问题很明显的hash算法，但同时也没有使用过于复杂的一致性hash，而是一种折中方案即 Hash slot(基本上也属于一致性hash的概念，解决的思路也基本与一致性hash差不多)
它的解决方案是这样的，同样是息份远大于节点数量槽位(16,384个槽)，key依然通过取模获取槽位索引，同时每个集群节点会分配一部分的槽位(可以自动也可以手动)，这样通过key计算出槽位索引，就可以寻址到该存放的节点
image.png
就这样，摒弃了复杂的圆环，同时新增节点时也只需要匀一些槽位给新节点并迁移少部分数据即可
如果集群的拓扑发生变化（例如添加或删除节点），可以通过CLUSTER SETSLOT命令手动迁移槽到不同的节点。集群软件也会定期检查槽的分配情况，并在必要时自动触发数据重平衡
那么问题又来了，这个槽位信息谁来维护，又存储在哪里
槽位信息
简单来说，槽位信息每个redis实例都会有一份，并且集群中互相同步
同时客户端当然也要存一份，不然怎么知道去哪取，当然客户端获取过程一旦发现定位错了(已改变)就会尝试同步回来一个最新的槽位分布信息
网友评论