概要
インターネットに晒されているWebサービスでは
など、本来想定していた以上のトラフィックが来ることはよくあります。
単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。
ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。
Leaky bucket
Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。
下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。
ref: What is the difference between token bucket and leaky bucket algorithms? - Quora
メリット
- トラフィックが一定になり負荷を制御しやすい
デメリット
Token bucket
Leaky bucketが上限を設定するのに対し、Token bucketは平均に制限を課してある程度のバースト性を許容します。
仕組みは以下のフローで
ref: 限流算法之令牌桶与漏桶算法 | 0xCAFEBABE
- 定期的にtokenが発行される
- tokenが残っていればトラフィックを通す
- tokenが残っていないればトラフィックをキューで保持（破棄するロジックも多い）
- トラフィックがなければ一定量tokenを保持できる
という形です。最後のtoken保持の仕組みにより、一時的にバーストリクエストが来てもtokenが残っている限り通すことができます。
AWSのCPUクレジットやEBSバーストバランスがまさしくこのアルゴリズムですね。
メリット
- バースト性のあるトラフィックにも向いてる
Fixed window counters
Fixed window countersは[00:00, 00:01), [00:01, 00:02), ...[23:59, 00:00)のように固定した期間でのリクエスト量を制限するアルゴリズムです。
例えば以下の図では各期間２リクエストまでとなっており、３リクエスト目以降は破棄されます。
しかし新しい期間になったら再び上限までリクエストを受け付けます。
ref: Rate Limiting Part 1
メリット
- シンプルで分かりやすいし実装もしやすい
デメリット
注意点としてはFixed windowの名の通り期間が固定されているため、リクエストが期間境界に偏ると上限の倍のリクエストが来ることになります。
例）[00:00:30, 00:01:00)に２リクエスト、[00:01:00, 00:01:30)に２リクエスト来た場合、[00:00:30, 00:01:30)の１分間に上限の倍の４リクエスト来たことになる
Sliding window log
先程のFixed window countersの問題点である期間境界の偏りに対応するアルゴリズムです。
2 req/minと制限した例で説明すると、
ref: Rate Limiting Part 1
00:00:12にリクエストがくる。00:00:12を含め過去1分間のリクエストは１つ。2 req/minを満たすので許可00:00:24にリクエストがくる。00:00:24を含め過去1分間のリクエストは00:00:12と合わせて２つ。2 req/minを満たすので許可00:00:36にリクエストがくる。00:00:36を含め過去1分間のリクエストは３つ。2 req/minを満たさないので拒否00:01:25にリクエストがくる。00:01:25を含め過去1分間のリクエストは00:00:36と合わせて２つ。2 req/minを満たすので許可
という仕組みです。
メリット
- 正確に
2 req/minといった制限ができるところ
デメリット
- その期間のログを常に保持してハンドリングする必要があるので実装コストやメモリコストが高い
Sliding window counters
Fixed window countersとSliding window logを組み合わせ、それぞれの問題点を解決させたアルゴリズムです。
10 req/minという上限を設定した場合に、
ref: Rate Limiting Part 1
[00:00, 00:01)の期間に９リクエスト来た00:01:15の段階で４リクエスト目が来た00:01:15は[00:01, 00:02)期間の25%。前期間のweightは75%。9 x 0.75 + 4 = 10.75 > 10で上限を超えたので拒否00:01:30時点では前期間weightが50%。9 x 0.5 = 4.5なので、５リクエスト目までOK
というように、現期間のリクエストタイミングにより前期間にweightを付けて上限以内かどうかチェックするアルゴリズムです。
メリット
これはweightによる計算のため小数点以降の値が出てくるため正確な制限にはなりませんが、
Fixed window countersの境界問題が解決されているSliding window logのようにログを保持するコストがない
という点で改良されてます。
まとめ
rate limitの様々なアルゴリズムを紹介しました。
実務ではAWSのWAFなどマネージドを採用するケースが多いと思いますが、このようにアルゴリズムを知っていればユースケースに応じて選択・自作することもできると思います。
