面试时没有回答上来的一道题：一致性哈希

在此前的面经里，曾经提到过，到EA面试时被面试官提问，使用哈希算法的分布式集群，如何处理扩容的问题。当时自己对一致性哈希完全不了解，也最终没能灵光乍现的现场想出解决办法。昨天地铁回家时不知为何突然想起这个问题，询问了Mars，才知道还有一致性哈希这种已经大量使用的解决办法，Mars用十几站地铁的时间给我大概讲明白了其原理，在此和同我一样小白的同学分享一下。

01

故事

首先，算法总归是为了解决问题而存在，我们先来想象一个场景。

假设我们是一个大型社交网站，每天，都有无数的用户上传奇奇怪怪的照片到我们的后台服务器。他们不仅爱传，还爱看，其中，有大概三万张照片特别火，基本每天的大部分请求都是为了看它们。

为了让用户更快的浏览到这些最火的照片，我们使用了缓存，即每次当用户发起一个浏览图片的请求的时候，我们会先看看缓存里有没有，这样的缓存往往是在内存中，可以迅速的给用户返回结果。只有在用户想看的图片不在这最火的三万张中，才会真的向保存图片的服务发送请求，这个过程比缓存可慢多了。

我们准备了三台机器做缓存。那么问题来了，这三万张照片要怎么放在这三台机器上，才能让每次请求都能最快的知道，自己的照片到底缓存在哪台机器呢？

02

方法一：瞎放

最直接的办法，随便放。

随便的放的结果就是，任何一张图片，都可能存在三台机器中的任何一台上。于是，每次请求到来，我们都不得不遍历三台机器中的每一张图片，直到找到为止，心好累。

03

方法二：哈希算法

更好的办法，使用哈希算法存放。

为了不用每次都遍历三台机器，我们开始使用哈希算法来解决这个问题。我们使用图片的名字生成了一个数字，再对这个数字按3取模，最终会得到0，1，2这三个数字其中一个，然后我们把图片存在得到的数字对应的机器上。这样一来，每次我们只需要访问其中一台机器，就能找到想要的图片了，需要花费的时间减少了2/3！

这样的好日子过了很久，我们遇到了下一个问题。随着网站的扩大，我们有了闲钱，准备再安排一个缓存服务器来放图片。这样一来，每台机器上存的图片少了，查找图片的时间肯定会更短！但是，当我们准备把这台机器投入使用的时候，遇到了困难。

一开始我们按照3取模，一切都很好。可是现在，我们有4台机器了，需要按照4取模。那么，如果一张图片生成的数字是11，按照3取模的时候，它应该在11%3=2号机器上，按照4取模的时候，它应该在11%4=3号机器上。尴尬了！我们发现，当我们增加了一个机器之后，之前几乎所有的缓存都失效了，图片明明存在其中一台机器了，可是因为计算出了不一样的哈希值，它总是跑到没有保存自己的机器上去寻找自己的下落，当然，这样的寻找肯定会落空的。于是，当我们上线第四台机器的那一刻，我们的所有缓存几乎都失效了，后台存储图片的服务突然收到了大量因为缓存失效导致的访问，压力山大，直接崩溃了 ...

好容易缓过劲，我们细思极恐。如果每次增加或者减少服务器，就会导致所有缓存失效，这对我们的后台服务简直是巨大的挑战，而这真的是不能避免的吗？

于是，我们引入了一致性哈希，来解决我们的问题。

04

方法三：一致性哈希

与普通哈希算法最大的不同在于，一致性哈希在计算哈希值的时候，不是使用哈希表的节点数，即我们故事中的缓存服务器个数取模，而是使用2^32，即最大无符号数取模。任何一个输入的数，都会在一个有着2^32个格子的圆盘上，找到自己的存在。

为了保证分配的平均，我们把我们此时的4台服务器，D0,D1,D2,D3，均匀的映射到了这个大圆圈的四个格子上。

好了，下一步，对这3万张图，我们也计算出他们对2^32取模之后的哈希值，并映射到这个圆圈上。取其中五张图ABCDE作为例子，如果是一个好的平均的计算结果，他们分布在圆圈上的位置应该是这样的。

从图上可以看出，几乎每两个服务器的格子之间，都会有一个图片的格子。下一步要做的事情就简单了，假设我们要找图片D，它会在哪呢？沿着D计算出来的格子顺时针往下找，我们遇到的第一个服务器格子是D1，于是我们知道，D存在于D1服务器，搞定！

那么，这样的一致性哈希，遇到服务器减少或者增加的情况，又如何表现呢？

05

服务器坏啦

假设有一天，D2机器因为有人带娃到机房乱玩，被拔掉电源关机了，上面的缓存肯定是找不回来了。于是，当我们尝试寻找A图片，发现D2已经完蛋了，此时，我们会继续顺时针往下找，直到找到D1机器，然后，将A图片重新缓存到D1机器上去。这样一来，经过一段时间，D0 - D2节点之间的图片，都会慢慢缓存到D1机器上，一切仿佛从没有发生过一般。

在这个过程中，D2缓存过的图片注定会经历一段失效的时间，但是对于其他图片，他们依然能正确的被找到，后台服务器因为缓存失效导致的访问量增大，也不会非常剧烈，我们只是不得不经受一点点小小的压力，这可比雪崩式的缓存失效好太多了。

那么，如果再增加一台服务器呢？

06

有新服务器啦

如图，有一天公司良心发现，给我们又分了一台D4服务器，我们赶紧把它部署到缓存服务器集群中，我们的圆圈上又多了一个D4小格子来干活。

此时，从D1-D2区间的图片的缓存都依然有效，A，C，E，B图片都还是在原来的机器上，并且能正确的找到。只是当我们尝试寻找D图片，由于它顺时针下去遇到的第一个服务器节点是D4，而此时D4刚起步，啥都没有，于是D图片缓存失败，只好去后端服务器把D图片重新缓存到D4服务器。这样的失败会经历一段时间，但不会太久，毕竟D2-D4只是一个很小的区间。一段时间过后，一切又恢复了平静，我们干活的服务器更多了，happy。

07

还没完

一切看起来都特别美好，只是，当我们的服务器数量特别少的时候，如果其中一台或多台挂掉，剩下的服务器很可能会出现负载严重不平衡的状况，累的累死，闲的闲死。

比如，我们的四台机器，由于年久失修，有一天直接崩了两台，剩下的D0和D2在圈圈上又挨的特别近，这样一来，曾经在其他两台机器上的图片缓存需求，全部转移到了D0机器上，D0不堪重负，直接崩溃了...

类似的情况，回到之前新增服务器的例子，如果你不记得了，我把图再贴一次。

虽然D4服务器的出现缓解了一部分D1服务器的压力，但是其他服务器的负载还是那么多，D4没有如同我们期待的那样，平均的为大家分担一点辛苦，这也不是我们想看到的最好的结果。

08

虚拟节点

为了避免这样的问题，一致性哈希引入了另一个概念，即虚拟节点。我们为每台机器虚拟出了多个节点，多个节点代表的是同一台机器，如图所示。

这样一来，不管是D0#1还是D0#2，代表的都是D0服务器，于是分散在盘子上的服务器节点变多了，相对来说就更容易均匀。回到之前四台服务器的例子，一旦其中两台挂掉，剩下的负载依然会均匀的分散给还活着的两台服务器，每个人都只多干了一份活儿，而不是一个人干一份，一个人干三份。同理，如果新增的服务器有多个虚拟节点分散在圆圈上，那么它也能为每一台机器分担一部分活儿，大家都轻松一点，happy。

故事讲完了。一致性哈希就是这样一个跑圈圈的算法，是不是还是挺有意思的？

最近刚忙完入职以来的第一个麻烦活儿，又不幸感染了严重的感冒，于是停更两周，非常对不起可爱的读者们。本以为应该没人发现我们偷懒了，没想到昨天一位现在在ZOOM财务自由的老同事突然问起，公众号咋没更新啦？才很惭愧的表示这周补上。一口气讲完故事，希望你喜欢。

Schönes Wochenende!

我的2019周更计划已完成：42/52

[********............]