共计 5255 个字符，预计需要花费 14 分钟才能阅读完成。
流控是任何一个简单零碎都必须思考的问题，本文介绍并比拟了不同的流控算法，从而帮忙咱们能够基于零碎需要和架构抉择适合的计划。原文：Distributed Rate-Limiting Algorithms[1]
当咱们设计分布式流控系统（distributed rate-limiting system）时，须要用到哪些工具和算法？
Criteo 是寰球最大的广告技术公司之一，随着广告市场的一直倒退，Criteo 在过来几年里始终致力于改良 API，帮忙客户更好的通过可编程接口拜访须要的服务。
随着越来越多的客户应用新的 API，很显著，须要实现某种流量管制，以确保所有客户端都能平等拜访资源，并爱护 API 免受 (歹意或谬误的) 频繁调用。
流控仿佛很简略: 只容许给定的客户端每分钟执行 X 个调用。在单个服务器实例上实现流控非常容易，能够很容易找到相干的库来实现。但问题是咱们的 API 托管在 6 个数据中心(欧洲、北美和亚洲)，每个数据中心都有多个实例，这意味着咱们须要某种分布式流控系统。
流控不仅与调用次数无关，还须要和客户端同步以后被限度的状态(例如，应用专用的报头和状态码)。然而本文将次要关注用于流控的算法和零碎。
利用负载平衡
在尝试开发本人的零碎之前，更重要的是查看现有的基础设施是否可能提供想要的个性。
那么，部署在数据中心所有实例之前，并且曾经在负责查看、路由流量的是什么？负载均衡器。大多数负载均衡器都提供了流控个性或某种可用于实现流控的形象。例如，HAProxy 有现成的可用于设置流控的 stick tables[2]，能够在实例之间同步状态，并且工作得很好。
可怜的是，负载平衡不反对咱们须要的某些个性(动静限度、令牌自省 token introspection、……)，因而咱们须要本人实现这些特定的需要。
高级计划
会话粘连（Sticky sessions）
说到负载平衡，如果给定客户端的负载并不平衡，并且总是与单个实例交互🤓，那么就不须要分布式流控系统。大多数客户端拜访间隔最近的数据中心(通过 geo-DNS)，如果在负载均衡器上启用“stickiness”，客户端应该总是拜访雷同的实例，这种状况下咱们能够应用简略的“本地”速率限度。
这在实践上可行，但在实践中行不通。Criteo 零碎面临的负载不是恒定的，例如，彩色星期五 /Cyber Week 是一年中最重要的时段。在此期间，团队随时处于戒备状态，筹备扩充基础设施，以应答客户一直增长的需要。然而会话粘连和可伸缩性不能很好的配合(如果所有客户端都粘连在旧实例上，那么创立新实例又有什么用呢?)
应用更智能的会话粘连 (在扩大时重新分配令牌) 会有所帮忙，但这意味着每次扩大时，客户端都可能切换到另一个实例上，而且并不知道客户端在前一个实例上执行了多少调用。实质上说，这将使咱们的流控在每次伸缩时不统一，客户端可能在每次零碎面临压力时会进行更多调用。
Chatty 服务器
如果客户端能够拜访任何实例，意味着“调用计数”必须在实例之间共享。一种计划是让每个实例调用所有其余实例，申请给定客户端的以后计数并相加。另一种计划反过来，每个服务器向其余服务器播送“计数更新”。
这会造成两个次要问题:
- 实例越多，须要进行的调用就越多。
- 每个实例都须要晓得其余实例的地址，并且每次服务扩缩容时都必须更新地址。
尽管能够实现这个解决方案(实质上是一个点对点环，许多零碎曾经实现了)，但老本较高。
Kafka
如果不想让每个实例都和其余实例通信，能够利用 Kafka 同步所有实例中的计数器。
例如，当某个实例被调用时，就将一个事件推到对应的 topic。这些事件会被滑动窗口聚合(Kafka Stream 在这方面做得很好)，每个客户端最初一分钟的最新计数会被公布到另一个 topic 上。而后，每个实例通过此 topic 取得所有客户端的共享计数。
问题在于 Kafka 实质上是异步的，尽管通常提早很小，但当 API 负载减少时，也会减少提早。如果实例应用了过期的计数器，那么可能会漏过那些本应被阻止的调用。
这些解决方案都有一个共同点: 当一切正常时，能够很好的工作，但当负载过重时，就会进化。咱们的大部分零碎都是这样设计的，通常状况下没有问题，但流控并不是典型组件，其指标就是爱护零碎的其余局部免受这种过重负载的影响。
流控系统的指标是在零碎负载较重时工作良好，其构建指标是为最差的 1% 而不是好的 99% 的状况服务。
分布式算法
咱们须要一个中心化的同步存储系统，以及为每个客户端计算以后速率的算法。内存缓存 (如 Memcached 或 Redis) 是现实的零碎，但并不是所有的流控算法都能够在缓存零碎中实现。上面咱们看看有什么样的算法。
简化起见，咱们思考尝试实现“每分钟 100 次调用”的流控。
看看有哪些工具可用。
基于事件日志的滑动窗口（Sliding window via event log）
如果想晓得某个客户端在过来一分钟内进行了多少次调用，能够在缓存中为每个客户端存储一个工夫戳列表。每次调用时，相应的工夫戳都会增加到列表中。而后循环遍历列表中的每一项，抛弃超过一分钟的旧项，并计算新项。
👍长处：
- 十分准确
- 简略
👎毛病：
- 须要弱小的事务反对(解决同一客户端的两个实例须要更新雷同的列表)。
- 依据不同的调用限度和次数，存储对象 (列表) 的大小可能相当大。
- 性能不稳固(更多的调用意味着须要解决更多的工夫戳)。
固定窗口（Fixed window）
大多数分布式缓存零碎都有特定的、高性能的“计数器”形象(一个能够主动减少的整数值，附加在一个字符串键上)。
以“{clientId}”为 key 为每个客户端保护一个计数器非常容易，但只会计算自计数器创立以来客户端调用的次数，而不是最初一分钟的次数。以“{clientId}_{yyyyMMddHHmm}”为 key 能够每分钟都为客户端保护一个计数器(换句话说: 以 1 分钟为固定窗口)，查找与以后工夫绝对应的计数器能够通知咱们这一分钟客户端执行的调用数量，如果这个值超过下限，就能够阻止调用。
请留神，这与“最近一分钟”不是一回事。如果在上午 07:10:23 有一次调用，固定窗口计数器会显示在上午 07:10:00 到 07:10:23 之间调用的数量。但咱们真正想要的是早上 07:09:23 到 07:10:23 之间的调用数量。
在某种程度上，固定窗口算法每过一分钟都会“遗记”之前有多少次呼叫，因而客户端实践上能够在 07:09:59 执行 100 次调用，而后在 07:10:00 执行 100 次额定的调用。
👍长处：
- 十分快(单个原子增量 + 读取操作)
- 只须要十分根本的事务反对(原子计数器)
- 性能稳固
- 简略
👎毛病：
- 不精确(最多会容许 2 倍调用)
令牌桶（Token bucket)
回到 1994 年，父母把你送到游戏厅和敌人们一起玩《超级街霸 2》。他们给你一个装了 5 美元硬币的小桶，而后去了街对面的酒吧，并且每个小时都会过去往桶里扔 5 美元硬币。因而你基本上被限度每小时玩 5 美元(心愿你在《街头霸王》中表现出色)。
这就是“令牌桶”算法背地的次要思维: 与简略计数器不同，“桶”存储在每个客户端缓存中。桶是由两个属性组成的对象:
- 残余“令牌”的数量(或残余能够进行的调用的数量)
- 最初一次调用的工夫戳。
当 API 被调用时，检索桶，依据以后调用和最初一次调用之间的工夫距离，向桶中增加新的令牌，如果有多余令牌，递加并容许调用。
所以，和“街头霸王”的例子相同，没有“父母”帮咱们每分钟从新装满桶。桶在与令牌耗费雷同的操作中被无效的从新填充(令牌的数量对应于上次调用之后的工夫距离)。如果最初一次调用是在半分钟之前，那么每分钟 100 次调用的限度意味着将向桶中增加 50 个令牌。如果桶太“旧”(最初一次调用超过 1 分钟)，令牌计数将重置为 100。
事实上，能够在初始化的时候填充超过 100 个令牌(但补充速度为 100 令牌 / 分钟): 这相似于“burst”性能，容许客户端在一小段时间内超过流控的限度，但不能长期维持。
留神: 正确计算要增加的令牌数很重要，否则有可能谬误的填充桶。
该算法提供了完满的准确性，同时提供了稳固的性能，次要问题是须要事务(不心愿两个实例同时更新缓存对象)。
👍长处：
- 十分准确
- 疾速
- 性能稳固
- 优化初始令牌数量能够容许客户端“burst”调用
👎毛病：
- 更简单
- 须要弱小的事务反对
漏桶 (Leaky bucket): 该算法的另一个版本。在这个版本中，调用沉积在 bucket 中，并以恒定的速率(匹配速率限度) 解决。如果桶溢出，则回绝调用。这实现起来比较复杂，但能够平滑服务负载(这可能是您想要的，也可能不是)。
🏆最好的算法？
比拟这三种算法，令牌桶仿佛在性能和准确性方面提供了最好的折衷。但只有当零碎提供良好的事务反对时，才有可能实现。如果有 Redis 集群，这是完满计划(甚至能够实现基于 Lua 的算法，间接运行在 Redis 集群上，以进步性能)，但 Memcached 只反对原子计数器，而不是事务。
能够基于 Memcached 实现令牌桶的乐观并发（optimistic concurrent）版本[3]，但这更加简单，而且乐观并发的性能在负载较重的状况下会降落。
用固定窗口近似模仿滑动窗口
如果没有弱小的事务反对，是否注定要应用不精确的固定窗口算法？
算是吧，但还有改良的空间。请记住，固定窗口的次要问题是它每过一分钟都会“遗记”之前产生的事件，但咱们依然能够拜访相干信息(在前一分钟的计数器中)，所以能够通过计算加权平均值来预计前一分钟的调用次数。
* 例如: 如果在 00:01:43 进行了一次调用，递增失去“00:01”计数器的值。因为这是以后的日历分钟，当初蕴含 00:01:00 至 00:01:43 之间的调用数 (最初 17 秒还没有产生)。\
但咱们想要的是 60s 滑动窗口中的调用数，意味着咱们错过了 00:00:43 到 00:01:00 这段时间的计数。为此咱们能够读取“00:00”计数器，并以 17/60 的因子进行调整，从而阐明咱们只对最初 17 秒感兴趣。*
如果负载不变，这一近似是完满的。但如果大多数调用都集中在前一分钟，那就会取得一个高估的值。而当大多数调用都集中在前一分钟完结后，这个数字就会被低估。
比拟
为了更精确的理解精度差别，最好是在雷同的条件下模仿两种算法。
上面的图显示了“固定计数器”算法在输出随机流量时将返回什么。灰色的线是一个“完满”的滑动窗口输入，该窗口在任何工夫点对应于过来 60 秒内的呼叫次数，这是咱们的指标。橙色虚线示意固定窗口算法对雷同流量的“计数”。
它们在第一分钟的输入是雷同的，但很快就能够看到固定窗口版本在每分钟标记处有很大的降落。固定窗口算法很少会超过 100 个调用的限度，这意味着会容许很多本应被阻止的调用。
上面的图示意雷同的场景，具备雷同的流量，但应用了近似的滑动窗口。同样，灰色线代表“完满”滑动窗口。橙色虚线示意近似算法。
在每分钟标记左近不再看到降落，能够看到新版本算法与完满算法更靠近，它有时略高，有时略低，但总体上是微小的提高。
收益递加
但咱们能做得更好吗？
咱们的近似算法只应用以后和以前的 60 秒固定窗口。然而，也能够应用几个更小的子窗口，一种极其办法是应用 60 个 1s 窗口来重建最初一分钟的流量。显然这意味着为每个调用读取 60 个计数器，这将极大减少性能老本。不过咱们能够抉择任意固定窗口工夫，从中拟合近似值。窗口越小，须要的计数器就越多，近似值也就越准确。
咱们看看组合 5 个 15 秒窗口会有什么成果:
正如预期的那样，准确率有所提高，但依然不够完满。
咱们处在一个经典的 更好的准确性 = 更差的性能 的状况下。没有相对的最佳计划，必须均衡对于准确性和性能的要求，找到最适宜的解决方案。如果你只关怀爱护本人的服务不被适度应用，而不须要继续管制，那么甚至最简略的固定窗口就可能是可行的解决方案。
论断
流控是一种非常容易形容但却暗藏了很多复杂性的个性。心愿本文可能帮忙你了解在简单分布式系统中实现流控所波及的工具和算法。
References: \
[1] Distributed Rate-Limiting Algorithms: https://medium.com/criteo-engineering/distributed-rate-limiti… \
[2] Introduction to HAProxy stick tables: https://www.haproxy.com/blog/introduction-to-haproxy-stick-ta… \
[3] Optimistic currency control: https://en.wikipedia.org/wiki/Optimistic_concurrency_control你好，我是俞凡，在 Motorola 做过研发，当初在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓重的趣味，平时喜爱浏览、思考，置信继续学习、一生成长，欢送一起交流学习。\
微信公众号：DeepNoMind
本文由 mdnice 多平台公布
