Load

6 min read

负载均衡需要将大量的请求按照一定的权重把请求分散到各个后台服务器。得益于Hashing函数的特性——确定的输入和哈希函数能够得到唯一且确定的哈希值,水平负载均衡都采用一定的哈希函数来确定入向的请求应该被重定向到哪一台后端服务器。

以三台后端服务器(A、B和C)为例,假设三台服务器权重相同。下列请求可以按如下规则来确定

请求哈希值对3取余数对应服务器

请求 哈希值 对3取余数 对应服务器
1 c4ca4238a0b923820dcc509a6f75849b 1 B
2 c81e728d9d4c2f636f067f89cc14862c 0 A
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 1 B
4 a87ff679a2f3e71d9181a67b7542122c 2 C
5 e4da3b7fbbce2345d7772b0674a318d5 0 A
6 1679091c5a880faf6fb5e6087eb1b2dc 0 A
7 8f14e45fceea167a5a36dedd4bea2543 0 A
8 c9f0f895fb98ab9159f51fd0297e236d 2 C
9 45c48cce2e2d7fbdea1afc51c7c6ad26 2 C
10 d3d9446802a44259755d38e6d163e820 2 A

这里的哈希函数我才用了MD5作为例子,并不代表实际场景中会使用同样的哈希算法。

从上面表格的结果来看,10个请求被大致平均的分配到了3台服务器。达到了我们的要求。但这种方法对后端服务器数量的变化毫无应对能力。比如我们增加或者减少一台服务器都会对所有请求的分配造成巨大影响:

请求 哈希值 3台服务器时(A/B/C) 2台服务器时(A/B) 4台服务器时(A/B/C/D)
1 c4ca4238a0b923820dcc509a6f75849b B B D
2 c81e728d9d4c2f636f067f89cc14862c A A A
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 B B C
4 a87ff679a2f3e71d9181a67b7542122c C A A
5 e4da3b7fbbce2345d7772b0674a318d5 A B B
6 1679091c5a880faf6fb5e6087eb1b2dc A A A
7 8f14e45fceea167a5a36dedd4bea2543 A B D
8 c9f0f895fb98ab9159f51fd0297e236d C B B
9 45c48cce2e2d7fbdea1afc51c7c6ad26 C A C
10 d3d9446802a44259755d38e6d163e820 A A A

正如表里情况,增加减少后端都会对分配情况造成巨大的影响。如果后端是无状态的,即服务不依赖任何以往数据,那这种分配的改变仅仅可能是一段时间的分配不均,最后还是会趋于平均。但如果后端是有状态的,比如数据库,那么这种变化将会导致数据要从一台服务器上迁移到其他服务器上来正确响应请求。

这时我们就需要引入一个新的方法,在保持哈希函数特性的同时,又对这种变化有足够的适应性。Consistent hashing就是这样我们这样的方法。他首先保持了哈希函数的特性的同时,用了一种特殊的设计来减少需要迁移状态的数量。

Consistent hashing把它的哈希值域收尾相连成为一个环,以MD5为例,它的哈希值范围时128位0到128位1的二进制,那么我们就可以将最大哈希值128位1的后一个值定位最小值——128位0。这样便形成了一个环。然后我们可以通过如下的步骤确定某个请求应该归属于哪一个服务器:

  1. 把所有的哈希值都放在这个环上对应的位置。这里我们以上表中的一些值举例,如果我们这个环是从0点顺时针计算的话,请求1大概在277度的位置,请求2在281度左右。
  2. 给每个服务器随机的取一个哈希值。同样也放在环上。
  3. 定义一个规则,来确定归属。比如可以是顺时针方向的第一个服务器,当然也可以是逆时针,或者离请求哈希值最近的服务器等等。我们这里以顺时针方向的下一个作为归属规则。我们假设A、B和C的哈希值是:
服务器 哈希值
A 7fc56270e7a70fa81a5935b72eacbe29
B 9d5ed678fe57bcca610140957afab571
C 0d61f8370cad1d412f80b84d143e1257

4. 由于顺时针的哈希值是递增的,我们可以用如下的方式来表示请求和服务器在这个环上从起点开始的位置,以及他们对应的服务器

请求/服务器 哈希值 服务器
C 0d61f8370cad1d412f80b84d143e1257
6 1679091c5a880faf6fb5e6087eb1b2dc A
9 45c48cce2e2d7fbdea1afc51c7c6ad26 A
A 7fc56270e7a70fa81a5935b72eacbe29
7 8f14e45fceea167a5a36dedd4bea2543 B
B 9d5ed678fe57bcca610140957afab571
4 a87ff679a2f3e71d9181a67b7542122c C
1 c4ca4238a0b923820dcc509a6f75849b C
2 c81e728d9d4c2f636f067f89cc14862c C
10 d3d9446802a44259755d38e6d163e820 C
5 e4da3b7fbbce2345d7772b0674a318d5 C
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 C
8 c9f0f895fb98ab9159f51fd0297e236d C

5. 这时你可能发现了一个很明显的问题,即这些请求的分布非常不均。不着急,我们可以对服务器进行虚拟扩展,比如说我们定义A1-A3都是A,B1-B3是B,C1-C3表示C。这时我们不在使用A、B和C,而是使用新定义的9个服务器。让我们重复上两步

请求/服务器 哈希值 服务器
B3 0c4ecd7b59ebc5b9f47974cb9845fd02
6 1679091c5a880faf6fb5e6087eb1b2dc C
C1 1a2ddc2db4693cfd16d534cde5572cc1
A1 27f237e6b7f96587b6202ff3607ad88a
C3 3abe124ecc82bf2c2e22e6058f38c50c
9 45c48cce2e2d7fbdea1afc51c7c6ad26 A
10 d3d9446802a44259755d38e6d163e820 A
A3 6593d7b12fd418cdb35bbf438de72f66
7 8f14e45fceea167a5a36dedd4bea2543 B
4 a87ff679a2f3e71d9181a67b7542122c B
B2 bbd97b00c539801e32317ab550867ec4
1 c4ca4238a0b923820dcc509a6f75849b A
A2 c6bdf6f65f3845da9085e9ae5790b494
2 c81e728d9d4c2f636f067f89cc14862c B
B1 c9512565ef6194ca664dc41ec0de7a53
8 c9f0f895fb98ab9159f51fd0297e236d C
5 e4da3b7fbbce2345d7772b0674a318d5 C
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 C
C2 f1a543f5a2c5d49bc5dde298fcf716e4

6. 可以发现,虽然三台服务器的比重相同,但是我们把他们从1:1:1变成3:3:3时,分配的更加均匀了。我们可以尝试改变这个值来得到一个取值较小但分配也相对平均的数,比如10:10:10。当然也可以让三个值不同,来改变服务器的权重。

7. 我们现在去掉C,情况会变成这样。可以发现,删除的服务器数据当然需要迁移,但是其他的状态都可以保持。

请求/服务器 哈希值 服务器
B3 0c4ecd7b59ebc5b9f47974cb9845fd02
6 1679091c5a880faf6fb5e6087eb1b2dc C->A
A1 27f237e6b7f96587b6202ff3607ad88a
9 45c48cce2e2d7fbdea1afc51c7c6ad26 A
10 d3d9446802a44259755d38e6d163e820 A
A3 6593d7b12fd418cdb35bbf438de72f66
7 8f14e45fceea167a5a36dedd4bea2543 B
4 a87ff679a2f3e71d9181a67b7542122c B
B2 bbd97b00c539801e32317ab550867ec4
1 c4ca4238a0b923820dcc509a6f75849b A
A2 c6bdf6f65f3845da9085e9ae5790b494
2 c81e728d9d4c2f636f067f89cc14862c B
B1 c9512565ef6194ca664dc41ec0de7a53
8 c9f0f895fb98ab9159f51fd0297e236d C->B
5 e4da3b7fbbce2345d7772b0674a318d5 C->B
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 C->B

8. 类似的,我们增加D,组成3:3:3:3。同样的,只有部分数据小部分数据需要迁移

请求/服务器 哈希值 服务器
B3 0c4ecd7b59ebc5b9f47974cb9845fd02
6 1679091c5a880faf6fb5e6087eb1b2dc C
C1 1a2ddc2db4693cfd16d534cde5572cc1
A1 27f237e6b7f96587b6202ff3607ad88a
C3 3abe124ecc82bf2c2e22e6058f38c50c
9 45c48cce2e2d7fbdea1afc51c7c6ad26 A->D
D1 4a4079e06eb2f7ba7a12821c7c58a3f6
10 d3d9446802a44259755d38e6d163e820 A
A3 6593d7b12fd418cdb35bbf438de72f66
7 8f14e45fceea167a5a36dedd4bea2543 B->D
D3 a3deb6e481689f1d3303caecb8a6c401
4 a87ff679a2f3e71d9181a67b7542122c B
B2 bbd97b00c539801e32317ab550867ec4
1 c4ca4238a0b923820dcc509a6f75849b A->D
D2 c4d62b6dcca08e5caf06c01889282859
A2 c6bdf6f65f3845da9085e9ae5790b494
2 c81e728d9d4c2f636f067f89cc14862c B
B1 c9512565ef6194ca664dc41ec0de7a53
8 c9f0f895fb98ab9159f51fd0297e236d C
5 e4da3b7fbbce2345d7772b0674a318d5 C
3 eccbc87e4b5ce2fe28308fd9f2a7baf3 C
C2 f1a543f5a2c5d49bc5dde298fcf716e4

如果上面的比较不明显,可以尝试1000条请求和10:10:10这样的额比例,看看普通的哈希和consistent hashing需要迁移的数据量的区别。甚至扩展到10万请求和50:50:50这样的比例来比较。这种方法的优势会相对更加明显。

Ken lai

Read more posts by this author.