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