元にした自社ブログ: https://www.aceround.app/blog/ja/backend-developer-interview-ai
バックエンドのシステム設計面接で「API Gateway にレートリミッターを入れるならどう設計しますか？」と聞かれたとき、単に「Redis を使います」と答えるだけでは弱いです。面接官が見たいのは、どの制御アルゴリズムを選び、どの性質を捨て、分散環境でどこが壊れるかまで説明できるかです。
この記事では、まず単一プロセスで Token Bucket を実装し、その後に分散 API Gateway へ拡張するときの論点を整理します。コードは Node.js だけで動きます。
結論
Token Bucket は、短いバーストを許容しながら長期的な平均流量を制御したい API に向いています。
-
capacity: 一時的に許す最大バースト数 -
refillPerSecond: 1 秒あたりに補充する token 数 - リクエストごとに token を消費し、足りなければ 429 を返す
固定ウィンドウカウンターより実装は少し複雑ですが、ウィンドウ境界でリクエストが集中する問題を避けやすいです。
なぜ固定ウィンドウだけでは足りないのか
例えば「1 分 60 回まで」という固定ウィンドウをそのまま実装すると、ユーザーは 12:00:59 に 60 回、12:01:00 に 60 回リクエストできます。実質 2 秒で 120 回通ってしまいます。
Token Bucket では「token が時間で少しずつ戻る」ので、この境界バーストが起きにくくなります。一方で、capacity までは意図的にバーストを許せます。これは UI の再読み込み、短時間のリトライ、モバイル回線の揺れを完全に弾きたくない API と相性が良いです。
最小実装
以下を token-bucket.js として保存し、node token-bucket.js で実行できます。
class TokenBucket {
constructor({ capacity, refillPerSecond, now = () => Date.now() }) {
if (capacity <= 0) throw new Error("capacity must be positive");
if (refillPerSecond <= 0) throw new Error("refillPerSecond must be positive");
this.capacity = capacity;
this.refillPerSecond = refillPerSecond;
this.now = now;
this.tokens = capacity;
this.updatedAt = now();
}
take(cost = 1) {
this.refill();
if (this.tokens < cost) {
return {
allowed: false,
remaining: this.tokens,
retryAfterMs: Math.ceil(((cost - this.tokens) / this.refillPerSecond) * 1000),
};
}
this.tokens -= cost;
return {
allowed: true,
remaining: this.tokens,
retryAfterMs: 0,
};
}
refill() {
const current = this.now();
const elapsedSeconds = (current - this.updatedAt) / 1000;
if (elapsedSeconds <= 0) return;
this.tokens = Math.min(
this.capacity,
this.tokens + elapsedSeconds * this.refillPerSecond,
);
this.updatedAt = current;
}
}
let t = 0;
const bucket = new TokenBucket({
capacity: 5,
refillPerSecond: 2,
now: () => t,
});
console.log("burst:");
for (let i = 0; i < 7; i += 1) {
console.log(i + 1, bucket.take());
}
t += 1500;
console.log("after 1.5s:");
for (let i = 0; i < 4; i += 1) {
console.log(i + 1, bucket.take());
}
期待される挙動は次の通りです。
- 最初の 5 回は通る
- 6 回目と 7 回目は拒否される
- 1.5 秒後に 3 token 補充される
- その後 3 回は通り、4 回目は拒否される
now を外から注入している理由は、テストで時間を自由に進めるためです。実装の本質は Date.now() ではなく、最後に補充した時刻との差分から token 数を再計算することです。
HTTP API に置くなら何を返すか
HTTP ミドルウェアとして使う場合、最低限返したいのは次の 3 つです。
HTTP/1.1 429 Too Many Requests
Retry-After: 2
X-RateLimit-Remaining: 0
Retry-After はクライアント側の指数バックオフと相性が良いです。単に 429 だけ返すと、クライアントが即時リトライしてさらに負荷を増やすことがあります。
面接で説明すべき設計上の論点
1. key を何にするか
最初に決めるべきなのは、bucket の単位です。
- 未ログイン API: IP アドレス
- ログイン後 API: userId
- 外部公開 API: API key
- 高コスト処理: userId + endpoint
「全 API を userId だけで制限します」と答えると、重いエンドポイントと軽いエンドポイントが同じ予算を奪い合う設計になります。面接では、エンドポイント別の重み付けや cost の導入まで話せると強いです。
2. 単一プロセス実装は水平スケールで壊れる
上の実装は 1 プロセス内では正しく動きます。しかし API Gateway が 10 台あると、各プロセスが別々の bucket を持つため、実効上の上限が 10 倍になります。
分散環境では、状態を共有ストアに移します。典型的には Redis を使い、次の更新を 1 回の原子的操作にまとめます。
key = rate:user:{userId}
value = { tokens, updatedAt }
1. 現在値を読む
2. 経過時間から tokens を補充する
3. 足りるなら消費する
4. tokens と updatedAt を保存する
5. allowed / retryAfter を返す
重要なのは、読み取りと書き込みを分けないことです。高並列では race condition が起きます。本番では Redis Lua script や Redis Function で「読む、計算する、書く」を 1 命令として扱うのが安全です。
3. Redis 障害時に fail-open か fail-closed か
レートリミッターは保護装置ですが、依存先でもあります。Redis が落ちたときに全 API を止めるのか、制限なしで通すのかを決める必要があります。
- 認証、決済、在庫確保のような高リスク API: fail-closed 寄り
- 読み取り中心の低リスク API: fail-open 寄り
- 中間案: ローカルの粗い制限に一時退避する
この判断は技術だけでなく、プロダクトのリスク許容度に依存します。システム設計面接では、ここを「要件として確認する」と言えるだけで印象が変わります。
よくある落とし穴
token を整数だけで持つ
refillPerSecond = 0.5 のような低速制限を扱うなら、小数 token を保持する方が自然です。整数に丸めると補充タイミングが粗くなり、期待より厳しい制限になります。
TTL を設定しない
Redis に bucket を保存する場合、使われなくなった userId や API key の状態が残り続けます。capacity / refillPerSecond から「満杯に戻るまでの時間」を計算し、それより十分長い TTL を設定します。
全リクエストを同じ cost にする
検索 API、画像生成 API、単純なプロフィール取得 API を同じ 1 token として扱うと、高コスト API を守れません。高価な処理ほど cost を大きくする設計が必要です。
まとめ
Token Bucket の説明で見るべきポイントは、コードそのものよりも次の 4 つです。
- バースト許容量と平均流量を分けて説明できるか
- 固定ウィンドウとの違いを境界バーストで説明できるか
- 分散環境で状態をどこに置くかを説明できるか
- Redis 障害時の fail-open / fail-closed を要件として扱えるか
面接では、まず単一プロセスの正しい実装を示し、その後で「このままでは水平スケール時に壊れる」と自分から言えると、実装力とシステム設計力の両方を示せます。