計數器

計數器法

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

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

圖片

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

圖片

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

滑動窗口

圖片

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

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

回頭看看計數器算法，會發現，其實計數器算法就是窗口滑動算法，只不過計數器算法沒有對時間窗口進行劃分，所以是一格。

由此可見，當滑動窗口的格子劃分越多，限流的統計就會越精確。

漏桶算法

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

圖片

漏桶算法不支持突發流量。

令牌桶算法

圖片

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

令牌桶算法支持突發流量。

令牌桶算法實現

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

平滑流量示例

這里，我寫了一個使用Guava框架實現令牌桶算法的示例，如下所示。

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);

        //返回值表示從令牌桶中獲取一個令牌所花費的時間，單位是秒
        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));
    }
}

代碼的實現非常簡單，就是使用Guava框架的RateLimiter類生成了一個每秒向桶中放入5個令牌的對象，然后不斷從桶中獲取令牌。我們先來運行下這段代碼，輸出的結果信息如下所示。

0.0
0.197294
0.191278
0.19997
0.199305
0.200472
0.200184
0.199417
0.200111
0.199759

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

因為在Guava的實現是這樣的：我們使用RateLimiter.create(5)創建令牌桶對象時，表示每秒新增5個令牌，1秒等于1000毫秒，也就是每隔200毫秒向桶中放入一個令牌。

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

突發流量示例

我們再來看一個突發流量的示例，代碼示例如下所示。

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);

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

0.0
9.998409
0.99109
1.000148
0.999752

運行代碼時，會發現當命令行打印出0.0后，會等很久才會打印出后面的輸出結果。

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

這是因為我們使用RateLimiter limiter = RateLimiter.create(5);代碼向桶中放入令牌時，一秒鐘放入5個，而System.out.println(limiter.acquire(50));需要獲取50個令牌，也就是獲取50個令牌需要花費10秒鐘時間，這是因為程序向桶中放入50個令牌需要10秒鐘。程序第一次從桶中獲取令牌時，很快就獲取到了。而第二次獲取令牌時，花費了將近10秒的時間。

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

Guava令牌桶算法的特點

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