本文延續 Amazon API Gateway 裡很重要的觀念：限速 Rate Limit、Throttling、Burst 等概念。

Rate Limit 概念在 SRE CH21: 處理系統超載 (Handling Overload)、Service Mesh 都有直接關聯。

介紹

名詞

整理 Study 過程看到的名詞，也整理過去不清楚的點：

• rate limit (速度限制): 單位時間內的速度，單位通常是秒，常見的有述語有以下：
  • rps: request per second, 通常是網頁請求
  • qps: query per second, 通常是 database 的 query
  • tps: transcation per second, 每秒的交易數量，考驗分散式架構最關鍵的數字。
  • pv: page view, 網頁打開的次數，例如一天的 pv = 30k
• throttle: 中文是 節流閥、俗稱油門，用來控制流速的增、減。
  • 想像是個閥門，打開後讓水流過去，閥門的高度決定水流的速度。
  • 在 Amazon API Gateway，就是最小單位 (1ms) 可以過去的數目
• burst limit: burst 中文翻成爆裂、爆走，突然的流量爆衝，但是暴衝還是要有限制，不然下一步就是爆炸 XDD
• steady-state rate: 穩態速率
• Levels in Amazon API Gateway: 分成 Account-Level Throttling 和 Stage-Level

Algorithms for Rate Limit

常見實作 Rate Limit 的演算法有兩個：

• Leaky Bucket: 中文翻成 漏桶演算法
  • 設計給通訊設備 (通常是網路設備) 的傳輸控制，像是 QoS 實作
  • 實作：
    • nginx 使用此演算法實作，官方描述請參考 Rate Limiting with NGINX and NGINX Plus 。
    • tyk 使用此演算法實作 Hard-synchronised rate limiter，官方說明 Rate Limiting
  • 保證速率 <= 設定值，不會超過
  • 無法應付突發流量 (Burst)
  • 實作分 meter (簡單)、queue (複雜) 兩種，nginx 使用 Queue (FIFO) 方式處理
  • bucket 裡放的是 packet or data，滿了資料會遺失
  • 演算法核心概念：緩存請求、勻速處理、多餘的請求直接丟棄。
• Token Bucket: 中文翻成 令牌桶演算法、單信號桶演算法
  • bucket 裡放的是 token，不是 packet or data
  • Amazon API Gateway 使用此演算法實作。
  • 可以應付突發流量 (Burst)，我猜這是 AWS 選擇的主因吧？
  • Burst 大小就是 bucket size
  • 另外兩個著名演算法分別為:
    • RFC2697: two rate three color marker, trTCM (雙速率三色標記演算法)
    • RFC2698: single rate Three Color Marker, trTCM (單速率三色標記演算法)

兩個演算法的差異是是否允許 突發流量 (Burst) 的處理。

底下是相關參考文件：

• Rate Limiting with NGINX and NGINX Plus
• 速率限制的一些思考
• Nginx 限速模塊初探

Rate Limit and Throttling in Amazon API Gateway

關於 Rate Limit 在 Amazon API Gateway 的ㄧ些基本資訊：

• Rate Limit: 預設為 10,000 Per Account Per Region. Soft Limit
• Throttle limits: bucket 上限為 5000, 固定，無法調整。

底下整理官方文件 Throttle API Requests 的說明，有點像是在翻譯練習啦 XDD

1. 10,000 個請求，在一分鐘之內 平均 送出

• API Gateway 處理所有的請求，沒有丟失。

2. 10,000 個請求，在第 1 毫秒 (ms) 送出

• API Gateway 處理 5000 個，然後在一秒之內對剩餘的請求進行限制 (throttle)

3. 5,000 個請求，在第 1 毫秒送出，然後剩下 999 毫秒平均送出 5000 請求 (每毫秒 5 個)

• API Gateway 在一秒鐘的期間處理了 10000 個請求，沒有丟失。
• 沒有回傳 429 Too Many Requests 錯誤

4. 5000 個請求，在第 1 毫秒送出，然後等到第 101 毫秒，再送出另 5,000 個請求，API Gateway 處理 6,000 個請求，然後在一秒之內限制進行 (throttle) 。

• 這是因為限制比率為 10,000 rps， API Gateway 已經再第 100 毫秒後處理 1,000 個請求，然後因此清空 bucket 裡同樣數量。
• 接下來的 5000 的請求，1000 個填滿了 Bucket 並等待處理，其他 4000 個超過的將被丟失。

5. 5000 個請求，在第 1 毫秒送出，然後在第 101 毫秒送出 1000 個請求，然後剩下的 899 毫秒再平均送出 4000 個請求

• API Gateway 在一秒內處理所有 10,000 個請求，沒有丟失

這五個 Case 整理如下圖 (大概只有我看得懂 XDD)

Token Bucket 相關參數如下：

• B: bucket 總容量
• b: bucket 使用容量
• Δ: bucket 可用容量
• r: bucket 消耗斜率

Bucket 可用容量計算： Δ = B - b

下圖是官方文件中，簡單描述各個時間點消化的狀況：

• t1:
  • Δ1: 約消耗了 1/5 的 request
  • b1: 還有約 4/5 的 request 在 bucket 裡尚未處理
• t2:
  • Δ2: 約消耗了 1/2 的 request
  • b2: 還有約 1/2 的 request 在 bucket 裡尚未處理
• t3:
  • Δ3: 所有 request 已經消化完了
  • b3: 沒有 request 在 bucket 等待處理
• t4:
  • Δ4: 約消耗了 1/6 的 request
  • b4: 還有約 5/6 的 request 在 bucket 裡尚未處理

Rate Limit 推算

以下推算兩種：極大、極小

推算一: Rate Limit = 100,000 (10萬)

如果我送出 Support ，請 AWS 調整 Rate Limit 為 100,000

• 代表每秒可以處理 10 萬個 Request
• burst 為固定大小 5000
• 處理的最小單位 (window size) 為 1ms => 100 rpms (Request Per Millisecond) < Throttle Limit

所以同前述的案例描述：

• 第 1 毫秒同時收到 5000 個 request
  • 總量有 10 萬個，所以還有 95,000 個可以處理
  • 第 2 豪秒能再收 100 個 request
  • 如果 2-100 都沒收到，第 101 毫秒 (過了 100 毫秒後)，則可以處理 100 * 100 = 10,000 個 request
  • 總量有 10 萬個，已經處理 5000 + 10,000 = 15,000，還剩下 100,000 - 15,000 = 85,000 個容量
• 剩下的時間，如果平均每個豪妙都收到 100 個 request，則可以處理總數量： (1000ms - 101ms) x 100 = 89,900 > 85,000
• 這個 Rate Limit 合理

推算二: Rate Limit = 1,000,000 (100 萬)

如果我送出 Support ，請 AWS 調整 Rate Limit 為 1,000,000

• 代表每秒可以處理 100 萬個 Request
• burst 為固定最大 5000
• 處理的最小單位為 1ms => 1,000 rpms (Request Per Millisecond) < Throttle Limit

同前述，再次推算：

• 第 1 毫秒同時收到 5000 個 request
  • 總量有 100 萬個，所以還有 955,000 (95.5 萬) 個可以處理
  • 第 2 豪秒能再收 1,000 個 request
  • 如果 2-100 都沒收到，第 101 毫秒 (過了 100 毫秒後)，則可以處理 100 * 1000 = 100,000 (十萬) 個 request
  • 總量有 100 萬個，已經處理 5000 + 100,000 = 105,000，還剩下 1,000,000 - 105,000 = 895,000 個容量
• 剩下的時間，如果平均每個豪妙都收到 1000 個 request，則可以處理總數量： (1000ms - 101ms) x 1000 = 899,000 > 895,000

推算三: Rate Limit = 10,000,000 (1000 萬)

如果我送出 Support ，請 AWS 調整 Rate Limit 為 10,000,000 (他應該會覺得我發瘋了)

• 代表每秒可以處理 1000 萬個 Request
• burst 為固定最大 5000
• 處理的最小單位為 1ms => 10,000 rpms (Request Per Millisecond) > Throttle Limit

同前述，再次推算：

• 第 1 毫秒同時收到 5000 個 request
  • 總量有 1,000 萬個，所以還有 9,995,000 (999.5 萬) 個可以處理
  • 第 2 豪秒能再收 10,000 個 request
  • 如果 2-100 都沒收到，第 101 毫秒 (過了 100 毫秒後)，則可以處理 100 * 10,000 = 1,000,000 (一百萬) 個 request
  • 總量有 1,000 萬個，已經處理 5000 + 1,000,000 = 1,005,000，還剩下 10,000,000 - 1,005,000 = 8,995,000 個容量
• 剩下的時間，如果平均每個豪妙都收到 1000 個 request，則可以處理總數量： (1000ms - 101ms) x 10,000 = 8,990,000 > 8,995,000

推算四

• Rate Limit: 100M rpm, window size = 0.1M rpms > throttle limit (5k)
• Rate Limit: 1000M rpm, window size = 1M rpms > throttle limit (5k)
• … 全世界流量有那麼大？

Burst 合理性, Rate Limit 的上限？

前面三個推算是要確認：

• Burst 為固定最大 5000 的合理性
• 如果最小處理單位 (Token Bucket 演算法的 window size) 為 1ms，如果 Burst Limit = window size 會怎樣？
• 實際上不會怎樣，Rate Limit = 5Mrps 的時候： Burst Limit = window size

問題

Q1: Burst Limit 怎麼實作？

Token Bucket 可以實作，由 Bucket Size 決定大小。
Burst Limit = Bucket Size = B

Q2: Amazon API Gateway 的 Burst Limit 為什麼是固定的？

跟成本有關係，東京 1,000,000 Request 4.5USD, 如果流量超過每秒 10,000，整理換算：

• 10k * 60 = 600k/min
• 600K * 60 = 6M/h
• 6M * 24 = 144M/h
• 144M * 30 = 4320M/month = 18,360 USD/month

超過這個流量，代表可以考慮其他 Solution 了。

Q3: Amazon API Gateway 的 Rate Limit 每個 Stage 都可以個別指定，所以全部加起來是總數？

這概念跟網路頻寬類似，總量是固定的，例如區域網路裡 Gateway 對外、對內最大是 1Gbps，但是區域網路每台電腦自己的網卡可能是 100Mbps、1Gbps 或者 10Gbps，所以 Rate Limit 不是加起來的概念，而是 單位時間內最大數量

Q4: Rate Limit 有上限？

從前面推算可以到 10M rps，實際上問題已經不是效能問題，而是成本。如果成本可以扛下，那應該不是技術的問題了。

類比

這種跟時間、速度、能量有關的東西，不太好理解，不過我在 Study 過程，腦袋裡一直出現底下這張圖：

圖片來源: HOW TO USE A COMPRESSOR: THE EASY TO FOLLOW GUIDE

這是吉他效果器之一 Compressor (壓縮器) 的原理，他主要是用來控制音量，讓音量維持在穩定的 dB 範圍，通常在混音、後製時是非常重要的設備。

Rate Limit 和 Compressor 的觀念幾乎一模一樣，只是參數換了一些名詞而已。

底下是 Compressor 一些常見的參數，和 Rate Limit 做對比：

• Attack: 相當於 Burst
• Threshold: 相當於 Rate Limit
• Release: 相當於前圖中的 消耗斜率

下面兩張圖是 Guitar 硬體 CS-3、軟體 SV-315 的壓縮效果器～

哈，實在是太有趣了！

相關音樂科技文章： 如何選擇適合的數位設備 - 以吉他綜合效果器為例、數位音樂科技概論 (Concepts of Digital Music Technology)

延伸閱讀

系列文章

• Study Notes - Overview API Gateway
• Study Notes - Amazon API Gateway
• API Gateway - Custom Authorizers using Lambda
• API Gateway - Setup Logging
• API Gateway - Custom Domain Names
• API Gateway - Integrate with Internal Services
• Using API Gateway as DynamoDB Proxy
• API Gateway - Rate Limit and Throttling
• API Gateway Private Endpoint
• Design Async Invocation using API Gateway and SQS
• 2018/06/28: AWS Summit - 邁向 API 經濟 - API Gateway 導入之旅

站內延伸

• Service Mesh

參考資料

• Amazon API Gateway
• Throttle API Requests
• Leaky Bucket & Tocken Bucket - Traffic shaping
• How to build Resilience in large scale Distributed Systems
• Enable API Caching to Enhance Responsiveness
• Throttling pattern