大规模分布式架构中，怎样设计和选择 API 限流技术？
你好，我是丁硕青，目前在腾讯云负责 API 网关等中间件产品的研发工作，工作以来主要从事云计算相关的项目，也从 0 到 1 经历过不少项目的落地。今天主要想跟你聊一下在分布式架构中，我们应该如何设计和选择一个最适合的 API 限流技术方案。
接下来，我会从以下四个章节来进行介绍：
为什么需要限流
常见限流算法
分布式限流技术要点
分布式限流实践方案
我们为什么需要限流？相信你在设计所有系统的时候，都会首先问自己这样一个问题。
之所以会有限流这个问题，是因为我们生活在一个资源有限的社会当中，当资源供不应求的时候，就会引发一系列的问题。为了避免资源问题，我们通常会增加对资源的限制，比如交通限行。回到 API 这个概念上同样如此。
常见的 API 限流应用场景主要包含以下 4 点：
避免突发流量时，服务出现雪崩，比如早些年春运购票时系统崩溃的场景；
流量整形，无论进入的流量频率如何，我们要保证请求转发到后端时是平稳的；
-
用户 SLA 的分级，比如针对付费用户和免费用户，提供不同的 API QPS 额度；
API 市场中的 API 商品，会通过 API 限流来满足商品库存的调用限制。
现在我们大致了解了 API 限流主要解决的问题，我们也对 API 限流需要具备的能力做一些总结和归纳。
我将它分成了三类：
基础限流
a. 按照一个固定的时间维度来限制 API 的调用次数，比如 10000 次请求 / 分钟。
b. 请求缓冲队列。当后端资源不足的时候，我们除了直接拒绝请求之外，还可以把请求缓冲到队列中。当后端的资源释放后，我们再把请求转发过去。这种对于没有重试逻辑的客户端来说是更友好的一种限流的行为。
业务维度限流
针对 API 报文当中的业务属性进行限流，比如针对 API 的调用者，或者请求客户端 IP 去进行不同的限流。
信息反馈
限流最基本的信息反馈是按照 HTTP 的标准，返回 429 状态码。除了返回错误之外，我们还可以在请求被限流时，通过响应头返回给客户端重试的间隔时间，如 X-Ratelimit-Retry-After: 5。当没有被限流时，我们也可以通过 X-Ratelimit-Remaing 来告知客户端剩余调用配额。这些信息都会很好地帮助客户端来进行下一步的决策。
接下来，我们将会介绍限流中的几种非常常见的算法，主要包括：
-
固定窗口 -
滑动日志 -
滑动窗口 -
漏桶算法 -
令牌桶
固定窗口是最常见的限流算法之一。其中窗口的概念，对应限流场景当中的限流时间单元。
如上图中的场景是每秒钟限流 10 次，那么窗口大小就是 1 秒。可以看到，在第一个窗口当中每一个方块代表一个请求。绿色的方块代表可以放通给后端的请求，红色的方块代表被限流的请求。在每秒钟限流 10 次这个场景当中，因为从左到右是时间维度，所以在窗口 1 中，先进来的 10 个请求会被放通，之后的请求会被限流（红色方块）。
优势
逻辑非常简单，实现起来非常快，而且它维护成本比较低；
时间和空间复杂度都非常低，因为只需要维护当前窗口中的一个计数器。
劣势
窗口切换时无法保证限流值。
如上图，分别看两个固定窗口，窗口内的有效请求都没有超过限流值。但是我们如果在窗口交界处截取一个新的窗口，窗口中的有效请求会超过我们限流的 10 次。极端情况下，至多会有两倍于限流值的有效请求。这个问题在请求速率相对比较平稳时，影响不大。但是由于我们通常没有办法控制客户端的请求行为，所以说极端情况下，还是会对后端产生一些影响的。
这个问题出现的主要原因是窗口是固定的，那么我们如果把窗口改成动态的，是否能解决？答案是肯定的。
在滑动日志算法中，我们需要维护每一条请求的日志。每当一个新的请求过来之后，我们会根据该请求动态计算出来当前窗口起始的边界。因为我们已经有时间戳了，所以向前遍历就可以简单地拿到边界值，之后我们会根据窗口中请求计数，和限流的值去对比，就能得出当前请求是要被限流，还是要放通。
优势
准确率 100%，因为我们保留了所有请求的日志，而且是针对每一个请求都会重新计算动态的窗口；
实现成本低。
劣势
-
时间空间复杂度高。因为我们需要保留每一条请求的日志，在存储上面需要额外的开销。在时间复杂度上，针对每一次请求都需要去重新做动态计算，虽然我们可以通过二分查找算法来进行优化，但相比起第一个方案，还是有很大的劣势。
滑动日志算法和固定窗口算法的优缺点几乎是完全相反的。那么我们将两个算法折中一下，就有了第三个算法——滑动窗口。
在滑动窗口的算法中，同样需要针对当前的请求来动态查询窗口。但窗口中的每一个元素，不再是请求日志，而是子窗口。子窗口的概念类似于方案一中的固定窗口，子窗口的大小是可以动态调整的。
比如上图中的场景是每分钟限流 100 次。我们可以把每一个子窗口的时间维度设置为 1 秒，那么一分钟的窗口，就有 60 个子窗口。这样每当一个请求来了之后，我们去动态计算这个窗口的时候，我们向前最多只需找 60 次。这样时间复杂度，就可以从线性变成常量级了，时间的复杂度相对来说也会更低了。
滑动窗口算法是前两个算法的折中，它在性能上明显优于第二种，但是它的准确度又差于第二种，所以它是一个比较平衡的算法。
接下来要介绍两种算法，都跟桶有关，第一种叫漏桶算法。
如图所示，在漏桶算法中，我们把每一次请求当成一个小水滴，水滴到限流组件后，我们会先把它储存在一个桶中。这个桶的底部有一个洞，会匀速地向外漏水。我们把漏水的过程当成请求放通的过程，请求进来的速率是不能控制的，不同客户端可能有不同的速率请求。但是由于桶洞的大小可控，所以我们能保证请求转发的速率上限。
在漏桶算法当中，桶的大小控制了系统能够处理的最大并发数，而实际的限流值是取决于桶最终往外漏水的流速。虽然我们把它具象成了一个桶，但从技术角度理解，它更像是一个 FIFO 队列。
优势
-
漏桶算法最大的优势在于它的流量整形功能，它适用于电商购物的支付环节，支付系统需要和上游的很多银行系统对接，这些银行系统负载能力有限，所以我们就需要针对不同的银行的 SLA 来对请求速率进行限制，避免银行系统高负载，这个场景中，漏桶算法就是一个非常合适的选择。
劣势
实现复杂度相比起前几种算法会更高，维护成本也会更高；
限制了最大转发速率，所以该算法并不适用于一些流量经常会突增的场景。
令牌桶算法是基于漏桶之上的一种改进版本，在令牌桶中，令牌代表当前系统允许的请求上限，令牌会匀速被放入桶中。当桶满了之后，新的令牌就会被丢弃。每当有一个新的请求过来的时候，我们就尝试去桶中拿取一个令牌。如果桶中有空闲令牌，请求就可以放通；如果没有，请求将会被限流。
这个算法跟漏桶比起来，最大的区别就是我们可以允许短时间的流量突增。因为在漏桶算法中，不管同时进来多少个请求，我们只能匀速地放行。但是在令牌桶当中，我们可以同时往后放行的请求数取决于桶中最大的令牌数量，也就是桶的容量。
优势
针对流量可能会出现突增且后端可以接受突增的场景，令牌桶是一种更适合的方案，因为令牌桶在限制平均请求速率的同时，还可以允许一定的突增。
劣势
实现复杂度相对较高。
刚才介绍到的几种限流算法，就像在学习一门剑法时，我们掌握了的基本剑术，比如砍、劈、刺等。那么为了将这些基本的剑法应用到最终的实战当中，就需要要结合具体的实战场景来针对性分析。在分布式限流的场景当中，我们设计方案前，先要看一下限流设计时要考虑的要点。
首先要关注的就是多次提到的准确性。在分布式架构当中，同一个数据的多次操作可能在不同的节点上执行。这个时候我们就需要保证分布式系统中数据的一致性，这样才能保障多次操作的准确性。
另外，我们要保证限流操作的原子性。在分布式架构当中，同一个业务操作往往包含多个子命令，子命令之间如果有其他操作干扰，会导致每次执行的结果不确定，那么就无法保证业务操作的准确性。
举个例子，在固定窗口算法当中，我们需要先判断当前计数器窗口是否过期。如果是还在当前窗口，就直接计数加一；如果已经过期，我们就需要重新创建一个新的窗口。
1 if redis.call('ttl', KEY) < 0 then # 检查限流 Key 是否过期2 redis.call('set', KEY, COUNT, 'EX', EXP) # 设置 Key 的初始值以及过期时间3 return COUNT4 end56 return redis.call('incrby', KEY, 1) # 计数
这里有一次读和一次写，如果在读写过程当中又有其他的操作，对操作的 Key 做了变更，可能使读到的结果被改变，就可能会导致在限流过程中出现一些数据的误判。所以，我们需要保证该读写操作的原子性。
第二点就是性能。虽然不是只有分布式架构才需要关注性能，但在分布式架构当中很可能增加分布式逻辑以及额外的链路，我们需要考虑由于分布式引起的性能额外的开销，对于业务来说是否可以接受。
第三点是可扩展性。我们选择分布式架构一个主要的原因，就是为了架构能够平滑扩展。这里扩展主要包含两个方面：横向扩展、纵向扩展。
针对 API 限流的场景，横向扩展是指当 API 数量增加后，需要平滑地支持更多 API 对象的限流。因为每个 API 对象的限流值不一样，我们需要保证每一个 API 的限流实体能够进行独立的限流判断，不能互相影响。纵向扩展是指特定 API 的调用量、并发量，由于业务增长，可能会从几百增长到几万，那么我们的限流也需要能支撑相应的请求量。
最后一点就是可用性。我们知道限流是保护系统可用性的非常重要的一个环节，其本身的可用性也是非常重要的。如果限流这个环节出现故障，很可能引发一系列的雪灾效应。要保证限流系统的可用性，我这里列举了几个需要考量的点：
1. 避免链路上的单点故障
2. 如果出现故障，需要有相应的降级策略
3.关键指标的可观测性
现在我们了解了 API 限流系统设计在分布式架构中需要关注的主要技术点，接下来我们结合腾讯云 API 网关产品的案例，一起看下具体实践的过程。
在我们设计系统方案之前，我们首先要明确需求，对于 API 网关这类产品来说，它主要的限流功能需求，大概可以分成了三类：
第一类是针对产品 SLA 的限流。因为 API 网关有不同规格的用户实例，不同的实例对应不同的 QPS 上限。这类需求的特点是：
性能要求非常高。因为每一次请求都要经过限流这个环节，如果每次环节都带来额外的性能开销，对于很多客户来说是不能接受的。
准确度要求不高。产品 SLA 层面的限流，可以容忍 5%～10% 的误差。
结合之前介绍的算法特点，SLA 的需求场景下，我们采用的固定窗口的算法。
第二类需求是用户业务维度的自定义限流。针对不同的 API 配置不同的限流值，保护对应的后端。这类需求的特点是：
对准确度要求相对高。因为主要是用来保护用户业务后端，如果限流不准可能对后端会有额外的压力。
需要允许一定的流量激增范围，避免流量波动的业务被频繁限流。
针对这类需求，使用令牌桶算法会更合适。
第三类需求是 API 市场的场景。比如，用户可以将自己的 API 上架到市场，同时配置一定的调用额度，调用者每调用一次，都需要支付一定的费用。
这类需求对于准确性要求极高，所以这里我们选择的是计数器数据结构。
除了功能需求之外，在性能上也需要提前规划，比如单集群需要能够支持百万的 QPS，单 API 能支持十万的 QPS，同时也需要能够支持平滑地横向扩展。
针对以上 API 网关产品需求，我们最终选择的是基于 Redis 中心存储的方案。其原因主要有：
产品本身已经在使用 Redis 了，所以从架构角度来看，使用 Redis 不会引入额外的复杂度。
我们用的是腾讯云上的 Redis，它对于业务方来说几乎是零运维成本
Redis 支持很多类型的存储结构，比如 String、Hash、Sorted Set 等，这些存储结构非常适合 API 网关这类同时存在多种限流算法的情况。
当然从技术的角度来看，也完全可以采用其他的 KV 存储，比如 memcached + proxy 的方式，具体要结合实际业务和技术团队的情况来做决策。
最初的方案在逻辑上是非常简单，请求到达 API 网关后，网关会先通过 Redis 中的实时计算（针对不同的场景使用不同的限流算法），判断是否要对本次 API 请求进行限流。
在这个链路当中，Redis 成为了一个关键环节，那么它本身的单点故障的风险也需要被重点考虑。针对 Redis 单点故障的情况，我们会将限流降级到本地进程级别来处理。降级后，由于没有了中心存储保证数据一致性，所以我们需要通过提前计算节点数量和每个节点的进程数量，来计算每个进程的限流值，这些进程限流值累加起来会接近于分布式限流的限流值。
举个例子，假设我们现在全局限流是每分钟 1000 次。我们有两个节点，每个节点有八个进程。这个时候可以做一个简单的除法，就能得出来每个进程的限流值大约是 1000/2/8=62.5。但由于节点进程之间的流量无法保证完全均匀，所以它存在一定的准确度下降的情况，但是在故障降级这种场景当中是可以接受的。
还有一点非常重要，就是在 Redis 恢复之后，仍然是需要将本地的数据同步回 Redis，避免出现限流窗口被重置，影响后端业务的情况。
存储方面
我们依赖于 Redis 来做限流数据的存储。
性能方面
使用连接池来减少一些 Redis 建连的的延迟。
通过 Redis 的就近接入的能力，减少跨 IDC 之间的额外耗时（需要考虑主从同步延迟所引起的可能的问题）。
原子性方面
Redis 提供了 Lua 脚本的能力，可以保证脚本中限流逻辑的原子性。但是这块需要注意的是，Redis 在执行 Lua 脚本的时候，为了保证原子性，会阻塞其他脚本或操作，所以要避免脚本逻辑耗时长，影响整体性能。
容错方面
Redis 故障时会触发降级到本地限流的逻辑。
扩展性方面
采用 Redis 集群架构。可以支持平滑扩展节点来实现横向的扩展。但是在纵向上扩容上 Redis 确实存在瓶颈（单节点 8 ～ 10 万 QPS）。
隔离性方面
通过 Redis Key 进行逻辑的隔离
通过多个 Redis 实例来实现租户的隔离
可见性方面
日志收集监控 & 告警：包含 API 网关的请求日志、组件错误日志等
系统资源监控：包含 CPU、内存、网络、磁盘等基础监控
Redis 监控：资源负载、命令耗时、慢查询、错误率等
依赖 Redis 解决分布式系统中的原子性、一致性等问题，降低了系统的复杂度和运维成本。
Redis 在纵向扩展（单限流 Key）存在瓶颈；
同步请求 Redis 会增加一个毫秒级的额外延迟；
依赖于中心存储，不适用于边缘计算的场景。
性能优化点：异步数据同步
针对上述提到的纵向扩展以及额外延迟的劣势，我们对方案进行了优化。
方案要点
核心的优化思路就是把同步限流计算变成异步批量同步，避免 Redis 成为瓶颈。限流主要包含两个阶段：
同步阶段：处理请求时，API 网关会优先在本地内存中进行限流的逻辑处理。
异步阶段：定时将内存中的限流数据和 Redis 进行同步。
该方案的主要问题是，如果在异步同步前，网关接收到了大量并发请求，可能导致限流击穿，引发后端的雪崩效应。针对这个问题，我们增加了一个额外的环节，叫做同步计数检查。每一个请求来了之后，我们会先检查本地计数器是否超过了全局限流阈值的一定百分比，如果超过了，那么要强制进行 Redis 限流计算和同步。
举个例子，假设限流每分钟 100 次请求，我们设置本地限流不能超过全局限流的 10%，如果本地内存计数超过了 10 次，就会在请求过程中同步触发一次强制的同步。通过这个机制，我们可以保证大部分请求的性能的同时，避免出现请求突增把限流打穿的场景。
采用异步同步的机制，避免 Redis 成为瓶颈，降低了平均延迟；
通过批量 Redis 同步机制，提高了限流单 Key 性能限制；
可以通过调节同步限流判断阈值，来权衡性能和限流准确性。
由于限流数据会优先在本地内存计算，所以限流的准确性会下降；
支持的场景有限，令牌桶、漏桶算法实现复杂度高。
除了中心存储的方案之外，我也了解过几种适用于分布式架构的限流方案，各有特点。第二个要介绍的方案是基于负载均衡将请求分发给多个服务节点，通过每个服务节点上的反向代理网关实现本地节点限流。
方案要点
这个方案中，请求会通过负载均衡分发给不同的 API 服务节点。在每一个服务节点之上会部署一个 Nginx 的反应代理服务器，通过 Nginx 的 limit_req 模块配置本地限流。我们的核心思路是将一个分布式的限流负载均衡后转化成了每个节点的本地限流。和上一个方案的本地限流场景类似，我们同样需要根据节点数量来计算每个节点的限流值。
本地内存限流，低延迟，同时可以实现 ms 级的限流时间粒度；
方案简单，实现成本和运维成本都比较低。
准确率不高，因为该方案依赖于负载均衡将流量均匀地分发给每一个节点，但实际场景中流量是不均匀的；
扩缩容时，我们需要重新计算单节点限流值。
-
方案要点
第三个方案跟第一个中心存储的方案类似，都是采用了中心化限流的设计思路。这个方案没有依赖中心存储，而是通过一致性哈希算法对限流对象的 Key 哈希后分配到一个固定的限流节点上。这个 API 后续请求就都会落到同一个节点上，所以本质上我们还是将分布式限流，转化成了节点的本地限流来解决。
本地内存限流，低延迟；
方案简单，实现、运维成本低；
通过一致性哈希，能够一定程度上降低由于节点增减造成的节点重新分配概率。
节点变更还是有概率会影响准确率；
单一限流对象的请求只会分配到一个节点上，虽然可以对节点进行垂直扩容，但同样存在扩容上限。
第四个方案是客户端限流，可能有人会问，客户端限流跟服务端的区别到底是什么？
我们可以通过一个现实的例子，来更好的理解这个问题。假设我计划第二天去动物园，这个时候我有两种方式购票。第一种是我第二天直接去动物园门口去买票，但有可能我到那之后发现票卖光了，会导致我在路上的时间都浪费掉了。另外一种方式就是我提前一天预约购票，这样就可以提前确认是否可以成行，避免出现浪费时间的情况。
再回到客户端限流这个场景中，如果我们把限流这个环节从服务端移到客户端的话，我们可以尽早地避免这些被限流的请求发生，节约更多的资源。但是为了实现在客户端侧的限流，我们需要一些额外的机制。
方案要点
首先，我们需要一个配额服务来管理服务端能承载的最大配额，同时根据客户端诉求，将配额分发给每个客户端。这个配额服务就起到了协调器的作用，它能够保证在整个服务调用链当中所有的客户端调用总和不超过服务端的配额大小。那它的配额从哪来呢？
我们还需要另外一个数据平台，它从服务端采集到服务的负载状态等信息，通过实时分析，计算出服务能够承载的请求上限。之后再将数据更新到配额服务中，最后由配额服务重新复配给客户端，这样就完成了一个周期。
可以看到，它在架构上相对前面的方案来说会增加一些复杂性，但同时更灵活，因为每个客户端可以根据自己的属性、标签来获取它自己想要的配额。最终是否能分发给客户端这么多配额，是由配额服务上面的一些配置策略决定的。我们甚至还可以基于 AI 算法通过历史数据来预测未来的一些配额可能发生变化，来对配额进行预分配。
可以看到，在客户端限流方案当中，它需要客户端是可控的，因为我们需要在客户端侧做很多逻辑。如果这个客户端不可控，某一个客户端没有按照协定的配额来进行请求，则会打破整体的规则。
在请求的源头增加限制，避免更多的资源浪费；
配额异步同步，客户端可以实现本地限流，所以在性能上也非常好；
单限流对象（限流 Key）不存在垂直扩容的问题。
它依赖于客户端的可控性，限制了使用场景；
没有办法保证全局限流的准确性难以保障。
思路参考—— Google Doorman：
https://github.com/youtube/doorman
前面介绍了四种分布式限流当中的方案，每一种方案都有它的优势和缺点，没有哪一种是完美的。所以在我们选择方案时，还是要针对自己的业务需求，在多个方案的优缺点中进行取舍，来选择最适合的场景。
在限流设计当中，不管采用哪种方案，都会有些共性的设计考虑点：
尽可能地将限流逻辑前置，减少不必要的资源消耗。
在设计限流 Key 的时候，尽量向后兼容，因为可能由于业务需求变化，导致变更限流算法，如果 Key 的规则中对算法数据结构强绑定，那么变更算法会导致存量的限流失效。
我们在限流 Key 的设计当中要加入足够多的业务标识，当出现限流不准问题的时候，我们可以快速地定位到问题，提高 Debug 效率。
Less Code == Less Bug。初始设计的时候，工程师确实要考虑后续可能出现的场景兼容问题，但没有必要为了小概率场景过早地进行复杂设计和实现。因为过度设计会增加复杂性，也可能会引入更多不确定的问题。
最后我们还是要总结一下，设计限流系统的几个关键步骤。
一开始，不要着急去选择算法和设计方案，而是先把需求梳理清楚，比如产品有哪些场景会用到限流？系统上都需要考虑哪些关键点？目前公司是否已经有现成的方案？这些都是决定了我们后面决策的一些重要因素。
根据业务场景来选择合适的算法，这里你可以重点参考算法的对比表格。
在方案设计的时候，根据收集到的需求来选择一个合适的技术架构。如果公司内部已经有现成的限流系统，我们也可以去考虑一下是不是可以避免重复造轮子。最后要额外强调的是，限流是保护服务的一个兜底手段，所以要重点考虑限流系统本身的稳定性机制（容灾、降级、监控等）。
在结束之前，我想跟你分享一个我个人比较认可的观点：没有完美的技术方案，只有最合适的。如尚未深思熟虑，先从简单方案开始。
希望以上内容对你有所帮助。
QCon+ 案例研习社（又名：大厂案例）是极客时间平台推出的视频案例课。内容由领域内技术专家出品审核、数百位不同大厂 / 独角兽公司的一线开发工程师、项目经理、产品经理、咨询师和 Tech Lead 亲身分享，所有实践案例都经过至少三个月打磨。QCon+ 专注于提供最接地气、最可靠的技术解决方案，目前已更新 90+ 专题、300+ 实战案例。专题每周一持续更新中，敬请期待！
👇 点击“阅读原文”领取 7 天试用会员 ~
相关内容
微信扫码咨询专知VIP会员