Random walk to my blog

my blog for sharing my knowledge,experience and viewpoint

0%

一致性哈希算法

发表于 更新于 分类于

分布式哈希（Distributed Hashing）

分布式环境中，需要进行分布式哈希来进行负载均衡，减少忙碌服务器的负载。例如，对一个键(key)做了哈希后，需要确定它保存在哪个服务器上面。一致性散列(consistent hash)函数的特点是，当函数范围(例如，服务器的数量)变化，它变化的最少。
一个对一致性哈希的典型应用是Memcached.

对长度做的哈希

假设不使用一致性哈希函数，只是简单地根据服务器的数量进行哈希。

假设有3台服务器A,B,C, 现在采用的策略是hash(key) mod N。

一般来说，取余(mod)操作比较慢，如果服务器的数量是2^N,计算mod操作时，可以用hash(key) & (2^N )来提高速度。

KEY HASH HASH mod 3
“john” 1633428562 2
“bill” 7594634739 0
“jane” 5000799124 1
“steve” 9787173343 0
“kate” 3421657995 2

key在服务器的分布情况如下：

A B C
“bill” “jane” “john”
“steve” “kate”

再散列问题

这时，如果服务器的数量发生改变，因为策略是hash(key) mod N。 key在服务器的分布情况会发生较大的变化。假设减少了一台服务器，现在只有服务器A,B。

KEY HASH HASH mod 2
“john” 1633428562 0
“bill” 7594634739 1
“jane” 5000799124 0
“steve” 9787173343 1
“kate” 3421657995 1

分布情况：

A B
“john” “bill”
“jane” “steve”
“kate”

可以看到，hash(key) mod N, 由于N这个值域发送变化，key的分布全部都变了。这会导致，短时间内，对key的查询失效，增加服务器的负担，减低性能。

解决方法：一致性hash

一致性hash是一个分布式的hash方法，它的hash与服务器的数量无关，因为它将key 映射在一个虚拟的hash环（hash ring)，使得服务变得更为可扩展。

假设将hash(key)映射到一个环，最小值是0，它的角度也为0度，最大值是INT_MAX,角度是360度。
hash ring

KEY HASH ANGLE (DEG)
“john” 1633428562 58.8
“bill” 7594634739 273.4
“jane” 5000799124 180
“steve” 9787173343 352.3
“kate” 3421657995 123.2

同样地，将服务器做系统的映射，放到hash ring。
hash ring server

KEY HASH ANGLE (DEG)
“john” 1633428562 58.8
“bill” 7594634739 273.4
“jane” 5000799124 180
“steve” 9787173343 352.3
“kate” 3421657995 123.2
“A” 5572014558 200.6
“B” 8077113362 290.8
“C” 2269549488 81.7

我们可以设置自己的规则，以逆时针方向，每个key都属于距离它最近的服务器
hash ring skey erver

EY HASH ANGLE (DEG)
“john” 1633428562 58.7
“C” 2269549488 81.7
“kate” 3421657995 123.1
“jane” 5000799124 180
“A” 5572014557 200.5
“bill” 7594634739 273.4
“B” 8077113361 290.7
“steve” 787173343 352.3
KEY HASH ANGLE (DEG) LABEL SERVER
“john” 1632929716 58.7 “C” C
“kate” 3421831276 123.1 “A” A
“jane” 5000648311 180 “A” A
“bill” 7594873884 273.4 “B” B
“steve” 9786437450 352.3 “C” C

从编程的角度，我们可以将服务器的值（角度或者hash值）保存在一个有序列表中，然后去搜索这个列表，找到第一个它的值大于或者等于key值的服务器，如果找不到，就去去列表的第一个服务器。

为了保证key是均匀第分布在服务器中，我们给服务器赋予很多的标签(label)，例如A0...A9, B0...B9, C0...C9,然后将其散布到hash ring中。每个服务器的label的数量就是这个服务器的权重(weight)， 这是用来调整key落在服务器上的可能性。权重越大，label越多，一个服务器保存的key越多。

例如，给服务器A,B, C相同的权重，10个权重，分布在hash ring中。

hash_ring_weight

KEY HASH ANGLE (DEG)
“C6” 408965526 14.7
“A1” 473914830 17
“A2” 548798874 19.7
“A3” 1466730567 52.8
“C4” 1493080938 53.7
“john” 1633428562 58.7
“B2” 1808009038 65
“C0” 1982701318 71.3
“B3” 2058758486 74.1
“A7” 2162578920 77.8
“B4” 2660265921 95.7
“C9” 3359725419 120.9
“kate” 3421657995 123.1
“A5” 3434972143 123.6
“C1” 3672205973 132.1
“C8” 3750588567 135
“B0” 4049028775 145.7
“B8” 4755525684 171.1
“A9” 4769549830 171.7
“jane” 5000799124 180
“C7” 5014097839 180.5
“B1” 5444659173 196
“A6” 6210502707 223.5
“A0” 6511384141 234.4
“B9” 7292819872 262.5
“C3” 7330467663 263.8
“C5” 7502566333 270
“bill” 7594634739 273.4
“A4” 8047401090 289.7
“C2” 8605012288 309.7
“A8” 8997397092 323.9
“B7” 9038880553 325.3
“B5” 9368225254 337.2
“B6” 9379713761 337.6
“steve” 9787173343 352.3
KEY HASH ANGLE (DEG) LABEL SERVER
“john” 1632929716 58.7 “B2” B
“kate” 3421831276 123.1 “A5” A
“jane” 5000648311 180 “C7” C
“bill” 7594873884 273.4 “A4” A
“steve” 9786437450 352.3 “C6” C

使用hash ring的好处是，如果标签C0...C9被移除， 之前属于C0...C9标签的key就会落到A0...A1和B0...B1上面，其他标签的key没有变化。

hash_ring_reduce

KEY HASH ANGLE (DEG) LABEL SERVER
“john” 1632929716 58.7 “B2” B
“kate” 3421831276 123.1 “A5” A
“jane” 5000648311 180 “B1” B
“bill” 7594873884 273.4 “A4” A
“steve” 9786437450 352.3 “A1” A

同样地，当服务器数量增加时，变化也是类似的。

如果有k个key，N个服务器，当服务器数量变化时。只有k/N个key发生变化。

更多内容，访问我的博客