学习笔记|高并发-令牌桶算法_stopwatch.readmicros();

令牌桶概念

原理

系统以一个恒定的速度往桶里放入令牌，如果请求需要被处理，则需要先从令牌桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。相比较漏桶算法令牌桶算法允许一定的突发流量，但是又不会让突发流量超过我们给定的限制（单位时间窗口内的令牌数）
对于一个请求，需要根据计算您核实的间隔时间，然后让这个请求等待相应的时间以达到限流的目的。
令牌是对“过去的空闲”状态进行建模，当没有空闲时，这个变量为0，当有了非常长的空间时间时，令牌数增长允许存储的最大令牌数。所以一个请求需要令牌时，派发的令牌来源有两个：存储的令牌；新产生的令牌。在有存储的令牌时，会先获取存储的令牌，当存储令牌为空了，才会获取新产生的令牌
RateLimiter不会记录最后一个请求，而是下一个请求允许执行的事假你，这也可以直白地告诉我们到达下一个调度时间点的时间间隔。下一个调度时间点已经过去，这个事假难点和现在时间的查就是Ratelimiter多久没有被使用，我们将这段时间翻译成storedPermits

令牌的产生

① 开启一个定时任务，由定时任务持续生成令牌。问题：极大地消耗系统资源
② 延迟计算，resync函数，若当前时间晚于下次生成时间，计算该段时间内可以生成多少令牌，将生成的令牌加入令牌桶中并更新数据

限流工具类RateLimiter

Guava com.google.common.util.concurrent.RateLimiter基基于令牌桶算法完成限流

使用

最简单的调用如下：
public static void main(String[] args) {
RateLimiter limiter = RateLimiter.create(0.5); // 入参为每秒生产的令牌数，0.5表示2秒生产一个令牌
for (int i = 0; i < 5; i++) {
System.out.println(limiter.acquire());
}
}

类图

关健属性

final SleepingStopwatch stopwatch：底层计时器
volatile Object mutexDoNotUseDirectly：锁，不能在构造器里声明
final double maxBurstSeconds：限流器空闲时存在的最大令牌数，默认是1
double storedPermits：当前存储的令牌数
double maxPermit：最大存储令牌数
double stableIntervalMicros： 添加令牌的时间间隔
private long nextFreeTicketMicros：下一个请求可以获取令牌的起始时间，默认为0L，由于RateLimiter允许预消费，上次请求预消费令牌后下次请求需要等待时间到这个时刻才可以获取令牌

RateLimiter类

① RateLimiter提供了create静态方法用于创建限流器
RateLimiter create(double permitsPerSecond) {
// 从当前系统时间开始，创建一个SmoothBuisty模式的限流器
return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond);
}
RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond) {
// 创建一个SmoothBuisty模式的限流器
RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* 空闲时令牌存在最长时间*/);
rateLimiter.setRate(permitsPerSecond);
return rateLimiter;
}
RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
checkArgument(warmupPeriod >= 0, “warmupPeriod must not be negative: %s”, warmupPeriod);
return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit);
}
RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
// 创建一个SmoothWarmingUp模式的限流器
RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit);
rateLimiter.setRate(permitsPerSecond);
return rateLimiter;
}

② 通过acquire方法获取令牌
public double acquire() {
// 默认情况下表示只获取一个令牌
return acquire(1);
}
public double acquire(int permits) {
// 计算能获取[permits]个令牌需要等待的时间
long microsToWait = reserve(permits);
// 当permits==0时，抛IllegalArgumentException异常
stopwatch.sleepMicrosUninterruptibly(microsToWait);
// 返回等待时间，单位：秒
return 1.0 * microsToWait / SECONDS.toMicros(1L);
}

③ RateLimiter还通过tryAcquire方法尝试获取令牌，分为带超时时间和不带超时时间两种
permits：获取令牌的个数
timeout：等待超时时间，=0：非阻塞，直接返回
unit：超时时间单位
可以尝试在timeout时间内获取令牌，如果可以则挂起等待相应时间并返回true，否则立即返回false
public boolean tryAcquire(long timeout, TimeUnit unit) {
return tryAcquire(1, timeout, unit);
}
public boolean tryAcquire(int permits) {
return tryAcquire(permits, 0, MICROSECONDS);
}
public boolean tryAcquire() {
return tryAcquire(1, 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;
}

SmoothRateLimiter类

① final long reserveEarliestAvailable(int requiredPermits, long nowMicros)
获取requiredPermits个令牌，并返回需要等待到的时间点
其中，storedPermitsToSpend为桶中可以消费的令牌数，freshPermits为还需要的(需要补充的)令牌数，根据该值计算需要等待的时间，追加并更新nextFreeTicketMicros
需要注意的是，该函数的返回是更新前的(上次请求计算的)nextFreeTicketMicros，而不是本次更新的nextFreeTicketMicros，通俗来讲，本次请求需要为上次请求的预消费行为埋单，这也是RateLimiter可以预消费(处理突发)的原理所在。若需要禁止预消费，则修改此处返回更新后的nextFreeTicketMicros值。
② void resync(long nowMicros)
延迟计算
在每次获取令牌之前调用，若当前时间晚于nextFreeTicketMicros ，则计算该段时间内可以生成多少令牌，将生成的令牌加入令牌桶中并更新数据，这样只需要在获取令牌时计算一次即可

实现类

① SmoothWarmingUp 渐进模式 令牌生成速度缓慢提升直到维持在一个稳定值

1）限流器的状态是图中的这条直线
2）当限流器空闲时，它在右边，存储最大令牌数
3）当限流器在使用时，会向左（直到降为0）
4）当没有使用时，限流器会以相同的速率增加令牌数，直到达到最大令牌数

空闲存储令牌数:
SmoothWarmingUp 模式下空闲时存储令牌数
RateLimiter 不需要记住上个请求的时间,它只需要记住“希望下个请求到来的时间”即可。这样使得我们能够马上识别出，一个确切的超时时间（跟 tryAcquire(timeout) 相关）是否满足下一个计划时间点。如果当前时间大于“期望的下个请求到来的时间”，那么这两个时间的差值就是 Ratelimiter 的未使用时间 t，通过 t*QPS 计算出 storedPermits。
数学建模思想参考： https://tech.kujiale.com/ratelimiter-architecture/

② SmoothBuisty 稳定模式 令牌生成速度恒定
这个工具是个“突发”限流器，
关健属性：
maxBurstSeconds：限流器在不使用时令牌可以保存多少秒
构造器：
SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
super(stopwatch);
this.maxBurstSeconds = maxBurstSeconds; // 最大存储maxBurstSeconds秒生成的令牌
桶中可存放的最大令牌数由maxBurstSeconds计算而来，其含义为最大存储maxBurstSeconds秒生成的令牌。
该参数的作用在于，可以更为灵活地控制流量。如，某些接口限制为300次/20秒，某些接口限制为50次/45秒等。
}

空闲存储令牌数:
SmoothBuisty 模式下空闲时不存储令牌
storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
return 0L;
}

[参考文章]
https://segmentfault.com/a/1190000012875897 源码解析
https://blog.csdn.net/liyantianmin/article/details/79086571 设计解析