一致性哈希算法及其PHP实现的详细分析

在进行服务器负载均衡时，有许多负载均衡算法可供选择，包括循环法、哈希法、最少连接法、响应时间法、加权法等。哈希算法是最常用的算法，典型的应用场景是有N台服务器提供缓存服务，因此需要对服务器进行负载均衡，将请求平均分配给每台服务器，每台机器负责1/N的服务。通常的算法是取散列结果的余数(hash() mod N):对于编号从0到N-1的机器，根据自定义的hash()算法，将每个请求的hash()值取模N，得到余数I，然后将请求分发到编号为I的机器上.然而，这样的算法有致命的问题。如果某台机器发生故障，应该落在该机器上的请求将无法正确处理。此时，需要从算法中删除故障服务器。此时需要重新计算(N-1)/N台服务器的缓存数据。如果添加了新机器，则需要重新计算N/(N+1)个服务器的缓存数据。对于系统来说，这通常是不可接受的抖动(因为这意味着大量缓存故障或数据需要传输)。那么，如何设计一个负载平衡策略来使受影响的请求尽可能少呢？在LVS Bittorrent DHT的Memcached、Key-Value Store中采用了一致哈希算法，可以说一致哈希是分布式系统负载均衡的首选算法。1.一致哈希算法的描述下面是Memcached中一致哈希算法的一个例子。由于哈希算法的结果一般是无符号的int类型，哈希函数的结果应该均匀分布在[0，232-1]之间。如果我们用232个点均匀地切一个圆，首先根据hash(key)函数计算服务器(节点)的哈希值，分配到从0到232的圆上。使用相同的hash(key)函数找到需要存储数据的键的哈希值，并将其映射到圆。然后从数据映射的位置顺时针搜索，将数据保存到找到的第一个服务器(节点)。

当一个节点被添加到一致哈希的示意图中时，只有逆时针方向的第一个节点的数据会受到影响。删除节点时，只会影响环上原删除节点顺时针方向的第一个节点的数据。因此，一致哈希很好地解决了负载均衡中添加和删除节点带来的哈希值碰撞问题。

一致哈希(Consistent Hashing)在服务器图中增加虚拟节点：引入虚拟节点的原因是当服务器(节点)数量较少时(例如只有三个服务器)，通过hash(key)计算的节点哈希值在环上分布不均匀(稀疏)，仍然会存在各节点负载不均衡的问题。虚拟节点可以看作是实际节点的复制品，与实际节点本质上是一样的(密钥不一样)。引入虚拟节点后，将实际服务器(节点)的数量按一定比例(例如200倍)放大，计算出其hash(key)值均匀分布在环上。在负载平衡中，落在虚拟节点上的哈希值实际上落在实际节点上。由于将所有的实际节点按照相同的比例复制成虚拟节点，解决了节点数少时哈希值在环上均匀分布的问题。

虚拟节点对一致哈希结果的影响从上图可以看出，当节点数为10，每个实际节点的虚拟节点数是实际节点的100-200倍时，结果非常均衡。第三段有这样的话：“但是，这个算法有致命的问题。如果某台机器发生故障，应该落在该机器上的请求将无法正确处理。此时，需要从算法中删除故障服务器。此时需要重新计算(N-1)/N台服务器的缓存数据；”为什么是(N-1)/N？解释如下：例如，有3台机器，哈希值1-6在这3台机器上的分布是：主机1: 1 4主机2: 25主机： 3 6。如果一台机器挂机，只剩下两台，模数为2，则分布为：主机1: 1 3 5主机2: 2 4 6。可以看到，只有2个不变的数据位置：1和2，4个变了的数据位置，占了总共6个数据的4/6=2/3。在这种情况下，受影响的数据太多，因此需要将太多的数据从数据库重新加载到缓存中，这将严重影响性能。【一致哈希法】上面提到的哈希模比较小。一般是负载数，而一致哈希的本质是取模大一些，就是2的32次方减1，也就是最大的32位整数。然后，你可以冷静地安排数据方向，图形相当直观。以下部分是一致哈希算法的PHP实现。点击下载。