限流是保证系统可用性的重要手段, 一般说来, 任何一个系统在单位时间内能处理的任务数都存在上限, 当待处理的任务数超过这个上限时可能会导致系统不可用, 因此限流器是高可用系统不可缺少的一个组件, 限流的相关算法有很多, 常用的有计数器 (Counter) / 漏桶(leaky bucket) / 令牌桶(token bucket) 等, 在讨论和分析问题之前, 首先要做的第一件事便是清晰、完整地定义问题, 我们剥离限流的实际背景, 从抽象层面上来说, 所谓限流即是设置系统在单位时间内处理任务数的上界, 因此限流器设计的目标即是保证在单位时间内系统真正处理的请求数不高于这个上界, 而对于超出这个上界之外的请求处理策略, 可以根据实际业务场景来选定, 例如直接拒绝服务或是放入到一个等待队列中进行排队

11.1 计数器 (Counter)

计数器是最直观的 API 限流的实现方式, 计数器对每次 API 请求进行计数, 如果数量超过设定的阈值便拒绝此次请求, 例如业务中常见的限流规则有 1 min 内某接口的调用次数不超过 N 次, 最简单的计数器实现方式是在每分钟开始的时间点上复位计数器, 但是这样的限流是不平滑的, 假设用户在上 1 min 的后半区间内发起了 N 次调用, 又在下一分钟的前半区间内发起了 N 次调用, 则从上一分钟的时间区间中点到下一分钟的时间区间中点的这一分钟内总共发起了 2N 次 API 调用, QPS 将会达到限定的两倍, 解决这个问题可以使用滑动窗口的方式, 将 1 min 的时间区间再划分为若干个小的限流窗口, 如每 10s 为一个限流窗口, 每个限流窗口都有独立的计数器, 当进行限流校验时统计从当前时间点往前 6 个小窗口的 API 调用总数, 如果超过限制则拒绝此次调用, 滑动窗口计数器限流方式的精度取决于窗口的粒度

11.2 漏桶算法 (Leaky Bucket Algorithm)

漏桶算法将限流器形象化为一个盛水的桶, 将每一个外界请求看做是水滴, 请求在真正被系统处理之前需要首先经过漏桶, 漏桶以恒定的速率滴水, 只有穿过这个漏桶的请求才会真正被系统处理, 由于滴水的速率是恒定的, 所以可以严格保证系统的最大 QPS, 当请求频率高于设定的 QPS 时, 即漏水的速度小于向桶中流入水滴的速度时, 桶中的水将会不断增多, 直至到达桶的最大容量, 如果此时请求频率依然没有下降, 那么多余的请求将会 「溢出」, 溢出的请求可以直接向调用方返回失败, 或是放入到另一个缓冲队列中进行排队, 这取决于具体的设计, 漏桶算法可以用如下所示的图片来形象地表示

漏桶算法本身的原理非常简单, Uber 有一个关于漏桶算法的开源实现 - ratelimit

11.3 令牌桶算法 (Token Bucket Algorithm)

令牌桶算法是与漏桶算法相反的思路, 在漏桶算法中, API 请求被看做是水滴, 当水将桶盛满时将不再接受新的调用, 令牌桶的思路是按一定速率地向桶中投放令牌, 每一个 API 请求被真正被执行之前都需要首先去桶内拿到令牌, 当桶内的令牌都被取完时, 新的 API 请求将无法被接受, 对于令牌桶算法来说, 当需要改变限流数值时, 只需改变向桶内投放令牌的频率即可

令牌桶算法的实现可以阅读 - ratelimit