1. 限流算法

整理 date: 2021-07-22

参考

参考博客

01 固定窗口

通过在单位时间内维护的计数器来限制该时间单位内的最在访问量。假设限制每分钟请求量不超过60，设置一个计数器，当请求到达时如果计数器到达阈值，则拒绝请求，否则计数器加1；每分钟重置计数器为0。

02 滑动窗口

解决了计数器中的瞬时流量高峰问题，其实计数器算法也是滑动窗口的一种，当窗口中流量到达阈值时，流量会瞬间切断。

为了防止瞬时流量，可以把固定窗口近一步划分成多个格子，每次向后移动一小格，而不是固定窗口大小，这就是滑动窗口（Sliding Window）。
比如每分钟可以分为6个10秒中的单元格，每个格子中分别维护一个计数器，窗口每次向前滑动一个单元格。每当请求到达时，只要窗口中所有单元格的计数总和不超过阈值都可以放行。TCP协议中数据包的传输，是采用滑动窗口来进行流量控制。

03 漏桶算法（Leaky Bucket)

注入速度大于漏出速度 ，限流

语法像水一样以任意速度注入漏桶中（桶满则溢，丢弃请求），桶会按照固定的速率将水漏掉。
核心能力： 限流 和 整形

想要以恒定的速率漏出流量，通常还应配合一个FIFO队列来实现，当tryAcquire返回true时，将请求入队，然后再以固定频率从队列中取出请求进行处理。

04 令牌桶

取出
以恒定速率向停牌桶放入令牌（桶满就不放，此时丢弃要放的令牌），请求到达时，先取令牌，取到令牌放行，否则拒绝。

允许一定的流量突发（瞬时将桶内的令牌全部消耗完，后续的流量只能按照速率r通过限流器。）

05 滑动日志

滑动日志限速算法需要记录请求的时间戳，通常使用有序集合来存储，我们可以在单个有序集合中跟踪用户在一个时间段内所有的请求。
假设我们要限制给定T时间内的请求不超过N，我们只需要存储最近T时间之内的请求日志，每当请求到来时判断最近T时间内的请求总数是否超过阈值。