限流

• 限流指代的是 限制到达系统的并发请求数，使得系统能够正常的处理 部分 用户的请求，来保证系统的稳定性。
• 限流不可避免的会造成用户的请求变慢或者被拒的情况，从而会影响用户体验，因此限流是需要在用户体验和系统稳定性之间做平衡的，即我们常说的 trade off

计数限流

• 计数限流是最简单的限流算法，基本原理为保存一个计数器，处理了一个请求，计数器加一，一个请求处理完毕之后计数器减一，每次请求来的时候看看计数器的值，如果超过阈值要么拒绝。
• 优点：实现简单，单机在 Java 中可用 Atomic 等原子类，分布式可用Redis incr
• 缺点：只能限制请求的总数，而无法限制请求的密度，假设我们允许的阈值是1万，此时计数器的值为0，当1万个请求在前1秒内都涌进来，这突发的流量无法承受。

固定窗口限流

• 一般的限流都是为了限制在指定时间间隔内的访问量，因此还有个算法叫固定窗口，它相比于计数限流主要是多了个时间窗口的概念，计数器每过一个时间窗口就重置，规则如下：
  1. 请求次数小于阈值，允许访问并且计数器 +1
  2. 请求次数大于阈值，拒绝访问。
  3. 这个时间窗口过了之后，计数器清零。

固定窗口临界问题

• 固定窗口临界问题是指无法细粒度地控制流量在定时区间内的平滑性，流量依旧可以出现尖刺。
• 假设系统每秒允许 100 个请求，假设第一个时间窗口是 0-1s，在第 0.55s 处一下次涌入 100 个请求，过了 1 秒的时间窗口后计数清零，此时在 1.05 s 的时候又一下次涌入100个请求，虽然窗口内的计数没超过阈值，但是全局来看在 0.55s-1.05s 这 0.1 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。

滑动窗口限流

• 滑动窗口限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值，相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多，规则如下，假设时间窗口为 1 秒：
  1. 记录每次请求的时间。
  2. 统计每次请求的时间至 往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
  3. 统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

• 但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击，例如每秒限制 100 个请求，希望请求每 10ms 来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率，因此可能存在 5ms 内就打满了阈值的情况。
• 当然对于这种情况还是有变型处理的，例如设置多条限流规则，不仅限制每秒 100 个请求，再设置每 10ms 不超过 2 个。

漏桶算法

• 如下图所示，水滴持续滴入漏桶中，底部定速流出，如果水滴滴入的速率大于流出的速率，当存水超过桶的大小的时候就会溢出，规则如下：
  1. 请求来了放入桶中。
  2. 桶内请求量满了拒绝请求。
  3. 服务定速从桶内拿请求处理。

• 可以看到水滴对应的就是请求，它的特点就是宽进严出，无论请求多少，请求的速率有多大，都按照固定的速率流出，对应的就是服务按照固定的速率处理请求。
• 但是在面对突发请求时，服务的处理速度和平时是一样的，这其实不是我们想要的，在面对突发流量我们希望在系统平稳的同时，提升用户体验即能更快的处理请求，而不是和正常流量一样，循规蹈矩的处理，而令牌桶在应对突击流量的时候，可以更加的"激进”

令牌桶算法

• 令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然后请求只有拿到了令牌才能通过，之后再被服务器处理。
• 当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃，如下规则：
  1. 定速的往桶内放入令牌。
  2. 令牌数量超过桶的限制，丢弃。
  3. 请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝。

• 令牌桶的伪代码实现，可以看出和漏桶的区别就在于一个是加法，一个是减法。

• 可以看出令牌桶在应对突发流量的时候，桶内假如有 100 个令牌，那么这 100 个令牌可以马上被取走，而不像漏桶那样匀速的消费，所以在应对突发流量的时候令牌桶表现的更佳