顧名思義,計(jì)數(shù)器算法是指在一定的時(shí)間窗口內(nèi)允許的固定數(shù)量的請(qǐng)求.比如,2s內(nèi)允許10個(gè)請(qǐng)求,30s內(nèi)允許100個(gè)請(qǐng)求等等.如果設(shè)置的時(shí)間粒度越細(xì),那么相對(duì)而言限流就會(huì)越平滑,控制的粒度就會(huì)更細(xì).

場(chǎng)景分析

試想,如果設(shè)置的粒度比較粗會(huì)出現(xiàn)什么樣的問題呢?如下圖設(shè)置一個(gè) 1000/3s 的限流計(jì)數(shù)統(tǒng)計(jì).

圖中的限流策略為3s內(nèi)允許的最大請(qǐng)求量為1000,那么會(huì)出現(xiàn)2個(gè)極端:

極端情況1:

第1s請(qǐng)流量為10,
第2s請(qǐng)流量為10,
第3s請(qǐng)流量突然激增到980.這意味著在這一刻,有大量的請(qǐng)求蜂擁而至,假設(shè)服務(wù)每秒能處理的

上線為800/1s,但是此刻卻有超過這個(gè)量級(jí)的請(qǐng)求量,那么后果是不堪設(shè)想的.

極端情況2:

第1s請(qǐng)流量突然就達(dá)到990,
留給后續(xù)第2s,3s的可請(qǐng)求數(shù)量就非常少了,可能會(huì)出現(xiàn)大量的拒絕請(qǐng)求.

結(jié)論:

如果用統(tǒng)計(jì)計(jì)數(shù)算法,盡量保持粒度切割精細(xì).

算法實(shí)現(xiàn)

redis的ttl特性完美的滿足了這一需求,將時(shí)間窗口設(shè)置為key的失效時(shí)間,然后將key的值每次請(qǐng)求+1即可.偽代碼實(shí)現(xiàn)思路:

//1.判斷是否存在該key
if(EXIT(key)){
  // 1.1自增后判斷是否大于最大值,并返回結(jié)果
  if(INCR(key) > maxPermit){
     return false;
  }
 return true;
}
//2.不存在key,則設(shè)置key初始值為1,失效時(shí)間為3秒
SET(KEY,1);
EXPIRE(KEY,3);

漏銅算法

漏桶算法核心概念：

桶的容量是固定的,并且水流以一個(gè)固定的速率流出；
流入的水流可以是任意速率；
如果流入的水流超出了桶的容量，則后續(xù)流入的水流溢出(請(qǐng)求被丟棄)。
如果桶內(nèi)沒有水,則不需要流出

缺點(diǎn):

不難想象漏桶算法并不能很好的應(yīng)對(duì)突發(fā)的流量限制,在某一個(gè)時(shí)間段流量激增,則漏桶算法處理就比較無能為力.這個(gè)時(shí)候就需要用到和他相反設(shè)計(jì)的令牌桶算法

令牌桶算法:

如上圖所示,整個(gè)請(qǐng)求流程一目了然.簡單概括如下:

1.用戶請(qǐng)求資源時(shí)首選從桶里獲取令牌,如果有令牌則放行,如此同時(shí)桶里的令牌數(shù)量-1

2.于此同時(shí),以一定的速率往桶里加入令牌,這個(gè)速度是可根據(jù)實(shí)際場(chǎng)景隨意設(shè)置.

算法實(shí)現(xiàn)

var key;
var maxPermit;//桶的容量,即最大請(qǐng)求限制
var expire;//失效時(shí)間
var bucketInterval;//每次向桶里添加令牌的時(shí)間間隔
var bucketNum;//每次向桶里添加令牌的個(gè)數(shù)
var lastTimeKey = key +"last";//標(biāo)記上一次操作時(shí)間
//判斷是否存在該key
if(EXIT(key)){
  var value = GET(key);
  var diffTime = now() - lastTimeKey;
  // 1.1判斷是否超出時(shí)間間隔
  if(diffTime  > bucketInterval){
      // 1.2根據(jù)時(shí)間間隔,計(jì)算出應(yīng)該向桶里添加令牌的個(gè)數(shù)
      local maxValue = value+math.floor(diff/interval)*step;
      if (maxValue > limit)
         value = limit;
      else
         value = maxValue;
     //設(shè)置key的值及操作時(shí)間
     SET(key,value);
     SET(lastTimeKey,now());     
  }
  // 2.1在時(shí)間間隔內(nèi),判斷桶里是否有值
  if(value <= 0){
     reurn false;
  }else{
    // 2.2 減1
    DECR(key);
  }
reture true;
}
//2.不存在key,則設(shè)置key初始值為maxPermit-1
SET(key,maxPermit-1);
EXPIRE(lastTimeKey,now());

上面實(shí)現(xiàn)代碼只是偽代碼,提供的是一種思路而已. 仔細(xì)想來其中某個(gè)環(huán)節(jié)其實(shí)并不完美.大家可以參考Guava的ratelimit實(shí)現(xiàn)思路,他的限流就是基于令牌桶算法,但是比較遺憾的是在單機(jī)下的限流.

思考:

就是時(shí)間間隔如果過長的話,一次性向桶里添加的令牌數(shù)量則是桶的最大容量!那么某個(gè)時(shí)間的瞬間請(qǐng)求過來,服務(wù)器的壓力是非常大的.

所以此處增加令牌數(shù)可以設(shè)置的稍微合理些,哪怕間隔時(shí)間再長!

以上就是redis lua限流算法實(shí)現(xiàn)示例的詳細(xì)內(nèi)容，更多關(guān)于redis lua限流算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: