GCRA(Generic cell rate algorithm)でAPIリクエストをレート制限する話

この記事は、 富士通クラウドテクノロジーズ Advent Calendar 2019 の21日目の記事です。
20日目は @foobaron さんの プライベートLAN同士を接続する機能 プライベートブリッジ の提供を開始しました でした！

🌞はじめに

こんにちは！NIFCLOUDでIaaS向けAPIの開発をしている @kzmake と申します。

みなさんは、APIリクエストの瞬間的なバースト、どのように対応していますか？

リクエストの瞬間的なバーストによるサービス影響を最小限にするため、WebAPIを公開するにあたりレート制限などの仕組みが必要な場面もあるかとおもいます。

そんなこんなで今年は、

• WebAPIのレート制御のアルゴリズムとして、GCRAの解説
• GCRA + Redisを利用したWebAPIのレート制限

の話をざっくりと書いていきたいとおもいます！

💡TL;DR

• GCRAはシンプルで高速なレート制限を実現する
• GCRA + Redisで好きなパラメータをKeyとしてレート制限できる
• GCRA + Redisで複数のサービス間でレート制限を共有できる

🤔Generic cell rate algorithm(GCRA)って？

ドリッププロセスなしでLeaky buketを表現するアルゴリズムです。「セル」と呼ばれる固定サイズの小さなパケット単位でレート制限やスケジューリングを行う仕組みです。

Leaky bucketとは

一定量の「漏れ」(制限されたスループット)を持つバケットのこと。容量を超えて入れる事はできないバケット。ドリッププロセスを持つことで、滑らかなバケット容量の回復を表現できます。

このドリッププロセスとバケット容量は、APIリクエストのレート制限などにも応用されています。

GCRAとは

理論到着時刻($TAT$)として、理論的に挿入されるセルがパケットから排出されるまでの時刻をもとにLeaky bucketのドリッププロセスを再現するアルゴリズムです。

GCRAで利用されるパラメータと式

• $t_a$
  • セルをパケットに挿入しようとした時刻
• $TAT$
  • 挿入されるセルがバケットから排出されるまでの時刻
• $T$
  • パケットが1つのセルを排出する時間
• $\tau$
  • バケットの時間的な最大容量
    • $バケットのセル最大容量 \times T$
• $\tau + T$
  • パケットの排出感覚を含めて許容できる最大時間

バケットに挿入されているセル数を$n$としたとき、理論到着時刻$TAT$は、

TAT_{n+1} = \begin{cases}
  t_a + T & (n=0) \\
  TAT_{n} + T & (otherwise)
\end{cases}

と表されます

セルを挿入しようとしたときはどのように評価するの？

１つのセルを挿入しようとしたとき、
バケットに挿入されているセル数を$n$である場合、セルをバケットに挿入できるかを

TAT_{n+1} - (\tau + T) \geq t_a

で評価していきます。これを整理すると、

TAT_{n} - \tau \geq t_a

となりますね。

GCRAでは、Leaky bucketのドリッププロセスを$TAT$を用いてシンプルに表現しています。

⚙️レート制限の機能として

複数のサービスから共通して利用できるようにRedisの利用を想定していきます。

GCRAで必要となるRedisコマンド

GCRAは、ソフトウェア的に$TAT$を永続化し、$TAT$の時刻でexpireすることで実現できます。($t_a$はレート制限時に決まり、$\tau$と$T$はレート制限システム毎に決定しています。)

複数のサービスから共通してレート制限を行う場合は、Redisなどを利用してこの$TAT$をサービス間で共有すればいいことになりますね。

今回のアルゴリズムで使用するRedisコマンドは、

• SET
• EXPIRE

の２つのみです。とってもシンプルですね
(ちなみにコストは同じですが、SETEXのワンコマンドでまとめて設定も可能です。)

独自で実装しても簡単なアルゴリズムですが、この記事では、

• github.com/brandur/redis-cell
• github.com/throttled/throttled

の２つのレート制限を紹介していきます。

brandur/redis-cellの利用

github.com/brandur/redis-cellでSETEXを利用したRedisモジュールが公開されています。これは、Redis側にモジュールとして github.com/brandur/redis-cellを導入することで利用可能となります。

redis-cellで追加されるコマンド

github.com/brandur/redis-cell#Usageにて紹介されているコマンドはこちら。

CL.THROTTLE <key> <max_burst> <count per period> <period> [<quantity>]

redis-cellコマンドとGCRA関係

CL.THROTTLE user123 15 30 60 1
               ▲     ▲  ▲  ▲ ▲
               |     |  |  | └───── apply 1 token (default if omitted)
               |     |  └──┴─────── 30 tokens / 60 seconds
               |     └───────────── 15 max_burst
               └─────────────────── key "user123"

user123と名前のついたセル最大容量15となるバケットを作成するイメージとなりますね。
コマンドを叩く というアクションは バケットにセルを挿入する とすると、

• 挿入されるセル数
  • 1
• $\tau$
  • 15 * T
• $T$
  • 60/30
• $\tau + T$
  • (15 + 1) * T
• $t_a$
  • コマンドを叩いた時刻

と関係してそうです。

redis-cellのレスポンス

APIリクエストのレート制限として利用することを想定した場合には、

127.0.0.1:6379> CL.THROTTLE user123 15 30 60
1) (integer) 0
2) (integer) 16
3) (integer) 15
4) (integer) -1
5) (integer) 2

1. ブロックされているかのフラグ
   • 0: ブロックされていない
   • 1: ブロックされている
2. ブロックするまでの上限値 + 1
   • 一般的な X-RateLimit-Limit の値
3. ブロックされるまでの残りの値
   • 一般的な X-RateLimit-Remaining の値
4. ユーザーが再リクエストできるまでの秒数[sec]
   • 一般的な Retry-After の値
   • 許可されている間は -1
5. 上限値までリセットされるまでの秒数[sec]
   • 一般的な X-RateLimit-Reset の値

と見てよさそうです。

あとはそれぞれのプログラムでRedis Clientを準備し、コマンドを実行していくのみとなります。

throttled/throttledの利用

golang packageとしてgithub.com/throttled/throttledというものも公開されています。こちらはstoreとして、

• goredisstore
• memstore
• redigostore

をサポートしているので柔軟に利用できそうですね。

throttled/throttledを使ったプログラムの例

github.com/brandur/redis-cellと同等の機能を持っているので一例で紹介するのみとします。APIリクエストをレート制限するのであれば、とっても簡単に導入できますね。

mux := http.NewServeMux()
mux.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
    w.WriteHeader(http.StatusOK)
    fmt.Fprintf(w, "Hello World")
})

store, err := memstore.New(65536)
if err != nil {
    log.Fatal(err)
}

rateLimiter, err := throttled.NewGCRARateLimiter(store, throttled.RateQuota{MaxRate: throttled.PerMin(30), MaxBurst: 15})
if err != nil {
    log.Fatal(err)
}

// Custom: func(r *http.Request) string { ... } により好きなキーを設定可能
varyBy := &throttled.VaryBy{Path: true}

httpRateLimiter := throttled.HTTPRateLimiter{
    RateLimiter: rateLimiter,
    VaryBy:      varyBy, 
}

http.ListenAndServe(":3000", httpRateLimiter.RateLimit(mux))

🌜おわりに

GCRAは洗練されたレート制限を提供してくれる、高速かつシンプルなアルゴリズムでした。github.com/brandur/redis-cellやgithub.com/throttled/throttledなどを用いることで簡単にWebAPIへレート制限の機能を追加できます。

レート制限は、

• 有限のリソースへのアクセスを抑制する
• パスワード試行回数のセキュリティ強化
• レート制限の解除や上限数の緩和などのマネタイズ

で利用できる要素なので、このような目的がある方はぜひGCRAを検討してみてください。

明日は @hunter9xさんがなにか書いてくれるそうです！お楽しみに！

🔖 参考

• Rate Limiting, Cells, and GCRA
• Generic cell rate algorithm - Wikipedia
• brandur/redis-cell: A Redis module that provides rate limiting in Redis as a single command.
• throttled/throttled: Package throttled implements rate limiting access to resources such as HTTP endpoints.