計(jì)數(shù)器

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

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

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

圖片

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

圖片

這個問題我們可以使用滑動窗口解決。

滑動窗口

圖片

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

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

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

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

漏桶算法

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

圖片

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

令牌桶算法

圖片

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

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

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

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

平滑流量示例

這里，我寫了一個使用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個令牌
        RateLimiter limiter = RateLimiter.create(5);

        //返回值表示從令牌桶中獲取一個令牌所花費(fèi)的時間，單位是秒
        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)非常簡單，就是使用Guava框架的RateLimiter類生成了一個每秒向桶中放入5個令牌的對象，然后不斷從桶中獲取令牌。我們先來運(yùn)行下這段代碼，輸出的結(jié)果信息如下所示。

0.0
0.197294
0.191278
0.19997
0.199305
0.200472
0.200184
0.199417
0.200111
0.199759

從輸出結(jié)果可以看出：第一次從桶中獲取令牌時，返回的時間為0.0，也就是沒耗費(fèi)時間。之后每次從桶中獲取令牌時，都會耗費(fèi)一定的時間，這是為什么呢？按理說，向桶中放入了5個令牌后，再從桶中獲取令牌也應(yīng)該和第一次一樣并不會花費(fèi)時間?。?/span>

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

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

突發(fā)流量示例

我們再來看一個突發(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個令牌
        RateLimiter limiter = RateLimiter.create(5);

        //返回值表示從令牌桶中獲取一個令牌所花費(fèi)的時間，單位是秒
        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個令牌，第一次從桶中獲取50個令牌，也就是我們說的突發(fā)流量，后續(xù)每次從桶中獲取5個令牌。接下來，我們運(yùn)行上述代碼看下效果。

0.0
9.998409
0.99109
1.000148
0.999752

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

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

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

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

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

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