网站安装环境配置,网站开发需要大学吗,北京网站开发哪家强,毕节市建设网站大纲
1.漏桶算法的实现对比
(1)普通思路的漏桶算法实现
(2)节省线程的漏桶算法实现
(3)Sentinel中的漏桶算法实现
(4)Sentinel中的漏桶算法与普通漏桶算法的区别
(5)Sentinel中的漏桶算法存在的问题
2.令牌桶算法的实现对比
(1)普通思路的令牌桶算法实现
(2)节省线程的…大纲
1.漏桶算法的实现对比
(1)普通思路的漏桶算法实现
(2)节省线程的漏桶算法实现
(3)Sentinel中的漏桶算法实现
(4)Sentinel中的漏桶算法与普通漏桶算法的区别
(5)Sentinel中的漏桶算法存在的问题
2.令牌桶算法的实现对比
(1)普通思路的令牌桶算法实现
(2)节省线程的令牌桶算法实现
(3)Guava中的令牌桶算法实现
(4)Sentinel中的令牌桶算法实现
(5)Sentinel中的令牌桶算法总结 1.漏桶算法的实现对比
(1)普通思路的漏桶算法实现
(2)节省线程的漏桶算法实现
(3)Sentinel中的漏桶算法实现
(4)Sentinel中的漏桶算法与普通漏桶算法的区别
(5)Sentinel中的漏桶算法存在的问题 (1)普通思路的漏桶算法实现
一.漏桶算法的处理流程
二.漏桶算法的主要特点
三.漏桶算法的优缺点 一.漏桶算法的处理流程
漏桶算法的核心思想是以固定速率流出。 步骤一当新的请求到达时会将新的请求放入缓冲区(请求队列)中类似于往水桶里注水。 步骤二系统会以固定的速度处理缓冲区中的请求类似于水从窟窿中以固定的速度流出比如开启一个后台线程定时以固定的速度从缓冲区中取出请求然后进行分发处理。 步骤三如果缓冲区已满则新的请求将被拒绝或丢弃类似于水溢出。 二.漏桶算法的主要特点
特点一固定速率
水从桶底的孔洞中以固定速率流出类似于网络中以固定速率发送数据包。但写入速度不固定也就是请求不是匀速产生的。相当于生产者生产消息不固定消费者消费消息是匀速消费的。 特点二有限容量
桶的容量有限当桶满时新到达的水会溢出即拒绝超过容量的请求。 特点三先进先出(FIFO)
水按照先进先出的顺序从桶中流出类似于请求的处理顺序。 这种算法的一个重要特性是无论请求的接收速率如何变化请求的处理速率始终是稳定的这就确保了系统的负载不会超过预设的阈值。但是由于请求的处理速率是固定的所以无法处理突发流量。此外如果入口流量过大漏桶可能会溢出导致请求丢失。 三.漏桶算法的优缺点
优点一平滑流量
由于以固定的速率处理请求所以可以有效地平滑和整形流量避免流量的突发和波动类似于消息队列的削峰填谷的作用。 优点二防止过载
当流入的请求超过桶的容量时可以直接丢弃请求防止系统过载。 缺点一无法处理突发流量
由于漏桶的出口速度是固定的无法处理突发流量。例如即使在流量较小的时候也无法以更快的速度处理请求。 缺点二可能会丢失数据
如果入口流量过大超过了桶的容量那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中这可能是一个问题。 缺点三不适合处理速率变化大的场景
如果处理速率变化大或需要动态调整处理速率则无法满足。 漏桶算法适用于需要以固定速率处理请求的场景。在多数业务场景中其实并不需要按照严格的速率进行请求处理。而且多数业务场景都需要应对突发流量的能力所以会使用令牌桶算法。 (2)节省线程的漏桶算法实现
漏桶算法可以通过延迟计算的方式来实现。延迟计算指的是不需要单独的线程来定时生成令牌或从漏桶中定时取请求而是由调用限流器的线程自己计算是否有足够的令牌以及需要sleep的时间。延迟计算的方式可以节省一个线程资源。
public class LeakyBucketLimiter {//桶的最大容量public static long threshold 10;//当前桶内的水量public static long count 0;//漏水速率(每秒5次)public static long leakRate 5;//上次漏水时间public static long lastLeakTime System.currentTimeMillis();//限流方法返回true表示通过public boolean canPass() {//调用漏水方法this.leak();//判断是否超过最大请求数量if (count threshold) {count;return true;}return false;}//漏水方法计算并更新这段时间内漏水量private void leak() {//获取系统当前时间long currentTime System.currentTimeMillis();//计算这段时间内需要流出的水量long leakWater (currentTime - lastLeakTime) * leakRate / 1000;count Math.max(count - leakWater, 0);//更新最近一次的漏水时间lastLeakTime currentTime;}
}
(3)Sentinel中的漏桶算法实现
在RateLimiterController的canPass()方法中为了判断是否超出QPS阈值通过原子类变量latestPassedTime简化成单线程让请求先后通过的处理模型。为了尽量让业务不受Sentinel影响采用预估请求的被处理时间点的方式。也就是无需等前面的请求完全被处理完才确定后面的请求被处理的时间。因为在普通的漏桶算法中是处理完一个请求才从漏桶取出水滴。而RateLimiterController的漏桶算法则是假设请求已经被通过了。 具体的判断逻辑如下首先获取系统的当前时间currentTime。然后计算在满足流控规则中限制的QPS阈值count的情况下先后的两个请求被允许通过时的最小时间间隔costTime。接着计算当前请求最早的预期通过时间expectedTime也就是此次请求预计会在几时几分几秒内通过。最后比较expectedTime和currentTime就可知当前请求是否允许通过了。 一.如果expectedTime小于等于currentTime
也就是当前请求最早的预期通过时间比系统当前时间小。如果在此时(currentTime)通过当前请求则当前请求的通过时间就比它最早的预期通过时间(expectedTime)要晚即当前请求和最近通过的请求的时间间隔变大了所以此时不会超QPS阈值。于是返回true允许通过同时更新最近允许请求通过的时间戳为当前时间。 二.如果expectedTime大于currentTime
也就是当前请求最早的预期通过时间比系统当前时间大。如果在此时(currentTime)通过当前请求则当前请求的通过时间就比它最早的预期通过时间(expectedTime)要早即当前请求和最近通过的请求的时间间隔变小了比最小间隔时间costTime还小所以此时必然会超QPS阈值。因此返回进行等待或者返回false不允许通过等待的最小时间就是最近通过请求的时间 先后两个请求允许通过时的最小间隔时间 - 当前时间。 需要注意Sentinel流量控制的漏桶算法只能限制在costTime内的流量激增限制不了costTime外的流量激增。比如系统启动完一瞬间就涌入大量并发请求此时的流量激增限制不了。又比如系统处理完正常流量的最后一个请求隔了costTime的时间后突然涌入超QPS阈值的并发请求此时也限制不了这种情况的流量激增。但如果系统处理完正常流量的最后一个请求隔了costTime-的时间后突然涌入超QPS阈值的并发请求此时则可以限制这种情况的流量激增。 同时为了避免等待的各个并发线程被同时唤醒可以利用原子变量的addAndGet()方法 假设等待请求已被通过的方式实现需要等待的并发请求进行睡眠等待的时间都不一样从而实现并发请求排队等待的效果。 实现排队等待效果的核心逻辑由于latestPassedTime的原子性每个线程都会获得不一样的oldTime。接着根据oldTime - 当前时间就可以得到每个线程需要睡眠等待的时间waitTime。此时的waitTime都将会不一样从而避免并发线程同时被唤醒的情况。将latestPassedTime按costTime进行自增其实相当于假设当前请求在不超过QPS阈值的情况下被允许通过了。
public class RateLimiterController implements TrafficShapingController {//排队等待的意思是超出阈值后等待一段时间maxQueueingTimeMs就是请求在队列中的最大等待时间private final int maxQueueingTimeMs;//流控规则中限制QPS的阈值也就是QPS超出多少后会进行限制private final double count;//最近允许一个请求通过的时间每次请求通过后就会更新此时间可以根据该时间计算出当前请求最早的预期通过时间//注意Sentinel是在业务前面的尽量不要让业务受到Sentinel的影响所以不需要等请求完全被处理完才确定请求被通过的时间private final AtomicLong latestPassedTime new AtomicLong(-1);public RateLimiterController(int timeOut, double count) {this.maxQueueingTimeMs timeOut;this.count count;}Overridepublic boolean canPass(Node node, int acquireCount) {return canPass(node, acquireCount, false);}Overridepublic boolean canPass(Node node, int acquireCount, boolean prioritized) {//acquireCount代表每次从桶底流出多少个请求//如果acquireCount小于等于0则表示无需限流直接通过不过acquireCount一般默认是1if (acquireCount 0) {return true;}//如果限流规则的count(即限制QPS的阈值)小于等于0则直接拒绝相当于一个请求也不能放行if (count 0) {return false;}//1.首先获取系统的当前时间long currentTime TimeUtil.currentTimeMillis();//2.然后计算在满足流控规则中限制的QPS阈值count的情况下先后的两个请求被允许通过时的最小间隔时间(假设请求是单线程处理的)long costTime Math.round(1.0 * (acquireCount) / count * 1000);//3.接着计算当前请求最早的预期通过时间 满足QPS阈值下的两个请求的最小时间间隔 上次请求的通过时间long expectedTime costTime latestPassedTime.get();//4.最后判断当前请求最早的预期通过时间是否比系统当前时间小if (expectedTime currentTime) {//等价于没有超出QPS阈值//当前请求最早的预期通过时间比系统当前时间小//如果在此时(currentTime)通过当前请求那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要晚//也就是当前请求和最近通过的请求的时间间隔变大了所以此时不会超QPS阈值返回true允许通过//由这里可知latestPassedTime并不会影响costTime也就是说多个线程可以并发执行到这里而不受阈值的影响//这意味着Sentinel流量控制的漏桶算法只能限制在costTime时间内的流量激增限制不了costTime时间外的流量激增//比如系统启动完的那一瞬间就涌入超出QPS阈值的并发请求此时的这种流量激增是限制不了的//又比如系统正常运行时处理完了正常流量的最后一个请求隔了costTime的时间后突然涌入超出QPS阈值的并发请求此时也限制不了//只能限制住这样的一种情况系统正常运行处理完正常流量的最后一个请求隔了costTime-的时间突然涌入超出QPS阈值的并发请求latestPassedTime.set(currentTime);return true;} else {//如果不是即当前请求最早的预期通过时间比系统当前时间大//则说明latestPassedTime.get()大了也就是上一个可能由于QPS超出阈值的原因导致请求处理慢了所以需要进行等待//计算当前请求的等待时间用于判断是否超出流控规则设置的最大等待时间long waitTime costTime latestPassedTime.get() - TimeUtil.currentTimeMillis();if (waitTime maxQueueingTimeMs) {//如果超出最大等待时间则直接返回falsereturn false;} else {//等价于超出了QPS阈值//当前请求最早的预期通过时间比系统当前时间大//如果在此时(currentTime)通过当前请求那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要早//也就是当前请求和最近通过的请求的时间间隔变小了比最小间隔时间costTime还小//所以此时必然会超QPS阈值因此返回进行等待或者返回false不允许通过//而等待的最小时间就是最近通过请求的时间 先后两个请求允许通过时的最小间隔时间 - 当前时间//首先通过latestPassedTime这个原子变量的addAndGet()方法//将最近通过请求的时间latestPassedTime加上先后两次请求需要的最小间隔时间costTime得到当前请求本来预期的通过时间//注意//当多个并发线程执行到此处时由于latestPassedTime的原子性每个线程都会获得不一样的oldTime//接着根据oldTime - 当前时间就可以得到每个线程需要睡眠等待的时间waitTime//此时的waitTime都将会不一样从而避免并发线程同时被唤醒的情况//将latestPassedTime进行自增其实相当于假设当前请求在不超过QPS阈值的情况下被允许通过了long oldTime latestPassedTime.addAndGet(costTime);try {//然后计算当前请求需要等待多久 当前请求最早的预期通过时间 - 当前系统时间waitTime oldTime - TimeUtil.currentTimeMillis();//如果等待时间大于流控规则设置的最大等待时间则需要回滚刚才更新的最近通过请求的时间//也就是将latestPassedTime减去costTime然后返回false表示请求无法通过if (waitTime maxQueueingTimeMs) {//如果发现新计算的等待时间 大于 最大等待时间则需要回滚latestPassedTimelatestPassedTime.addAndGet(-costTime);return false;}//in race condition waitTime may 0if (waitTime 0) {//当前请求需要进行等待Thread.sleep(waitTime);}return true;} catch (InterruptedException e) {}}}return false;}
}
(4)Sentinel中的漏桶算法与普通漏桶算法的区别
区别一普通漏桶算法使用的是真实队列
节省线程的漏桶算法会有一个单独的字段去记录当前桶内的水量也就是请求量。每通过一个请求则该字段值-1。反之每新进一个请求此字段值1。 区别二Sentinel漏桶算法使用的是虚拟队列
它没有单独的字段去记录当前桶内的请求量而是根据最近通过请求的时间得出当前请求最早的预期通过时间来实现。其本质就是先假设当前请求可以通过然后再按照先后请求在QPS阈值下可以允许通过时的最大时间间隔来计算出当前请求最早的预期通过时间再对比是否和当前发生冲突。 区别三普通漏桶算法使用的策略是直接拒绝
如果流入速度大于流出速度则直接拒绝。 区别四Sentinel漏桶算法使用的策略是排队等待
如果超出了阈值则不会直接拒绝请求而是会等待一段时间只要在这段时间内能处理到这个请求就不会拒绝掉。 (5)Sentinel中的漏桶算法存在的问题
问题一在costTime时间内出现流量激增才能限流
如果在costTime时间外即最后一次请求通过的时间已经好久了突然流量激增以及并发进入系统那么此时是无法限制住的。 问题二Sentinel排队等待流控效果支持的QPS阈值不能超过1000
如果超过1000且costTime计大于等于0.5则会认为间隔时间都是1ms。如果costTime小于0.5则认为配置失效相当于没有配置此条流控规则。
long costTime Math.round(1.0 * (acquireCount) / count * 1000);
long costTime Math.round(1.0 * (1) / 1100 * 1000)约等于0.9ms
默认情况下acquireCount的值是1那么如果QPS阈值count在10002000此时costTime 1限流不受阈值影响。如果QPS阈值count大于2000此时costTime 0限流配置失效。 2.令牌桶算法的实现对比
(1)普通思路的令牌桶算法实现
(2)节省线程的令牌桶算法实现
(3)Guava中的令牌桶算法实现
(4)Sentinel中的令牌桶算法实现
(5)Sentinel中的令牌桶算法总结 (1)普通思路的令牌桶算法实现
一.令牌桶算法的处理流程
二.令牌桶算法的特点
三.令牌桶算法的优缺点
四.漏桶算法和令牌桶算法的对比
五.令牌桶算法和漏桶算法的核心区别 一.令牌桶算法的处理流程
令牌桶算法的核心思想是以固定速率流入。 步骤一初始化令牌桶设置其容量和生成速率。 步骤二当有新请求到来时检查令牌桶中是否有足够的令牌。如果有足够的令牌则允许请求通过并从令牌桶中扣除相应数量令牌。如果没有足够的令牌则拒绝请求。 步骤三系统会以固定的速度添加令牌直到达到令牌桶容量比如开启一个后台线程以固定的速度向令牌桶中添加令牌。 二.令牌桶算法的特点
特点一支持突发流量
令牌桶算法允许在限流内应对突发流量有助于提高系统的响应能力。 特点二平滑处理速率
和漏桶算法一样令牌桶算法也可以平滑处理流量避免处理速率突变。 令牌桶算法的一个重要特性是它能够处理突发流量。当桶中有足够的令牌时可以一次性处理多个请求。这对于需要处理突发流量的应用场景非常有用但是又不会无限制的增加处理速率导致压垮服务器因为桶内令牌数量是有限制的。 三.令牌桶算法的优缺点
优点一可以处理突发流量
令牌桶算法可以处理突发流量。当桶满时能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。 优点二限制请求处理的平均速率
在长期运行中请求的处理速率会被限制在预定义的平均速率下也就是生成令牌的速率。 优点三灵活性
与漏桶算法相比令牌桶算法提供了更大的灵活性。例如可以动态地调整生成令牌的速率。 缺点一可能导致过载
如果令牌产生速度过快可能会导致大量突发流量使网络或服务过载。 缺点二需要存储空间
令牌桶需要一定的存储空间来保存令牌可能会导致内存资源的浪费。 四.漏桶算法和令牌桶算法的对比
漏桶算法是突然往桶里注水但是漏水的窟窿是固定大小的因此流出水的速度是固定的也就是生产不限速消费限速。 令牌桶算法是突然从桶中抽水也就是固定大小的窟窿变成了入水口而没桶盖的桶口变成了出水口。相当于入水速度变得固定了而出水速度不做限制了也就是生产限速消费不限速。 五.令牌桶算法和漏桶算法的核心区别
令牌桶算法允许用户在短时间内发起更多请求从而支持突发流量。漏桶算法只能支持每秒固定处理一定数量的请求从而不支持突发流量。这就是令牌桶和漏桶的核心区别。 (2)节省线程的令牌桶算法实现
令牌桶算法可以通过延迟计算的方式来实现。延迟计算指的是不需要单独的线程来定时生成令牌或从漏桶中定时取请求而是由调用限流器的线程自己计算是否有足够的令牌以及需要sleep的时间。延迟计算的方式可以节省一个线程资源。
public class TokenBucketLimiter {//桶的最大容量public static long threshold 10;//当前桶内的令牌数public static long count 0;//令牌生成速率(每秒5次)public static long tokenRate 5;//上次生成令牌的时间public static long lastRefillTime System.currentTimeMillis();//限流方法返回true表示通过public boolean canPass() {//调用生成令牌方法this.refillTokens();//判断桶内是否还有令牌if (count 0) {count--;return true;}return false;}//生成令牌方法计算并更新这段时间内生成的令牌数量private void refillTokens() {long currentTime System.currentTimeMillis();//计算这段时间内需要生成的令牌数量long refillTokens (currentTime - lastRefillTime) * tokenRate / 1000;//更新桶内的令牌数count Math.min(count refillTokens, threshold);//更新令牌生成时间lastRefillTime currentTime;}
}
(3)Guava中的令牌桶算法实现
一.SmoothBursty的初始化
二.SmoothBursty的acquire()方法
三.SmoothWarmingUp的初始化
四.SmoothWarmingUp的acquire()方法 SmoothBursty和SmoothWarmingUp这两种限流器都使用了预支令牌的思路来实现就是当前线程获取令牌的代价(阻塞时间)需要由下一个线程来支付。这样可以减少线程阻塞的概率因为下一个请求不确定什么时候才来。如果下一个请求很久才来那么这段时间产生的新令牌已满足下一个线程的需求这样就不用阻塞了。 一.SmoothBursty的初始化
RateLimiter不保存上一次请求的时间但是它保存下一次请求期望到达的时间。如果下一个请求的预期到达时间实际上已经过去了并且假设下次请求期望到达的时间点是past现在的时间点是now。那么now - past的这段时间表示RateLimiter没有被使用所以在这段空闲的时间内RateLimiter就会增加storedPermits的数量。
Beta
GwtIncompatible
SuppressWarnings(GoodTime)
public abstract class RateLimiter {...//Creates a RateLimiter with the specified stable throughput, //given as permits per second (commonly referred to as QPS, queries per second).//The returned RateLimiter ensures that on average no more than permitsPerSecond are issued during any given second, //with sustained requests being smoothly spread over each second.//When the incoming request rate exceeds permitsPerSecond the rate limiter will release one permit every (1.0 / permitsPerSecond) seconds. //When the rate limiter is unused, bursts of up to permitsPerSecond permits will be allowed, //with subsequent requests being smoothly limited at the stable rate of permitsPerSecond.//创建一个具有指定稳定吞吐量的RateLimiter传入的permits per second通常称为QPS、每秒查询量//返回的RateLimiter确保在任何给定的秒期间平均不超过permitsPerSecond的令牌被发出持续的请求将在每一秒内被平稳地通过//当传入请求的速率超过permitsPerSecond时速率限制器将每隔(1.0/permitsPerSecond)秒释放一个令牌//当速率限制器未被使用时将允许突发式的高达permitsPerSecond的令牌而随后的请求将以permitsPerSecond的稳定速率被平滑地限制//对外暴露的创建方法//param permitsPerSecond the rate of the returned RateLimiter, measured in how many permits become available per second.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.//默认的RateLimiter配置可以保存长达一秒钟的未被使用的令牌//这是为了避免在这种情况下出现不必要的停顿//一个由1qps和4个线程组成的RateLimiter所有线程都在如下这些时刻调用acquired()//Thread0在0秒、Thread1在1.05秒、Thread2在2秒、Thread3在3秒//由于Thread1的轻微延迟Thread2必须睡眠到2.05秒Thread3也必须睡眠到3.05秒//内部调用一个qps设定 起始时间StopWatch的构建函数.//这里传入的SleepingStopwatch是一个以系统启动时间的一个相对时间的计量.//后面的读时间偏移是以这个开始的时间偏移为起始的.return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());}VisibleForTestingstatic RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {//指定了令牌桶中最多存储1秒的令牌数RateLimiter rateLimiter new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);//调用RateLimiter.setRate()方法rateLimiter.setRate(permitsPerSecond);return rateLimiter;}//Updates the stable rate of this RateLimiter, //that is, the permitsPerSecond argument provided in the factory method that constructed the RateLimiter. //Currently throttled threads will not be awakened as a result of this invocation, //thus they do not observe the new rate; only subsequent requests will.//Note though that, since each request repays (by waiting, if necessary) the cost of the previous request, //this means that the very next request after an invocation to setRate() will not be affected by the new rate; //it will pay the cost of the previous request, which is in terms of the previous rate.//The behavior of the RateLimiter is not modified in any other way, //e.g. if the RateLimiter was configured with a warmup period of 20 seconds, //it still has a warmup period of 20 seconds after this method invocation.//更新该RateLimiter的稳定速率即在构造RateLimiter的工厂方法中提供permitsPerSecond参数//当前被限流的线程将不会由于这个调用而被唤醒因此它们没有观察到新的速率只有随后的请求才会//但是要注意的是由于每个请求(如果需要通过等待)会偿还先前请求的成本//这意味着调用setRate()方法后的下一个请求将不会受到新速率的影响//它将按照先前的速率处理先前请求的成本//RateLimiter的行为不会以任何其他方式修改//例如如果RateLimiter被配置为具有20秒的预热周期在该方法调用之后它仍然有20秒的预热期//param permitsPerSecond the new stable rate of this {code RateLimiter}public final void setRate(double permitsPerSecond) {checkArgument(permitsPerSecond 0.0 !Double.isNaN(permitsPerSecond), rate must be positive);//在同步代码块中设定速率synchronized (mutex()) {//调用SmoothRateLimiter.doSetRate()方法doSetRate(permitsPerSecond, stopwatch.readMicros());}}...
}GwtIncompatible
abstract class SmoothRateLimiter extends RateLimiter {//The currently stored permits. //令牌桶中当前缓存的未消耗的令牌数double storedPermits;//The maximum number of stored permits. //令牌桶中允许存放的最大令牌数double maxPermits;//The interval between two unit requests, at our stable rate.//E.g., a stable rate of 5 permits per second has a stable interval of 200ms.//按照我们稳定的速率两个单位请求之间的时间间隔例如每秒5个令牌的稳定速率具有200ms的稳定间隔double stableIntervalMicros;//The time when the next request (no matter its size) will be granted. //After granting a request, this is pushed further in the future. Large requests push this further than small requests.//下一个请求(无论大小)将被批准的时间.//在批准请求后这将在未来进一步推进大请求比小请求更能推动这一进程。private long nextFreeTicketMicros 0L;//could be either in the past or future...//这是一个可以重复调用的函数.//第一次调用和非第一次调用的过程有些不一样目的是设定设定最大令牌数maxPermits和已存储的令牌数storedPermitsOverridefinal void doSetRate(double permitsPerSecond, long nowMicros) {//调用SmoothRateLimiter.resync()方法重试计算和同步存储的预分配的令牌.resync(nowMicros);//计算稳定的发放令牌的时间间隔. 单位us, 比如qps为5, 则为200ms即20万us的间隔进行令牌发放. double stableIntervalMicros SECONDS.toMicros(1L) / permitsPerSecond;this.stableIntervalMicros stableIntervalMicros;//调用SmoothBursty.doSetRate()设定最大令牌数maxPermits和已存储的令牌数storedPermitsdoSetRate(permitsPerSecond, stableIntervalMicros);}//Updates storedPermits and nextFreeTicketMicros based on the current time.//根据当前时间更新storedPermits和nextFreeTicketMicros变量//注意: 在初始化SmoothBursty时会第一次调用resync()方法此时各值的情况如下//coolDownIntervalMicros 0、nextFreeTicketMicros 0、newPermits 无穷大.//maxPermits 0(初始值还没有重新计算)、最后得到的: storedPermits 0;//同时nextFreeTicketMicros 起始时间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;}}abstract void doSetRate(double permitsPerSecond, double stableIntervalMicros);...//This implements a bursty RateLimiter, where storedPermits are translated to zero throttling.//The maximum number of permits that can be saved (when the RateLimiter is unused) is defined in terms of time, //in this sense: if a RateLimiter is 2qps, and this time is specified as 10 seconds, we can save up to 2 * 10 20 permits.//SmoothBursty实现了一个突发式的速率限制器RateLimiter其中的storedPermits会被转换为0//它可以保存的最大令牌数量(当RateLimiter未使用时)是根据时间定义的//从这个意义上说如果RateLimiter是2qps并且这个时间被指定为10秒那么我们最多可以保存2*1020个令牌static final class SmoothBursty extends SmoothRateLimiter {//The work (permits) of how many seconds can be saved up if this RateLimiter is unused?//如果这个速率限制器RateLimiter没有被使用那么可以节省多少秒的工作(令牌)final double maxBurstSeconds;SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {super(stopwatch);this.maxBurstSeconds maxBurstSeconds;}Overridevoid doSetRate(double permitsPerSecond, double stableIntervalMicros) {//初次设定的时候oldMaxPermits 0.0double oldMaxPermits this.maxPermits;//新的(当前的)maxPermits为burst的时间周期(1秒) * 每周期的令牌数.maxPermits maxBurstSeconds * permitsPerSecond;if (oldMaxPermits Double.POSITIVE_INFINITY) {//if we dont special-case this, we would get storedPermits NaN, belowstoredPermits maxPermits;} else {//初始化SmoothBursty执行到此处时storedPermits为0storedPermits (oldMaxPermits 0.0) ? 0.0 : storedPermits * maxPermits / oldMaxPermits;}}Overridelong storedPermitsToWaitTime(double storedPermits, double permitsToTake) {return 0L;}Overridedouble coolDownIntervalMicros() {return stableIntervalMicros;}}...
}
二.SmoothBursty的acquire()方法 Beta
GwtIncompatible
SuppressWarnings(GoodTime)
public abstract class RateLimiter {...//无限等待的获取//Acquires the given number of permits from this RateLimiter, //blocking until the request can be granted. //Tells the amount of time slept, if any.//param permits the number of permits to acquire获取的令牌数量//return time spent sleeping to enforce rate, in seconds; 0.0 if not rate-limitedCanIgnoreReturnValuepublic double acquire(int permits) {//调用RateLimiter.reserve()方法//预支令牌并获取需要阻塞的时间即预定数量为permits的令牌数并返回需要等待的时间long microsToWait reserve(permits);//将需要等待的时间补齐, 从而满足限流的需求即根据microsToWait来让线程sleep(共性)stopwatch.sleepMicrosUninterruptibly(microsToWait);//返回这次调用使用了多少时间给调用者return 1.0 * microsToWait / SECONDS.toMicros(1L);}//Reserves the given number of permits from this RateLimiter for future use, //returning the number of microseconds until the reservation can be consumed.//从这个RateLimiter限速器中保留给定数量的令牌以备将来使用返回可以使用保留前的微秒数//return time in microseconds to wait until the resource can be acquired, never negativefinal long reserve(int permits) {checkPermits(permits);//由于涉及并发操作所以必须使用synchronized进行互斥处理synchronized (mutex()) {//调用RateLimiter.reserveAndGetWaitLength()方法return reserveAndGetWaitLength(permits, stopwatch.readMicros());}}//Reserves next ticket and returns the wait time that the caller must wait for.//预定下一个ticket并且返回需要等待的时间final long reserveAndGetWaitLength(int permits, long nowMicros) {//调用SmoothRateLimiter.reserveEarliestAvailable()方法long momentAvailable reserveEarliestAvailable(permits, nowMicros);return max(momentAvailable - nowMicros, 0);}//Reserves the requested number of permits and returns the time that those permits can be used (with one caveat).//保留请求数量的令牌并返回可以使用这些令牌的时间(有一个警告)//生产令牌、获取令牌、计算阻塞时间的具体细节由子类来实现//return the time that the permits may be used, or, if the permits may be used immediately, an arbitrary past or present timeabstract long reserveEarliestAvailable(int permits, long nowMicros);...
}GwtIncompatible
abstract class SmoothRateLimiter extends RateLimiter {//The currently stored permits. //令牌桶中当前缓存的未消耗的令牌数double storedPermits;//The maximum number of stored permits. //令牌桶中允许存放的最大令牌数double maxPermits;//The interval between two unit requests, at our stable rate.//E.g., a stable rate of 5 permits per second has a stable interval of 200ms.//按照我们稳定的速率两个单位请求之间的时间间隔例如每秒5个令牌的稳定速率具有200ms的稳定间隔double stableIntervalMicros;//The time when the next request (no matter its size) will be granted. //After granting a request, this is pushed further in the future. Large requests push this further than small requests.//下一个请求(无论大小)将被批准的时间. 在批准请求后这将在未来进一步推进大请求比小请求更能推动这一进程.private long nextFreeTicketMicros 0L;//could be either in the past or future ...Overridefinal long reserveEarliestAvailable(int requiredPermits, long nowMicros) {//1.根据nextFreeTicketMicros计算新产生的令牌数更新当前未使用的令牌数storedPermits//获取令牌时调用SmoothRateLimiter.resync()方法与初始化时的调用不一样.//此时会把还没有使用的令牌存储起来.//但是如果计数时间nextFreeTicketMicros是在未来. 那就不做任何处理.resync(nowMicros);//下一个请求(无论大小)将被批准的时间long returnValue nextFreeTicketMicros;//2.计算需要阻塞等待的时间//2.1.先从桶中取未消耗的令牌如果桶中令牌数不足看最多能取多少个//存储的令牌可供消费的数量double storedPermitsToSpend min(requiredPermits, this.storedPermits);//2.2.计算是否需要等待新鲜的令牌(当桶中现有的令牌数不足时就需要等待新鲜的令牌)如果需要则计算需要等待的令牌数//需要等待的令牌新鲜的令牌double freshPermits requiredPermits - storedPermitsToSpend;//计算需要等待的时间//分两部分计算waitMicros 从桶中获取storedPermitsToSpend个现有令牌的代价 等待生成freshPermits个新鲜令牌的代价//从桶中取storedPermitsToSpend个现有令牌也是有代价的storedPermitsToWaitTime()方法是个抽象方法会由SmoothBursty和SmoothWarmingUp实现//对于SmoothBursty来说storedPermitsToWaitTime()会返回0表示已经存储的令牌不需要等待.//而生成新鲜令牌需要等待的代价是新鲜令牌的个数freshPermits * 每个令牌的耗时stableIntervalMicroslong waitMicros storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) (long) (freshPermits * stableIntervalMicros);//3.更新nextFreeTicketMicros//由于新鲜的令牌可能已被预消费所以nextFreeTicketMicros就得往后移以表示这段时间被预消费了this.nextFreeTicketMicros LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);//4.扣减令牌数更新桶内剩余令牌//最后把上面计算的可扣减的令牌数量从存储的令牌里减掉this.storedPermits - storedPermitsToSpend;//返回请求需要等待的时间//需要注意returnValue被赋值的是上次的nextFreeTicketMicros说明当前这次请求获取令牌的代价由下一个请求去支付return returnValue;}//Updates storedPermits and nextFreeTicketMicros based on the current time.//根据当前时间更新storedPermits和nextFreeTicketMicros变量//计算nextFreeTicketMicros到当前时间内新产生的令牌数这个就是延迟计算void resync(long nowMicros) {//if nextFreeTicket is in the past, resync to now//一般当前的时间是大于下个请求被批准的时间//此时会把过去的时间换成令牌数存储起来注意存储的令牌数不能大于最大的令牌数//当RateLimiter初始化好后可能刚开始没有流量或者是一段时间没有流量后突然来了流量//此时可以往后预存储一秒时间的令牌数. 也就是这里所说的burst能力//如果nextFreeTicketMicros在未来的一个时间点那这个if判断便不满足//此时不需要进行更新storedPermits和nextFreeTicketMicros变量//此种情况发生在预借了令牌的时候if (nowMicros nextFreeTicketMicros) {//时间差除以生成一个新鲜令牌的耗时coolDownIntervalMicros()是抽象方法由子类实现double newPermits (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();//更新令牌桶内已存储的令牌个数注意不超过最大限制storedPermits min(maxPermits, storedPermits newPermits);//更新nextFreeTicketMicros为当前时间nextFreeTicketMicros nowMicros;}}//Translates a specified portion of our currently stored permits which we want to spend/acquire, into a throttling time.//Conceptually, this evaluates the integral of the underlying function we use, for the range of [(storedPermits - permitsToTake), storedPermits].//This always holds: 0 permitsToTake storedPermits//从桶中取出已存储的令牌的代价由子类实现//这是一个抽象函数SmoothBursty中的实现会直接返回0可以认为已经预分配的令牌在获取时不需要待待时间abstract long storedPermitsToWaitTime(double storedPermits, double permitsToTake);//Returns the number of microseconds during cool down that we have to wait to get a new permit.//每生成一个新鲜令牌的耗时由子类实现abstract double coolDownIntervalMicros();...static final class SmoothBursty extends SmoothRateLimiter {...Overridelong storedPermitsToWaitTime(double storedPermits, double permitsToTake) {return 0L;}Overridedouble coolDownIntervalMicros() {return stableIntervalMicros;}}...
}
