一致哈希

一个关于去医院看病的故事~...



又到周日下午，快来听老王扯技术了~

上周我们聊了哈希，这周我们来聊聊一致哈希。这是个什么东东？是不是长的很一样的哈希？或是意见相同的哈希？

看过老王之前写的文章的朋友，一定记得在《负载均衡》这篇文章中，老王有简单聊过这个算法。如果没看过也不要紧，老王今天就来详细讲讲这个听起来牛逼的算法~

来，先看看一个场景（老王冥思苦想了好久，才想到这样一个场景，所以要把文章写好确实不容易啊~）。

我们去医院看病，第一次挂号完了，可能就被随机分配给一个医生。医生看完以后，说你这个病需要长期的治疗，所以以后每周来检查一次，持续3个月。好了，等到下周的时候，你再去医院看病的时候，这个时候最理想的情况是上周那个医生给你检查，给你提供持续的关注，对吧。而其他医生也有自己的病人，一般也是持续性的。

突然有一天你去医院检查，你看到给你就诊的医生的诊室人变多了，排了很多人，你不得不排在了很后面（这时候就会觉得心烦），一打听，哦，隔壁有个医生家里有事情，最近一周都不能上班，所以他的病人都分给了其他的医生。

到了第三个月，你快康复了，这周又去做检查，结果到医院，被告知给你看病的医生出差了，你不得不到隔壁某个医生那里检查。这个时候，也是没有办法，就去检查了。幸好，隔了一周，给你持续检查的医生回来了，你再去他那儿检查的时候，他告诉你，你已经完全康复了~

故事终于讲完了，真是不容易啊~ 扯了这么多，这个故事跟我们今天要讲的技术有什么关系么？大伙儿别急，肯定有关系啦~

我们把上面的问题抽象一下：

1、你第一次去医院看病，被医院的某个算法h(user)分配到了某一个医生那里；

2、之后，你每次去的时候，都是分配到这个医生；

3、如果某个医生有缺席，他的病人会被分配给其他医生；

4、当缺席的医生会来以后，他的病人会重新分配给他；

5、每个医生接待的病人量是差不多的。

大家看上面的这个case是不是跟我们上次讲的哈希算法有点相似啊：病人就像是一个个的key，被医院的挂号系统做了一个hash(key)运算，然后得到了一个hash_code。

不过感觉又有一点不同：我们拿到的这个hash_code被分配到固定的几个桶里面的某一个。如果其中一个不在了，这个桶里的hash_code会被再分配给其他的桶；如果这个桶恢复了，这个hash_code又重新分配回来。

看起来就是这个hash_code和这个桶是尽量保持一致的，对吗？其实，这个让key怎么样得到hash_code，然后这个hash_code又怎么样能尽量均匀、尽量不变的映射到桶里的这个算法，就是我们今天要聊的一致哈希算法。

聊了这么大一圈，终于开始说到正题上了。

在我们分布式计算中，很多情况要用到这个算法。比如：

场景一：

我们在做server开发的时候，经常有这样的需求：当有多台机器提供同一类服务（比如：用户发贴）的时候，我们希望某一个用户的请求，尽量的落在同一台服务器上，这样不论是统计用户行为（每个用户每分钟发贴个数）监控还是做日志分析（一天下来一个用户平均发贴数量），都会很方便。

场景二：

当我们提供分布式cache的时候，希望将某一个key的数据，尽可能存放到某一台机器上，这样数据就可以只存放一份，从而大大节省存储空间，让有限的存储空间缓存尽可能多的数据，从而提高cache的命中率。

场景三：

当我们的分布式cache有机器宕机了，或者需要添加新机器以应对更多的请求，那我们希望失效的缓存（因为要重新计算某一个key的数据会落到哪台机器上，就会产生cache失效）影响面越小越好，这样可以尽量保证cache的命中率，从而保证服务的稳定，将机器损坏对服务的影响降低到最低限度。

以上的这些问题，就是可以通过一致哈希算法来解决的。这个算法现在已经广泛的应用到分布式计算中，大家看这篇文章的时候，我猜测微信的服务处理就已经用到了这个算法。

所以，一致哈希算法，一般在分布式系统中用于选择服务（或者服务器）。那一致哈希比其他算法究竟有哪些好处呢？

如果我们采用随机算法，则同一用户的请求会分散到各个机器，不利于有效利用资源；如果用轮训，也是同样的效果。而一致哈希算法，可以避免这些不足。

这个算法具体是怎么样来实现的呢？

大家去百度搜索一致哈希算法，基本上会看到有几十上百万个相关网页。但是绝大部分都会讲同样的一个算法。那按照国际惯例，老王还是先讲讲这个与国际接轨的算法，然后再讲讲有老王特色的一个算法实现。

国际接轨算法

1、这个算法将所有的请求key（比如：请求的用户id、单词id等）做一个hash运算，hash的结果是一个[0,232)非负整数的区间，也即：hash(request) -> hash_code， hash_code ∈ [0,232)；

2、另一方面，我们将我们拥有的桶（比如：cache集群中的每一台cache机器、处理用户请求的每一台机器）也做一个hash运算，得到同样的一个值域：hash(node) -> hash_code， hash_code ∈ [0,232)；

3、我们将0-232 这些点做成一个圆环，两头首位相接；

4、我们将得到的request和node的hash_code映射到上面这个圆环上；

5、按顺时针方向旋转，每一个request去查找距离自己最近的node。



如果把request当做病人，node当做医生，大家来看看这个算法，是否满足我们之前提到的那些要求：

1、一个病人来到医院，会做一个hash，得到hash_code；

2、每一个医生有一个hash_code；

3、病人的hash_code找到最近的医生的hash_code；

4、以后每次来的时候，hash_code不变，从而对应的医生也不变；

5、当某一个医生缺席，即对应的node消失，这个医生对应的病人，会延顺时针方向寻找对应的医生；

6、当缺席的医生又回来的时候，这个医生对应的病人又自己回来了。

那代码上怎么落地呢？

1、hash算法：可以用我们上周讲过的那些算法，比如md5、sha、或者是简单运算等，只要保证足够分散就可以；

2、查找node结点：如果node结点不多，可以直接线性遍历；如果结点较多，就可以使用二分搜索。

好了，这个算法就讲的差不多了，大家理解了嘛？

有老王特色的算法

讲了国际算法，再来看看老王的土办法（其实也是去百度偷学到的，不是老王发明的~）

其实，不论哪种算法，实际上最终要解决以下两个问题：

1、散列的不变性：就是同一个请求（比如：同一个用户id）尽量的落入到一台机器，不要因为时间等其他原因，落入到不同的机器上了；

2、异常以后的分散性：当某些机器坏掉（或者增加机器），原来落到同一台机器的请求（比如：用户id为1，101，201），尽量分散到其他机器，不要都落入其他某一台机器。这样对于系统的冲击和影响最小。

有了以上两个原则，这个代码写起来就很好写了。比如我们可以这样做(假定请求的用户id=100）：

1、我们将这个id和所有的服务的IP和端口拼接成一个字符串：

str1 = "192.168.1.100:8080-100"

str2 = "192.168.1.101:8080-100"

2、对这些字符串做hash，然后得到对应的一些整数：

iv1 = hash(str1)

iv2 = hash(str2)

3、对这些整数做从大到小的排序，选出第一个。

好，现在来看看我们的这个算法是否符合之前说的两个原则。

1、散列的不变性：很明显，这个算法是可重入的，只要输入一样，结果肯定一样；

2、异常以后的分散性：当某台机器坏掉以后，原本排到第一的这些机器就被第二位的取代掉了。只要我们的hash算法是分散的，那么得到排到第二位的机器就是分散的。

所以，这种算法其实也能达到同样的目的。当然，可以写出同样效果的算法很多很多，大家也可以自己琢磨琢磨。最根本的，就是要满足以上说的原则。

怎么样，一致哈希算法看懂了嘛？

    关注 SimpleMain