当单个节点(缓存服务器等)的能力达到上限,一般需要增加节点来打破瓶颈。在分布式系统中,扩容缩容操作极为常见。为了保证数据的均匀,一般情况会采用对key值hash,然后取模的方式,然后根据结果,确认数据落到哪台节点上。如:hash(key)%N
,这的确实现了初步的分布式,数据均匀分散到了各个节点上,流量请求也均匀的分散到了各个节点;但出现以下情况:
上面的情况带来的问题:增加或者删除服务器的时候,意味着大部分的数据都会失效。这个是比较致命的一点。如果频繁进行重Hash操作显然是不可取的,一是消耗太大,而是可能引发服务的中断。
所以,增删机器时,希望大部分key依旧在原有的服务器上保持不变。
这就需要一致性hash算法。
一致性Hash算法(Consistent Hashing)是一种hash算法,它能够在Hash输出空间发生变化时,引起最小的变动。以我们的例子来讲,增加或者移除一台服务器时,对原有的服务器和用户之间的映射关系产生的影响最小。
好的一致性Hash算法应该能够满足以下要求:
一致性哈希将整个哈希输出空间设置为一个环形区域,将整个哈希值空间组织成一个虚拟的圆环。而且这个哈希值空间的大小为 [0, 2^32-1]。
假设我们有3台服务器,把服务器通过hash算法,加入到上述的环中。一般情况下是根据机器的IP地址或者唯一的计算机别名进行哈希。
c1=hash(cache1) % ^;
c2=hash(cache2) % ^;
c3=hash(cache3) % ^;
假设我们现在有key1,key2,key3,key4 4个key值,我们通过一定的hash算法,将其对应到上面的环形hash空间中。
k1=hash(key1) % ^;
k2=hash(key2) % ^;
k3=hash(key3) % ^;
k4=hash(key4) % ^;
一致性hash的寻址方案如下:
一致性hash算法是允许对任意一个数字取模的。但是,如果数字太小,扩容时服务器数量大于该数字,就会存在环空间节点重复。所以一般选择一个固定大的数来取模运算(2^32=4294947297(最大的非符号整形数,也是ip地址的数值空间))。
只有环形可以覆盖所有hash值,不然就必须在首或者尾存在节点。
上面的简单的一致性hash的方案在某些情况下但依旧存在问题:一个节点宕机之后,数据需要落到距离他最近的节点上,会导致下个节点的压力突然增大,可能导致雪崩,整个服务挂掉。
可以用虚拟节点解决,用实际节点虚拟复制而来的节点被称为”虚拟节点”,将虚拟节点分散在环上,并映射到实际节点上。
这个就解决之前的问题,某个节点宕机之后,存储及流量压力并没有全部转移到某台机器上,而是分散到了多台节点上。解决了节点宕机可能存在的雪崩问题。当物理节点多的时候,虚拟节点多,这个的雪崩可能就越小。