1 10
一致性哈希学习总结

概念

一致性哈希最早由 MIT的 Karger 提出,在发表于1997年的论文 《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》,

一致性hash算法提出了在动态变化的Cache环境中,应该做到的四方面内容:平衡性、单调性、分散性、负载。

学习

当我们了解了上述的一致性哈希的概念,其实往往都还一知半解的,因为单凭枯燥的概念无法让我们建立清晰的一致性哈希的模型。但如果我们能结合日常开发分布式系统的经验,这就是不错的切入点了。

在互联网公司做的产品或者工具,基本都是分布式的了,以监控系统或者提供上报服务的系统为例:为了提供整个系统的高可用和吞吐量,我们一般会有这么一个机制:把请求分派到不同的服务节点上。

具体的服务节点收到这些请求后,会根据某些业务准则判断是否触发告警或进行一些实时的计算等。但这种机制会引出了一种比较棘手的问题: 以监控系统为例,我们有一套分布式的监控上报服务,然后我们在某些被观察的服务器上安装agent,我们希望这台服务器上的同一个监控项(例如:cpu空闲率)总能被推送到 同一台的监控上报服务节点上进行处理,另外一些监控项(如内存使用率)能分配到另外一台监控上报服务节点上。

假如我们的agent把监控项是随机分配到任何一个上报服务节点的,同一个监控项会在不同的时间点上被分配到不同的上报节点中。如果我们下游的告警系统需要以维度逻辑来判断某一个时间区间 之内是否达到触发告警条件的时候,我们就必须将这些分散在不同服务节点上的资料整理在一起才能处理了。如果我们设计我们的分布系统安装这种思路的话,很容易让我们的服务出现SPF(单点故障)的问题。

那么,有没办法能够做到:我们agent采集的不同监控项都能按照指示分配到同一服务节点上去呢?也就是说不同的上报服务集中处理不同的监控维度信息,很明显这种方法能避免单点故障的问题。

一致性哈希算法

哈希表

哈希表,也叫散列表:是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

它本身是一个ADT,它的好处是能快速完成节点搜索,举个例子:我们想对哈希表进行存取的时候,首先会输入一个参数,我们成为key,然后我们会利用 一个成为hash function的函数把key映射到一个hash-value。hash-value 在哈希表中是用作index的,这个index会决定存取的元素在哪个slot中。

在分布式系统中,我们把待处理的数据当做key,最后找到value的行为相当于把数据请求分派到相应的服务节点上。

分布式的哈希化优点是:当服务节点的增加或者减少的情况下,key与value的映射关系变动相当小

一致性哈希原理

在大多数的分布式哈希例子中,我们都希望hash算法能尽量让每个slot的可能性是一样的,这样才能避免服务冲突的发生。最简单粗暴的hash函数例子就是使用 算余数的方式,假设服务节点的数量是N,那么这个hash function的计算方法是:

hash_function(key) = key mod N

我之前看很多开源项目的代码,从RPC到MQ的开源产品,里面牵涉到一些hash的处理都是用这种简单的方案,这也是我们可以用来使用的最简单的方法了。

hash function 应用在我们的分布式系统中能产生什么收益呢?

我们举一个模拟的场景:

假设,我们总共有23个服务节点,也就是N=23。这23个服务节点相当于hash table的23个slots。那么一个随机的key映射到slot的几率都是1/23。 当由于业务需要我们的系统需要增加一个服务节点,也就是N改为24,则每个key只会有1/24的几率被分配到原来的slot中。又或者,我们的系统系统裁减 一个服务节点,也就是N=22, 则每个key则只会有1/23的几率被分配到原来的slot。

以上的例子告诉我们一个事实:大部分的数据请求在服务节点数量改变之后都会被分派到不同的服务节点,然而如果使用了一致性哈希的方法(可以参考这论文), 在此范围增加一个服务节点,则每个只有1/24的概率会改变映射关系,减少一个节点,则每个key只有1/23的概率会改变关系。

为了增加理解,我们结合一致性哈希环来解析原理

我们假设我们有一个hash空间范围是 0 ~ 2³²-1,且操作是按照顺时针, 用哈希环表示如下图:

chr-1

当我们的三台服务节点分别是 ServiceNode-1、ServiceNode-2、ServiceNode-3,我们可以把这三台服务器名称的字符串当做参数, 并利用某个函数把它转换成三个Unsinged integer,当作存放这些代表服务节点的slots的index,这个函数我们暂时称为pre-hashing。 在现实中,我也常常需要把keys或者Hash values以 Unsinged integer 的数据类型呈现,而pre-hashing做得事情就是把这些非整数的类型转化为Unsinged integers。

这样,三台服务节点indexs放在哈希环中的形态,如下图:

chr-2

我们使用Go语言把添加服务节点的方法叫add()

func (c *Consistent) add(elt string) {
    for i := 0; i < c.NumberOfReplicas; i++ {
        c.circle[c.hashKey(c.eltKey(elt, i))] = elt
    }
    c.members[elt] = true
    c.updateSortedHashes()
    c.count++
}

在上述代码中,服务节点都是使用字符串代表,add()函数中的 circle 所代表的就是 一致性哈希环 ,存放在上面的数据代表 的是服务节点的字符串,而存储circle所使用的indexs就是服务节点的Slots的indexs, hashKey() 就是前文提到的 pre-hashing。 它把字符串转化为无符号整数,作为slot的索引indexs

add() 中我们可以发现这里面有一个for循环,使得一个字符串最后在circle中存入多个indexs。

接下来,我们要说明是在一致性哈希中,hash function是怎么根据keys找到hash-values的。在现实中,keys必须是无符号整型,假设今天我们是 要为被监控项目的数据请求找到一个服务节点,则我们必须先把这数据请求透过上面的pre-hashing函数,转换为一个Unsinged integer来作为代表这个 数据请求的key,我们把这个key放到一致性哈希环中展现,如下图:

chr-3

接着,一致性哈希算法的做法 “沿着顺时针方向走,直到遇到第一个index”。我们从这个Unsigned integer 的所在位置沿着顺时针方向走,遇到的第一个代表 服务节点的index就是这个key所映射的hash-value。找到了这个slot,就表示找到了这份被监控服务器的数据请求对应的服务节点了。如下图:

chr-4

这样的操作行为,我们用Go语言实现名为 func Get() 的函数

func (c *Consistent) Get(name string) (string, error) {
    c.RLock()
    defer c.RUnlock()
    if len(c.circle) == 0 {
        return "", ErrEmptyCircle
    }
    key := c.hashKey(name)
    i := c.search(key)
    return c.circle[c.sortedHashes[i]], nil
}

此函数先用hashKey()这个方法作为pre-hashing,把字符串形态的参数转化为Unsinged integer,再利用 search() 函数以 Key 为参数进行binary search。

search()函数所搜索的对象是sortedHashes这个slice。在sortedHashes中存放的是排序过的服务节点indexs。找到key所对应的index后, Get()函数最后根据index作为circle的索引,返回代表具体服务节点的字符串。

在上述解析了一致性哈希的工作方式后,我们来讨论增加或者减少服务节点的情况。假设我们今天增加一个服务节点ServiceNode-4,则只有图中黄色区间的keys会因为 ServiceNode-4 的加入而找到不同的Hash-values:

chr-5

假设我们进入把ServiceNode-2给移除了,只有图中黄色的keys会因此找到不同的hash-value

chr-6

根据以上的例子,我们并不难观察出一致性哈希的做法的确比一般的方式更能保持原本keys与values之间的映射关系。

改进:虚拟服务节点

有一种情况:当我们将node进行哈希后,这些值并没有均匀地落在环上,因此,最终会导致,这些节点所管辖的范围并不均匀, 最终导致了数据分布的不均匀,如下图:

chr-7

因此,通过增加虚节点的方法,使得每个节点在环上所“管辖”更加均匀。 这样就既保证了在节点变化时,尽可能小的影响数据分布的变化,而同时又保证了数据分布的均匀。 也就是靠增加“节点数量”加强管辖区间的均匀。

chr-8

当一致性哈希环中的indexs数量变多,分布不均匀的机会较小,服务节点的承载不均匀就可以得到改善

虚拟服务节点的Go语言代码表示:

for i := 0; i < c.NumberOfReplicas; i++ {
    c.circle[c.hashKey(c.eltKey(elt, i))] = elt
}

代码中的 NumberOfReplicas 决定了循环的次数,也技术节点复制的次数。

总结

经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,例如新加入的节点H的散列在B与C之间,则原先由C处理的一些数据可能将移至H处理,而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。而如果删除一台机器,例如删除C节点,此时原来由C处理的数据将移至D节点,而其它节点的处理情况仍然不变。而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。而通过引入虚拟节点的方式,也大大提高了平衡性。