限流是什么？

限流在日常生活中限流很常见，例如去有些景区玩，每天售卖的门票数是有限的，例如 2000 张，即每天最多只有 2000 个人能进去游玩。那在我们工程上限流是什么呢？限制的是 「流」，在不同场景下「流」的定义不同，可以是每秒请求数、每秒事务处理数、网络流量等等。通常意义我们说的限流指代的是限制到达系统的并发请求数，使得系统能够正常的处理部分用户的请求，来保证系统的稳定性。

限流的本质是因为后端处理能力有限，需要截掉超过处理能力之外的请求，亦或是为了均衡客户端对服务端资源的公平调用，防止一些客户端饿死。

为什么要限流？

• 为了保证系统的稳定性。

日常的业务上有类似秒杀活动、双十一大促或者突发新闻等场景，用户的流量突增，后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮。另外像爬虫之类的不正常流量，我们对外暴露的服务都要以最大恶意为前提去防备调用者。我们不清楚调用者会如何调用我们的服务，假设某个调用者开几十个线程一天二十四小时疯狂调用你的服务，如果不做啥处理咱服务基本也玩完了，更胜者还有ddos攻击。

• 保证资源公平利用

对于很多第三方开放平台来说，不仅仅要防备不正常流量，还要保证资源的公平利用，一些接口资源不可能一直都被一个客户端占着，也需要保证其他客户端能正常调用。

例子：高德开放平台流量限制说明

图片

常见的限流算法

1、计数器限流

计数器限流也就是最简单的限流算法就是计数限流了。例如系统能同时处理 100 个请求，保存一个计数器，处理了一个请求，计数器就加一，一个请求处理完毕之后计数器减一。每次请求来的时候看看计数器的值，如果超过阈值就拒绝。计数器的值要是存内存中就算单机限流算法，如果放在第三方存储里（例如Redis中）集群机器访问就算分布式限流算法。

• 优点：简单，单机在 Java 中可用 Atomic 等原子类、分布式就使用 Redis incr命令。

• 缺点：假设我们允许的阈值是1万，此时计数器的值为 0，当 1 万个请求在1秒内全部请求进来，那么服务可能就扛不住了。

计数器限流伪代码实现

boolean tryAcquire() {
    if (counter < threshold)  {
        counter++;
        return true;
    }
    return false;
}

boolean tryRelease() {
    if (counter > 0)  {
        counter--;
        return true;
    }
    return false;
}

一般的限流都是为了限制在指定时间间隔内的访问量，因此还有个算法叫固定窗口。

2、固定窗口限流

它相比于计数限流主要是多了个时间窗口的概念，计数器每过一个时间窗口就重置。规则如下：

• 请求次数小于阈值，允许访问并且计数器 +1；

• 请求次数大于阈值，拒绝访问；

• 这个时间窗口过了之后，计数器清零；

固定窗口限流伪代码实现

boolean trvAcquire() {
    // 获取当前时间
    long now = currentTimeMillis( )；
    // 看是否过了时间窗口
    if (now - lastAcquireTime > TimeWindow ） { 
        // 计数器置零
        counter = 0;
        lastAcquireTime = now;
    }
    // 小于阈值
    if (counter < threshold) { 
        counter++;
        return true;
    }
    return false
}

这种方式也会面临一些问题，例如固定窗口临界问题：假设系统每秒允许 100 个请求，假设第一个时间窗口是 0-1s，在第 0.55s 处一下次涌入 100 个请求，过了 1 秒的时间窗口后计数清零，此时在 1.05 s 的时候又一下次涌入100个请求。虽然窗口内的计数没超过阈值，但是全局来看在 0.55s-1.05s 这 0.1 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。

image-20210420115824978

为了解决这个问题，业界又提出另外一种限流算法，即滑动窗口限流。

3、滑动窗口限流

滑动窗口限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值。相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。

规则如下，假设时间窗口为 1 秒：

• 记录每次请求的时间

• 统计每次请求的时间至往前推1秒这个时间窗口内的请求数，并且1 秒前的数据可以清除。

• 统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

滑动窗口

图片

滑动窗口伪代码实现

boolean tryAcquire() {
    long now = currentTimenillis(); 
    // 根据当前时间获取时间窗口内的计数
    long counter = getCounterInTimewindow(now);

    // 小于阈值
    if (counter < threshold）{ 
        // 记录当前时间
        addToTimewindow(now)；
        return true;
    }
    return false;

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

而漏桶算法，可以解决时间窗口类的痛点，使得流量更加平滑。

4、漏桶算法

如下图所示，水滴持续滴入漏桶中，底部定速流出。如果水滴滴入的速率大于流出的速率，当存水超过桶的大小的时候就会溢出。

规则如下：

• 请求来了放入桶中（不限制流入速率）

• 桶内请求量满了拒绝请求

• 服务定速从桶内拿请求处理（定速流出）

漏桶算法示意图

图片

漏桶伪代码实现

LeakyDemo {
  public long timeStamp = getNowTime();
  public int capacity; // 桶的容量
  public int rate; // 水漏出的速度
  public Long water; // 当前水量(当前累积请求数)
  public boolean grant() {
    long now = getNowTime();
    water = Math.max(0L, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
    timeStamp = now;
    if ((water + 1) < capacity) {
      // 尝试加水,并且水还未满
      water += 1;
      return true;
    }
    else {
    // 水满，拒绝加水
    return false;
    }
 }
 private static Long getNowTime(){
   return System.currentTimeMillis();
 }
}

水滴对应的就是请求。

• 特点：流量宽进严出。无论请求多少，请求的速率有多大，都按照固定的速率流出，对应的就是服务按照固定的速率处理请求。和消息队列思想有点像，削峰填谷。一般而言漏桶也是由队列来实现的，处理不过来的请求就排队，队列满了就拒绝请求。

与线程池实现的方式方式如出一辙。

• 缺点

面对突发请求，服务的处理速度和平时是一样的，这并非我们实际想要的。我们希望的是在突发流量时，在保证系统平稳的同时，也要尽可能提升用户体验，也就是能更快地处理并响应请求，而不是和正常流量一样循规蹈矩地处理。

而令牌桶在应对突击流量的时候，可以更加的“激进”。

5、令牌桶算法

令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然后请求只有拿到了令牌才能通过，之后再被服务器处理。

当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃。

规则：

• 定速的往桶内放入令牌（定速生成）

• 令牌数量超过桶的限制，丢弃

• 请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝

令牌桶

图片

令牌桶的原理与JUC的Semaphore 信号量很相似，信号量可控制某个资源被同时访问的个数，其实和拿令牌思想一样，不同的是一个是拿信号量，一个是拿令牌。信号量用完了返还，而令牌用了不归还，因为令牌会定时再填充。

借助Semaphore实现单机流量限制（其原理与令牌桶算法基本一致）

import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;

/**
 * @author: xiebochang
 * @Title: SemaphoreLocalRateLimiter
 * @date: 2021/4/20
 */
public class SemaphoreLocalRateLimiter {

    public static void main (String[] args) {
        ExecutorService service = Executors.newFixedThreadPool(10);
        // 最多允许5个线程同时访问
        int limit = 5;
        Semaphore semaphore = new Semaphore(limit);
        // 模拟10个请求同时涌进来
        int requiredCount = 10;
        for (int i = 0; i < requiredCount; i++) {
        final int num = i;
        service.submit(() -> {
            try {
                // 获取许可
                semaphore.acquire();
                // 每个线程睡[0,10)s后释放许可
                System.out.println(num + "获得许可，开始执行");
                long sleepTime = new Random().nextInt(10000);
                Thread.sleep(sleepTime);
                semaphore.release();
                System.out.println(num + "释放许可，" + "休眠了" + sleepTime + "ms");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
 }
   service.shutdown();
 /**
 *
 * 执行结果示例：(在5个许可发放完毕后，只有等拿到许可的线程释放了许可，其它未获取许可的线程才能获取许可，执行业务代码)
 *
 * 5获得许可，开始执行
 * 0获得许可，开始执行
 * 4获得许可，开始执行
 * 2获得许可，开始执行
 * 3获得许可，开始执行
 * 3释放许可，休眠了964ms
 * 1获得许可，开始执行
 * 0释放许可，休眠了5139ms
 * 6获得许可，开始执行
 * 5释放许可，休眠了6105ms
 * 7获得许可，开始执行
 * 7释放许可，休眠了319ms
 * 8获得许可，开始执行
 * 4释放许可，休眠了6912ms
 * 9获得许可，开始执行
 * 2释放许可，休眠了8870ms
 * 8释放许可，休眠了3079ms
 * 1释放许可，休眠了9480ms
 * 6释放许可，休眠了6018ms
 * Disconnected from the target VM, address: '127.0.0.1:64441', transport: 'socket'
 * 9释放许可，休眠了7000ms
 *
 **/
 }

}

Guava包RateLimiter实现简单限流

/**
 * 简单的tryAcquire
 *
 * @param
 * @return void
 **/
 private static void testSimpleTryAcquire () throws InterruptedException {
    RateLimiter limiter = RateLimiter.create(2);
    while (true) {
    Thread.sleep(2000);
    System.out.println("tryAcquire:" + limiter.tryAcquire(2));
 }
 /**
 *
 * output:
 *
 * tryAcquire:true
 * tryAcquire:true
 * tryAcquire:true
 *
 **/
 }

 /**
 *
 * 默认使用SmoothBursty -- 平滑突发限流
 * 一开始便初始化填入permitsPerSecond个令牌
 * 不预热，一开始就固定令牌生成速率
 *
 * @param permitsPerSecond -- 每秒生成token数
 * @param requiredPermits -- 请求token数
 * @return void
 **/
 private static void simpleSmoothBursty (double permitsPerSecond, int requiredPermits) {
    RateLimiter limiter = RateLimiter.create(permitsPerSecond);
    int i = 1;
    while (true) {
    System.out.println("round " + i + ":get " + requiredPermits + " tokens spend:" + limiter.acquire(requiredPermits) + "s");
    i ++;
 }
 /**
 * permitsPerSecond = 2，requiredPermits = 2
 *
 * output:
 *
 * round 1:get 2 tokens spend:0.0s
 * round 2:get 2 tokens spend:0.997221s
 * round 3:get 2 tokens spend:0.99515s
 * round 4:get 2 tokens spend:0.992469s
 * round 5:get 2 tokens spend:0.996439s
 * round 6:get 2 tokens spend:0.999554s
 *
 **/
 }

简单令牌桶算法伪代码

/**
 * @author: xiebochang
 * @Title: LocalRateLimiter
 * @date: 2021/4/20
 */
public class LocalRateLimiter {

    private long tokens = getInitTokens();
    private long lastRefreshTime = getInitLastRefreshTime();
    private int rate = 1; // 1ms生成1个

    public boolean tryGrant (long required, long capacity) {
        long now = System.currentTimeMillis();
        // 计算生成令牌数
        long generateTokens = Math.max(0, (now - lastRefreshTime) * rate);
        // 可取令牌数
        long currTokens = Math.min(tokens + generateTokens, capacity);
        // 是否足够取
        boolean allowed = currTokens >= required;
        if (allowed) {
            tokens = currTokens - required;
            lastRefreshTime = now;
            return true;
        }
        return false;
     }

    private long getInitTokens() {
      return 100;
    }

    private long getInitLastRefreshTime() {
        return lastRefreshTime > 0 ? lastRefreshTime : System.currentTimeMillis() - 1000;
    }

    public static void main (String[] args) throws InterruptedException {
        LocalRateLimiter limiter = new LocalRateLimiter();
        System.out.println(limiter.tryGrant(1200, 3000));
        Thread.sleep(1000);
        System.out.println(limiter.tryGrant(2100, 3000));
    }
}

对比漏桶算法可以看出令牌桶更适合应对突发流量，假如桶内有 100 个令牌，那么这100个令牌可以马上被取走，而不像漏桶那样匀速的消费。不过上面批量获取令牌也会致使一些新的问题出现，比如导致一定范围内的限流误差，举个例子你取了 10 个此时不用，等下一秒再用，那同一时刻集群机器总处理量可能会超过阈值，所以现实中使用时，可能不会去考虑redis频繁读取问题，转而直接采用一次获取一个令牌的方式，具体采用哪种策略还是要根据真实场景而定。

限流算法总结

1、计数器 VS 固定窗口 VS 滑动窗口

计数器可以说是固定窗口的低精度实现，固定窗口又可以说是滑动窗口的低精度实现。

因此在限流时间精度上，三种算法关系为：计数器<固定窗口<滑动窗口

但精度的精确同时也要消耗内存，因此三种算法内存占用关系为：计数器<固定窗口<滑动窗口

2、漏桶算法 VS 令牌桶算法

两者都比较适合阻塞式的限流场景。（类似分布式锁，获取不到令牌则一直等待）

漏桶算法是将请求暂存于桶内，再定速处理，不大符合互联网业务中低延迟的需求，用户体验不佳。而令牌桶算法在限流时，还可应对突增流量的场景（可以批量获取令牌），对用户端的体验较好。

但令牌桶算法使用不当也有弊端，比如上线初期未对桶内的令牌做初始化，在第一批令牌还未生成时接受到请求会被丢弃，造成误杀。

总的来说

• 计数器比较适合简单、粗力度限流需求

• 固定/滑动窗口则适合对响应时间要求较高的限流场景，比如一些微服务接口

• 漏桶算法则比较适合后台任务类的限流场景

• 令牌桶则适用于大流量接口，特别是有瞬时流量较高的接口限流场景。

单机限流和分布式限流

单机限流和分布式限流本质上的区别在于 “阈值” 存放的位置，单机限流就是“阀值”存放在单机部署的服务/内存中，但我们的服务往往是集群部署的，因此需要多台机器协同提供限流功能。像上述的计数器或者时间窗口的算法，可以将计数器存放至 Redis 等分布式 K-V 存储中。又如滑动窗口的每个请求的时间记录可以利用 Redis 的 zset 存储，利用ZREMRANGEBYSCORE 删除时间窗口之外的数据，再用 ZCARD计数，

限流的难点

• 如何设定阀值？

可以看到，每个限流都有个阈值，这个阈值如何定是个难点。定大了服务器可能顶不住，定小了就“误杀”了，没有资源利用最大化，对用户体验不好。一般的做法是限流上线之后先预估个大概的阈值，然后不执行真正的限流操作，而是采取日志记录方式，对日志进行分析查看限流的效果，然后调整阈值，推算出集群总的处理能力，和每台机子的处理能力(方便扩缩容)。然后将线上的流量进行重放，测试真正的限流效果，最终阈值确定，然后上线。

其实真实的业务场景很复杂，需要限流的条件和资源很多，每个资源限流要求还不一样。

限流组件

一般而言，我们不需要自己实现限流算法来达到限流的目的，不管是接入层限流还是细粒度的接口限流，都有现成的轮子使用，其实现也是用了上述我们所说的限流算法。

• Google Guava 提供的限流工具类 RateLimiter，是基于令牌桶实现的，并且扩展了算法，支持预热功能。

• 阿里开源的限流框架Sentinel 中的匀速排队限流策略，就采用了漏桶算法。

• Nginx 中的限流模块 limit_req_zone，采用了漏桶算法，还有 OpenResty 中的 resty.limit.req库等等。

• 基于redis lua脚本 / redisson实现的令牌桶。

具体的使用还是很简单的，有兴趣的同学可以自行搜索，对内部实现感兴趣的同学可以下个源码看看，学习下生产级别的限流是如何实现的。

总结

限流具体应用到工程还是有很多点需要考虑的，并且限流只是保证系统稳定性中的一个环节，还需要配合降级、熔断等相关内容。