一致性哈希 哈希槽(哈希碰撞和哈希冲突)

大家好，又见面了，我是你们的朋友全栈君。

背景

随着memcache和redis的出现，更多人认识到了一致性哈希。

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

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

一致性哈希

一致性hash是一个0-2^32的闭合圆，（拥有2^23个桶空间，每个桶里面可以存储很多数据，可以理解为s3的存储桶）所有节点存储的数据都是不一样的。计算一致性哈希是采用的是如下步骤：

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

添加节点带来的影响
图1为一致性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该存在哪里节点呢？说到这里你应该明白来吧

哈希槽

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

和一致性哈希相比

1. 它并不是闭合的，key的定位规则是根据CRC-16(key)%16384的值来判断属于哪个槽区，从而判断该key属于哪个节点，而一致性哈希是根据hash(key)的值来顺时针找第一个hash(ip)的节点，从而确定key存储在哪个节点。
2. 一致性哈希是创建虚拟节点来实现节点宕机后的数据转移并保证数据的安全性和集群的可用性的。redis cluster是采用master节点有多个slave节点机制来保证数据的完整性的,master节点写入数据，slave节点同步数据。当master节点挂机后，slave节点会通过选举机制选举出一个节点变成master节点，实现高可用。但是这里有一点需要考虑，如果master节点存在热点缓存，某一个时刻某个key的访问急剧增高，这时该mater节点可能操劳过度而死，随后从节点选举为主节点后，同样宕机，依次类推，造成缓存雪崩。解决这个问题请看我的另一篇文章如何应对热点缓存问题

新建master节点
使用redis-trib.rb工具来创建master节点

./redis-trib.rb add-node 172.60.0.7:6379 172.60.0.5:6379

注释：

192.168.10.219:6378是新增的节点

192.168.10.219:6379集群任一个旧节点

注意：新建的master节点是没有槽区的，需要给master节点分配槽，不然缓存无法命中。分配槽的方法自行百度。
删除master节点
1.如果主节点有从节点，需要将从节点转移到别的主节点上。
2.转移后 如果主节点有哈希槽，去调哈希槽，然后在删除master节点
注意：redis cluster的动态扩容和缩容并不会影响集群的使用。