レート制限はプロダクションAPIを構成する重要な要素です。バックエンドサービスを悪用から保護し、公平なリソース割り当てを保証し、負荷時のパフォーマンスを維持し、DoS攻撃を軽減します。本記事では主要なレート制限アルゴリズムとそのトレードオフ、実装パターン、ベストプラクティスを解説します。
トークンバケットアルゴリズム
トークンバケットは最も広く使われているレート制限アルゴリズムのひとつです。バケットは一定レートで補充されるトークンを保持し、各リクエストがトークンをひとつ消費します。バケットが空の場合はリクエストが拒否されます。このアプローチはバケット容量までのバーストを許可しつつ、長期的なトラフィックを平滑化します。
class TokenBucket {
constructor(capacity, refillRate) {
this.capacity = capacity;
this.tokens = capacity;
this.refillRate = refillRate;
this.lastRefill = Date.now();
}
tryConsume() {
this._refill();
if (this.tokens > 0) { this.tokens--; return true; }
return false;
}
_refill() {
const now = Date.now();
const elapsed = (now - this.lastRefill) / 1000;
this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillRate);
this.lastRefill = now;
}
}
実装はシンプルで、クライアントあたり1つのカウンタのみで動作し、メモリ効率に優れています。バースト許容が求められる汎用的なレート制限に適しています。
リーキーバケットアルゴリズム
リーキーバケットは厳格な出力レートを強制します。リクエストはキューに入り、固定レートで処理されるため、バーストを完全に防ぎます。急激なトラフィック増加に対応できない下流システムを保護する場合に最適です。ただし、キューを保持するためメモリ使用量が増加し、バースト処理は一切できません。
スライディングウィンドウアルゴリズム
スライディングウィンドウは固定ウィンドウ方式よりも正確なレート制限を提供します。スライディングウィンドウログは現在のウィンドウ内の全リクエストのタイムスタンプを保存し、リクエストのたびにウィンドウ外のエントリを削除して残数をカウントします。最も正確ですが、タイムスタンプをすべて保存するためメモリ集約的であり、低トラフィックか精度が最優先されるシナリオに適しています。
スライディングウィンドウカウンターは、前のウィンドウのカウントと現在のウィンドウの部分カウントを重み付きで組み合わせて近似レートを計算します。クライアントあたり2つのカウンタのみで動作し、ほとんどのユースケースで十分な精度を提供します。StripeやGitHubでも採用されている業界標準の手法です。
Redisベースの実装
Redisは分散レート制限のバックエンドストアとして最も一般的です。INCRやEXPIREによるアトミック操作がスレッド安全性を保証し、TTLによる自動クリーンアップ、Luaスクリプトによる複雑なアルゴリズムの実装が可能です。
const { SlidingWindowRateLimiter } = require("redis-rate-limiter");
const limiter = new SlidingWindowRateLimiter({
client: redisClient,
window: 60,
limit: 100,
});
クラスタによる水平スケーリングとサブミリ秒のレイテンシもRedisの大きな利点です。本番環境では、アトミックなレート制限のためのLuaスクリプトパターン、フェイルオーバー処理、パフォーマンスチューニングが重要な考慮事項となります。
HTTPレート制限ヘッダー
標準化されたヘッダーにより、サーバーはクライアントにレート制限ステータスを通知できます。RateLimit-Limitはウィンドウ内の最大リクエスト数、RateLimit-Remainingは残りリクエスト数、RateLimit-Resetはウィンドウのリセット時間、Retry-Afterはリトライまでの待機時間を示します。
HTTP/1.1 200 OK
RateLimit-Limit: 100
RateLimit-Remaining: 87
RateLimit-Reset: 1712345678
IETF標準ドラフトがこれらのヘッダーを正式化していますが、多くのAPIは依然としてベンダー固有のX-RateLimitプレフィックスを使用しています。適切な429レスポンスのフォーマットと情報を含むレスポンスボディも、クライアントの相互運用性にとって重要です。
分散レート制限
分散システムではレート制限をインスタンス間で調整する必要があります。Redisによる集中管理は単一の真実源として一貫した制限を提供しますが、単一障害点のリスクがあります。ローカルカウンターは調整のオーバーヘッドがありませんが、負荷不均衡時に不整合が生じます。ハイブリッド方式はローカルカウンターと定期的なRedis同期を組み合わせて両者のバランスを取ります。
| 方式 | 一貫性 | 可用性 | 複雑さ |
|---|---|---|---|
| Redis集中型 | 正確 | 低い | 低い |
| ローカルカウンター | 近似 | 高い | なし |
| ハイブリッド | ほぼ正確 | 高い | 中程度 |
クライアントIPベースか認証ユーザーベースかの選択、匿名・認証・プレミアムユーザーの段階的制限も重要な設計判断です。
クライアントリトライ戦略
クライアントはレート制限応答を適切に処理するためのインテリジェントなリトライ動作を実装すべきです。指数バックオフとジッターによりシェパード問題を防止し、Retry-Afterヘッダーを尊重することでサーバーの期待に合わせた動作が可能になります。
async function fetchWithRetry(url, options = {}) {
const maxRetries = options.maxRetries || 3;
for (let i = 0; i < maxRetries; i++) {
const response = await fetch(url);
if (response.status === 429) {
const retryAfter = response.headers.get("Retry-After") || 1;
await sleep(retryAfter * 1000);
continue;
}
return response;
}
throw new Error("Max retries exceeded");
}
冪等性キーにより変更を伴うリクエストの安全なリトライが可能になり、リトライによる重複副作用を防止します。
アルゴリズム選択ガイド
| アルゴリズム | バースト対応 | メモリ | 精度 | 最適な用途 |
|---|---|---|---|---|
| トークンバケット | あり | 低 | 良好 | 汎用 |
| リーキーバケット | なし | 中 | 良好 | 安定スループット |
| 固定ウィンドウ | あり | 低 | 低い | 簡易制限 |
| スライディングウィンドウログ | あり | 高 | 優秀 | 高精度要件 |
| スライディングウィンドウカウンター | あり | 低 | 非常に良い | プロダクションAPI |
結論
適切なアルゴリズムの選択は、バースト許容度、精度、メモリ効率の要件に依存します。スライディングウィンドウカウンターはほとんどのプロダクションAPIに最適なバランスを提供し、トークンバケットはトラフィックシェーピングに優れています。サーバー側の強制、情報提供ヘッダー、協調的なクライアント動作を組み合わせることで、堅牢なAPIエコシステムを構築できます。