Open1
アーキテクチャ
Tomoki Otaレートリミッタ
実装場所
クライアント
簡単に偽造できるため、信頼性が低い。また、クライアントの実装を制御できない可能性がある。
サーバ
APIサーバに置く。
ミドルウェア
クライアントとサーバの間にスロットルで制限するレートリミッターミドルウェアを作成する。
ユーザから多くのリクエストが送信され、スロットリング(制限)された場合、HTTPステータスコード429を返す。
APIゲートウェイに通常は実装されている。
APIゲートウェイとはレート制限、SSL終了、認証、IPホワイトリスト、静的コンテンツのサービスなどをサポートするフルマネージドサービス、ミドルウェア。
サーバ側 vs ゲートウェイ
- サーバ側 : プログラミング言語、キャッシュサービスに依存する。アルゴリズムの制御が可能。
- ゲートウェイ : 構築が容易。マイクロサービスアーキテクチャでAPIゲートウェイを組み込んでいる場合、APIゲートウェイにレート制限を追加できる。アルゴリズムの選択肢が限られる。
レートリミッタのアルゴリズム
トークンバケットアルゴリズム
シンプルで分かりやすい。
トークン・バケット
e.g.)Amazon, Stripeなど
メリット
- アルゴリズムの実装が簡単。
- メモリ効率が良い。
- トークンバケットは短時間のバーストトラフィックを可能にする。トークンが残っている限り、リクエストは通過できる。
デメリット
- バケットサイズとトークン補充率という2つのパラメータを適切に調整するのが難しい。
リーキーバケットアルゴリズム
FIFOで実装される。
e.g.)Shopify
メリット
- キューサイズに制限があるため、メモリ効率が良い。
- リクエストは固定レートで処理されるため、安定した流出レートが必要なユースケースに適している。
デメリット
- トラフィックのバーストは古いリクエストでキューを満たし、それらが時間内に処理されない場合、新しいリクエストはレート制限される。
- バケットサイズと流出率という2つのパラメータを適切に調整するのが難しい。
固定ウィンドウカウンタアルゴリズム
メリット
- メモリ効率が良い。
- 理解しやすい。
- 単位時間のウィンドウが終了した時点で利用可能な割り当てをリセットすることは、特定のユースケースに適合している。
デメリット
- ウィンドウの端におけるトラフィックの急増は通過する許容割り当てよりも多くの再リクエストを引き起こす可能性がある。
スライディングウィンドウログアルゴリズム
固定ウィンドウカウンタアルゴリズムの問題を解決したもの。
メリット
- 非常に正確で、どのローリングウィンドウにおいても、リクエストはレート制限を超えることはない。
デメリット
- 再探索が拒否されても、タイムスタンプがメモリに保存されている可能性があるため、メモリを多く消費する。
スライディングウィンドウカウンタ
固定ウィンドウカウンタとスライディングウィンドウログを組み合わせたハイブリッドアプローチ。
2つの実装方法がある。
メリット
- 直前のウィンドウの平均レートに基づいているため、トラフィくのスムーズな急増が可能。
- メモリ効率が良い。
####デメリット - あまり厳密でないルックバックウィンドウにしか使えない。ただし、Cloudfrareの実験では4億のリクエストのうち、間違って許可またはレート制限されたリクエストは0.003%だけ。
高度なアーキテクチャ
インメモリキャッシュを用いた同じユーザやIPアドレスなどから送られたリクエストを追跡するためのカウンタの実装。
Redis
Redisには以下の2つのコマンドがある。
- INCR
- EXPIRE
レート制限ルール
Lyft : レート制限のコンポーネントをオープンソース化した。
レート制限の超過
レート制限された場合、429を返す。または、キューに入れる。
レートリミッタのヘッダ
- X-Ratelimit-Remaining
- X-Ratelimit-Limit
- X-Ratelimit-Retry-After
ユーザがあまりに多くのリクエストを送った場合、429 too many requestsエラーとX-Ratelimit-Retry-Afterヘッダが返される。
分散環境におけるレートリミッタ
- レースコンディション
- 同期の問題
モニタリング
- レートリミッタのアルゴリズムが有効か
- レートリミッタのルールが有効か