はじめに
こんにちは、aptpodのサーバーサイドエンジニアの宮内です。
突然ですが、APIのレートリミット実装していますか？ 最近、弊社のバックエンドAPIでもレート制限を実装しました。
Generic Cell Rate Algorithm (GCRA) を使ったのですが、 このアルゴリズムが面白かったので、今回はこのGCRAについてと、GoでGCRAを利用したレートリミットについて説明します。
Leaky Bucketについて
GCRAの説明に入る前に、GCRAはLeaky Bucketを再現するアルゴリズムであるため、 まずはLeaky Bucketの理解からしていきましょう。
と言っても、深くは触れません。 Wikipedia. Leaky_bucket が詳しいので、詳細はこちらで。
Leaky Bucketとはトラフィックシェーピングやポリシングで良く利用されるアルゴリズムです。 一定のバースト性を許可する Token Bucket アルゴリズムとは異なり、一定のトラフィックに制限するという点が特徴です。
Leaky(漏れ穴のある) Bucket(バケツ) の文字通り、バケツに一気に水が入っても穴からでる水の量は一定というアルゴリズムです。
GCRAとは
Understanding Generic Cell Rate Limiting から一部引用します。
Leaky bucket algorithms, however, tend to rely on a separate process to leak used capacity from the bucket. If that process fails, then the bucket may fill up and users may be limited from performing any action. Herein lies the beauty of GCRA, it doesn't rely on a separate process just an accurate clock, but it still acts like a leaky bucket.
かいつまんで書くと、 世間的にLeaky Bucketを実装する場合バケットからセル（HTTPで言うリクエスト）を放出する処理を別のプロセス（ドリッププロセス）にすることが多く、 その別プロセスが失敗すると、バケットが満杯になりユーザーが何もできなくなってしまうという課題があったようです。
GCRAはこのドリッププロセスを用いずに時間ウィンドウをスライドさせることでLeakey Bucketを再現するアルゴリズムです。
GCRAの詳細
（ちょっと長いので手っ取り早く使い方だけ知りたい方は GCRAの利用 まで飛ばしてください。）
ここの説明は、 先程も引用しましたが Understanding Generic Cell Rate Limiting に詳しく書いてあります。
しかし、時間ウィンドウのスライドが、ややイメージしづらいと思ったので、改めて同記事をベースに解説します。 他にもGCRAの記事を探してみたのですが、数式で語られる記述が多い印象でした。 セルの到着から、制限の判定までを細かく追っていきつつ、GCRAを理解していきましょう。
はじめに変数について書いておきます。
- PERIOD -> 単位時間
- LIMIT -> 単位時間あたりの最大セル（バケットを埋める単位）数
- EMISSION INTERVAL -> 一つのセルが開放される間隔（= PERIOD/LIMIT）
- ARRIVED_AT -> セルの到着時間
- ALLOWED_AT -> タイムウィンドウの一番最初
- TAT -> 理論到着時間（Theoredical Arraival Time）
- NEW_TAT -> 次の理論到着時間
- DELAY_VARIATION_TOLERANCE -> 許容値時間ウィンドウの幅（=PERIOD）
TATについては重要な概念なのですが、ここではひとまずそういうものだと思って読み進めてもらうと良いと思います。
初回セル到着
まずは、初回のセルが到着したときから考えます。
１. セルが到着。
-----------------x-----------------> t
|
ARRIVED_AT(今)
２. TATを決める。TATがないので到着時刻をTATとする。
-----------------x-----------------> t
|
ARRIVED_AT(今)
TAT
３. TATからEMISSION_INTERVALを足した時間をNEW_TATとして定義する。
|<- EMISSION -->|
| INTERVAL |
-----------------x---------------x-> t
| |
ARRIVED_AT(今) NEW_TAT
TAT
４. NEW_TATから、DELAY_VARIATION_TOLERANCE（PERIOD分）を引いた時刻をALLOWED_ATとする。
|<- EMISSION -->|
| INTERVAL |
-x-------------------x---------------x--> t
| | |
| ARRIVED_AT(今) NEW_TAT
| TAT |
| |
| DELAY_VARIATION_TOLERANCE(PERIOD) |
|<--------------------------------->|
ALLOWED_AT
５. ARRIVED_ATがALLOWED_ATより後の時間だったら許可する。
６. セルを許可したときはNEW_TATをTATとして保存しておく。
ここまでが初回セルが到着したときの処理です。 ALLOWED_ATとNEW_TATの間を時間ウィンドウとし，このウィンドウの中にARRIVED_ATがあれば、そのセルを許可します。 時間ウィンドウはセルが到着する度に前方向にスライドしていき、その度にARRIVED_ATが時間ウィンドウの中にあるかでセルの許可/拒否を決めていきます。
ここからは２回目以降のセル到着時の時間ウィンドウについて説明を移します。 ２回目以降のセル到着はそのセルのARRIVED_ATとTATの前後関係によってウィンドウの進み方が変わるので、それぞれ順番に見ていきます。
２回目のセル到着（TATよりARRIVED_ATが後）
まず、TATより後にセルが到着した時を見ていきます。
１. セルが到着
-----------------x----------------------> t
|
ARRIVED_AT(今)
２. TATを取得する。
------x----------x----------------------> t
| |
TAT ARRIVED_AT(今)
３. NEW_TATを決める。TATとARRIVED_ATを比較して、より後ろの時間にEMISSION_INTERVALを加算し、その点をNEW_TATとする。この場合はARRIVE_ATに加算。
|<- EMISSION -->|
| INTERVAL |
------x----------x---------------+------> t
| | |
TAT ARRIVED_AT(今) NEW_TAT
４. 以降は初回セルと同じようにNEW_TATからDELAY_VARIATION_TOLERANCE(PERIOD)を引いてALLOWED_ATを決める。
|<- EMISSION -->|
| INTERVAL |
-x--------x----------x---------------x------> t
| | | |
| TAT ARRIVED_AT(今) NEW_TAT
| |
| |
| DELAY_VARIATION_TOLERANCE(PERIOD) |
|<--------------------------------->|
ALLOWED_AT
５. ARRIVED_ATはウィンドウの中に入っているのでOK。NEW_TATをTATとして保存して終了。
２回目のセル到着（TATよりARRIVED_ATが前）
次にTATより前にセルが到着したときを見ていきます。よりたくさんリクエストが来ているときのイメージです。
６. セルが到着
-----------------x----------------------> t
|
ARRIVED_AT(今)
７. TATを取得する。
-----------------x----------------x-----> t
| |
ARRIVED_AT(今) TAT
８. NEW_TATを決める。TATとARRIVED_ATを比較して、より後ろの時間にEMISSION_INTERVALを加算し、その点をNEW_TATとする。この場合はTATに加算。
|<- EMISSION -->|
| INTERVAL |
----------x----------------x---------------x-------t
| | NEW_TAT
ARRIVED_AT(今) TAT
９. 以降は初回セルと同じようにNEW_TATからDELAY_VARIATION_TOLERANCE(PERIOD)を引いてALLOWED_ATを決める。
|<- EMISSION -->|
| INTERVAL |
---x---------x----------------x---------------x--> t
| | | |
| ARRIVED_AT(今) TAT NEW_TAT
| |
| |
| DELAY_VARIATION_TOLERANCE(PERIOD) |
|<---------------------------------------->|
ALLOWED_AT
１０. ARRIVED_ATはウィンドウの中に入っているのでOK。NEW_TATをTATとして保存して終了。
ARRIVED_ATに対して、初回到着よりALLOWED_AT~NEW_TAT間の時間ウィンドウが前にスライドしていることがわかると思います。
さらにTATより短い間隔でセルが到着するとどうなるか見てみます。
N回目のセル到着（TATよりARRIVED_ATが結構前）
１. セルが到着
---x--------------------> t | ARRIVED_AT(今)
２. TATを取得してNEW_TATを決める。TATがだいぶ先の時間なので、NEW_TATもだいぶ先となる。
|<- EMISSION -->|
| INTERVAL |
----x-----------------------------------x---------------x--> t
| | |
ARRIVED_AT(今) TAT NEW_TAT
３. 以降は初回セルと同じように決めていくと次のようになる。
|<- EMISSION -->|
| INTERVAL |
---x--------x--------------------------x---------------x--> t
| | | |
ARRIVED_AT(今) TAT NEW_TAT
| |
| DELAY_VARIATION_TOLERANCE(PERIOD) |
|<---------------------------------------->|
ALLOWED_AT
ARRIVED_ATがALLOWED_ATより前にあります。 つまり時間ウィンドウの外に出ているということなので、ここで初めてそのセルは拒否（またはキューイング）されます。
セルが拒否された場合は、NEW_TATは更新しません。 ARRIVED_ATがALLOWED_ATより後の時間になるまでは、セルは拒否され続けます。
WebでいうとALLOED_ATとARRIVED_ATの差がRetry-Afterになります。
以上でGCRAアルゴリズムの説明は終わりです。
記事中にはKEYやQUANTITYなどもありますが、時間ウィンドウのスライドが読み取るという趣旨であるため, 説明から省きました。
少しだけ説明すると、QUANTITYというのは到着したセルの数で、その分NEW_TATが後ろに伸びます（ウィンドウが前に進みます） Webの世界だとレート制限はリクエスト数でやることが一般的かと思いますが、その場合QUANTITYは１となります。
KEYは制限の対象を識別するための任意値です。 例えば、クライアントIPアドレスやエンドポイントのパスなどです。
GCRAの利用
さて、概念的なところは前述の通りです。実装していきましょう、と言いたいところですが、既にライブラリがあります。 ここでは throttled を使ったサンプルを紹介します。
手元で動かせるように簡単に書いてみました。
package main import ( "flag" "fmt" "log" "time" "github.com/throttled/throttled/v2" "github.com/throttled/throttled/v2/store/memstore" ) func main() { var ( maxRate int burst int interval time.Duration ) flag.IntVar(&maxRate, "r", 1, "") flag.IntVar(&burst, "b", 1, "") flag.DurationVar(&interval, "i", time.Second, "") flag.Parse() store, err := memstore.New(65536) if err != nil { log.Fatal(err) } quota := throttled.RateQuota{ MaxRate: throttled.PerSec(maxRate), MaxBurst: burst, } rateLimiter, err := throttled.NewGCRARateLimiter(store, quota) if err != nil { log.Fatal(err) } ticker := time.NewTicker(interval) defer ticker.Stop() for range ticker.C { ng, res, err := rateLimiter.RateLimit("sample", 1) if err != nil { log.Fatal(err) } if ng { fmt.Printf("NG res = %+v\n", res) continue } fmt.Printf("OK res = %+v\n", res) } }
- MaxRate -> 最大レートです。秒間Nセルまでに制限します。
- MaxBurst-> バースト数です。内部ではDELAY_VARIATION_TORELANCEの幅に使われています。１秒のウィンドウで１セルなのか100秒のウィンドウで100セルなのか、レートは同じでもバーストはかけられます。
go run で動くようになっているので、試してみるとわかりやすいと思います。
throttled はHTTPのミドルウェアもライブラリとして提供しています。 この使い方は同リポジトリのREADMEに書いてあるとおりなので割愛します。
ミドルウェアの実装を見ると難しいことはしていないので、自分で実装してしまっても良いかもしれません。
終わりに
ライブラリを使うだけなら簡単ですが、いざ使おうとしたときにどういった原理で動いているか理解していないと困ることってありますよね。 今回はGCRAについて困ったときの助けになれれば幸いです。
aptpodではサーバーサイドエンジニアを絶賛募集中です。Goをやりたい！という方、まずはカジュアル面談から会話してみませんか？ 以上です。
ありがとうございました。
