一致性哈希

#软件架构与思考

2014-06-05

我们以动态网站的静态化为例子。

如果一个网站的是大部分内容是动态生成的，但是网站的已有内容又是很少改变的。如果用户每次访问都需要服务器动态的生成网页，怎么想都是一件很浪费资源的事情。很明显，将这些内容静态化能够很大程度上减少网站的负载，提升网站访问速度。wordpress用户使用WP Super Cache插件优化网站就是这么一个道理。

另外，如果网站内容很多，多到不适合在一台机器上存储静态化的网页，那么有必要将这些静态化网页合理的分配到多台机器上。设定静态化的网页共有6000个，依次为1.html、2.html、...、6000.html，需要将这些网站合理分配到3台服务器上存储。可以将这6000个网页看成是键值对，网页名（例如1.html）是键，网页内容是值。这三台机器依次标号为0、1、2。通过下面的函数我们确定将一个网页存放到哪个服务器上：

# python 代码
def my_hash(key):
    key = key.replace('.html', '')
    return int(key) % 3

函数的参数是网页的名称，int(key)%3是得到的这个网页的哈希值（真实情况下，哈希值的计算会复杂很多），因为有三台服务器，所以用3进行取模运算，最终的返回值也就是key对应的网页应该存储的服务器的服务器序号。

由此，1.html、4.html、7.html、10.html等网页存在服务器1中，2.html、5.html、8.html、11.html等网页存在服务器2中，3.html、6.html、9.html、12.html等网页存在服务器0中。用表格表示如下：

现在考虑一下增加服务器的情况。我们将增加的服务器标号设为3，my_hash函数成了下面的样子：

# python 代码
def my_hash(key):
    key = key.replace('.html', '')
    return int(key) % 4

现在的网页分配情况如下：

可以看到，有1/4的静态网页被重新分配到服务器3中。1/4是一个不小的量。实际情况中，远远不是只需要迁移1/4的数据这么简单，因为服务器0、1、2内的缓存也重新分布了。**原先的在服务器0的网页，现在通过hash，只能命中12.html，服务器1、2类似。这意味着对于服务器0、1、2有3/4的缓存无法命中。**假设每个服务器以<网页名，网页内容>的形式存储静态网页，那么添加服务器时候需要所有的服务器的所有网页使用my_hash函数重新映射，判断是否应该重新迁移到服务器3中。这其中的“重新映射”也是一个不可忽略的开销。

要减少上面方法的，一致性哈希是一个很好的解决方法。

在上面的示例中，如果有四台服务器，那么我们对网页哈希后的取值空间是0、1、2、3。现在我们改一下，将这个哈希空间改为0到31，并假设服务器永远不会超过32台（如果服务器是上百台，我们可以将哈希空间更改成更大，例如0~2000000）。新的my_hash函数如下：

# python 代码
def my_hash(key):
    key = key.replace('.html', '')
    return int(key) % 32

同时，假设四台服务器服务器被标号为A、B、C、D，我们给这四台服务器（或者说服务器）也分配哈希值，分别是2、10、18、26。然后，将0~31这个哈希空间改成圆环，如下所示：

那么现在如何分配一个静态网页？方法是：取得这个静态网页的哈希值，把这个值放在上图中环的相应位置，然后顺时针地走，遇到的第一个服务器，就是这个网页要存储的位置。

根据这个方法，1.html、28.html会存放在服务器A上，5.html、37.html会存放在服务器B中，11.html、12.html、……、18.html会存放在服务器C中。

在这种情况下，由于使用my_hash计算的网页的哈希值是不变的，可以考虑也将哈希值持久化。

现在添加一个服务器E，分配哈希值15，则圆环变成了：

这时候，原本应该存储在服务器C中的11.html、12.html、……、15.html就要迁移到服务器E中。 按照之前的方法，大致有1/5的静态网页会发生迁移，而现在，大致有5/32的网页发生迁移。可见迁移量有所减少。另外一方面，只需要对服务器C的网页重新分配，而不是将所有的6000个网页重新计算并考虑如何分配。

以上就是一致性哈希的主要思想。

不过，上面的一致性哈希带来了负载不均衡的问题。以下是五个服务器存储静态网页量所占的百分比：

很明显，五个服务器的存储量不再均衡。要解决这个问题，需要引入虚拟节点的概念。

虚拟节点算是一种虚拟化。如果我们有4台服务器，一个服务器虚拟出三个服务器（也就是三个虚拟节点），总共12个“虚拟节点”，而放在哈希环的不再是真实的服务器，而是“虚拟节点”。为达到效果，相邻的三个虚拟节点应尽量不属于同一个服务器。现在，每个虚拟节点的负载比率可能如下：

1/12
1/12
1/12
1/12
1/12
1/12
1/12
1/12
1/12
1/12
1/12
1/12

当我们新添一个服务器，相当于新添加3个虚拟节点。现在的每个虚拟节点的负载比率可能如下：

1/24
1/12
1/24
1/12
1/24
1/12
1/24
1/12
1/24
1/12
1/24
1/12
1/12
1/12
1/12

将虚拟节点映射到真实的服务器上，这五台服务器的负载可能如下：

4/24
5/24
4/24
5/24
6/24

这种情况下，负载均衡问题已经有很大的改善。其原因就在于，新添加服务器后，需要迁移的数据来自于多个其他服务器。而虚拟节点的存在又使得需要重新计算哈希值的网页数量仍是上面的“一致性哈希”中的水平。

( 本文完 )