网站情况建设说明,ps模板下载网站,网络商城网站建设,香河住房和建设局网站令牌桶算法与Guava的实现RateLimiter源码分析 令牌桶RateLimiter简介RateLimiter使用示例导入maven依赖编写测试代码 RateLimiter的实现源码解析SmoothRateLimiterSmoothBursty恒速获取令牌acquire(int)tryAcquire(int,long,TimeUnit) 存量桶系数小结 优缺点与漏桶的区别总结 令… 令牌桶算法与Guava的实现RateLimiter源码分析 令牌桶RateLimiter简介RateLimiter使用示例导入maven依赖编写测试代码 RateLimiter的实现源码解析SmoothRateLimiterSmoothBursty恒速获取令牌acquire(int)tryAcquire(int,long,TimeUnit) 存量桶系数小结 优缺点与漏桶的区别总结 令牌桶RateLimiter 简介
令牌桶算法是一种限流算法。
令牌桶算法的原理就是以一个恒定的速度往桶里放入令牌每一个请求的处理都需要从桶里先获取一个令牌当桶里没有令牌时则请求不会被处理要么排队等待要么降级处理要么直接拒绝服务。当桶里令牌满时新添加的令牌会被丢弃或拒绝。 令牌桶算法主要是可以控制请求的平均处理速率它允许预消费即可以提前消费令牌以应对突发请求但是后面的请求需要为预消费买单等待更长的时间以满足请求处理的平均速率是一定的。
RateLimiter使用示例 导入maven依赖
dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion29.0-jre/version
/dependency编写测试代码
public class RateLimiterTest {public void limit() {// 创建一个限流器设置每秒放置的令牌数为1个RateLimiter rateLimiter RateLimiter.create(1);IntStream.range(1, 10).forEach(i - {// 一次获取i个令牌double waitTime rateLimiter.acquire(i);System.out.println(acquire i waitTime: waitTime);});}public static void main(String[] args) {RateLimiterTest rateLimiterTest new RateLimiterTest();rateLimiterTest.limit();}
}这段代码创建一个限流器设置每秒放置的令牌数为1个并循环获取令牌每次获取i个。执行结果第一次获取一个令牌时等待0s立即可获取到这里之所以不需要等待是因为令牌桶的预消费特性第二次获取两个令牌等待时间1s这个1s就是前面获取一个令牌时因为预消费没有等待延到这次来等待的时间这次获取两个又是预消费所以下一次获取取3个时就要等待这次预消费需要的2s了依此类推。可见预消费不需要等待的时间都由下一次来买单以保障一定的平均处理速率上例为1s一次。
RateLimiter的实现
RateLimiter类在guava里是一个抽象类其有两个具体实现
SmoothBursty平滑突发以恒定的速率生成令牌。SmoothWarmingUp顺利热身令牌生成的速度逐渐提升直到达到一个稳定的值。
其类图如下他们的关系与作用
RateLimiter是顶层封装提供新建令牌桶的方法SleepingStopwatch是guava实现的一个时钟类提供时钟功能SmoothRateLimiter是令牌桶抽象提供操作令牌桶的抽象方法其有两个内部类SmoothBursty和SmoothWarmingUpSmoothBursty是恒定速率令牌桶实现SmoothWarmingUp是逐渐加速知道稳定的令牌桶实现 源码解析 SmoothRateLimiter
SmoothRateLimiter是令牌桶抽象其有四个关键的属性
/** 当前存储的许可证。 */
double storedPermits;/** 存储许可证的最大数量。 */
double maxPermits;/*** 两个单位请求之间的间隔以我们的稳定速率。* 例如每秒 5 个许可的稳定速率具有 200 毫秒的稳定间隔。*/
double stableIntervalMicros;/*** 授予下一个请求无论其大小如何的时间。* 在批准请求后这将在将来进一步推送。大请求比小请求更进一步。*/
private long nextFreeTicketMicros 0L; // could be either in the past or future他们的作用可以看注释。此外还有两个内部类实现此抽象
SmoothBursty平滑突发以恒定的速率生成令牌。SmoothWarmingUp顺利热身令牌生成的速度逐渐提升直到达到一个稳定的值。
SmoothBursty恒速
首先来看下恒定速率生成令牌的实现。其使用方法是
// 创建一个限流器设置每秒放置的令牌数为1个
RateLimiter rateLimiter RateLimiter.create(1);RateLimiter#create
public static RateLimiter create(double permitsPerSecond) {/** The default RateLimiter configuration can save the unused permits of up to one second. This* is to avoid unnecessary stalls in situations like this: A RateLimiter of 1qps, and 4 threads,* all calling acquire() at these moments:** T0 at 0 seconds* T1 at 1.05 seconds* T2 at 2 seconds* T3 at 3 seconds** Due to the slight delay of T1, T2 would have to sleep till 2.05 seconds, and T3 would also* have to sleep till 3.05 seconds.*/return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
}static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {RateLimiter rateLimiter new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);rateLimiter.setRate(permitsPerSecond);return rateLimiter;
}实际是创建了一个SmoothBursty实例默认的maxBurstSeconds是1其中SleepingStopwatch是guava实现的一个时钟类。 代码第三行调用了RateLimiter#setRate
public final void setRate(double permitsPerSecond) {checkArgument(permitsPerSecond 0.0 !Double.isNaN(permitsPerSecond), rate must be positive);synchronized (mutex()) {doSetRate(permitsPerSecond, stopwatch.readMicros());}
}abstract void doSetRate(double permitsPerSecond, long nowMicros);方法签名为更新此 RateLimiter的稳定速率 permitsPerSecond 即构造 RateLimiter的工厂方法中提供的参数。当前受限制的 线程不会因此 调用而被唤醒因此它们不会遵守新的速率只有后续请求才会。但请注意由于每个请求都会偿还如有必要通过等待前一个请求的成本这意味着调用setRate后的下一个请求将不受新速率的影响它将支付前一个请求的成本这是根据以前的速率计算的。
此方法调用了抽象方法doSetRate这里的实现是SmoothRateLimiter提供的来看SmoothRateLimiter#doSetRate源码
Override
final void doSetRate(double permitsPerSecond, long nowMicros) {resync(nowMicros);double stableIntervalMicros SECONDS.toMicros(1L) / permitsPerSecond;this.stableIntervalMicros stableIntervalMicros;doSetRate(permitsPerSecond, stableIntervalMicros);
}此方法
调用 resync(nowMicros) 对 storedPermits 与 nextFreeTicketMicros 进行了调整——如果当前时间晚于 nextFreeTicketMicros则计算这段时间内产生的令牌数累加到 storedPermits 上并更新下次可获取令牌时间 nextFreeTicketMicros 为当前时间。计算stableIntervalMicros的值此值代表产生令牌的时间间隔1/permitsPerSecond(每秒几个令牌)调用doSetRate(double, double)
其将输入的permitsPerSecond转换为速度传给SmoothRateLimiter的doSetRate(permitsPerSecond, stableIntervalMicros)方法doSetRate(permitsPerSecond, stableIntervalMicros)方法是抽象方法
abstract void doSetRate(double permitsPerSecond, double stableIntervalMicros);由SmoothBursty的实现为
Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {double oldMaxPermits this.maxPermits;maxPermits maxBurstSeconds * permitsPerSecond;if (oldMaxPermits Double.POSITIVE_INFINITY) {// if we dont special-case this, we would get storedPermits NaN, belowstoredPermits maxPermits;} else {storedPermits (oldMaxPermits 0.0)? 0.0 // initial state: storedPermits * maxPermits / oldMaxPermits;}
}此方法计算maxPermits的值maxBurstSeconds * permitsPerSecond。maxBurstSeconds是new SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds)构造方法传进来的这里离默认是1。
获取令牌 acquire(int)
acquire(int)方法在获取不到令牌时阻塞等待直到获取到令牌。获取令牌方法为RateLimiter#acquire(int):
// 从中 RateLimiter获取给定数量的令牌阻塞直到请求可以被批准。告诉睡眠时间如果有
CanIgnoreReturnValue
public double acquire(int permits) {long microsToWait reserve(permits);stopwatch.sleepMicrosUninterruptibly(microsToWait);return 1.0 * microsToWait / SECONDS.toMicros(1L);
}调用RateLimiter#reserve 获取需要等待的时间
// RateLimiter 保留给定数量的令牌以供将来使用并返回使用这些令牌需要等待的微秒数。
final long reserve(int permits) {checkPermits(permits);synchronized (mutex()) {return reserveAndGetWaitLength(permits, stopwatch.readMicros());}
}调用RateLimiter#reserveAndGetWaitLength
// 保留令牌并返回使用者需要等待的时间。
final long reserveAndGetWaitLength(int permits, long nowMicros) {long momentAvailable reserveEarliestAvailable(permits, nowMicros);return max(momentAvailable - nowMicros, 0);
}调用RateLimiter#reserveEarliestAvailable
abstract long reserveEarliestAvailable(int permits, long nowMicros);是抽象方法具体实现为SmoothRateLimiter#reserveEarliestAvailable
// 更新下次可取令牌时间点与存储的令牌数返回本次可取令牌的时间点
Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {resync(nowMicros); // 如果nextFreeTicket小于当前时间更新当前存储的令牌数和下次可使用令牌的时间为now// nextFreeTicketMicros表示下一个可以分配令牌的时间点这个值返回后// 上一层的函数会调用stopwatch.sleepMicrosUninterruptibly(microsToWait);// 即阻塞到这个分配的时间点long returnValue nextFreeTicketMicros;// 本次需要用掉的令牌数取本次需要的和当前可以使用的令牌数的最小值double storedPermitsToSpend min(requiredPermits, this.storedPermits);// 需要用的令牌大于暂存的令牌数计算需要新增的令牌数double freshPermits requiredPermits - storedPermitsToSpend;// 计算补齐需要新增的令牌需要等待的时间long waitMicros storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) (long) (freshPermits * stableIntervalMicros);// 将下一个可分配令牌的时间点向后移动这里是实现与消费的关键this.nextFreeTicketMicros LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);// 更新当前存储的令牌数this.storedPermits - storedPermitsToSpend;return returnValue;
}
// 如果nextFreeTicket小于当前时间更新当前存储的令牌数和下次可使用令牌的时间为now
void resync(long nowMicros) {// if nextFreeTicket is in the past, resync to nowif (nowMicros nextFreeTicketMicros) {double newPermits (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();storedPermits min(maxPermits, storedPermits newPermits);nextFreeTicketMicros nowMicros;}
}上面是获取令牌的关键方法 tryAcquire(int,long,TimeUnit)
指定时间内尝试获取令牌获取到或获取超时返回。
public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {// 将timeout换算成微秒long timeoutMicros max(unit.toMicros(timeout), 0);checkPermits(permits);long microsToWait;synchronized (mutex()) {long nowMicros stopwatch.readMicros();// 判断是否可以在timeoutMicros时间范围内获取令牌if (!canAcquire(nowMicros, timeoutMicros)) {return false;} else {// 获取令牌并返回需要等待的毫秒数microsToWait reserveAndGetWaitLength(permits, nowMicros);}}// 等待microsToWait时间stopwatch.sleepMicrosUninterruptibly(microsToWait);return true;
}private boolean canAcquire(long nowMicros, long timeoutMicros) {return queryEarliestAvailable(nowMicros) - timeoutMicros nowMicros;
}// 返回可用令牌的最早时间
abstract long queryEarliestAvailable(long nowMicros);// SmoothRateLimiter#queryEarliestAvailable
final long queryEarliestAvailable(long nowMicros) {// 授予下一个请求无论其大小如何的时间return nextFreeTicketMicros;
}该方法执行下面三步
判断能否在指定超时时间内获取到令牌通过 nextFreeTicketMicros nowMicros timeoutMicros 是否为true来判断即当前时间超时时间 在可取令牌时间 之后则可取预消费的特性否则不可获取。如果不可获取立即返回false。如果可获取则调用 reserveAndGetWaitLength(permits, nowMicros) 来更新下次可取令牌时间点与当前存储的令牌数返回等待时间逻辑与acquire(int)相同并阻塞等待相应的时间返回true。
存量桶系数
令牌桶算法中多余的令牌会放到桶里。这个桶的容量是有上限的决定这个容量的就是存量桶系数默认为 1.0即默认存量桶的容量是 1.0 倍的限流值。推荐设置 0.6~1.5 之间。存量桶系数的影响有两方面
突发流量第一个周期放过的请求数。如存量桶系数等于 0.6第一个周期最多放过 1.6 倍限流值的请求数。影响误杀率。存量桶系数越大越能容忍流量不均衡问题。误杀率服务限流是对单机进行限流线上场景经常会用单机限流模拟集群限流。由于机器之间的秒级流量不够均衡所以很容易出现误限。例如两台服务器总限流值 20每台限流 10某一秒两台服务器的流量分别是 5、15这时其中一台就限流了 5 个请求。减小误杀率的两个办法 拉长限流周期。使用令牌桶算法并且调出较好的存量桶系数。
小结
RateLimiter 令牌桶的实现并不是起一个线程不断往桶里放令牌而是以一种延迟计算的方式参考resync函数在每次获取令牌之前计算该段时间内可以产生多少令牌将产生的令牌加入令牌桶中并更新数据来实现比起一个线程来不断往桶里放令牌高效得多。想想如果需要针对每个用户限制某个接口的访问则针对每个用户都得创建一个RateLimiter并起一个线程来控制令牌存放的话如果在线用户数有几十上百万起线程来控制是一件多么恐怖的事情
优缺点
优点
放过的流量比较均匀有利于保护系统。存量令牌能应对突发流量很多时候我们希望能放过脉冲流量。而对于持续的高流量后面又能均匀地放过不超过限流值的请求数。
缺点
存量令牌没有过期时间突发流量时第一个周期会多放过一些请求可解释性差。即在突发流量的第一个周期默认最多会放过 2 倍限流值的请求数。实际限流数难以预知跟请求数和流量分布有关。
与漏桶的区别
令牌桶是按照固定速率往桶中添加令牌请求是否被处理需要看桶中令牌是否足够当令牌数减为零时则拒绝新的请求。漏桶则是按照固定速率流出请求流入请求速率任意当流入的请求数累积到漏桶容量时则新流入的请求被拒绝。令牌桶限制的是平均流入速率允许突发请求只要有令牌就可以处理支持一次拿3个令牌或4个令牌 并允许一定程度的突发流量。漏桶限制的是常量流出速率即流出速率是一个固定常量值比如都是1的速率流出而不能一次是1下次又是2) , 从而平滑突发流入速率。令牌桶允许一定程度的突发而漏桶主要目的是平滑流入速率。
总结
令牌桶算法是一种单机限流算法已一定速率向桶中添加令牌允许突发流量支持预消费预消费的等待时间由之后的请求承担。当QPS小于100时比较适合使用。
