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?

@sen-ltd

5 つのレートリミットアルゴリズムを同時に動かして比較する PHP サービスを作った

0
Posted at

なぜ作ったか

ほとんどのバックエンドはいずれレートリミットが必要になる。実際にはたいてい最初に見つけたアルゴリズム — だいたい固定ウィンドウ — をそのまま採用して、本番のバーストやクレームで欠点を知ることになる。「アルゴリズムの名前は知っている」と「実際のトラフィックに対してどう振る舞うか分かっている」の間にはかなりの距離がある。

Slim 4 で小さなサービスを作り、教科書に出てくる 5 つのアルゴリズムを同じ設定（10 リクエスト / 10 秒、またはバケット容量 10・1 トークン/秒リフィル）で同時に動かして、異なるエンドポイントに同じ curl ループを打ったときの判定の違いを観察できるようにした。/compare エンドポイントで N リクエストのシミュレーションを全アルゴリズム横並びで実行できる。

🔗 GitHub: https://github.com/sen-ltd/rate-limit-demo

Screenshot

5 つのアルゴリズム

エンドポイント アルゴリズム キーあたりメモリ
/fixed-window 固定ウィンドウカウンタ O(1)
/sliding-window-log タイムスタンプのスライディングログ O(limit)
/sliding-window-counter 2 バケット近似 O(1)
/token-bucket トークンバケット（遅延リフィル） O(1)
/leaky-bucket リーキーバケット O(1)

5 つすべてが同じインターフェースを共有:

interface LimiterInterface
{
    public function name(): string;
    public function check(string $key): Decision;
    public function peek(string $key): Decision;
    public function reset(?string $key = null): void;
    public function storedKeys(): int;
    public function exportState(): array;
    public function importState(array $state): void;
}

check() がミューテーション操作で、$key からのリクエストを許可するか判定し、試行を記録し、Decision を返す。peek() は読み取り専用の /compare 用。

設計: クロックを注入する

レートリミットは本質的に時間の問題。リミッタが microtime(true) を直接呼ぶとテストで実際にスリープが必要になり、遅くて不安定になる。全リミッタに Clock インターフェースを注入:

interface Clock
{
    public function now(): float;
}

テストでは FakeClock を注入して advance() で時間を進める。

固定ウィンドウ — 誰もが最初に選ぶやつ

壁時計を幅 $windowSeconds のウィンドウに分割し、ウィンドウごとにキー別のカウンタを持つ:

public function check(string $key): Decision
{
    $now    = $this->clock->now();
    $bucket = (int) floor($now / $this->windowSeconds);

    $entry = $this->state[$key] ?? ['bucket' => $bucket, 'count' => 0];
    if ($entry['bucket'] !== $bucket) {
        $entry = ['bucket' => $bucket, 'count' => 0];
    }

    $resetAt = (float) (($bucket + 1) * $this->windowSeconds);

    if ($entry['count'] >= $this->limit) {
        $this->state[$key] = $entry;
        return new Decision(false, $this->name(), $this->limit, 0, $resetAt, $entry['count']);
    }

    $entry['count']++;
    $this->state[$key] = $entry;
    return new Decision(true, $this->name(), $this->limit,
                        $this->limit - $entry['count'], $resetAt, $entry['count']);
}

キーあたり整数 1 つ。シンプルで安い。ただし有名な欠陥がある — ウィンドウ境界をまたいだクライアントは 2 × limit のリクエストを数百ミリ秒以内に通せる:

public function testEdgeBurstFlaw20RequestsIn10Seconds(): void
{
    $clock = new FakeClock(1_000_009.5); // 境界の 0.5 秒前
    $fw    = new FixedWindow($clock, 10, 10);

    $allowed = 0;
    for ($i = 0; $i < 10; $i++) {
        if ($fw->check('k')->allowed) $allowed++;
    }
    $clock->advance(0.6);
    for ($i = 0; $i < 10; $i++) {
        if ($fw->check('k')->allowed) $allowed++;
    }

    $this->assertSame(20, $allowed,
        'fixed window allows 20 requests inside a 10s span at the boundary');
}

10 req / 10 s のリミッタが 1.1 秒で 20 リクエスト許可する。バグではなく、固定ウィンドウの仕様通りの動作。

スライディングウィンドウログ — 正確だが高コスト

ウィンドウ境界を捨て、キーごとに直近 $windowSeconds 分のタイムスタンプを保持する:

public function check(string $key): Decision
{
    $now    = $this->clock->now();
    $cutoff = $now - $this->windowSeconds;
    $log    = $this->state[$key] ?? [];

    $drop = 0;
    foreach ($log as $t) {
        if ($t > $cutoff) break;
        $drop++;
    }
    if ($drop > 0) $log = array_slice($log, $drop);

    if (count($log) >= $this->limit) {
        $this->state[$key] = $log;
        return new Decision(false, ...);
    }

    $log[] = $now;
    $this->state[$key] = $log;
    return new Decision(true, ...);
}

任意の時点で過去 windowSeconds に limit 以上のリクエストがないことを保証する。代わりにメモリは O(limit)。limit=10 なら些細だが、高レートのAPIゲートウェイでは問題になる。

スライディングウィンドウカウンタ — Cloudflare の近似式

固定ウィンドウの O(1) メモリと、エッジバースト耐性を両立する近似アルゴリズム。現バケットと前バケットの 2 カウンタで加重平均を取る:

$bucket      = (int) floor($now / $this->windowSeconds);
$bucketStart = (float) ($bucket * $this->windowSeconds);
$elapsed     = $now - $bucketStart;
$weight      = 1.0 - ($elapsed / $this->windowSeconds);

$estimate = (int) floor($entry['prev'] * $weight + $entry['count']);

if ($estimate >= $this->limit) {
    // deny
}

バケットに入って 1% の時点では weight = 0.99、99% の時点では weight = 0.01。前バケットのリクエストが均等分布だと仮定した近似で、実用上は正確な値から数パーセントの誤差。

トークンバケット — 通常の API に最適

容量 $capacity のバケットにトークンが入っている。$refillRate トークン/秒で補充され、リクエストごとに 1 トークン消費。遅延リフィルのトリック — バックグラウンドタイマーは不要で、次に参照するときに経過時間分を計算:

public function check(string $key): Decision
{
    $now   = $this->clock->now();
    $entry = $this->state[$key] ?? ['tokens' => (float) $this->capacity, 'last' => $now];

    $elapsed = $now - $entry['last'];
    if ($elapsed > 0) {
        $entry['tokens'] = min(
            (float) $this->capacity,
            $entry['tokens'] + $elapsed * $this->refillRate,
        );
    }
    $entry['last'] = $now;

    if ($entry['tokens'] >= 1.0) {
        $entry['tokens'] -= 1.0;
        // allowed
    }
    // denied
}

トークンが float なのには理由がある — 0.4 秒間隔のリクエストで 1 token/sec なら 0.4 トークンが貯まる。整数に丸めると持続レートが設定より低くなる。

トークンバケットは「しばらくアイドル → バースト → またアイドル」という人間の API 利用パターンにマッチする。

リーキーバケット — トークンバケットとの違い

一文で言うと: トークンバケットはクレジットカード、リーキーバケットは水道管。アイドル時間はトークンバケットではクレジットとして蓄積されるが、リーキーバケットでは単に水が抜けるだけ。バースト許容力が根本的に異なる。

public function check(string $key): Decision
{
    $now   = $this->clock->now();
    $entry = $this->state[$key] ?? ['size' => 0.0, 'last' => $now];

    $elapsed = $now - $entry['last'];
    if ($elapsed > 0) {
        $entry['size'] = max(0.0, $entry['size'] - $elapsed * $this->leakRate);
    }
    $entry['last'] = $now;

    if ($entry['size'] + 1.0 > (float) $this->capacity) {
        // queue full → deny
    }
    $entry['size'] += 1.0;
    // allow
}

SPA のページロードで 5 リクエストを並列に飛ばすと、トークンバケットなら余裕で通るのにリーキーバケットだと 429 になることがある。

/compare エンドポイントが本体

5 つの実装を読むのと、同じ入力で挙動が違うのを見るのは別物。/compare?n=20&delay=0.1 が N リクエストのシミュレーションを全リミッタ横並びで実行する:

{
  "input": { "key": "0.0.0.0", "n": 15, "delay": 0.1 },
  "results": {
    "fixed_window":           { "allowed": 10, "denied": 5, "sequence": [...] },
    "sliding_window_log":     { "allowed": 10, "denied": 5, "sequence": [...] },
    "sliding_window_counter": { "allowed": 10, "denied": 5, "sequence": [...] },
    "token_bucket":           { "allowed": 11, "denied": 4, "sequence": [...] },
    "leaky_bucket":           { "allowed": 11, "denied": 4, "sequence": [...] }
  }
}

内部では FakeClock で全リミッタが同じ時間軸を見る。リアルスリープなし。HTML ページでは sequence を色付きの矩形で描画して、どのリクエストがどのアルゴリズムに許可/拒否されたかが一目で分かる。

トレードオフ

  • インメモリのみ — シングルプロセス。2 台のアプリサーバがあれば実効レートは設定の 2 倍。本番では Redis が必要
  • IP ベースのみ — ほとんどの本番 API ではユーザー単位や API キー単位が正解
  • エンドポイント別設定なし — 全リミッタが 10 / 10 s 固定
  • スライディングウィンドウカウンタは近似 — 法的拘束力のあるレート制限（課金、コンプライアンス）にはスライディングログを使う

試してみる

git clone https://github.com/sen-ltd/rate-limit-demo
cd rate-limit-demo
docker build -t rate-limit-demo .
docker run --rm -p 8000:8000 rate-limit-demo

# 別シェルで:
for i in $(seq 1 12); do
  curl -sS -o /dev/null -w "%{http_code} " http://localhost:8000/fixed-window
done; echo
# → 200 200 200 200 200 200 200 200 200 200 429 429

curl -sS 'http://localhost:8000/compare?n=15&delay=0.1' | jq '.results | keys'

51 の PHPUnit テスト。全テストがフェイククロック上で動くのでスイート全体が 14 ミリ秒で完了する。

覚えておくべき 1 つ: アルゴリズムの選択基準はクライアントにバーストを許すかどうか。固定ウィンドウは許す。スライディングログとカウンタは許さない。トークンバケットはバケットサイズまで許す。リーキーバケットはまったく許さない。

SEN 合同会社 の 100 超ポートフォリオシリーズ #165。

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
Sign upLogin
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?