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