前言

Apache Dubbo 是由阿里開源的一個RPC框架，除了基本的 RPC 功能以外，還提供了一整套的服務(wù)治理相關(guān)功能。目前它已經(jīng)是 Apache 基金會下的頂級項目。

而 dubbo-go 則是 Dubbo 的 Go 語言實現(xiàn)。

最近在 dubbo-go 的 todo list 上發(fā)現(xiàn)，它還沒有實現(xiàn) TPS Limit 的模塊，于是就抽空實現(xiàn)了這個部分。

TPS limit 實際上就是限流，比如說限制一分鐘內(nèi)某個接口只能訪問 200 次，超過這個次數(shù)，則會被拒絕服務(wù)。在 Dubbo 的 Java 版本上，只有一個實現(xiàn)，就是 DefaultTPSLimiter 。

DefaultTPSLimiter 是在服務(wù)級別上進(jìn)行限流。雖然 Dubbo 的官方文檔里面聲稱可以在 method 級別上進(jìn)行限流，但是我看了一下它的源碼，實際上這個是做不到的。當(dāng)然，如果自己通過實現(xiàn) Filter 接口來實現(xiàn) method 級別的限流，那么自然是可以的——這樣暴露了 Dubbo Java 版本實現(xiàn)的另外一個問題，就是 Dubbo 的 TpsLimitFilter 實現(xiàn)，是不允許接入自己 TpsLimiter 的實現(xiàn)的。這從它的源碼也可以看出來：

它直接寫死了 TpsLimiter 的實現(xiàn)。

這個實現(xiàn)的目前只是合并到了 develop 上，等下次發(fā)布正式版本的時候才會發(fā)布出來。

GitHub: https://github.com/apache/dubbo-go/pull/237

設(shè)計思路

于是我大概參考了一下 Dubbo 已有的實現(xiàn)，做了一點改進(jìn)。

Dubbo 里面的核心抽象是 TpsLimiter 接口。 TpsLimitFilter 只是簡單調(diào)用了一下這個接口的方法而已：

這個抽象是很棒的。但是還欠缺了一些抽象。

實際上，一個 TPS Limit 就要解決三個問題：

對什么東西進(jìn)行 limit 。比如說，對服務(wù)進(jìn)行限流，或者對某個方法進(jìn)行限流，或者對IP進(jìn)行限流，或者對用戶進(jìn)行限流；

如何判斷已經(jīng) over limitation 。這是從算法層面上考慮，即用什么算法來判斷某個調(diào)用進(jìn)來的時候，已經(jīng)超過配置的上限了；

被拒絕之后該如何處理。如果一個請求被斷定為已經(jīng) over limititation 了，那么該怎么處理；

所以在 TpsLimiter 接口的基礎(chǔ)上，我再加了兩個抽象：

TpsLimiter

TpsLimitStrategy

RejectedExecutionHandler

TpsLimiter 對應(yīng)到 Java 的 TpsLimiter ，兩者是差不多。在我的設(shè)想里面，它既是頂級入口，還需要承擔(dān)解決第一個問題的職責(zé)。

而 TpsLimitStrategy 則是第二個問題的抽象的接口定義。它代表的是純粹的算法。該接口完全沒有參數(shù)，實際上，所有的實現(xiàn)需要維護(hù)自身的狀態(tài)——對于大部分實現(xiàn)而言，它大概只需要獲取一下系統(tǒng)時間戳，所以不需要參數(shù)。

最后一個接口 RejectedExecutionHandler 代表的是拒絕策略。在 TpsLimitFilter 里面，如果它調(diào)用 TpsLimiter 的實現(xiàn)，發(fā)現(xiàn)該請求被拒絕，那么就會使用該接口的實現(xiàn)來獲取一個返回值，返回給客戶端。

實現(xiàn)

其實實現(xiàn)沒太多好談的。不過有一些微妙的地方，我雖然在代碼里面注釋了，但是我覺得在這里再多說一點也是可以的。

首先提及的就是拒絕策略 RejectedExecutionHandler ，我就是提供了一種實現(xiàn)，就是隨便 log 了一下，什么都沒做。因為這個東西是強業(yè)務(wù)相關(guān)的，我也不能提供更加多的通用的實現(xiàn)。

方法與服務(wù)雙重支持的 TpsLimiter

TpsLimiter 我只有一個實現(xiàn)，那就是 MethodServiceTpsLimiterImpl 。它就是根據(jù)配置，如果方法級別配置了參數(shù)，那么會在方法級別上進(jìn)行限流。否則，如果在服務(wù)級別（ ServiceKey ）上有配置，那么會在服務(wù)級別進(jìn)行限流。

舉個最復(fù)雜的例子：服務(wù) A 限制 100 ，有四個方法，方法 M1 配置限制 40 ，方法 M2 和方法 M3 無配置，方法M4配置限制 -1 ：那么方法 M1 會單獨限流 40 ； M2 和 M3 合并統(tǒng)計，被限制在 100 ；方法 M4 則會被忽略。

用戶可以配置具體的算法。比如說使用我接下來說的，我已經(jīng)實現(xiàn)的三種實現(xiàn)。

FixedWindow 和 ThreadSafeFixedWindow

FixedWindow 直接對應(yīng)到 Java 的 DefaultTpsLimiter 。它采用的是 fixed-window 算法：比如說配置了一分鐘內(nèi)只能調(diào)用 100 次。假如從 00:00 開始計時，那么 00:00-01:00 內(nèi)，只能調(diào)用 100 次。只有到達(dá) 01:00 ，才會開啟新的窗口 01:00-02:00 。如圖：

Fixed-Window圖示

Fixed-Window實現(xiàn)

這里有一個很有意思的地方。就是這個實現(xiàn)，是一個幾乎線程安全但是其實并不是線程安全的實現(xiàn)。

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

它只會在多個線程通過第 67 行的檢測之后，才會出現(xiàn)并發(fā)問題，這個時候就不是線程安全了。但是在最后的 return 語句中，那一整個是線程安全的。它因為不斷計數(shù)往上加，所以多個線程同時跑到這里，其實不會有什么問題。

現(xiàn)在我要揭露一個最為奇詭的特性了：并發(fā)越高，那么這個 race condition 就越嚴(yán)重，也就是說越不安全。

但是從實際使用角度而言，有極端 TPS 的還是比較少的。對于那些 TPS 只有幾百每秒的，是沒什么問題的。

為了保持和 Dubbo 一致的特性，我把它作為默認(rèn)的實現(xiàn)。

此外，我還為它搞了一個線程安全版本，也就是 ThreadSafeFixedWindowTpsLimitStrategyImpl ，只是簡單的用 sync 封裝了一下，可以看做是一個 Decorator 模式的應(yīng)用。

如果強求線程安全，可以考慮使用這個。

SlidingWindow

這是我比較喜歡的實現(xiàn)。它跟網(wǎng)絡(luò)協(xié)議里面的滑動窗口算法在理念上是比較接近的。

具體來說，假如我設(shè)置的同樣是一分鐘 1000 次，它統(tǒng)計的永遠(yuǎn)是從當(dāng)前時間點往前回溯一分鐘內(nèi)，已經(jīng)被調(diào)用了多少次。如果這一分鐘內(nèi)，調(diào)用次數(shù)沒超過 1000 ，請求會被處理，如果已經(jīng)超過，那么就會拒絕。

我再來描述一下， SldingWindow 和 FixedWindow 兩種算法的區(qū)別。這兩者很多人會搞混。假如當(dāng)前的時間戳是 00:00 ，兩個算法同時收到了第一個請求，開啟第一個時間窗口。

那么 FixedWindow 就是 00:00-01:00 是第一個窗口，接下來依次是 01:00-02:00 , 02:00-03:00 , ...。當(dāng)然假如說 01:00 之后的三十秒內(nèi)都沒有請求，在 01:31 又來了一個請求，那么時間窗口就是 01:31-02:31 。

而 SildingWindow 則沒有這種概念。假如在 01:30 收到一個請求，那么 SlidingWindow 統(tǒng)計的則是 00:30-01:30 內(nèi)有沒有達(dá)到 1000 次。它永遠(yuǎn)計算的都是接收到請求的那一刻往前回溯一分鐘的請求數(shù)量。

如果還是覺得有困難，那么簡單來說就是 FixedWindow 往后看一分鐘， SlidingWindow 回溯一分鐘。 這個說法并不嚴(yán)謹(jǐn)，只是為了方便理解。 在真正寫這個實現(xiàn)的時候，我稍微改了一點點：

我用了一個隊列來保存每次訪問的時間戳。一般的寫法，都是請求進(jìn)來，先把已經(jīng)不在窗口時間內(nèi)的時間戳刪掉，然后統(tǒng)計剩下的數(shù)量，也就是后面的 slow path 的那一堆邏輯。

但是我改了的一點是，我進(jìn)來直接統(tǒng)計隊列里面的數(shù)量——也就是請求數(shù)量，如果都小于上限，那么我可以直接返回 true ,即 quick path 。

這種改進(jìn)的核心就是：我只有在檢測到當(dāng)前隊列里面有超過上限數(shù)量的請求數(shù)量時候，才會嘗試刪除已經(jīng)不在窗口內(nèi)的時間戳。

這其實就是，是每個請求過來，我都清理一下隊列呢？還是只有隊列元素超出數(shù)量了，我才清理呢？我選擇的是后者。

我認(rèn)為這是一種改進(jìn)……當(dāng)然從本質(zhì)上來說，整體開銷是沒有減少的——因為 golang 語言里面 List 的實現(xiàn)，一次多刪除幾個，和每次刪除一個，多刪幾次，并沒有多大的區(qū)別。

算法總結(jié)

無論是 FixedWindow 算法還是 SlidingWindow 算法都有一個固有的缺陷，就是這個時間窗口難控制。

我們設(shè)想一下，假如說我們把時間窗口設(shè)置為一分鐘，允許 1000 次調(diào)用。然而，在前十秒的時候就調(diào)用了 1000 次。在后面的五十秒，服務(wù)器雖然將所有的請求都處理完了，然是因為窗口還沒到新窗口，所以這個時間段過來的請求，全部會被拒絕。

解決的方案就是調(diào)小時間窗口，比如調(diào)整到一秒。但是時間窗口的縮小，會導(dǎo)致 FixedWindow 算法的 race condition 情況加劇。

那些沒有實現(xiàn)的

基于特定業(yè)務(wù)對象的限流

舉例來說，某些特殊業(yè)務(wù)用的針對用戶 ID 進(jìn)行限流和針對 IP 進(jìn)行限流，我就沒有在 dubbo-go 里面實現(xiàn)。有需要的可以通過實現(xiàn) TpsLimiter 接口來完成。

全局 TPS limit

這篇文章之前討論的都是單機限流。如果全局限流，比如說針對某個客戶，它購買的服務(wù)是每分鐘調(diào)用 100 次，那么就需要全局限流——雖然這種 case 都不會用 Filter 方案，而是另外做一個 API 接入控制。

比如說，很常用的使用 Redis 進(jìn)行限流的。針對某個客戶，一分鐘只能訪問 100 次，那我就用客戶 ID 做 key ， value 設(shè)置成 List ，每次調(diào)用過來，隨便塞一個值進(jìn)去，設(shè)置過期時間一分鐘。那么每次統(tǒng)計只需要統(tǒng)計當(dāng)前 key 的存活的值的數(shù)量就可以了。 這種我也沒實現(xiàn)，因為好像沒什么需求。國內(nèi)討論 TPS limit 都是討論單機 TPS limit 比較多。

這個同樣可以通過實現(xiàn) TpsLimiter 接口來實現(xiàn)。

Leaky Bucket 算法

這個本來可以是 TpsLimitStrategy 的一種實現(xiàn)的。后來我覺得，它其實并沒有特別大的優(yōu)勢——雖然號稱可以做到均勻，但是其實并做不到真正的均勻。通過調(diào)整 SlidingWindow 的窗口大小，是可以接近它宣稱的均勻消費的效果的。比如說調(diào)整到一秒，那其實就已經(jīng)很均勻了。而這并不會帶來多少額外的開銷。