阿里雲二面:你對限流了解多少?
今天來說說限流的相關內容,包括常見的限流算法、單機限流場景、分佈式限流場景以及一些常見限流組件。
當然在介紹限流算法和具體場景之前我們先得明確什麼是限流,爲什麼要限流?。
任何技術都要搞清它的來源,技術的產生來自痛點,明確痛點我們才能抓住關鍵,對症下藥。
限流是什麼?
首先來解釋下什麼是限流?
在日常生活中限流很常見,例如去有些景區玩,每天售賣的門票數是有限的,例如 2000 張,即每天最多隻有 2000 個人能進去遊玩。
那在我們工程上限流是什麼呢?限制的是 「流」,在不同場景下「流」的定義不同,可以是每秒請求數、每秒事務處理數、網絡流量等等。
而通常我們說的限流指代的是 限制到達系統的併發請求數,使得系統能夠正常的處理 部分 用戶的請求,來保證系統的穩定性。
限流不可避免的會造成用戶的請求變慢或者被拒的情況,從而會影響用戶體驗。
因此限流是需要在用戶體驗和系統穩定性之間做平衡的,即我們常說的 trade off
。
對了,限流也稱流控(流量控制)。
爲什麼要限流?
前面,我們提到限流是爲了保證系統的穩定性。
日常的業務上有類似秒殺活動、雙十一大促或者突發新聞等場景,用戶的流量突增,後端服務的處理能力是有限的,如果不能處理好突發流量,後端服務很容易就被打垮。
亦或是爬蟲等不正常流量,我們對外暴露的服務都要以最大惡意去防備調用者。
我們不清楚調用者會如何調用我們的服務,假設某個調用者開幾十個線程一天二十四小時瘋狂調用你的服務,如果不做啥處理咱服務也算完了,更勝的還有 DDos 攻擊。
還有對於很多第三方開放平臺來說,不僅僅要防備不正常流量,還要保證資源的公平利用,一些接口都免費給你用了,資源都不可能一直都被你佔着吧,別人也得調的。
高德開放平臺流量限制說明
當然加錢的話好商量。
題外話
在之前公司還做過一個系統,當時 SaaS 版本還沒出來,因此係統需要部署到客戶方。
當時老闆的要求是,我們需要給他個限流降級版本。
不但系統給出的方案是降級後的方案,核心接口每天最多隻能調用 20 次,還需要限制系統所在服務器的配置和數量,即限制部署的服務器的 CPU 核數等。
還限制所有部署的服務器數量,防止客戶集羣部署,提高系統的性能。
當然這一切需要能動態配置,因爲加錢的話好商量。客戶一直都不知道。
估計老闆在等客戶說感覺系統有點慢吧。然後就搞個 2.0 版本?我讓我們研發部加班加點給你搞出來。
小結一下
限流的本質是因爲後端處理能力有限,需要截掉超過處理能力之外的請求,亦或是爲了均衡客戶端對服務端資源的公平調用,防止一些客戶端餓死。
常見的限流算法
有關限流算法我給出了對應的圖解和相關僞代碼,有些人喜歡看圖,有些人更喜歡看代碼。
計數限流
最簡單的限流算法就是計數限流了。
例如系統能同時處理 100 個請求,保存一個計數器,處理了一個請求,計數器就加一,一個請求處理完畢之後計數器減一。
每次請求來的時候看看計數器的值,如果超過閾值就拒絕。
非常簡單粗暴,計數器的值要是存內存中就算單機限流算法。
如果放在第三方存儲裏,例如 Redis 中,集羣機器訪問就算分佈式限流算法。
優點就是:簡單粗暴,單機在 Java 中可用 Atomic 等原子類、分佈式就 Redis incr。
缺點就是:假設我們允許的閾值是 1 萬,此時計數器的值爲 0, 當 1 萬個請求在前 1 秒內一股腦兒的都湧進來,這突發的流量可是頂不住的。
緩緩地增加流量處理和一下子湧入對於程序來說是不一樣的。
計數器限流僞代碼實現
而且一般的限流都是爲了限制在指定時間間隔內的訪問量,因此還有個算法叫固定窗口。
固定窗口限流
它相比於計數限流主要是多了個時間窗口的概念,計數器每過一個時間窗口就重置。規則如下:
-
請求次數小於閾值,允許訪問並且計數器 +1;
-
請求次數大於閾值,拒絕訪問;
-
這個時間窗口過了之後,計數器清零;
固定窗口限流僞代碼實現
看起來好像很完美,實際上還是有缺陷的。
固定窗口臨界問題
假設系統每秒允許 100 個請求,假設第一個時間窗口是 0-1s,在第 0.55s 處一下次湧入 100 個請求,過了 1 秒的時間窗口後計數清零,此時在 1.05 s 的時候又一下次湧入 100 個請求。
雖然窗口內的計數沒超過閾值,但是全局來看在 0.55s-1.05s 這 0.1 秒內湧入了 200 個請求,這其實對於閾值是 100/s 的系統來說是無法接受的。
固定窗口
爲了解決這個問題引入了滑動窗口限流。
滑動窗口限流
滑動窗口限流解決固定窗口臨界值的問題,可以保證在任意時間窗口內都不會超過閾值。
相對於固定窗口,滑動窗口除了需要引入計數器之外還需要記錄時間窗口內每個請求到達的時間點,因此對內存的佔用會比較多。
規則如下,假設時間窗口爲 1 秒:
-
記錄每次請求的時間
-
統計每次請求的時間 至 往前推 1 秒這個時間窗口內請求數,並且 1 秒前的數據可以刪除。
-
統計的請求數小於閾值就記錄這個請求的時間,並允許通過,反之拒絕。
滑動窗口
滑動窗口僞代碼實現
但是滑動窗口和固定窗口都無法解決短時間之內集中流量的突擊。
我們所想的限流場景是:
每秒限制 100 個請求。希望請求每 10ms 來一個,這樣我們的流量處理就很平滑,但是真實場景很難控制請求的頻率,因此可能存在 5ms 內就打滿了閾值的情況。
當然對於這種情況還是有變型處理的,例如設置多條限流規則。不僅限制每秒 100 個請求,再設置每 10ms 不超過 2 個。
再多說一句,這個滑動窗口可與 TCP 的滑動窗口不一樣。
TCP 的滑動窗口是接收方告知發送方自己能接多少 “貨”,然後發送方控制發送的速率。
接下來再說說漏桶,它可以解決時間窗口類的痛點,使得流量更加平滑。
漏桶算法
如下圖所示,水滴持續滴入漏桶中,底部定速流出。
如果水滴滴入的速率大於流出的速率,當存水超過桶的大小的時候就會溢出。
規則如下:
-
請求來了放入桶中
-
桶內請求量滿了拒絕請求
-
服務定速從桶內拿請求處理
漏桶
漏桶僞代碼實現
可以看到水滴對應的就是請求。
它的特點就是寬進嚴出,無論請求多少,請求的速率有多大,都按照固定的速率流出,對應的就是服務按照固定的速率處理請求。
“他強任他強,老子尼克楊”。
看到這想到啥,是不是和消息隊列思想有點像,削峯填谷。
一般而言漏桶也是由隊列來實現的,處理不過來的請求就排隊,隊列滿了就開始拒絕請求。
看到這又想到啥,線程池不就是這樣實現的嘛?
經過漏洞這麼一過濾,請求就能平滑的流出,看起來很像很挺完美的?實際上它的優點也即缺點。
面對突發請求,服務的處理速度和平時是一樣的,這其實不是我們想要的。
在面對突發流量我們希望在系統平穩的同時,提升用戶體驗即能更快的處理請求,而不是和正常流量一樣,循規蹈矩的處理(看看,之前滑動窗口說流量不夠平滑,現在太平滑了又不行,難搞啊)。
而令牌桶在應對突擊流量的時候,可以更加的 “激進”。
令牌桶算法
令牌桶其實和漏桶的原理類似,只不過漏桶是定速地流出,而令牌桶是定速地往桶裏塞入令牌,然後請求只有拿到了令牌才能通過,之後再被服務器處理。
當然令牌桶的大小也是有限制的,假設桶裏的令牌滿了之後,定速生成的令牌會丟棄。
規則:
-
定速的往桶內放入令牌
-
令牌數量超過桶的限制,丟棄
-
請求來了先向桶內索要令牌,索要成功則通過被處理,反之拒絕
令牌桶
看到這又想到啥?Semaphore 信號量啊,信號量可控制某個資源被同時訪問的個數,其實和咱們拿令牌思想一樣,一個是拿信號量,一個是拿令牌。
只不過信號量用完了返還,而咱們令牌用了不歸還,因爲令牌會定時再填充。
再來看看令牌桶的僞代碼實現,可以看出和漏桶的區別就在於一個是加法,一個是減法。
令牌桶僞代碼實現
可以看出令牌桶在應對突發流量的時候,桶內假如有 100 個令牌,那麼這 100 個令牌可以馬上被取走,而不像漏桶那樣勻速的消費。所以在應對突發流量的時候令牌桶表現的更佳。
限流算法小結
上面所述的算法其實只是這些算法最粗略的實現和最本質的思想,在工程上其實還是有很多變型的。
從上面看來好像漏桶和令牌桶比時間窗口算法好多了,那時間窗口算法有啥子用,扔了扔了?
並不是的,雖然漏桶和令牌桶對比時間窗口對流量的整形效果更佳,流量更加得平滑,但是也有各自的缺點(上面已經提到了一部分)。
拿令牌桶來說,假設你沒預熱,那是不是上線時候桶裏沒令牌?沒令牌請求過來不就直接拒了麼?
這就誤殺了,明明系統沒啥負載現在。
再比如說請求的訪問其實是隨機的,假設令牌桶每 20ms 放入一個令牌,桶內初始沒令牌,這請求就剛好在第一個 20ms 內有兩個請求,再過 20ms 裏面沒請求,其實從 40ms 來看只有 2 個請求,應該都放行的,而有一個請求就直接被拒了。
這就有可能造成很多請求的誤殺,但是如果看監控曲線的話,好像流量很平滑,峯值也控制的很好。
再拿漏桶來說,漏桶中請求是暫時存在桶內的,這其實不符合互聯網業務低延遲的要求。
所以漏桶和令牌桶其實比較適合阻塞式限流場景,即沒令牌我就等着,這樣就不會誤殺了,而漏桶本就是等着,比較適合後臺任務類的限流。
而基於時間窗口的限流比較適合對時間敏感的場景,請求過不了您就快點兒告訴我,等的花兒都謝了 (給阿姨倒一杯卡布奇諾。爲什麼我會突然打這句話??)。
單機限流和分佈式限流
本質上單機限流和分佈式限流的區別其實就在於 “閾值” 存放的位置。
單機限流就上面所說的算法直接在單臺服務器上實現就好了,而往往我們的服務是集羣部署的。
因此需要多臺機器協同提供限流功能。
像上述的計數器或者時間窗口的算法,可以將計數器存放至 Redis 等分佈式 K-V 存儲中。
例如滑動窗口的每個請求的時間記錄可以利用 Redis 的 zset
存儲,利用ZREMRANGEBYSCORE
刪除時間窗口之外的數據,再用 ZCARD
計數。
像令牌桶也可以將令牌數量放到 Redis 中。
不過這樣的方式等於每一個請求我們都需要去Redis
判斷一下能不能通過,在性能上有一定的損耗。
所以有個優化點就是 「批量獲取」,每次取令牌不是一個一取,而是取一批,不夠了再去取一批,這樣可以減少對 Redis 的請求。
不過要注意一點,批量獲取會導致一定範圍內的限流誤差。比如你取了 10 個此時不用,等下一秒再用,那同一時刻集羣機器總處理量可能會超過閾值。
其實「批量」這個優化點太常見了,不論是 MySQL 的批量刷盤,還是 Kafka 消息的批量發送還是分佈式 ID 的高性能發號,都包含了「批量」的思想。
當然,分佈式限流還有一種思想是平分,假設之前單機限流 500,現在集羣部署了 5 臺,那就讓每臺繼續限流 500 唄,即在總的入口做總的限流限制,然後每臺機子再自己實現限流。
限流的難點
可以看到,每個限流都有個閾值,這個閾值如何定是個難點。
定大了服務器可能頂不住,定小了就 “誤殺” 了,沒有資源利用最大化,對用戶體驗不好。
我能想到的就是限流上線之後先預估個大概的閾值,然後不執行真正的限流操作,而是採取日誌記錄方式,對日誌進行分析查看限流的效果,然後調整閾值,推算出集羣總的處理能力,和每臺機子的處理能力 (方便擴縮容)。
然後將線上的流量進行重放,測試真正的限流效果,最終閾值確定,然後上線。
我之前還看過一篇耗子叔的文章,講述了在自動化伸縮的情況下,我們要動態地調整限流的閾值很難。
於是基於 TCP 擁塞控制的思想,根據請求響應在一個時間段的響應時間 P90 或者 P99 值來確定此時服務器的健康狀況,來進行動態限流。在他的 Ease Gateway 產品中實現了這套算法,有興趣的同學可以自行搜索。
其實真實的業務場景很複雜,需要限流的條件和資源很多,每個資源限流要求還不一樣。所以我上面就是嘴強王者
。
羅老師 V5
限流組件
一般而言,我們不需要自己實現限流算法來達到限流的目的,不管是接入層限流還是細粒度的接口限流,都有現成的輪子使用,其實現也是用了上述我們所說的限流算法。
比如Google Guava
提供的限流工具類 RateLimiter
,是基於令牌桶實現的,並且擴展了算法,支持預熱功能。
阿里開源的限流框架Sentinel
中的勻速排隊限流策略,就採用了漏桶算法。
Nginx 中的限流模塊 limit_req_zone
,採用了漏桶算法,還有 OpenResty 中的 resty.limit.req
庫等等。
具體的使用還是很簡單的,有興趣的同學可以自行搜索,對內部實現感興趣的同學可以下個源碼看看,學習下生產級別的限流是如何實現的。
最後
今天只是粗略講解了限流相關的內容,具體應用到工程還是有很多點需要考慮的,並且限流只是保證系統穩定性中的一個環節,還需要配合降級、熔斷等相關內容。
以後有機會再講講。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/XGHS3lRJKMJ52PSLZCfpAQ