一致性哈希

一致性哈希是一种特殊的哈希过程,它被用于bucket数量会动态变化的场景中。所谓的“一致性”是指当bucket数量发生改变时,绝大多数的key-value映射关系都不会改变。若使用不具备“一致性”特性的哈希过程,几乎所有的key-value映射关系都将遭到破坏。

哈希的一般过程是:用户输入一个key,由哈希函数计算得出哈希值,然后基于这个值再算出一个索引号,最后用该索引号在一组bucket中检索出一个特定的bucket,在该bucket中读写value:

上图假设4个字符串类型的key(key可以是字符串或整形),6个bucket,hash值对bucket的个数取模所得的数值即为bucket的索引号。

正常情况下,bucket的个数是不会动态变化的。当使用一个哈希表结构时,会在一开始就指明bucket组的长度,bucket是静态分配的,在使用过程中不可改变。不过,若将哈希过程对应到某个缓存系统对内容的分发处理上来的话,bucket的个数就有可能发生变化。

见下图,假设4个客户分别发来请求,要求后台系统给出自己的账号信息。proxy机构负责将这些客户映射到各个缓存服务器(A~F)。proxy所执行的就是第一张图中描述的哈希过程,此时的bucket中存放的是各缓存服务器的信息。用作key的str1~str4可以是客户的名字,账号ID号或邮箱等可以标识客户的字符串或整形。算出索引号,即可检索出其对应的缓存服务器,然后向该服务器发出读/写请求。

在现实当中,当业务量增大时,为保证服务质量,会人为地去增加缓存服务器的数量;当业务量降低,不需要太多的缓存服务器时,就需要将多余的服务器停掉。还有,服务器本身出现故障导致不可用的情况,也相当于减少了机器数量。

服务器数量增加的情况:目的是让新服务器分担掉一部分压力,为达到这个目的,取模运算要模的数值至少要等于当前服务器的个数

由此可见,每增加一台服务器,所有的key-value对应关系就会变化一次。当然,这里的key-value对只有4个,实际情况要多的多,而且增加服务器的时候,有时会一次性增加n台也不一定。总之,是有一些key-value关系是不会发生变化的,不过只是极少数(如果这里一次性增加6台机器,那么1001对12取模,得到的结果还是5)。

服务器数量减少的情况:服务器个数减少,取模运算要模的数值也要随之减少,否则,就有可能取到一个不存在的索引号

这个过程是服务器数量增加的逆过程,想象一下服务器从10台减少到6台的过程。不过,减少的时候还有些特别,bucket组是一个顺序表结构,如果服务器并非按顺序关停该如何处理?实际上服务器宕机就是随机的,不太可能从顺序表的尾部依序进行。
这种情况若不处理,那么映射到索引号为3的请求将无法被受理,因为此服务已不可用。可按照如下的两种方式进行处理,显然,处理过程会再次破坏key-value的映射关系。

几乎所有的key-value映射关系都发生了变化看上去也没什么大不了,这些毕竟是缓存服务器,映射关系变了,没命中,就去其后的数据库中去取一份数据即可,这样服务依然是可用的,不过性能将大打折扣。但是,缓存服务器的存在就是要提高系统性能,现在反而成了负担。

若有大量的并发请求到来,为提高系统系统性能,人为新增缓存服务器,此时的效果可能适得其反,幕后的数据库服务会因不堪重负而崩溃。

问题出在取模操作:index = hash mod n (n为bucket个数),若能保持n不变,那么index也就不会变,key-value的映射关系自然也不会改变。做法是预置大量的bucket,bucket的数量会超出当前可用服务器的数量。每当要增加新服务,就向首个空bucket中存放服务器信息即可。

假设事先预置了12个bucket,增加服务器的过程见下图。bucket的数量大于服务器的数量,而又按照bucket的数量进行取模运算,就会出现将key映射到空bucket上的情形。这个时候再多进行一步操作,从当前bucket出发顺序向后依次查找,直到遇到一个不为空的bucket,将这个key映射到该非空bucket上即可。若连最后一个bucket都是空的,那么就转向首个bucket重新来过。

服务器被人为删除,或者宕机的情况,不需要特殊的处理,就将那个bucket视为空。若有key映射到该bucket,就使用上面的处理过程,从该bucket处出发,去找第一个不为空的bucket即可。

经过上述改进,bucket组在逻辑上就构成了一个环形结构:

  • 增加一台服务器X,只会影响到紧邻其后的那一台机器Y。本来映射到Y机上的key,有一部分将被映射到X上。感觉就像是Y被X“截流“了,这也符合增加机器的初衷,就是要分担压力,Y的部分压力被X分担了。

  • 减少或挂掉一台机器(任意位次的bucket皆可)X,同样也只会影响紧邻其后的那一台机器Y。与增加机器相反,X不可用后,原本映射到X机的key,会全部转向Y机,Y机的压力由此增加。

不过,这种哈希方式仍需要改进,我们这里预设的bucket的个数为12个,如果未来某一天服务器的总个数超过12个该怎么办?到那时,如果增加新的bucket,那就又回到一开始的状况了,几乎所有的key-value映射关系都会发生改变!若想避免这个问题,就要在一开始预设足够多的bucket,那么到底预设多少个才合适呢?还有,根据设定的规则,所有映射到那6个空bucket上的key,全部都要被重新映射到A服务器上,显然,A的压力是要比其它机器大的,这不太公平,应该想办法让这些机器分散一些,不要都挤到一起,如何让机器尽量分散?

要做两件事情:1. 确定足够多的bucket;2. 让有效主机尽量分散地存储于这些bucket中。把这两件事情合起来看,就是在一个空间内,尽量均匀地去分布一些数值。而这与哈希函数所做工作类似,假设某个哈希函数每执行一次就产生一个16bit的哈希值,那么就相当于在0~2^16-1这个空间内占用了一个位置。

把2^16视为bucket的总个数,0~2^16-1即为各个bucket的索引号。以每个服务器的名字(A,B,C,D,E,F)或者IP、端口号二元组作为key,输入该哈希函数,算出每个服务器对应的哈希值,以该值直接作为索引号(不进行取模操作),去检索bucket,并写入服务器信息即完成服务器的分布。若该哈希函数设计良好的话,服务器的分布将是比较均匀的。当要确定key与服务器之间的映射关系时,同样将key输入该哈希函数,得出的数值即为bucket索引号(不进行取模操作),以此去索引bucket,读出服务器信息,即完成与服务器的映射。

下图的bucket环中密布着2^16个bucket,bucket的形状不一一画出。这个环就是“一致性哈希环”。

到目前为止的哈希过程就是最基本的一致性哈希,这个最基本的方案还是有一定问题的。

假设服务器A~F正承受巨大的压力,需要引入新服务以进行缓解。引入新机器之后,根据一致性哈希的规则,它只会帮紧邻其后的那台机器分担压力,对其它机器来说毫无助益。

想让一个机器“减负”,就只能在紧邻该机器的前一个bucket处安插新机器,同理,若想让多个机器都减负,那就需要安插多个机器才行,而我们只想加入一台机器就实现这个效果。做法就是在多个bucket中存放这个新机器的信息,让新机器的信息在环中分布开来,这样就会影响到不只一个机器了。

假设新加入的服务器名字为X,则同时增加服务器:X1~X4 ,它们其实都是X,不是真实的新服务器,因此叫做虚节点。

使用虚节点可以让新加入的服务器分担多个机器的压力。