两个随机选择的力量

在许多大型Web服务中，多层无状态和有状态服务由负载均衡器分隔。负载平衡可以使用专用硬件、使用专用软件负载平衡器、使用DNS技巧或通过客户端中的负载平衡机制来实现。在大型系统中，每一层的资源和约束可能差别很大。有些层是无状态的，可以很容易地水平扩展到许多机器。由于需要访问状态或争用某些其他共享资源，其他层可能会受到更多限制。

集中式负载平衡解决方案可以很好地将负载分布在一组机器上。它们跟踪它们发送到每台机器的负载量(通常基于简单的测量，如连接计数)。因为它们是集中式的，所以负载平衡器通常不需要担心从其他来源发送的负载。他们完全控制着荷载的分配。

尽管有这一优势，专用负载均衡器通常是不受欢迎的。它们增加了成本、延迟和复杂性，并可能引入单点故障。将负载平衡任务交给每个上游客户端也是可能的，但会带来从多个地方公平平衡负载的挑战。在具有大量客户端和相当同类调用的大型系统中，纯随机系统(如DNS循环调度)可以非常好地工作。在较小的系统中，在每个下游服务只能处理少量或并发请求的系统中，以及在请求是异构的系统中，负载平衡通常比随机负载平衡更好。

通过跨所有客户端分发有关系统负载的信息，可以实现完美的分布式负载平衡，至少在令人满意的情况下是这样。在不同的源之间不断共享准确的负载信息的开销可能很高，因此让每个源在一个缓存副本中工作是很有诱惑力的。此数据可以从下游或其他客户端定期刷新。

“两个随机选择的力量：技术和结果的调查”，Mitzenmacher et。艾尔。调查了一些与这个问题非常相关的研究。整个调查都很好读，但最有趣的结果之一是关于延迟数据(如上面提到的缓存负载结果)对负载平衡的影响。回想起来，结果相当合乎逻辑，但可能与大多数工程师的最初预期不符。

使用陈旧数据进行负载平衡会导致群组行为，在这种情况下，请求将向以前安静的主机聚集的时间比使该主机真正变得非常繁忙所需的时间长得多。下一次刷新缓存的加载数据将把服务器放在负载列表的最前面，并且它将再次变得安静。然后又忙碌起来，因为下一群牛群看到这里很安静。忙着呢。安静。忙着呢。安静。诸若此类。

一种可能的解决方案是完全放弃负载平衡，只需随机选择一台主机。根据负载率的不同，这可能是一个很好的方法。然而，对于许多典型的负载，选择随机主机会降低延迟并减少吞吐量，因为这会浪费服务器上的资源，而这些资源最终会以不幸和安静告终。

Mitzenmacher调查的研究采取的方法是尝试两个主机，然后选择负载最小的一个。这可以直接完成(通过查询主机)，但在缓存的加载数据上也运行得出奇地好。

为了说明这是如何工作的，我对一个非常简单的系统进行了模拟。每隔一秒就有一个请求到达具有10台服务器的系统。每8秒从服务器上的队列中删除最早的请求(如果有)。负载平衡是使用服务器队列长度的缓存副本完成的，每N秒更新一次。我考虑了四种方法：选择一个随机服务器，选择最好的服务器，两个随机选择中最好的和三个随机选择中最好的。

正如您所预期的那样，当有完美的、未延迟的信息可用时，选择最好的方法效果最好。在相同的情况下，随机挑选方法的效果很差，导致了所有方法中最糟糕的排队时间。随着数据年龄的增加，挑选最好的方法会因为羊群效应而变得越来越差，很快就会超过随机方法成为最差的方法。

三局四胜排在第二位，表现不错。它获得了第一名，但随着延迟的增加，它被让给了2胜2负的结果。显然，当k接近服务器数量时，k中最佳的行为将接近Best的行为。在此模拟结束的过程中，2胜2取始终是强有力的引导者。在给定这些参数的情况下，它将在刷新间隔70左右开始输给随机方法。它在从10到70的区间内是明显的领先者，对于这样一个简单的方法来说，这是一个令人印象深刻的表现。

二选一是好的，因为它结合了两种方法的优点：它使用关于负载的真实信息来选择主机(与随机不同)，但比其他两种方法更强烈地拒绝羊群行为。

看看两个随机选择的力量，以获得更有力的数学论证，以及一些更令人惊讶的地方，这个算法真的工作得很好。