本記事では、API のレート制限 (Rate limiting) について解説します。

レート制限

レート制限とは ユーザが一定期間に API に送信できるリクエスト数を制限 することです。

下記のように、レート制限はサービスの安定性を確保し、悪意のある攻撃から守るだけでなく、公正な利用とリソース管理にも寄与します。

悪意のあるユーザからの保護
- 悪意のあるユーザが連続して多数のリクエストを送信することを防ぎます。
一部のユーザによるAPIの過剰利用の防止
- 一部のユーザがAPIを過剰に使用することを防ぎ、正常なユーザへのサービス提供を安定化します。
リソースの適切な管理と公平な分配
- サーバのリソースを適切に管理し、公平に分配する手段となります。
サービスのクラッシュの回避
- リクエストの過剰な送信を防ぎ、サービスがクラッシュするリスクを低減させます。

制限対象

レート制限は、さまざまな対象に適用され、その制約の対象はいくつかのカテゴリに分類できます。

ユーザベース
- 対象: 特定のユーザからのリクエスト
- 目的: 過剰なリクエスト、スパムアカウント作成、不正ログインなどの防止
- 識別方法: ユーザ ID、ユーザのロール、IP アドレス、メールアドレスなど
- 懸念事項: 不正アクセス者が別のユーザー ID を作成したり、ユーザー ID や IP アドレスを偽装することで制限を回避する可能性があります。
ロケーションベース
- 対象: 特定の地域からのリクエスト
- 目的: 特定の地域からの攻撃の防止
- 識別方法: 国コード、地域コード、IP アドレスの範囲など
- 懸念事項: ユーザが VPN やプロキシサーバなどを使用する場合、正確なロケーション情報が得られない可能性があります。
サーバベース
- 対象: 特定のサーバやサーバグループ
- 目的: 複数のサーバでサービスを提供する場合、各サーバごとにアクセス数や処理量を制限することでサービスの安定性を維持する
- 識別方法: サーバ ID、ホスト名、IP アドレスなど
- 懸念事項: 複数のサーバを管理する必要があり、これがシステム全体の複雑性を増加させる可能性があります。
操作ベース
- 対象: 特定の操作（画像のアップロードやクレジットカード情報の更新など）
- 目的: 特定の操作の頻度を管理し、不正利用を防ぐ
- 識別方法: リクエストのメソッド、API エンドポイントなど
- 懸念事項: 操作によって制限を変えると、ユーザはどのリクエストがどのくらいの頻度で実行できるのか予測が難しくなる可能性があります。
時間帯ベース
- 対象: 特定の時間帯や期間におけるリクエスト
- 目的: トラフィックのピーク時や予測される負荷増加時に制限をかけ、サービスの安定性を確保する
- 識別方法: 時間帯、曜日、祝日など
- 懸念事項: タイムゾーンや利用者の行動パターンに合わせて調整する必要があります。

小規模なサービスでは、通常、最初にユーザーベースのレート制限を考慮することが一般的です。ただし、サービスの性質や要件によっては、ロケーションベースやサーバベースなどの制限を追加することが有効な場合もあります。小規模なサービスでは、複雑性を最小限に抑えるために、必要に応じて段階的にこれらの制限を追加することが重要です。

レート制限情報の保存場所

レート制限情報を保存する場所は、サービスの規模や性質、要件によって異なります。

ファイル
- 小規模なプロジェクトではファイル内に制限情報を保存することがあります。
- ファイルへの保存は、シンプルで導入が容易な反面、スケーラビリティの面で課題があります。
- Web フレームワークの Laravel ではデフォルトでファイルにレート制限情報を保存します。
リレーショナルデータベース
- リレーショナルデータベース (MySQL や PostgreSQL など) は、大量のデータを効率的に管理できます。
- キャッシュよりも読み書きには遅延が発生する可能性があります。
キャッシュシステム
- キャッシュシステム (Redis や memcached など) を利用することで、高速な読み書きが可能です。
- サーバーが再起動されるとキャッシュがクリアされ、データが失われる可能性があります。
- fastapi-limiter では Redis を利用しています。また、SlowApi では Redis や memcached を利用しています。

特に理由がなければ Redis を使用するのがよいかもしれません。Figma などの大規模なシステムでも使用され、Redis を使用することを前提としているレート制限ライブラリも多く存在します。
また、Redis はレート制限において一般的に利用されるデータベースであり、そのために蓄積された情報も非常に豊富です。

現在のレート制限の状況

各レスポンスで送信されるヘッダーを使用して、レート制限の現在の状況をユーザに提供する場合があります。

標準的な仕様はないですが、draft-polli-ratelimit-headers-00 で以下のヘッダーが提案されています。

Ratelimit-Remaining: 現在許可されている残りのリクエスト
Ratelimit-Limit: 単位時間あたりの最大リクエスト数
RateLimit-Reset: 上限がリセットされるまでの残り期間、もしくはリセットされたときのタイムスタンプ

ただし、実際のサービスでは X- の接頭辞が用いられている場合が多いです。(X-Ratelimit-Remaining、X-Ratelimit-Limit、X-RateLimit-Reset)

また、Githubでは x-ratelimit-limit、X では x-rate-limit-limit のように、すべて小文字であったり、ハイフンが追加される場合もあります。

slack の Retry-After (同じリクエストを再試行する前に待機すべき秒数)のように他の種類のヘッダーも使用されることもあります。

レート制限を超えた場合の処理

レート制限を超えた場合、通常、ユーザに HTTP エラーコードとメッセージを送信します。

HTTP エラーコードは 429 もしくは 403 です。
メッセージは API rate limit exceeded や Too Many Requests などです。

レート制限には標準的な仕様がなく、上記はあくまでも一般的に用いられている方法です。

アルゴリズム

レート制限を超えているかを判断するために様々なアルゴリズムが利用されます。

以下では、一般的にレート制限の実装に使用されるアルゴリズムを紹介します。

トークンバケット

トークンバケット (token bucket) を用いたレート制限ではバケットと呼ばれる仕組みを利用します。

バケットが保持できるトークン数には上限があります。
バケットはトークンと呼ばれる単位を保持し、トークンは一定の間隔で追加されます。
リクエストごとにトークンが消費されます。
トークンが残っている場合、リクエストは処理されます。
トークンが残っていない場合、リクエストは拒否もしくは処理が遅延されます。

アルゴリズムが単純で実装が容易です。

このアルゴリズムは Twitch などのレート制限で使用されています。

リーキーバケット

リーキーバケット (leaky bucket) を用いたレート制限ではバケットと呼ばれる仕組みを利用します。

バケットが保持できるトークン数には上限があります。
バケットから一定時間ごとにトークンを削除します。
バケットの限度を超えない場合、トークンを追加し、リクエストを処理します。
バケットの限度を超える場合、リクエストは拒否もしくは処理が遅延されます。

アルゴリズムが単純で実装が容易です。
このアルゴリズムは Shopify などのレート制限で使用されています。

固定ウィンドウカウンタ

固定ウィンドウカウンタ (fixed window counter)を用いたレート制限では、一定の期間を指すウィンドウと呼ばれる概念を導入して、その範囲ごとのリクエストの頻度を制限します。

ウィンドウサイズを設定します。
例: 1 秒間、5 分間
ウィンドウ内でのリクエストの最大数を閾値として設定します。
例: 1 秒間に 10 リクエスト
リクエストごとにカウンタを増やします。
ウィンドウの開始時にカウンタがリセットされます。
例: 10 秒の固定ウィンドウの場合、0 秒目、10 秒目、20 秒目 ... のように各 10 秒ごとに新しいウィンドウが開始されます。
ウィンドウ内でのリクエストの数が設定した閾値以下の場合、リクエストは通常通り処理します。
ウィンドウ内でのリクエストの数が設定した閾値を超える場合、リクエストを拒否や遅延などの制限を行います。

ウィンドウの境界でリクエストが集中すると、その境界周辺の短期間で制約の 2 倍のリクエストを処理する必要がある場合があります。

スライディングウィンドウ

スライディングウィンドウは、固定ウィンドウカウンタと同様に、ウィンドウ（一定の時間範囲）と呼ばれる概念を導入して、その範囲ごとのリクエストの頻度を制限します。

スライディングウィンドウは新しいリクエストが到着するたびにウィンドウをスライドさせます。そのウィンドウ内でのリクエスト数が上限を超える場合、リクエストを拒否や遅延などの制限を行います。

スライディングウィンドウは、スライディングウィンドウログとスライディングウィンドウカウンタという 2 つのアプローチがあります。

スライディングウィンドウログ

スライディングウィンドウログ (sliding window logs) は各リクエストのタイムスタンプをすべて保存し、そのログに基づいてレート制限を行います。

ウィンドウサイズ (例: 5 秒間) と閾値 (例: 1 秒間に 10 リクエスト) を定義します。
リクエストごとにタイムスタンプをログに記録し、ウィンドウ外のタイムスタンプはログから削除します。
ログの合計が閾値を超えていない場合、リクエストは通常通り処理されます。
ログの合計が閾値を超えた場合、リクエストは制限されます。

参照元: Rate Limiting Part 1 | Hechao's Blog

ログのサイズが大きくなるため、メモリや処理能力の負荷が大きいです。

スライディングウィンドウカウンタ

スライディングウィンドウカウンタ (sliding window counter) は固定ウィンドウカウンターとスライディングウィンドウログを組み合わせたものです。

ウィンドウサイズ (例: 5 秒間) と閾値 (例: 1 分間に 10 リクエスト) を定義します。
ウィンドウごとにリクエスト数をカウントします。
リクエストごとに、前のカウンタも考慮した上で、リクエストを制限するか判断します。

直前のウィンドウのリクエスト数 × ((ウィンドウサイズ - 現在のウィンドウが開始してからの経過時間) ÷ ウィンドウサイズ) + 現在のウィンドウのリクエスト数」が閾値を超えるとリクエストを制限します。

※ ウィンドウサイズと現在のウィンドウが開始してからの経過時間は同じ単位