本文主要介绍几种常用的限流算法：计数器算法、漏桶算法、令牌桶算法。然后结合我对Sentinel1.8.0的理解，给大家分享一下Sentinel在源码中是如何使用这些算法进行流控判断的。计数器限流算法我们可以直接通过一个计数器来限制每秒可以接收的请求数。比如设置qps为1000，那么实现思路是从第一个请求开始计时。在接下来的1秒内，每有一个请求过来，计数就会加1，如果累计到1000，那么后面的请求都会被拒绝。1s结束后，将计数恢复为0，重新开始计数。优点：实现简单缺点：如果1秒的前半秒已经通过了1000个请求，那么只能在后半秒拒绝该请求。我们称这种现象为“尖峰现象”。实现代码示例：publicclassCounter{publiclongtimeStamp=getNowTime();publicintreqCount=0;publicfinalintlimit=100;//时间窗口内最大请求数publicfinallonginterval=1000;//时间窗口mspublicbooleanlimit(){longnow=getNowTime();if(now>MAP=newConcurrentHashMap<>();privateSlideWindow(){}publicstaticvoidmain(String[]args)throwsInterruptedException{while(true){//任意10秒内，只允许2次通过System.out.println(LocalTime.now().toString()+SlideWindow.isGo("ListId",2,10000L));//休眠0-10秒Thread.sleep(1000*newRandom().nextInt(10));}}/***滑动时间窗限流算法*在指定的时间窗内，在指定的限定次数内，是否允许通过**@paramlistIdqueueid*@paramcount限定次数*@paramtimeWindow时间窗大小*@returnis允许通过*/publicstaticsynchronizedbooleanisGo(StringlistId,intcount,longtimeWindow){//获取当前时间longnowTime=System.currentTimeMillis();//根据队列id，取出对应的限流队列，如果没有，创建一个Listlist=MAP.computeIfAbsent(listId,k->newLinkedList<>());//如果队列未满，则允许通过，并将当前时间戳添加到队列的开头if(list.size()currentWindow(longtimeMillis){if(timeMillis<0){returnnull;}intidx=calculateTimeIdx(timeMillis);//计算开始时间/bucketstarttime.窗户的，加州longwindowStart=calculateWindowStart(timeMillis);/**Getbucketitematgiventimefromthearray.**(1)Bucketisabsent,thenjustcreateanewbucketandCASupdatetocirculararray.*(2)Bucketisup-to-date,thenjustreturnthebucket.*(3)Bucketisdeprecated,然后resetcurrentbucketsandcleanalldeprecatedget(While=rap>owraywindow=newWindowWrap(windowLengthInMs,ifwindowStart,new(emptyBucket));(idx,null,window)){//成功更新,returnthecreatedbucket.returnwindow;}else{//竞争失败,thethreadwillyielditstimeslicetowaitforbucketavailable.Thread.yield();}//当前pane存在,返回历史pane}elseif(windowStart==old.windowStart()){/**B0B1B2B3B4*||______|_______|_______|_______|_______||___*20040060080010001200timestamp*^*time=888*startTimeofBucket3:800，所以它是最新的**Ifcurrent{@codewindowStart}等于开始时间戳桶，*thatmeansthetimeiswithinthebucket,sodirectlyreturnthebucket.*/returnold;//elseif(windowStart>old.windowStart()){/**（旧）*B0B1B2NULLB4*|_______||_______|_______|_______|_______|_______||___*...120014001600180020002200timestamp*^*time=1676*startTimeofBucket2:400,deprecated,shouldbereset**Ifthestarttimestampofoldbucketisbehindprovidedtime,thatmeans*thebucketisdeprecated.Wehavetoresetthebuckettocurrent{@codewindowStart}.*Notethattheresetandclean-upoperationsarehardtobeatomic,*soweneedaupdatelocktoguaranteethecorrectnessofbucketupdate.**Theupdatelockisconditional(tinyscope)andwilltakeeffectonlywhen*bucketisdeprecated,soinmostcasesitwon'tleadtoperformanceloss.*/if(updateLock.tryLock()){try{//Successfullygettheupdatelock,nowweresetthebucket.//清空所有的窗体数据returnresetWindowTo(old,windowStart);}finally{updateLock.unlock();}}else{//Contentionfailed,thethreadwillyielditstimeslicetowaitforbucketavailable.Thread.yield();}//如果时间回拨，重新创建时间格式}elseif(windowStart(windowLengthInMs,windowStart,newEmptyBucket(timeMillis));}}}漏桶算法一种常用的算法，其主要目的是控制数据注入网络的速率。平滑网络突发流量的漏桶算法提供了一种机制，可以对突发流量进行整形，为网络提供稳定的流量，执行过程如下图所示。实现代码示例：publicclassLeakyBucket{publiclongtimeStamp=System.currentTimeMillis();//当前时间publiclongcapacity;//桶容量publiclongrate;//漏水速度publiclongwater;//当前水量（当前累计请求数）publicbooleanggrant(){longnow=System.currentTimeMillis();//先执行漏水，计算剩余水量water=Math.max(0,water-(now-timeStamp)*rate);timeStamp=now;if((water+1)预计时间if(expectedTime<=currentTime){//Contentionmaybethere,butit'sokay.//可以通过，并设置最后一次通过时间latestPassedTime.set(currentTime);returntrue;}else{//Calculatethetimetowait.//waitingtime=expectedtime-lasttime-currenttimelongwaitTime=costTime+latestPassedTime.get()-TimeUtil.currentTimeMillis();//等待时间>最大排队时间if(waitTime>maxQueueingTimeMs){returnfalse;}else{//上次时间+间隔时间longoldTime=最新通过Time.addAndGet(costTime);try{//等待时间waitTime=oldTime-TimeUtil.currentTimeMillis();//等待时间>最大排队时间if(waitTime>maxQueueingTimeMs){latestPassedTime.addAndGet(-costTime);returnfalse;}//inraceconditionwaitTimemay<=0//休眠等待if(waitTime>0){Thread.sleep(waitTime);}//等待结束后释放returntrue;}catch(InterruptedExceptione){}}}returnfalse;}令牌桶算法顺序卡桶算法是网络流量整形（TrafficShaping）和速率限制（RateLimiting）中最常用的算法。通常，令牌桶算法用于控制发送到网络的数据数量并允许突发发送数据。如下图所示：简单的说，一侧请求时会消耗桶中的token，另一侧按固定比例将token放入桶中。当消耗的请求大于输入速率时，采取相应的措施，如等待或拒绝。实现代码示例：publicclassTokenBucket{publiclongtimeStamp=System.currentTimeMillis();//当前时间publiclongcapacity;//桶容量publiclongrate;//token插入速度publiclongtokens;//当前token数量publicbooleanggrant(){longnow=System.currentTimeMillis();//先添加tokenstokens=Math.min(capacity,tokens+(now-timeStamp)*rate);timeStamp=now;if(tokens<1){//如果少于1个token，则Rejectreturnfalse;}else{//有令牌，接收令牌tokens-=1;returntrue;}}}Sentinel在WarmUpController中使用令牌桶算法，这里可以实现系统的预热，设置预热为加热时间和水level，预热期间多余的请求直接拒绝。publicbooleancanPass(Nodenode,intacquireCount,booleanprioritized){longpassQps=(long)node.passQps();longpreviousQps=(long)node.previousPassQps();syncToken(previousQps);//开始计算它的斜率//如果它进入warningline,开始调整他的qpslongestToken=storedTokens.get();if(restToken>=warningToken){longaboveToken=restToken-warningToken;//消费速度比warning快，但是比//currentinterval=restToken*slope慢+1/countdoublewarningQps=Math.nextUp(1.0/(aboveToken*slope+1.0/count));if(passQps+acquireCount<=warningQps){returntrue;}}else{if(passQps+acquireCount<=count){returntrue;}}returnfalse;}限流算法总结CounterVSTimeWindow时间窗算法的本质也是通过counter算法实现的。时间窗算法划分的格子越多，滑动窗口的滚动越流畅，限流统计越准确，但也会占用更多的内存。LeakyBucketVSTokenBucket漏桶算法和令牌桶算法本质上都是为了流量整形或者限速，避免系统因为大流量而崩溃，但是两者最核心的区别在于限流的方向相反。Bucket：限制流量的流出速率，相对固定。令牌桶：限制流量的平均流入速率，允许一定程度的突发流量。最大速率是桶的容量和令牌生成速率。在某些场景下，漏桶算法不能有效利用网络资源，因为漏桶的泄漏率是相对固定的，所以当网络状况良好且没有拥塞时，漏桶仍然会受到限制。量不能释放，网络资源不能有效利用。令牌桶算法不同。它支持一定程度的突发流量，同时限制平均速率。参考文档https://www.cnblogs.com/linjiqin/p/9707713.htmlhttps://www.cnblogs.com/dijia478/p/13807826.html
