システム設計の面接試験を読んでいて、レートリミッターのアルゴリズムについてはじめはうまく理解できなかったため、頭の整理がてら調べてみる。
そもそもレートリミッターとは
アクセスが集中することによる過負荷を防ぐことを目的として使われる。
プロモーション時のスパイクやDDoS攻撃などでAPIへのアクセスが集中すると、その裏で稼働するサーバーがリソース不足に陥り他ユーザーへのレスポンスが遅延したり、パブリッククラウドのようなオンデマンドなコンピューティングを利用していれば利用コストが跳ね上がってしまったりしかねない。
そこで、クライアントとサーバーの間でアクセス量をコントロールする層の役割を果たすのが、このレートリミッターである。
調べてみた
代表的なものは以下。今回は、基本形と思われるトークンバケットとリーキーバケットについて調べる。
トークンバケット
一定間隔で供給されるトークンをバケットに貯めておき、トークンを消費することでリクエストを処理するアルゴリズム。
Amazon API Gatewayをはじめとして、Web APIでよく利用されるらしいのがトークンバケット。
API Gateway は、トークンバケットアルゴリズムを使用してトークンでリクエストをカウントし、API へのリクエストを調整します。
引用：API リクエストを調整してスループットを向上させる https://docs.aws.amazon.com/ja_jp/apigateway/latest/developerguide/api-gateway-request-throttling.html
リクエストが来た際にトークンがあれば、トークンを消費してリクエストを中継する。そのため、リクエストのバーストに備えた分のトークンを貯めておければバーストを捌ける。一方で、リクエストが来た際にトークンがなければ、リクエストは即座に破棄される。なお、トークンは一定量以上をバケットに貯めておくことはできない。
2つのパラメータでアルゴリズムを調整することになる。
リーキーバケット
上限帯域が決まっており、単位時間においてその帯域内であればリクエストを順次処理していくアルゴリズム。
トークンバケットとあわせて解説されていることが多い印象。正確ではないかもしれないが、ざっくりいうとFIFOキューという理解。Shopifyで使われているらしい。
参考：レート制限について https://www.shopify.com/jp/blog/partner-rate-limits
リクエストが来た際にバケットに空きがあればバケットへリクエストを格納していく。そして格納したリクエストは一定のペースで処理される。そのため、バーストが発生した場合にバーストに追随して処理量を増やすことはできない。ただし、バケットサイズ内にバーストのリクエスト量が収まっていれば、一定のペースで処理されていくため、いずれは処理される。
リクエストのバーストが発生しても、単位時間あたりの処理数は変わらない。そのため、一定負荷を中継し続けたいようなユースケースで利用できる。
2つのパラメータでアルゴリズムを調整することになる。
