四種常見的限流算法以及實戰

簡介

限流顧名思義是對流量大小進行限制，防止請求數量超過系統的負載能力，導致系統崩潰，起到保護作用。
現實生活中限流也隨處可見，節假日出門旅行的人數會劇增，對於旅遊景點來說往往會不堪重負，如果不進行人數控制，對整個景點的壓力會非常大，遊客的體驗也會非常差，還容易出現安全事故等危險。
同樣的在一線城市地鐵限流也非常常見，早高峯爲了控制乘車人數和有序進站，地鐵往往會在地鐵口進行攔截，一定時間內才放行一部分人進站乘車。

具體到程序，限流可以有以下幾種場景

限流起到了保護作用，那麼如何限呢？如果限制得太嚴，保護是保護到了，但是系統的處理能力下降了，體驗會很差；如果限制得太鬆，就會被一些突增流量衝擊到，或者被黑客利用進行安全攻擊。如何限流需要根據系統的負載來評估，系統的負載和處理能力是動態的，例如平時的 qps 是 1000，雙 11 一般會進行擴容，也就是加服務節點，qps 可能就是 5000，這個時候系統處理能力變強的，限流策略也應該相應的調整。還有一種是出於安全的限流，例如同一個客戶端 ip 1s 內對系統發出上萬次請求，這種可以確定就是安全攻擊，很可能是有人惡意破壞，或者是一些爬蟲，這種可以限制請求數，超出的就直接拒絕。
如何限流是限流算法要實現的，常見的限流算法有 “兩桶兩窗”，固定窗口、滑動窗口、漏桶與令牌桶，接下來介紹這四種算法及應用。

固定窗口

固定窗口的思想和實現非常簡單，就是統計每個固定每個時間窗口的請求數，超過則拒絕。

如圖我們定義了窗口大小爲 1s，最大請求數 100，窗口內超過 100 的請求數將被拒絕。實現上也非常簡單，利用 redis 的 incr 自增計數，當前時間秒作爲緩存 key，每次自增後判斷是否超過指定大小即可。
固定窗口的問題是容易出現 “突刺現象”，例如在 1s 內，100 個請求都是在前 100ms 過來的，那麼後面的 900ms 的請求都會被拒絕，而系統此時是空閒的。另外還有 “臨界問題”，如果 100 個請求是在後 100ms 過來的，而下一個 1s 的 100 個請求在前 100ms 過來，此時系統在這 200ms 內就需要處理 200 個請求，跟我們想要的不符合。到這裏我們很容易想到，1s 這個範圍太大了，縮小一些就更好了，這種把固定窗口拆成更多個小窗口的做法就是滑動窗口算法了。

滑動窗口

滑動窗口的思想是將固定窗口拆成更多個小窗口，隨着時間的推移，窗口不斷的滑動，統計也在不斷的變化。窗口拆分的越多，滑動就會越平滑，統計就會越精確，所消耗的資源就會越多。滑動窗口如果只拆爲 1 個窗口，就退化爲固定窗口。
滑動窗口算法可以解決上面固定窗口的問題，像 hystrix 和 sentinel 中都使用該算法進行數據統計，用於限流熔斷等策略處理。如 hystrix 中圖所示，在一個窗口內拆分了 10 個桶（bucket），隨着時間的推移，會創建新的桶也會丟棄過期的桶，當然窗口的大小和拆分桶的數量都是可配置的。

漏桶

漏桶算法的思想是將請求先放到一個桶中，然後像滴水一樣不斷的從中取出請求執行，桶滿則溢，後面的請求會被拒絕。

漏桶算法的特點是流入速度不確定，但是流出速度是確定的，漏桶可以很平滑，均衡的處理請求，但是無法應對短暫的突發流量。

令牌桶

令牌桶算法的思想是不斷的生成令牌放到一個桶中，請求到來時到桶中申請令牌，申請得到就執行，申請不到就拒絕。如果桶中的令牌滿了，新生成的令牌也會丟棄。

與漏桶不同的是，令牌桶是流入速度確定 (生成令牌的速度)，流出速度不確定，所以它不想漏桶一樣可以均衡的處理請求，但是由於有令牌桶這個緩衝，一旦有突增的流量，令牌桶裏已有的令牌可以短暫的應對突發流量，由於流出速度是不限制的，此時桶中已有的令牌都可以被申請到，請求一下子就會到我們的服務，給系統帶來一定的壓力，所以桶的大小需要合適，不宜過大。舉個栗子：令牌桶的大小是 1000，每秒放 100 個令牌，經過一段時間後，請求有空閒時，桶裏的令牌就會積壓，最終保存了滿 1000 個令牌，由於某刻流量突增，有 1000 個請求到來，此時能申請到 1000 個令牌，所有請求都會放行，最終達到我們的系統，如果令牌桶過大，系統可能會承受不了這波請求。

應用

guava RateLimiter

guava 限流實現的是桶算法，通過 RateLimiter.create 創建，可以創建兩種類型的限流器，SmoothBursty 和 SmoothWarmingUp，前者定時生成令牌，後者有一個預熱的過程。
我們如下示例代碼，每秒會創建 2 個令牌，並且初始化的時候就是 2。定時器每 200ms 會申請一次令牌，每秒申請 5 次，只有 2 次成功，所有運行程序每秒有 3 次 success 和 2 次 fail。

        RateLimiter rateLimiter = RateLimiter.create(2);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				if (rateLimiter.tryAcquire()) {
					System.out.println("success");
				} else {
					System.out.println("fail");
				}
			}
		}, 0, 200);

既然是桶，那麼桶的大小是多少呢？SmoothBursty 裏最大令牌數由 maxPermits 字段表示，該字段等於 maxBurstSeconds * permitsPerSecond，permitsPerSecond 是每秒要生成的令牌數，maxBurstSeconds 默認是 1。
另外還可以創建 SmoothWarmingUp 帶有預熱功能的限流器，預熱的作用是通過一個過程才達到 permitsPerSecond，相當於讓系統有個熱身的時間。

		RateLimiter rateLimiter = RateLimiter.create(5, 10, TimeUnit.MILLISECONDS);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				log.info("" + rateLimiter.acquire());			
			}
		}, 0, 200);

rateLimiter.acquire() 返回的是獲取打令牌的時間，運行程序可以看到開始並不是每秒都能產生 5 個令牌，也就是不是能立刻獲取到令牌，獲取令牌需要的時間會越來越小，直到預熱期過後就能立馬獲取到令牌了。
guava 的限流只能提供單機版的實現，對於集羣就無能爲力了，並且它通常作爲一個工具存在，使用還需要自己封裝，集成到服務，並不能開箱即用。

bucket4j

bucket4j 是一個 java 實現，基於令牌桶算法的限流組件。它支持分佈式限流，支持多種存儲，可以方便與各種框架和監控集成。github 上 start 1.2K，但是 issues 數量少，國內估計使用的人也不多，並且官方的實現存儲不支持最常用的 redis，它專注於限流，如果是自研或者二次開發，是一個很好的參考。

Resilience4j

之前我們介紹過它的熔斷功能，Resilience4j 也提供了限流的實現，可以參考這裏。相比 guava，Resilience4j 是框架級別的，可以很方便的使用。但 Resilience4j 也是單機版的實現，無法支持集羣功能。
Resilience4j 限流實現的是令牌桶，如下配置，每 1s 會生成 10 個令牌。

resilience4j.ratelimiter:
    instances:
        backendA:
            limitForPeriod: 10
            limitRefreshPeriod: 1s
            timeoutDuration: 0
            registerHealthIndicator: true
            eventConsumerBufferSize: 100

sentinel

流量控制是 sentinel 最重要的一個功能，sentinel 屬於後起之秀，文檔齊全，支持的場景更加豐富。sentinel 支持集羣限流，也可以像 guava 一樣預熱，還可以基於調用鏈路進行限流。
sentinel 還提供了控制檯功能，支持多種數據源的持久化，使用 spring cloud 的話可以通過 spring cloud alibaba 引入 sentinel。
開源版的 sentinel 有一些限制，並且使用起來並不是那麼方便，例如 Resilience4j 可以配置一個 default 針對所有的請求生效，但 sentinel 需要單個單個 url 去配置，顯得非常麻煩，包括熔斷 feign 接口的配置也是，這個給 spring cloud alibaba 提了 feature，也許在下一個版本就會提供支持。

nginx

上面講到的都是應用級別的限流，nginx 通常作爲網絡請求的入口，從運維的角度來說，在這裏做限流再合適不過，nginx 本身也提供了限流的支持。
nginx 比較適合對外的限流，但是我們內部不同系統間的調用一遍不經過 nginx，會直接訪問到對方的網關，所以兩者並不矛盾。
nginx 限流通過 limit_req 和 limit_conn 兩個模塊支持，分別對應請求限制和鏈接限制（一個鏈接可以有多個請求）。

http {  
    limit_req_zone zone=name:10m rate=100r/s;  
    server {  
        location /app/ {
            limit_req zone=name burst=500 nodelay;
        }
}

如上，定義了一個 name zone，訪問速率最高是 100 個每秒，/app 路徑應用了這個規則。busrt 表示爆發的意思，是一個緩衝隊列，用於存儲突增的請求，這些請求會被緩存不會拒絕，如果超過了 burst，nodelay 表示不等待直接拒絕。
前面我們說到有些惡意攻擊可能每秒發送上萬個請求，導致服務崩潰，如果多個應用系統共用一個 nginx，那麼可以統一在 nginx 配置處理，不需要每個系統自己去實現。

limit_conn_zone $binary_remote_addr zone=name:10m;

server {    
    limit_conn name 50;    
}

如上，定義了一個 name zone，$binary_remote_addr 表示遠端地址，也就是 ip，10m 表示存儲空間，10m 大概可以存儲 16w 的 ip 地址，我們在 server 節點應用這個規則，50 表示最多 50 個，超過就會拒絕。

文章來源：https://www.cnblogs.com/jtea/p/17057214.html?utm_source=gold_browser_extension

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vpUmqhlPjzJrW4MpMdsDNA

猜你喜歡