60秒で3回までのAPI制限でも、固定窓なら59秒に3回と60秒に3回で、1.3秒のうちに6回通る。窓の数え方を変えるだけで守れる量は2倍変わり、スライディング窓にしてもサーバが2台になればまた2倍通る。この記事では、固定窓・スライディング窓・スライディング窓カウンタ・Redisの4つの数え方を同じ「60秒で3回」の条件で比べ、制限器が死んだときの開閉まで決める。
出発点は、LINEヤフーのコーディング試験対策で出ていた練習問題の問題5「APIレート制限(60秒で最大3回)」である。Dequeで直近60秒を数える書き方は、AIエージェントが5日間気づかれず顧客情報を抜いた――WorkOS事件の4つの弱点の中で、レート制限がなかった場合の対処としてすでに置いた。あの事件ではレート制限そのものが4つの弱点の1つだった。ここでは一歩進めて、制限を付けたつもりでも残る抜け道を扱う。
固定窓は窓の境目で2倍通る
一番素直な数え方は、時間を60秒ごとの窓に区切って窓ごとに数える固定窓である。Javaで書くと次のようになる。
import java.util.HashMap;
import java.util.Map;
public class FixedWindowLimiter {
private final int limit;
private final long windowMs;
private final Map<String, long[]> state = new HashMap<>();
public FixedWindowLimiter(int limit, long windowMs) {
this.limit = limit;
this.windowMs = windowMs;
}
public synchronized boolean allow(String key, long nowMs) {
long[] s = state.computeIfAbsent(key, k -> new long[]{nowMs, 0});
long windowStart = (nowMs / windowMs) * windowMs;
if (s[0] != windowStart) {
s[0] = windowStart;
s[1] = 0;
}
if (s[1] < limit) {
s[1]++;
return true;
}
return false;
}
}
窓が変わればカウンタは0に戻る。この「窓が変われば0に戻る」が抜け道になる。59.0秒・59.2秒・59.5秒に3回来たあと、60.1秒・60.2秒・60.3秒にまた3回来ると、どちらの窓も上限3回以内なので全部通る。検証した結果は次の通りである。
| 時刻(秒) | 59.0 | 59.2 | 59.5 | 60.1 | 60.2 | 60.3 |
|---|---|---|---|---|---|---|
| 固定窓 | 許可 | 許可 | 許可 | 許可 | 許可 | 許可 |
6件が1.3秒のうちに通った。「60秒で3回まで」というつもりが、窓をまたいだ2秒弱では6回通る。窓の境目にリクエストが集まるほど、この2倍に近づく。バースト混じりの到着列707件を1時間分シミュレーションしたところ、固定窓は179件を許可し、任意の60秒区間の最大は6件だった。上限3回のつもりが、区間の取り方次第で6件になる。
固定窓の取り柄は、持つ状態が「窓の開始時刻と件数」の2つだけで済むことである。メモリも計算も軽い。内側のAPIで、多少のバーストを許容できるなら十分に使える。ただし、守りたい量が「どの60秒を取っても3回まで」なら、固定窓はその条件を満たさない。
スライディング窓は「直近60秒」を数える
境界の抜け道を塞ぐには、窓を固定せず、リクエストが来た時点から直近60秒を数えればよい。許可したリクエストの時刻をDequeに残し、60秒より古いものを先頭から捨てる書き方である。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public class SlidingWindowLimiter {
private final int limit;
private final long windowMs;
private final Map<String, Deque<Long>> state = new HashMap<>();
public SlidingWindowLimiter(int limit, long windowMs) {
this.limit = limit;
this.windowMs = windowMs;
}
public synchronized boolean allow(String key, long nowMs) {
Deque<Long> q = state.computeIfAbsent(key, k -> new ArrayDeque<>());
while (!q.isEmpty() && q.peekFirst() <= nowMs - windowMs) {
q.pollFirst();
}
if (q.size() < limit) {
q.addLast(nowMs);
return true;
}
return false;
}
}
同じ到着列で試すと、59.0秒・59.2秒・59.5秒の3件は通り、60.1秒・60.2秒・60.3秒はすべて拒否される。59.0秒の記録が窓から出る119.1秒になって、ようやく1件通る。ランダムな到着列707件では153件の許可で、任意の60秒区間の最大は3件に収まった。固定窓の179件と比べると、境界バーストの分だけ少なくなる。
代償はメモリである。許可したリクエストの時刻を1件ずつ持つため、上限が1時間で1万回なら、1キーあたり最大1万件の時刻が残る。キーがAPIキーやユーザーIDの数だけ増えれば、その分だけ膨らむ。古い時刻は次のリクエストが来たときにしか捨てられないため、来なくなったキーのDequeも残り続ける。キーに有効期限を付けて掃除する仕組みが別に要る。
近似で済ませる手もある――スライディング窓カウンタ
時刻を全部持たずに、固定窓のカウンタ2つだけで近似する手もある。前の窓の件数に重みを掛けて、今の窓の件数に足す。重みは「今の窓に入ってからの経過時間」を窓の長さで割ったものの余りである。
public class SlidingWindowCounter {
private final int limit;
private final long windowMs;
private long prevCount;
private long currCount;
private long windowStart;
public SlidingWindowCounter(int limit, long windowMs, long nowMs) {
this.limit = limit;
this.windowMs = windowMs;
this.windowStart = (nowMs / windowMs) * windowMs;
}
public synchronized boolean allow(long nowMs) {
long start = (nowMs / windowMs) * windowMs;
if (start != windowStart) {
// 2窓以上飛んだ場合は前の窓の件数は0になる
if (start - windowStart >= 2 * windowMs) {
prevCount = 0;
} else {
prevCount = currCount;
}
currCount = 0;
windowStart = start;
}
double elapsed = nowMs - windowStart;
double estimate = prevCount * (1 - elapsed / windowMs) + currCount;
if (estimate < limit) {
currCount++;
return true;
}
return false;
}
}
境界バーストの場面で試すと、前の窓の末尾に3件、今の窓の先頭に3件、経過0.1秒の推定値は5.995で、上限3を超えるため拒否される。30秒経って今の窓が0件なら推定値は1.5で許可される。59秒経って今の窓が2件なら推定値は2.05で許可される。固定窓のカウンタ2つだけ持てばよく、時刻のリストは要らない。
ただしこれは推定である。境界付近では上限を厳密には守らない。前の窓の末尾に3件(59.0秒・59.2秒・59.5秒)、今の窓の先頭に2件(119.0秒・119.1秒)ある状態で、119.1秒に3件目を試すと推定値は2.045で許可される。だが直近60秒の実件数は59.2秒・59.5秒・119.0秒・119.1秒の4件で、上限3件を超える。少しの超過を許容できる場面では使えるが、「どの60秒を取っても3回まで」を厳密に守りたい場面では選ばない。
サーバが2台になると、Dequeの数は合わない
ここまでの数え方は、サーバが1台であることを前提にしている。サーバが2台になり、リクエストが交互に振り分けられると、それぞれのサーバが自分のDequeだけで数えるため、意図の2倍が通る。検証では、0秒から50秒まで10秒おきの6件を2台に交互に振り分けると、6件すべてが許可された。
台数が増えるほど、数える場所を1か所に集める必要が出てくる。よく使われるのはRedisのソート済みセットである。リクエストの時刻をスコアにしてため、窓から出たものを消し、残りを数え、余裕があれば追加する。4つのコマンドは分けて送ると、2台のサーバが同時に「残り3件」と読んで両方通す競合が起きる。だから1本のLuaスクリプトにして、Redisの中で原子的に実行する。
// ZREMRANGEBYSCORE・ZCARD・ZADD・PEXPIREを1本のLuaスクリプトで実行する
String script =
"redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[1] - ARGV[2]) "
+ "local n = redis.call('ZCARD', KEYS[1]) "
+ "if n < tonumber(ARGV[3]) then "
+ " redis.call('ZADD', KEYS[1], ARGV[1], ARGV[4]) "
+ " redis.call('PEXPIRE', KEYS[1], ARGV[2] + 1000) "
+ " return 1 "
+ "end "
+ "return 0";
Object r = jedis.eval(script, 1, "ratelimit:" + key,
String.valueOf(nowMs), // ARGV[1] 現在時刻(ミリ秒)
String.valueOf(windowMs), // ARGV[2] 窓の長さ
String.valueOf(limit), // ARGV[3] 上限
nowMs + ":" + UUID.randomUUID()); // ARGV[4] 一意なメンバー
boolean allowed = Long.valueOf(1).equals(r);
細部が2つある。1つはメンバーの一意性である。同じミリ秒に2件来ると、メンバーが時刻だけでは衝突して1件にまとめられてしまう。時刻:UUIDのように一意なメンバーにする。もう1つは時刻の出所である。アプリ側の時計とRedis側の時計がずれると窓がずれるため、どちらか一方の時刻に統一する。PEXPIREで窓の長さに1秒の余裕を付けておくと、使われなくなったキーが自然に消える。
この競合の形は、Two SumはcontainsKeyを先に書く――putが先だと自分とペアになるで扱った「確認してから登録する」2段構えと同じである。確認と登録の間に割り込みが入るなら、原子的な操作にまとめる。HashMapの話ではputIfAbsentがその役で、Redisの話ではLuaスクリプトがその役である。
制限器が死んだら、開けるか閉じるか
数え方を決めても、制限器そのものが死んだときの挙動が残る。Redisが応答しなくなったとき、リクエストを通すか、全部止めるかである。
| 制限器が死んだとき | 通るもの | 起きること | |
|---|---|---|---|
| フェイルオープン | 通す | 全部 | 下流が直撃を受け、障害が広がる |
| フェイルクローズ | 全部429で返す | なし | サービス全体が止まる |
どちらが正しいかは、守る対象で決まる。課金APIや外部の従量課金APIを守るなら、通し続けて請求が膨らむより止める方がましな場合が多い。読み取り専用の社内APIなら、止めるより通して業務を続けた方がましな場合が多い。決める前に、制限器が死んだときに何が一番困るかを書き出しておく。決めずに置くと、実装した人のその場の判断で決まる。
拒否するときの返し方も決めておく。429 Too Many RequestsはRFC 6585の第4節で定められた状態コードで、応答には理由の説明を含め、Retry-Afterヘッダを付けてもよいとされている。Retry-AfterはRFC 9110の10.2.3節で定められ、待つ秒数かHTTP日付の2形式を取る。秒数形式はクライアントの時計に依存しないため、レート制限の用途では秒数形式が向いている。RFC 6585は「サーバがユーザーをどう識別するか、リクエストをどう数えるかはこの仕様では定めない」とも明記している。数え方は仕様の外にあるため、この記事で比べた数え方の選択がそのまま設計になる。
呼び出し側も、429を受け取ったらすぐ送り直してはいけない。全員が同時に送り直すと、窓が開けた瞬間にまた上限に達し、リトライの波が重なる。Retry-Afterの秒数を守り、指数バックオフにジッターを混ぜて送り直す時刻を散らす。送り直しは重複処理になり得るため、冪等性の扱いもセットで決める。重複排除の考え方は決済履歴の重複排除と集計をJavaでO(n)で解く――FAILEDも「出現した」として記録する順序に置いた。
4つの数え方の選び方
| 固定窓 | スライディング窓ログ | スライディング窓カウンタ | トークンバケット | |
|---|---|---|---|---|
| どの60秒でも上限以内か | いいえ(最大2倍) | はい | 近似(少し超える) | バーストを許す設計 |
| 持つ状態 | 窓の開始時刻と件数 | 許可した時刻のリスト | 前と今の窓の件数 | トークン数と最終補充時刻 |
| サーバが増えたとき | 別途集計が必要 | Redisのソート済みセットで集計 | Redisのカウンタ2つで集計 | Redisでトークンを共有 |
| 向いている場面 | 内側のAPI、多少のバーストを許容できる場合 | 厳密に守りたい公開API | メモリを抑えつつ境界バーストを塞ぎたい場合 | 短いバーストを許しつつ平均を抑えたい場合 |
トークンバケットは、ここまでの窓とは発想が違う。窓で区切るのではなく、バケツにたまったトークンを1リクエスト1枚ずつ消費し、一定の速さで補充する。容量3・60秒で3枚の補充なら、最初に3件まで一気に通し、4件目は拒否され、20秒たつと1枚回復して1件通る。検証では0秒に3件、4件目を拒否、20秒に1件、25秒に拒否、40秒に1件、60秒に1件という動きになった。短いバーストを許しつつ、長い目で見た平均を抑えたい場合に向いている。窓の数え方とバケツの数え方は、守りたいのが「どの区間でも上限以内」か「平均の速さ」かで選ぶ。
選ぶときは、守りたい条件を先に言葉にするとよい。「どの60秒を取っても3回まで」ならスライディング窓ログ、「だいたい3回までで、少しの超過は許容できる」ならスライディング窓カウンタ、「短いバーストは許して平均を抑えたい」ならトークンバケット、「内側のAPIで軽さが最優先」なら固定窓、という順に決まる。条件を言わずに実装から入ると、固定窓の2倍のような抜け道が後から見つかる。
検証環境
- Javaのコードはこの環境にJDKがないためJVMで実行していない。構文は目視で確認した。
- ロジックはPython 3.12.3に写して検証した。固定窓の境界バースト(1.3秒で6件)、ランダムな到着列707件での任意の60秒区間の最大(固定窓6件・スライディング窓3件)、サーバ2台への振り分け(6件すべて許可)、トークンバケットの補充(20秒に1枚)、スライディング窓カウンタの推定値(境界直後5.995で拒否、30秒経過で1.5で許可、59秒経過で2.05で許可)とその弱点(直近60秒の実件数4件)をすべて確認した。
- RFC 6585とRFC 9110の該当箇所、Redisのソート済みセットを使ったスライディング窓の実装例は、2026-11-14に一次資料と実装例で確認した。
今後見るべきもの
- 自分のAPIのレート制限が固定窓かスライディング窓か。固定窓なら、窓の境目にリクエストが集まったときの実測値を取る。境目に集まるのは、クライアントが決まった時刻に一斉に動く場合に起きやすい。
- 制限の単位が何か。IPアドレス単位か、APIキー単位か、ユーザー単位か。RFC 6585が数え方を定めていない以上、単位の決め方がそのまま守れる量を決める。NATの内側でIPを共有する利用者がいれば、IP単位では無関係な利用者まで止める。
-
Retry-Afterを返しているか。429だけ返して待つ時間を教えないと、呼び出し側は推測で送り直し、リトライの波が重なる。秒数形式で返すのが無難である。 - 制限器の死に方を決めてあるか。フェイルオープンとフェイルクローズのどちらを選んだか、選んだ理由を残す。選んでいない場合は、障害のときにその場の判断で決まる。
- 分散時の数え方が原子化されているか。確認と登録を分けて送っていないか。RedisのLuaスクリプト、あるいは同等の原子操作にまとめているかを確認する。
- トークンバケットを使っている場合、補充の速さと容量の決め方。容量が大きいほどバーストを許し、補充が速いほど平均が高くなる。どちらも「守りたい量」から逆算する。
- 制限のログとアラート。拒否された回数が急に増えたとき、それが攻撃か、正規の利用者の増加か、クライアントのバグかを切り分ける材料になる。WorkOS事件では検知の仕組みそのものがなかった。
参考資料
- RFC 6585: Additional HTTP Status Codes(第4節 429 Too Many Requests)
- Rate Limiting Strategies With Redis(固定窓・スライディング窓・トークンバケットのRedis実装例)
- Redis Rate Limiting for APIs: Sliding Window Without the Pain(Luaスクリプトによる原子化、メンバーの一意性)
- Rate Limit Visualization | Fixed and Sliding Windows(固定窓の2倍バーストとスライディング窓の動きの可視化)
- AIエージェントが5日間気づかれず顧客情報を抜いた――WorkOS事件の4つの弱点(レート制限がなかった場合の事例)
- Two SumはcontainsKeyを先に書く――putが先だと自分とペアになる(確認と登録の間の競合)
- 決済履歴の重複排除と集計をJavaでO(n)で解く――FAILEDも「出現した」として記録する順序(リトライ時の重複処理の考え方)