使用池化技术、令牌桶算法和漏桶算法实现限流的原理

@[toc]

1. 池化技术

池化资源技术的限流其实就是通过计算器算法来控制全局的总并发数，例如常用的线程池中核心线程数和最大线程数的设置、数据库连接池中对于最大连接数的限制等等。就数据库连接池技术而言，为了避免并发场景下连接数超过数据库所能承载的最大上限，合理的运用连接池技术，可以有效的限制单个进程内能够申请到的最大连接数，确保在并发环境下连接数不会超过资源阈值。

2. 令牌桶算法

令牌桶算法主要用于限制流量的平均流入速率，并允许出现一定程度上的突发流量，假设令牌桶的容量为，

那么算法执行的流程为：

• 每秒向令牌桶中放入个令牌，即每秒放入一个令牌的平均速率来提供可以使用的令牌
• 令牌桶的容量自始至终都是固定的，最多只能放入个令牌，桶满则溢出
• 当一个个字节的请求包到达时，将消耗个令牌，然后再发送该数据包
• 如果桶中的令牌数小于，则该数据包将被执行限流处理

Guava Cache中的RateLimiter抽象类能够以一种简便的方式实现流量的平均流入速率限流，起到类似令牌桶算法的效果，

为了使用Guava Cache，首先需要创建工程，导入依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>27.0.1-jre</version>
</dependency>

如果想要使用RateLimiter，可以调用它的create()来指定令牌桶的容量。当需要令牌时，请求需要调用acquire()方法。如下所示，此时令牌桶容量为5，假设请求数也是5，那么5个请求都可以近乎同时获取令牌，并不会触发限流。

@Test
void testLimit(){
    RateLimiter limiter = RateLimiter.create(5);
    for (int i = 0; i < 5; i++) {
        double waitTime = limiter.acquire();
        System.out.println(waitTime); 
    }
}

0.0
0.198812
0.199176
0.199727
0.19905

如果此时有了突发流量，某个请求需要一次申请5个令牌，那么后续的请求就会被限流。大约等待1秒后，后续请求才可以继续从桶中拿令牌。

@Test
void testLimitMore() {
    RateLimiter limiter = RateLimiter.create(5);
    for (int i = 0; i < 5; i++) {
        System.out.println(limiter.acquire(5));
        System.out.println(limiter.acquire());
        System.out.println("--------");
    }
}

0.0
0.999008
--------
0.198522
0.998839
--------
0.199423
0.999741
--------
0.196243
0.999406
--------
0.199218
0.99949
--------

调用acquire()获取令牌不到，请求将会一直等待。如果需要请求在获取不到令牌后，直接丢弃或是短暂等待，可以调用tryAcquire()的无参和带参形式。那么RateLimiter底层是如何实现流量的平均流入速率限流的效果的呢？下面我们通过源码看一下它的create()、acquire()和tryacquire()的实现。

RateLimiter的create()最基本的实现如下：

public static RateLimiter create(double permitsPerSecond) {
    return create(permitsPerSecond, RateLimiter.SleepingStopwatch.createFromSystemTimer());
}

其中的permitsPerSecond可用于设置限流速率从慢速过渡到平均速率的缓存时间。当前，RateLimiter中还提供了其他重载的形式，用于创建不同需求的limiter。acquire()的实现如下：

@CanIgnoreReturnValue
public double acquire() {
    return acquire(1);
}
@CanIgnoreReturnValue
public double acquire(int permits) {
    // 计算获取令牌所需等待的时间
    long microsToWait = reserve(permits);
     // 进行线程sleep
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
}

它会根据设置的桶容量来计算获取一个令牌所需要等待的时间。tryacquire()的实现如下：

public boolean tryAcquire(int permits) {
    return tryAcquire(permits, 0, MICROSECONDS);
}
public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
    long timeoutMicros = max(unit.toMicros(timeout), 0);
    checkPermits(permits);
    long microsToWait;
    synchronized (mutex()) {
        long nowMicros = stopwatch.readMicros();
        if (!canAcquire(nowMicros, timeoutMicros)) {
            return false;
        } else {
            microsToWait = reserveAndGetWaitLength(permits, nowMicros);
        }
    }
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return true;
}

RateLimiter具体的源码解析阅读：

使用Guava RateLimiter限流以及源码解析

超详细的Guava RateLimiter限流原理解析

3. 漏桶算法

漏桶算法允许以任意的速率向桶中流入水滴，但由于桶的容量是固定的，如果桶已满，那么水滴将溢出被丢弃。而且桶流出水滴的速率是固定的，起到限制数据的传输速率。

上述两种算法虽然都可以在高并发场景下起到限流的效果，但是两者的限流方向是相反的。令牌桶算法限制的是向桶中放入令牌的数量，允许一定程度上的突发流量。当用户请求所需的令牌数多于桶中剩下的令牌数，就会被执行限流操作。

而漏桶算法控制的是令牌流出的速率，并且流出的速率还是固定的，主要用于平滑网络流量。例如，假设桶只能接受大小为10的数据包，那么当数据包大于10时，请求将被执行限流处理，由于流出速率固定，那么每秒处理的数据包大小将固定，从而起到平滑流量的作用。

4. 计数器算法

单位时间内会有一个计数器负责计数，不停的和阈值进行比较，当等于阈值时触发限流逻辑。它主要用于限制单位时间内的总并发数，假设规定每秒可以处理的请求数为100，那么一秒内请求一次，计数器值加1。如果一秒内计数器值到达阈值，那么后续的请求就被执行限流处理。并且只有达到临界值时，计数器才会被重置。

当等于阈值时触发限流逻辑。它主要用于限制单位时间内的总并发数，假设规定每秒可以处理的请求数为100，那么一秒内请求一次，计数器值加1。如果一秒内计数器值到达阈值，那么后续的请求就被执行限流处理。并且只有达到临界值时，计数器才会被重置。