背景

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

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

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

哈希

哈希算法最重要的特点就是：

• 相同的输入一定得到相同的输出；
• 不同的输入大概率得到不同的输出。

哈希碰撞

哈希碰撞是指，两个不同的输入得到了相同的输出：

"AaAaAa".hashCode(); // 0x7460e8c0
"BBAaBB".hashCode(); // 0x7460e8c0

有童鞋会问：碰撞能不能避免？答案是不能。碰撞是一定会出现的，因为输出的字节长度是固定的，String的hashCode()输出是4字节整数，最多只有4294967296种输出，但输入的数据长度是不固定的，有无数种输入。所以，哈希算法是把一个无限的输入集合映射到一个有限的输出集合，必然会产生碰撞。

碰撞不可怕，我们担心的不是碰撞，而是碰撞的概率，因为碰撞概率的高低关系到哈希算法的安全性。一个安全的哈希算法必须满足：

• 碰撞概率低；
• 不能猜测输出。

不能猜测输出是指，输入的任意一个bit的变化会造成输出完全不同，这样就很难从输出反推输入（只能依靠暴力穷举）。假设一种哈希算法有如下规律：

hashA("java001") = "123456"
hashA("java002") = "123457"
hashA("java003") = "123458"

那么很容易从输出123459反推输入，这种哈希算法就不安全。安全的哈希算法从输出是看不出任何规律的：

hashB("java001") = "123456"
hashB("java002") = "580271"
hashB("java003") = ???

常用的哈希算法有：

根据碰撞概率，哈希算法的输出长度越长，就越难产生碰撞，也就越安全。

哈希算法的用途

• 判断是否篡改

因为相同的输入永远会得到相同的输出，因此，如果输入被修改了，得到的输出就会不同。

我们在docker hup上随便找一个镜像，看到采用的hash算法为SHA-256：

image

如何判断下载到本地的软件是原始的、未经篡改的文件？
我们只需要自己计算一下本地文件的哈希值，再与官网公开的哈希值对比，如果相同，说明文件下载正确，否则，说明文件已被篡改。

• 密码加密

在登录系统中我们通常使用md5方式加密用户密码，这样当数据库泄漏之后，也看不到用户的密码。
因为相同的输入永远会得到相同的输出，因此，对用户输入的密码进行MD5加密并与数据库存储的MD5对比，如果一致，说明口令正确，否则，口令错误

介绍了这么多，言归正传，介绍一致性哈希。

一致性哈希

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

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

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

image

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

image

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

image

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

image

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

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

image

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

image

正因为加入了虚拟节点机制，数据倾斜的问题也随之解决

注意：

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

哈希槽

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

image

和一致性哈希相比

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节点可能操劳过度而死，随后从节点选举为主节点后，同样宕机，一次类推，造成缓存雪崩。解决这个问题请看我的另一篇文章如何应对热点缓存问题
3. 扩容和缩容
   可以看到一致性哈希算法在新增和删除节点后，数据会按照顺时针来重新分布节点。而redis cluster的新增和删除节点都需要手动来分配槽区。

• 新建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节点上，然后在删除master节点
  注意：redis cluster的动态扩容和缩容并不会影响集群的使用。

参考文章
一致性哈希原理
一致性hash介绍及使用原理