嘍，大家好呀，我是呼嚕嚕，好久沒有更新文章了，今天我們來聊聊在企業級項目中，常見的幾種限流手段的原理及其實現
隨著互聯網的業務發展，比如秒殺、雙十一、618等這些我們耳熟能詳，也有被人惡意攻擊的場景下，系統往往經受被高并發流量沖垮的風險，這個時候可以采用限流的方式，來保護自身的系統以及下游系統，當然還有其他各種方式手段，比如熔斷、降級、隔離等，本文將重點來講講限流
限流就是就是對請求或并發數進行限制，通過在一定時間內對請求量進行限制，來達到保護系統正常運行的目的。常見的限流算法，有計數器算法、滑動窗口計數算法、漏桶算法、令牌桶算法
計數器算法，通過計數器在周期內累加訪問次數，并規定一個周期(時間窗口)內的系統處理的請求數量(閾值)，當在一個周期內，計數的值達到限流閾值時觸發拒絕策略；到下一周期計數器就重置為0，重新開始計數，它是一種簡單方便的限流算法
比如我們設置系統的閾值1s中最多請求100次，在計數器算法中，我們需要把時間劃分固定大小窗口(所以計數器算法又叫固定窗口算法Fixed Window)，這里我們將1s劃分為一個時間窗口；然后用計數器來記錄在每個時間窗口的處理的請求數量，如果請求數量超過100次，后續的請求會被直接拒絕，直到1s結束后，重新開始計數
計數器算法優點實現簡單, 占用內存小，性能較高，但是有一個缺點，就是臨界問題，因為在一個時間窗口中，請求或者流量并不是均勻分布的，比如，在1.9s和2.1s的時間點，分別被人惡意并發請求了100次，也就是說從1.9s開始后的1s時間窗口期間，被瞬間請求了200次已經超過系統的閾值了，即使窗口2和窗口3還是正常的，這樣可能會導致系統直接掛掉
這里提供一個簡單的demo(Java版，其他語言大家自行改寫):
public class MyFixedWindowRateLimiterDemo {
// 閾值
private static Integer QPS=2;
// 時間窗口（毫秒）
private static long TIME_WINDOWS=1000;
// 計數器
private static AtomicInteger counter=new AtomicInteger();
//上一個窗口的開始時間
private static long START_TIME=System.currentTimeMillis();
public synchronized static boolean tryAcquire() {
if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
counter.set(0);
START_TIME=System.currentTimeMillis();
}
return counter.incrementAndGet() <=QPS;
}
public static void main(String[] args) throws InterruptedException {
for (int i=0; i < 10; i++) {
Thread.sleep(250);
LocalTime now=LocalTime.now();
if (!tryAcquire()) {
System.out.println(now + " 請求被限流");
} else {
System.out.println(now + " 請求通過");
}
}
}
}滑動窗口算法(Sliding Window)出現于網絡協議中傳輸層，是一種流量控制技術。我們這里對計數器(固定窗口)算法的臨界問題，滑動窗口算法進行了改進，不再固定窗口大小，而是將把固定窗口近一步劃分成多個小周期，每個周期都記錄自己的請求訪問次數，隨著時間流逝，滑動時間窗口(每次向后移動一周期)，同時刪除過期的小周期。每次判斷限流時，需要將一個窗口的所有小周期合起來，再與閾值進行比較
舉個例子，上圖我們將1s時間窗口，劃分成5個200ms的小周期，記錄每個周期的請求訪問次數，這里沿用上一小節的情形在1.9s和2.1s的時間點，分別被人惡意并發請求了100次，當滑動到第5個小周期時，訪問量為100次，未達到閾值；而當窗口滑動到第6個小周期時，訪問數量變為：200，這個時候會超過閾值，觸發拒絕訪問的限制
這樣就能限制住瞬時流量爆發。如果滑動窗口的單位區間劃分越細的話，滑動窗口的滾動就越平滑，限流統計也會越精準。但隨著而來的是實現滑動窗口算法，需要更多的存儲空間。另外計數器算法實現起來比較簡單，滑動窗口則更復雜
這里提供一個筆者感覺非常簡單明了的demo，參考于簡單的java實現滑動時間窗口限流算法，在此感謝
public class MySlidingWindowRateLimiterDemo {
/** 隊列id和隊列的映射關系，隊列里面存儲的是每一次通過時候的時間戳，這樣可以使得程序里有多個限流隊列 */
private volatile static Map<String, List<Long>> MAP=new ConcurrentHashMap<>();
//閾值
private static int QPS=2;
//時間窗口總大小（毫秒）
private static long WindowSize=10 * 1000;
/**
* 滑動時間窗口限流算法
* 在指定時間窗口，指定限制次數內，是否允許通過
*
* @param listId 隊列id
* @param count 限制次數
* @param timeWindow 時間窗口大小
* @return 是否允許通過
*/
public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
// 獲取當前時間
long nowTime=System.currentTimeMillis();
// 根據隊列id，取出對應的限流隊列，若沒有則創建
List<Long> list=MAP.computeIfAbsent(listId, k -> new LinkedList<>());
// 如果隊列還沒滿，則允許通過，并添加當前時間戳到隊列開始位置
if (list.size() < count) {
list.add(0, nowTime);
return true;
}
// 隊列已滿（達到限制次數），則獲取隊列中最早添加的時間戳
Long farTime=list.get(count - 1);
// 用當前時間戳 減去 最早添加的時間戳
if (nowTime - farTime <=timeWindow) {
// 若結果小于等于timeWindow，則說明在timeWindow內，通過的次數大于count
// 不允許通過
return false;
} else {
// 若結果大于timeWindow，則說明在timeWindow內，通過的次數小于等于count
// 允許通過，并刪除最早添加的時間戳，將當前時間添加到隊列開始位置
list.remove(count - 1);
list.add(0, nowTime);
return true;
}
}
public static void main(String[] args) throws InterruptedException {
for (int i=0; i < 20; i++) {
Thread.sleep(1000);
LocalTime now=LocalTime.now();
if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒內，只允許2次通過;自定義限流規則“ip”
System.out.println(now + " 請求被限流");
} else {
System.out.println(now + " 請求通過");
}
}
}
}
美中不足的是，在滑動窗口算法，窗口中流量到達閾值時，流量會瞬間切斷，而現實中我們還是更希望，讓流量跟平滑地放行到系統中，而不是簡單粗暴地將其掐斷
我們再來看看漏桶算法Leaky Bucket，是一個非常貼切的比喻，意思是，水(就是請求/流量)從進水口(生產端)進入桶(隊列)中，這個桶是漏的(比方說桶底有一個孔)，以一定的速度漏水(消費端不斷的在消費隊列中的請求)，當水進入桶的速度過大(大于漏水的速度)，會導致桶里的水堆積，當超過桶容量時會溢出來(請求被拒絕)。從而實現網絡流量整形和限流的功能
這里漏水的速度其實就是限流的閾值，所謂的閾值，表示在一個單位時間內允許的請求量，比如如QPS為100，說明1秒內系統最多可以消費100個請求。如果生產端的速率超過閾值的話，請求會慢慢堆積，又因為漏桶的容量是固定的，最后會觸發拒絕策略(溢出)
漏桶算法它的優點是，實現起來簡單，很容易理解。它可以嚴格限制請求的處理速度，一旦超過該速度就拒絕服務，從而避免網絡擁塞和系統過載
但它也有缺點：
這里提供一個簡單的demo(不完整，生產慎用，僅用來演示):
public class MyLeakyBucketRateLimiterDemo {
// 桶的容量
private final int capacity;
// 漏出速率
private final int rate;
// 剩余水量
private long leftWater;
// 上次注入時間
private long timeStamp=System.currentTimeMillis();
public MyLeakyBucketRateLimiterDemo(int rate, int capacity) {
this.capacity=capacity;
this.rate=rate;
}
public synchronized boolean tryAcquire() {
//1. 計算剩余水量
long now=System.currentTimeMillis();
long timeGap=(now - timeStamp) / 1000;
leftWater=Math.max(0, leftWater - timeGap * rate);
timeStamp=now;
// 如果未滿，則放行；否則限流
if (leftWater < capacity) {
leftWater +=1;
return true;
}
return false;
}
public static void main(String[] args) throws InterruptedException {
MyLeakyBucketRateLimiterDemo limiterDemo=new MyLeakyBucketRateLimiterDemo(2,5);
for (int i=0; i < 10; i++) {
Thread.sleep(500);
LocalTime now=LocalTime.now();
if (!limiterDemo.tryAcquire()) {
System.out.println(now + " 請求被限流");
} else {
System.out.println(now + " 請求通過");
}
}
}
}令牌桶算法是漏桶算法的改進版，是網絡流量整形(Traffic Shaping)和限流(Rate Limiting)中最常使用的一種算法，它也有一個桶，現在用來存放固定數量的令牌(token)，該算法會以一定的速率(閾值)往桶中發放令牌。每次請求都需要先獲取到桶中的一個令牌才能繼續執行，請求處理完畢之后將這個令牌丟棄，否則執行拒絕策略(一般有直接拒絕、排隊等待 等)；另外放令牌的動作是持續不斷進行的，如果桶裝滿了，則丟棄令牌
表面上看，令牌桶算法和漏桶算法是相反的，一個"進水"，一個是"漏水"。但與漏桶算法實際不同的是，令牌桶不僅能夠在限制客戶端請求流量速率的同時還能允許一定程度的突發流量。限流和允許瞬時流量其實并不矛盾，在大多數場景中，小批量的突發流量系統是完全可以接受的
因為令牌桶算法中，發放令牌是持續不間斷的，當流量一直比較緩和時，桶能夠一直持有冗余的令牌，以應對突發流量。如果這時突發大流量，形成流量尖峰，這些請求進來可以直接拿到令牌去執行。只有超越系統閾值的流量，由于未獲得桶中的令牌，請求只能等待或者被拒絕，從而維護系統的穩定。
當然相較于漏桶算法，令牌桶算法，實現更為復雜，需要維護令牌的生成和消耗，還需要精確的時間控制(不然會影響限流的效果)，需要消耗更多的內存來儲存令牌
這里也提供一下代碼實現，單機下推薦使用(或者仿寫)Google Guava自帶的限流工具類RateLimiter
先引入依賴：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.0-jre</version>
</dependency>設置發放令牌的速率，然后直接調用tryAcquire，大家感興趣地可以看看其源碼實現
public class MyTokenBucketRateLimiterDemo {
public static void main(String[] args) throws InterruptedException {
// 每1s發放5個令牌到桶里
RateLimiter rateLimiter=RateLimiter.create(5);
for (int i=0; i < 10; i++) {
Thread.sleep(100L);
if(rateLimiter.tryAcquire()) {
System.out.println("get one token");
}else {
System.out.println("no token");
}
}
}
}本文上述提供的例子，僅適用于單機，如果是多機部署(分布式)場景下，算法還是可以采用上述算法，需要通過中間件將限流算法的參數信息(比如令牌桶、計數器等)改成存儲全局化，比如采用redis+lua的方式實現，或者使用開源工具比如redisson(內部封裝了基于Redis的限流)、Sentinel(帶有監控監控平臺)等
或者我們也可以利用nginx來從上層流量入口進行限流，它提供2個限流模塊ngx_http_limit_req_module，ngx_http_limit_conn_module
上述幾種限流算法都是業內常見的，各有優劣，我們需要理解每種方案的工作原理和特性，這樣可以能更好地根據項目具體的情況和多種因素，選擇合適的方案
全文完，感謝您的閱讀，點贊收藏在看就是對筆者最好的催更！
我們下期再見~
作者：小牛呼嚕嚕 ，關注公眾號「小牛呼嚕嚕」，更多高質量好文等你！
電腦出現故障，即便是老鳥也要研究半天才能找到原因(有時候根本就找不到)，比如突然網絡中斷，就得從軟到硬排查個遍，令人煩躁。
為了幫助用戶查找解決電腦故障，微軟也是一直不遺余力。Windows 10 v1809的時候，就引入了一個名為“Packet Monitor”(數據包監視器)的新功能，簡稱PacketMon，對應進程為pktmon.exe。
這是一個跨組件的網絡診斷工具，支持數據包捕捉、丟包檢測、數據包過濾與計數等，會捕捉通過網絡的每一個數據包，深入網絡堆棧內部，從而可以快速準確地檢測網絡故障根源，尤其適合大型網絡環境。
這個功能自誕生后一直在升級，而在最新的Windows 10 v2004版本中，它迎來了一次大規模更新，技能更加豐富：
－ 可在不同的網絡位置捕捉數據包
－ 支持丟包檢測，包括丟包原因報告
－ 運行時數據包篩選，包括封裝支持
－ 彈性數據包計數
－ 實時屏幕數據包監控
－ 大容量內存日志
－ 兼容網絡監視器(NetMon)、Wireshark(pcapng)
不過這個工具目前還有一些局限性，比如僅支持有線以太網而不支持Wi-Fi無線網絡，沒有集成防火墻，丟包檢測也僅限支持的組件。微軟承諾后續會不斷改進。