一致性哈希算法ITeye - AG环亚娱乐

一致性哈希算法ITeye

2019-01-14 05:08:21 | 作者: 宛南 | 标签: 算法,映射,目标 | 浏览: 2939

问题描绘: 例如手机朋友网有n个效劳器,为了便使用户的拜访会在效劳器上缓存数据,因而用户每次拜访的时分最好能坚持同一台效劳器。
已 有的做法是依据ServerIPIndex[QQNUM%n]得到恳求的效劳器,这种办法很便利将用户分到不同的效劳器上去。可是假如一台效劳器死掉了, 那么n就变为了n-1,那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%(n-1)]根本上都不相同了,所 以大多数用户的恳求都会转到其他效劳器,这样会发作许多拜访过错。

    问: 怎么改善或许换一种办法,使得:
(1)一台效劳器死掉后,不会形成大面积的拜访过错,
(2)原有的拜访根本仍是停留在同一台效劳器上;
(3)尽量考虑负载均衡。(思路:往散布式共同哈希算法方面考虑。)

最土的办法仍是用模余办法:做法很简略,假定有N台效劳器,现在无缺的是M(M =N),先用N求模,假如不落在无缺的机器上,然后再用N-1求模,直到M.这种办法关于坏的机器不多的状况下,具有更好的稳定性。
共同性哈希算法。

    在做效劳器负载均衡时分可供挑选的负载均衡的算法有许多,包含:  轮循算法(Round Robin)、哈希算法(HASH)、最少衔接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其间哈希算法是最为常用的算法.

    典型的运用场景是: 有N台效劳器供给缓存效劳,需求对效劳器进行负载均衡,将恳求均匀分发到每台效劳器上,每台机器担任1/N的效劳。

    常用的算法是对hash成果取余数 (hash() mod N): 对机器编号从0到N-1,依照自界说的hash()算法,对每个恳求的hash()值按N取模,得到余数i,然后将恳求分发到编号为i的机器。但这样的算 法办法存在丧命问题,假如某一台机器宕机,那么应该落在该机器的恳求就无法得到正确的处理,这时需求将当掉的效劳器从算法从去除,此刻分会有(N- 1)/N的效劳器的缓存数据需求从头进行核算;假如新增一台机器,会有N /(N+1)的效劳器的缓存数据需求进行从头核算。关于体系而言,这一般是不行承受的波动(由于这意味着许多缓存的失效或许数据需求搬运)。那么,怎么设 计一个负载均衡战略,使得受到影响的恳求尽或许的少呢?
    在Memcached、Key-Value Store、Bittorrent DHT、LVS中都选用了Consistent Hashing算法,能够说Consistent Hashing 是散布式体系负载均衡的首选算法。

Consistent Hashing算法描绘

    下面以Memcached中的Consisten Hashing算法为例阐明。

    consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,现在在 cache 体系中运用越来越广泛;

1 根本场景

比方你有 N 个 cache 效劳器(后边简称 cache ),那么怎么将一个目标 object 映射到 N 个 cache 上呢,你很或许会选用相似下面的通用办法核算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;

hash(object)%N

一切都运转正常,再考虑如下的两种状况;

一 个 cache 效劳器 m down 掉了(在实践运用中必需求考虑这种状况),这样一切映射到 cache m 的目标都会失效,怎么办,需求把 cache m 从 cache 中移除,这时分 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ; 由于拜访加剧,需求增加 cache ,这时分 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

    1 和 2 意味着什么?这意味着突然之间简直一切的 cache 都失效了。关于效劳器而言,这是一场灾祸,洪水般的拜访都会直接冲向后台效劳器;再来 考虑第三个问题,由于硬件才能越来越强,你或许想让后边增加的节点多做点活,明显上面的 hash 算法也做不到。

      有什么办法能够改动这个状况呢,这就是consistent hashing。

2 hash 算法和单调性

Hash 算法的一个衡量目标是单调性( Monotonicity ),界说如下:

单调性是指假如现已有一些内容经过哈希分配到了相应的缓冲中,又有新的缓冲加入到体系中。哈希的成果应能够确保原有已分配的内容能够被映射到新的缓冲中去,而不会被映射到旧的缓冲调集中的其他缓冲区。

    简略看到,上面的简略 hash 算法 hash(object)%N 难以满意单调性要求。

3 consistent hashing 算法的原理

    consistent hashing 是一种 hash 算法,简略的说,在移除 / 增加一个 cache 时,它能够尽或许小的改动已存在 key 映射联系,尽或许的满意单调性的要求。

    下面就来依照 5 个过程简略讲讲 consistent hashing 算法的根本原理。

3.1 环形hash 空间

    考虑一般的 hash 算法都是将 value 映射到一个 32 为的 key 值,也便是 0~2^32-1 次方的数值空间;咱们能够将这个空间幻想成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

图 1 环形 hash 空间

3.2 把目标映射到hash 空间

    接下来考虑 4 个目标 object1~object4 ,经过 hash 函数核算出的 hash 值 key 在环上的散布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

图 2 4 个目标的 key 值散布

3.3 把cache 映射到hash 空间

    Consistent hashing 的根本思想就是将目标和 cache 都映射到同一个 hash 数值空间中,而且运用相同的hash 算法。

    假定当时有 A,B 和 C 共 3 台 cache ,那么其映射成果将如图 3 所示,他们在 hash 空间中,以对应的 hash值摆放。

hash(cache A) = key A;

… …

hash(cache C) = key C;

图 3 cache 和目标的 key 值散布

 

    提到这儿,趁便提一下 cache 的 hash 核算,一般的办法能够运用 cache 机器的 IP 地址或许机器名作为hash 输入。

3.4 把目标映射到cache

    现在 cache 和目标都现现已过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是怎么将目标映射到 cache 上面了。

    在这个环形空间中,假如沿着顺时针方向从目标的 key 值动身,直到遇见一个 cache ,那么就将该目标存储在这个 cache 上,由于目标 和 cache 的 hash 值是固定的,因而这个 cache 必定是唯一和断定的。这样不就找到了目标和 cache 的映射办法了吗?!

    仍然持续上面的比方(参见图 3 ),那么依据上面的办法,目标 object1 将被存储到 cache A 上; object2和 object3 对应到 cache C ; object4 对应到 cache B ;

3.5 调查cache 的变化

    前面讲过,经过 hash 然后求余的办法带来的最大问题就在于不能满意单调性,当 cache 有所变化时,cache 会失效,进而对后台效劳器形成巨大的冲击,现在就来剖析剖析 consistent hashing 算法。

3.5.1 移除 cache

    考虑假定 cache B 挂掉了,依据上面讲到的映射办法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的目标,也便是原本映射到 cache B 上的那些目标。

    因而这儿仅需求变化目标 object4 ,将其从头映射到 cache C 上即可;参见图 4 。

图 4 Cache B 被移除后的 cache 映射

3.5.2 增加 cache

    再考虑增加一台新的 cache D 的状况,假定在这个环形 hash 空间中, cache D 被映射在目标 object2 和object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的目标(它们是也原本映射到 cache C 上目标的一部分),将这些目标从头映射到 cache D 上即可。

    因而这儿仅需求变化目标 object2 ,将其从头映射到 cache D 上;参见图 5 。

图 5 增加 cache D 后的映射联系

4 虚拟节点

考量 Hash 算法的另一个目标是平衡性 (Balance) ,界说如下:

平衡性

平衡性是指哈希的成果能够尽或许散布到一切的缓冲中去,这样能够使得一切的缓冲空间都得到使用。

    hash 算法并不是确保肯定的平衡,假如 cache 较少的话,目标并不能被均匀的映射到 cache 上,比方在上面的比方中,仅布置 cache A 和 cache C 的状况下,在 4 个目标中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2 、 object3 和 object4 ;散布是很不均衡的。

    为了处理这种状况, consistent hashing 引进了“虚拟节点”的概念,它能够如下界说:

“虚拟节点”( virtual node )是实践节点在 hash 空间的仿制品( replica ),一实践个节点对应了若干个“虚拟节点”,这个对应个数也成为“仿制个数”,“虚拟节点”在 hash 空间中以 hash 值摆放。

    仍以仅布置 cache A 和 cache C 的状况为例,在图 4 中咱们现已看到, cache 散布并不均匀。现在咱们引进虚拟节点,并设置“仿制个数”为 2 ,这就意味着总共会存 在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假定一种比较抱负的状况,参见图 6 。

图 6 引进“虚拟节点”后的映射联系

 

    此刻,目标到“虚拟节点”的映射联系为:

objec1- cache A2 ; objec2- cache A1 ; objec3- cache C1 ; objec4- cache C2 ;

    因而目标 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大进步。

    引进“虚拟节点”后,映射联系就从 { 目标 -  节点 } 转化到了 { 目标 -  虚拟节点 } 。查询物体地点 cache时的映射联系如图 7 所示。

图 7 查询目标地点 cache

 

    “虚拟节点”的 hash 核算能够选用对应节点的 IP 地址加数字后缀的办法。例如假定 cache A 的 IP 地址为202.168.14.241 。

    引进“虚拟节点”前,核算 cache A 的 hash 值:

Hash(“202.168.14.241”);

    引进“虚拟节点”后,核算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表AG环亚娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章