常见的服务限流算法及实现

原创聂丹颖系统工程实验室

服务限流概念

随着现在微服务、分布式系统的发展，各个服务之间的互相调用越来越复杂。为了保证自身服务的稳定性与高可用，需要对超出自身服务处理能力之外的请求进行拦截。

限流的主要目标：

防止服务被突发流量冲垮
防止恶意请求和攻击
限流的处理方式：
拒绝服务
排队等待
服务降级

最简单的做法是拒绝服务，直接抛出异常，返回错误信息（比如返回 HTTP 状态码 429 Too Many Requests），或者给前端返回 302 重定向到一个错误页面，提示用户资源没有了或稍后再试。但是对于一些比较重要的接口不能直接拒绝，比如秒杀、下单等接口，我们既不希望用户请求太快，也不希望请求失败，这种情况一般会将请求放到一个消息队列中排队等待，消息队列可以起到削峰和限流的作用。第三种处理方式是服务降级，当触发限流条件时，直接返回兜底数据，比如查询商品库存的接口，可以默认返回有货。

限流的架构

针对不同的系统架构，需要使用不同的限流方案。如下图所示，服务部署的方式一般可以分为单机模式和集群模式：

单机模式的限流非常简单，可以直接基于内存就可以实现，而集群模式的限流必须依赖于某个“中心化”的组件，比如网关或 Redis。集群中的每个服务必须将自己的流量信息统一汇总到某个地方供其他服务读取，一般来说用 Redis 的比较多，Redis 提供的过期特性和 lua 脚本执行非常适合做限流。

常用限流算法

1 固定窗口计数器

固定窗口计数器(Fixed Window)算法的实现思路非常简单，首先维护一个计数器，将单位时间段当做一个窗口，计数器记录这个窗口接收请求的次数。

当次数少于限流阀值，就允许访问，并且计数器+1
当次数大于限流阀值，就拒绝访问
当前的时间窗口过去之后，计数器清零

假设单位时间是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数。如下图：

计数器算法在单机场景下可以使用 AtomicLong、LongAdder 或 Semaphore 来实现计数，而在分布式场景下可以通过 Redis 的 INCR 和 EXPIRE 等命令并结合 EVAL 或 lua 脚本来实现。

主要优点：实现简单，容易理解

主要缺点：

一段时间内（不超过时间窗口）系统服务不可用

比如窗口大小为1s，限流大小为5，然后恰好在某个窗口的第1ms来了5个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。

存在临界问题，窗口切换时，可能会产生两倍于阈值流量的请求

比如窗口大小为1s，限流大小为5，然后恰好在某个窗口的第0.8-1s来了5个请求，窗口前期没有请求，所以这5个请求都会通过。再恰好，下一个窗口的第0-0.2s又来了5个请求，也全部通过了，那也就是在0.4s之内通过了10个请求，而我们设定的阈值是5，通过的请求达到了阈值的两倍。

代码实现：

/*** 固定窗口计数器法*/publicclassRateLimiterSimpleWindow {// 阈值    privatestatic Integer QPS = 5;// 时间窗口（毫秒）    privatestaticlong TIME_WINDOWS = 1000;// 计数器    privatestatic AtomicInteger REQ_COUNT = new AtomicInteger();    privatestaticlong LAST_REQUEST_TIME = System.currentTimeMillis();    publicsynchronizedstaticbooleantryAcquire() {if ((System.currentTimeMillis() - LAST_REQUEST_TIME) > TIME_WINDOWS) {            REQ_COUNT.set(0);            LAST_REQUEST_TIME = System.currentTimeMillis();        }return REQ_COUNT.incrementAndGet() <= QPS;    }    publicstaticvoidmain(String[] args) throws InterruptedException {for (int i = 0; i < 10; i++) {            Thread.sleep(100);            LocalTime now = LocalTime.now();if (!tryAcquire()) {                System.out.println(now + " 被限流");            } else {                System.out.println(now + " 做点什么");            }        }    }}

2 滑动窗口计数器

滑动窗口算法是固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点。

滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器。当请求的时间大于当前窗口的最大时间时，则将计时窗口向右平移一个小窗口。平移时，将最左边小窗口的数据丢弃，将新的请求放在最右边的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之和不能超过设定的阈值。

一张图解释滑动窗口算法，如下：

假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。每格表示0.2s。每过0.2s，时间窗口就会往右滑动一格。然后呢，每个小周期，都有自己独立的计数器，如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。

我们来看下滑动窗口是如何解决临界问题的？

假设我们1s内的限流阈值还是5个请求，0.8~1.0s内（比如0.9s的时候）来了5个请求，落在黄色格子里。时间过了1.0s这个点之后，又来5个请求，落在紫色格子里。如果**是固定窗口算法，是不会被限流的**，但是**滑动窗口的话，每过一个小周期，它会右移一个小格**。过了1.0s这个点后，会右移一小格，当前的单位时间段是0.2~1.2s，这个区域的请求已经超过限定的5了，已触发限流啦，实际上，紫色格子的请求都被拒绝啦。

TIPS: 当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

主要优点：避免了计数器固定窗口算法固定窗口切换时可能会产生两倍于阈值流量请求的问题；

主要缺点：

流量超过就必须抛弃或者走降级逻辑
对流量控制不够精细，不能限制集中在短时间内的流量，也不能削峰填谷

代码实现：

packagecom.wdbyte.rate.limiter;importjava.time.LocalDateTime;importjava.time.ZoneOffset;importjava.util.Iterator;importjava.util.Map;importjava.util.TreeMap;/*** 滑动窗口限流工具类** @author https://www.wdbyte.com*/publicclassRateLimitSlideWindow {    /**     * 每个小格子的时间窗口大小（单位时间是1分钟，10s一个小格子窗口，一共6个格子）     */    privateint SUB_CYCLE = 10;    /**     * 每分钟限流请求数     */    privateint thresholdPerMin = 10;    /**     * 计数器, key为当前窗口的开始时间值秒，value为当前窗口的计数     */    privatefinal TreeMap<Long, Integer> counters = new TreeMap<>();    /**     * 滑动窗口时间算法实现     */    publicbooleanslidingWindowsTryAcquire() {    //获取当前时间在哪个小周期窗口    long currentTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);    long currentWindowTime = currentTime / SUB_CYCLE * SUB_CYCLE;    //当前窗口总请求数    int currentWindowNum = countCurrentWindow(currentWindowTime);            //超过阀值限流    if (currentWindowNum >= thresholdPerMin) {                returnfalse;            }        //计数器+1        counters.merge(currentWindowTime, 1, Integer::sum);        returntrue;    }    /**     * 统计当前窗口的请求数     */    privateintcountCurrentWindow(long currentWindowTime) {      //计算滑动窗口第一格的开始位置      long startTime = currentWindowTime - (long) SUB_CYCLE * (60 / SUB_CYCLE - 1);      int count = 0;    //遍历存储的计数器            Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();    while (iterator.hasNext()) {                Map.Entry<Long, Integer> entry = iterator.next();    // 删除无效过期的子窗口计数器    if (entry.getKey() < startTime) {                    iterator.remove();                } else {    //累加当前窗口的所有计数器之和                    count = count + entry.getValue();                }            }      return count;      }    publicstaticvoidmain(String[] args) throws Exception {        RateLimitSlideWindow rateLimitSlideWindow = new RateLimitSlideWindow();        int i = 0;        while (i++ < 10) {                    boolean res = rateLimitSlideWindow.slidingWindowsTryAcquire();                    System.out.println("第"+ i + "次请求结果：" + res + rateLimitSlideWindow.counters);                }       }}

3 漏桶算法

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

请求来了放入桶中
桶内请求量满了拒绝请求
服务定速从桶内拿请求处理

可以看到水滴对应的就是请求。它的特点就是**宽进严出**，无论请求多少，请求的速率有多大，都按照固定的速率流出，对应的就是服务按照固定的速率处理请求。面对突发请求，服务的处理速度和平时是一样的。

主要优点：漏桶的漏出速率是固定的，可以起到整流的作用

虽然请求的流量可能具有随机性，忽大忽小，但是经过漏斗算法之后，变成了有固定速率的稳定流量，从而对下游的系统起到保护作用。可以削峰填谷。

漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的打到第三方的接口上。

缺点：响应延迟，并且不能解决流量突发的问题

如果突增的流量对于系统来说完全没有压力，使用漏桶算法，其实是对系统性能的浪费。

代码实现：

publicclassLeakBucketLimiter {    /**     * 每秒处理请求数（出水率）     */    privatelong rate = 2;    /**     * 桶容量     */    privatelong capacity = 10;    /**     * 桶内剩余水量     */    privatelong currentWater;    /**     * 上一次请求时间     */    privatelong refreshTime = System.currentTimeMillis();    /**     * 漏桶算法     *     * @return     */    publicsynchronizedbooleantryAcquire() {      //获取系统当前时间      long currentTime = System.currentTimeMillis();      //流出的水量 =(当前时间-上次刷新时间)* 出水率      long outWater = (currentTime - refreshTime) / 1000 * rate;       // 当前桶内剩余水量 = 之前的桶内水量-流出的水量，不能小于0      currentWater = Math.max(0, currentWater - outWater);       // 刷新时间      refreshTime = currentTime;      // 当前剩余水量还是小于桶的容量，则请求放行      if (currentWater < capacity) {                  currentWater++;                  returntrue;              }      // 当前剩余水量大于等于桶的容量，限流              returnfalse;          }}

4 令牌桶算法

令牌桶和漏桶的原理类似，不过漏桶是**定速地流出**，而令牌桶是**定速地往桶里塞入令牌**，然后请求只有拿到了令牌才能通过，之后再被服务器处理。当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃。规则：

定速的往桶内放入令牌
令牌数量超过桶的限制，丢弃
请求来了先向桶内索要令牌，索要成功则通过被处理，反之拒绝

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

特点分析：

令牌桶算法是对漏桶算法的一种改进，除了能够限制调用的平均速率，还允许一定程度的流量突发。一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。

代码实现：

publicclassTokenBucketLimiter {    /**     * 每秒处理数（放入令牌数量）     */    privatelong putTokenRate = 1;    /**     * 最后刷新时间     */    privatelong refreshTime = System.currentTimeMillis();    /**     * 令牌桶容量     */    privatelong capacity = 10;    /**     * 当前桶内令牌数     */    privatelong currentToken = 0L;    /**     * 漏桶算法     *     * @return     */    booleantokenBucketTryAcquire() {    //获取系统当前时间    long currentTime = System.currentTimeMillis();    //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌速率    long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate;    // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量    currentToken = Math.min(capacity, generateToken + currentToken);    // 刷新时间    refreshTime = currentTime;    //桶里面还有令牌，请求正常处理    if (currentToken > 0) {            currentToken--; //令牌数量-1            returntrue;         }        returnfalse;    }}

开源限流方案

1 RateLimiter

Guava的`RateLimiter`提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

Guava 地址：https://github.com/google/guava

1、SmoothBursty：令牌的生成速度恒定。使用 RateLimiter.create(double permitsPerSecond) 创建的是 SmoothBursty 实例。

2、SmoothWarmingUp：令牌的生成速度持续提升，直到达到一个稳定的值。WarmingUp，顾名思义就是有一个热身的过程。使用 RateLimiter.create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) 时创建就是 SmoothWarmingUp 实例，其中 warmupPeriod 就是热身达到稳定速度的时间。

如下：创建一个限流器，设置每秒放置的令牌数为5个。返回的RateLimiter对象可以保证1秒内不会给超过5个令牌，并且以固定速率进行放置，达到平滑输出的效果。

publicvoidtestSmoothBursty() {  // 限流器容量为5，并且每秒生成5个令牌  RateLimiter r = RateLimiter.create(5);  for (int i = 0; i++ < 2; ) {       
        System.out.println("get 5 tokens: " + r.acquire(5) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("get 1 tokens: " + r.acquire(1) + "s");
        System.out.println("end");
  }
    /**    * 控制台输出    * get 5 tokens: 0.0s      初始化时桶是空的，直接从空桶获取5个令牌    * get 1 tokens: 0.998068s 滞后效应，需要替前一个请求进行等待    * get 1 tokens: 0.196288s    * get 1 tokens: 0.200394s    * end    * get 5 tokens: 0.195756s    * get 1 tokens: 0.995625s 滞后效应，需要替前一个请求进行等待    * get 1 tokens: 0.194603s    * get 1 tokens: 0.196866s    * end    */}

第一次请求之所以不需要等待是因为令牌桶的预消费特性。

2 Bucket4j

基于令牌桶算法实现的限流库，Bucket4j 地址：https://github.com/vladimir-bukhtoyarov/bucket4j

Bucket4j不仅支持单机限流，还支持通过诸如 Hazelcast、Ignite、Coherence、Infinispan 或其他兼容 JCache API (JSR 107) 规范的分布式缓存实现分布式限流。

缺点：只支持请求频率限流；不能使用redis做分布式限流。

Refill – 令牌的填充速度。

Bandwidth – 带宽，也就是每秒能够通过的流量，自动维护令牌生产。

Bucket – 桶，不论状态，或是令牌的消费，`bucket`是我们操作的入口。

tryConsume：尝试消费n个令牌，返回布尔值，表示能够消费或者不能够消费，给我们判断依据。

使用示例：创建一个容量为10的存储桶，每秒填充5个令牌：

publicstaticvoidmain(String[] args) {  Bandwidth limit = Bandwidth.simple(10, Duration.ofSeconds(1));  Bucket bucket = Bucket4j.builder().addLimit(limit).build();  if(bucket.tryConsume(1)){    System.out.println("do something");‍     ‍   ‍  ‍‍}else{‍    System.out.println("do nothing");  }}

3 Hystrix

Netflix开源的熔断组件，支持两种资源隔离策略：THREAD（默认）或者SEMAPHORE

线程池：每个command运行在一个线程中，限流是通过线程池的大小来控制的
信号量：command是运行在调用线程中，但是通过信号量的容量来进行限流

Hystrix默认是线程池策略，对每一个资源创建一个线程池以进行流量管控，优点是资源隔离彻底，缺点增加了线程切换的成本，还需要预先给各个资源做线程池大小的分配。

使用样例：

// HelloWorldHystrixCommand要使用Hystrix功能publicclassHelloWorldHystrixCommandextends HystrixCommand {    privatefinal String name;    publicHelloWorldHystrixCommand(String name) {         super(HystrixCommandGroupKey.Factory.asKey("ExampleGroup"));           this.name = name;    }  // 如果继承的是HystrixObservableCommand，要重写Observable construct()  @Override  protected String run() {         return"Hello " + name;   }}

调用该command：

String result = new HelloWorldHystrixCommand("HLX").execute();
System.out.println(result);  // 打印出Hello HLX

Hystrix已经在2018年停止开发，官方推荐替代项目[Resilience4j](https://resilience4j.readme.io/)

4 Sentinel

Sentinel 是阿里巴巴提供的一种限流、熔断中间件，与RateLimiter相比，Sentinel提供了丰富的限流、熔断功能。它支持控制台配置限流、熔断规则，支持集群限流，并可以将相应服务调用情况可视化。文档地址：https://sentinelguard.io/zh-cn/docs/introduction.html。

底层统计采用滑动窗口算法，限流方面有两种使用方式：API调用和注解，内部采责任链来统计和执行校验规则。通过为方法增加注解`@SentinelResource(String name)`或者手动调用`SphU.entry(String name)`方法开启流控。

Sentinel基本概念：

-资源：被保护的逻辑，可以是一个服务，服务里的方法，也可以是一段代码，用`SphU.entry("HelloWorld")`和`entry.exit()`包围起来

-规则：围绕资源的实时状态设定的规则，可以包括流量控制规则、熔断降级规则以及系统保护规则。所有规则可以动态实时调整。

使用API手动调用流控示例：

publicstaticvoidmain(String[] args) {  // 配置规则.  initFlowRules();  while (true) {    // 1.5.0 版本开始可以直接利用 try-with-resources 特性    try (Entry entry = SphU.entry("HelloWorld")) {    // 被保护的逻辑      System.out.println("hello world");    } catch (BlockException ex) {      // 处理被流控的逻辑      System.out.println("blocked!");    }  }}  //资源 HelloWorld 每秒最多只能通过 20 个请求。    privatestaticvoidinitFlowRules(){        List<FlowRule> rules = new ArrayList<>();        FlowRule rule = new FlowRule();        rule.setResource("HelloWorld");        rule.setGrade(RuleConstant.FLOW_GRADE_QPS);        // Set limit QPS to 20.        rule.setCount(20);        rules.add(rule);        FlowRuleManager.loadRules(rules);    }

分布式限流

分布式限流针对的分布式/微服务应用架构应用，在这种架构下，单机限流就不适用了，因为会存在多种服务，并且一种服务也可能会被部署多份。

分布式限流常见的方案：

-借助中间件件限流**：可以借助 Sentinel 或者使用 Redis 来自己实现对应的限流逻辑。

-网关层限流：比较常用的一种方案，直接在网关层把限流给安排上了。不过，通常网关层限流通常也需要借助到中间件/框架。就比如 Spring Cloud Gateway 的分布式限流实现`RedisRateLimiter`就是基于 Redis+Lua 来实现的，再比如 Spring Cloud Gateway 还可以整合 Sentinel 来做限流。

如果你要基于 Redis 来手动实现限流逻辑的话，建议配合 Lua 脚本来做。

为什么建议 Redis+Lua 的方式？

主要有两点原因：

-减少了网络开销：我们可以利用 Lua 脚本来批量执行多条 Redis 命令，这些 Redis 命令会被提交到 Redis 服务器一次性执行完成，大幅减小了网络开销。

-原子性：一段 Lua 脚本可以视作一条命令执行，一段 Lua 脚本执行过程中不会有其他脚本或 Redis 命令同时执行，保证了操作不会被其他指令插入或打扰。

Redis通过lua脚本实现令牌桶

实现思路是获取令牌后，用SET记录“请求时间”和“剩余token数量”。

每次请求令牌时，通过这两个参数和请求的时间、流速等参数进行计算，返回是否获取令牌成功。

获取令牌lua脚本：

local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')local last_time = ratelimit_info[1]local current_token = tonumber(ratelimit_info[2])local max_token = tonumber(ARGV[1])local token_rate = tonumber(ARGV[2])local current_time = tonumber(ARGV[3])local reverse_time = 1000/token_rateif current_token == nilthen  current_token = max_token  last_time = current_timeelselocal past_time = current_time-last_timelocal reverse_token = math.floor(past_time/reverse_time)current_token = current_token+reverse_tokenlast_time = reverse_time*reverse_token+last_timeif current_token>max_token then    current_token = max_token  endendlocal result = 0if(current_token>0) then  result = 1  current_token = current_token-1endredis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))return result

初始化令牌桶lua脚本：

local result=1redis.pcall("HMSET",KEYS[1],"last_mill_second",ARGV[1],"curr_permits",ARGV[2],"max_burst",ARGV[3],"rate",ARGV[4])return result

继续滑动看下一个