1. 概述
在高并发服务中，限流是一种对请求或并发数进行限制的技术手段。当服务资源或处理能力有限时，限流可以对调用服务的上游请求进行限制，或对下游访问进行限制，以防止自身或下游服务因资源耗尽而影响服务。
在限流中，阈值指在单位时间内允许的请求量。如 QPS（每秒请求数）为 100 表示在 1 秒内最多接受 100 次请求，QPM（每分钟请求数）为 1000 表示在 1 分钟内最多接受 1000 次请求。单位时间的定义依实际场景而定，需要留意 10 QPS 和 600 QPM 实际情况是不同的意思。
拒绝策略是指处理超过阈值的请求的策略，常见的拒绝策略包括直接拒绝和排队等待等。
设计限流方案时，需要根据系统需求、实际适用场景、系统负载情况作出权衡选择。还可以考虑以下几点：
- 多级限流：可以在应用层、服务层、数据层都设置限流，更好地控制限流和防止系统过载
- 动态阈值调整：考虑支持阈值动态调整，从而根据系统实时负载情况调整限流频率
- 灵活维度：支持根据不同的业务场景调整限流的维度，考虑更细的维度，如支持接口、设备、账户、IP 等维度的限流
- 解耦：限流作为基础服务，应当与具体的业务逻辑分离
- 容错：限流服务应当具有高可用性，出现问题时有其它备选方案，如熔断和降级
- 监控告警：对限流策略实时监控，设置告警机制
2. 基本限流算法
2.1 固定窗口算法
固定窗口算法（fixed window）将时间划分为固定大小的窗口，在每个时间窗口内限制请求的数量。它使用一个计数器来记录当前窗口内的请求数，当有请求到达时，判断当前窗口内请求计数是否达到设定的阈值，如果达到了则拒绝该请求，否则将请求计数加一。在进入下一个时间窗口时重置请求计数。
这个算法的优点是原理和实现相对比较简单。它的缺点是无法实现平滑地限流，应对段时间内的突发流量，在固定窗口内可能流量集中在某一时间段内。这也造成了一个临界问题，就是有可能流量集中在上一个时间窗口的末尾和下一个时间窗口的开始，造成在短时间内消耗了两个时间窗口允许的流量。
2.2 滑动窗口算法
滑动窗口算法（sliding window）是对固定窗口算法的一种改进，它解决了固定窗口算法处理时间窗口临界位置突发流量的缺陷。
这个算法又分为两种实现，第一种是计数器实现，即将每个固定时间窗口又拆分为多个更小的周期，并记录每个小周期的访问次数，根据时间滑动删除过期的小周期。划分的格子越多，滑动窗口的滚动就越平滑。
第二种是记录日志实现，它维护一个长度固定而起止时间动态调整的时间窗口，并记录时间窗口内所有请求的时间记录，当有请求到达时，判断从当前时间往前的固定长度时间窗口内请求数量是否达到设定的阈值，如果达到了则拒绝该请求，否则接受请求并记录此次请求的时间。无论是否接受请求，都可以及时清理距今时间差大于时间窗口的记录。
这个算法的解决了固定窗口算法临界位置突发流量的问题，能够更好地应对突发流量的情况，实现更精确的限流控制。但是它需要记录滑动时间窗口内的每个小周期请求次数或每个请求时间列表，会消耗更多的内存，同时需要较多时间开销用于处理窗口滑动、请求计数、过时请求移除。
2.3 漏桶算法
漏统算法（leaky bucket）维护一个固定容量的漏桶，请求相当于流入漏桶的水，以不稳定的速度到达，请求到达时如果漏桶未满则流入漏桶，如果漏桶已满则会触发拒绝策略。按固定的速率将漏桶内的水流出，然后执行请求。
这个算法可以平滑突发流量，使流量变得平稳，防止系统过载，同时它的原理和实现都比较简单。它的缺点是流出速率是固定的，即使流量比较低的情况下也无法有效地提高资源消耗速度，资源利用率低，对突发流量无法快速处理，造成饥饿问题。
2.4 令牌桶算法
令牌桶算法（token bucket）维护一个固定容量的令牌桶，按照固定速率将令牌放入令牌桶中，如果桶已满则将多余的令牌丢弃，请求达到时需要从令牌桶中获取令牌，成功获取令牌的请求将被执行，获取不到令牌时将请求拒绝。
这个算法可以平滑突发流量，使突发流量可以均匀分布，它可以积攒令牌，相对于漏桶算法它有更好的突发流量处理能力，并且可以调整令牌生成速率和桶的大小来灵活地控制流量。它相对于漏桶算法实现相对复杂一些，需要维护令牌的生成和消耗。
2.5 各算法的比较
| 算法 | 优点 | 缺点 | 适用场景 | 时间复杂度 | 空间复杂度 | 限制突发流量 | 平滑限流 |
|---|---|---|---|---|---|---|---|
| 固定窗口算法 | 实现简单 | 流量不均，无法应对突发流量 | 不需要保证请求均匀分布的场景 | O(1) | O(1) | 否 | 否 |
| 滑动窗口算法 | 流量部分平滑 | 实现相对复杂，更高的内存和时间消耗 | 需要平滑处理突发流量的场景 | O(N) | O(N) | 部分 | 部分 |
| 漏桶算法 | 平滑突发流量，固定输出速率 | 对突发流量不够灵活，无法应对流量波动 | 需要固定速率、平滑流量的场景 | O(N) | O(N) | 是 | 是 |
| 令牌桶算法 | 平滑突发流量，动态调整限流规则 | 实现相对复杂 | 需要平滑流量、动态调整限流规则的场景 | O(N) | O(N) | 是 | 是 |
3. 分布式限流
在单体服务使用限流算法，可以限制该服务处理请求的速率。随着服务部署在多个服务器或节点上时，便无法简单地使用限流算法来达成目的了。
以下介绍了三种基于不同原理的分布式限流方案。
3.1 基于负载均衡
结合负载均衡器和本地限流实现分布式限流。
首先使用负载均衡器或分布式服务发现，将请求均匀地分发到每台机器上，然后在每个机器上使用本机的限流算法进行限流，在每个部署的节点使用相同的限流算法和限流速率。例如，我们需要将针对某个第三方服务的访问频率限制在 100 次每秒，当前服务部署了 10 个节点，可以在每个节点都设置 10 次每秒的限流，这样整体上针对该第三方服务的访问频率就不会超过总的频率限制了。
每个节点独立限流，当一些节点的处理速度充足而一些节点的处理速度不足时，不同节点间设置的限流无法共享，就会拖慢整体的处理速度，无法跑慢设定的频率。另外，当系统需要动态扩缩容或部分节点出现异常无法服务时，需要手动地调整配置以达到整体频率的不变。请求负载均衡器还可能会引发单点故障影响整个系统。
3.2 基于中心化
基于一个中心化的组件，如 Redis，来保存限流规则和获取请求令牌。
将限流规则如每秒允许的最大请求数存储在 Redis 中，对每个请求需要先向 Redis 请求令牌，如果获取到令牌则处理请求，如果获取不到令牌则等待重试或者返回错误。
基于 Redis 的固定窗口限流可以使用 incr 来实现，当值为 1 表示初次设置 key，通过 pexpire 设置键的过期时间。使用 lua 脚本来实现原子操作。
这种方案存在的问题有：
- 所有请求都需要访问 Redis，使得 Redis 可能会成为性能瓶颈，可以通过 Redis 集群来提高性能
- Redis 出现单点故障会影响整个系统的限流功能，可以使用 Redis 的主从复制或者哨兵来实现高可用
- 访问 Redis 的网络带宽会对系统造成影响
3.3 基于分布式协调服务
使用分布式协调服务如 ZooKeeper 或 etcd 来实现限流。
在 ZooKeeper 中创建一个节点作为令牌桶，节点的数据代表令牌的数量，设置一个定时任务定期向 ZooKeeper 中的令牌桶补充令牌。当一个请求到达时，向 ZooKeeper 申请一个令牌，即获取节点的分布式锁然后将节点的数据减 1，如果操作成功则表示成功获取了令牌，可以处理请求，如果操作失败则表示令牌已经用完，请求被拒绝或等待。
这个方案可以实现精确的全局限流，避免单点故障，但是它的实现较为复杂，且对 ZooKeeper 的性能有较高要求，可能会成为系统的瓶颈。