在開發(fā)高并發(fā)系統(tǒng)時，有三把利器用來保護系統(tǒng)：緩存、降級和限流。通過限流，我們可以很好地控制系統(tǒng)的qps，從而達到保護系統(tǒng)的目的。主要算法有：計數(shù)器算法，滑動窗口算法，漏桶算法，令牌桶算法

1.計數(shù)器算法

規(guī)定接口的最大頻率，例如一分鐘最多100次接口調(diào)用，利用一個計數(shù)器來不斷計數(shù)，統(tǒng)計一分鐘內(nèi)調(diào)用次數(shù)是否超過100，如果沒有超過則本次請求可以響應，如果超過則阻塞丟棄本次請求，計數(shù)器清零，重新開始計數(shù)。

public class Counter {public long timeStamp = System.currentTimeMillis();public int reqCount = 0;public final int limit = 100;public final long interval = 1000;public boolean grant(){long now = System.currentTimeMillis();if(now < timeStamp+interval){reqCount++;return reqCount<=limit;}else{timeStamp = now;reqCount = 1;return false;}} }

問題：如果在判斷時間間隔前后進行大量請求，則會突破限流頻率給系統(tǒng)造成損害，假設有一個惡意用戶，他在0:59時，瞬間發(fā)送了100個請求，并且1:00又瞬間發(fā)送了100個請求，那么其實這個用戶在 1秒里面，瞬間發(fā)送了200個請求。我們剛才規(guī)定的是1分鐘最多100個請求，也就是每秒鐘最多1.7個請求，用戶通過在時間窗口的重置節(jié)點處突發(fā)請求， 可以瞬間超過我們的速率限制。用戶有可能通過算法的這個漏洞，瞬間壓垮我們的應用。

2.滑動窗口算法

設置一個1秒鐘的滑動窗口，窗口中有10個格子，每個格子100毫秒，每100毫秒移動一次，每次移動都需要記錄當前服務請求的次數(shù)。內(nèi)存中需要保存10次的次數(shù)。可以用數(shù)據(jù)結(jié)構LinkedList來實現(xiàn)。格子每次移動的時候判斷一次，當前訪問次數(shù)和LinkedList中最后一個相差是否超過100，如果超過就需要限流。

public class RollingWindow {Long counter = 0L;LinkedList<Long> ll = new LinkedList<Long>();public void doCheck() throws Exception{while(true){ll.addLast(counter);if(ll.size()>10){ll.removeFirst();}if(ll.peekLast()-ll.peekFirst()>100){// to do limit }Thread.sleep(100);}} }

計數(shù)器算法其實就是滑動窗口算法。它沒有對時間窗口做進一步地劃分，只有1格。當滑動窗口的格子劃分的越多，那么滑動窗口的滾動就越平滑，限流的統(tǒng)計就會越精確。

3.漏桶算法

漏桶算法，又稱leaky bucket。首先，我們有一個固定容量的桶，有水流進來，也有水流出去。對于流進來的水來說，我們無法預計一共有多 少水會流進來，也無法預計水流的速度。但是對于流出去的水來說，這個桶可以固定水流出的速率。而且，當桶滿了之后，多余的水將會溢出。

public class LeakyBucket {public long timeStamp = System.currentTimeMillis();public int capacity;//桶大小public int rate;//漏水速率public int water;//水量public boolean grant(){long now = System.currentTimeMillis();water = (int)Math.max(0, water-(now-timeStamp)*rate);timeStamp = now;if(water+1<capacity){water += 1;return true;}else{return false;}} }

因為漏桶的漏出速率是固定的參數(shù),所以,即使網(wǎng)絡中不存在資源沖突(沒有發(fā)生擁塞),漏桶算法也不能使流突發(fā)(burst)到端口速率.因此,漏桶算法對于存在突發(fā)特性的流量來說缺乏效率.

4.令牌桶算法

令牌桶算法，又稱token bucket。首先，我們有一個固定容量的桶，桶里存放著令牌（token）。桶一開始是空的，token以 一個固定的速率r往桶里填充，直到達到桶的容量，多余的令牌將會被丟棄。每當一個請求過來時，就會嘗試從桶里移除一個令牌，如果沒有令牌的話，請求無法通過。

public class TokenBucket {public long timeStamp = System.currentTimeMillis();public int capacity;public int rate;public int tokens;public boolean grant(){long now = System.currentTimeMillis();tokens = (int)Math.min(capacity, tokens+(now-timeStamp)*rate);timeStamp = now;if(tokens<1){return false;}else{tokens -= 1;return true;}} }

令牌桶的一個好處是可以方便的改變速度. 一旦需要提高速率,則按需提高放入桶中的令牌的速率. 一般會定時(比如100毫秒)往桶中增加一定數(shù)量的令牌, 有些變種算法則實時的計算應該增加的令牌的數(shù)量。漏桶算法和令牌桶算法最明顯的區(qū)別是令牌桶算法允許流量一定程度的突發(fā)。因為默認的令牌桶算法，取走token是不需要耗費時間的，也就是說，假設桶內(nèi)有100個token時，那么可以瞬間允許100個請求通過。令牌桶算法由于實現(xiàn)簡單，且允許某些流量的突發(fā)，對用戶友好，所以被業(yè)界采用地較多。當然我們需要具體情況具體分析，只有最合適的算法，沒有最優(yōu)的算法。

Google開源工具包Guava提供了限流工具類RateLimiter,該類基于令牌桶算法(Token Bucket)來完成限流,非常易于使用.RateLimiter經(jīng)常用于限制對一些物理資源或者邏輯資源的訪問速率.它支持兩種獲取permits接口,一種是如果拿不到立刻返回false,一種會阻塞等待一段時間看能不能拿到。

對于Nginx接入層限流可以使用Nginx自帶了兩個模塊：連接數(shù)限流模塊ngx_http_limit_conn_module和漏桶算法實現(xiàn)的請求限流模塊ngx_http_limit_req_module。

1. ngx_http_limit_conn_module

服務器流量異常，負載過大等等。對于大流量惡意的攻擊訪問，會帶來帶寬的浪費，服務器壓力，影響業(yè)務，往往考慮對同一個ip的連接數(shù)，并發(fā)數(shù)進行限制。ngx_http_limit_conn_module 模塊來實現(xiàn)該需求。該模塊可以根據(jù)定義的鍵來限制每個鍵值的連接數(shù)，如同一個IP來源的連接數(shù)。并不是所有的連接都會被該模塊計數(shù)，只有那些正在被處理的請求（這些請求的頭信息已被完全讀入）所在的連接才會被計數(shù)。

2. ngx_http_limit_req_module

該模塊可以通過定義的鍵值來限制請求處理的頻率。特別的，可以限制來自單個IP地址的請求處理頻率。 限制的方法是使用了漏斗算法，每秒固定處理請求數(shù)，推遲過多請求。如果請求的頻率超過了限制域配置的值，請求處理會被延遲或被丟棄，所以所有的請求都是以定義的頻率被處理的。

參考鏈接：

https://www.cnblogs.com/haoxinyue/p/6792309.html

https://www.cnblogs.com/clds/p/5850070.html

https://www.cnblogs.com/haoxinyue/p/6792309.html

總結(jié)

以上是生活随笔為你收集整理的高并发系统--限流算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。