Sentinel核心算法解析の漏桶算法

前言

  在Sentinel中，流控效果有快速失败、预热和排队等待。其中排队等待的实现，利用的是漏桶算法。

一、回顾：排队等待

  首先演示一下排队等待的效果，下面的设置代表每秒只允许一次请求通过：

  使用压测工具进行测试，在没有进行流控的情况下，所有的请求是在1s内全部执行完毕，现在则是每秒放行1个请求，匀速通过：

二、漏桶算法

  漏桶算法是一种常用的流量整形和限流算法，主要用于控制请求处理的速率，防止突发请求压垮系统。其名字来源于一个形象的比喻：水以任意速率流入漏桶中，但只能以固定速率流出。漏桶算法通过维护一个固定容量的“桶”和一个固定的出流速率，来限制请求的处理速率。

1. 每个请求都视为一滴“水”。
2. 请求到来时，尝试放入漏桶：
   • 如果桶未满，请求进入，等待被处理；
   • 如果桶已满，请求被丢弃或延迟处理。
3. 系统以固定速率从桶中取出请求进行处理。

  一个漏桶算法的简单实现：

public class LeakyBucket {
    private final int capacity;        // 漏桶容量
    private final int outRate;         // 出水速率（单位：请求/秒）
    private int water = 0;             // 当前水量（当前排队请求数）

    private final ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();

    public LeakyBucket(int capacity, int outRate) {
        this.capacity = capacity;
        this.outRate = outRate;

        // 启动定时任务，每秒漏出一定的水
        executor.scheduleAtFixedRate(() -> {
            if (water == 0){
                return;
            }
            //防止减到负数的情况
            int leakAmount = Math.min(water,outRate);
            water = water - leakAmount;
        }, 0, 1, TimeUnit.SECONDS);

    }

    /**
     * 请求尝试进入漏桶
     * @return true 表示允许处理；false 表示被限流
     */
    public synchronized boolean tryRequest(){
        if (water>capacity){
            System.out.println("桶已满，请求被拒绝！");
            return false;
        }
        water ++;
        System.out.println("请求通过，当前桶内水量：" + water);
        return true;

    }

    /**
     * 关闭线程池
     */
    public void shutDown(){
        this.executor.shutdown();
    }

    public static void main(String[] args) throws InterruptedException {
        LeakyBucket bucket = new LeakyBucket(5, 2); // 容量 5，每秒处理 2 个请求

        // 模拟高并发请求
        for (int i = 0; i < 10; i++) {
            boolean accepted = bucket.tryRequest();
            Thread.sleep(200); // 每 200ms 发一个请求
        }

        // 稍等以观察漏水效果
        Thread.sleep(5000);
        bucket.shutDown();
    }
}

  每秒漏出的水量都是固定的，但是灌入的水量是不确定的：

请求通过，当前桶内水量：1
漏出水量：1，当前桶内水量：0
请求通过，当前桶内水量：1
请求通过，当前桶内水量：2
请求通过，当前桶内水量：3
请求通过，当前桶内水量：4
请求通过，当前桶内水量：5
漏出水量：2，当前桶内水量：3
请求通过，当前桶内水量：4
请求通过，当前桶内水量：5
桶已满，请求被拒绝！
桶已满，请求被拒绝！
漏出水量：2，当前桶内水量：3
漏出水量：2，当前桶内水量：1
漏出水量：1，当前桶内水量：0

三、源码体现

  Sentinel的漏桶算法，体现在RateLimiterController的canPass方法中。
  RateLimiterController有三个属性：

1. maxQueueingTimeMs：最大排队时间（毫秒），限流器会尝试让请求排队等待通过，如果一个请求到来时，预计要等待的时间超过该值，则会被拒绝处理（限流）。对应的是控制台页面上的超时时间。
2. count：每秒允许通过的请求数（QPS）。对应的是控制台页面上的单机阈值
3. latestPassedTime：上一个被允许通过的请求时间戳（毫秒）。初始值为 -1，表示还没有请求通过，每当一个请求被允许通过，就更新为当前时间。

  在canPass方法中，首先会进行判断，如果当前没有请求，则直接放行。每秒允许通过的请求数为0或小于0，则直接返回失败，表示接口不再接收新的请求。

  然后获取当前时间，并且计算costTime，表示本次请求所需“时间成本”，也就是按照 QPS 匀速计算出来的请求间隔。例如我现在有2个请求，但是每秒允许通过的请求数为1，则计算出的costTime为2000。代表这次请求通过之后，必须间隔 2000ms才能让下一个请求通过，否则就需要排队或者被拒绝。

  获取expectedTime，使用上一步计算出的costTime加上上一个被允许通过的请求时间戳。latestPassedTime.get() 是上一个通过请求的时间，expectedTime 是这个请求应该被处理的“最早”时间点。如果现在已经到了这个时间点，则说明可以直接通过了。假设上一个被允许通过的请求时间戳是500，则计算出的结果是 500 + 2000 = 2500,后续会再次用当前时间进行判断，在 2500ms 之前的请求，都会被认为“来得太早”，要么排队，要么拒绝。

  然后会进行判断：

• expectedTime小于当前时间，则将latestPassedTime更新为当前时间，并且立即放行请求。

• 否则就计算等待时间 = expectedTime - 当前时间。
  • 如果等待时间大于控制台配置的超时时间，则直接限流。
  • 否则继续进行“排队尝试”。（排队等待的体现），更新 latestPassedTime 并尝试进入排队，如果排队等待超时，需要回滚时间（撤销之前的排队），并且限流。如果 waitTime 合理，当前线程进入等待，然后放行。

  该方法的目的是，控制请求通过的速率，如果来得太快就排队，如果排队太久就拒绝。

总结

  Sentinel 的排队等待机制采用了漏桶算法来实现流量控制。漏桶算法的核心思想是：控制请求处理的速率，而不是请求到达的速率。桶的容量是固定的，当短时间内大量请求突发到达时，如果超出系统处理能力，部分请求将被直接拒绝。而系统会以固定速率从“桶”中取出请求进行处理，从而达到匀速限流的目的。

  例如：

• count = 5 → 表示每秒允许通过 5 个请求，即 每隔 200ms 允许一个请求通过
• maxQueueingTimeMs = 500 → 表示请求最多可以排队等待 500ms

  具体示例如下：

1. 请求1 到达：
   • 当前无请求，立即通过
   • 设置 latestPassedTime = t1
2. 请求2 到达，时间距请求1仅 100ms：
   • 请求间隔 < 200ms，节奏未满足
   • 预计等待时间为 100ms < 500ms，允许排队
   • 更新 latestPassedTime = t1 + 200ms
3. 请求3 到达，距请求1为 300ms：
   • 请求预计等待 300ms < 500ms，允许排队
   • 更新 latestPassedTime = t1 + 400ms
4. 请求4 到达，距请求1为 500ms：
   • 预计等待时间为 800ms - t1 = 超出最大排队时间 500ms
   • 请求被拒绝

  通过上述示例可以看出，Sentinel 的漏桶实现并不直接控制请求的突发量，而是通过排队和限时机制，以固定速率处理请求，同时保证排队等待时间不会过长，从而避免系统过载。