高并發系統設計之限流-有解無憂

本文已收錄至Github，推薦閱讀 ?? Java隨想錄

微信公眾號：Java隨想錄

CSDN：碼農BookSea

限流演算法
- 計數器演算法
- 滑動視窗
- 漏桶演算法
- 令牌桶演算法
限流演算法實作
- Guava RateLimiter實作限流
  - 令牌預分配
  - 預熱限流
- Nginx 限流
  - limit_conn
  - limit_req
  - 黑白名單限流

這篇文章來講講限流，在高并發系統中限流是必不可少的，限流可以保證一部分的請求得到正常的回應，是一種自我保護的措施，限流可以保證使用有限的資源提供最大化的服務能力，按照預期流量提供服務，超過的部分將會拒絕服務、排隊或等待、降級等處理，

首先，先來了解下幾種限流演算法，

限流演算法

計數器演算法

計數器演算法是限流演算法里最簡單也是最容易實作的一種演算法，

舉個例子：我們規定介面A在1分鐘內訪問次數不能超過1000個，我們可以設定一個計數器，對固定時間視窗1分鐘進行計數，每有一個請求，計數器就+1，如果請求數超過了閾值，則舍棄該請求，當時間視窗結束時，重置計數器為0，

計數器演算法雖然簡單，但是有一個十分致命的問題，那就是臨界問題，

假設有一個用戶，他在0:59時，瞬間發送了1000個請求，并且1:01又發送了1000個請求，那么其實用戶在 2秒里面，瞬間發送了2000個請求，用戶通過在時間視窗的重置節點處突發請求，可以瞬間超過我們的速率限制，用戶有可能利用這個漏洞卡Bug，瞬間壓垮我們的應用，

缺點：沒有辦法防止時間范圍臨界點突發大流量，很可能在時間范圍交界處被大量請求直接打到降級，影響后續服務，

滑動視窗

滑動視窗演算法解決了上訴計數器演算法的缺點，計數器的時間視窗是固定的，而滑動視窗的時間視窗是動態的，

整個紅色的矩形框表示一個時間視窗，在我們的例子中，一個時間視窗就是一分鐘，然后我們將時間視窗進行劃分，比如圖中，我們就將滑動視窗劃成了6格，所以每格代表的是10秒鐘，每過10秒鐘，我們的時間視窗就會往右滑動一格，每一個格子都有自己獨立的計數器，比如當一個請求在0:35秒的時候到達，那么0:30~0:39對應的計數器就會加1，

那么滑動視窗怎么解決剛才的臨界問題的呢？我們可以看上圖，0:59到達的1000個請求會落在灰色的格子中，而1:01到達的請求會落在橘黃色的格子中，當時間到達1:00時，我們的視窗會往右移動一格，那么此時時間視窗內的總請求數量一共是2000個，超過了限定的1000個，所以此時能夠檢測出來觸發限流，

當滑動視窗的格子劃分的越多，那么滑動視窗的滾動就越平滑，限流的統計就會越精確，

缺點：滑動視窗無法平滑控制請求流量，僅能控制時間段內請求總量，宏觀來看，時間軸上的請求數量波形可能出現較大的波動，

漏桶演算法

說到漏桶演算法的時候，我們腦中先構思出一幅圖：一個水桶，桶底下有一個小孔，水以固定的頻率流出，水龍頭以任意速率流入水，當水超過桶則”溢位“，

漏桶演算法的話保證了固定的流出速率，這是漏桶演算法的優點，也可以說是缺點，始終恒定的處理速率有時候并不一定是好事情，對于突發的請求洪峰，在保證服務安全的前提下，應該盡最大努力去回應，這個時候漏桶演算法顯得有些呆滯，最終可能導致水位”溢位“，請求被丟棄，

缺點：無法應對突發流量，由于處理速度恒定，當大量請求到來時，用戶等待時間長，用戶體驗差，

令牌桶演算法

對于很多應用場景來說，除了要求能夠限制資料的平均傳輸速率外，還要求允許某種程度的突發傳輸，這時候漏桶演算法可能就不合適了，令牌桶演算法更為適合，

令牌桶演算法的原理是系統以恒定的速率產生令牌，然后把令牌放到令牌桶中，令牌桶有一個容量，當令牌桶滿了的時候，再向其中放令牌，那么多余的令牌會被丟棄；當想要處理一個請求的時候，需要從令牌桶中取出一個令牌，如果此時令牌桶中沒有令牌，那么則拒絕該請求，

缺點：令牌桶的數量，生成的速度需要根據以往的系統性能以及用戶習慣等經驗的累積來判斷，實際限流數難以預知，

限流演算法實作

Guava RateLimiter實作限流

引入依賴

<dependency>
	<groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

下面是一個使用的簡單例子：

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

public class RateLimiterTest {
    public static void main(String[] args) {
        RateLimiter rateLimiter = RateLimiter.create(1); //創建一個每秒產生一個令牌的令牌桶
        for (int i = 1; i <= 5; i++) {
            double waitTime = rateLimiter.acquire(i); //一次獲取i個令牌
            System.out.println("acquire:" + i + " waitTime:" + waitTime);
        }

    }
}

結果：
    
acquire:1 waitTime:0.0
acquire:2 waitTime:0.995081
acquire:3 waitTime:1.998054
acquire:4 waitTime:2.999351
acquire:5 waitTime:3.999224

可以發現等待時間差不多間隔都是1秒，

RateLimiter是個抽象類，子類SmoothRateLimiter又做了層抽象，SmoothRateLimiter有兩個子類SmoothBursty和SmoothWarmingUp，

SmoothBursty：令牌的生成速度恒定，使用 RateLimiter.create(double permitsPerSecond) 創建的是 SmoothBursty 實體，
SmoothWarmingUp：令牌的生成速度持續提升，直到達到一個穩定的值，WarmingUp，顧名思義就是有一個熱身的程序，使用 RateLimiter.create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) 時創建就是 SmoothWarmingUp 實體，其中 warmupPeriod 就是熱身達到穩定速度的時間，

SmoothWarmingUp可以理解為是進階版的SmoothBursty，

令牌預分配

RateLimiter 使用令牌桶演算法，會進行令牌的累積，令牌會被預先分配，

public class RateLimiterTest {
    public static void main(String[] args) {
        RateLimiter r = RateLimiter.create(5);
        while (true) {
            System.out.println("get 5 tokens: " + r.acquire(5) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("end");
            /**
             * output:
             * get 5 tokens: 0.0s
             * get 1 tokens: 0.996766s 滯后效應，需要替前一個請求進行等待
             * get 1 tokens: 0.194007s
             * get 1 tokens: 0.196267s
             * end
             * get 5 tokens: 0.195756s
             * get 1 tokens: 0.995625s 滯后效應，需要替前一個請求進行等待
             * get 1 tokens: 0.194603s
             * get 1 tokens: 0.196866s
             */
        }
    }
}

RateLimiter 由于會累積令牌，所以可以應對突發流量，有一個請求會直接請求5個令牌，但是由于此時令牌桶中有累積的令牌，足以快速回應， RateLimiter 在沒有足夠令牌發放時，采用滯后處理的方式，也就是前一個請求獲取令牌所需等待的時間由下一次請求來承受，也就是代替前一個請求進行等待，

預熱限流

RateLimiter 的 SmoothWarmingUp 是帶有預熱期的平滑限流，它啟動后會有一段預熱期，逐步將分發頻率提升到配置的速率，

public class RateLimiterTest {
    public static void main(String[] args) {
        RateLimiter r = RateLimiter.create(2, 3, TimeUnit.SECONDS);
        while (true) {
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("get 1 tokens: " + r.acquire(1) + "s");
            System.out.println("end");
            /**
             * output:
             * get 1 tokens: 0.0s
             * get 1 tokens: 1.329289s
             * get 1 tokens: 0.994375s
             * get 1 tokens: 0.662888s  上邊三次獲取的時間相加正好為3秒
             * end
             * get 1 tokens: 0.49764s  正常速率0.5秒一個令牌
             * get 1 tokens: 0.497828s
             * get 1 tokens: 0.49449s
             * get 1 tokens: 0.497522s
             */
        }
    }
}

創建一個平均分發令牌速率為2，預熱期為3秒，令牌桶一開始并不會0.5秒發一個令牌，而是頻率越來越高，在3秒鐘之內達到原本設定的頻率，以后就以固定的頻率輸出，

介紹幾個重要的引數

abstract class SmoothRateLimiter extends RateLimiter {
	//當前存盤令牌數
    double storedPermits;
    //最大存盤令牌數
    double maxPermits;
    //添加令牌時間間隔
    double stableIntervalMicros;
    private long nextFreeTicketMicros;
}

通過Debug我們可以看到，SmoothBursty方法的最大令牌數被設定成了，maxBurstSeconds * permitsPerSecond，而maxBurstSeconds默認是1，

而 SmoothWarmingUp最大令牌數的計算方法要復雜的多，

Nginx 限流

對于Nginx接入層限流可以使用 Nginx自帶的兩個模塊：連接數限流模塊ngx_http _limit_conn_module和漏桶演算法實作的請求限流模塊ngx_http_limit_req_module，

limit_conn 用來對某個key對應的總的網路連接數進行限流，可以按照如IP、域名維度進行限流，limit_req用來對某個key對應的請求的平均速率進行限流，有兩種用法：平滑模式（delay）和允許突發模式（nodelay），

limit_conn

limit_conn是對某個key對應的總的網路連接數進行限流，可以按照IP來限制IP維度的總連接數，或者按照服務域名來限制某個域名的總連接數，但是，記住不是每個請求連接都會被計數器統計，只有那些被Nginx處理的且已經讀取了整個請求頭的請求連接才會被計數器統計，

http {
    limit_conn_zone $binary_remote_addr zone=addr:10m;
    limit_conn_log_level error;
    limit_conn_status 503 ;

    server {
        location /limit {
            limit_conn addr l;
        }
    }
}

limit_conn：要配置存放key和計數器的共享記憶體區域和指定key的最大連接數，此處指定的最大連接數是1，表示Nginx最多同時并發處理1個連接，addr就是限流key，對應上文 zone=addr，
limit_conn_zone：用來配置限流key及存放key對應資訊的共享記憶體區域大小，此處的key是$binary_remote_addr，表示IP地址，也可以使用$server_name作為key來限制域名級別的最大連接數，
limit_conn_status：配置被限流后回傳的狀態碼，默認回傳503，
limit_conn_log_level：配置記錄被限流后的日志級別，默認error級別，

limit_req

limit_req 是漏桶演算法實作，用于對指定key 對應的請求進行限流，比如，按照 IP維度限制請求速率，配置示例如下：

http {
    limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;
    limit_conn_log_level error;
    limit_conn_status 503;

    server {
        location /limit {
            limit_req zone=one burst=20 nodelay;
        }
    }
}

limit_req 和 limit_conn 的配置類似，

limit_req：配置限流區域，上面的引數會讓nginx 每個IP一秒鐘只處理一個請求，
burst： burst 引數定義了超出 zone 指定速率的情況下，客戶端還能發起多少請求，超出速率的請求將會被放入佇列，我們將佇列大小設定為20，這意味著，如果從一個給定 IP 地址發送 21 個請求，Nginx 會立即將第一個請求發送到上游服務器群，然后將余下 20 個請求放在佇列中，然后每1秒轉發一個排隊的請求，只有當傳入請求使佇列中排隊的請求數超過 20 時，Nginx 才會向客戶端回傳 503，
nodelay：配置 burst 引數將會使通訊更流暢，但是可能會不太實用，因為該配置會使站點看起來很慢，在上面的示例中，佇列中的第 20 個包需要等待 20 秒才能被轉發，此時回傳給客戶端的回應可能不再有用，要解決這個情況，可以在 burst 引數后添加 nodelay 引數，使用 nodelay 引數，當一個請求到達“太早”時，只要在佇列中能分配位置，Nginx 將立即轉發這個請求，將佇列中的該位置標為”taken”(占據)，并且不會被釋放以供另一個請求使用，直到一段時間后才會被釋放，假設如前所述，佇列中有 20 個空位，從給定的 IP 地址發出的 21 個請求同時到達，Ngin x會立即轉發這個 21 個請求，并且標記佇列中占據的 20 個位置，然后每 1秒釋放一個位置，如果是25個請求同時到達，Nginx 將會立即轉發其中的 21 個請求，標記佇列中占據的 20 個位置，并且回傳 503 狀態碼來拒絕剩下的 4 個請求，如果希望不限制兩個請求間允許間隔的情況下實施“流量限制”，nodelay 引數是很實用的，
limit_req_zone：配置限流key、存放key對應資訊的共享記憶體區域大小、固定請求速率，此處指定的key是“$binary_remote_addr”，表示IP地址，10m表示共享記憶體的大小，16000 個 IP 地址的狀態資訊，大約需要 1MB，所以示例中區域可以存盤 160000 個 IP 地址，
limit_conn_status：配置被限流后回傳的狀態碼，默認回傳503，
limit_conn_log_level：配置記錄被限流后的日志級別，默認級別為error，

黑白名單限流

geo $limit {
    default         1;
    10.0.0.0/8      0;
    192.168.0.0/64  0;
}
map $limit $limit_key {
    0 "";
    1 $binary_remote_addr;
}
limit_req_zone $limit_key zone=req_zone:10m rate=5r/s;
server {
    location / {
        limit_req zone=req_zone burst=10 nodelay;
    }
}

geo 指令將給在白名單中的 IP 地址對應的 $limit 變數分配一個值 0，給其它不在白名單中的分配一個值 1，然后我們使用一個映射將這些值轉為 key，

白名單內 IP 地址的$limit_key變數被賦值為空字串，不在白名單內的被賦值為客戶端的 IP 地址，當limit_req_zone后的第一個引數是空字串時，不會應用“流量限制”，所以白名單內的 IP 地址不會被限制，其它所有 IP 地址都會被限制到每秒 5 個請求，

而要做出網站黑名單，就有可能要屏蔽一堆ip，但是如果將其放在nginx.conf檔案夾下，既不美觀，也不利于管理，因此需要單獨寫出一個conf檔案，然后在nginx.conf中使用 include標簽參考它，

如果我們不是要限流，而是要直接實作黑名單禁止訪問網站的話，可以使用allow和deny標簽，

server{
    listen: 80;
    server_name www.baidu.com;
    allow all; #允許訪問所有的ip
    deny 172.0.0.1; #禁止 172.0.0.1 訪問
}

可以配合shell腳本，然后把腳本加入crontab定時任務就可以實作動態添加黑名單，

#!/bin/bash
#取最近5w條資料
tail -n50000 /usr/local/nginx/logs/access.log \
#過濾需要的資訊行ip等
|awk '{print $1,$12}' \
#過濾爬蟲
|grep -i -v -E "google|yahoo|baidu|msnbot|FeedSky|sogou|360|bing|soso|403|admin" \
#統計
|awk '{print $1}'|sort|uniq -c|sort -rn \
#超過1000加入黑名單
|awk '{if($1>1000)print "deny "$2";"}' >> /usr/local/nginx/conf/blockip.conf
#重啟nginx生效
/usr/local/nginx/sbin/nginx -s reload

本篇文章就到這里，感謝閱讀，如果本篇博客有任何錯誤和建議，歡迎給我留言指正，文章持續更新，可以關注公眾號第一時間閱讀，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544811.html

標籤：Java

上一篇：java基礎語法

下一篇：day02-自己實作Mybatis底層機制-01