為什么要限流

限流在很多場景中用來限制并發(fā)和請求量独悴，比如說秒殺搶購述吸，保護自身系統(tǒng)和下游系統(tǒng)不被巨型流量沖垮等盏求。

以微博為例噪漾，例如某某明星公布了戀情,訪問從平時的50萬增加到了500萬，系統(tǒng)的規(guī)劃能力蜂莉，最多可以支撐200萬訪問,那么就要執(zhí)行限流規(guī)則,保證是一個系統(tǒng)的可用的狀態(tài),不至于服務(wù)器崩潰蜡娶，導(dǎo)致所有請求不可用。

常用的限流方案

廢話不多說映穗，直接進入正題窖张，常用的限流方案有計數(shù)器、滑動窗口蚁滋、令牌桶和漏桶4種算法宿接。

主要介紹這4種算法的原理、實現(xiàn)使用的數(shù)據(jù)結(jié)構(gòu)辕录、使用場景以及優(yōu)缺點睦霎。

計數(shù)器

1. 首先我們需要選定一個時間起點，之后每當有接口請求到來走诞，我們就將計數(shù)器加一碎赢。
2. 如果在當前時間窗口內(nèi)，根據(jù)限流規(guī)則（比如每秒鐘最大允許 100 次訪問請求）速梗，出現(xiàn)累加訪問次數(shù)超過限流值的情況時，我們就拒絕后續(xù)的訪問請求襟齿。
3. 當進入下一個時間窗口之后姻锁，計數(shù)器就清零重新計數(shù)。

這個算法雖然簡單猜欺，但是有一個十分致命的問題位隶，那就是臨界問題 : 無法應(yīng)對兩個時間窗口臨界時間內(nèi)的突發(fā)流量,我們看下圖：

假設(shè)我們的限流規(guī)則是，每秒鐘不能超過 100 次接口請求开皿。

第一個 1s 時間窗口內(nèi)涧黄，100 次接口請求都集中在最后 10ms 內(nèi)篮昧。

在第二個 1s 的時間窗口內(nèi)，100 次接口請求都集中在最開始的 10ms 內(nèi)笋妥。

雖然兩個時間窗口內(nèi)流量都符合限流要求（≤100 個請求）懊昨，但在兩個時間窗口臨界的 20ms 內(nèi)，會集中有 200 次接口請求春宣。固定時間窗口限流算法并不能對這種情況做限制酵颁，所以，集中在這 20ms 內(nèi)的 200 次請求就有可能壓垮系統(tǒng)月帝。

由于這種算法有嚴重的臨界問題躏惋，所以使用的場景如下：

1. 相對簡單的場景： 當系統(tǒng)相對簡單，對于計數(shù)器的高精度要求不是很高嚷辅，并且可以容忍一定的限流不準確性時簿姨，計數(shù)器限流算法是一個簡單且易于實現(xiàn)的方案。

2. 不需要極高精度的流控場景： 在某些場景下簸搞，對于請求的限流并不需要非常精確的控制扁位，而是希望通過一種簡單的方式控制系統(tǒng)的流量，這時計數(shù)器限流算法可能是一個可行的選擇攘乒。

3. 流量變化較緩慢的應(yīng)用： 如果系統(tǒng)的請求流量相對穩(wěn)定贤牛，且變化不是很大压储，那么計數(shù)器限流算法可能可以滿足需求皆疹。

滑動時間窗口

由于計數(shù)器算法有嚴重的臨界問題，不太適合高精度和復(fù)雜的場景俗壹。

為了解決這個問題沽讹，我們可以對固定時間窗口限流算法稍加改造般卑。我們可以限制任意時間窗口（比如 1s）內(nèi)，接口請求數(shù)都不能超過某個閾值（ 比如 100 次）爽雄。因此蝠检，相對于固定時間窗口限流算法，這個算法叫滑動時間窗口限流算法挚瘟。

我們假設(shè)限流的規(guī)則是叹谁，在任意 1s 內(nèi)，接口的請求次數(shù)都不能大于 K 次乘盖，即最大的qps為k焰檩。

那么要實現(xiàn)這一的一個算法，需要什么的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)呢订框？答案就是：循環(huán)隊列析苫，我們需要維護一個大小為 K+1 的循環(huán)隊列，用來記錄 1s 內(nèi)到來的請求。注意衩侥，這里循環(huán)隊列的大小等于限流次數(shù)加一国旷，因為循環(huán)隊列存儲數(shù)據(jù)時會浪費一個存儲單元。

實現(xiàn)了一個簡單的循環(huán)隊列代碼如下

public class Queue {
  private Long[] data;
  private int size = 0, head = 0, tail = 0;
  public Queue(int size) {
    this.data = new Long[size];
    this.size = size;
  }

  public boolean add(Long element) {
    if ((tail + 1) % size == head) return false;
    data[tail] = element;
    tail = (tail + 1) % size;
    return true;
  }

  public Long poll() {
    if (head == tail) return null;
    long ret = data[head];
    head = (head + 1) % size;
    return ret;
  }
}

public class Producer {
  private Queue queue;
  public Producer(Queue queue) {
    this.queue = queue;
  }

  public void produce(Long data) throws InterruptedException {
    while (!queue.add(data)) {
      Thread.sleep(100);
    }
  }
}

public class Consumer {
  private Queue queue;
  public Consumer(Queue queue) {
    this.queue = queue;
  }

  public void comsume() throws InterruptedException {
    while (true) {
      Long data = queue.poll();
      if (data == null) {
        Thread.sleep(100);
      } else {
        // TODO:...消費數(shù)據(jù)的業(yè)務(wù)邏輯...
      }
    }
  }
}

上面的介紹已經(jīng)知道時間滑動窗口算法使用的是循環(huán)隊列結(jié)構(gòu),上面也給出了循環(huán)隊列的實現(xiàn)代碼,那么該算法的具體執(zhí)行流程是什么呢茫死？

1. 先設(shè)置一個大小為k+1的循環(huán)隊列跪但。
2. 當有新的請求到來時，我們將與這個新請求的請求時間間隔超過 1s 的請求璧榄，從隊列中刪除（消息消費）特漩，刪除方式為從head頭節(jié)點順序遍歷查詢。
3. 第二步完成后骨杂，嘗試將新請求添加到隊頭head位置涂身。如果此時隊列已滿，則拒絕請求搓蚪；如果此時隊列未滿則正常插入請求蛤售。

可以發(fā)現(xiàn)滑動時間窗口算法一個特點：只有在新請求到來時，才會判斷隊列中的所有元素妒潭，哪些元素是可以正常消費的悴能。那么如果一直沒用新請求過來，隊列中的消息將永遠不會消費雳灾。

為了方便理解漠酿，結(jié)合下面這張圖來理解下吧。

使用場景： 滑動窗口算法適用于需要對請求的時間窗口內(nèi)流量進行限制的場景谎亩。它可以有效控制單位時間內(nèi)的請求頻率炒嘲。

令牌桶

令牌桶算法以一個設(shè)定的速率產(chǎn)生令牌并放入令牌桶，每次用戶請求都得申請令牌匈庭，如果令牌不足夫凸，則拒絕請求。

大致的流程如下：

1. 接口限制 t 秒內(nèi)最大訪問次數(shù)為 n阱持，則每隔 t/n 秒會放一個 token 到桶中夭拌；

2. 桶中最多可以存放 b 個 token，如果 token 到達時令牌桶已經(jīng)滿了衷咽，那么這個 token 會被丟棄鸽扁；如果令牌桶沒有滿時，該token會被加入到這個桶中镶骗。

3. 接口請求會先從令牌桶中取 token桶现，拿到 token 則處理接口請求，拿不到 token 則執(zhí)行限流卖词，拒絕請求或者是阻塞等待。

令牌桶算法是一直以固定速率往桶里加token，不管有沒有請求接口此蜈，直到桶滿為止即横。

正是由于上述的原因使令牌桶算法可以有效應(yīng)對突然流量,怎么理解有效應(yīng)對突然流量這句話呢？舉個例子

1. qps為1000裆赵，即1ms往桶內(nèi)增加一個token东囚。
2. 設(shè)置桶的容量為2000。
3. 假如1500ms之前一直都沒有流量請求战授，此時桶內(nèi)的token量積累為1500页藻。
4. 此時來了一波突發(fā)請求，大致為1500個植兰，那么所有的請求是可以都獲取到token的而不會被拒絕份帐。
5. 可以發(fā)現(xiàn)我們設(shè)置的qps為1000，但是卻滿足了1500的請求量楣导。這是這個現(xiàn)象废境，體現(xiàn)了令牌桶是可以應(yīng)對突發(fā)流量的。

令牌桶算法允許一定程度的突發(fā)流量筒繁。如果令牌桶中有足夠的令牌噩凹，系統(tǒng)可以處理更多的請求。這使得令牌桶算法在應(yīng)對短時的毡咏、不過分激烈的突發(fā)流量時比較靈活驮宴。然而，如果突發(fā)流量太過劇烈呕缭，令牌桶算法也有可能因為令牌桶被耗盡而進行限流堵泽。

上面的例子可以看出token是隨著時間的推移而增加，那么如果剛開始時來了一波突發(fā)請求臊旭，此時桶內(nèi)是沒有足夠的token的落恼，該怎么應(yīng)付這種情況呢？答案就是預(yù)熱桶：即剛開始時就往桶里放入一部分token离熏，而不是0 token的情況佳谦。

上面的介紹中其實忽略的一個重要的因素：桶容量。如果上面的流程中設(shè)置的桶容量為10000滋戳，且此時桶中token數(shù)也為最大值10000钻蔑，正好此時的突發(fā)流量也達到了10000，由于這些請求都可以獲取到token則所有流量都將會打到系統(tǒng)奸鸯，如果系統(tǒng)能承受的最大qps也就5000咪笑，那么此時系統(tǒng)將會發(fā)生奔潰。

令牌桶算法中桶的最大容量是一個關(guān)鍵參數(shù)娄涩，對系統(tǒng)的性能和流量控制都有影響窗怒。選擇桶的最大容量應(yīng)該根據(jù)具體的業(yè)務(wù)需求和系統(tǒng)的特點來合理設(shè)置映跟。

• 系統(tǒng)的處理能力： 桶的容量應(yīng)該能夠適應(yīng)系統(tǒng)的處理能力。桶容量太小將會導(dǎo)致合法的請求被拒絕扬虚。桶的容量較大努隙，在應(yīng)對突然流量時可能沖垮系統(tǒng)，應(yīng)該保證桶容量的最大值小于系統(tǒng)的最大承受能力辜昵。
• 系統(tǒng)的峰值流量： 考慮系統(tǒng)的峰值流量荸镊，設(shè)置桶的容量，使其足夠大以應(yīng)對可能的峰值請求堪置。
• 對突發(fā)流量的容忍度： 桶的容量也會影響系統(tǒng)對于突發(fā)流量的容忍度躬存。如果桶的容量較大，系統(tǒng)可以在短時間內(nèi)處理一些累積的請求舀锨，但這也可能導(dǎo)致一些短時刻內(nèi)的資源競爭岭洲。

經(jīng)過上面的探討，發(fā)現(xiàn)令牌桶算法適用的場景是：用于限制請求的整體速率雁竞，它具有一定的突發(fā)流量處理能力钦椭，可以應(yīng)對短時的流量峰值。

我相信介紹了這么多碑诉，肯定對令牌桶算法有了一些基本的了解彪腔，如果讓你實現(xiàn)一個這樣的算法，你會怎么設(shè)計呢进栽？我的大致思路如下：

1. 使用循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)來充當令牌桶德挣。
2. 循環(huán)隊列的大小： 可以設(shè)置為令牌桶的容量快毛，即桶中能夠存放的令牌的最大數(shù)量格嗅。
3. 令牌生成： 可以有一個單獨的線程，以固定的速率（比如每秒生成一定數(shù)量的令牌）向循環(huán)隊列中添加令牌(入隊)唠帝。在添加令牌時屯掖，需要考慮隊列已滿的情況，如果隊列已滿襟衰，則新生成的令牌不會被添加贴铜。
4. 請求處理： 當請求到達時，嘗試從循環(huán)隊列中取出一個令牌(出隊)瀑晒。如果隊列中有足夠的令牌绍坝，允許請求通過，并從隊列中取出一個令牌苔悦；如果隊列中沒有足夠的令牌轩褐，拒絕請求。

漏桶

漏桶算法限流的基本原理為：水（對應(yīng)請求）從進水口進入到漏桶里玖详，漏桶以一定的速度出水（請求放行）把介，當水流入速度過大勤讽，桶內(nèi)的總水量大于桶容量會直接溢出，請求被拒絕拗踢。
大致的漏桶限流規(guī)則如下：
（1）進水口（對應(yīng)客戶端請求）以任意速率流入進入漏桶地技。
（2）漏桶的容量是固定的，出水（放行）速率也是固定的秒拔。
（3）漏桶容量是不變的，如果處理速度太慢飒硅，桶內(nèi)水量會超出了桶的容量砂缩，則后面流入的水滴會溢出，表示請求拒絕三娩。

漏桶算法通過固定速率漏水的方式庵芭，對流量進行整形，限制了流量的速率雀监。漏桶算法相對來說對于限制整體速率和防止長時間的高速流量比較有效双吆，但對于短時的突發(fā)流量的處理相對較為嚴格。

和令牌桶算法相比会前，可以發(fā)現(xiàn)好乐，令牌桶可以應(yīng)對一些突發(fā)流量,而漏桶的是以固定速率在漏水，呈現(xiàn)的現(xiàn)象就是流量會非常平穩(wěn)瓦宜，防止突發(fā)流量對系統(tǒng)的沖擊蔚万，不會像令牌桶那樣出現(xiàn)突刺的情況。

這個漏桶有明顯的倆個作用：

• 削峰:有大量流量進入時,會發(fā)生溢出,從而限流保護服務(wù)可用

• 緩沖:不至于直接請求到服務(wù)器, 緩沖壓力

網(wǎng)上有一種說法是漏桶不能有效應(yīng)對突發(fā)流量临庇，但是能起到平滑突發(fā)流量（整流）的作用反璃。后半句話是沒有問題，但是我對前半句話有一點質(zhì)疑：

舉個例子假夺，比如此時桶沒有滿淮蜈，來了一大堆突發(fā)的流量，加入到桶內(nèi)時也沒有滿已卷，其實這些請求是不會被拒絕的梧田，只是會被固定速率消費而已，所以漏桶在一定程度上也是可以應(yīng)對突發(fā)流量的悼尾。

在漏桶算法中柿扣，桶的容量決定了系統(tǒng)能夠處理的瞬時峰值。當突發(fā)流量到來時闺魏，如果桶有足夠的空間未状，這些請求將被放入桶中，然后以固定速率被漏桶算法處理析桥。

然而司草，漏桶算法的特性主要是對整體速率進行控制艰垂，而不是對瞬時峰值進行緩沖。漏桶算法可以平滑流量埋虹，但并不會增加系統(tǒng)的處理能力猜憎。如果突發(fā)流量超過了桶的容量，那么超過容量的部分請求將被丟棄或拒絕搔课，漏桶并不能緩沖這些額外的請求胰柑。

漏桶也介紹的差不多了，如果讓你實現(xiàn)一個漏桶爬泥，你會怎么實現(xiàn)呢柬讨？首先同樣可以使用一個 循環(huán)隊列數(shù)據(jù)結(jié)構(gòu)來作為漏桶，大致思路如下：

1. 循環(huán)隊列的大小即漏桶的大小袍啡。
2. 請求過來時相當于入隊列踩官，直到循環(huán)隊列已滿，則拒絕請求繼續(xù)入隊列境输。
3. 起一個單獨的線程以固定的速率來消費隊列中的元素蔗牡，知道隊列中的元素為空時則阻塞。

參考

固定窗口限流和滑動窗口限流的實現(xiàn)
限流算法的實現(xiàn)