原文:Sentinel 万字教程
限流作为现在微服务中常见的稳定性措施,在面试中肯定也是经常会被问到的,我在面试的时候也经常喜欢问一下你对限流算法知道哪一些?有看过源码吗?实现原理是什么?
第一部分先讲讲限流算法,最后再讲讲源码的实现原理。
限流算法
关于限流的算法大体上可以分为四类:固定窗口计数器、滑动窗口计数器、漏桶(也有称漏斗,英文Leaky bucket)、令牌桶(英文Token bucket)。
固定窗口
固定窗口,相比其他的限流算法,这应该是最简单的一种。
它简单地对一个固定的时间窗口内的请求数量进行计数,如果超过请求数量的阈值,将被直接丢弃。
这个简单的限流算法优缺点都很明显。优点的话就是简单,缺点举个例子来说。
比如我们下图中的黄色区域就是固定时间窗口,默认时间范围是60s,限流数量是100。
如图中括号内所示,前面一段时间都没有流量,刚好后面30秒内来了100个请求,此时因为没有超过限流阈值,所以请求全部通过,然后下一个窗口的20秒内同样通过了100个请求。
所以变相的相当于在这个括号的40秒的时间内就通过了200个请求,超过了我们限流的阈值。
滑动窗口
为了优化这个问题,于是有了滑动窗口算法,顾名思义,滑动窗口就是时间窗口在随着时间推移不停地移动。
滑动窗口把一个固定时间窗口再继续拆分成N个小窗口,然后对每个小窗口分别进行计数,所有小窗口请求之和不能超过我们设定的限流阈值。
以下图举例子来说,假设我们的窗口拆分成了3个小窗口,小窗口都是20s,同样基于上面的例子,当在第三个20s的时候来了100个请求,可以通过。
然后时间窗口滑动,下一个20s请求又来了100个请求,此时我们滑动窗口的60s范围内请求数量肯定就超过100了啊,所以请求被拒绝。
漏桶Leaky bucket
漏桶算法,人如其名,他就是一个漏的桶,不管请求的数量有多少,最终都会以固定的出口流量大小匀速流出,如果请求的流量超过漏桶大小,那么超出的流量将会被丢弃。
也就是说流量流入的速度是不定的,但是流出的速度是恒定的。
这个和MQ削峰填谷的思想比较类似,在面对突然激增的流量的时候,通过漏桶算法可以做到匀速排队,固定速度限流。
漏桶算法的优势是匀速,匀速是优点也是缺点,很多人说漏桶不能处理突增流量,这个说法并不准确。
漏桶本来就应该是为了处理间歇性的突增流量,流量一下起来了,然后系统处理不过来,可以在空闲的时候去处理,防止了突增流量导致系统崩溃,保护了系统的稳定性。
但是,换一个思路来想,其实这些突增的流量对于系统来说完全没有压力,你还在慢慢地匀速排队,其实是对系统性能的浪费。
所以,对于这种有场景来说,令牌桶算法比漏桶就更有优势。
令牌桶token bucket
令牌桶算法是指系统以一定地速度往令牌桶里丢令牌,当一个请求过来的时候,会去令牌桶里申请一个令牌,如果能够获取到令牌,那么请求就可以正常进行,反之被丢弃。
现在的令牌桶算法,像Guava和Sentinel的实现都有冷启动/预热的方式,为了避免在流量激增的同时把系统打挂,令牌桶算法会在最开始一段时间内冷启动 ,随着流量的增加,系统会根据流量大小动态地调整生成令牌的速度,最终直到请求达到系统的阈值。
源码举例
我们以sentinel举例,sentinel中统计用到了滑动窗口算法,然后也有用到漏桶、令牌桶算法。
滑动窗口
sentinel
中就使用到了滑动窗口算法来进行统计,不过他的实现和我上面画的图有点不一样,实际上sentinel中的滑动窗口用一个圆形来描述更合理一点。
前期就是创建节点,然后slot串起来就是一个责任链模式,StatisticSlot通过滑动窗口来统计数据,FlowSlot是真正限流的逻辑,还有一些降级、系统保护的措施,最终形成了整个sentinel的限流方式。
就看看官方图吧,这圆形画起来好恶心
滑动窗口的实现主要可以看LeapArray
的代码,默认的话定义了时间窗口的相关参数。
对于sentinel来说其实窗口分为秒 和分钟 两个级别,秒的话窗口数量是2,分钟则是60个窗口,每个窗口的时间长度是1s,总的时间周期就是60s,分成60个窗口,这里我们就以分钟级别的统计来说。
1 2 3 4 5 6 7 8 9 10 11 public abstract class LeapArray <T > { protected int windowLengthInMs; protected int sampleCount; protected int intervalInMs; private double intervalInSecond; protected final AtomicReferenceArray<WindowWrap<T>> array;
然后我们要看的就是它是怎么计算出当前窗口的,其实源码里写的听清楚的,但是如果你按照之前想象把他当做一条直线延伸去想的话估计不太好理解。
首先计算数组索引下标和时间窗口时间这个都比较简单,难点应该大部分在于第三点窗口大于old这个是什么鬼,详细说下这几种情况。
数组中的时间窗口是是空的,这个说明时间走到了我们初始化的时间之后了,此时new一个新的窗口通过CAS的方式去更新,然后返回这个新的窗口就好了。
第二种情况是刚好时间窗口的时间相等,那么直接返回,没啥好说的
第三种情况就是比较难以理解的,可以参看两条时间线的图,就比较好理解了,第一次时间窗口走完了达到1200,然后圆形时间窗口开始循环,新的时间起始位置还是1200,然后时间窗口的时间来到1676,B2的位置如果还是老的窗口那么就是600,所以我们要重置之前的时间窗口的时间为当前的时间。
最后一种一般情况不太可能发生,除非时钟回拨这样子
从这个我们可以发现就是针对每个WindowWrap
时间窗口都进行了统计,最后实际上在后面的几个地方都会用到时间窗口统计的QPS结果,这里就不再赘述了,知道即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 private int calculateTimeIdx ( long timeMillis) { long timeId = timeMillis / windowLengthInMs; return (int ) (timeId % array.length()); } protected long calculateWindowStart ( long timeMillis) { return timeMillis - timeMillis % windowLengthInMs; } public WindowWrap<T> currentWindow (long timeMillis) { if (timeMillis < 0 ) { return null ; } int idx = calculateTimeIdx(timeMillis); long windowStart = calculateWindowStart(timeMillis); while (true ) { WindowWrap<T> old = array.get(idx); if (old == null ) { WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); if (array.compareAndSet(idx, null , window)) { return window; } else { Thread.yield(); } } else if (windowStart == old.windowStart()) { return old; } else if (windowStart > old.windowStart()) { if (updateLock.tryLock()) { try { return resetWindowTo(old, windowStart); } finally { updateLock.unlock(); } } else { Thread.yield(); } } else if (windowStart < old.windowStart()) { return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); } } }
漏桶
sentinel主要根据FlowSlot
中的流控进行流量控制,其中RateLimiterController
就是漏桶算法的实现,这个实现相比其他几个还是简单多了,稍微看一下应该就明白了。
首先计算出当前请求平摊到1s内的时间花费,然后去计算这一次请求预计时间
如果小于当前时间的话,那么以当前时间为主,返回即可
反之如果超过当前时间的话,这时候就要进行排队等待了,等待的时候要判断是否超过当前最大的等待时间,超过就直接丢弃
没有超过就更新上一次的通过时间,然后再比较一次是否超时,还超时就重置时间,反之在等待时间范围之内的话就等待,如果都不是那就可以通过了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 public class RateLimiterController implements TrafficShapingController { private final int maxQueueingTimeMs; private final double count; private final AtomicLong latestPassedTime = new AtomicLong(-1 ); @Override public boolean canPass (Node node, int acquireCount, boolean prioritized) { if (acquireCount <= 0 ) { return true ; } if (count <= 0 ) { return false ; } long currentTime = TimeUtil.currentTimeMillis(); long costTime = Math.round(1.0 * (acquireCount) / count * 1000 ); long expectedTime = costTime + latestPassedTime.get(); if (expectedTime <= currentTime) { latestPassedTime.set(currentTime); return true ; } else { long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis(); if (waitTime > maxQueueingTimeMs) { return false ; } else { long oldTime = latestPassedTime.addAndGet(costTime); try { waitTime = oldTime - TimeUtil.currentTimeMillis(); if (waitTime > maxQueueingTimeMs) { latestPassedTime.addAndGet(-costTime); return false ; } if (waitTime > 0 ) { Thread.sleep(waitTime); } return true ; } catch (InterruptedException e) { } } } return false ; } }
令牌桶
最后是令牌桶,这个不在于实现的复制,而是你看源码会发现都算的些啥玩意儿。。。sentinel的令牌桶实现基于Guava,代码在WarmUpController
中。
这个算法那些各种计算逻辑其实我们可以不管(因为我也没看懂。。),但是流程上我们是清晰的就可以了。
几个核心的参数看注释,构造方法里那些计算逻辑暂时不管他是怎么算的(我也没整明白,但是不影响我们理解),关键看canPass
是怎么做的。
拿到当前窗口和上一个窗口的QPS
填充令牌,也就是往桶里丢令牌,然后我们先看填充令牌的逻辑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 public class WarmUpController implements TrafficShapingController { protected double count; private int coldFactor; protected int warningToken = 0 ; private int maxToken; protected double slope; protected AtomicLong storedTokens = new AtomicLong(0 ); protected AtomicLong lastFilledTime = new AtomicLong(0 ); public WarmUpController (double count, int warmUpPeriodInSec, int coldFactor) { construct(count, warmUpPeriodInSec, coldFactor); } public WarmUpController (double count, int warmUpPeriodInSec) { construct(count, warmUpPeriodInSec, 3 ); } private void construct (double count, int warmUpPeriodInSec, int coldFactor) { if (coldFactor <= 1 ) { throw new IllegalArgumentException("Cold factor should be larger than 1" ); } this .count = count; this .coldFactor = coldFactor; warningToken = (int )(warmUpPeriodInSec * count) / (coldFactor - 1 ); maxToken = warningToken + (int )(2 * warmUpPeriodInSec * count / (1.0 + coldFactor)); slope = (coldFactor - 1.0 ) / count / (maxToken - warningToken); } @Override public boolean canPass (Node node, int acquireCount, boolean prioritized) { long passQps = (long ) node.passQps(); long previousQps = (long ) node.previousPassQps(); syncToken(previousQps); long restToken = storedTokens.get(); if (restToken >= warningToken) { long aboveToken = restToken - warningToken; double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); if (passQps + acquireCount <= warningQps) { return true ; } } else { if (passQps + acquireCount <= count) { return true ; } } return false ; } }
填充令牌的逻辑如下:
拿到当前的时间,然后去掉毫秒数,得到的就是秒级时间
判断时间小于这里就是为了控制每秒丢一次令牌
然后就是coolDownTokens
去计算我们的冷启动/预热是怎么计算填充令牌的
后面计算当前剩下的令牌数这个就不说了,减去上一次消耗的就是桶里剩下的令牌
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 protected void syncToken (long passQps) { long currentTime = TimeUtil.currentTimeMillis(); currentTime = currentTime - currentTime % 1000 ; long oldLastFillTime = lastFilledTime.get(); if (currentTime <= oldLastFillTime) { return ; } long oldValue = storedTokens.get(); long newValue = coolDownTokens(currentTime, passQps); if (storedTokens.compareAndSet(oldValue, newValue)) { long currentValue = storedTokens.addAndGet(0 - passQps); if (currentValue < 0 ) { storedTokens.set(0L ); } lastFilledTime.set(currentTime); } }
最开始的事实因为lastFilledTime
和oldValue
都是0,所以根据当前时间戳会得到一个非常大的数字,最后和maxToken
取小的话就得到了最大的令牌数,所以第一次初始化的时候就会生成maxToken
的令牌
之后我们假设系统的QPS一开始很低,然后突然飙高。所以开始的时候回一直走到高于警戒线的逻辑里去,然后passQps
又很低,所以会一直处于把令牌桶填满的状态(currentTime - lastFilledTime.get()
会一直都是1000,也就是1秒),所以每次都会填充最大QPScount
数量的令牌
然后突增流量来了,QPS瞬间很高,慢慢地令牌数量就会消耗到警戒线之下,走到我们if
的逻辑里去,然后去按照count
数量增加令牌
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 private long coolDownTokens (long currentTime, long passQps) { long oldValue = storedTokens.get(); long newValue = oldValue; if (oldValue < warningToken) { newValue = (long )(oldValue + (currentTime - lastFilledTime.get()) * count / 1000 ); } else if (oldValue > warningToken) { if (passQps < (int )count / coldFactor) { newValue = (long )(oldValue + (currentTime - lastFilledTime.get()) * count / 1000 ); } } return Math.min(newValue, maxToken); }
上面的逻辑理顺之后,我们就可以继续看限流的部分逻辑:
令牌计算的逻辑完成,然后判断是不是超过警戒线,按照上面的说法,低QPS的状态肯定是一直超过的,所以会根据斜率来计算出一个warningQps
,因为我们处于冷启动的状态,所以这个阶段就是要根据斜率来计算出一个QPS数量,让流量慢慢地达到系统能承受的峰值。举个例子,如果count
是100,那么在QPS很低的情况下,令牌桶一直处于满状态,但是系统会控制QPS,实际通过的QPS就是warningQps
,根据算法可能只有10或者20(怎么算的不影响理解)。QPS主键提高的时候,aboveToken
再逐渐变小,整个warningQps
就在逐渐变大,直到走到警戒线之下,到了else
逻辑里。
流量突增的情况,就是else
逻辑里低于警戒线的情况,我们令牌桶在不停地根据count
去增加令牌,这时候消耗令牌的速度超过我们生成令牌的速度,可能就会导致一直处于警戒线之下,这时候判断当然就需要根据最高QPS去判断限流了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 long restToken = storedTokens.get();if (restToken >= warningToken) { long aboveToken = restToken - warningToken; double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); if (passQps + acquireCount <= warningQps) { return true ; } } else { if (passQps + acquireCount <= count) { return true ; } }
所以,按照低QPS到突增高QPS的流程,来想象一下这个过程:
刚开始,系统的QPS非常低,初始化我们就直接把令牌桶塞满了
然后这个低QPS的状态持续了一段时间,因为我们一直会填充最大QPS数量的令牌(因为取最小值,所以其实桶里令牌基本不会有变化),所以令牌桶一直处于满的状态,整个系统的限流也处于一个比较低的水平
这以上的部分一直处于警戒线之上,实际上就是叫做冷启动/预热的过程。
接着系统的QPS突然激增,令牌消耗速度太快,就算我们每次增加最大QPS数量的令牌任然无法维持消耗,所以桶里的令牌在不断低减少,这个时候,冷启动阶段的限制QPS也在不断地提高,最后直到桶里的令牌低于警戒线
低于警戒线之后,系统就会按照最高QPS去限流,这个过程就是系统在逐渐达到最高限流的过程
那这样一来,实际就达到了我们处理突增流量的目的,整个系统在漫漫地适应突然飙高的QPS,然后最终达到系统的QPS阈值。
最后,如果QPS回复正常,那么又会逐渐回到警戒线之上,就回到了最开始的过程。
总结
因为算法如果单独说的话都比较简单,一说大家都可以听明白,不需要几个字就能说明白,所以还是得弄点源码看看别人是怎么玩的,所以尽管我很讨厌放源码,但是还是不得不干。
光靠别人说一点其实有点看不明白,按照顺序读一遍的话心里就有数了。
那源码的话最难以理解的就是令牌桶的实现了,说实话那几个计算的逻辑我看了好几遍不知道他算的什么鬼,但是思想我们理解就行了,其他的逻辑相对来说就比较容易理解。