前言
Apache Dubbo 是由阿里開(kāi)源的一個(gè)RPC框架,除了基本的 RPC 功能以外,還提供了一整套的服務(wù)治理相關(guān)功能。目前它已經(jīng)是 Apache 基金會(huì)下的頂級(jí)項(xiàng)目。
而 dubbo-go 則是 Dubbo 的 Go 語(yǔ)言實(shí)現(xiàn)。
最近在 dubbo-go 的 todo list 上發(fā)現(xiàn),它還沒(méi)有實(shí)現(xiàn) TPS Limit 的模塊,于是就抽空實(shí)現(xiàn)了這個(gè)部分。
TPS limit 實(shí)際上就是限流,比如說(shuō)限制一分鐘內(nèi)某個(gè)接口只能訪問(wèn) 200 次,超過(guò)這個(gè)次數(shù),則會(huì)被拒絕服務(wù)。在 Dubbo 的 Java 版本上,只有一個(gè)實(shí)現(xiàn),就是 DefaultTPSLimiter 。
DefaultTPSLimiter 是在服務(wù)級(jí)別上進(jìn)行限流。雖然 Dubbo 的官方文檔里面聲稱可以在 method 級(jí)別上進(jìn)行限流,但是我看了一下它的源碼,實(shí)際上這個(gè)是做不到的。當(dāng)然,如果自己通過(guò)實(shí)現(xiàn) Filter 接口來(lái)實(shí)現(xiàn) method 級(jí)別的限流,那么自然是可以的——這樣暴露了 Dubbo Java 版本實(shí)現(xiàn)的另外一個(gè)問(wèn)題,就是 Dubbo 的 TpsLimitFilter 實(shí)現(xiàn),是不允許接入自己 TpsLimiter 的實(shí)現(xiàn)的。這從它的源碼也可以看出來(lái):
它直接寫(xiě)死了 TpsLimiter 的實(shí)現(xiàn)。
這個(gè)實(shí)現(xiàn)的目前只是合并到了 develop 上,等下次發(fā)布正式版本的時(shí)候才會(huì)發(fā)布出來(lái)。
GitHub: https://github.com/apache/dubbo-go/pull/237
設(shè)計(jì)思路
于是我大概參考了一下 Dubbo 已有的實(shí)現(xiàn),做了一點(diǎn)改進(jìn)。
Dubbo 里面的核心抽象是 TpsLimiter 接口。 TpsLimitFilter 只是簡(jiǎn)單調(diào)用了一下這個(gè)接口的方法而已:
這個(gè)抽象是很棒的。但是還欠缺了一些抽象。
實(shí)際上,一個(gè) TPS Limit 就要解決三個(gè)問(wèn)題:
對(duì)什么東西進(jìn)行 limit 。比如說(shuō),對(duì)服務(wù)進(jìn)行限流,或者對(duì)某個(gè)方法進(jìn)行限流,或者對(duì)IP進(jìn)行限流,或者對(duì)用戶進(jìn)行限流;
如何判斷已經(jīng) over limitation 。這是從算法層面上考慮,即用什么算法來(lái)判斷某個(gè)調(diào)用進(jìn)來(lái)的時(shí)候,已經(jīng)超過(guò)配置的上限了;
被拒絕之后該如何處理。如果一個(gè)請(qǐng)求被斷定為已經(jīng) over limititation 了,那么該怎么處理;
所以在 TpsLimiter 接口的基礎(chǔ)上,我再加了兩個(gè)抽象:
TpsLimiter
TpsLimitStrategy
RejectedExecutionHandler
TpsLimiter 對(duì)應(yīng)到 Java 的 TpsLimiter ,兩者是差不多。在我的設(shè)想里面,它既是頂級(jí)入口,還需要承擔(dān)解決第一個(gè)問(wèn)題的職責(zé)。
而 TpsLimitStrategy 則是第二個(gè)問(wèn)題的抽象的接口定義。它代表的是純粹的算法。該接口完全沒(méi)有參數(shù),實(shí)際上,所有的實(shí)現(xiàn)需要維護(hù)自身的狀態(tài)——對(duì)于大部分實(shí)現(xiàn)而言,它大概只需要獲取一下系統(tǒng)時(shí)間戳,所以不需要參數(shù)。
最后一個(gè)接口 RejectedExecutionHandler 代表的是拒絕策略。在 TpsLimitFilter 里面,如果它調(diào)用 TpsLimiter 的實(shí)現(xiàn),發(fā)現(xiàn)該請(qǐng)求被拒絕,那么就會(huì)使用該接口的實(shí)現(xiàn)來(lái)獲取一個(gè)返回值,返回給客戶端。
實(shí)現(xiàn)
其實(shí)實(shí)現(xiàn)沒(méi)太多好談的。不過(guò)有一些微妙的地方,我雖然在代碼里面注釋了,但是我覺(jué)得在這里再多說(shuō)一點(diǎn)也是可以的。
首先提及的就是拒絕策略 RejectedExecutionHandler ,我就是提供了一種實(shí)現(xiàn),就是隨便 log 了一下,什么都沒(méi)做。因?yàn)檫@個(gè)東西是強(qiáng)業(yè)務(wù)相關(guān)的,我也不能提供更加多的通用的實(shí)現(xiàn)。
方法與服務(wù)雙重支持的 TpsLimiter
TpsLimiter 我只有一個(gè)實(shí)現(xiàn),那就是 MethodServiceTpsLimiterImpl 。它就是根據(jù)配置,如果方法級(jí)別配置了參數(shù),那么會(huì)在方法級(jí)別上進(jìn)行限流。否則,如果在服務(wù)級(jí)別( ServiceKey )上有配置,那么會(huì)在服務(wù)級(jí)別進(jìn)行限流。
舉個(gè)最復(fù)雜的例子:服務(wù) A 限制 100 ,有四個(gè)方法,方法 M1 配置限制 40 ,方法 M2 和方法 M3 無(wú)配置,方法M4配置限制 -1 :那么方法 M1 會(huì)單獨(dú)限流 40 ; M2 和 M3 合并統(tǒng)計(jì),被限制在 100 ;方法 M4 則會(huì)被忽略。
用戶可以配置具體的算法。比如說(shuō)使用我接下來(lái)說(shuō)的,我已經(jīng)實(shí)現(xiàn)的三種實(shí)現(xiàn)。
FixedWindow 和 ThreadSafeFixedWindow
FixedWindow 直接對(duì)應(yīng)到 Java 的 DefaultTpsLimiter 。它采用的是 fixed-window 算法:比如說(shuō)配置了一分鐘內(nèi)只能調(diào)用 100 次。假如從 00:00 開(kāi)始計(jì)時(shí),那么 00:00-01:00 內(nèi),只能調(diào)用 100 次。只有到達(dá) 01:00 ,才會(huì)開(kāi)啟新的窗口 01:00-02:00 。如圖:
Fixed-Window圖示
Fixed-Window實(shí)現(xiàn)
這里有一個(gè)很有意思的地方。就是這個(gè)實(shí)現(xiàn),是一個(gè)幾乎線程安全但是其實(shí)并不是線程安全的實(shí)現(xiàn)。
在所有的實(shí)現(xiàn)里面,它是最為簡(jiǎn)單,而且性能最高的。我在衡量了一番之后,還是沒(méi)把它做成線程安全的。事實(shí)上, Java 版本的也不是線程安全的。
它只會(huì)在多個(gè)線程通過(guò)第 67 行的檢測(cè)之后,才會(huì)出現(xiàn)并發(fā)問(wèn)題,這個(gè)時(shí)候就不是線程安全了。但是在最后的 return 語(yǔ)句中,那一整個(gè)是線程安全的。它因?yàn)椴粩嘤?jì)數(shù)往上加,所以多個(gè)線程同時(shí)跑到這里,其實(shí)不會(huì)有什么問(wèn)題。
現(xiàn)在我要揭露一個(gè)最為奇詭的特性了:并發(fā)越高,那么這個(gè) race condition 就越嚴(yán)重,也就是說(shuō)越不安全。
但是從實(shí)際使用角度而言,有極端 TPS 的還是比較少的。對(duì)于那些 TPS 只有幾百每秒的,是沒(méi)什么問(wèn)題的。
為了保持和 Dubbo 一致的特性,我把它作為默認(rèn)的實(shí)現(xiàn)。
此外,我還為它搞了一個(gè)線程安全版本,也就是 ThreadSafeFixedWindowTpsLimitStrategyImpl ,只是簡(jiǎn)單的用 sync 封裝了一下,可以看做是一個(gè) Decorator 模式的應(yīng)用。
如果強(qiáng)求線程安全,可以考慮使用這個(gè)。
SlidingWindow
這是我比較喜歡的實(shí)現(xiàn)。它跟網(wǎng)絡(luò)協(xié)議里面的滑動(dòng)窗口算法在理念上是比較接近的。
具體來(lái)說(shuō),假如我設(shè)置的同樣是一分鐘 1000 次,它統(tǒng)計(jì)的永遠(yuǎn)是從當(dāng)前時(shí)間點(diǎn)往前回溯一分鐘內(nèi),已經(jīng)被調(diào)用了多少次。如果這一分鐘內(nèi),調(diào)用次數(shù)沒(méi)超過(guò) 1000 ,請(qǐng)求會(huì)被處理,如果已經(jīng)超過(guò),那么就會(huì)拒絕。
我再來(lái)描述一下, SldingWindow 和 FixedWindow 兩種算法的區(qū)別。這兩者很多人會(huì)搞混。假如當(dāng)前的時(shí)間戳是 00:00 ,兩個(gè)算法同時(shí)收到了第一個(gè)請(qǐng)求,開(kāi)啟第一個(gè)時(shí)間窗口。
那么 FixedWindow 就是 00:00-01:00 是第一個(gè)窗口,接下來(lái)依次是 01:00-02:00 , 02:00-03:00 , ...。當(dāng)然假如說(shuō) 01:00 之后的三十秒內(nèi)都沒(méi)有請(qǐng)求,在 01:31 又來(lái)了一個(gè)請(qǐng)求,那么時(shí)間窗口就是 01:31-02:31 。
而 SildingWindow 則沒(méi)有這種概念。假如在 01:30 收到一個(gè)請(qǐng)求,那么 SlidingWindow 統(tǒng)計(jì)的則是 00:30-01:30 內(nèi)有沒(méi)有達(dá)到 1000 次。它永遠(yuǎn)計(jì)算的都是接收到請(qǐng)求的那一刻往前回溯一分鐘的請(qǐng)求數(shù)量。
如果還是覺(jué)得有困難,那么簡(jiǎn)單來(lái)說(shuō)就是 FixedWindow 往后看一分鐘, SlidingWindow 回溯一分鐘。 這個(gè)說(shuō)法并不嚴(yán)謹(jǐn),只是為了方便理解。 在真正寫(xiě)這個(gè)實(shí)現(xiàn)的時(shí)候,我稍微改了一點(diǎn)點(diǎn):
我用了一個(gè)隊(duì)列來(lái)保存每次訪問(wèn)的時(shí)間戳。一般的寫(xiě)法,都是請(qǐng)求進(jìn)來(lái),先把已經(jīng)不在窗口時(shí)間內(nèi)的時(shí)間戳刪掉,然后統(tǒng)計(jì)剩下的數(shù)量,也就是后面的 slow path 的那一堆邏輯。
但是我改了的一點(diǎn)是,我進(jìn)來(lái)直接統(tǒng)計(jì)隊(duì)列里面的數(shù)量——也就是請(qǐng)求數(shù)量,如果都小于上限,那么我可以直接返回 true ,即 quick path 。
這種改進(jìn)的核心就是:我只有在檢測(cè)到當(dāng)前隊(duì)列里面有超過(guò)上限數(shù)量的請(qǐng)求數(shù)量時(shí)候,才會(huì)嘗試刪除已經(jīng)不在窗口內(nèi)的時(shí)間戳。
這其實(shí)就是,是每個(gè)請(qǐng)求過(guò)來(lái),我都清理一下隊(duì)列呢?還是只有隊(duì)列元素超出數(shù)量了,我才清理呢?我選擇的是后者。
我認(rèn)為這是一種改進(jìn)……當(dāng)然從本質(zhì)上來(lái)說(shuō),整體開(kāi)銷是沒(méi)有減少的——因?yàn)?golang 語(yǔ)言里面 List 的實(shí)現(xiàn),一次多刪除幾個(gè),和每次刪除一個(gè),多刪幾次,并沒(méi)有多大的區(qū)別。
算法總結(jié)
無(wú)論是 FixedWindow 算法還是 SlidingWindow 算法都有一個(gè)固有的缺陷,就是這個(gè)時(shí)間窗口難控制。
我們?cè)O(shè)想一下,假如說(shuō)我們把時(shí)間窗口設(shè)置為一分鐘,允許 1000 次調(diào)用。然而,在前十秒的時(shí)候就調(diào)用了 1000 次。在后面的五十秒,服務(wù)器雖然將所有的請(qǐng)求都處理完了,然是因?yàn)榇翱谶€沒(méi)到新窗口,所以這個(gè)時(shí)間段過(guò)來(lái)的請(qǐng)求,全部會(huì)被拒絕。
解決的方案就是調(diào)小時(shí)間窗口,比如調(diào)整到一秒。但是時(shí)間窗口的縮小,會(huì)導(dǎo)致 FixedWindow 算法的 race condition 情況加劇。
那些沒(méi)有實(shí)現(xiàn)的
基于特定業(yè)務(wù)對(duì)象的限流
舉例來(lái)說(shuō),某些特殊業(yè)務(wù)用的針對(duì)用戶 ID 進(jìn)行限流和針對(duì) IP 進(jìn)行限流,我就沒(méi)有在 dubbo-go 里面實(shí)現(xiàn)。有需要的可以通過(guò)實(shí)現(xiàn) TpsLimiter 接口來(lái)完成。
全局 TPS limit
這篇文章之前討論的都是單機(jī)限流。如果全局限流,比如說(shuō)針對(duì)某個(gè)客戶,它購(gòu)買(mǎi)的服務(wù)是每分鐘調(diào)用 100 次,那么就需要全局限流——雖然這種 case 都不會(huì)用 Filter 方案,而是另外做一個(gè) API 接入控制。
比如說(shuō),很常用的使用 Redis 進(jìn)行限流的。針對(duì)某個(gè)客戶,一分鐘只能訪問(wèn) 100 次,那我就用客戶 ID 做 key , value 設(shè)置成 List ,每次調(diào)用過(guò)來(lái),隨便塞一個(gè)值進(jìn)去,設(shè)置過(guò)期時(shí)間一分鐘。那么每次統(tǒng)計(jì)只需要統(tǒng)計(jì)當(dāng)前 key 的存活的值的數(shù)量就可以了。 這種我也沒(méi)實(shí)現(xiàn),因?yàn)楹孟駴](méi)什么需求。國(guó)內(nèi)討論 TPS limit 都是討論單機(jī) TPS limit 比較多。
這個(gè)同樣可以通過(guò)實(shí)現(xiàn) TpsLimiter 接口來(lái)實(shí)現(xiàn)。
Leaky Bucket 算法
這個(gè)本來(lái)可以是 TpsLimitStrategy 的一種實(shí)現(xiàn)的。后來(lái)我覺(jué)得,它其實(shí)并沒(méi)有特別大的優(yōu)勢(shì)——雖然號(hào)稱可以做到均勻,但是其實(shí)并做不到真正的均勻。通過(guò)調(diào)整 SlidingWindow 的窗口大小,是可以接近它宣稱的均勻消費(fèi)的效果的。比如說(shuō)調(diào)整到一秒,那其實(shí)就已經(jīng)很均勻了。而這并不會(huì)帶來(lái)多少額外的開(kāi)銷。
評(píng)論
查看更多