限流器（rate limiter）用于控制网络流量，比如限制客户在一定时间内能够发起的请求数量，如果超过了该数量，那么接下来的请示都会被阻挡，以下是一些限流的需求示例：

• 用户每秒最多只能发起两次请示
• 每个IP一天最多只能创建10个用户
• 每个设备每周最多只能奖励5次

限流的用处包括但不局限于：

• 防止由拒绝服务攻击引起的资源耗尽
• 降低成本
• 防止服务器过载

Step 1 - 理解需求，确定设计范围

沟通并确定设计需求，以下是一些可供讨论的点：

1. 哪端限流？客户端限流or服务端API限流？

2. 限流策略？基于IP限流 or 基于用户ID限流 or 其它？

3. 系统规模？

4.分布式？

5. 限流器作为一个单独的服务还是集成到代码中？

6. 需要通知被限流的用户吗？

以下是一个需求示例：

1. 精确限制超额访问流量

2. 低延迟，不能降低HTTP响应速度

3. 尽可能少得使用内存

4. 分布式，可跨服务器提供限流服务

5. 异常处理，为限流用户提供异常报警

6. 高容错率，当限流器异常时，不能影响整个系统的使用

Step 2 - 系统设计

在哪里限流

1. 在客户端限流，一般不靠谱

2. 在服务端限流

3. 在中间件中限流，比如API网关

限流算法

令牌桶

维护一个固定容量的令牌桶，系统以稳定的速率向桶内添加令牌，当令牌数量超过容量时多余的令牌会被抛弃。

每次用户请求都会消耗一个令牌，当桶内没有令牌时，限流生效，用户请求被阻挡。

Image Modified

令牌桶算法依赖两个参数：

• 桶容量
• 重填速率

设计这两项参数需要根据实际情况来确定，比如下面是一些实际场景：

1. 不同的API一般需要不同的限流速率，则每个API都需要一个令牌桶
2. 如果根据IP地址进行限流，则每个IP地址都需要一个令牌桶
3. 如果系统每秒最多只能访问10000次，则所有的请求需要共享一个令牌桶

优点：

1. 算法简单
2. 内存效率高
3. 允许短时间内的突发访问

缺点：

1. 桶容量和重填速率两项参数可能不容易调整到合适值

漏桶

所有的请求先存放在一个固定容量的漏桶里，系统以恒定的速率从漏桶里取出请求进行处理。如果漏桶满了，则后续的请求会被丢弃。

漏桶与令牌桶的区别是漏桶对请求的处理速率是固定的。

漏桶算法依赖两项参数：

• 桶容量
• 取出速率

优点：

1. 内存效率高
2. 可保证处理请求的速率是固定的，不会出现突发访问的情况

缺点：

1. 不能处理突发访问的情况，出现突发访问时，旧的请求被积压，导致新的请求被丢弃
2. 算法的两个参数不容易调到合适值

固定窗口计数器

将时间线划分成一个一个的固定窗口，在每个窗口内维护一个计数器，每次用户访问时计数器加一，到达阈值后新的访问被丢弃。

固定窗口计数器的预期目标是限制每个时间段内的流量，但如果流量峰值出现在时间段的开头和结尾处，则仍会出现时间段内的流量超时限定值的情况，如下：

Image Modified

上面的固定窗口是1分钟，流量上限是5，从2:00:00~2:01:00和2:01:00~2:02:00这两个时间段来看，流量都没有超出限定值，但是从2:00:30~2:01:30这个时间段来看，流量是10，超出了限定值。

优点：

1. 内存高效，容量理解
2. 可以做到在每个时间窗结束时调整流量，这在某些场景下有用

缺点：

• 峰值流量出现在时间窗的开始或结束位置时，实际流量超标

滑动窗口日志

用于解决固定窗口计数器中流量峰值出现在边缘位置时实际流量超标的问题，实际操作如下：

1. 每次有请求到达时，记录该请求的时间戳。
2. 当新的请求到达时，移除所有过时的时间戳，比如时间窗口是1分钟，则移除1分钟以前的请求
3. 记录新的