icon psd下载网站,开通微信公众号要钱吗,做高端网站的网络公司,建设旅游信息网站的好处文章目录 基本知识限流器的类图使用示例 原理解析限流整体流程问题驱动1、限流器创建的时候会初始化令牌吗#xff1f;2、令牌是如何放到桶里的#xff1f;3、如果要获取的令牌数大于桶里的令牌数会怎么样4、令牌数量的更新会有并发问题吗 总结 实际工作中难免有限流的场景。… 文章目录 基本知识限流器的类图使用示例 原理解析限流整体流程问题驱动1、限流器创建的时候会初始化令牌吗2、令牌是如何放到桶里的3、如果要获取的令牌数大于桶里的令牌数会怎么样4、令牌数量的更新会有并发问题吗 总结 实际工作中难免有限流的场景。我们熟知的限流算法有计数器限流固定窗口、滑动窗口算法、漏桶算法、令牌桶算法等。其具体实现也多种多样本文就来简单窥探一下Guava的实现。 基本知识
限流器的类图 RateLimiter限流器基类定义限流器的创建、令牌的获取等操作。 SmoothRateLimiter定义一种平滑的限流器也是抽象类继承RateLimiter。 SmoothBursty普通的平滑限流器实现类实现SmoothRateLimiter。以稳定的速率生成令牌则会同时全部被获取到。比如令牌桶现有令牌数为5这时连续进行10个请求则前5个请求会全部直接通过没有等待时间之后5个请求则每隔200毫秒通过一次。 SmoothWarmingUp预热的平滑限流器实现类实现SmoothRateLimiter。随着请求量的增加令牌生成速率会缓慢提升直到一个稳定的速率。比如令牌桶现有令牌数为5这时连续进行10个请求只会让第一个请求直接通过之后的请求都会有等待时间等待时间不断缩短直到稳定在每隔200毫秒通过一次。这样就会有一个预热的过程。 下文以SmoothBursty为例来分析限流原理。 使用示例
public class RateLimitTest {public static void main(String[] args) throws InterruptedException {// 1、创建限流器一秒内最多允许2个请求通过RateLimiter rateLimiter RateLimiter.create(2);serial(rateLimiter);}private static void serial(RateLimiter rateLimiter) throws InterruptedException {for (int i 0; i 10; i) {String time LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);// 2、尝试获取令牌不论是否能获取到都直接返回boolean res rateLimiter.tryAcquire();// 获取令牌如果获取不到就一直等待// rateLimiter.acquire();if (res) {System.out.println(time :请求被允许);} else {System.out.println(time :请求被限流);}Thread.sleep(250);}}}执行结果
15:52:08.583:请求被允许
15:52:08.852:请求被限流
15:52:09.108:请求被允许
15:52:09.361:请求被限流
15:52:09.617:请求被允许
15:52:09.872:请求被限流
15:52:10.127:请求被允许
15:52:10.378:请求被限流
15:52:10.629:请求被允许
15:52:10.882:请求被限流可以看到同一秒内最多只有2个请求被允许。
原理解析
限流整体流程 创建限流器。此时桶里的令牌数为0。设置QPS5每秒最多允许5个请求这个数字“5”带表了两层含义 1桶里最大只能容纳5个令牌。 2一秒可以生成5个令牌生成一个令牌需要1/50.2秒200毫秒。发起请求。此时距离限流器创建已经经过了一秒桶里应该存在5个令牌而本次请求需要获取并消耗1个令牌。更新令牌数量。
上面只是描述了一个大致思路还有很多细节问题需要考虑下文就以问题来驱动原理探究。
问题驱动
限流器关键属性解释 SmoothRateLimiter.java
/*** 当前桶中已存在的令牌数如果请求需要的令牌数小于已存在的令牌数就允许通过*/
double storedPermits;/*** 令牌桶可以保存的最大令牌数*/
double maxPermits;/*** 多长时间可以生成一个令牌单位是微秒。比如RateLimiter.create(5)就意味着1秒生成5个令牌那么生成一个令牌就需要200ms*/
double stableIntervalMicros;/*** 重要下一个请求可以被允许获取令牌的时间点单位是微秒。*/
private long nextFreeTicketMicros 0L;1、限流器创建的时候会初始化令牌吗
我们从限流器的创建源码着手分析。 RateLimiter.java
public static RateLimiter create(double permitsPerSecond) {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;}public final void setRate(double permitsPerSecond) {checkArgument(permitsPerSecond 0.0 !Double.isNaN(permitsPerSecond), rate must be positive);synchronized (mutex()) {// 关键doSetRate(permitsPerSecond, stopwatch.readMicros());}}// 由子类即SmoothRateLimiter来实现abstract void doSetRate(double permitsPerSecond, long nowMicros);SmoothRateLimiter.java
Overridefinal void doSetRate(double permitsPerSecond, long nowMicros) {// 重点1生成令牌并同步下次可以获取令牌的时间resync(nowMicros);double stableIntervalMicros SECONDS.toMicros(1L) / permitsPerSecond;// 将stableIntervalMicros从默认的0.0设置为 生成一个令牌所需的时间this.stableIntervalMicros stableIntervalMicros;// 重点2doSetRate(permitsPerSecond, stableIntervalMicros);}// 重点1/** 限流器创建doSetRate(double permitsPerSecond, long nowMicros)* 以及 获取令牌reserveEarliestAvailable(int requiredPermits, long nowMicros)的时候都会调用这个方法* 如果是创建时调用 由于coolDownIntervalMicros返回值即stableIntervalMicros0所以当前storedPermits的计算结果仍为0**/void resync(long nowMicros) {if (nowMicros nextFreeTicketMicros) {// 下一次可以获取令牌的时间到现在这段时间内需要生成多少令牌由于当前coolDownIntervalMicros()会返回0.0所以计算结果为Infinity无穷double newPermits (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();// 保证桶里的令牌数不能超过最大允许的令牌数因为newPermits无穷所以这里计算出桶里的令牌数应该是0storedPermits min(maxPermits, storedPermits newPermits);// 将nextFreeTicketMicros值设为限流器创建的时间nextFreeTicketMicros nowMicros;}}// 由子类即SmoothBursty来实现abstract void doSetRate(double permitsPerSecond, double stableIntervalMicros);static final class SmoothBursty extends SmoothRateLimiter {// 重点2Overridevoid doSetRate(double permitsPerSecond, double stableIntervalMicros) {// 当前允许的最大令牌数限流器创建时该值为0.0double 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 {// 如果最大允许的令牌数时0则将桶里的令牌数也置为0storedPermits (oldMaxPermits 0.0)? 0.0 // initial state: storedPermits * maxPermits / oldMaxPermits;}}Overridedouble coolDownIntervalMicros() {// 返回的就是生成一个令牌需要多长时间该值在限流器创建的时候初始值为0.0return stableIntervalMicros;}}通过上面源码中 重点1和重点2的分析可以发现在创建限流器的时候当前桶中的令牌数一直是0。
结论限流器创建的时候不会初始化令牌
2、令牌是如何放到桶里的
我们经常看到对于令牌桶限流算法的描述是将令牌每隔一段时间定时放入桶中。 乍一看也许需要一个定时器才能达到这个效果。但Guava的实现告诉我们其实不用这么复杂只需要一个计数器storedPermits变量就能搞定。
想要知道令牌如何放到桶里就需要从获取令牌的时候开始探索。 这有点奇怪对吗正常是先把令牌放到桶里然后才获取令牌即有因才有果但是我们却需要先知道如何获取令牌才能知道令牌是如何放到桶里的。 在我看来这正是Guava实现的巧妙之处。 RateLimiter.java
/**
* 尝试获取令牌
* param permits 要获取的令牌数
* param timeout 能获取到令牌的最大等待时间等待时间超过这个时间就直接返回false。如果该值是0不做任何等待直接返回是否获取到令牌
*/
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)) {// 获取不了就返回falsereturn false;} else {// 关键如果在超时时间内能获取到令牌计算需要等待的时间microsToWait reserveAndGetWaitLength(permits, nowMicros);}}// 睡眠等待足够的时间stopwatch.sleepMicrosUninterruptibly(microsToWait);return true;}private boolean canAcquire(long nowMicros, long timeoutMicros) {// 获取最早可以获得令牌的时间return queryEarliestAvailable(nowMicros) - timeoutMicros nowMicros;}final long reserveAndGetWaitLength(int permits, long nowMicros) {// 关键获取令牌并返回最早能获得令牌的时间long momentAvailable reserveEarliestAvailable(permits, nowMicros);return max(momentAvailable - nowMicros, 0);}// 由子类即SmoothBursty实现abstract long queryEarliestAvailable(long nowMicros);// 由子类即SmoothBursty实现abstract long reserveEarliestAvailable(int permits, long nowMicros);SmoothBursty.java
final long queryEarliestAvailable(long nowMicros) {// 又是它待会分析它到底是个什么东西return nextFreeTicketMicros;}/*** 获取令牌的核心方法** param requiredPermits 需要获取的令牌数* param nowMicros* return*/Overridefinal long reserveEarliestAvailable(int requiredPermits, long nowMicros) {// 关键生成令牌并将下一次可以获取令牌的时间设置为当前时间resync(nowMicros);// 这里拿到的是最早可以获取到令牌的时间long returnValue nextFreeTicketMicros;// 实际能获取的令牌数有可能需要的令牌数大于当前桶里的令牌数两者取最小double storedPermitsToSpend min(requiredPermits, this.storedPermits);// 实际拿到的令牌数相比需要的令牌数还差多少double freshPermits requiredPermits - storedPermitsToSpend;// 要拿到还差的令牌数还需要等多久long waitMicros storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) (long) (freshPermits * stableIntervalMicros);// 重点3更新下一次可以获取令牌的时间 当前时间 要拿到还差的令牌数要等的时间this.nextFreeTicketMicros LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);// 重点4更新桶里还剩的令牌数this.storedPermits - storedPermitsToSpend;return returnValue;}void resync(long nowMicros) {if (nowMicros nextFreeTicketMicros) {// 下一次可以获取令牌的时间到现在这段时间内需要生成多少令牌double newPermits (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();// 重点1生成令牌并放入桶中storedPermits min(maxPermits, storedPermits newPermits);// 重点2将nextFreeTicketMicros值设为当前时间nextFreeTicketMicros nowMicros;}}通过上面源码中的重点1、重点2、重点3、重点4可以发现
重点1是向桶里放令牌既增加令牌计数器storedPermits重点4是从桶里获取令牌既减少令牌计数器storedPermits重点2和重点3都是更新nextFreeTicketMicros
所以令牌的生成、获取都围绕着两个变量storedPermits当前桶里的令牌数和nextFreeTicketMicros下次可以获得令牌的时间。
而这两个变量也正是Guava限流设计的巧妙之处不必提前向桶里放入令牌或通过一个单独的定时器向桶里放令牌而是在获取令牌的时候增加令牌数量再减少令牌数量。
用图来更加直观的体现这里的逻辑。 nextFreeTicketMicros在源码中其实是用微秒级时间戳表示为了方便理解下面就用正常时间来表示。 创建限流器。RateLimiter rateLimiter RateLimiter.create(5);即QPS5每秒生成5个令牌生成1个令牌需要200毫秒桶内最大令牌数5。storedPermits此时桶里的令牌数0nextFreeTicketMicros下次可以获取令牌的时间0。请求A要获取1个令牌。rateLimiter.acquire();当前时间是2023-9-26 10:00:00。发现当前时间 nextFreeTicketMicros两者相差的这段时间远远大于1秒而1秒可以生成5个令牌最多也只能存5个。同时要把nextFreeTicketMicros设置为当前时间意味着现在桶里已经有令牌了现在马上就可以获取到令牌。此时storedPermits5nextFreeTicketMicros2023-9-26 10:00:00。获取到1个令牌此时storedPermits4nextFreeTicketMicros2023-9-26 10:00:00。请求B要获取10个令牌。rateLimiter.acquire(10);当前时间是2023-9-26 10:00:01.001。发现当前时间 nextFreeTicketMicros两者相差的这段时间大于1秒1秒可以生成5个令牌当前桶里还有4个549但桶最多只能存5个。同时要把nextFreeTicketMicros设置为当前时间意味着现在桶里已经有令牌了现在马上就可以获取到令牌。此时storedPermits5nextFreeTicketMicros2023-9-26 10:00:01.001。需要获取10个令牌但是现在桶里只有5个即使全部获取还欠5个那就提前透支5个咯。意味着接下来这1秒生成的5个令牌是预留给当前请求的其它请求1秒后才能再获取令牌。此时storedPermits0nextFreeTicketMicros2023-9-26 10:00:02.001。请求C要获取1个令牌。rateLimiter.acquire();当前时间是2023-9-26 10:00:01.999。由于nextFreeTicketMicros2023-9-26 10:00:02.001。还没到下次可以获取令牌的时间就只能等待。等待ing …当前时间是2023-9-26 10:00:02.200。当前时间 nextFreeTicketMicros相差的这段时间是200毫秒刚好能生成1个令牌。同时要把nextFreeTicketMicros设置为当前时间意味着现在桶里已经有令牌了现在马上就可以获取到令牌。此时storedPermits1nextFreeTicketMicros2023-9-26 10:00:02.200。获取到1个令牌此时storedPermits0nextFreeTicketMicros2023-9-26 10:02:200。
结论令牌的生成其实是在令牌的获取逻辑中。
3、如果要获取的令牌数大于桶里的令牌数会怎么样
经过上面的分析可以得出结论会透支/预支不足的令牌数。
4、令牌数量的更新会有并发问题吗
可以看一下获取令牌时的源码
public double acquire(int permits) {long microsToWait reserve(permits);stopwatch.sleepMicrosUninterruptibly(microsToWait);return 1.0 * microsToWait / SECONDS.toMicros(1L);}final long reserve(int permits) {checkPermits(permits);// 这里已经加了同步处理synchronized (mutex()) {return reserveAndGetWaitLength(permits, stopwatch.readMicros());}}结论同一个限流器不会有并发问题。
总结
本文并不过多深度剖析源码和原理。旨在以初学者的角度窥探Guava限流器的限流实现思路并解答一些理解中存在的疑惑。
尤其是令牌生成和获取的设计思路也能对自己的日常工作有启发作用
