为什么要限流

限流在很多场景中用来限制并发和请求量，比如说秒杀抢购，保护自身系统和下游系统不被巨型流量冲垮等。

以微博为例，例如某某明星公布了恋情,访问从平时的50万增加到了500万，系统的规划能力，最多可以支撑200万访问,那么就要执行限流规则,保证是一个系统的可用的状态,不至于服务器崩溃，导致所有请求不可用。

常用的限流方案

废话不多说，直接进入正题，常用的限流方案有计数器、滑动窗口、令牌桶和漏桶4种算法。

主要介绍这4种算法的原理、实现使用的数据结构、使用场景以及优缺点。

计数器

1. 首先我们需要选定一个时间起点，之后每当有接口请求到来，我们就将计数器加一。
2. 如果在当前时间窗口内，根据限流规则（比如每秒钟最大允许 100 次访问请求），出现累加访问次数超过限流值的情况时，我们就拒绝后续的访问请求。
3. 当进入下一个时间窗口之后，计数器就清零重新计数。

这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题 : 无法应对两个时间窗口临界时间内的突发流量,我们看下图：

假设我们的限流规则是，每秒钟不能超过 100 次接口请求。

第一个 1s 时间窗口内，100 次接口请求都集中在最后 10ms 内。

在第二个 1s 的时间窗口内，100 次接口请求都集中在最开始的 10ms 内。

虽然两个时间窗口内流量都符合限流要求（≤100 个请求），但在两个时间窗口临界的 20ms 内，会集中有 200 次接口请求。固定时间窗口限流算法并不能对这种情况做限制，所以，集中在这 20ms 内的 200 次请求就有可能压垮系统。

由于这种算法有严重的临界问题，所以使用的场景如下：

1. 相对简单的场景： 当系统相对简单，对于计数器的高精度要求不是很高，并且可以容忍一定的限流不准确性时，计数器限流算法是一个简单且易于实现的方案。

2. 不需要极高精度的流控场景： 在某些场景下，对于请求的限流并不需要非常精确的控制，而是希望通过一种简单的方式控制系统的流量，这时计数器限流算法可能是一个可行的选择。

3. 流量变化较缓慢的应用： 如果系统的请求流量相对稳定，且变化不是很大，那么计数器限流算法可能可以满足需求。

滑动时间窗口

由于计数器算法有严重的临界问题，不太适合高精度和复杂的场景。

为了解决这个问题，我们可以对固定时间窗口限流算法稍加改造。我们可以限制任意时间窗口（比如 1s）内，接口请求数都不能超过某个阈值（ 比如 100 次）。因此，相对于固定时间窗口限流算法，这个算法叫滑动时间窗口限流算法。

我们假设限流的规则是，在任意 1s 内，接口的请求次数都不能大于 K 次，即最大的qps为k。

那么要实现这一的一个算法，需要什么的数据结构来实现呢？答案就是：循环队列，我们需要维护一个大小为 K+1 的循环队列，用来记录 1s 内到来的请求。注意，这里循环队列的大小等于限流次数加一，因为循环队列存储数据时会浪费一个存储单元。

实现了一个简单的循环队列代码如下

public class Queue {
  private Long[] data;
  private int size = 0, head = 0, tail = 0;
  public Queue(int size) {
    this.data = new Long[size];
    this.size = size;
  }

  public boolean add(Long element) {
    if ((tail + 1) % size == head) return false;
    data[tail] = element;
    tail = (tail + 1) % size;
    return true;
  }

  public Long poll() {
    if (head == tail) return null;
    long ret = data[head];
    head = (head + 1) % size;
    return ret;
  }
}

public class Producer {
  private Queue queue;
  public Producer(Queue queue) {
    this.queue = queue;
  }

  public void produce(Long data) throws InterruptedException {
    while (!queue.add(data)) {
      Thread.sleep(100);
    }
  }
}

public class Consumer {
  private Queue queue;
  public Consumer(Queue queue) {
    this.queue = queue;
  }

  public void comsume() throws InterruptedException {
    while (true) {
      Long data = queue.poll();
      if (data == null) {
        Thread.sleep(100);
      } else {
        // TODO:...消费数据的业务逻辑...
      }
    }
  }
}

上面的介绍已经知道时间滑动窗口算法使用的是循环队列结构,上面也给出了循环队列的实现代码,那么该算法的具体执行流程是什么呢？

1. 先设置一个大小为k+1的循环队列。
2. 当有新的请求到来时，我们将与这个新请求的请求时间间隔超过 1s 的请求，从队列中删除（消息消费），删除方式为从head头节点顺序遍历查询。
3. 第二步完成后，尝试将新请求添加到队头head位置。如果此时队列已满，则拒绝请求；如果此时队列未满则正常插入请求。

可以发现滑动时间窗口算法一个特点：只有在新请求到来时，才会判断队列中的所有元素，哪些元素是可以正常消费的。那么如果一直没用新请求过来，队列中的消息将永远不会消费。

为了方便理解，结合下面这张图来理解下吧。

使用场景： 滑动窗口算法适用于需要对请求的时间窗口内流量进行限制的场景。它可以有效控制单位时间内的请求频率。

令牌桶

令牌桶算法以一个设定的速率产生令牌并放入令牌桶，每次用户请求都得申请令牌，如果令牌不足，则拒绝请求。

大致的流程如下：

1. 接口限制 t 秒内最大访问次数为 n，则每隔 t/n 秒会放一个 token 到桶中；

2. 桶中最多可以存放 b 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 会被丢弃；如果令牌桶没有满时，该token会被加入到这个桶中。

3. 接口请求会先从令牌桶中取 token，拿到 token 则处理接口请求，拿不到 token 则执行限流，拒绝请求或者是阻塞等待。

令牌桶算法是一直以固定速率往桶里加token，不管有没有请求接口，直到桶满为止。

正是由于上述的原因使令牌桶算法可以有效应对突然流量,怎么理解有效应对突然流量这句话呢？举个例子

1. qps为1000，即1ms往桶内增加一个token。
2. 设置桶的容量为2000。
3. 假如1500ms之前一直都没有流量请求，此时桶内的token量积累为1500。
4. 此时来了一波突发请求，大致为1500个，那么所有的请求是可以都获取到token的而不会被拒绝。
5. 可以发现我们设置的qps为1000，但是却满足了1500的请求量。这是这个现象，体现了令牌桶是可以应对突发流量的。

令牌桶算法允许一定程度的突发流量。如果令牌桶中有足够的令牌，系统可以处理更多的请求。这使得令牌桶算法在应对短时的、不过分激烈的突发流量时比较灵活。然而，如果突发流量太过剧烈，令牌桶算法也有可能因为令牌桶被耗尽而进行限流。

上面的例子可以看出token是随着时间的推移而增加，那么如果刚开始时来了一波突发请求，此时桶内是没有足够的token的，该怎么应付这种情况呢？答案就是预热桶：即刚开始时就往桶里放入一部分token，而不是0 token的情况。

上面的介绍中其实忽略的一个重要的因素：桶容量。如果上面的流程中设置的桶容量为10000，且此时桶中token数也为最大值10000，正好此时的突发流量也达到了10000，由于这些请求都可以获取到token则所有流量都将会打到系统，如果系统能承受的最大qps也就5000，那么此时系统将会发生奔溃。

令牌桶算法中桶的最大容量是一个关键参数，对系统的性能和流量控制都有影响。选择桶的最大容量应该根据具体的业务需求和系统的特点来合理设置。

• 系统的处理能力： 桶的容量应该能够适应系统的处理能力。桶容量太小将会导致合法的请求被拒绝。桶的容量较大，在应对突然流量时可能冲垮系统，应该保证桶容量的最大值小于系统的最大承受能力。
• 系统的峰值流量： 考虑系统的峰值流量，设置桶的容量，使其足够大以应对可能的峰值请求。
• 对突发流量的容忍度： 桶的容量也会影响系统对于突发流量的容忍度。如果桶的容量较大，系统可以在短时间内处理一些累积的请求，但这也可能导致一些短时刻内的资源竞争。

经过上面的探讨，发现令牌桶算法适用的场景是：用于限制请求的整体速率，它具有一定的突发流量处理能力，可以应对短时的流量峰值。

我相信介绍了这么多，肯定对令牌桶算法有了一些基本的了解，如果让你实现一个这样的算法，你会怎么设计呢？我的大致思路如下：

1. 使用循环队列的数据结构来充当令牌桶。
2. 循环队列的大小： 可以设置为令牌桶的容量，即桶中能够存放的令牌的最大数量。
3. 令牌生成： 可以有一个单独的线程，以固定的速率（比如每秒生成一定数量的令牌）向循环队列中添加令牌(入队)。在添加令牌时，需要考虑队列已满的情况，如果队列已满，则新生成的令牌不会被添加。
4. 请求处理： 当请求到达时，尝试从循环队列中取出一个令牌(出队)。如果队列中有足够的令牌，允许请求通过，并从队列中取出一个令牌；如果队列中没有足够的令牌，拒绝请求。

漏桶

漏桶算法限流的基本原理为：水（对应请求）从进水口进入到漏桶里，漏桶以一定的速度出水（请求放行），当水流入速度过大，桶内的总水量大于桶容量会直接溢出，请求被拒绝。
大致的漏桶限流规则如下：
（1）进水口（对应客户端请求）以任意速率流入进入漏桶。
（2）漏桶的容量是固定的，出水（放行）速率也是固定的。
（3）漏桶容量是不变的，如果处理速度太慢，桶内水量会超出了桶的容量，则后面流入的水滴会溢出，表示请求拒绝。

漏桶算法通过固定速率漏水的方式，对流量进行整形，限制了流量的速率。漏桶算法相对来说对于限制整体速率和防止长时间的高速流量比较有效，但对于短时的突发流量的处理相对较为严格。

和令牌桶算法相比，可以发现，令牌桶可以应对一些突发流量,而漏桶的是以固定速率在漏水，呈现的现象就是流量会非常平稳，防止突发流量对系统的冲击，不会像令牌桶那样出现突刺的情况。

这个漏桶有明显的俩个作用：

• 削峰:有大量流量进入时,会发生溢出,从而限流保护服务可用

• 缓冲:不至于直接请求到服务器, 缓冲压力

网上有一种说法是漏桶不能有效应对突发流量，但是能起到平滑突发流量（整流）的作用。后半句话是没有问题，但是我对前半句话有一点质疑：

举个例子，比如此时桶没有满，来了一大堆突发的流量，加入到桶内时也没有满，其实这些请求是不会被拒绝的，只是会被固定速率消费而已，所以漏桶在一定程度上也是可以应对突发流量的。

在漏桶算法中，桶的容量决定了系统能够处理的瞬时峰值。当突发流量到来时，如果桶有足够的空间，这些请求将被放入桶中，然后以固定速率被漏桶算法处理。

然而，漏桶算法的特性主要是对整体速率进行控制，而不是对瞬时峰值进行缓冲。漏桶算法可以平滑流量，但并不会增加系统的处理能力。如果突发流量超过了桶的容量，那么超过容量的部分请求将被丢弃或拒绝，漏桶并不能缓冲这些额外的请求。

漏桶也介绍的差不多了，如果让你实现一个漏桶，你会怎么实现呢？首先同样可以使用一个 循环队列数据结构来作为漏桶，大致思路如下：

1. 循环队列的大小即漏桶的大小。
2. 请求过来时相当于入队列，直到循环队列已满，则拒绝请求继续入队列。
3. 起一个单独的线程以固定的速率来消费队列中的元素，知道队列中的元素为空时则阻塞。

参考

固定窗口限流和滑动窗口限流的实现
限流算法的实现