1. 限流器
1.1 限流器
常见限流算法：
-
计数器算法
计数器算法是一种简单的限流方法，通过对请求进行计数，当请求达到一定的阈值时，进行限制。这种方法适用于简单场景，但不够灵活。容易出现临界时间点限流失效问题。 -
滑动窗口算法
滑动窗口算法维护一个时间窗口内的请求数量，通过动态调整窗口大小，可以更灵活地适应流量的变化。其实就是计数器算法的优化版本，将计数器算法中的单位时间切割成了多块，但也没有完全解决临界时间点限流失效问题。 -
漏桶算法（Leaky Bucket）
漏桶算法与令牌桶算法类似，但是它是按照固定速率漏水，而不是放入令牌。请求被处理的速度是固定的，当请求到来时，如果漏桶未满，则请求被处理，否则被丢弃或等待。 -
令牌桶算法（Token Bucket）
令牌桶算法是漏桶算法的优化版，支持突发流量。在令牌桶中，令牌以固定的速率被放入到桶中，而请求要想通过，必须获取到一个令牌。如果桶中没有足够的令牌，请求就会被限制。
1.2 Guava实现原理
Guava就是令牌桶算法的实现。
需要实现的功能点：
- 令牌以固定的速率添加到令牌桶中，假设限流的速率是 r/ 秒，则令牌每 1/r 秒会添加一个；
- 假设令牌桶的容量是 b ，如果令牌桶已满，则新的令牌会被丢弃；
- 请求能够通过限流器的前提是令牌桶中有令牌。
很容易想到令牌桶的一个实现是：工作线程执行操作前去申请令牌，后台再开启一个子线程定时地添加令牌。但是Guava的RateLimiter限流器并不是这个原理。
RateLimiter的实现是：通过计算下个令牌颁发时间点，并让申请线程休眠对应时长。
假设每次只申请1个令牌（实际上可以申请n个），主要流程如下图所示。
线程执行调用acquire()方法请求令牌，acquire()会调用同步reserve(long time)方法计算下个令牌颁发时间点并返回，线程计算休眠时长后，调用sleep()方法直接休眠对应时长。
1.3 简易限流器代码实现
class RateLimiter {
// 单个令牌颁发间隔时长,单位纳秒
private final long INTERVAL = 1000_000_000;
// 最大令牌数，额外的突发量
private final long maxPermits;
// 当前令牌数
private long storePermits;
// 下个令牌颁发时间点
private long next;
/**
* @param initPermits 初始令牌数
* @param maxPermits 最大令牌数
*/
public RateLimiter(long initPermits, long maxPermits) {
// 省略合法性检查
this.storePermits = initPermits;
this.maxPermits = maxPermits;
}
/**
* 获取令牌，没有令牌则等待
*/
@SneakyThrows
public void acquire() {
// 获取当前时间
long now = System.nanoTime();
// 预占令牌，计算可执行时间点
long timePoint = reverse(now);
// 计算等待时长, 避免异常负数最小置为0
long wait = Math.max(timePoint - now, 0);
// 如果wait大于0，则休眠对应时长
if (wait > 0) {
TimeUnit.NANOSECONDS.sleep(wait);
}
}
/**
* 预占令牌，并返回线程可执行时间点
* 加锁为了保护共享变量storePermits及next
*
* @param now 线程申请令牌时间点
* @return 可执行时间点
*/
synchronized private long reverse(long now) {
// 更新令牌数及下个令牌颁发时间点
resync(now);
// 获取下一个令牌颁发时间
long timePoint = next;
// 判断是否有令牌
if (storePermits > 0) {
// 有令牌，令牌数-1
storePermits--;
} else {
// 没有令牌，下一个令牌颁发时间需要增加一个间隔时长
next += INTERVAL;
}
return timePoint;
}
/**
* 更新令牌数及下个令牌颁发时间点
* @param now 线程申请令牌时间点
*/
private void resync(long now) {
// 如果线程申请令牌时间点比下个令牌颁发时间点还早，那么不需要新增令牌数及更新下个令牌颁发时间点
if (now <= next) {
return;
}
// 计算新增令牌数, 实际上Guava限流器实现用double更精准
long newPermits = (now - next) / INTERVAL;
// 更新令牌数
storePermits = Math.min(storePermits + newPermits, maxPermits);
// 更新下次颁发令牌时间点
next = now;
}
}
@Slf4j
public class Test {
@SneakyThrows
public static void main(String[] args) {
// 创建固定6个线程的线程池
ExecutorService executor = Executors.newFixedThreadPool(6);
// 创建一个初始令牌3个，最大令牌数为3的限流器
RateLimiter simpleLimiter = new RateLimiter(3, 3);
// 丢9个数字打印观察
for (int i = 1; i <= 9; i++) {
int finalI = i;
executor.submit(() -> {
simpleLimiter.acquire();
log.info(String.valueOf(finalI));
});
}
executor.shutdown();
}
}
打印如下。由于设置了初始令牌数为3，可以看到刚开始4个线程并发打印。后续则每秒只有1个线程打印。
21:43:31.319 [pool-1-thread-2] INFO com.huaxiaogou.MDog.myguava.Test - 2
21:43:31.319 [pool-1-thread-3] INFO com.huaxiaogou.MDog.myguava.Test - 3
21:43:31.319 [pool-1-thread-4] INFO com.huaxiaogou.MDog.myguava.Test - 4
21:43:31.319 [pool-1-thread-1] INFO com.huaxiaogou.MDog.myguava.Test - 1
21:43:32.323 [pool-1-thread-5] INFO com.huaxiaogou.MDog.myguava.Test - 5
21:43:33.323 [pool-1-thread-6] INFO com.huaxiaogou.MDog.myguava.Test - 6
21:43:34.323 [pool-1-thread-2] INFO com.huaxiaogou.MDog.myguava.Test - 7
21:43:35.323 [pool-1-thread-4] INFO com.huaxiaogou.MDog.myguava.Test - 8
21:43:36.323 [pool-1-thread-3] INFO com.huaxiaogou.MDog.myguava.Test - 9