前言

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è)接口只能訪(fǎng)問(wèn) 200 次，超過(guò)這個(gè)次數(shù)，則會(huì)被拒絕服務(wù)。在 Dubbo 的 Java 版本上，只有一個(gè)實(shí)現(xiàn)，就是 DefaultTPSLimiter 。

DefaultTPSLimiter 是在服務(wù)級(jí)別上進(jìn)行限流。雖然 Dubbo 的官方文檔里面聲稱(chēng)可以在 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ì)用戶(hù)進(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è)返回值，返回給客戶(hù)端。

實(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ì)被忽略。

用戶(hù)可以配置具體的算法。比如說(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è)幾乎線(xiàn)程安全但是其實(shí)并不是線(xiàn)程安全的實(shí)現(xiàn)。

在所有的實(shí)現(xiàn)里面，它是最為簡(jiǎn)單，而且性能最高的。我在衡量了一番之后，還是沒(méi)把它做成線(xiàn)程安全的。事實(shí)上， Java 版本的也不是線(xiàn)程安全的。

它只會(huì)在多個(gè)線(xiàn)程通過(guò)第 67 行的檢測(cè)之后，才會(huì)出現(xiàn)并發(fā)問(wèn)題，這個(gè)時(shí)候就不是線(xiàn)程安全了。但是在最后的 return 語(yǔ)句中，那一整個(gè)是線(xiàn)程安全的。它因?yàn)椴粩嘤?jì)數(shù)往上加，所以多個(gè)線(xiàn)程同時(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è)線(xiàn)程安全版本，也就是 ThreadSafeFixedWindowTpsLimitStrategyImpl ，只是簡(jiǎn)單的用 sync 封裝了一下，可以看做是一個(gè) Decorator 模式的應(yīng)用。

如果強(qiáng)求線(xiàn)程安全，可以考慮使用這個(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)保存每次訪(fǎng)問(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)銷(xiāo)是沒(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ì)用戶(hù) 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è)客戶(hù)，它購(gòu)買(mǎi)的服務(wù)是每分鐘調(diào)用 100 次，那么就需要全局限流——雖然這種 case 都不會(huì)用 Filter 方案，而是另外做一個(gè) API 接入控制。

比如說(shuō)，很常用的使用 Redis 進(jìn)行限流的。針對(duì)某個(gè)客戶(hù)，一分鐘只能訪(fǎng)問(wèn) 100 次，那我就用客戶(hù) 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)稱(chēng)可以做到均勻，但是其實(shí)并做不到真正的均勻。通過(guò)調(diào)整 SlidingWindow 的窗口大小，是可以接近它宣稱(chēng)的均勻消費(fèi)的效果的。比如說(shuō)調(diào)整到一秒，那其實(shí)就已經(jīng)很均勻了。而這并不會(huì)帶來(lái)多少額外的開(kāi)銷(xiāo)。