Rate Limit アルゴリズムの比較と事例調査

Giselle の API に Rate Limit を実装するにあたり、レートリミットアルゴリズムについて調査しました。

Rate Limit は、システムへの過剰なリクエストを防ぎ、可用性とセキュリティ（DoS 攻撃対策など）を維持するために不可欠な仕組みです。この記事では、代表的なアルゴリズムの特徴と選定指針をまとめます。

アルゴリズム比較表

アルゴリズム	特徴	バースト許容	メモリ効率	精度	実装難易度
Fixed Window Counter	シンプル、境界でバースト可能	△	最高	低	低
Sliding Window Log	正確、メモリ使用量大	×	低	最高	中
Sliding Window Counter	Fixed + Sliding の中間	○	高	高	中
Token Bucket	バースト許容、平滑化	◎	高	中	中
Leaky Bucket	一定レートで処理	×	高	中	中

1. Fixed Window Counter（固定ウィンドウカウンタ）

時間を一定の間隔（1分間など）で区切り、その中でカウントする最もシンプルな方法です。

Window 1 (12:00:00-12:00:59)    Window 2 (12:01:00-12:01:59)
┌─────────────────────────┐    ┌─────────────────────────┐
│  count: 45/60           │    │  count: 12/60           │
│  ████████████░░░░░░░░░  │    │  ████░░░░░░░░░░░░░░░░░  │
└─────────────────────────┘    └─────────────────────────┘

仕組み

「1分」「1時間」など 固定の時間枠 ごとにカウンタをリセット
例：1分あたり100リクエスト
- 12:00:00〜12:00:59 → 最大100
- 12:01:00 でリセット

メリット

実装が非常に簡単
Redis / インメモリで容易に実装可能
1レコード/ウィンドウで済むため効率的

デメリット：境界問題（Boundary Problem）

Window 1の最後      Window 2の最初
    ↓                    ↓
────────────┼────────────┼────────────
   59秒目に   │  1秒目に
   60リクエスト│  60リクエスト
            │
         2秒間で120リクエスト可能！

これは「境界問題（boundary problem）」や「burst at window edges」と呼ばれ、Fixed Window の最大の弱点です。

向いている用途

管理画面
多少のバーストを許容できる API
MVP・初期実装

実際の採用事例

GitHub API

GitHub API は Fixed Window ベースの Rate Limit を採用しています。GitHub API の公式ドキュメントで詳細が公開されています。

未認証: 60リクエスト/時間（IPアドレス単位）
Personal Access Token: 5,000リクエスト/時間（ユーザー単位）
GitHub Apps (Enterprise Cloud): 15,000リクエスト/時間

レスポンスヘッダーで残りリクエスト数やリセット時刻を確認できます。

X-RateLimit-Limit: 5000
X-RateLimit-Remaining: 4999
X-RateLimit-Reset: 1372700873

X (Twitter) API

X API は 15分間の固定ウィンドウ を採用しています。X API の公式ドキュメントで詳細が公開されています。

ほとんどのエンドポイント: 15分あたり n リクエスト
一部のエンドポイント（ツイート投稿など）: 3時間あたり300リクエスト

認証方法によって制限が異なり、OAuth 1.0a ではユーザー単位、OAuth 2.0 Bearer Token ではアプリ単位で制限されます。

Slack API

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 されても他のメソッドは引き続き利用可能です。

Giselle での実装例

今回の 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）

シンプルさとパフォーマンスのバランスが取れた選択です。

2. Sliding Window Log（スライディングウィンドウログ）

固定ウィンドウの境界問題を解決するための手法です。

仕組み

各リクエストの タイムスタンプをすべて記録
「直近60秒間に何回あったか」を毎回計算
新しいリクエストが来たら、現在から「1分前」より古いログを削除
残ったログの数が上限以下であれば許可

メリット

最も正確 な Rate Limit が可能
境界バーストが起きない

デメリット

すべてのリクエストのタイムスタンプを保存・計算するため メモリ消費量が多い
高トラフィックには不向き

向いている用途

高精度な制限が必要
ユーザー数・リクエスト数が少ない API
厳密さが求められる場面

実装パターン

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 への移行が推奨されます。

3. Sliding Window Counter（スライディングウィンドウカウンタ）

「Fixed Window」の低負荷さと「Sliding Window Log」の正確さを組み合わせた折衷案です。

仕組み

直前ウィンドウと現在ウィンドウの 加重平均 で計算します。

effective_count =
  current_window_count +
  previous_window_count × overlap_ratio

例えば、ウィンドウが1分で、現在時刻が12:01:30の場合：

前のウィンドウ（12:00:00-12:00:59）のカウント × 0.5
現在のウィンドウ（12:01:00-12:01:59）のカウント

メリット

Fixed Window より滑らか
Log 方式より軽量
境界問題も緩和される

デメリット

完全な正確性はない（近似）

向いている用途

多くの API Gateway
精度と性能のバランス重視

実際の採用事例

Cloudflare

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% の誤差率という高い精度を実現しています。

また、以下の最適化も行われています。

最小限のストレージ: カウンター1つあたり2つの数値のみ
アトミック操作: 単一の INCR コマンドで実装
非同期カウント: 正規のリクエストを遅延させない

4. Token Bucket（トークンバケット）

最も一般的に利用されているアルゴリズムで、Amazon API Gateway、Stripe など多くのサービスで採用されています。

仕組み

一定の容量を持つ「バケット（桶）」に、一定の割合でトークンが補充される
リクエストが来るたびに、バケットからトークンを1つ消費
バケットが空の場合、リクエストは拒否

バケット容量: 10トークン
補充レート: 1トークン/秒
→ 瞬間的に10リクエスト可能、その後は1リクエスト/秒

メリット

短時間のバーストを許容 しつつ、平均レートを制限できる
実世界の API 制限と相性が良い
ユーザー体験を重視

デメリット

実装がやや複雑
分散環境では同期が必要

向いている用途

公開 API
ユーザー体験を重視する API
Stripe / AWS API 系

実際の採用事例

Stripe

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

Discord API は Token Bucket ベースの Rate Limit を採用しています。Discord API の公式ドキュメントで詳細が公開されています。

グローバル制限: 50リクエスト/秒（全エンドポイント合計）
ルート別制限: エンドポイントごとに異なる制限

レスポンスヘッダーで制限状況を確認できます。

X-RateLimit-Limit: 5
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1470173023.123
X-RateLimit-Bucket: abcd1234

特徴的なのは X-RateLimit-Bucket ヘッダーで、同じバケットを共有するエンドポイントをグループ化できます。また、リソース（guild_id、channel_id など）ごとに独立した制限が適用されるため、あるチャンネルで制限されても他のチャンネルには影響しません。

5. Leaky Bucket（リーキーバケット）

Token Bucket に似ていますが、リクエストの処理速度に焦点を当てています。

仕組み

底に穴が開いたバケットを想像
リクエストはバケットに入り、一定の速度（穴から漏れる水）で処理
バケットが溢れた場合、新しいリクエストは破棄

メリット

出力（処理）を 常に一定のペースに保つ ことができる
下流システムを確実に保護
トラフィックの平滑化に向いている

デメリット

バーストは即座に遅延 or ドロップ
レイテンシが増える

向いている用途

バックエンド保護
非同期ジョブ・キュー
ネットワークトラフィック制御

実際の採用事例

Shopify

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 を採用しました。選定理由は以下の通りです。

シンプルさ - 実装・理解が容易
効率性 - 1レコード/ウィンドウで済む
アトミック操作 - DB の upsert で競合状態を回避
十分な精度 - 多くのユースケースで許容範囲

境界問題は存在しますが、今回のユースケースでは許容範囲と判断しました。より厳密な制御が必要になった場合は、Sliding Window Counter や Token Bucket への移行を検討します。

以上、Rate Limit アルゴリズムの比較と事例調査について、現場からお送りしました。