常見限流演算法-有解無憂

簡介

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

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

限制某個介面每秒最多訪問多少次
限制某個ip每秒最多訪問多少次
限制某個用戶或某個來源每秒最多訪問多少次
限制某些用戶下載速度每秒最多多少kb
禁止某些用戶或ip的訪問

限流起到了保護作用，那么如何限呢？如果限制得太嚴，保護是保護到了，但是系統的處理能力下降了，體驗會很差；如果限制得太松，就會被一些突增流量沖擊到，或者被黑客利用進行安全攻擊，如何限流需要根據系統的負載來評估，系統的負載和處理能力是動態的，例如平時的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.uj5u.com/houduan/542126.html

標籤：其他

上一篇：Frida-trace常用命令

下一篇：垃圾回識訓制