計(jì)數(shù)器

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

限流算法中最簡(jiǎn)單粗暴的一種算法，例如，某一個(gè)接口1分鐘內(nèi)的請(qǐng)求不超過(guò)60次，我們可以在開(kāi)始時(shí)設(shè)置一個(gè)計(jì)數(shù)器，每次請(qǐng)求時(shí)，這個(gè)計(jì)數(shù)器的值加1，如果這個(gè)這個(gè)計(jì)數(shù)器的值大于60并且與第一次請(qǐng)求的時(shí)間間隔在1分鐘之內(nèi)，那么說(shuō)明請(qǐng)求過(guò)多；如果該請(qǐng)求與第一次請(qǐng)求的時(shí)間間隔大于1分鐘，并且該計(jì)數(shù)器的值還在限流范圍內(nèi)，那么重置該計(jì)數(shù)器。

使用計(jì)數(shù)器還可以用來(lái)限制一定時(shí)間內(nèi)的總并發(fā)數(shù)，比如數(shù)據(jù)庫(kù)連接池、線程池、秒殺的并發(fā)數(shù)；計(jì)數(shù)器限流只要一定時(shí)間內(nèi)的總請(qǐng)求數(shù)超過(guò)設(shè)定的閥值則進(jìn)行限流，是一種簡(jiǎn)單粗暴的總數(shù)量限流，而不是平均速A                                  ,VCW率限流。

圖片

這個(gè)方法有一個(gè)致命問(wèn)題：臨界問(wèn)題——當(dāng)遇到惡意請(qǐng)求，在0:59時(shí)，瞬間請(qǐng)求100次，并且在1:00請(qǐng)求100次，那么這個(gè)用戶在1秒內(nèi)請(qǐng)求了200次，用戶可以在重置節(jié)點(diǎn)突發(fā)請(qǐng)求，而瞬間超過(guò)我們?cè)O(shè)置的速率限制，用戶可能通過(guò)算法漏洞擊垮我們的應(yīng)用。

圖片

這個(gè)問(wèn)題我們可以使用滑動(dòng)窗口解決。

滑動(dòng)窗口

圖片

在上圖中，整個(gè)紅色矩形框是一個(gè)時(shí)間窗口，在我們的例子中，一個(gè)時(shí)間窗口就是1分鐘，然后我們將時(shí)間窗口進(jìn)行劃分，如上圖我們把滑動(dòng)窗口劃分為6格，所以每一格代表10秒，每超過(guò)10秒，我們的時(shí)間窗口就會(huì)向右滑動(dòng)一格，每一格都有自己獨(dú)立的計(jì)數(shù)器。

例如：一個(gè)請(qǐng)求在0:35到達(dá)， 那么0:30到0:39的計(jì)數(shù)器會(huì)+1，那么滑動(dòng)窗口是怎么解決臨界點(diǎn)的問(wèn)題呢？如上圖，0:59到達(dá)的100個(gè)請(qǐng)求會(huì)在灰色區(qū)域格子中，而1：00到達(dá)的請(qǐng)求會(huì)在紅色格子中，窗口會(huì)向右滑動(dòng)一格，那么此時(shí)間窗口內(nèi)的總請(qǐng)求數(shù)共200個(gè)，超過(guò)了限定的100，所以此時(shí)能夠檢測(cè)出來(lái)觸發(fā)了限流。

回頭看看計(jì)數(shù)器算法，會(huì)發(fā)現(xiàn)，其實(shí)計(jì)數(shù)器算法就是窗口滑動(dòng)算法，只不過(guò)計(jì)數(shù)器算法沒(méi)有對(duì)時(shí)間窗口進(jìn)行劃分，所以是一格。

由此可見(jiàn)，當(dāng)滑動(dòng)窗口的格子劃分越多，限流的統(tǒng)計(jì)就會(huì)越精確。

漏桶算法

算法的思路就是水（請(qǐng)求）先進(jìn)入到漏桶里面，漏桶以恒定的速度流出，當(dāng)水流的速度過(guò)大就會(huì)直接溢出，可以看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率。如下圖所示。

圖片

漏桶算法不支持突發(fā)流量。

令牌桶算法

圖片

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

令牌桶算法支持突發(fā)流量。

令牌桶算法實(shí)現(xiàn)

Guava框架提供了令牌桶算法的實(shí)現(xiàn)，可直接使用這個(gè)框架的RateLimiter類創(chuàng)建一個(gè)令牌桶限流器，比如：每秒放置的令牌桶的數(shù)量為5，那么RateLimiter對(duì)象可以保證1秒內(nèi)不會(huì)放入超過(guò)5個(gè)令牌，并且以固定速率進(jìn)行放置令牌，達(dá)到平滑輸出的效果。

平滑流量示例

這里，我寫了一個(gè)使用Guava框架實(shí)現(xiàn)令牌桶算法的示例，如下所示。

package io.binghe.limit.guava;

import com.google.common.util.concurrent.RateLimiter;

/**
 * @author binghe
 * @version 1.0.0
 * @description 令牌桶算法
 */
publicclass TokenBucketLimiter {
    public static void main(String[] args){
        //每秒鐘生成5個(gè)令牌
        RateLimiter limiter = RateLimiter.create(5);

        //返回值表示從令牌桶中獲取一個(gè)令牌所花費(fèi)的時(shí)間，單位是秒
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
        System.out.println(limiter.acquire(1));
    }
}

代碼的實(shí)現(xiàn)非常簡(jiǎn)單，就是使用Guava框架的RateLimiter類生成了一個(gè)每秒向桶中放入5個(gè)令牌的對(duì)象，然后不斷從桶中獲取令牌。我們先來(lái)運(yùn)行下這段代碼，輸出的結(jié)果信息如下所示。

0.0
0.197294
0.191278
0.19997
0.199305
0.200472
0.200184
0.199417
0.200111
0.199759

從輸出結(jié)果可以看出：第一次從桶中獲取令牌時(shí)，返回的時(shí)間為0.0，也就是沒(méi)耗費(fèi)時(shí)間。之后每次從桶中獲取令牌時(shí)，都會(huì)耗費(fèi)一定的時(shí)間，這是為什么呢？按理說(shuō)，向桶中放入了5個(gè)令牌后，再?gòu)耐爸蝎@取令牌也應(yīng)該和第一次一樣并不會(huì)花費(fèi)時(shí)間啊！

因?yàn)樵贕uava的實(shí)現(xiàn)是這樣的：我們使用RateLimiter.create(5)創(chuàng)建令牌桶對(duì)象時(shí)，表示每秒新增5個(gè)令牌，1秒等于1000毫秒，也就是每隔200毫秒向桶中放入一個(gè)令牌。

當(dāng)我們運(yùn)行程序時(shí)，程序運(yùn)行到RateLimiter limiter = RateLimiter.create(5);時(shí)，就會(huì)向桶中放入一個(gè)令牌，當(dāng)程序運(yùn)行到第一個(gè)System.out.println(limiter.acquire(1));時(shí)，由于桶中已經(jīng)存在一個(gè)令牌，直接獲取這個(gè)令牌，并沒(méi)有花費(fèi)時(shí)間。然而程序繼續(xù)向下執(zhí)行時(shí)，由于程序會(huì)每隔200毫秒向桶中放入一個(gè)令牌，所以，獲取令牌時(shí)，花費(fèi)的時(shí)間幾乎都是200毫秒左右。

突發(fā)流量示例

我們?cè)賮?lái)看一個(gè)突發(fā)流量的示例，代碼示例如下所示。

package io.binghe.limit.guava;

import com.google.common.util.concurrent.RateLimiter;

/**
 * @author binghe
 * @version 1.0.0
 * @description 令牌桶算法
 */
publicclass TokenBucketLimiter {
    public static void main(String[] args){
        //每秒鐘生成5個(gè)令牌
        RateLimiter limiter = RateLimiter.create(5);

        //返回值表示從令牌桶中獲取一個(gè)令牌所花費(fèi)的時(shí)間，單位是秒
        System.out.println(limiter.acquire(50));
        System.out.println(limiter.acquire(5));
        System.out.println(limiter.acquire(5));
        System.out.println(limiter.acquire(5));
        System.out.println(limiter.acquire(5));
    }
}

上述代碼表示的含義為：每秒向桶中放入5個(gè)令牌，第一次從桶中獲取50個(gè)令牌，也就是我們說(shuō)的突發(fā)流量，后續(xù)每次從桶中獲取5個(gè)令牌。接下來(lái)，我們運(yùn)行上述代碼看下效果。

0.0
9.998409
0.99109
1.000148
0.999752

運(yùn)行代碼時(shí)，會(huì)發(fā)現(xiàn)當(dāng)命令行打印出0.0后，會(huì)等很久才會(huì)打印出后面的輸出結(jié)果。

程序每秒鐘向桶中放入5個(gè)令牌，當(dāng)程序運(yùn)行到 RateLimiter limiter = RateLimiter.create(5); 時(shí)，就會(huì)向桶中放入令牌。當(dāng)運(yùn)行到 System.out.println(limiter.acquire(50)); 時(shí)，發(fā)現(xiàn)很快就會(huì)獲取到令牌，花費(fèi)了0.0秒。接下來(lái)，運(yùn)行到第一個(gè)System.out.println(limiter.acquire(5));時(shí)，花費(fèi)了9.998409秒。小伙們可以思考下，為什么這里會(huì)花費(fèi)10秒中的時(shí)間呢？

這是因?yàn)槲覀兪褂?/span>RateLimiter limiter = RateLimiter.create(5);代碼向桶中放入令牌時(shí)，一秒鐘放入5個(gè)，而System.out.println(limiter.acquire(50));需要獲取50個(gè)令牌，也就是獲取50個(gè)令牌需要花費(fèi)10秒鐘時(shí)間，這是因?yàn)槌绦蛳蛲爸蟹湃?0個(gè)令牌需要10秒鐘。程序第一次從桶中獲取令牌時(shí)，很快就獲取到了。而第二次獲取令牌時(shí)，花費(fèi)了將近10秒的時(shí)間。

Guava框架支持突發(fā)流量，但是在突發(fā)流量之后再次請(qǐng)求時(shí)，會(huì)被限速，也就是說(shuō)：在突發(fā)流量之后，再次請(qǐng)求時(shí)，會(huì)彌補(bǔ)處理突發(fā)請(qǐng)求所花費(fèi)的時(shí)間。所以，我們的突發(fā)示例程序中，在一次從桶中獲取50個(gè)令牌后，再次從桶中獲取令牌，則會(huì)花費(fèi)10秒左右的時(shí)間。

Guava令牌桶算法的特點(diǎn)

• RateLimiter使用令牌桶算法，會(huì)進(jìn)行令牌的累積，如果獲取令牌的頻率比較低，則不會(huì)導(dǎo)致等待，直接獲取令牌。
• RateLimiter由于會(huì)累積令牌，所以可以應(yīng)對(duì)突發(fā)流量。也就是說(shuō)如果同時(shí)請(qǐng)求5個(gè)令牌，由于此時(shí)令牌桶中有累積的令牌，能夠快速響應(yīng)請(qǐng)求。
• RateLimiter在沒(méi)有足夠的令牌發(fā)放時(shí)，采用的是滯后的方式進(jìn)行處理，也就是前一個(gè)請(qǐng)求獲取令牌所需要等待的時(shí)間由下一次請(qǐng)求來(lái)承受和彌補(bǔ)，也就是代替前一個(gè)請(qǐng)求進(jìn)行等待。（這里，小伙伴們要好好理解下）