0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

「60秒3回」のAPI制限は境界で2倍通る――固定窓のバーストとRedisの数え方

0
Posted at

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事件では検知の仕組みそのものがなかった。

参考資料


0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?