流量控制是任何复杂系统都必须考虑的问题。本文对不同的流控算法进行介绍和比较，以帮助我们根据系统需求和架构选择合适的方案。原文：DistributedRate-LimitingAlgorithms[1]我们在设计分布式限速系统（distributedrate-limitingsystem）时，需要用到哪些工具和算法？JoshuaHoehne@UnsplashCriteo是世界上最大的广告技术公司之一。随着广告市场的不断发展，Criteo在过去几年一直致力于改进API，以帮助客户更好地通过可编程接口访问他们需要的服务。随着越来越多的客户端使用新的API，很明显需要实施某种流量控制以确保所有客户端对资源具有平等的访问权限并保护API免受频繁（恶意或错误）调用。流量控制看起来很简单：只允许给定的客户端每分钟进行X次调用。在单个服务器实例上实现流量控制非常容易，你可以很容易地找到相关的库来实现它。但问题是我们的API托管在6个数据中心（欧洲、北美和亚洲），每个数据中心都有多个实例，这意味着我们需要某种分布式流量控制系统。流量控制不仅与调用次数有关，还需要与客户端同步当前受限状态（例如，使用专用的标头和状态码）。但本文将主要关注用于流量控制的算法和系统。使用负载平衡在尝试开发自己的系统之前，更重要的是查看现有的基础设施是否能够提供所需的特性。那么，是什么部署在数据中心所有实例的前面，并且已经负责流量的检测和路由呢？负载均衡器。大多数负载均衡器都提供流量控制功能或某种可用于实现流量控制的抽象。例如，HAProxy有开箱即用的sticktables[2]，可以用来设置流量控制，同步实例之间的状态，并且工作得很好。不幸的是，负载均衡不支持我们需要的一些特性（动态节流、令牌内省……），所以我们需要自己实现这些特定的需求。基本解决方案Stickysessions当谈到负载平衡时，如果给定的客户端是不平衡的并且总是与单个实例交互，那么就不需要分布式流量控制系统。大多数客户端访问最近的数据中心（通过geo-DNS），如果在负载均衡器上启用了“粘性”，客户端应该总是访问同一个实例，在这种情况下我们可以使用简单的“本地”速率限制。这在理论上可行，但在实践中行不通。Criteo系统面临的负载不是恒定的，例如黑色星期五/网络周是一年中最重要的时间。在此期间，该团队随时准备扩展基础架构以满足客户不断增长的需求。但是会话粘附和可伸缩性不能很好地结合在一起（如果所有客户端都粘在旧实例上，创建新实例有什么意义？）使用更智能的会话粘附（在扩展时重新分配令牌）会有所帮助，但这意味着每次扩展向上，客户端可能会切换到另一个实例，并且不知道客户端对前一个实例进行了多少次调用。从本质上讲，这会导致我们每次扩展时的流量控制都不一致，每次系统有压力时，客户端可能会进行更多调用。Chatty服务器如果客户端可以访问任何实例，则意味着“调用计数”必须在实例之间共享。一种选择是让每个实例调用所有其他实例，请求给定客户端的当前计数并将其相加。另一种方案正好相反，每个服务器向其他服务器广播“计数更新”。这产生了两个主要问题：您拥有的实例越多，您需要进行的调用就越多。每个实例都需要知道其他实例的地址，并且每次服务扩展或缩减时都必须更新地址。虽然可以实施此解决方案（本质上是点对点环，许多系统已经实施），但成本很高。如果Kafka不希望每个实例都与其他实例通信，可以使用Kafka来同步所有实例中的计数器。例如，当一个实例被调用时，一个事件被推送到相应的主题。这些事件通过滑动窗口聚合（KafkaStream在这方面做得很好），每个客户端最后一分钟的最新计数被发布到另一个主题。然后每个实例通过该主题获得所有客户端的共享计数。问题是Kafka本质上是异步的，虽然通常很少有延迟，但当API上的负载增加时，它会增加延迟。如果实例使用过时的计数器，则可能会错过本应阻止的调用。这些解决方案都有一个共同点：它们在一切正常时运行良好，但在过载时性能下降。我们的大部分系统都是这样设计的，通常不会有问题，但流量控制不是一个典型的组件，目标是保护系统的其他部分免受这种过载的影响。流量控制系统的目标是在系统负载较重时正常工作，它是为服务于最差的1%而不是99%的良好情况而构建的。分布式算法我们需要一个中心化的同步存储系统和一个算法来为每个客户端计算当前的费率。内存缓存（如Memcached或Redis）是一个理想的系统，但并不是所有的流量控制算法都可以在缓存系统中实现。让我们看看有什么样的算法。为简单起见，让我们考虑尝试实现“每分钟100次调用”流量控制。查看可用的工具。BarnImages@UnsplashSlidingwindowviaeventlog如果您想知道客户端在过去一分钟内进行了多少次调用，您可以在缓存中存储每个客户端的时间戳列表。每次调用时，都会将相应的时间戳添加到列表中。然后循环遍历列表中的每个项目，丢弃超过一分钟的项目，并计算新项目。:+1:优点：非常精确和简单:-1:缺点：需要强大的事务支持（处理同一个客户端的两个实例需要更新同一个列表）。根据调用的限制和次数，存储对象（列表）的大小可能会非常大。性能不稳定（更多调用意味着要处理更多时间戳）。固定窗口（Fixedwindow）大多数分布式缓存系统都有特定的、高性能的“计数器”抽象（一个可以自动递增的整数值，附加到一个字符串键上）。使用“{clientId}”键为每个客户端维护一个计数器非常容易，但它只会计算自计数器创建以来客户端调用的次数，而不是最后一分钟的次数。以“{clientId}_{yyyyMMddHHmm}”为key，可以每分钟为客户端维护一个计数器（换句话说：固定窗口1分钟），找到当前时间对应的计数器就可以告诉我们这一分钟client端执行的调用次数，如果这个值超过上限，可以阻塞调用。请注意，这与“最后一分钟”不同。如果在07:10:23AM有呼叫，则固定窗口计数器显示07:10:00AM和07:10:23AM之间的呼叫数。但我们真正想要的是早上07:09:23到07:10:23之间的调用次数。在某种程度上，固定窗口算法“忘记”了每分钟之前有多少次调用，因此客户端理论上可以在07:09:59进行100次调用，然后在07:10:00进行100次调用。:+1:优点：非常快（单个原子增量+读取操作）只有非常基本的事务支持（原子计数器）稳定和简单:-1:缺点：不准确（将允许最多2次调用）令牌桶（令牌桶）返回1994年，你爸妈送你去游戏厅和朋友玩《超级街霸2》。他们给你一小桶5美元的硬币，然后去街对面的酒吧，每小时过来一次，把5美元的硬币扔进桶里。所以你基本上只能以每小时5美元的价格玩游戏（希望你擅长《街头霸王》）。这是“令牌桶”算法背后的主要思想：与简单的计数器不同，“桶”存储在每个客户端的缓存中。桶是一个包含两个属性的对象：剩余“令牌”的数量（或可以进行的剩余调用次数）和最后一次调用的时间戳。调用API时，取出桶，根据本次调用与上次调用的时间间隔，向桶中添加新的token，如果有多余的token，则递减允许调用。所以，与《街头霸王》的例子相反，没有“家长”分分钟帮我们装满桶。在消耗令牌的同一操作中有效地重新填充桶（令牌的数量对应于自上次调用以来的时间间隔）。每分钟100次调用的限制意味着如果最后一次调用是在半分钟前，将向桶中添加50个令牌。如果桶太“旧”（自上次调用后超过1分钟），令牌计数将重置为100。实际上，在初始化时可以填充超过100个令牌（但补充速率为100个令牌/minute)：这个类似于“突发”功能，允许客户端小时间超过流量控制限制，但不能长期维持。注意：正确计算要添加的令牌数量很重要，否则有错误填充桶的风险。该算法在提供可靠性能的同时提供了完美的准确性，主要问题是需要事务（您不希望两个实例同时更新缓存的对象）。具有100次调用/分钟的令牌桶的分步示例：+1：优点：非常精确、快速和稳定的性能优化初始令牌数量可以允许客户端“突发”调用：-1：缺点：更复杂需要强大事务支持漏桶：该算法的另一个版本。在此版本中，调用在桶中累积并以恒定速率（匹配速率限制）处理。如果桶溢出，呼叫将被拒绝。这实现起来更复杂，但可以减轻服务的负载（这可能是您想要的，也可能不是您想要的）。:trophy:最好的算法？比较这三种算法，令牌桶似乎在性能和准确性方面提供了最好的折衷。但这只有在系统提供良好的事务支持的情况下才有可能。如果你有一个Redis集群，这是完美的解决方案（你甚至可以实现一个基于Lua的算法，直接在Redis集群上运行以提高性能），但Memcached只支持原子计数器，不支持事务。可以基于Memcached[3]实现一个乐观并发（optimisticconcurrent）版本的令牌桶，但是这样比较复杂，而且乐观并发在重负载下性能会下降。用固定窗口近似滑动窗口如果没有强大的事务支持，是不是就注定了使用不准确的固定窗口算法？有点，但还有改进的余地。请记住，固定窗口的主要问题是它“忘记”了每一分钟之前发生的事情，但我们仍然可以访问相关信息（在前一分钟的计数器中），因此可以通过计算加权平均值来估算前一分钟的呼叫数。通过组合一个60s的固定窗口来近似模拟一个60s的滑动窗口示例：如果在00:01:43调用，递增得到“00:01”计数器的值。由于这是当前日历分钟，它现在包含00:01:00和00:01:43之间的呼叫数（最后17秒尚未发生）。但我们想要的是60秒滑动窗口中的调用次数，这意味着我们错过了从00:00:43到00:01:00的计数。为此，我们可以读取“00:00”计数器并将其调整为17/60倍，从而表明我们只对最后17秒感兴趣。如果负载恒定，这种近似是完美的。但是如果大部分调用都集中在前一分钟，你会得到一个高估的值。而当大部分呼叫都集中在前一分钟结束后，这个数字就会被低估。比较为了更准确地了解精度差异，最好在相同条件下模拟两种算法。下图显示了“固定计数器”算法在提供随机流量时将返回的内容。灰线是一个“完美”滑动窗口的输出，它在任何时间点对应于过去60秒内的调用次数，这就是我们的目标。橙色虚线表示固定窗口算法对同一流的“计数”。它们的输出在第一分钟是相同的，但很快你就会看到固定窗口版本在分钟标记处有很大的下降。固定窗口算法很少超过100次调用限制，这意味着允许许多调用，否则将被阻止。下图表示相同的场景，具有相同的流量，但具有近似的滑动窗口。同样，灰线代表“完美”的滑动窗口。橙色虚线表示近似算法。每分钟标记附近没有更多的下降，你可以看到新版本的算法更接近完美算法，有时高一点，有时低一点，但总体来说是一个巨大的改进。收益递减，但我们能做得更好吗？我们的近似算法只使用当前和之前固定的60秒窗口。但是，也可以使用几个更小的子窗口，一个极端的做法是使用60个1s的窗口来重构最后一分钟的流量。显然这意味着每次调用都要读取60个计数器，这将增加巨大的性能成本。然而，我们可以选择任何固定的时间窗口来拟合近似值。窗口越小，需要的计数器越多，近似值就越准确。让我们看看组合五个15秒窗口会发生什么：正如预期的那样，准确性有所提高，但仍不完美。我们处于经典的更高准确度=更差性能的情况下。没有绝对的最佳方案，必须平衡精度和性能的要求，找到最合适的方案。如果您只关心保护您的服务不被过度使用，而不需要持续控制，那么即使是最简单的固定窗口也可能是一个可行的解决方案。结论流量控制是一个非常容易描述但隐藏了很多复杂性的属性。我希望本文能帮助您了解在复杂的分布式系统中实现流控制所涉及的工具和算法。
