漏桶算法和令牌桶算法

标签：11 令牌请求 08 算法 2022 漏桶 14

一、漏桶算法

漏桶算法原理：水(请求)先进入到漏桶里，人为设置一个最大出水速率，漏桶以<=最大出水速率的速度出水，当水流速度过大会直接溢出（拒绝服务）

因此，此算法的核心为：

存下请求
匀速处理
多余丢弃

因此这是一种强行限制请求速率的方式，但是缺点非常明显，主要有两点

无法面对突发的大流量—>比如请求速率为1000/s，容量为5000,来了一波2000/s的请求持续10s，那么后5s的请求将全部直接被丢弃，服务器拒绝服务，但是实际上网络中突发一波大流量尤其是短时间的大流量是非常正常的。
无法有效利用网络资源—>比如虽然服务器的处理能力是1000/s，但这不是绝对的，这个1000只是一个宏观服务器处理能力的数据，实际上一共5秒，每秒请求量分别为1200、1300、500、800、平均下来QPS也是1000/s，但是这个量对服务器来说完全是可以接受的，但是因为限制了速率是1000/s，因此前面的3秒，每秒只能处理掉1000个请求而一共打回了700个请求，白白浪费了服务器资源

所以，通常来说利用漏桶算法来限流，实际场景下用得不多。

二、令牌桶算法

令牌桶算法是网络流量整形(Traffic Shaping)和限流(Rate Limiting)中最常使用的一种算法，它可用于控制发送到网络上数据的数量并允许突发数据的发送。

令牌桶算法原理

从某种意义上来说，令牌桶算法是对漏桶算法的一种改进，主要在于令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用，来看下令牌桶算法的实现原理：

整个的过程是这样的：

系统以恒定的速率产生令牌，然后将令牌放入令牌桶中
令牌桶有一个容量，当令牌桶满了的时候，再向其中放入的令牌就会被丢弃
每次一个请求过来，需要从令牌桶中获取一个令牌，假设有令牌，那么提供服务；假设没有令牌，那么拒绝服务

那么，我们再看一下，为什么令牌桶算法可以防止一定程度的突发流量呢？可以这么理解，假设我们想要的速率是1000Qps，那么往桶中放令牌的速度就是1000个/s，假设第1秒只有800个请求，那么意味着第2秒可以容许1200个请求，这就是一定程度突发流量的意思，反之我们看漏桶算法，第1秒只要800个请求，那么全部放过，第2秒这1200个请求将会被打回200个。

注意上面多次提到一定程度这四个字，这也是我认为令牌桶算法最需要注意的一个点。假设还是1000QPS的速率，那么每秒钟放1000个令牌，第1秒钟800个请求过来，第2~4秒没有请求，那么按照令牌桶算法，第5秒钟可以接受4200个请求，但是实际上这已经远远超出了系统的承载能力，因此使用令牌桶算法特别注意设置桶中令牌的上限即可

总而言之，作为对漏桶算法的改进，令牌桶算法在限流场景下被使用更加广泛。

RateLimiter使用

代码示例：模拟一下每秒最多过5个请求

package com.chenly.ratelimit;

import com.google.common.util.concurrent.RateLimiter;
import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * @author: chenly
 * @date: 2022-11-08 11:23
 * @description:
 * @version: 1.0
 */
public class RateLimiterTest2 {

    private static final SimpleDateFormat FORMATTER = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    public static void main(String[] args) {
        RateLimiter limiter = RateLimiter.create(5);
        long start = System.currentTimeMillis();
        for (int i= 0; i < 30; i++) {
            double time = limiter.acquire(5);
            long after = System.currentTimeMillis() - start;
            System.out.println(FORMATTER.format(new Date())+":第"+i + "个请求等待:" + time + "，已开始" + after + "毫秒");

        }
        System.out.println("total time：" + (System.currentTimeMillis() - start));

    }

}

利用RateLimiter.create这个构造方法可以指定每秒向桶中放几个令牌，比如上面的代码create(5),那么每秒放置5个令牌，即200ms会向令牌桶中放置一个令牌。看一下代码执行结果

2022-11-08 14:06:13.949:第0个请求等待:0.0，已开始0毫秒
2022-11-08 14:06:14.150:第1个请求等待:0.197792，已开始201毫秒
2022-11-08 14:06:14.349:第2个请求等待:0.198286，已开始400毫秒
2022-11-08 14:06:14.549:第3个请求等待:0.200435，已开始600毫秒
2022-11-08 14:06:14.749:第4个请求等待:0.200484，已开始800毫秒
2022-11-08 14:06:14.950:第5个请求等待:0.200522，已开始1001毫秒
2022-11-08 14:06:15.150:第6个请求等待:0.199529，已开始1201毫秒
2022-11-08 14:06:15.349:第7个请求等待:0.199495，已开始1400毫秒
2022-11-08 14:06:15.549:第8个请求等待:0.200473，已开始1600毫秒
2022-11-08 14:06:15.750:第9个请求等待:0.200584，已开始1801毫秒
2022-11-08 14:06:15.950:第10个请求等待:0.199586，已开始2001毫秒
2022-11-08 14:06:16.149:第11个请求等待:0.199438，已开始2200毫秒
2022-11-08 14:06:16.350:第12个请求等待:0.200656，已开始2401毫秒

可以看到：在每次消耗一个令牌的情况下，RateLimiter可以保证每一秒内最多只有5个请求获得令牌，使用这种方式可以很好的做单机对请求的QPS数控制

上面的写法是RateLimiter最常用的写法

acquire()方法是阻塞的且会一直等待获取令牌为止，它的返回值为double型，表示从阻塞开始到获取令牌的等待时间，单位为秒
tryAcquire()方法，可以指定超时时间，返回值为boolean类型，假设线程等待了指定时间后仍然没有获取到令牌，那么就会返回给客户端false

RateLimiter预消费

每次来一个请求就acquire一个令牌是RateLimiter最常见的用法，但是我们看acquire还有个acquire(int permits)的重载方法，即允许每次获取多个令牌数。这也是有可能的，请求数是一个大维度，有可能服务器按照字节数来进行限流，例如每秒最多处理10000字节的数据，那每次扣减的就不止1了

package com.chenly.ratelimit;

import com.google.common.util.concurrent.RateLimiter;
import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * @author: chenly
 * @date: 2022-11-08 11:23
 * @description:
 * @version: 1.0
 */
public class RateLimiterTest2 {

    private static final SimpleDateFormat FORMATTER = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");

    public static void main(String[] args) {
        RateLimiter rateLimiter = RateLimiter.create(1);

        System.out.println("获取1个令牌开始，时间为" + FORMATTER.format(new Date()));
        double cost = rateLimiter.acquire(1);
        System.out.println("获取1个令牌结束，时间为" + FORMATTER.format(new Date()) + ", 耗时" + cost + "ms");
        System.out.println("获取5个令牌开始，时间为" + FORMATTER.format(new Date()));
        cost = rateLimiter.acquire(5);
        System.out.println("获取5个令牌结束，时间为" + FORMATTER.format(new Date()) + ", 耗时" + cost + "ms");
        System.out.println("获取3个令牌开始，时间为" + FORMATTER.format(new Date()));
        cost = rateLimiter.acquire(3);
        System.out.println("获取3个令牌结束，时间为" + FORMATTER.format(new Date()) + ", 耗时" + cost + "ms");
    }

}

代码运行结果为：

获取1个令牌开始，时间为2022-11-08 14:25:25.450
获取1个令牌结束，时间为2022-11-08 14:25:25.451, 耗时0.0ms
获取5个令牌开始，时间为2022-11-08 14:25:25.452
获取5个令牌结束，时间为2022-11-08 14:25:26.450, 耗时0.997399ms
获取3个令牌开始，时间为2022-11-08 14:25:26.451
获取3个令牌结束，时间为2022-11-08 14:25:31.450, 耗时4.999021ms

第二次需要获取5个令牌，指定的是每秒放1个令牌到桶中，我们发现实际上并没有等5秒钟等桶中积累了5个令牌才能让第二次acquire成功，而是直接等了1秒钟就成功了。这就是预消费能力，也是RateLimiter中允许一定程度突发流量的实现方式。

我们来捋一捋这个逻辑：

第一次请求过来需要获取1个令牌，直接拿到
RateLimiter在1秒钟后放一个令牌，第一次请求预支的1个令牌还上了
1秒钟之后第二次请求过来需要获得5个令牌，直接拿到
RateLimiter再花了5秒钟放了5个令牌，还上了第二次请求预支的5个令牌
第三个请求在5秒钟之后拿到3个令牌

也就是说，前面的请求如果流量大于每秒放置令牌的数量，那么允许处理，但是带来的结果就是后面的请求延后处理，从而整体上达到一个平衡整体处理速率的效果。

突发流量的处理，在令牌桶算法中有两种方式，一种是有足够的令牌才能消费，一种是先消费后还令牌，即先让请求得到处理，再慢慢还上预支的令牌

标签：11,令牌,请求,08,算法,2022,漏桶,14
From： https://www.cnblogs.com/kiko2014551511/p/16869723.html