1 IP に 1 秒 2 手。容量 2 の token bucket を、時計ごと自前で書いた
Two moves per second per IP: a capacity-2 token bucket, clock and all, written ourselves
D16-3-T31-token-bucket-rate-limit・技術・日本語入力でプレイする仕組み
ブラウザ版のサーバは、同じ IP から 1 秒に 2 手までしか受けません。
今日、同時に 10 本送ると 2 本だけが通り、8 本は 429 で返りました。仕組みは 20 行ほどの token bucket で、時計に Date.now() を使って一度踏んだ話もあります。
昨夜の T30 で書いたとおり、サーバは状態を持たず、1 手ごとに判定の C++（adv-sim serve）へ 1 行を渡します。
serve は 1 本で、要求を 1 つずつ順に処理します。誰かが速く送り続ければ、ほかの人の手が待たされます。
その入口に置いている絞りの話です。
この回の位置と、前後の回#
区切り: T30〜T33 配る仕組み（4 回のうち 2 回目）
先に読むとよい回: T30（状態を持たないサーバ）
次に読む回: T32（静的ファイルの出し方）
名前 — token bucket#
- 正式名
- token bucket（トークンバケット）
- 近い名前
- leaky bucket（リーキーバケット）・rate limiting（レート制限）・load shedding（過負荷のときに要求を捨てる）
初出:
token bucket そのものの初出は、確かめられませんでした。
leaky bucket は Jonathan S. Turner が最初に書いたとされ、論文は "New directions in communications (or which way to the information age?)"（IEEE Communications Magazine, 1986）として引かれています（二次資料で確かめ、本文は読んでいません）。
token bucket の二つの値は、IETF の RFC 2215（Shenker & Wroclawski, 1997）が token rate [r] と bucket depth [b] として定義しています。
一般の解説 — token bucket#
token bucket（トークンバケット）とは、一定の割合で桶にたまる札（token）を要求ごとに取り、取れた要求だけを通すレート制限の方式です。
桶に、毎秒 r 個の割合で札（token）がたまります。桶には b 個までしか入らず、あふれた札は捨てます。
要求が来たら札を 1 個（大きさのある要求なら大きさの分）取り、取れたら通す、取れなければ通さない。
これだけです。
ここから、どの長さ T の区間をとっても、通る要求の数は b + rT を超えない、が言えます。
長く見れば平均は毎秒 r に抑えられ、短い区間では b 個までのまとまり（burst）を許す。この二つの値で振る舞いが決まるのが特徴です。
名前の似た leaky bucket には、二つの読み方があります。
- 計数器として使う leaky bucket: 要求が来るたびに水位を上げ、水位は一定の速さで下がる。上限を超えたら通さない。これは token bucket を裏返したもので、同じ値を与えれば同じ要求を通し、同じ要求を落とします
- 待ち行列として使う leaky bucket: 要求をいったん行列に入れ、一定の速さで出す。こちらは落とすのではなく遅らせる（shaping）
ネットワークの世界では、守らない要求を落とすか印を付ける使い方を policing、待たせて形を整える使い方を shaping と呼び分けます。Web の API のレート制限は、多くが policing の使い方です。
ほかの方式も並べておきます。
- fixed window counter: 1 秒ごとの枠で数える。枠の境目の前後で 2 倍まで通る
- sliding window log: 要求の時刻を全部覚えて、直近 1 秒を数える。正確だが覚える量が多い
- sliding window counter: 二つの枠を重みで混ぜる近似
よく知られた弱点は、方式よりも「何で数えるか」の側にあります。
IP で数えると、学校や会社や携帯の回線のように、多くの人が 1 つの IP を共有する所で、関係ない人どうしが同じ桶を分けることになります。
逆に、要求の発信元を偽れるなら、桶ごと逃げられます。
複数のサーバに分けると、桶をどこに置くか（Redis など）が問題になります。
うちの実装 — token bucket#
上限は server.mjs の LIMITS の 1 か所で決めています。
perIpPerSec: 2, // 1 IP あたり 1 秒 2 手（token bucket。容量も 2）
queue: 32, // adv-sim に書いて返事待ちの要求数。超えたら 429
simReplyMs: 30_000, // adv-sim が 1 手にこれ以上かかったら死んだとみなす（実測は 12〜17 ms）
桶はこれだけです（server.mjs の RateLimit をそのまま写す）。
class RateLimit {
constructor(perSec) { this.perSec = perSec; this.cap = perSec; this.buckets = new Map(); }
take(ip) {
const now = performance.now();
let b = this.buckets.get(ip);
if (!b) { b = { tokens: this.cap, at: now }; this.buckets.set(ip, b); }
b.tokens = Math.min(this.cap, b.tokens + ((now - b.at) / 1000) * this.perSec);
b.at = now;
if (b.tokens < 1) return false;
b.tokens -= 1;
return true;
}
prune() { // 満タンに戻った IP は忘れる（メモリを増やさない）
const now = performance.now();
for (const [ip, b] of this.buckets) if (now - b.at > (this.cap / this.perSec) * 1000 + 1000) this.buckets.delete(ip);
}
}
要点を順に。
- タイマーで札を足さない。要求が来たときに、前回からの経過時間 × 毎秒 2 だけ足す（遅延評価の補充）。IP が何人いても、時計の割り込みは要らない
- 札は小数で持つ。0.4 秒あけば 0.8 個たまり、次の要求では足りない
- 初めての IP は満タン（2 個）から始める
- prune は 60 秒ごとに呼び、最後の要求から 2 秒（満タンに戻る 1 秒 ＋ 余裕 1 秒）過ぎた IP を消す。満タンの桶は、消して新しく作り直すのと同じなので、忘れても振る舞いは変わらない
IP は、Caddy が付ける X-Forwarded-For の先頭を使い、無ければソケットの相手です。
function clientIp(req) {
const xff = req.headers['x-forwarded-for']; // Caddy の reverse_proxy が付ける。直接来たら無い
if (typeof xff === 'string' && xff.length > 0) return xff.split(',')[0].trim();
return req.socket.remoteAddress ?? '';
}
server.mjs は 127.0.0.1 でしか待たないので、外から直接は来ません。
どこで桶を見るかも決めてあります。
- 本文を読む（64 KB を超えたら 413）
- 形を検査する（壊れた JSON・知らない kind・200 字を超える入力は 400）
- 桶から札を取る。取れなければ 429
- adv-sim が死んでいれば 503
- 返事待ちが 32 以上なら 429
形の悪い要求は札を減らしません。画面の静的ファイルと /api/health は GET なので、桶を通りません。「はじめる」の /api/new は 1 手として数えます。
429 の返事には retry-after: 1 を付けます。
if (!rate.take(clientIp(req))) return send(res, 429, { ok: false, error: `rate limit: ${LIMITS.perIpPerSec} turns/sec per IP` }, { ...cors, 'retry-after': '1' });
5 の返事待ちの上限は、IP ごとではなく全体の数です。IP ごとの桶で 1 人が占めるのを止め、全体の上限で serve の行列が伸び続けるのを止める。二つは別の物で、後者は load shedding（溢れたら捨てる）です。
ブラウザの画面は、429 を受けたら応答の欄に「（少し待ってからもう一度）」と 1 手ぶん出し、進行は直前のままにします。自動ではやり直しません。
AI のプレイヤー役をサーバ経由で回す CLI のラッパは、1 秒 2 手の内側で送り、429 なら待ってから送り直します。
Date.now() で踏んだこと#
最初は時計に Date.now() を使っていました。
9 月 13 日に WSL で 6 人ぶんの模擬プレイを 60 分流したところ、6 人同時に 429 が約 30 秒ごとに出ました。
WSL2 の時刻補正で壁時計が後ろへ飛ぶと、now − at が負になり、全員の札が一度に減っていたのです。
単調な時計の performance.now() に替えて計測し直し、それ以降は出ていません。VPS でも、NTP が時刻を一気に合わせれば同じことが起きえます。
経過時間を測るのに壁時計を使わない、はよく知られた注意ですが、桶の補充の式は経過時間しか見ないので、まさにそこに当たりました。
実測（今日・Windows の手元）#
手元で server.mjs を立て、同じ IP から「何も起きない手」（look）を送りました。
同時に 10 本。
200, 200, 429, 429, 429, 429, 429, 429, 429, 429
retry-after: 1
満タンの 2 個だけが通りました。
1.2 秒あけて桶を満たしてから、100 ms おきに 5 秒間（46 本）。
0 ms:200 110:200 219:429 329:429 437:429 547:200 655:429
765:429 874:429 982:429 1090:200 1200:429 …
200 が 11 本・429 が 35 本
頭の 2 本が満タンの分で、あとは 0.5 秒に 1 本ずつ通っています。式の上限は 2 + 2 × 5 = 12 で、通ったのは 11 でした。
5 秒目の端で札がちょうど 1 個に届かなかった分の差です。
人が入力して送る速さでは、まず当たりません。当たるのは、場所の一覧を続けて押したときや、道具で流したときです。
名前どおりでない所 — token bucket#
token bucket そのものは、名前どおりです。容量 b = 2、補充 r = 2/秒、1 要求で 1 個。
違うのは使い方で、三つあります。
一つ目、手の重さを見ていません。移動は 1〜4 ms、日本語の発話は埋め込みの推論で 20〜40 ms かかりますが、どちらも札 1 個です。重さで札の数を変える（cost-based）ことはしていません。
二つ目、policing だけで shaping はしません。超えた要求は待たせずに 429 で返します。サーバの中に IP ごとの行列は持ちません。
三つ目、数える単位は IP です。人でも、ブラウザでもありません。ブラウザが作る browserId はありますが、送る側が自由に作れる値なので、絞りの鍵には使いません。
弱点と、採らなかった案 — token bucket#
- 共有の IP。学校や会社から何人かが同時に遊ぶと、1 秒 2 手を分け合います。いまの遊ばれ方では困っていませんが、増えれば当たります
- X-Forwarded-For の先頭をそのまま信じています。先頭は、本来は送ってきた側が自由に書ける欄です。Caddy は 2.5 から、信頼した中継から来たのでない X-Forwarded-* を引き継がない、とされていて、それに頼っています（本番の Caddy の版と実際の届き方は、ここでは確かめていません）
- 桶は server.mjs のメモリにあるので、サーバを立て直すと全員が満タンに戻ります。サーバを 2 台にすると、桶も 2 つになります。いまは 1 台なので困りません
- 返事待ちの上限 32 は全体の数なので、たくさんの IP から少しずつ来ると、正しい人も 429 を受けます。そこまで来たら、1 本の serve では足りないということです
採らなかった案:
- Caddy 側のレート制限や WAF を入れる。上限を 2 か所に持つと、どちらで落ちたかが分からなくなる。上限は server.mjs の LIMITS の 1 か所と決めた
- fixed window。実装は同じくらい短いが、枠の境目で 1 秒に 4 手が通る
- 桶を Redis に置く。サーバが 1 台のうちは、外の部品を増やすだけ
- 429 の代わりに待たせる（shaping）。待たせている間も接続と返事待ちの枠を使うので、混んだときほど悪くなる
検索語#
token bucket algorithm
leaky bucket as a meter
rate limiting sliding window vs token bucket
monotonic clock performance.now
速く送らなければ、桶のことは忘れていられます。『霧走町 流氷に眠る』の第一章はブラウザで無料で遊べます。プロフィールのリンクから。