前一篇文章介绍了系统的两种扩展模式，垂直扩展和水平扩展。本节将介绍采用水平扩展方式的负载均衡和一致性哈希的概念。
初步设计
负载均衡的含义为将客户端的请求平均分散到每个服务器上。假设系统接收到的请求数为M，初始的服务器数量为N，那么我们可以很直接的想到以下的负载均衡方法：将每个请求的ID进行Hash，然后对N取模，得到的结果即为该请求应该发送的服务器ID。
假如服务器的数量N=4，那么负载均衡的示意图如下：
节点数量变化
上述的方法在服务器的数量不变时，可以实现负载均衡的功能。但当节点变化时，例如服务器的数量从4增加到5，如果采用上述的Hash算法的话，从饼图可以看出，原本服务器0上的5%的请求，会发送到服务器1上；服务器1的10%的请求，会发送到服务器2上；服务器2的15%的请求，会发送到服务器3上；服务器3的20%的请求，会发送到新添加的服务器4上。
由于新增加了一个服务器，使得请求最终发送到的服务器发生了巨大的变化，有50%的请求都发送到了其他服务器上。如果我们的系统并不关心是由哪台服务器处理这个请求，那是没有问题的。
但在通常情况下，我们可能会在系统中针对某个请求进行缓存，比如这是一个用户鉴权的服务，我们会把鉴权的相关信息存储在服务器的内存中，以提高性能。如果发生了服务器的变化，不仅需要重新获取用户的权限信息，之前保留的缓存也会有部分失效。因此采用这种负载均衡的方式，在节点数量变化时，对系统的运行产生了较大的影响。
改进设计
既然增加了一个服务器，就一定会有一些原本发送的已有服务器的请求，发送到新的服务器上，这是不可避免的。我们思考的是如何才能将这些请求的比例控制在最低。从下面的饼图看出，将发送到原服务器的请求，每个拿出5%发送到新服务器上，这样总共只有20%的请求改变了最终发送的服务器，如果采用这种方式处理服务器数量的变化，是最优的负载均衡方式。
改进设计的实现
为了实现上述的设计，我们采用的方法称为一致性哈希。通过将服务器ID进行哈希，然后对M取模，得到一个哈希值，该值为下图中圆环中的一点，用黑线表示。对所有服务器做同样的处理，得到每个服务器在圆环上对应的点。此时，在接收到一个请求后，根据请求ID计算哈希值，在圆环上用红线表示，再按顺时针方向寻找临近的服务器，作为该请求发送的目标服务器。
如果新增一个服务器s4，采用同样的方法将s4的哈希值标记为圆环的一点。如上图所示，原本发送到s0的请求，便有一部分发送到s4上，而发送到其他三个服务器的请求将不受影响。
上图存在的一个问题是，虽然说理论上N个服务器，可以将每个服务器的负载降低到原来的1/N，但是无论采用什么哈希算法，计算出的每个服务器的哈希值间距都是不相等的，在圆环上的分布是不均匀的，导致各个服务器的负载并不均衡。
那将如何解决这个问题呢：采用多种哈希算法。
假设我们使用两种哈希算法h1和h2，每个服务器对应在圆环上的两个点。将请求ID进行哈希后，同样顺时针查找最近的服务器，由于此时服务器的哈希值增多了一倍，在圆环上的分布比之前要更加均匀，负载不均衡的现象将得到改善。如果哈希算法的数量足够多，这里一般取K = log(N)，那就会得到类似于第三张图的效果，每个原服务器的相同比例的请求，发送到新服务器上。
同样，如果减少服务器的数量，和增加服务器数量是同理的。
小结
以上便是关于分布式系统中良好的负载均衡的实现，采用的方法称为一致性哈希算法，通过将服务器ID和请求ID同时进行哈希计算，寻找同一方向最临近值的方法，最大程度上避免了在服务器数量变化时，请求发送的目标服务器出现大规模变化。
欢迎大家订阅专题，其中包含了系统设计基础系列的全部文章：System Design
