前言
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 的實作的。這從它的源碼也可以看出來：
它直接寫死了 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
TpsLimitStrategy
RejectedExecutionHandler
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 。如圖：
Fixed-Window圖示
Fixed-Window實作
這裡有一個很有意思的地方。就是這個實作，是一個幾乎線程安全但是其實并不是線程安全的實作。
在所有的實作裡面，它是最為簡單，而且性能最高的。我在衡量了一番之後，還是沒把它做成線程安全的。事實上， 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 接口來完成。
全局 TPS limit
這篇文章之前讨論的都是單機限流。如果全局限流，比如說針對某個客戶，它購買的服務是每分鐘調用 100 次，那麼就需要全局限流——雖然這種 case 都不會用 Filter 方案，而是另外做一個 API 接入控制。
比如說，很常用的使用 Redis 進行限流的。針對某個客戶，一分鐘隻能通路 100 次，那我就用客戶 ID 做 key ， value 設定成 List ，每次調用過來，随便塞一個值進去，設定過期時間一分鐘。那麼每次統計隻需要統計目前 key 的存活的值的數量就可以了。
這種我也沒實作，因為好像沒什麼需求。國内讨論 TPS limit 都是讨論單機 TPS limit 比較多。
這個同樣可以通過實作 TpsLimiter 接口來實作。
Leaky Bucket 算法
這個本來可以是 TpsLimitStrategy 的一種實作的。後來我覺得，它其實并沒有特别大的優勢——雖然号稱可以做到均勻，但是其實并做不到真正的均勻。通過調整 SlidingWindow 的視窗大小，是可以接近它宣稱的均勻消費的效果的。比如說調整到一秒，那其實就已經很均勻了。而這并不會帶來多少額外的開銷。
作者資訊：鄧明，畢業于南京大學，就職于eBay Payment部門，負責退款業務開發