Giselle の API に Rate Limit を実装するにあたり、レートリミットアルゴリズムについて調査しました。
Rate Limit は、システムへの過剰なリクエストを防ぎ、可用性とセキュリティ（DoS 攻撃対策など）を維持するために不可欠な仕組みです。この記事では、代表的なアルゴリズムの特徴と選定指針をまとめます。
| アルゴリズム | 特徴 | バースト許容 | メモリ効率 | 精度 | 実装難易度 |
|---|---|---|---|---|---|
| Fixed Window Counter | シンプル、境界でバースト可能 | △ | 最高 | 低 | 低 |
| Sliding Window Log | 正確、メモリ使用量大 | × | 低 | 最高 | 中 |
| Sliding Window Counter | Fixed + Sliding の中間 | ○ | 高 | 高 | 中 |
| Token Bucket | バースト許容、平滑化 | ◎ | 高 | 中 | 中 |
| Leaky Bucket | 一定レートで処理 | × | 高 | 中 | 中 |
時間を一定の間隔（1分間など）で区切り、その中でカウントする最もシンプルな方法です。
Window 1 (12:00:00-12:00:59) Window 2 (12:01:00-12:01:59)
┌─────────────────────────┐ ┌─────────────────────────┐
│ count: 45/60 │ │ count: 12/60 │
│ ████████████░░░░░░░░░ │ │ ████░░░░░░░░░░░░░░░░░ │
└─────────────────────────┘ └─────────────────────────┘
1分あたり100リクエスト
Window 1の最後 Window 2の最初
↓ ↓
────────────┼────────────┼────────────
59秒目に │ 1秒目に
60リクエスト│ 60リクエスト
│
2秒間で120リクエスト可能！
これは「境界問題（boundary problem）」や「burst at window edges」と呼ばれ、Fixed Window の最大の弱点です。
GitHub API は Fixed Window ベースの Rate Limit を採用しています。GitHub API の公式ドキュメントで詳細が公開されています。
レスポンスヘッダーで残りリクエスト数やリセット時刻を確認できます。
X-RateLimit-Limit: 5000
X-RateLimit-Remaining: 4999
X-RateLimit-Reset: 1372700873
X API は 15分間の固定ウィンドウ を採用しています。X API の公式ドキュメントで詳細が公開されています。
認証方法によって制限が異なり、OAuth 1.0a ではユーザー単位、OAuth 2.0 Bearer Token ではアプリ単位で制限されます。
Slack API は Tier システム を採用した Fixed Window（1分間）の Rate Limit です。Slack API の公式ドキュメントで詳細が公開されています。
| Tier | 制限 | 対象メソッド例 |
|---|---|---|
| Tier 1 | 1リクエスト/分 | 最も制限が厳しい |
| Tier 2 | 20リクエスト/分 | files.upload |
| Tier 3 | 50リクエスト/分 | 一般的なメソッド |
| Tier 4 | 100リクエスト/分 | chat.postEphemeral |
メソッドごとに異なる Tier が割り当てられており、あるメソッドが Rate Limit されても他のメソッドは引き続き利用可能です。
今回の PR feat(api/apps/run): add team-scoped rate limiting to App Run API · #2603 では Fixed Window Counter を採用しました。
// 60秒の固定ウィンドウ
const WINDOW_SECONDS = 60;
// ウィンドウ開始時刻でキー付け
const windowStart = Math.floor(Date.now() / 1000 / WINDOW_SECONDS) * WINDOW_SECONDS;
// アトミックなカウンター増加（INSERT ... ON CONFLICT DO UPDATE）シンプルさとパフォーマンスのバランスが取れた選択です。
固定ウィンドウの境界問題を解決するための手法です。
Sliding Window Log はメモリ消費量の多さから大規模サービスでの採用は少なく、多くのサービスは Sliding Window Counter や Token Bucket を選択しています。
典型的な実装では、Redis の Sorted Set を使用します。
MULTI
ZREMRANGEBYSCORE $key 0 ($currentTime - $window)
ZADD $key $currentTime $uniqueRequestId
ZCARD $key
EXPIRE $key $window
EXEC
MULTI / EXEC による原子性が、分散環境での競合状態を防止します。高トラフィック環境では Sliding Window Counter への移行が推奨されます。
「Fixed Window」の低負荷さと「Sliding Window Log」の正確さを組み合わせた折衷案です。
直前ウィンドウと現在ウィンドウの 加重平均 で計算します。
effective_count =
current_window_count +
previous_window_count × overlap_ratio
例えば、ウィンドウが1分で、現在時刻が12:01:30の場合：
Cloudflare は Fixed Window の境界問題を解決するため、Sliding Window Counter を採用しています。公式ブログで詳細な実装が公開されています。Cloudflare の公式ドキュメントも参照してください。
計算式:
rate = previous_count × ((window_size - elapsed) / window_size) + current_count
例：50リクエスト/分の制限で、前の1分間に42リクエスト、現在の1分間（開始から15秒経過）に18リクエストがあった場合：
rate = 42 × ((60 - 15) / 60) + 18
= 42 × 0.75 + 18
= 49.5 リクエスト
Cloudflare の分析によると、4億リクエストで 0.003% の誤差率という高い精度を実現しています。
また、以下の最適化も行われています。
INCR コマンドで実装最も一般的に利用されているアルゴリズムで、Amazon API Gateway、Stripe など多くのサービスで採用されています。
バケット容量: 10トークン
補充レート: 1トークン/秒
→ 瞬間的に10リクエスト可能、その後は1リクエスト/秒
Stripe は Token Bucket を採用しており、公式ブログで詳細な実装を公開しています。Stripe API の公式ドキュメントも参照してください。各ユーザーにバケットが割り当てられ、Redis を使用して低レイテンシを実現しています。
Stripe は実際には 4種類のリミッター を組み合わせて使用しています。
| リミッター | 目的 |
|---|---|
| Request Rate Limiter | ユーザーあたり n リクエスト/秒（バースト許容） |
| Concurrent Requests Limiter | 同時リクエスト数を制限（CPU集約的なエンドポイント向け） |
| Fleet Usage Load Shedder | インフラ使用率が90%を超えたら非重要リクエストを拒否 |
| Worker Utilization Load Shedder | サーバー単位でトラフィックを4カテゴリに分類し優先制御 |
デフォルトでは 25リクエスト/秒 の制限があります。
Discord API は Token Bucket ベースの Rate Limit を採用しています。Discord API の公式ドキュメントで詳細が公開されています。
レスポンスヘッダーで制限状況を確認できます。
X-RateLimit-Limit: 5
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1470173023.123
X-RateLimit-Bucket: abcd1234
特徴的なのは X-RateLimit-Bucket ヘッダーで、同じバケットを共有するエンドポイントをグループ化できます。また、リソース（guild_id、channel_id など）ごとに独立した制限が適用されるため、あるチャンネルで制限されても他のチャンネルには影響しません。
Token Bucket に似ていますが、リクエストの処理速度に焦点を当てています。
Shopify は全 API で Leaky Bucket を採用しています。Shopify API の公式ドキュメントで詳細が公開されています。
REST Admin API の制限:
| プラン | バケットサイズ | リークレート |
|---|---|---|
| 標準 | 40リクエスト/app/store | 2リクエスト/秒 |
| Shopify Plus | 400リクエスト/app/store | 20リクエスト/秒 |
レスポンスヘッダーで現在の使用状況を確認できます。
X-Shopify-Shop-Api-Call-Limit: 32/40
GraphQL Admin API では、リクエスト数ではなく 計算クエリコスト に基づいて制限されます。複雑なクエリほど多くのポイントを消費する仕組みです。
なお、Storefront API には Rate Limit がなく、フラッシュセールなどの急激なトラフィック増加にも対応できるよう設計されています。
実際のシステムでは、複数の Rate Limit を組み合わせることが一般的です。
| レイヤー | 手法 |
|---|---|
| Edge / CDN | Fixed or Sliding Window |
| API Gateway | Token Bucket |
| バックグラウンド | Leaky Bucket |
| 要件 | 推奨アルゴリズム |
|---|---|
| 実装最優先 | Fixed Window Counter |
| 精度最優先 | Sliding Window Log |
| バランス型 | Sliding Window Counter |
| UX重視 | Token Bucket |
| 下流保護 | Leaky Bucket |
今回の Giselle の PR では Fixed Window Counter を採用しました。選定理由は以下の通りです。
境界問題は存在しますが、今回のユースケースでは許容範囲と判断しました。より厳密な制御が必要になった場合は、Sliding Window Counter や Token Bucket への移行を検討します。
以上、Rate Limit アルゴリズムの比較と事例調査について、現場からお送りしました。