一致性哈希算法

图解一致性哈希算法

负载均衡

顾名思义，负载均衡就是分摊压力，例如在我们的大多数网站背后，都会不止有一台服务器在支撑网站的业务。毕竟一个人的力量是有限的，那一台服务器所能承受的压力、并发量、数据量也都是有限的，那么我们在拥有多台服务器后，要怎么分配‘压力’才显得合理呢？

那么聪明的你肯定已经想到了，我们把压力平分给服务器就好了啊！就像发牌一样轮流转发请求给服务器不就行了嘛。对的，这其实就是一个简单的解决负载均衡的方法，但是我们还需要考虑到的一点是，每台服务器的配置是有所区别的，所以我们还可以给不同的机器根据配置设置权重，将配置差一点的机器权重设置得低一点，让配置好一点的服务器承受更多的压力，这种算法就被称之为加权轮询。

了解完负载均衡后，下面我们来看一个应用场景！

假设我们有两万张商品的图片需要缓存，而我们手中有4台缓存服务器，那么根据我们上面讲到的负载均衡，你很容易就会想到将这2万张图片平均缓存到这4台服务器中。的确这样可以解决我们的问题，但是如果我们要访问某个缓存时，最坏的情况需要遍历4台缓存服务器，设想如果你是访问者，当我们的后台以这种方式去查询的时候，等待中的访问者是可以明显感受到效率太低的，我们做缓存的目的不就是减少等待时长吗？

说到这里读者们应该都想到了哈希算法，对关键字进行哈希计算然后取模(确保结果小于等于哈希表的长度)，通过结果来选择对应的缓存服务器。

很好，看上去好像万无一失，所有的图片都可以有‘家’可归。But，这个商品购物网站越做越大，需要缓存的图片越来越多，4台服务器已经支撑不起了，这好办，多搞几台服务器不就好了，先上两台！如果我们还是使用同样的公式来决定该选择哪一台缓存服务器[hash(demo.jpg) % 6]，有没有突然发现，几乎所有需要缓存的图片的位置都发生了改变！同样我们如果我们因为机器故障要移除一台缓存服务器，那么几乎所有的数据都需要迁移！所以一致性哈希算法就该上场了~~

一致性哈希算法

基本概念

名字有相同之处，它们俩使用的方法也有相似之处。一致性哈希算法也是采用取模的方法，而刚才我们是对缓存服务器的数量取模，现在一致性哈希算法是对2^32取模。不对啊，那得需要多少台缓存服务器才能用得上这个算法啊？不急，我们来看看它的巧妙之处。

如果我们把使用一致性哈希算法取得的结果做成一个圆，那它是不是就变成这样了：

每一个使用一致性哈希算法得出的结果都可以在哈希环上找到一个自己的‘位置’，也就是说环上的点就是从0到2^32-1。

但是我们该怎么计算出自己的位置呢？以我们刚才的情景为例，分两步:

• 对存储节点做哈希映射。对应我们这里的对缓存服务器做哈希映射，也就是说把缓存服务器给分到哈希环上面去，例如用它的IP地址进行哈希
• 对数据做哈希映射。这里我们就要用到刚才说的对2^32取模

从图中我们也可以看到，计算出在哈希环上的位置后，往顺时针遇到的第一个节点，就是选择得缓存的服务器节点位置，即K1缓存在A上。那么我们再回到刚才遇到的问题，减少一个节点：

可以看到，只有缓存在B服务器上的图片收到了影响，需要迁移到节点C，增加节点同理。

也就是说，在一致性哈希算法中，增加或减少一个节点，只会影响哈希环上增加或删除的节点的后继节点(顺时针)，其他节点和数据并没有被影响。

但是上图中，看似服务器节点都均匀的分布到了哈希环上，但实际上一致性哈希算法并不能保证节点被均匀地分布在哈希环上，那么就可能产生这样一种情况：

可以看到，大量请求都打到了一个节点上，这还是负载均衡吗？

再想一想，如果此时节点A扛不住了，那所有请求都打到了节点B上，那么很容易就引发了连锁雪崩！

如果节点足够多的话，那是不是就会分布得更均匀一些？但实际中我们不会有那么多的节点，所以虚拟节点就派上用场了。

所谓虚拟节点就是实际节点的副本，首先将虚拟节点映射到哈希环上，再将虚拟节点映射到真实的节点，有了这两层映射关系这里就不再需要把真实节点再映射到哈希环上。

例如我们对ABCD四个节点分别设置3个虚拟节点：

节点数量变多后，分布就会更加均匀了。此时有请求访问到D-2，再通过D-2找到真实节点D，就能把请求打到D节点上了。

引入虚拟节点后，再有节点的增加或删除操作，就会有不同的节点来分担任务，提高了系统的稳定性。当然，也可以为配置好的节点分配更大的权重，设置更多的虚拟节点。