前言

在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。那么何为限流呢？顾名思义，限流就是限制流量，就像你宽带包了1个G的流量，用完了就没了。通过限流，我们可以很好地控制系统的qps，从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。

几种常见的限流方法

计数器固定窗口算法

计数器算法是限流算法里最简单也是最容易实现的一种算法。

比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，具体算法的示意图如下：

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }

    public long getNowTime() {
        return System.currentTimeMillis();
    }
}

问题

这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题，我们看下图：

从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

聪明的朋友可能已经看出来了，刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？或者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。

计数器滑动窗口算法

滑动窗口，又称rolling window。为了解决这个问题，我们引入了滑动窗口算法。如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。下面这张图，很好地解释了滑动窗口算法：

在上图中，整个红色的矩形框表示一个时间窗口，在我们的例子中，一个时间窗口就是一分钟。然后我们将时间窗口进行划分，比如图中，我们就将滑动窗口 划成了6格，所以每格代表的是10秒钟。每过10秒钟，我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒的时候到达，那么0:30~0:39对应的counter就会加1。

那么滑动窗口怎么解决刚才的临界问题的呢？如上述问题图示，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发了限流。

我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

伪代码

主要思路是:

  1. 定义滑动窗口大小windowSize
  2. 使用windowStart和windowEnd表示窗口开始和结束位置
  3. 当windowEnd向右滑动时,将新元素加入窗口
  4. 如果windowEnd - windowStart >= windowSize,表示窗口满了,移出最左侧元素
  5. 当窗口长度为size时,输出当前窗口内元素之和
  6. windowEnd向右滑动直到数组末尾

通过维护这个滑动窗口,就可以计算出每个大小为windowSize的子数组的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int windowSize = 5; // 滑动窗口大小
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 输入数组 

int windowStart = 0; // 滑动窗口开始位置
int windowSum = 0; // 滑动窗口数值之和

for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
  windowSum += arr[windowEnd]; // 添加新元素到窗口
    
  if (windowEnd >= windowSize) {
    // 窗口移出旧元素  
    windowSum -= arr[windowStart]; 
    windowStart++;
  }
  
  if (windowEnd >= windowSize - 1) {  
    // 窗口长度为size时,输出当前窗口和
    System.out.println(windowSum);
  }
}

令牌桶算法

令牌桶算法是比较常见的限流算法之一，大概描述如下：
1）、所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2）、根据限流大小，设置按照一定的速率往桶里添加令牌；
3）、桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝；
4）、请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；
5）、令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流；

伪代码

主要逻辑:

  1. 定义桶的容量和放入速率
  2. 使用队列作为令牌桶
  3. 每秒按速率放入令牌直到桶满
  4. 请求获取令牌时判断是否足够,足够则获取处理请求,不足则拒绝
  5. 获取令牌后从队列中移除

通过控制放入和获取令牌的速率,可以起到限流作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 令牌桶容量 
int bucketCapacity = 5;
// 每秒放入令牌数
int tokensPerSecond = 1;  
// 可存放令牌的队列
Queue<Integer> tokens = new LinkedList<>();
// 初始化放入令牌
for(int i = 0; i < bucketCapacity; i++) {
  tokens.add(1); 
}
while (true) {
  // 每秒向桶中放入新令牌
  for (int i = 0; i < tokensPerSecond; i++) {
    if (tokens.size() < bucketCapacity) {
      tokens.add(1);
    }
  }
  // 模拟请求获取令牌
  int tokensToGet = 2;
  if (tokens.size() >= tokensToGet) {
    // 获取令牌
    for (int i = 0; i < tokensToGet; i++) {
      tokens.poll(); 
    }
    // 处理请求
    handleRequest();
  } else {
    // 拒绝请求
    rejectRequest(); 
  }
  // 等待1秒
  waitFor1Second(); 
}

特点

  • 能够限制调用的平均速率
  • 允许一定程度的突发调用

漏桶算法

漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

伪代码

主要逻辑:

  1. 定义漏桶容量和流出速率
  2. 将请求放入队列作为漏桶
  3. 如果漏桶满了就丢弃多的请求
  4. 按速率从桶中取出请求处理
  5. 取出请求后从队列中删除

通过控制流出速率,可以平滑请求流量,起到限流的作用。

相比令牌桶算法,漏桶算法更适合用来平滑突发流量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 漏桶的容量
int bucketCapacity = 5;  
// 漏洞流出速率 
int drainRatePerSecond = 1;
// 用队列模拟漏桶
Queue<Integer> bucket = new LinkedList<>();
while (true) {
  // 接收新请求
  int request = receiveRequest(); 
  // 将请求放入桶中
  bucket.offer(request);
  // 如果桶满了,丢弃多的请求
  if (bucket.size() > bucketCapacity) {
    bucket.poll();
  }
  // 按速率处理请求
  for (int i = 0; i < drainRatePerSecond; i++) {
    if (!bucket.isEmpty()) {
      // 从桶中取出请求并处理
      int currentRequest = bucket.poll();
      handleRequest(currentRequest);
    }
  }
  // 等待1秒
  waitFor1Second();
}

缺点

  • 无法面对突发的大流量

    比如：请求处理速率为1000/s，容量为5000，来了一波2000/s的请求持续10s，那么5s后会有大量的请求被丢弃。

  • 无法有效利用网络资源

    比如：服务器的处理能力是1000/s，连续5s每秒请求量分别为1200、1300、1200、500、800，平均下来QPS也是1000/s，但是有700个请求被拒绝。