摘要：接口限流的常用算法計(jì)數(shù)器法計(jì)數(shù)器法是限流算法里最簡(jiǎn)單也是最容易實(shí)現(xiàn)的一種算法。由此可見(jiàn)，當(dāng)滑動(dòng)窗口的格子劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會(huì)越精確。漏桶算法漏桶算法，又稱(chēng)。

什么是接口限流

那么什么是限流呢？顧名思義，限流就是限制流量，包括并發(fā)的流量和一定時(shí)間內(nèi)的總流量，就像你寬帶包了1個(gè)G的流量，用完了就沒(méi)了，所以控制你的使用頻率和單次使用的總消耗。通過(guò)限流，我們可以很好地控制系統(tǒng)的qps，從而達(dá)到保護(hù)系統(tǒng)或者接口服務(wù)器穩(wěn)定的目的。

接口限流的常用算法

計(jì)數(shù)器法

計(jì) 數(shù)器法是限流算法里最簡(jiǎn)單也是最容易實(shí)現(xiàn)的一種算法。比如我們規(guī)定，對(duì)于A接口來(lái)說(shuō)，我們1分鐘的訪問(wèn)次數(shù)不能超過(guò)100個(gè)。那么我們可以這么做：在一開(kāi) 始的時(shí)候，我們可以設(shè)置一個(gè)計(jì)數(shù)器counter，每當(dāng)一個(gè)請(qǐng)求過(guò)來(lái)的時(shí)候，counter就加1，如果counter的值大于100并且該請(qǐng)求與第一個(gè) 請(qǐng)求的間隔時(shí)間還在1分鐘之內(nèi)，那么說(shuō)明請(qǐng)求數(shù)過(guò)多；如果該請(qǐng)求與第一個(gè)請(qǐng)求的間隔時(shí)間大于1分鐘，且counter的值還在限流范圍內(nèi)，那么就重置 counter，具體算法的示意圖如下：

偽代碼如下

class CounterDemo{

    private  $timeStamp;
    public  $reqCount=0;
    public  $limit=100;//時(shí)間窗口內(nèi)最大請(qǐng)求數(shù)
    public $interval=1000; //時(shí)間窗口 ms


    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        if($now<$this->timeStamp+$this->interval){
            //時(shí)間窗口內(nèi)
            $this->reqCount++;
            return $this->reqCount<=$this->limit;
        }else{
            // 超時(shí)后重置
            $this->timeStamp=time();
            $this->reqCount=1;
            return true;
        }

    }

}

這個(gè)算法看起來(lái)簡(jiǎn)單但是有個(gè)很?chē)?yán)重的問(wèn)題,那就是臨界問(wèn)題，看下圖

從上圖中我們可以看到，假設(shè)有一個(gè)惡意用戶(hù)，他在0:59時(shí)，瞬間發(fā)送了100個(gè)請(qǐng)求，并且1:00又瞬間發(fā)送了100個(gè)請(qǐng)求，那么其實(shí)這個(gè)用戶(hù)在 1秒里面，瞬間發(fā)送了200個(gè)請(qǐng)求。我們剛才規(guī)定的是1分鐘最多100個(gè)請(qǐng)求，也就是每秒鐘最多1.7個(gè)請(qǐng)求，用戶(hù)通過(guò)在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請(qǐng)求， 可以瞬間超過(guò)我們的速率限制。用戶(hù)有可能通過(guò)算法的這個(gè)漏洞，瞬間壓垮我們的應(yīng)用。

聰明的朋友可能已經(jīng)看出來(lái)了，剛才的問(wèn)題其實(shí)是因?yàn)槲覀兘y(tǒng)計(jì)的精度太低。那么如何很好地處理這個(gè)問(wèn)題呢？或者說(shuō)，如何將臨界問(wèn)題的影響降低呢？我們可以看下面的滑動(dòng)窗口算法。

滑動(dòng)窗口算法
直接上圖吧

在上圖中，整個(gè)紅色的矩形框表示一個(gè)時(shí)間窗口，在我們的例子中，一個(gè)時(shí)間窗口就是一分鐘。然后我們將時(shí)間窗口進(jìn)行劃分，比如圖中，我們就將滑動(dòng)窗口 劃成了6格，所以每格代表的是10秒鐘。每過(guò)10秒鐘，我們的時(shí)間窗口就會(huì)往右滑動(dòng)一格。每一個(gè)格子都有自己獨(dú)立的計(jì)數(shù)器counter，比如當(dāng)一個(gè)請(qǐng)求 在0:35秒的時(shí)候到達(dá)，那么0:30~0:39對(duì)應(yīng)的counter就會(huì)加1。

那么滑動(dòng)窗口怎么解決剛才的臨界問(wèn)題的呢？我們可以看上圖，0:59到達(dá)的100個(gè)請(qǐng)求會(huì)落在灰色的格子中，而1:00到達(dá)的請(qǐng)求會(huì)落在橘黃色的格 子中。當(dāng)時(shí)間到達(dá)1:00時(shí)，我們的窗口會(huì)往右移動(dòng)一格，那么此時(shí)時(shí)間窗口內(nèi)的總請(qǐng)求數(shù)量一共是200個(gè)，超過(guò)了限定的100個(gè)，所以此時(shí)能夠檢測(cè)出來(lái)觸 發(fā)了限流。

我再來(lái)回顧一下剛才的計(jì)數(shù)器算法，我們可以發(fā)現(xiàn)，計(jì)數(shù)器算法其實(shí)就是滑動(dòng)窗口算法。只是它沒(méi)有對(duì)時(shí)間窗口做進(jìn)一步地劃分，所以只有1格。
由此可見(jiàn)，當(dāng)滑動(dòng)窗口的格子劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會(huì)越精確。

漏桶算法
漏桶算法，又稱(chēng)leaky bucket。為了理解漏桶算法，我們看一下維基百科上的對(duì)于該算法的示意圖：

從圖中我們可以看到，整個(gè)算法其實(shí)十分簡(jiǎn)單。首先，我們有一個(gè)固定容量的桶，有水流進(jìn)來(lái)，也有水流出 去。對(duì)于流進(jìn)來(lái)的水來(lái)說(shuō)，我們無(wú)法預(yù)計(jì)一共有多 少水會(huì)流進(jìn)來(lái)，也無(wú)法預(yù)計(jì)水流的速度。但是對(duì)于流出去的水來(lái)說(shuō)，這個(gè)桶可以固定水流出的速率。而且，當(dāng)桶滿(mǎn)了之后，多余的水將會(huì)溢出。

我們將算法中的水換成實(shí)際應(yīng)用中的請(qǐng)求，我們可以看到漏桶算法天生就限制了請(qǐng)求的速度。當(dāng)使用了漏桶算法，我們可以保證接口會(huì)以一個(gè)常速速率來(lái)處理請(qǐng)求。所以漏桶算法天生不會(huì)出現(xiàn)臨界問(wèn)題。具體的偽代碼實(shí)現(xiàn)如下：

class LeakyDemo{

    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 水漏出的速度
    public  $water;// 當(dāng)前水量(當(dāng)前累積請(qǐng)求數(shù))


    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->water=max(0,$this->water-($now-$this->timeStamp)*$this->rate);// 先執(zhí)行漏水，計(jì)算剩余水量
        $this->timeStamp=$now;
        if(($this->water+1)<$this->capacity){
            // 嘗試加水,并且水還未滿(mǎn)
            $this->water+=1;
            return true;
        }else{
            // 水滿(mǎn)，拒絕加水
            return false;
        }

    }

}

令牌桶算法
令牌桶算法，又稱(chēng)token bucket。為了理解該算法，我們?cè)賮?lái)看一下維基百科上對(duì)該算法的示意圖：

從圖中我們可以看到，令牌桶算法比漏桶算法稍顯復(fù)雜。首先，我們有一個(gè)固定容量的桶，桶里存放著令牌（token）。桶一開(kāi)始是空的，token以 一個(gè)固定的速率r往桶里填充，直到達(dá)到桶的容量，多余的令牌將會(huì)被丟棄。每當(dāng)一個(gè)請(qǐng)求過(guò)來(lái)時(shí)，就會(huì)嘗試從桶里移除一個(gè)令牌，如果沒(méi)有令牌的話，請(qǐng)求無(wú)法通 過(guò)。

具體的偽代碼實(shí)現(xiàn)如下：

class TokenBucketDemo{
    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 令牌放入的速度
    public  $tokens;// 當(dāng)前令牌的數(shù)量


    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->tokens=min(0,$this->tokens+($now-$this->timeStamp)*$this->rate);// 先執(zhí)行漏水，計(jì)算剩余水量
        $this->timeStamp=$now;
        if($this->tokens<1){
            // 若不到1個(gè)令牌,則拒絕
            return false;
        }else{
            // 還有令牌，領(lǐng)取令牌
            $this->tokens -= 1;
            return true;
        }

    }

}

臨界問(wèn)題
臨界問(wèn)題

我們?cè)賮?lái)考慮一下臨界問(wèn)題的場(chǎng)景。在0:59秒的時(shí)候，由于桶內(nèi)積滿(mǎn)了100個(gè)token，所以這100個(gè)請(qǐng)求可以瞬間通過(guò)。但是由于token是以較低的 速率填充的，所以在1:00的時(shí)候，桶內(nèi)的token數(shù)量不可能達(dá)到100個(gè)，那么此時(shí)不可能再有100個(gè)請(qǐng)求通過(guò)。所以令牌桶算法可以很好地解決臨界問(wèn) 題。下圖比較了計(jì)數(shù)器（左）和令牌桶算法（右）在臨界點(diǎn)的速率變化。我們可以看到雖然令牌桶算法允許突發(fā)速率，但是下一個(gè)突發(fā)速率必須要等桶內(nèi)有足夠的 token后才能發(fā)生

總結(jié)
計(jì)數(shù)器算法是最簡(jiǎn)單的算法，可以看成是滑動(dòng)窗口的低精度實(shí)現(xiàn)?；瑒?dòng)窗口由于需要存儲(chǔ)多份的計(jì)數(shù)器（每一個(gè)格子存一份），所以滑動(dòng)窗口在實(shí)現(xiàn)上需要更多的存儲(chǔ)空間。也就是說(shuō)，如果滑動(dòng)窗口的精度越高，需要的存儲(chǔ)空間就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明顯的區(qū)別是令牌桶算法允許流量一定程度的突發(fā)。因?yàn)槟J(rèn)的令牌桶算法，取走token是不需要耗費(fèi)時(shí)間的，也就是說(shuō)，假設(shè)桶內(nèi)有100個(gè)token時(shí)，那么可以瞬間允許100個(gè)請(qǐng)求通過(guò)。

令牌桶算法由于實(shí)現(xiàn)簡(jiǎn)單，且允許某些流量的突發(fā)，對(duì)用戶(hù)友好，所以被業(yè)界采用地較多。當(dāng)然我們需要具體情況具體分析，只有最合適的算法，沒(méi)有最優(yōu)的算法。