高並發之限流，到底限的什麼鬼 （精品長文）
可能知道高並發系統需要限流這個東西，但具體是限制的什麼，該如何去做，還是臨摹兩可。我們接下來系統性的給它歸個小類，希望對你有所幫助。
google guava中提供了一個限流實現: RateLimiter，這個類設計的非常精巧，可以適用於我們日常業務中大多數流控的場景，但鑒於使用場景的多樣性，使用時也需要相當小心。
前面已經使用兩篇簡單的文章進行了預熱。
信號量限流，高並發場景不得不說的秘密
沒有預熱，不叫高並發，叫並發高
這次不同。本篇文章將詳細的，深入的介紹限流的各種場景和屬性，然後分析guava這個限流器的核心源碼，並對其特性進行總結。屬於稍高級的進階篇。
限流場景
弄清楚你要限制的資源，是這個過程中最重要的一環。我大體將它分為三類。
代理層
比如SLB、nginx或者業務層gateway等，都支持限流，通常是基於連接數（或者並發數）、請求數進行限流。限流的維度通常是基於比如IP地址、資源位置、用戶標誌等。更進一步，還可以根據自身負載情況動態調整限流的策略（基準）。
服務調用者
服務調用方，也可以叫做本地限流，客戶端可以限制某個遠端服務的調用速度，超過閾值，可以直接進行阻塞或者拒絕，是限流的協作方。
服務接收方
基本同上，流量超過系統承載能力時，會直接拒絕服務。通常基於應用本身的可靠性考慮，屬於限流的主體方。我們常說的限流，一般發生在此處。本文主要結合RateLimiter討論基於限流主體方的使用方式，其他的都類似。
限流策略
限流策略有時候很簡單，有時候又很複雜，但常見的就三種。其他的都是在這之上進行的改進和擴展。
根據並發級別限流
這是一種簡單的、易於實施的限流方式，可以使用我們前面提到的java信號量實現。它的使用場景也有著比較鮮明的特點：
1）每次請求，所需要的資源開支都比較均衡，比如，每個請求對CPU的消耗、IO消耗等，都差不多，請求的RT時間都基本接近。
2） 請求密度或稀疏或高頻，這個我們不去關注。
3）資源本身不需要繁瑣的初始化工作（預熱），或者初始化工作的開支可以忽略。(會增加複雜度)
4）對待流量溢出的策略比較簡單，通常是直接拒絕而不是等待，因為等待往往意味著故障。
這種策略通常在適用在流量的頂層組件上，比如代理層、中間件等對並發連接數的限制。而嘗試獲取憑證的超時時間，就叫做溢出等待。很上檔次很裝b的詞，對不對？
漏桶演算法
請求流量以不確定速率申請資源，程序處理以恆定的速率進行，就是漏桶演算法的基本原理。有點像製作冰激凌的過程。-.- 有關漏桶模型，大家可以去研究一下相關資料。
大體有以下幾個概念。
桶 buffer
請求首先嘗試進入隊列，如果隊列溢滿，則拒絕此請求。進入隊列以後，請求則等待執行。
由此可見，請求究竟何時被執行，還存在一些變數，這直接取決於隊列中pending的請求數。有時候，挑剔的設計者會考慮增加有關限制請求等待的時間閾值，這個時間就是請求入隊、出隊的最大時差。buffer的大小設計，通常與速率有直接關係。
漏：請求出隊
這個出隊，有些講究，不同的設計理念實現就有所不同。有搶佔式、有調度式。其中「搶佔式」就是處理線程（或者進程，比如nginx worker進程）在上一個請求處理完畢之後即從buffer隊列中poll新的請求，無論當前線程（或者進程）的處理速率是否超過設定的速率，這種策略下buffer大小就限定了速率的上限。
調度式，就比較易於理解，需要額外的調度線程（進程），並嚴格按照設定的速率，從buffer中獲取請求，並輪訓的方式將請求交給其他worker線程，如果已有的worker線程繁忙，則直接創建新線程，目的就是確保速率是有保障的，這種方式下，buffer大小主要取決於等待時間。
溢出
就是因為漏桶的速率限制比較穩定，所以其面臨流量突發（bursty）幾乎沒有應對能力，簡單來說，超出buffer，就直接拒絕。
多麼可憐的請求們。
流量突發
儘管buffer的設計在一定層面上兼顧流量突發，但是還是太脆弱了，比如某個瞬間，請求密度很高（最尷尬的就是，只大了一點），將buffer溢滿，或許buffer再「大一點點」就能夠在合理時間內被處理；對於請求方，就會有些迷惑，「我只不過是稍微超了一點，你就給了我一連串無法工作的信息，so nave!!!」。
這種策略，也很常用，但是通常適用在限流的協作方，也是就客戶端層面。請求發出之前，做流控，如果有溢出，就要用其他可靠的策略來保障結果，比如重試等；反正 「對面的服務壓垮了，別怪我，我很自律」。
令牌桶
設計模型，我就不再介紹，大家可以去wiki深入了解一下。
令牌桶的基本思想，跟老一輩的集體公社時代一樣，每個月的供銷是限額的，有資源才分配給個人，不足部分下個月再說，你可以排隊賒賬。
令牌的個數，就是可以允許獲取資源的請求個數（我們假設每個請求只需要一個令牌）。事實上，我們並不會真的去創建令牌實體，因為這是沒有必要的，我們使用帶有時間特徵的計數器來表示令牌的可用個數即可。跟漏桶演算法相比，令牌桶的「桶」不是用來buffer請求的、而是用來計量可用資源數量（令牌）的。雖然我們並不會創建令牌實體，但是仍然可以假想，這個桶內每隔X時間就會新增一定數量的令牌，如果沒有請求申請令牌，那麼這個令牌桶是會溢出的…你會發現，這個設計跟漏桶演算法從IO方向上是相反的。
那麼漏桶演算法的缺點，也正好成為了令牌桶的專長：流量突發；令牌桶成了buffer，如果請求密度低，或者處於冷卻狀態，那麼令牌桶就會溢滿，此後如果流量突發，則過去積累的結餘資源則可以直接被「借用」。
令牌桶演算法，使用場景很多，適應程度很高，現實中流量突發是常見的，而且從設計角度考慮，令牌桶更易於實現。回到正題，RateLimiter，就是一個基於令牌桶思想的實現。
我們的口子越縮越小，終於到正題了。
RateLimiter使用
guava的api已經把它的設計思想闡述的比較清楚了,但是這個注釋閱讀起來還是稍微有點「哲學派」,我們先看兩個栗子，然後從源碼層面看下它的設計原理。
//RateLimiter limiter = RateLimiter.create(10,2, TimeUnit.SECONDS);//QPS 100
RateLimiter limiter = RateLimiter.create(10);
long start = System.currentTimeMillis();
for (int i= 0; i < 30; i++) {
double time = limiter.acquire();
long after = System.currentTimeMillis() - start;
if (time > 0D) {
System.out.println(i + ",limited,等待:" + time + "，已開始" + after + "毫秒");
} else {
System.out.println(i + ",enough" + "，已開始" + after + "毫秒");
}
//模擬冷卻時間，下一次loop可以認為是bursty開始
if (i == 9) {
Thread.sleep(2000);
}
}
System.out.println("total time：" + (System.currentTimeMillis() - start));
此例為簡單的流控，只有一種資源，QPS為10；在實際業務場景中，可能不同的資源速率是不同的，我們可以創建N多個limeter各自服務於資源。
acquire()方法就是獲取一個令牌（源碼中使用permit，許可證），如果permit足夠，則直接返回而無需等待，如果不足，則等待1/QPS秒。
此外，你會發現， limiter並沒有類似於鎖機制中的release()方法 ，這意味著「只要申請，總會成功」、且退出時也無需歸還。
RateLimiter內部有兩種實現：（下文中，「資源」、「令牌」、「permits」為同一含義）
SmoothBursty
可以支持「突發流量」的限流器，即當限流器不被使用時間，可以額外存儲一些permits以備突發流量，當突發流量發生時可以更快更充分的使用資源，流量平穩後（或者冷卻期，積累的permits被使用完之後）速率處於限制狀態。
其重點就是，冷卻期間，permits會積累，且在突發流量時，可以消耗此前積累的permits而且無需任何等待。就像一個人，奔跑之後休息一段時間，再次起步可以有更高的速度。
由此可見，如果你的資源，冷卻（不被使用）一段時間之後，再次被使用時可以提供比正常更高的效率，這個時候，你可以使用SmoothBursty。
創建方式
RateLimiter.create(double permitsPerSecond)
結果類似
0,enough，已開始1毫秒
1,limited,等待:0.098623，已開始105毫秒
2,limited,等待:0.093421，已開始202毫秒
3,limited,等待:0.098287，已開始304毫秒
4,limited,等待:0.096025，已開始401毫秒
5,limited,等待:0.098969，已開始505毫秒
6,limited,等待:0.094892，已開始605毫秒
7,limited,等待:0.094945，已開始701毫秒
8,limited,等待:0.099145，已開始801毫秒
9,limited,等待:0.09886，已開始905毫秒
10,enough，已開始2908毫秒
11,enough，已開始2908毫秒
12,enough，已開始2908毫秒
13,enough，已開始2908毫秒
14,enough，已開始2908毫秒
15,enough，已開始2908毫秒
16,enough，已開始2908毫秒
17,enough，已開始2908毫秒
18,enough，已開始2908毫秒
19,enough，已開始2908毫秒
20,enough，已開始2909毫秒
21,limited,等待:0.099283，已開始3011毫秒
22,limited,等待:0.096308，已開始3108毫秒
23,limited,等待:0.099389，已開始3211毫秒
24,limited,等待:0.096674，已開始3313毫秒
25,limited,等待:0.094783，已開始3411毫秒
26,limited,等待:0.097161，已開始3508毫秒
27,limited,等待:0.099877，已開始3610毫秒
28,limited,等待:0.097551，已開始3713毫秒
29,limited,等待:0.094606，已開始3809毫秒
total time：3809
SmoothWarmingUp
具有warming up（預熱）特性，即突發流量發生時，不能立即達到最大速率，而是需要指定的「預熱時間」內逐步上升最終達到閾值；它的設計哲學，與SmoothBursty相反，當突發流量發生時，以可控的慢速、逐步使用資源（直到最高速率），流量平穩後速率處於限制狀態。
其重點是，資源一直被使用，那麼它可以持續限制穩定的速率；否則，冷卻時間越長（有效時長為warmup間隔）獲取permits時等待的時間越長，需要注意，冷卻時間會積累permits，但是獲取這些permits仍然需要等待。
由此可見，如果你的資源，冷卻（不被使用）一段時間之後，再次被使用時它需要一定的準備工作，此時它所能提供的效率比正常要低；比如鏈接池、資料庫緩存等。
創建方式
RateLimiter.create(double permitsPerSecond,long warnupPeriod,TimeUnit unit)
執行結果如下，可以看到有一個明顯的增長過程。
0,enough，已開始1毫秒
1,limited,等待:0.288847，已開始295毫秒
2,limited,等待:0.263403，已開始562毫秒
3,limited,等待:0.247548，已開始813毫秒
4,limited,等待:0.226932，已開始1041毫秒
5,limited,等待:0.208087，已開始1250毫秒
6,limited,等待:0.189501，已開始1444毫秒
7,limited,等待:0.165301，已開始1614毫秒
8,limited,等待:0.145779，已開始1761毫秒
9,limited,等待:0.128851，已開始1891毫秒
10,enough，已開始3895毫秒
11,limited,等待:0.289809，已開始4190毫秒
12,limited,等待:0.264528，已開始4458毫秒
13,limited,等待:0.247363，已開始4710毫秒
14,limited,等待:0.225157，已開始4939毫秒
15,limited,等待:0.206337，已開始5146毫秒
16,limited,等待:0.189213，已開始5337毫秒
17,limited,等待:0.167642，已開始5510毫秒
18,limited,等待:0.145383，已開始5660毫秒
19,limited,等待:0.125097，已開始5786毫秒
20,limited,等待:0.109232，已開始5898毫秒
21,limited,等待:0.096613，已開始5999毫秒
22,limited,等待:0.096321，已開始6098毫秒
23,limited,等待:0.097558，已開始6200毫秒
24,limited,等待:0.095132，已開始6299毫秒
25,limited,等待:0.095495，已開始6399毫秒
26,limited,等待:0.096352，已開始6496毫秒
27,limited,等待:0.098641，已開始6597毫秒
28,limited,等待:0.097883，已開始6697毫秒
29,limited,等待:0.09839，已開始6798毫秒
total time：6798
acquire方法源碼分析
上面兩個類都繼承自SmoothRateLimiter，最終繼承自RateLimiter；RateLimiter內部核心的方法：
1）double acquire()：獲取一個permit，如果permits充足則直接返回，否則等待1/QPS秒。此方法返回線程等待的時間（秒），如果返回0.0表示未限流、未等待。
2）double acquire(int n)：獲取n個permits，如果permits充足則直接返回，否則限流並等待，等待時間為「不足的permits個數 / QPS」。（暫且這麼解釋）
下面就是這個方法的偽代碼啦。
//偽代碼
public double acquire(int requiredPermits) {
long waitTime = 0L;
synchronized(mutex) {
boolean cold = nextTicketTime > now;
if (cold) {
storedPermits = 根據冷卻時長計算累積的permits;
nextTicketTime = now;
}
//根據storedPermits、requiredPermits計算需要等待的時間
//bursty：如果storePermits足夠，則waitTime = 0
//warmup：平滑預熱，storePermits越多（即冷卻時間越長），等待時間越長
if(storedPermits不足) {
waitTime += 欠缺的permits個數 / QPS;
}
if(bursty限流) {
waitTime += 0;//即無需額外等待
}
if(warmup限流) {
waitTime += requiredPermits / QPS;
if(storedPermits > 0.5 * maxPermits) {
waitTime += 阻尼時間;
}
}
nextTicketTime += waitTime
}
if (waitTime > 0L) {
Thread.sleep(waitTime);
}
return waitTime;
}
以下內容會比較枯燥～～～非常枯燥～～～
1、Object mutex：同步鎖，如上述偽代碼所示，在計算存量permits、實際申請permits（包括計算）的過程中全部是同步的；我們需要知道，RateLimiter內部確實使用了鎖同步機制。
2、maxPermits：最大可存儲的許可數量（tickets數量），SmoothBursty和SmoothWarimingUp默認實現中，有所不同：
1）SmoothBusty，其值為maxBurstSecond QPS，就是允許「突發流量持續時間」 QPS，這種設計可以理解，不過RateLimiter將maxBustSecond硬編碼為1.0，最終此值等於QPS。
2）SmoothWarmingUp：默認演算法值為warmupPeriod QPS，簡單說就是「預熱時長」 QPS。
此參數主要限制，無論冷卻多長時間，其storedPermits不能超過此值；此值在設定QPS之後，則不會再改變。
3、storedPermits：已存儲的permits數量，此值取決於冷卻時間，簡單來說冷卻的時間越久，此值越大，但不會超過maxPermits，起始值為0。
1）當一個請求，申請permit之前，將會計算上一次令牌申請（nexFreeTicketTime）的時間與now之間的時差，並根據令牌產生速率（1/QPS）計算此冷卻期間可以存儲的令牌數，也就是storedPermits。
2）permits申請完畢之後，將當前時間（如果需要等待，額外加上等待時間）作為下一次令牌申請的起始時間，此時冷卻時間結束。
3）申請完畢之後，storedPermits將會減去申請的permits個數，直到為0。
冷卻時長和申請頻次，都決定了storedPermits大小，其中冷卻時間會導致storePermits增加，acquire操作將導致storePermits減少。
4、nextFreeTicketMicros（時間戳，微妙單位）：下一個可以自由獲取的令牌的時間，此值可以為未來的某個時間，此時表示限流已經開始，部分請求已經在等待，此值主要用來標記「冷卻狀態」。（賒賬）
1）如果處於冷卻期，那麼此值通常是過去式，即此值小於now。
2）如果此時有請求申請permits，則會通過此值與now的時差，計算storedPermits，同時將此值設置為now。
3）如果此值是未來時刻，即大於now，則無需計算storedPermits，也無需重置此值。
4）申請tickets後，從storedPermits減去需要的tickets個數，如果觸發限速等待（比如預熱期、permits不足），則會將2）操作之後額外增加等待時間作為nextFreeTicketsTime值。
5）基於2），對於warmingUp限流，冷卻期之後的首個請求是不需要等待的，只是將此值設置為now + 阻尼性質的等待時間waitTime（），這意味著在此後waitTime期間再有請求，則會觸發等待，並繼續延續nextFreeTicketMicros值。此值的延續，在warming up期間，阻尼waitTime計算比較複雜，由1/QPS + 額外值，這個額外值，隨著預熱時間增長而減小。
6）基於2），對於bursty限流，如果storedPermits大於0，則總是不需要等待，只是簡單將此值設為為now；否則，則按照正常的1/QPS間隔計算其應該被推延的時間點。
5、對於warming up限流，將maxPermits * 0.5作為一個閾值分割線，當storedPermits小於此分割線時，在限流時使用正常等待時間（申請permits個數 / QPS）；在此分割線之上時，則4）增加額外阻尼，即預熱阻尼。
6、我們發現，RateLimiter內部並不會真的生成tickets實體，而是根據冷卻時長、在申請資源時才計算存量tickets（對應為storedPermits）。無論何種限流，storedPermits都是優先使用。
小總結
是時候總結一下了。
RateLimiter是線程安全的，所以在並發環境中可以直接使用，而無需額外的lock或者同步。
考慮到RateLimiter內部的同步鎖，我們通常在實際業務開發中，每個資源（比如URL）使用各自的RateLimiter而不是公用一個，佔用的內存也不大。
這個限流器內部無額外的線程，也沒有其他的數據結構用來存儲tickets實體，所以它非常的輕量級，這也是優勢所在。
RateLimiter最大的問題，就是acquire方法總會成功，內部的tickets時間點會向後推移； 如果並發很高，嚴重超過rate閾值時，後續被限流的請求，其等待時間將會基於時間線累加，導致等待時間不可控，這和信號量同病相憐。
為了避免上面的問題，我們通常先使用tryAcquired檢測，如果可行再去acquire；如果令牌不足，適當拒絕。所以 基於RateLimiter，並沒有內置的拒絕策略，這一點需要我們額外開發。
我們不能簡單依賴於acquire方法，來實現限流等待，否則這可能帶來嚴重問題。我們通常需要封裝RateLimiter，並使用額外的屬性記錄其是否「處於限流狀態」、「已經推延的tickets時間點」，如果「已經推延的時間點非常遙遠」且超過可接受範圍，則直接拒絕請求。簡單來說，封裝acquire方法，增加對請求可能等待時間的判斷，如果超長，則直接拒絕。
RateLimiter存在一個很大的問題，就是幾乎沒法擴展：子類均為protected。反射除外哦。
一個實踐
還是上一段代碼吧，能更加清晰的看到我們所做的工作： FollowCotroller.java：流控器，如果限流開始，則只能有max個請求因此而等待，超過此值則直接拒絕
public class FollowController {
private final RateLimiter rateLimiter;
private int maxPermits;
private Object mutex = new Object();
//等待獲取permits的請求個數，原則上可以通過maxPermits推算
private int maxWaitingRequests;
private AtomicInteger waitingRequests = new AtomicInteger(0);
public FollowController(int maxPermits,int maxWaitingRequests) {
this.maxPermits = maxPermits;
this.maxWaitingRequests = maxWaitingRequests;
rateLimiter = RateLimiter.create(maxPermits);
}
public FollowController(int permits,long warmUpPeriodAsSecond,int maxWaitingRequests) {
this.maxPermits = maxPermits;
this.maxWaitingRequests = maxWaitingRequests;
rateLimiter = RateLimiter.create(permits,warmUpPeriodAsSecond, TimeUnit.SECONDS);
}
public boolean acquire() {
return acquire(1);
}
public boolean acquire(int permits) {
boolean success = rateLimiter.tryAcquire(permits);
if (success) {
rateLimiter.acquire(permits);//可能有出入
return true;
}
if (waitingRequests.get() > maxWaitingRequests) {
return false;
}
waitingRequests.getAndAdd(permits);
rateLimiter.acquire(permits);
waitingRequests.getAndAdd(0 - permits);
return true;
}
}
以上代碼，都可以在github找到。
https://github.com/sayhiai/example-ratelimit
End
可以看到，guava提供了一個非常輕量而全面的限流器。它本身沒有使用多線程去實現，但它是線程安全的。相比較信號量，它的使用簡單的多。但鑒於限流場景的多樣性，使用時同樣要非常小心。
更多精彩文章。
微服務不是全部，只是特定領域的子集
這麼多監控組件，總有一款適合你
「分庫分表」 ？選型和流程要慎重，否則會失控
使用Netty，我們到底在開發些什麼？
Linux生產環境上，最常用的一套「vim「技巧
推薦閱讀：
