普通Hash算法

我们在实现服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法.

典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。

分配的的原则就是，通过计算请求的hash值来决定请求由哪一台服务器来服务serverID=hash(key_request)%numberOfServer这种方法的缺点很明显，系统的容错性和扩展性非常低。如果需要新增服务器，那么之前N台服务器的缓存资源需要重新hash计算，同理如果减少服务器，那么也需要重新计算。

class HashServer:
    def __init__(self, numberOfServer=1):
        self.numberOfServer=numberOfServer

    def hashServer(self, request):
        serverID=hash(request)%self.numberOfServer
        return serverID

一致性hash算法

可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。一致性哈希算法通过一个叫作一致性哈希环的数据结构实现。这个环的起点是 0，终点是 2^32 – 1，并且起点与终点连接，故这个环的整数分布范围是 [0, 2^32-1]，如下图所示：

将请求对象放置到hash环上

假设我们有 “semlinker”、”kakuqo”、”lolo”、”fer” 四个对象，分别简写为 o1、o2、o3 和 o4，然后使用哈希函数计算这个对象的 hash 值，值的范围是 [0, 2^32-1]：

图中请求的映射关系如下：

hash(o1) = k1; 
hash(o2) = k2;
hash(o3) = k3; 
hash(o4) = k4;

将服务器放置到hash环

接着使用同样的哈希函数，我们将服务器也放置到哈希环上，可以选择服务器的 IP 或主机名作为键进行哈希，这样每台服务器就能确定其在哈希环上的位置。这里假设我们有 3 台缓存服务器，分别为 cs1、cs2 和 cs3：

图中服务器的映射关系如下：

hash(cs1) = t1; 
hash(cs2) = t2; 
hash(cs3) = t3; # Server

为对象选择服务器

将对象和服务器都放置到同一个哈希环后，在哈希环上顺时针查找距离这个请求的 hash 值最近的机器，即是这个对象所属的机器。 以o2对象为例，顺序针找到最近的机器是 cs2，故服务器cs2会缓存 o2 对象。而服务器 cs1 则缓存 o1，o3 对象，服务器 cs3 则缓存 o4 对象。

服务器增加的情况

假设由于业务需要，我们需要增加一台服务器 cs4，经过同样的 hash 运算，该服务器最终落于 t1 和 t2 服务器之间，具体如下图所示：

对于上述的情况，只有 t1 和 t2 服务器之间的对象需要重新分配。在以上示例中只有 o3 对象需要重新分配，即它被重新到 cs4 服务器。在前面我们已经分析过，如果使用简单的取模方法，当新添加服务器时可能会导致大部分缓存失效，而使用一致性哈希算法后，这种情况得到了较大的改善，因为只有少部分请求需要重新分配。

服务器减少的情况

假设 cs3 服务器出现故障导致服务下线，这时原本存储于 cs3 服务器的对象 o4，需要被重新分配至 cs2 服务器，其它对象仍存储在原有的机器上。

虚拟节点

到这里一致性哈希的基本原理已经介绍完了，但对于新增服务器的情况还存在一些问题。新增的服务器 cs4 只分担了 cs1 服务器的负载，服务器 cs2 和 cs3 并没有因为 cs4 服务器的加入而减少负载压力。如果 cs4 服务器的性能与原有服务器的性能一致甚至可能更高，那么这种结果并不是我们所期望的。同时，如果需要减少服务器的数量，那么不可避免的需要进行数据迁移，当有大量数据的时候，这是不可接受的。

针对这个问题，我们可以通过引入虚拟节点来解决负载不均衡的问题。即将每台物理服务器虚拟为一组虚拟服务器，将虚拟服务器放置到哈希环上，如果要确定对象的服务器，需先确定对象的虚拟服务器，再由虚拟服务器确定物理服务器。

图中 o1 和 o2 表示对象，v1 ~ v6 表示虚拟服务器，s1 ~ s3 表示物理服务器。

当需要增加或者减少物理节点的时候，只需要修改虚拟节点对应的物理节点，同时请求到达虚拟节点的请求也会达到均衡的效果。

类似文章