限流算法

漏桶算法

漏桶算法的思路很简单,请求先进入到漏桶里,漏桶以固定速度出水,也就是处理请求当水加的过快,则会直接溢出,也就是拒绝请求,可以看出漏桶算法执行强行限制数据的传输速度

但是对于很多常见来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发.这时候漏桶算法可能就不合适了,令牌桶算法更合适

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,如果请求需要被处理,则需要从桶里获取出一个令牌,当桶里没有令牌时,则拒绝服务

代码

public class TaskRunnable implements Runnable {
    private Integer reqCount;//已使用令牌数量
    public TaskRunnable(int reqCount) {
        this.reqCount = reqCount;
    }
    @Override
    public void run() {
        System.out.println(Thread.currentThread().getName() + "已经执行...,目前已使用令牌数：" + reqCount);
    }
}

代码

public class TokenTask {
    //关键：时间控制周期+令牌桶容量
    static volatile long timeStamp = getNowTime();//令牌桶计时开始
    static AtomicInteger reqCount = new AtomicInteger(0);//统计调用数
    static final int maxReqCount = 5;//时间周期内最大请求数
    static final long effectiveDuration = 1000;//时间控制周期(秒)
    /**
     * 限流逻辑
     * @return
     */
    public static boolean passControl() {
        long now = getNowTime();//程序执行时间
        if (now < (timeStamp + effectiveDuration)) {//在时间控制范围内
            reqCount.getAndIncrement();
            return reqCount.get() <= maxReqCount;//当前时间范围内超过最大请求控制数
        } else {
            timeStamp = now;//超时后重置
            reqCount = new AtomicInteger(1);//占用一个令牌
            return true;
        }
    }
    //获取执行时间
    public static long getNowTime() {
        return System.currentTimeMillis();
    }
 
    public static void main(String[] args) throws InterruptedException {
        ExecutorService executor = Executors.newFixedThreadPool(10);
        for (int i = 0; i < 10; i++) {
            //Thread.sleep(200); //用来模拟令牌周期
            if (passControl()) {//放行
                executor.execute(new TaskRunnable(reqCount.get()));
            } else {
                System.out.println("被限流，请稍后访问！");
            }
        }
    }
}

限流工具

用法

google开源工具包guava提供了限流工具类,该类基于令牌桶算法,非常方便使用.rateLimiter经常用于限制对一些物理资源或者逻辑资源的的访问速率.它支持俩种获取Permits接口,一种是拿不到令牌立刻返回,一种是阻塞一段时间看看能不能拿到

//多任务执行,但每秒执行不超过2个任务
final RateLimiter rateLimiter = RateLimiter.create(2.0);
void submitTasks(List<Runnable> tasks, Executor executor) {
    for (Runnable task : tasks) {
        rateLimiter.acquire(); //默认获取1个令牌
        executor.execute(task);
    }
}
//以每秒5kb内的速度发送-限制数据包大小
final RateLimiter rateLimiter = RateLimiter.create(5000.0);
void submitPacket(byte[] packet) {
    rateLimiter.acquire(packet.length);//获取指定数量的令牌
    networkService.send(packet);
}
//以非阻塞的形式达到降级
if(limiter.tryAcquire()) { //未请求到limiter则立即返回false
    doSomething();
}else{
    doSomethingElse();
}

主要接口

RateLimiter其实是一个abstract类，但是它提供了几个static方法用于创建RateLimiter：

/**
* 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* 当请求到来的速度超过了permitsPerSecond，保证每秒只处理permitsPerSecond个请求
* 当这个RateLimiter使用不足(即请求到来速度小于permitsPerSecond)，会囤积最多permitsPerSecond个请求
*/
public static RateLimiter create(double permitsPerSecond);
 
/**
* 创建一个稳定输出令牌的RateLimiter，保证了平均每秒不超过permitsPerSecond个请求
* 还包含一个热身期(warmup period),热身期内，RateLimiter会平滑的将其释放令牌的速率加大，直到起达到最大速率
* 同样，如果RateLimiter在热身期没有足够的请求(unused),则起速率会逐渐降低到冷却状态
*
* 设计这个的意图是为了满足那种资源提供方需要热身时间，而不是每次访问都能提供稳定速率的服务的情况(比如带缓存服务，需要定期刷新缓存的)
* 参数warmupPeriod和unit决定了其从冷却状态到达最大速率的时间
*/
public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit);

提供了两个获取令牌的方法，不带参数表示获取一个令牌。如果没有令牌则一直等待，返回等待的时间(单位为秒)，没有被限流则直接返回0.0

public double acquire();//默认获取一个令牌
public double acquire(int permits);//获取指定令牌数

尝试获取令牌分为超市和不带超时俩种

//尝试获取一个令牌,立即返回
public boolean tryAcquire();
public boolean tryAcquire(int permits);
//尝试获取permits个令牌，带超时时间
public boolean tryAcquire(long timeout, TimeUnit unit);
public boolean tryAcquire(int permits, long timeout, TimeUnit unit);

使用

平滑突发限流

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

public void testSmoothBursty() {
 RateLimiter r = RateLimiter.create(5);
 while (true) {
 System.out.println("get 1 tokens: " + r.acquire() + "s");
 }
 /**
     * output: 基本上都是0.2s执行一次，符合一秒发放5个令牌的设定。
     * get 1 tokens: 0.0s 
     * get 1 tokens: 0.182014s
     * get 1 tokens: 0.188464s
     * get 1 tokens: 0.198072s
     * get 1 tokens: 0.196048s
     * get 1 tokens: 0.197538s
     * get 1 tokens: 0.196049s
     */
}

RateLimiter使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。

public void testSmoothBursty2() {
 RateLimiter r = RateLimiter.create(2);
 while (true)
 {
    System.out.println("get 1 tokens: " + r.acquire(1) + "s");
 try {
    Thread.sleep(2000);
 } catch (Exception e) {}
 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");
 /**
       * output:
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * end
       * get 1 tokens: 0.499796s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       */
 }
}

RateLimiter由于会累积令牌，所以可以应对突发流量。在下面代码中，有一个请求会直接请求5个令牌，但是由于此时令牌桶中有累积的令牌，足以快速响应。 RateLimiter在没有足够令牌发放时，采用滞后处理的方式，也就是前一个请求获取令牌所需等待的时间由下一次请求来承受，也就是代替前一个请求进行等待。

public void testSmoothBursty3() {
 RateLimiter r = RateLimiter.create(5);
 while (true)
 {
    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");
 /**
       * output:
       * get 5 tokens: 0.0s
       * get 1 tokens: 0.996766s 滞后效应，需要替前一个请求进行等待
       * get 1 tokens: 0.194007s
       * get 1 tokens: 0.196267s
       * end
       * get 5 tokens: 0.195756s
       * get 1 tokens: 0.995625s 滞后效应，需要替前一个请求进行等待
       * get 1 tokens: 0.194603s
       * get 1 tokens: 0.196866s
       */
 }
}

RateLimiter使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。

public void testSmoothBursty2() {
 RateLimiter r = RateLimiter.create(2);
 while (true)
 {
    System.out.println("get 1 tokens: " + r.acquire(1) + "s");
 try {
    Thread.sleep(2000);
 } catch (Exception e) {}
 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");
 /**
       * output:
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * end
       * get 1 tokens: 0.499796s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       * get 1 tokens: 0.0s
       */
 }
}

RateLimiter由于会累积令牌，所以可以应对突发流量。在下面代码中，有一个请求会直接请求5个令牌，但是由于此时令牌桶中有累积的令牌，足以快速响应。 RateLimiter在没有足够令牌发放时，采用滞后处理的方式，也就是前一个请求获取令牌所需等待的时间由下一次请求来承受，也就是代替前一个请求进行等待。

public void testSmoothBursty3() {
 RateLimiter r = RateLimiter.create(5);
 while (true)
 {
    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");
 /**
       * output:
       * get 5 tokens: 0.0s
       * get 1 tokens: 0.996766s 滞后效应，需要替前一个请求进行等待
       * get 1 tokens: 0.194007s
       * get 1 tokens: 0.196267s
       * end
       * get 5 tokens: 0.195756s
       * get 1 tokens: 0.995625s 滞后效应，需要替前一个请求进行等待
       * get 1 tokens: 0.194603s
       * get 1 tokens: 0.196866s
       */
 }
}

平滑预热流

RateLimiter的 SmoothWarmingUp是带有预热期的平滑限流，它启动后会有一段预热期，逐步将分发频率提升到配置的速率。 比如下面代码中的例子，创建一个平均分发令牌速率为2，预热期为3分钟。由于设置了预热时间是3秒，令牌桶一开始并不会0.5秒发一个令牌，而是形成一个平滑线性下降的坡度，频率越来越高，在3秒钟之内达到原本设置的频率，以后就以固定的频率输出。这种功能适合系统刚启动需要一点时间来“热身”的场景。

public void testSmoothwarmingUp() {
 RateLimiter r = RateLimiter.create(2, 3, TimeUnit.SECONDS);
 while (true)
 {
   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("get 1 tokens: " + r.acquire(1) + "s");
   System.out.println("end");
 /**
       * output:
       * get 1 tokens: 0.0s
       * get 1 tokens: 1.329289s
       * get 1 tokens: 0.994375s
       * get 1 tokens: 0.662888s  上边三次获取的时间相加正好为3秒
       * end
       * get 1 tokens: 0.49764s  正常速率0.5秒一个令牌
       * get 1 tokens: 0.497828s
       * get 1 tokens: 0.49449s
       * get 1 tokens: 0.497522s
       */
 }
}

超详细的Guava RateLimiter限流原理解析 - 知乎 (zhihu.com)

流量控制算法——漏桶算法和令牌桶算法 - 知乎 (zhihu.com)

俩种算法区别

漏桶

原理

请求放入桶(消息队列等),业务处理单元(线程/进程/服务)从桶里拿请求处理,桶满则丢弃新的请求

本质:总量控制,桶的大小是关键

优缺点

桶大小调整比较困难,例如java BlockkingQueue

无法精确控制流出速度(处理速度)

突发流量时丢弃的请求较少

应用场景:瞬时高并发,例如0点签到,整点秒杀

令牌桶

某个处理单元按照指定的速率将令牌放入桶(消息队列等),业务处理单元收到请求后需要获取令牌,获取不到就丢弃请求

技术本质:速率控制,令牌产生的速度是设计的关键

优点

可以动态调整处理的速度

突发流量的时候可能丢弃很多请求

实现相对复杂

场景:控制访问第三方服务的速度,防止把下游压垮,控制自己的处理速度防止过载

常见问题

漏桶和令牌桶的区别是保护自己还是保护别人吗

很显然不是,令牌桶保护自己和保护下游都可以,而不是说保护自己用令牌桶,保护别人用漏桶

原因很简单,令牌桶就是一个速率控制,你可以用来控制自己的处理速度,也可以控制别人的处理速度,都可以起到保护作用

其实漏桶也可以既保护自己又保护下游,因为请求太多的时候,把请求先缓存到漏桶里了,漏桶放不下就丢弃新的请求,下游按照自己的速度来桶里拿任务就可以了,这也是保护机制

其实就是

漏桶的本质是总量控制,令牌桶的本质是速率控制

至于这个控制,可以保护自己,也可以用来保护别人

有的技术人员对于“保护别人”可能不太理解，这个主要应用于访问第三方，最典型的例子就是双十一的支付宝，支付的时候要访问银行的接口，银行的接口实际上处理高并发的能力并不强（例如澳门某银行对外提供的移动支付接口，峰值 TPS 是 30 次/s），这个时候支付宝自己处理性能再高都没用，而且越高越容易把下游的银行给压垮，所以支付宝不得不针对下游接口请求做限流。

网上的文章都说令牌桶更适合“突发流量”，为何你这里说漏桶更适合“瞬时（业务）高并发”？

其实，令牌桶的“突发流量”跟我们通常理解的“业务高并发”并不一样。令牌桶的算法原本是用于网络设备控制传输速度的，而且它控制的目的是保证一段时间内的平均速率控制，之所以说令牌桶适合突发流量，是指在网络传输的时候，可以允许某段时间内（一般就几秒）超过平均传输速率，这在网络环境下常见的情况就是“网络抖动”，但这个短时间的突发流量是不会导致雪崩效应，网络设备也能够处理得过来。对应到令牌桶应用到业务处理的场景，就要求即使有突发流量来了，系统自己或者下游系统要真的能够处理的过来，否则令牌桶允许突发流量进来，结果系统或者下游处理不了，那还是会被压垮。

而我说漏桶算法更适合“瞬时高并发”，是指秒杀、抢购、整点打卡签到、微博热点事件这种业务高并发场景，它不是由于“XX抖动”引起的，而是由业务场景引起的，并且持续的事件可能是几分钟甚至几十分钟，这种业务场景为了用户体验和业务尽量少受损，优先采取的不是丢弃大量请求，而是缓存请求，避免系统出现雪崩效应。因此我们会看到，漏桶和令牌桶都有保护作用，但漏桶的保护是尽量缓存请求（缓存不下才丢），令牌桶的保护主要是丢弃请求（即使系统还能处理，只要超过指定的速率就丢弃，除非此时动态提高速率）。

所以如果在秒杀、抢购、整点打卡签到、微博热点事件这些业务场景用令牌桶的话，会出现大量用户访问出错，因为请求被直接丢弃了；而用漏桶的话，处理可能只是会慢一些，用户体验会更好一些，所以我认为漏桶更适合“突发流量”。

Last modification：December 23, 2022
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏