简介

一致性哈希用于解决分布式缓存系统中的数据选择节点存储问题和数据选择节点读取问题以及在增删节点后减少数据缓存的消失范畴，防止雪崩的发生。

哈希槽是在redis cluster集群方案中采用的，redis cluster集群没有采用一致性哈希方案，而是采用数据分片中的哈希槽来进行数据存储与读取的。

一致性哈希

一个0-2^32 的闭合圆，占用4个字节，所有节点存储的数据都是不一样的。计算一致性哈希是采用的是如下步骤：

• 对节点进行hash,通常使用其节点的ip或者是具有唯一标示的数据进行hash(ip),将其值分布在这个闭合圆上。
• 将存储的key进行hash(key),然后将其值要分布在这个闭合圆上。
• 从hash(key)在圆上映射的位置开始顺时针方向找到的一个节点即为存储key的节点。如果到圆上的0处都未找到节点，那么0位置后的顺时针方向的第一个节点就是key的存储节点。

添加节点带来的影响
图为一致性hash的分布情况，箭头指向key的分布情况。

如果现在node2和node4节点中间增加一个node5节点，那么在node4和node2之间的这些数据要存储的节点就会有所变化。在图中的黄色区域的数据将会从原来的node4节点挪到node5节点。

删除节点带来的影响
以图1为基准，删除了node2节点后，原本在node2节点上的数据就会被重新定位node4上。这样就产生一个影响：原来node2的数据转移到node4上，这样node4的内存使用率会骤增，如果node2上存在热点数据，node4会扛不住甚至会可能挂掉，挂掉之后数据又转移给node3,如此循环会造成所有节点崩溃，也就是所说的雪崩的情况。

节点太少造成的影响
节点太少的话可能造成数据倾斜的情况，如图中中只有俩节点，可能会造成大量数据存放在node A节点上，而node B节点存储很少的数据。

虚拟节点
为了解决雪崩现象和数据倾斜现象，提出了虚拟节点这个概念。就是将真实节点计算多个哈希形成多个虚拟节点并放置到哈希环上，定位算法不变，只是多了一步虚拟节点到真实节点映射的过程

以雪崩现象来说明:如下图节点real1节点又俩个虚拟节点v100和v101,real2有俩个虚拟节点v200和v201，real3节点有v300和v301俩个虚拟节点

当real1节点挂掉后，v100和v101节点也会随即消失，这时k1数据就会被分配到v301上，k4就会被分配到了v200上，这就解决了雪崩的问题，当某个节点宕机后，其数据并没有全部分配给某一个节点，而是被分到了多个节点（理想情况下）。
注意：

• 真实节点不放置到哈希环上，只有虚拟节点才会放上去。
• 为什么要使用闭合的哈希环?举个例子，如果在2^23-3 处有一个key,而2^23 -3~2^23 处并没有节点,那么这个key该存在哪里节点呢？
• 一致性哈希使用的32个bits，4个bytes，肯定也会有哈希碰撞的问题存在。

哈希槽

redis cluster采用数据分片的哈希槽来进行数据存储和数据的读取。redis cluster一共有2^14（16384）个槽，所有的master节点都会有一个槽区比如0～1000，槽数是可以迁移的。master节点的slave节点不分配槽，只拥有读权限。但是注意在代码中redis cluster执行读写操作的都是master节点，并不是读是从节点，写是主节点。

为什么是16384个槽？
在握手成功后，两个节点之间会定期发送ping/pong消息，交换数据信息，在redis节点发送心跳包时需要把所有的槽信息放到这个心跳包里，以便让节点知道当前集群信息，在发送心跳包时使用char进行bitmap压缩后是2k（16384÷8÷1024=2kb），也就是说使用2k的空间创建了16k的槽数。
虽然使用CRC16算法最多可以分配65535（2^16-1）个槽位，65535=65k，压缩后就是8k（8 * 8 (8 bit) * 1024(1k) = 8K），也就是说需要需要8k的心跳包，作者认为这样做不太值得；并且一般情况下一个redis集群不会有超过1000个master节点，所以16k的槽位是个比较合适的选择。

• 如果槽位为65536，发送心跳信息的消息头达8k，发送的心跳包过于庞大。
• redis的集群主节点数量基本不可能超过1000个。集群节点越多，心跳包的消息体内携带的数据越多。如果节点过1000个，也会导致网络拥堵。因此redis作者，不建议redis cluster节点数量超过1000个。
• 槽位越小，节点少的情况下，压缩率高
  Redis主节点的配置信息中，它所负责的哈希槽是通过一张bitmap的形式来保存的，在传输过程中，会对bitmap进行压缩，但是如果bitmap的填充率slots / N很高的话(N表示节点数)，bitmap的压缩率就很低。
  如果节点数很少，而哈希槽数量很多的话，bitmap的压缩率就很低。

和一致性哈希相比

• 并不是闭合的，key的定位规则是根据CRC-16(key)%16384的值来判断属于哪个槽区，从而判断该key属于哪个节点，而一致性哈希是根据hash(key)的值来顺时针找第一个hash(ip)的节点，从而确定key存储在哪个节点。
• 一致性哈希是创建虚拟节点来实现节点宕机后的数据转移并保证数据的安全性和集群的可用性的。redis cluster是采用master节点有多个slave节点机制来保证数据的完整性的,master节点写入数据，slave节点同步数据。当master节点挂机后，slave节点会通过选举机制选举出一个节点变成master节点，实现高可用。但是这里有一点需要考虑，如果master节点存在热点缓存，某一个时刻某个key的访问急剧增高，这时该mater节点可能操劳过度而死，随后从节点选举为主节点后，同样宕机，进入fail状态。
• 扩容和缩容
  一致性哈希算法在新增和删除节点后，数据会按照顺时针来重新分布节点。而redis cluster的新增和删除节点都需要手动来分配槽区。