レートリミッターの設計

APIリクエストの数がレートリミッターにより閾値を超えると過剰なAPIリクエストを防ぎDoS攻撃を防止する。 レートリミッターはさまざまなアルゴリズムで実装可能。 レートリミッターはクライアントよりもサーバー側で実装されたり、APIサーバーより手前のミドルウェア(API ゲートウェイ)で実装する。どこに実装するのかは会社やチームの優先順位や目標に依存する。 レートリミッターを次そうするには時間がかかるため、エンジニアのリソースがない場合は、商用APIゲートウェイを利用するのが良い。

レートリミッターのアルゴリズム

• トークンバケットアルゴリズム。

  • AmazonとStripeはこのアルゴリズムを利用している。 あらかじめ決められた容量を持つバケットにトークンを入れ、リクエストが来るたびにトークンを取り出す(消費する)。 トークンがない場合はリクエストを拒否する。 バケットサイズと補充率を調整することで、リクエストの許可数を調整できる。一方でこの調整が難しいらしい。

• リーキーバケットアルゴリズム。

  • 先入れ先だしのキューで実装される。 Shopifyが使用しちる。バケットにリクエストを入れ、一定時間ごとにリクエストを処理する。 バケットサイズと流出率を調整することで、リクエストの許可数を調整できる。

• 固定ウィンドウカウンタアルゴリズム。

  • タイムウィンドウサイズ内でのリクエスト数をカウントし、閾値を超えるとリクエストを拒否する。 時間単位は1秒で、システムが1秒間に最大3つのリクエストを許可している。と3つ以上のリクエストを受信した場合、4つ目のリクエストは拒否される。

• スライディングウィンドウログアルゴリズム。

  • リクエストのタイムスタンプを追跡して、Redisのようなキャッシュに保存される。 新しいリクエストが来たら、古いリクエストは削除して、新しいリクエストを追加する。 ログのサイズが許容カウントよりも大きい場合、リクエストを拒否する。

• スライディングウィンドウカウンタアルゴリズム。

  • 固定ウィンドウカウンタアルゴリズムとスライディングウィンドウログアルゴリズムのハイブリッド。

レートリミッターを実装するのであれば、ディスクアクセスの遅いデータベースではなく、メモリアクセスの速いRedisなどのキャッシュを利用するのが良い。 クライアントはX-Ratelimit-remaining, X-Ratelimit-limit, X-Ratelimit-Retry-Afterを確認して、リクエストの制限数などを確認する。

参照

システム設計の面接試験