この記事は、 富士通クラウドテクノロジーズ Advent Calendar 2019 の21日目の記事です。
20日目は @foobaron さんの プライベートLAN同士を接続する機能 プライベートブリッジ の提供を開始しました でした！
🌞はじめに
こんにちは！NIFCLOUDでIaaS向けAPIの開発をしている @kzmake と申します。
みなさんは、APIリクエストの瞬間的なバースト、どのように対応していますか？
リクエストの瞬間的なバーストによるサービス影響を最小限にするため、WebAPIを公開するにあたりレート制限などの仕組みが必要な場面もあるかとおもいます。
そんなこんなで今年は、
の話をざっくりと書いていきたいとおもいます！
💡TL;DR
🤔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コマンドは、
の２つのみです。とってもシンプルですね 
(ちなみにコストは同じですが、SETEXのワンコマンドでまとめて設定も可能です。)
独自で実装しても簡単なアルゴリズムですが、この記事では、
の２つのレート制限を紹介していきます。
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
- ブロックされているかのフラグ
- 0: ブロックされていない
- 1: ブロックされている
- ブロックするまでの上限値 + 1
- 一般的な
X-RateLimit-Limitの値
- 一般的な
- ブロックされるまでの残りの値
- 一般的な
X-RateLimit-Remainingの値
- 一般的な
- ユーザーが再リクエストできるまでの秒数[sec]
- 一般的な
Retry-Afterの値 - 許可されている間は
-1
- 一般的な
- 上限値までリセットされるまでの秒数[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さんがなにか書いてくれるそうです！お楽しみに！