流量控制還能這么搞。。。

一個(gè)優(yōu)秀的RPC框架，流量控制是必不可少的功能之一。

在上一篇文章聊聊服務(wù)注冊與發(fā)現(xiàn)中，我們講了微服務(wù)架構(gòu)中核心功能之一服務(wù)注冊與發(fā)現(xiàn)。在本文中，我們將著重講下微服務(wù)的另外一個(gè)核心功能點(diǎn)：流量控制。

在微服務(wù)系統(tǒng)中，整個(gè)系統(tǒng)是以一系列固有功能的微服務(wù)組成，如果某一個(gè)服務(wù)，因?yàn)榱髁慨惓；蛘咂渌?，?dǎo)致響應(yīng)異常，那么同樣的也會(huì)影響到調(diào)用該服務(wù)的其他服務(wù)，從而引起了一系列連鎖反應(yīng)，最終導(dǎo)致整個(gè)系統(tǒng)崩潰。針對此種問題，我們在之前的文章微服務(wù)架構(gòu)之雪崩效應(yīng)有講解過解決方案，今天我們針對方案中的限流控制來進(jìn)行深入講解。

1引言

限流這件事，對于微服務(wù)架構(gòu)來說，最直接的就是跟系統(tǒng)承載能力正相關(guān)。任何系統(tǒng)都有它服務(wù)能力上限，如果在請求鏈路上，某個(gè)子服務(wù)的請求量超過其承載能力，那么該鏈路上的請求將無法正常響應(yīng)，而此時(shí)，如果在client端對于不能返回的請求不斷重試(retry)，那么對原本已經(jīng)超過負(fù)載上限的子服務(wù)來說，無異于雪上加霜。而這一的模式在拖垮了鏈路上的某個(gè)子服務(wù)后，可能會(huì)影響到其上游服務(wù)，導(dǎo)致影響范圍持續(xù)擴(kuò)大，進(jìn)而讓其它原本正常的服務(wù)也跟著失效，從而引起雪崩，雪崩效應(yīng)會(huì)加速整個(gè)系統(tǒng)無法提供服務(wù)。

解決這個(gè)問題的方式，就是限流。如果監(jiān)測到這個(gè)現(xiàn)象時(shí)候(錯(cuò)誤率增高，rt變大或者是服務(wù)負(fù)載高于其安全閾值)，就直接開啟某些策略，在服務(wù)負(fù)載恢復(fù)前，丟棄新的request，以使得整個(gè)系統(tǒng)安全可靠。這個(gè)就是限流的目的。不過，這個(gè)機(jī)制困難的不在于要挑選哪種框架或者給某個(gè)服務(wù)來使用，而是是否有辦法精準(zhǔn)掌握系統(tǒng)內(nèi)各個(gè)子服務(wù)的負(fù)載上限，并且有能力做好整合，進(jìn)一步做到自動(dòng)化調(diào)節(jié)限流策略。

2概念

在解釋什么是限流之前，我們先了解一個(gè)點(diǎn)，就是服務(wù)的請求上限，也可以理解為是服務(wù)承載量，即該服務(wù)支持一定時(shí)間內(nèi)最多能夠支持多少請求。只有將服務(wù)承載量進(jìn)行量化，能夠被測量，才能根據(jù)這個(gè)測量值，采取一定的對應(yīng)措施。

服務(wù)承載量，指的是單位時(shí)間內(nèi)的處理量。北京地鐵早高峰，地鐵站都會(huì)做一件事情，就是限流了！想法很直接，就是想在一定時(shí)間內(nèi)把請求限制在一定范圍內(nèi)，保證系統(tǒng)不被沖垮，同時(shí)盡可能提升系統(tǒng)的吞吐量。

再以我家里的帶寬為例，是聯(lián)通100m的，也就是說，每一秒鐘，聯(lián)通提供最大100m bits的數(shù)據(jù)傳輸量。那么聯(lián)通是如何限制這個(gè)上限的呢？假如我是聯(lián)通，可能有以下幾個(gè)方面：

• 每秒總共傳輸量，在1秒內(nèi)只要不超過100m bits，能傳多快就多塊
• 按照位來平均，每傳1bit需要花費(fèi)0.01ns，因此沒傳完1bits后必須得到0.01ns后才能繼續(xù)傳
• 只要60秒內(nèi)不超過60*100Mb就行
• ....

看到上面這些方案，就會(huì)發(fā)現(xiàn)，做到真正的限制，不是那么容易的。因?yàn)槊恳粋€(gè)方案實(shí)現(xiàn)原理都不同，也就意味著代碼實(shí)現(xiàn)不同。

現(xiàn)在，假如我們使用方案2來實(shí)現(xiàn)，等真正測試或者上線后，會(huì)崩潰吧，因?yàn)榱髁靠刂聘静皇窍裎覀冾A(yù)期的那樣進(jìn)行控制，這是因?yàn)橹匦掠?jì)算流量的過程有可能已經(jīng)超了0.01ns。顯然要盡可能精準(zhǔn)的控制流量，需要回答下面兩個(gè)問題：

• 如何定義流量的計(jì)算方式？是選擇1s、10s還是60s？
• 如果流量超了之后，該怎么做？是直接返回空值還是一個(gè)默認(rèn)值？

顯然，我們在想清楚上面兩個(gè)問題后，實(shí)現(xiàn)方案基本就能定下來了。收到了新的request，只要確認(rèn)目前的服務(wù)是否還有能力處理這個(gè)request即可。這個(gè)時(shí)候流量是直接丟棄，還是返回其他值，根據(jù)具體情況進(jìn)行具體分析。

3常用方式

限流常用的方式有：

• 計(jì)數(shù)器
• 滑動(dòng)窗口
• 漏桶
• 令牌桶

下面我將深入講解上述的四種限流方式，先講解原理，然后是實(shí)現(xiàn)，最后分析其特點(diǎn)。

4計(jì)數(shù)器

確定方法的最大訪問量MAX，每次進(jìn)入方法前計(jì)數(shù)器+1，將結(jié)果和最大并發(fā)量MAX比較，如果大于等于MAX，則直接返回；如果小于MAX，則繼續(xù)執(zhí)行。

計(jì)數(shù)器的實(shí)現(xiàn)方式，簡單粗暴。在一段時(shí)間內(nèi)，進(jìn)行計(jì)數(shù)，與閥值進(jìn)行比較，到了時(shí)間臨界點(diǎn)，將計(jì)數(shù)器清0。

在上圖中，我們以1分鐘即60秒為一個(gè)時(shí)間片，在該時(shí)間片內(nèi)最多處理請求為1000，如果超過了上限，則拒絕服務(wù)(具體依賴于實(shí)際業(yè)務(wù)場景)。

原理

我們將計(jì)數(shù)器的思路在明確下就是：

• 設(shè)置單位時(shí)間T（如10s）內(nèi)的最大訪問量req_max，在單位時(shí)間T內(nèi)維護(hù)計(jì)數(shù)器count；
• 當(dāng)請求到達(dá)時(shí)，判斷時(shí)間是否進(jìn)入下一個(gè)單位時(shí)間；
• 如果是，則重置計(jì)數(shù)器為0；
• 如果不是，計(jì)數(shù)器count,并判斷計(jì)數(shù)器count是否超過最大訪問量req_max，如超過，則拒絕訪問。

實(shí)現(xiàn)

針對上面的計(jì)數(shù)器原理，代碼實(shí)現(xiàn)如下：

class?CounterController?{
?public:
??CounterController(int?max,?int?duration)?{
????max_?=?max;
????duration_?=?duration;
????last_update_time_?=?time(nullptr);
??}

??bool?IsValid()?{
?????uint64_t?now?=?time(nullptr);
?????if?(now?????????++req_num_;
????????return?max_?>?req_num_;
?????}?else?{
???????last_update_time_?=?now;
???????req_num_?=?1;
???????return?max_?>?req_num_;
?????}
??}
?private:
??int?max_;
??int?duration_;
??int?last_update_time_;
??int?req_num_?=?0;
};

在實(shí)現(xiàn)代碼中，其中有四個(gè)成員變量：

• max_ 代表時(shí)間片內(nèi)最多處理的請求個(gè)數(shù)
• duration_ 代表時(shí)間片，單位為秒
• last_update_time_ 上一次更新計(jì)數(shù)器的時(shí)間
• req_num_ 當(dāng)前時(shí)間片內(nèi)的處理的請求數(shù)

其中，計(jì)數(shù)器限流方案的實(shí)現(xiàn)是在成員函數(shù)IsValid()中實(shí)現(xiàn)的，即為該次請求是否有效。在該函數(shù)中，我們首先判斷當(dāng)前時(shí)間戳與上次更新時(shí)間戳之差是否超過了時(shí)間片，如果當(dāng)前時(shí)間戳處于上次更新后的時(shí)間片內(nèi)，則請求數(shù)+1，然后判斷請求數(shù)是否超過了該時(shí)間片的處理上限。如果不處于上次更新后的時(shí)間片內(nèi)，則重置更新時(shí)間以及請求數(shù)。

特點(diǎn)

• 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，容易理解
• 缺點(diǎn)：
• 一段時(shí)間內(nèi)（不超過時(shí)間窗口）系統(tǒng)服務(wù)不可用。以圖一為例，時(shí)間片為60s，在時(shí)間片內(nèi)的第一秒內(nèi)，處理請求量就達(dá)到了上限，那么在后面的59s內(nèi)，所有的請求都將被拒絕
• 在時(shí)間片切換時(shí)刻，可能會(huì)產(chǎn)生兩倍于上限的請求。仍然以圖一為例，時(shí)間片為60s，在時(shí)間片內(nèi)的前59s都無請求過來，在第60s的時(shí)候來了1000個(gè)請求，然后時(shí)間片切換，在新的時(shí)間片內(nèi)的第一秒內(nèi)，來了1000個(gè)請求，也就是說在2秒內(nèi)(上一個(gè)時(shí)間片的最后一秒 + 當(dāng)前時(shí)間片的第一秒)來了2000個(gè)請求，這個(gè)時(shí)候明顯超過我們的時(shí)間片內(nèi)的上限值，可能導(dǎo)致系統(tǒng)崩潰

5滑動(dòng)窗口

計(jì)數(shù)器滑動(dòng)窗口算法是計(jì)數(shù)器固定窗口算法的改進(jìn)，解決了固定窗口切換時(shí)可能會(huì)產(chǎn)生兩倍于閾值流量請求的缺點(diǎn)。

滑動(dòng)窗口的意思是說把固定時(shí)間片，進(jìn)行劃分，并且隨著時(shí)間的流逝，進(jìn)行移動(dòng)，這樣就巧妙的避開了計(jì)數(shù)器的臨界點(diǎn)問題。也就是說這些固定數(shù)量的可以移動(dòng)的格子，將會(huì)進(jìn)行計(jì)數(shù)判斷閥值，因此格子的數(shù)量影響著滑動(dòng)窗口算法的精度。

在TCP中，也使用了滑動(dòng)窗口來進(jìn)行網(wǎng)絡(luò)流量控制，感興趣的同學(xué)可以閱讀TCP之滑動(dòng)窗口原理。

計(jì)數(shù)器方式是一種特殊的滑動(dòng)窗口，其窗口大小為1個(gè)時(shí)間片;

原理

滑動(dòng)窗口算法在固定窗口的基礎(chǔ)上，將一個(gè)計(jì)時(shí)窗口分成了若干個(gè)小窗口，然后每個(gè)小窗口維護(hù)一個(gè)獨(dú)立的計(jì)數(shù)器。當(dāng)請求的時(shí)間大于當(dāng)前窗口的最大時(shí)間時(shí)，則將計(jì)時(shí)窗口向前平移一個(gè)小窗口。平移時(shí)，將第一個(gè)小窗口的數(shù)據(jù)丟棄，然后將第二個(gè)小窗口設(shè)置為第一個(gè)小窗口，同時(shí)在最后面新增一個(gè)小窗口，將新的請求放在新增的小窗口中。同時(shí)要保證整個(gè)窗口中所有小窗口的請求數(shù)目之后不能超過設(shè)定的閾值。

實(shí)現(xiàn)

class?SlidingWindowController?{
?public:
??SlidingWindowController(int?window_size,?int?limit,?int?split_num)?{
????limit_?=?limit;
????window_size_?=?window_size;
????counters_.resize(split_num);
????split_num_?=?split_num;
??}

??int?IsValid()?{
????uint64_t?now_ms?=?0;
????GetCurrentTimeMs(&now_ms);
????int?window_num?=?std::max(now_ms?-?window_size_?-?start_time_,?0)?/?(window_size_?/?split_num_);

????SlidingWindow(window_num);

????int?count?=?0;
????for(int?i?=?0;i?????????count?+=?counters_[i];
????}

????if(count?>=?limit){
??????return?false;
????}else{
??????counters_[index]?++;
??????return?true;
????}

????return?true;
??}
?private:
??void?SlidingWindow(int?window_num)?{
????if?(window_num?==?0)?{
??????return;
????}

????int?slide_num?=?std::min(window_num,?split_num_);

????for?(int?i?=?0;?i???????index_?=?(index_?+?1)?%?split_num;
??????counters_[index_]?=?0;
????}

????start_time_?=?start_time_?+?wind_num?*?(window_size_?/?split_num_);?//?更新滑動(dòng)窗口時(shí)間
??}
??
??int?window_size_;?//?窗口大小，單位為毫秒
??int?limit_;?//?窗口內(nèi)限流大小
??std::vector?counters_;
??uint64_t?start_time_;?//?窗口開始時(shí)間
??int?index_?=?0;?//?當(dāng)前窗口計(jì)時(shí)器索引
??int?split_num_;
};

特點(diǎn)

• 避免了計(jì)數(shù)器固定窗口算法固定窗口切換時(shí)可能會(huì)產(chǎn)生兩倍于閾值流量請求的問題
• 實(shí)現(xiàn)精度依賴于窗口的細(xì)分粒度，分的越細(xì)，即窗口分塊越多，控制的流量越平滑

6漏桶

漏桶算法思路很簡單，水（請求）先進(jìn)入到漏桶里，漏桶以一定的速度出水，當(dāng)水流入速度過大會(huì)直接溢出，可以看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率。

以固定速率從桶中流出水滴，以任意速率往桶中放入水滴，桶容量大小是不會(huì)發(fā)生改變的。

流入：以任意速率往桶中放入水滴。

流出：以固定速率從桶中流出水滴。

因?yàn)橥爸械娜萘渴枪潭ǖ模绻魅胨蔚乃俾?流出的水滴速率，桶中的水滴可能會(huì)溢出。那么溢出的水滴請求都是拒絕訪問的，或者直接調(diào)用服務(wù)降級方法。前提是同一時(shí)刻。

但是對于很多場景來說，除了要求能夠限制數(shù)據(jù)的平均傳輸速率外，還要求允許某種程度的突發(fā)傳輸。這時(shí)候漏桶算法可能就不合適了，令牌桶算法更為適合。

原理

請求來了之后會(huì)首先進(jìn)到漏斗里，然后漏斗以恒定的速率將請求流出進(jìn)行處理，從而起到平滑流量的作用。當(dāng)請求的流量過大時(shí)，漏斗達(dá)到最大容量時(shí)會(huì)溢出，此時(shí)請求被丟棄。從系統(tǒng)的角度來看，我們不知道什么時(shí)候會(huì)有請求來，也不知道請求會(huì)以多大的速率來，這就給系統(tǒng)的安全性埋下了隱患。但是如果加了一層漏斗算法限流之后，就能夠保證請求以恒定的速率流出。在系統(tǒng)看來，請求永遠(yuǎn)是以平滑的傳輸速率過來，從而起到了保護(hù)系統(tǒng)的作用。

實(shí)現(xiàn)

class?LeakyBucketController?{
?public:
??LeakyBucketController(int?rate)?{
????capacity_?=?rate;
????last_update_time_?=?time(nullptr);
??}

??bool?IsValid()?{

????//?計(jì)算這段時(shí)間，漏了多少水
????uint64_t?now?=?time(nullptr);
????int?out?=?(new?-?last_update_time_)?*?rate;
????if?(out?>?0)?{
??????last_update_time_?=?now;
????}

????//?計(jì)算桶中剩余的水
????water_?=?std::max(0,?water_?-?out);

????//?如果桶沒有滿，則表示有效
????if?(water_???????++water_;
??????return?true;
????}

????return?false;
??}

?private:
??int?capacity_;
??int?water_?=?0;
??uint64_t?last_update_time_;
};

特點(diǎn)

• 漏桶的漏出速率是固定的 由于漏出速率固定，因此即使流量流入速率不定，但是經(jīng)過漏斗之后，變成了有固定速率的穩(wěn)定流量，可以對下游系統(tǒng)起到保護(hù)作用

• 不能解決流量突發(fā)的問題。假設(shè)我們設(shè)置漏斗速率為10個(gè)/秒，桶的容量為50個(gè)。此時(shí)突然來了100個(gè)請求，那么只有50個(gè)請求被接收，另外50個(gè)被拒絕。這個(gè)時(shí)候，你可能會(huì)認(rèn)為瞬間接受了50個(gè)請求，不就解決了流量突發(fā)問題么？不，這50個(gè)請求只是被接受了，但是沒有馬上被處理，處理的速度仍然是我們設(shè)定的10個(gè)/秒，所以沒有解決流量突發(fā)的問題。而接下來我們要談的令牌桶算法能夠在一定程度上解決流量突發(fā)的問題。

7令牌桶

令牌桶算法是對漏斗算法的一種改進(jìn)，除了能夠起到限流的作用外，還允許一定程度的流量突發(fā)。

令牌桶算法是以恒定的速率將令牌放入桶中，這個(gè)時(shí)候如果來了突發(fā)流量，如果桶中有令牌，則可以直接獲取令牌，并處理請求，基于該原理，就解決了漏桶算法中不能 處理突發(fā)流量 的問題。

原理

在令牌桶算法中，令牌以恒定速率放入桶中。桶也有一定的容量，如果滿了令牌就無法放進(jìn)去了。當(dāng)請求來了之后，會(huì)受限到桶中去拿令牌，如何取到了令牌，則該請求被處理，并消耗掉拿到的令牌，否則，該請求被丟棄。

實(shí)現(xiàn)

class?TokenBucketController?{
?public:
??TokenBucketController(int?num,?uint64_t?duration)?:
????duration_(duration),?rate_(num?>?0???(num?/?duration_?/?1000)?:?0),??
????limit_(num),?modulo_(num?>?0??(num?%?(duration?*?1000))?:?0)?{
????GetCurrentTimeMs(&last_update_time_);
????::curr_idx?=?0;
??}

??bool?IsValid();
?private:
??void?Update();

??const?uint64_t?duration_;
??const?int?rate_;
??const?int?limit_;
??const?uint64_t?modulo_;
??uint64_t?last_update_time_;
??uint64_t?loss_?=?0;
??uint64_t?counts_?=?0;
};

void?TokenBucketController::Update()?{
??uint64_t?cur_time_ms;
??GetCurrentTimeMs(&cur_time_ms);
??uint64_t?time_passed_since_last_update?=?cur_time_ms?-?last_update_time_;

??if?(time_passed_since_last_update?==?0)?{
????return;
??}

??if?(counts_?==?static_cast(limit_))?{
????last_update_time_?=?cur_time_ms;
????return;
??}

??uint64_t?count_to_add?=?rate_?*?time_passed_since_last_update;
??loss_?+=?modulo_?*?time_passed_since_last_update;

??if?(loss_?>=?duration_?*?1000)?{
????count_to_add?+=?loss_?/?duration_?/?1000;
????loss_?%=?(duration_?*?1000);
??}

??counts_?+=?count_to_add;
??if?(counts_?>?static_cast(limit_))?{
????counts_?=?limit_;
??}


??last_update_time_?=?cur_time_ms;
}

bool?TokenBucketController::IsValid()?{

??if?(limit_?????return?true;
??}

??if?(counts_?>=?1)?{
????counts_?-=?1;
????return?true;
??}

??Update();

??if?(counts_?>=?1)?{
????counts_?-=?1;
????return?true;
??}

??return?false;
}

在實(shí)現(xiàn)上，令牌桶跟漏桶的區(qū)別，是一個(gè)控制進(jìn)，一個(gè)控制出。在InValid函數(shù)中，先判斷桶中是否有令牌，如果有則返回true，否則，進(jìn)行更新桶中令牌(Update函數(shù))，然后再進(jìn)行判斷是否有令牌可用。

特點(diǎn)

令牌桶算法來作為限流，在業(yè)界使用最多，除了能夠在限制調(diào)用的平均速率的同時(shí)還允許一定程度的流量突發(fā)。

8結(jié)語

下面我們把本文中的四種限流策略做下簡單對比，來作為對本文的一個(gè)總結(jié)。計(jì)數(shù)器算法：該算法實(shí)現(xiàn)簡單，容易理解。但是在時(shí)間片切換時(shí)刻，容易出現(xiàn)兩倍于閾值的流量，也可以說是滑動(dòng)窗口算法的簡版(窗口只有一個(gè))。

滑動(dòng)窗口算法：解決了計(jì)數(shù)器算法中的2倍閾值的問題，其流量控制精度依賴于窗口個(gè)數(shù)，窗口個(gè)數(shù)越多，精度控制越準(zhǔn)。

漏桶算法：以任意速率往桶中放入水滴，如果桶中的水滴沒有滿的話，可以訪問服務(wù)，不能處理突發(fā)流量。

令牌桶算法：以固定的速率(平均速率)生成對應(yīng)的令牌放到桶中，客戶端只需要在桶中獲取到令牌后，就可以訪問服務(wù)請求，與漏桶算法相比，其可以處理一定的突發(fā)流量。

令牌桶算法是通過控制令牌生成的速度進(jìn)行限流，

漏桶算法是控制請求從桶中流出的速度進(jìn)行限流。

簡單理解為：令牌桶控制進(jìn)，漏桶控制出。

如果要讓自己的系統(tǒng)不被打垮，用令牌桶。如果保證被別人的系統(tǒng)不被打垮，用漏桶算法。

以上四種限流算法都有自身的特點(diǎn)，具體使用時(shí)還是要結(jié)合自身的場景進(jìn)行選取，沒有最好的算法，只有最合適的算法。比如令牌桶算法一般用于保護(hù)自身的系統(tǒng)，對調(diào)用者進(jìn)行限流，保護(hù)自身的系統(tǒng)不被突發(fā)的流量打垮。如果自身的系統(tǒng)實(shí)際的處理能力強(qiáng)于配置的流量限制時(shí)，可以允許一定程度的流量突發(fā)，使得實(shí)際的處理速率高于配置的速率，充分利用系統(tǒng)資源。而漏斗算法一般用于保護(hù)第三方的系統(tǒng)，比如自身的系統(tǒng)需要調(diào)用第三方的接口，為了保護(hù)第三方的系統(tǒng)不被自身的調(diào)用打垮，便可以通過漏斗算法進(jìn)行限流，保證自身的流量平穩(wěn)的打到第三方的接口上。

算法是死的，而算法中的思想精髓才是值得我們學(xué)習(xí)的。實(shí)際的場景中完全可以靈活運(yùn)用，還是那句話，沒有最好的算法，只有最合適的算法。