標籤: Go

剛好在hacker news 上看到這一篇文章，看起來是個cgo free的Go Sqlite3 driver；讓我想起之前還真的因為升級Go的版本造成Go Sqlite3的一些runtime bug, 印象中最後的解法是透過把GNU GCC 改成MUSL GCC重新做cross compile 以後才解決，也因此看到這個資訊就蠻有興趣的。

不過從hacker news 的回應中看起來，效能上看起來會比原本常用的go-sqlite3 慢不少，如果在效能不是非常重要的情境下，看來也是可以考慮的方向。

References:

• https://github.com/mattn/go-sqlite3
• https://news.ycombinator.com/item?id=35488980
• cznic / sqlite · GitLab
• https://magiclen.org/musl-libc/

最近剛好公司某個專案需要將資料傳輸到遠端的某個服務上，而那個服務可能會有頻寬上的限制，所以我們的資料傳送端必須加入Rate limit這功能，以免瞬間的資料流造成資料被丟棄的問題；也趁這個機會多整理一點 Rate limit相關的知識…

rate limiting vs throttling

這兩個名詞常分別或一起出現在討論rate limiting 的相關文章中，而我也常搞混這兩個詞的意義，所以稍微再整理一下它們所代表的意思：

Rate limiting 指的是，限制requests在某個時間區間內，其可允許執行requests的數量。

Throttling 指的是，控制requests在特定的時間區間內出現時，允許可執行requests的 一種流程。

一個簡單的例子是，當我們限制某個API 每秒只能執行 100次，這是一個Rate limiting的流程；而當我們再把時間看得更細時，平均我們每100 ms 可以服務10個requests。
在這 100 reqs/s的情境下，控制requests 可以被服務的頻率的一個程序就是throttling。
* 這邊我們可以控制當requests 超過 10 reqs/100ms，就被丟棄 或是可以允許requests 最多到burst 20 reqs/100ms)
* 另一種Throttling的情境是，在某一秒的requests數量為105，那超過的這5個requests 我們可以允許它們被服務(soft throttling)或直接丟棄那5個requests(hard throttling)

簡而言之，Rate limiting比較偏向資源服務在大方向的一個規範，而Throttling責聚焦在實作上一些情境下的處理流程。

Rate limiting 相關演算法

Token bucket

Token bucket 主要的概念是，想像我們有一個水桶，裡面最多可以放到n 個token；每使用者需要使用某個資源時，他就必須到水桶中取走一個token，而如果水桶中沒有任何的token時，則使用者無法使用他想要用的資源。

而水桶中的token 會依照 1/n second的速率補充到水桶中，當水桶補滿n個token時，就不再補充任何的token了。

特色：

• 如果水桶中的token是滿的，其會允許使用者瞬間可以同時索取n個token，也就是允許requests 最多同時burst到n個。
• 可能會導致某個時間區間下，各個時間點request量不平均。
• Golang 有內建的lib 原生支援這個演算法。
• 主要的應用在於，如果我們必須限制我們的requests在固定區間下是有限的，但區間下的每個時間點是允許突然暴增的requests。

Leaky bucket

Leaky bucket 是常用來與Token bucket比較的一個演算法；其概念上是，我們會有一個水桶，並且我們有定義好這個水桶可以往下流出的速率，當我們的requests的量大於可允許流出的速率時，則會被queue起來；而同時間我們也會定義水桶中最多可允許queue起來的量，如果超過時，則這些新的requests 則會被丟棄。

特色：

• 概念上對於burst requests的限制較嚴，主要是用來維持每個時間點下的requests流量是固定的。
• Golang 中可以參考uber-go/ratelimit 這套 open source solution。
• 比較適合像是，網路頻寬或流量控制的相關應用。

相關文章：

• https://www.geeksforgeeks.org/leaky-bucket-algorithm/

Fixed window counter

這個演算法的概念是，我們定義每個時間區間下可以允許的requests 量是n，而這個區間間是固定的。(例如 [12:00:01-12:00:02), [12:00:02, 12:00:03) )
每個區間會有個counter，每當有新的request時，我們就會有個計算目前這個區間下已count的量，如果加入這個request會導致count > n，則我們會丟棄這個新的request。

特色：

• 實作上相對簡單，且對burst的限制較不嚴。
• 如果requests 量剛好發生的時間在，前一個區間的下半段與下一個區間的上半段時，則可能發生這段跨區間的requests量是我們原本定義的n的2倍。
  (e.g. 假設我們每個區間的允許的量是n ，而有n個requests發生在[12:01:30, 12:02:00)，另外n個requests發生在[12:02:00, 12:02:30)，則如果我們單看區間[12:01:30, 12:02:30)時，會發現requests量可能暴增到2n。)

Sliding window logs

這個演算法類似於Fixed window counter，會針對每一個request記錄其發生的時間，所以當一個新的request出現時，演算法會去比較目前時間點回推到過去的某個時間點下，這段時間區間中的request數量，再來衛量這個新的request是否允許，如果不允許的話，則這個新的request則會被丟棄。

隨著時間的流動，已經過期的request 記錄也會被清除…

特色：

• 解決了Fixed window counter演算法可能會遇到的request burst問題。
• 實作上，可能計算會相對較秏資源；因為每次要確認一個新的request是否允許時，需要從目前時間點往回計算，而且過期的記錄要刪除也會是額外要做的事。

Sliding window counter

這個演算法是整合了Fixed window counter + Sliding window log的演算法的作法；概念上也是使用Fixed window counter的概念，只是每個時間區間又再切成多個子區間，所以每次在比對某個request是否可以服務時，就是比對目前時間點下的子區間再加上過去發生過的多個子區間之count 總合，如果低於某個值rate limit最初設定的值的話，那就代表這個新的request 是可以被服務的，反之則丟棄這個request。

舉例來說，我們定義某個API 的 rate limit 為每秒n個，則在實作上，我們可以多切10個子區間， 所以每個子區間的間隔會是100ms，以12:00:01這個區間為例，實際上記錄的子區間有12:00:01.1, 12:00:01.2 … 12:00:01.9 等等。
所以當一個新的request發生時，演算法會去計算目前這個子區間所有的count數量以及過去9個子區間count 數量的總合，再來比對加入這個新的request是否還是小於 n，如果是的話則允許服務這個api request。

特色：

• 整合了Fixed window counter 與Sliding window log的優點，且實作上也不難實現。

在分散式系統上的一些實務上作法

使用Central Storage – Redis/memcached

這是一個蠻常見的作法，透過一個高效的儲存db來存放一些狀態資料，每當一個新的request發生時，就先去儲存db獲取先前儲存的狀態(token/count… etc)來判定目前的request是否可以被服務。

特色：

• 效能瓶頸會是在redis/memcached本身，不過對大多數的應用來說應該是夠用了。
• 網路上可以找到蠻多資源的，相關的教學文或已經寫好的open source library。
• 若單存使用Redis/Memcached所提供的一般API時，可能在大量request發生時要小心處理race condition的問題。(或許要額外引入distributed lock之類的機制)
• 如果使用Redis + Lua時，則可以實現atomic operation，解決race condition的問題。

相關文章：

• https://redis.io/commands/incr#pattern-rate-limiter
• github 使用Redis rate limiting 的經驗
• 透過Stripe 透過redis +Lua來做 rate limiting?
• Figma 的相關rate limiting實作
• https://github.com/wallstreetcn/rate
• https://medium.com/@justin.graber/rate-limiting-in-golang-f3ed2c62df36
• https://medium.com/analytics-vidhya/custom-rate-limiting-in-golang-using-redis-with-docker-e4a7be96f7dc
• Go redis的實作

使用client based rate limiting

概念上是rate limit 的管理是放在client service 那邊管理的，而所有的client service 會透過一個central storage 來獲取某個API/Resource的total rate limiting與client rate limiting 。

舉例來說，我們可以在etcd上設定某個API的rate limiting為n，並且也記錄了目前註冊過的client service數量m，所以每個client service 相對於這個API的rate limit就會是n/m, 這樣每次client service在服務request時就只需要直接參考目前本機上的rate limit (n/m)就可以了。
而在這個例子下，我們還可以透過ectd的watch 機制來讓所有的client service即時的獲取更新後的n 與 m值。

特色：

• 效能可以到非常好，因為rate limit是實作在client 端，所以特別適合超大流量的應用。
• 有個先決條件為，流量必須很平均的分散在所有的client端，這樣才會更有效的使用到所有分配到rate。
• 作為取捨，對於rate limit的控制會相對沒那麼精準，畢境如果有client端的service 掛掉了，會有段時間差，之後所有的client才會獲取得最新的資訊。

相關文章：

• https://engineering.linecorp.com/en/blog/high-throughput-distributed-rate-limiter/

自行設計的rate limit cluster

mailgun這間公司有open source了一套Go的distributed rate limit service – guberator，其概念上是把micro services的概念應用到rate limit service上，每個client端的機器，都會另外在佈署這個gubernator peer，而gubernator之間是靠grpc來溝通的。

每個gubernator都會管理不同resource的rate limit，所以每當某個client service要服務某個request時，它會需要與本機端的gubernator詢問request 相關的limit，而本機端的gubernator 則會知道相對應的資訊是存在本機或是其它的gubernator上。

由於資訊還是由某個gubernator管理，所以理論上也會受限於單機可以處理的上限，但在這邊gubernator有透過一個自行實作的batch機制來提高機器處理的上限值。

這個機制也蠻容易理解的，主要就是再處理rate limit request之前，先把收到的requests 打包起來再送出去成一個單一的batch request。從文章上有提到，batch機制的預設是每當收到對於某個resource的第一個request時，會再等500 micro seconds來收集更多對同一個resource的請求，當時間到了以後，再處理這一包batch過的rate limit request；
假設在這段時間內，收到3000 個對於某個resource的rate limit requests，則只需要某個gubernator送出一個rate limit request，其request quota量為3000，接下來就只需要看收到request的gubernator它那邊會允許多少quote是可以被執行的。

相關文章：

• https://www.mailgun.com/blog/gubernator-cloud-native-distributed-rate-limiting-microservices/
• https://github.com/mailgun/gubernator

Reference:

• https://helpx.adobe.com/coldfusion/api-manager/throttling-and-rate-limiting.html
• https://en.wikipedia.org/wiki/Leaky_bucket
• https://en.wikipedia.org/wiki/Generic_cell_rate_algorithm
• https://baike.baidu.com/item/token%20bucket/4315253
• https://github.com/mennanov/limiters
• https://github.com/ulule/limiter
• How to Design a Scalable Rate Limiting Algorithm
• https://github.com/youtube/doorman
• https://hansliu.com/posts/2020/11/what-is-token-bucket-and-leaky-bucket-algorithms.html

在Go語言的世界裡，func init() {} 是一個適合用來初始化整個package的執行者，它會在package 第一次被import時，自動的執行其中之內容，並且它只會被執行一次…

不過使用上也必須特別注意，因為當某個package需要init 時，就代表它有一些package level variable，而這些package level variable 若是被一些內部的function 或 method 使用時，就可能造成一些side effect。

簡而言之，若使用的不好的話，是很容易造成一些anit pattern的…

舉例來說像下面這段範例程碼碼

package foo


type handler interface {
    shouldHandle() bool
    handleFoo() error
    handlerBar() error
}

type handlerImpl struct {}

func (h handlerImpl) shouldHandle() bool {
    return true
}

func (h handlerImpl) handleFoo() error {
    return nil
}

func (h handlerImpl) handleBar() error {
    return nil
}

var defaulHandler handler

func init() {
    defaultHandler = handlerImpl{}
}


func HandleFoo() error {
    if defaultHandler.shouldHandle() {
        return defaultHandler.handleFoo()
    }
    return errors.New("not allowed")
}

func HandleBar() error {
    if defaultHandler.shouldHandle() {
        return defaultHandler.handlerBar()
    }
    return errors.New("not allowed")
}

在上面這個範例中，HandleFoo, HandleBar都會先call defaultHandler.shouldHandle來看是不是需要處理接下來的流程，如果是的話，再執行各自的handle function。

如果要分別測試HandleFoo, HandleBar的話，我們就要想辦法mock defaultHandler 。 但因為defaultHandler是在init中被指派的，所以就上面的程式碼來看，是沒有直接可以測試的方式…

但如果我們不在init中指派defaultHandler，而是改用下面的範例來做的話，就可以進一步解決測試上的問題…

func Init(concreteHandler handler) {
    defaultHandler = concreteHandler
}

以這段程式碼來看，如果我們要測試HandleFoo, HandleBar的話，我們只需要在每一個unit test之前，先執行Init()來代入mocked 過的 concreteHandler就可以測試了。

不過這樣的作法是不是就沒有問題了???

很不幸的，透過Init來解決測試的問題還是會有一些副作用；由於這兩個HandleFoo與HandleBar 都同時用到handler.shouldHandle()，所以這也代表如果我們同時在測試這兩個function時，就會有可能發生下面的race issue:

• test 1: 測試HandleFoo時，代入mockDefaultHandler, 並且把shouldHandle()，mock成回傳值為true.
• test 2: 測試HandleBar時，代入mockDefaultHandler, 並且把shouldHandle()，mock成回傳值為false.

由於go test預設是會同時用多個cpu cores來執行所有的測試，這樣就會有機率性地遇到上述的問題，並發生測試結果不如預期情況…

當然如果我們直接使用go test -p 1來執行unit tests 的話就沒有race 的問題了，不過同樣的就造成測試時間變長的問題了。

寫到這邊的一些想法：

• 如果沒有必要的話，盡量不要使用init，因為會使用init的情況通常代表這個package 有些package level variables 需要被初始化。
• 盡量避免在func中直接使用package level variables，因為它會造成那些使用的func不易被測試。

references:

• https://stackoverflow.com/questions/56039154/is-it-really-bad-to-use-init-in-go
• https://leighmcculloch.com/posts/tool-go-check-no-globals-no-inits/
• https://peter.bourgon.org/blog/2017/06/09/theory-of-modern-go.html

對於常開發與使用AWS的開發者來說，要實作一些整合測試時通常會比較麻煩點，尤其是通常會需要在有網路的環境下做開發與測試。

Github上的這個Localstack 專案，就是為了解決這個痛點而存在的，它幫助AWS開發者搭建本地端的AWS 服務，舉例來說，我們可以透過Localstack在本地端搭建一個S3讓我們所開發的應用程式去連接。

目前Localstack支援的AWS 服務可以在他們的github頁面上找到，常見的API Gateway, DynamoDB, Lambda and S3都可以使用，如果是使用他們的付費方案, 則有支援更多的AWS 服務。

搭建Localstack S3

目前剛好有用到S3，所以記錄一下透過下面docker-compose.yaml來啟用Localstack的方式：

version: "3.3"
 services:
   localstack:
     image: localstack/localstack
     network_mode: bridge
     ports:
       - "4566:4566"
       - "4571:4571"
     environment:
       - SERVICES=s3
       - EDGE_PORT=4566
       - AWS_DEFAULT_REGION=us-east-1
     volumes:
       - "${TMPDIR:-/tmp/localstack}:/tmp/localstack"
       - "/var/run/docker.sock:/var/run/docker.sock"

NOTE:

• 這邊的SERVICES是可以指定多個服務的，例如SERVICE=s3,lambda。
• EDGE_PORT目前預設也是4566，主要是用來在本地端服務的port number。
• 更多詳細的docker-compose.yaml 範例可以參考官方的這個例子。

使用AWS CLI 連接 Localstack S3

在透過上面提到的方式搭建好本地端的S3以後，其實就可以直接用AWS CLI來去連到我們剛架好的S3了；唯一要注意的是，我們在使用cli 時必須指定對應的endpoint-url到我們剛架好的本地端url。

透過docker aws cli 連接Localstack s3

docker exec -t -e AWS_ACCESS_KEY_ID=1 -e AWS_SECRET_ACCESS_KEY=abc container_localstack_1 aws --endpoint-url=http://127.0.0.1:4566 s3 mb s3://my_bucket

NOTE:
透過AWS Cli連接 Localstack時，必須指定key_id 與key，要不然會報錯

透過AWS Go SDK

如果要透過Go AWS SDK 去連接Localstack S3的話，會有個額外要設定的AWS.Config欄位，其具體的範例程式碼為：

awsCfg := &aws.Config{
   Credentials: credentials.NewStaticCredentials(awsKeyId, awsKeySecret, ""),
   Region:      aws.String(region),
}

if customEndpoint != "" {
   awsCfg.Endpoint = aws.String("http://localhost:4566")
   awsCfg.S3ForcePathStyle = aws.Bool(true)
}

在這邊，設定 S3ForcePathStyle=true 主要是為了讓Go SDK與連接S3的時候會把bucket 的資訊透過path的方式去代入到resource的uri中。

舉例來說，如果我們有個bucket=my_bucket，而我們在這個bucket裡面的一個測試檔案test.txt的完整uri為是http://localhost:4566/my_bucket/test.txt；有了這樣的設定，才會讓我們使用Go AWS SDK時，可以正確的存取Localstack S3上的檔案。

如果我們使用S3ForcePathStyle=false的話，則同個檔案， Go AWS SDK會使用這個uri: http://my_bucket.localhost:4566/test.txt 去存取Localstack上的檔案；顯然地，這個uri是有問題的，因為Localstack S3 是在listen http://localhost:4566，而不是http://my_bucket.localhost:4566這個子網域。

更多詳細的說明可以參考官方的這個issue：https://github.com/aws/aws-sdk-go/issues/2743

Reference:

• https://github.com/localstack/localstack
• https://onexlab-io.medium.com/localstack-s3-e28ad393c09