Featured image of post コードテイマー【Token Bucket】窓が改まる刹那、汲み手は源を二度干す〜窓で区切らず、雫の溜まる速さで流量を律する〜

コードテイマー【Token Bucket】窓が改まる刹那、汲み手は源を二度干す〜窓で区切らず、雫の溜まる速さで流量を律する〜

配水技師は源が涸れるたび善意で「一刻あたりの汲み上限」を設けた。どの刻も帳簿はきっちり上限で止まる。一度も超えていない。なのに街は渇く——決まって、刻の変わり目に。固定窓は窓ごとにカウンタを0へ戻す。その「0に戻す」一瞬が前の刻をまるごと忘れさせ、継ぎ目をまたいだ手は忘れられた帳簿で二度、上限まで汲む。上限の2倍が源を干す。窓で刻むのをやめ経過ぶん雫を連続で溜める器(Token Bucket)に差し替えれば、継ぎ目そのものが消える。境界バーストを注入時計の模擬戦で決定的に再現し、同時数(門番)とは別の物差し=時間あたり流量を律するTypeScriptの契約の物語。

渇いた街

街の蛇口が、また一斉に黙った。

私は配水の帳簿を抱えたまま、共同水源の前に立っていた。石組みの井戸から街じゅうの家と工房へ、魔力の水を分けるのが私の仕事だ。その水位が、いま見る間に落ちていく。台所の蛇口も、鍛冶場の冷却樋も、街灯の魔力線も、源が干上がれば一斉に止まる。止まった蛇口の数だけ、誰かの一日が止まる。

「また、刻の変わり目だった」

つぶやいて、私は井戸の縁に目をやった。そこには先客がいた。汲み口の脇に刻まれた時の目盛り——私が引いた「ひと刻み」の区切り——を、指の腹でなぞっていた。私の帳簿には、目もくれずに。噂は聞いていた。錬金術ギルドの、二つの釜が見つめ合って固まる呪いを解いた魔物使いがいる、と。あの釜も、この井戸から水を引いていた。だから水を分けるこの井戸のことなら、あの人に頼め、とギルドの釜守が言った。それがカイナだった。

「源が涸れるたび、私は手を打ってきました」と私は言った。打つ手は、もう尽きていた。「汲みすぎる者がいる。源が一気に落ちて、街が断水する。だから、汲める数に上限を設けたんです」

カイナは目盛りから顔を上げなかった。「上限を、どう数えた」

「ひと刻みごとに、です」

上限は、ずっと守られていた

私は帳簿を開いて見せた。誇るためではない。むしろ、わけが分からなくて、誰かに確かめてほしかった。

「ひと刻みの間、誰が何杯汲んだかを数えます。上限に達したら、その刻はもう汲ませない。刻が変われば、数を0に戻して、また一から数える。——見てください。どの刻も、きっちり上限で止まっている。一度も、超えていないんです」

帳簿の升目は、どの刻も同じ数で打ち止めになっていた。五、五、五。約束した上限ちょうどで、一つの例外もなく止まっている。

「公平にしたかった」と私は続けた。「誰も、ひと刻みに上限より多くは汲めない。富める者も、貧しい者も、同じ上限の下で並ぶ。私は、責任を果たしたつもりでした。なのに——なぜ、街はまだ渇くんでしょう。私の数えは、間違っていないはずなんです」

カイナはようやく帳簿から目を上げ、汲み口の目盛りに指を置いた。

「お前の数えは、間違っていない。どの刻も、上限ちょうどで止まっている。——だが、止めているのは『ひと刻みの中』だけだ。刻と刻の、継ぎ目を、お前は見ていない」

「継ぎ目?」私には意味が掴めなかった。「一刻ごとに、正しく数え直しているだけです」

「その『数え直し』が、どこで起きる」

ひと刻みを、数える術式

私は配水術式を写した板を取り出した。難しいことはしていない。だからこそ、穴があるとは思えなかった。

ひとつ言葉を補っておく。ここでいう「窓」とは、一定の刻ごとに区切った時間の区画のことだ。その区画の中で汲んだ数を数え、上限に達したら打ち切り、区画が変われば数を0に戻して数え直す——これが固定窓カウンタ(Fixed Window)、レート制限のいちばん素朴な数え方だ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 番人の共通の作法:今が何刻か(now)を渡し、汲めたか否かを返す。
export interface Limiter {
  tryAcquire(now: number): boolean;
}

// 固定窓カウンタ。窓(windowMs)ごとにカウンタを0へ戻し、窓内の汲みを limit 回まで許す。
// これは「正しく動く」固定窓だ——窓の中では決して上限を超えない。
export class FixedWindowLimiter implements Limiter {
  private windowMs: number;
  private limit: number;
  private windowStart: number; // 今の窓の開始時刻(windowMs 区切りに整列)
  private count: number;       // 今の窓で汲んだ数

  constructor(windowMs: number, limit: number) {
    this.windowMs = windowMs;
    this.limit = limit;
    this.windowStart = 0;
    this.count = 0;
  }

  tryAcquire(now: number): boolean {
    const window = Math.floor(now / this.windowMs) * this.windowMs; // 今いる窓の開始時刻
    if (window !== this.windowStart) {
      this.windowStart = window; // 窓が改まった:カウンタを0へ戻す(前の窓のことは忘れる)
      this.count = 0;
    }
    if (this.count < this.limit) {
      this.count++; // 窓内に空きあり:汲ませる
      return true;
    }
    return false; // 窓の上限に達した:捨てる
  }
}

カイナは術式を最後まで目で追って、低く言った。

「数え方に、嘘はない。ひと刻みの中では、確かに上限を超えない。——だが、ここだ」

指の先が、window !== this.windowStart の行を、それから this.count = 0 の行を、順になぞった。

「『刻が変われば0に戻す』。その『0に戻す』一瞬に、お前は前の刻のことを、まるごと忘れる。継ぎ目の前で上限まで汲んだ手が、継ぎ目を跨いだ次の瞬間、忘れられた帳簿で、もう一度、上限まで汲める」

「……まさか」と私は言った。「ひと刻みの上限は、守られているのに」

窓の中は、完璧だった。何度数え直しても、上限を超えていない。なのにカイナは、私が一度も見ていない場所——刻と刻の、継ぎ目を指している。そんなところに、街を渇かす穴があるというのか。

継ぎ目で、二度汲ませる

「渇きは、刻と刻の継ぎ目に隠れている」とカイナは言った。「その継ぎ目を、こちらで狙って踏みにいく」

刻を、手で進める

カイナがまず組んだのは、時を握る仕掛けだった。

「この術式に渡す『今、何刻か』を、こちらが手で決める。汲み口を叩くたびに、何刻のことかを指で示す。実際には一瞬も待たない。刻の目盛りだけを、こちらで進める」

これは大事なところだった。配水術式の tryAcquire(now) は、いつ汲まれたかを外から受け取る。だから模擬戦では、現の時計を使わず、こちらが決めた論理上の刻をそのまま渡せばいい。Date.now のような実時間を一切持ち込まないから、実時間はゼロ、しかも同じ叩き方をすれば毎回きっかり同じ結果になる。まぐれで通ることも、まぐれで落ちることもない。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// limiter を時刻列 times で叩き、各時刻で汲めたか(true/false)を記録する。
// now は注入時計=こちらが渡す明示の論理時刻(実時間は一切待たない)。
export function drive(limiter: Limiter, times: number[]): boolean[] {
  return times.map((t) => limiter.tryAcquire(t));
}

// 「汲めた時刻」を幅 span のローリング窓に通し、同じ窓に入った最大数(=流量のてっぺん)を返す。
export function peakInSpan(passTimes: number[], span: number): number {
  let peak = 0;
  for (const start of passTimes) {
    let count = 0;
    for (const t of passTimes) {
      if (t >= start && t < start + span) count++;
    }
    if (count > peak) peak = count;
  }
  return peak;
}

「測るのは、同時に井戸端にいる数じゃない」とカイナは言った。そして、自分の過去の仕事を引いた。「前に、別の山で、狭い通路に一度に通す数を絞る門番を立てたことがある。あれが測ったのは『今、何人が手をかけているか』——同時の数、いわば空間だ。だが、ここで源を涸らすのは、それじゃない。『ある一続きの刻の間に、何杯通ったか』——流量だ」

peakInSpan が数えるのは、まさにそれだった。汲めた刻を並べ、それぞれの刻を起点に幅 span の窓を張って、その窓に何杯が収まるかを見て、いちばん混む窓の数を拾う。起点を「汲めた刻」に限ってよいのは——いちばん混む一続きの刻は、必ずどれかの汲めた刻から始まるからだ。誰も汲んでいない位置から窓を張り直しても、混み具合が増すことはない。だから取り逃しはない。総当たりで二度舐めるが、これは模擬戦の事後に流量を測る物差しで、本番の汲みが通る経路ではない。手間は問わない。

同じ「てっぺん」でも、門番が見ていた同時占有とは、測り方からして違う。門番は、手をかけている間ずっと一を数える——占有は、続く時間を持つ。この器は、汲んだ刹那に一を数えるだけ——汲みは、時間の上の点だ。だから一方は重なりの本数(空間)を、もう一方は一続きの刻に落ちた点の数(時間)を測る。私の問題は、同時に何人が汲んでいるかではなかった。一続きの刻に、何杯が通り抜けたか、だった。

窓の中は、正しい

カイナは、まず私の正しさを確かめてみせた。窓をひと刻み(10刻)、上限を5として、同じ刻に六回叩く。

1
2
3
4
5
6
7
8
import { describe, it } from "node:test";
import assert from "node:assert/strict";

it("窓の中では limit までしか通さない(正しく動く固定窓)", () => {
  const limiter = new FixedWindowLimiter(10, 5); // 窓=10刻、上限5
  const results = drive(limiter, [0, 0, 0, 0, 0, 0]); // 同じ刻に6回叩く
  assert.deepEqual(results, [true, true, true, true, true, false]); // 5通り、6杯目は捨てる
});

五杯は通り、六杯目は捨てられた。「ひと刻みの中では、確かに上限で止まる。お前の数えは、正しい」とカイナは言った。私の確信は、ここではまだ崩れていなかった。むしろ、肯定された。

継ぎ目をまたぐと、十になる

それから、カイナは継ぎ目を狙った。

t=9——窓 [0,10) の終わり際——で、五杯。窓の上限ちょうどだから、全部通る。続けて t=10——窓 [10,20) の頭——で、五杯。窓が改まり、カウンタが0に戻る。だから、また五杯、通ってしまう。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
it("窓の継ぎ目で 2×limit が通る(境界バーストは仕様であって不具合でない)", () => {
  const limiter = new FixedWindowLimiter(10, 5);
  // t=9(窓[0,10)の終わり際)で5、t=10(窓[10,20)の頭)で5。継ぎ目をまたいで叩く。
  const times = [9, 9, 9, 9, 9, 10, 10, 10, 10, 10];
  const results = drive(limiter, times);
  assert.equal(results.filter((ok) => ok).length, 10); // 10杯すべて通った

  const passTimes = times.filter((_, i) => results[i]);
  assert.equal(peakInSpan(passTimes, 10), 10); // 一続きの10刻に通った数のてっぺん=10=上限の2倍
});

peakInSpan が返した数は、十だった。

私は、しばらく何も言えなかった。十、という数字と、目の前で水位を落としていく井戸とを、一度だけ見比べた。ひと刻みに五までと決めたのに、継ぎ目をまたぐ一続きの刻には、その二倍が通っていた。守ったはずの上限が——どの刻もきっちり止めた、あの上限が——街を渇かしていた。

その一拍を置いて、私の手は、すぐに術式へ伸びた。落ち込んでいる場合ではなかった。

「窓の中だけを、見ていたから」と私は言った。「『0に戻す』たびに、私は前の刻に汲まれた五杯を、無かったことにしていた。次の窓は、まっさらだと思っていた。——だから継ぎ目で、二度汲ませていたんですね」

継ぎ目をまたいで上限の二倍が通り抜けるこの現象を、境界バーストという。

「固定窓は、安い」とカイナは言った。その声に、けなす響きはなかった。「覚えておくのは『この刻に何杯か』、ただ一つだけ。だから街じゅうで使われている。間違いじゃない。ただ——刻を、ぶつ切りに数える。継ぎ目の向こうを、忘れる。その忘却が、継ぎ目に穴を空ける」

念のために言えば、この模擬戦が映し出したのは、継ぎ目を通り抜ける流量そのものだ。井戸を実際に涸らしてみせたわけではない。「繁忙の継ぎ目でだけ、たまに」起きていた二度汲みを、狙えば必ず起こせる形に固定した。それだけのことだ。

カイナは人差し指の先に魔力を込め、帳簿の上に青白い光の軌跡を描き出した。時間がぶつ切りの窓で区切られ、その継ぎ目で水が二倍汲み出される仕組みが、魔力の図となって浮かび上がる。

Infographic sequence diagram showing Fixed Window rate limiter boundary burst problem where 2x the limit of water is drawn across the boundary of two windows

「この青い境界線を跨ぐとき、前の窓で汲まれた五杯は、なかったことにされる」とカイナは光の図を指した。「忘却という名の裂け目から、二倍の負荷が水源へと滑り落ちるんだ」

切れ目そのものが、穴だった

カイナは涸れかけた井戸の縁を指した。水位が落ちた壁面には、刻の継ぎ目ごとに、水が二段に落ちた痕が残っていた。

「これは、溢れ出す水精だ。一気に汲めば洪水を起こし、堰き止めれば干上がる。悪いのは水精じゃない。汲ませ方——刻をぶつ切りにした窓で数えたことだ」

それから、術式そのものより、ひとつ深いところを衝いた。

「この穴は、術式のどこにも『間違い』として現れない。窓の数えは、型の上でも完璧だ。数は、上限を超えない。穴は、数えの正しさの中にあるんじゃない。『刻を、どう刻むか』という、時間の切り方そのものにある。何杯までか、は前もって決められる。だが、刻の継ぎ目を、どう跨ぐか——それは、走らせて、継ぎ目をまたいで、初めて立ち上がる」

上限は、ずっと守られていた。守られたまま、街は渇いた。穴は、私の数え間違いではなかった。刻を、ぶつ切りにしたこと——その切れ目そのものが、穴だった。

窓をやめ、器に溜める

継ぎ目を、無くす

「窓を、やめる」とカイナは言った。「刻をぶつ切りにして数え直すから、継ぎ目ができる。なら——継ぎ目を、無くす」

カイナは、井戸の脇にひとつの器を据える仕草をした。

「ここに、器を置く。器には、雫が、絶え間なく溜まっていく。決めた速さで、連続して。汲み手は、器に雫がある時だけ、汲める。雫がなければ、汲めない。それだけだ」

容量のある器に、決めた速さで雫——つまりトークン——が連続して溜まり、雫がある時だけ汲める。これがトークンバケット(Token Bucket)、器の比喩そのままの数え方だ。

「なぜ、継ぎ目が消えるんです?」と私は訊いた。

「窓のように『0に戻す』瞬間が、もう無いからだ。雫は、前の刻から地続きに溜まり続ける。継ぎ目で忘れることがないなら、継ぎ目で二度汲む隙も、生まれない」

「でも、器をずっと見張って、雫を一滴ずつ足し続けるんですか。それでは、番人を井戸の前に立たせ続けることに——」

「いや」とカイナは私の言葉を継いだ。「見張らない。汲みに来た、その時にだけ数える。『前に勘定してから今までに、何刻過ぎたか』を測って、その分の雫を、まとめて足す。経過した刻に、溜まる速さを掛ける。——前に勘定してから今まで、誰も汲んでいない間はな。その間に汲みが挟まらなければ、ひと雫ずつ連続で足すのも、経過ぶんをまとめて足すのも、溜まる量は同じだ。それだけで、絶え間なく溜まっていたのと、同じことになる」

汲みに来た時にだけ経過ぶんをまとめて足すこの数え方を、遅延補充(lazy refill)という。番人を巡回路に立たせ続けなくていい。汲まれた瞬間に、経過した刻のぶんを一度だけ勘定する。だから常に一定の手間で済む。

「もう一つ」とカイナは言った。「器には、上限がある。あふれた雫は、こぼれる。長く誰も汲まなくても、器いっぱい——たとえば五杯ぶん——より多くは溜まらない。だから、ためこんだ一気汲みも、器の大きさまで。それを超える殺到は、できない」

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// トークンバケット。容量 capacity の器に、1刻あたり refillPerMs 個の雫が連続で溜まる。
// 汲むたび、まず「前回からの経過 × 速さ」で雫を足し(遅延補充)、足りれば1つ消費する。窓の継ぎ目が無い。
export class TokenBucketLimiter implements Limiter {
  private capacity: number;    // 器の最大容量=バースト許容量(b)
  private refillPerMs: number; // 1刻あたり溜まる雫の数=平均レート(r)
  private tokens: number;      // いま器にある雫
  private lastRefill: number;  // 最後に雫を勘定した時刻

  constructor(capacity: number, refillPerMs: number) {
    this.capacity = capacity;
    this.refillPerMs = refillPerMs;
    this.tokens = capacity; // 満杯から始める(初回のバーストを許す)
    this.lastRefill = 0;
  }

  private refill(now: number): void {
    const elapsed = now - this.lastRefill; // 前回の勘定からの経過
    if (elapsed <= 0) return;
    this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillPerMs); // 連続補充・容量で頭打ち
    this.lastRefill = now;
  }

  tryAcquire(now: number): boolean {
    this.refill(now); // 経過した分だけ雫を足してから
    if (this.tokens >= 1) {
      this.tokens -= 1; // 足りる:汲ませる
      return true;
    }
    return false; // 雫が足りない:捨てる
  }
}

「変えたのは、汲み口の作法じゃない」とカイナは言った。「汲めるかを判じる、時間の数え方だけだ。窓でぶつ切りに数えるのを、経過した刻ぶん雫を足す数え方に、差し替えた。汲み手から見れば——『汲めるか訊いて、雫があれば汲む』——何も変わっていない。渡すのも『今、何刻か』、返るのも『汲めたか否か』。形も、呼び方も、同じだ」

容量で、頭を打たせる

カイナは refill の一行に指を置いた。Math.min(this.capacity, this.tokens + elapsed * this.refillPerMs) の、Math.min のところだ。

「この、容量で頭を打つ一行。これが、ためこみの上限を決める。これを忘れて、ただ『経過 × 速さ』を足すだけにすると、ひと晩遊ばせた器が、一晩ぶんの雫を抱える。朝いちばんに、その一晩ぶんを一気に汲ませる。それでは、窓の継ぎ目を消したつもりが、もっと大きな継ぎ目を、自分で作ることになる」

連続して溜めることと、容量で頭を打つこと。この二つが揃って、初めて流量が律される。片方だけでは足りない。器に底が無ければ、いくらでも溜まってしまう。

もう一度、同じ叩き方で

カイナは、さっきと寸分同じ叩き方を、今度は器に通した。t=9 で五杯、t=10 で五杯。継ぎ目をまたぐ、あの叩き方だ。固定窓と公平に比べるため、レートは揃えた。上限五杯を窓十刻で許すのと同じ平均になるよう、容量を五、補充を一刻あたり0.5杯とした。

補充の速さに、0.5という割り切れる値を選んだのには、わけがあった。「注入時計が消すのは、実時間と、汲みの届く順番のゆらぎだ」とカイナは言った。「だが、雫の量は小数になる。割り切れない速さだと、雫が一杯のすぐ手前——0.9999……のような値で止まって、汲めるか否かが、丸めの按配で揺れることがある。それは注入時計とは別の話だ。だからここでは、勘定に丸めの揺れが出ない速さを選んだ。本物の現場では、この丸めにも気を配る——雫を整数で数える、といった工夫がいる」

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
it("窓の継ぎ目でも 2×limit は通らない(バーストは capacity で頭打ち)", () => {
  // 固定窓(窓10・上限5)と同じ平均レート:容量5、1刻あたり 0.5 杯ずつ補充
  const limiter = new TokenBucketLimiter(5, 0.5);
  const times = [9, 9, 9, 9, 9, 10, 10, 10, 10, 10]; // 継ぎ目の叩き方は固定窓と寸分同じ
  const results = drive(limiter, times);

  // t=9 で満杯の5杯を汲み切り、t=10 の経過1刻で溜まる雫は 0.5<1 → t=10 は全部こぼれる
  assert.equal(results.filter((ok) => ok).length, 5);

  const passTimes = times.filter((_, i) => results[i]);
  assert.equal(peakInSpan(passTimes, 10), 5); // てっぺん=5=容量。固定窓の10と対照
});

t=9 で、満杯の五杯を汲み切る。器は空になる。t=10 までに経過したのは、一刻。溜まった雫は0.5杯——一杯に満たない。だから t=10 の五杯は、全部こぼれた。

peakInSpan が返したのは、五。固定窓が継ぎ目で通した十に対して、器は五で止めた。

「これは運じゃない」とカイナは言った。「窓のように0に戻す瞬間が無いから、継ぎ目の向こうに、忘れられた空の帳簿が現れない。継ぎ目で二度汲む隙そのものが、消える。——断っておく。この器が約束するのは『どんな一続きの刻も、必ず五杯までに収まる』ことじゃない。地続きに汲み続ければ、五杯を汲み切った後も、溜まる速さのぶんは流れていく。器が消したのは、継ぎ目の不連続——『0に戻して前を忘れる』、あの一瞬の二度汲みだ。瞬間に汲めるのは、いつでも器の大きさ、五杯まで。境界に、段差が無い」

そして、同じ叩き方だったことを念押しした。

「同じ刻に、同じ数を叩いた。違うのは、器の中の数え方だけだ。固定窓は継ぎ目で十を通し、この器は五で止めた。測ったのは『一続きの刻に何杯通ったか』——流量のてっぺんだ。門番が測った『同時に何人いるか』とは、別の物差し。お前たちはこのひと続きの旅で、源を二つの軸で締めることを学んだことになる。同時に幾つか——門番。そして、一刻に幾つか——この器だ」

カイナは再び魔力の光を走らせ、今度は井戸の脇に置かれた「トークンの器」の動きを空間に描き出した。時間の経過とともに雫が連続して滴り、継ぎ目そのものが融けて消えていく光景がそこに浮かび上がった。

Infographic showing Token Bucket rate limiter preventing boundary bursts using lazy refill calculation and capacity capping

「器の雫は、時間という見えない源泉から少しずつ、しかし確実に滴り落ちる」カイナは光を散らしながら言った。「だから、一瞬の隙を突いて二度汲むことはできない。時間が,自ずと流量を律するんだ」

律速と、容量と、こぼれ

「あと三つ、確かめておく」とカイナは言った。器の振る舞いの、肝だ。

一つ。汲み切った後、次の一杯が汲めるまで、どれだけかかるか。溜まる速さが一刻あたり0.5杯なら、一杯溜まるのに二刻。汲み切ってしまえば、次の一杯は二刻待たなければ汲めない。

1
2
3
4
5
6
it("汲み切った後は、補充速度が次の一杯までの間合いを決める(律速)", () => {
  const limiter = new TokenBucketLimiter(5, 0.5); // 1杯溜まるのに 1/0.5=2刻
  drive(limiter, [0, 0, 0, 0, 0]); // t=0 で満杯の5杯を汲み切る→雫0
  assert.equal(limiter.tryAcquire(1), false); // 1刻後:溜まった雫は0.5<1→まだ汲めない
  assert.equal(limiter.tryAcquire(2), true);  // 2刻後:雫がちょうど1→汲める
});

「速さが、そのまま、長い目で見た汲める量を決める」とカイナは言った。器の大きさは、一気汲みの上限。溜まる速さは、長く均した流量。二つは別の役目を持っている。

二つ。長く誰も汲まなかったら、器はどうなるか。容量で頭を打つから、いくら遊んでいても、五杯より多くは溜まらない。

1
2
3
4
5
6
7
it("遅延補充は容量で頭打ち(長い遊休でも溢れない)", () => {
  const limiter = new TokenBucketLimiter(5, 0.5);
  drive(limiter, [0, 0, 0, 0, 0]); // t=0 で汲み切る
  const longIdle = drive(limiter, Array(6).fill(10000)); // 遥か後(10000刻)にまとめて6回
  // 経過10000刻ぶん(5000杯相当)溜められても、器は容量5止まり→5通って6杯目は捨てる
  assert.deepEqual(longIdle, [true, true, true, true, true, false]);
});

一万刻も放っておけば、計算上は五千杯ぶんの雫が溜まる勘定だ。だが器は五杯で頭を打つ。あの Math.min が効いている。六杯目は、こぼれた。

三つ。雫が無いとき、どう断るか。例外を投げて暴れるのではない。静かに「汲めない」と返すだけだ。

1
2
3
4
5
it("雫が無ければ捨てる(例外でなく false を返す)", () => {
  const limiter = new TokenBucketLimiter(5, 0.5);
  drive(limiter, [0, 0, 0, 0, 0]); // 汲み切る
  assert.equal(limiter.tryAcquire(0), false); // 例外を投げず、静かに false
});

「雫が無いとき断るのは、静かにだ」とカイナは言った。「叫びも、暴れもしない。汲み手は、雫が戻るまで、また来ればいい」

器が、約束しないこと

「これで、もう源は涸れませんか」と私は訊いた。

私の問いに、カイナはすぐの答えを返さなかった。器の縁に溜まりはじめた雫を、指の先で一つ、受ける。それからゆっくり、器が約束できるものと、できないものを分けた。

約束できること。この器を通る限り、一続きの刻に通る流量は、器の容量と溜まる速さで決まる範囲を超えない。継ぎ目の二度汲みは、構造から消える。

約束できないこと。

「一つ。ここでは、雫が無ければ捨てた。だが『雫が溜まるまで待たせる』という契約もある。それは汲み手を行列で待たせる別の作法で、待つ間に気が変わったらどう抜けるか、誰を先に通すか——別の難所が要る。今日の器は、静かに捨てる、いちばん素直な形だ」

「二つ。継ぎ目を消すやり方は、これ一つじゃない。窓を一つに区切らず、連続でずらしながら数える別の器——スライディングウィンドウ——もある。この水瓶の取り柄は、一気汲みの上限を、器の大きさで、はっきり決められることだ。唯一の正解、というわけじゃない」

「三つ」とカイナは街の方を見た。「この器は、ひとつの配水所のものだ。街に配水所が幾つもあって、それぞれが自分の器を持てば、器同士は互いの汲みを知らない。皆の汲みを一つに合わせて数えるには、器の中身を分かち合う別の契約が要る。それは——状態をどう揃えるか、という、また別の獣の話だ」

そして、最後に静かに付け加えた。

「同時に幾つ。にらみ合いの解き方。そして、一刻に幾つ。源を守る、三つの締めが、これで揃った」

流れを、確かめる

固定窓と器、両方の模擬戦を、まとめて走らせた。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
$ node --test
▶ After: トークンバケット(連続補充・遅延補充)
  ✔ 窓の継ぎ目でも 2×limit は通らない(バーストは capacity で頭打ち)
  ✔ 汲み切った後は、補充速度が次の一杯までの間合いを決める(律速)
  ✔ 遅延補充は容量で頭打ち(長い遊休でも溢れない)
  ✔ 雫が無ければ捨てる(例外でなく false を返す)
▶ Before: 固定窓カウンタ(窓ごとリセット)
  ✔ 窓の中では limit までしか通さない(正しく動く固定窓)
  ✔ 窓の継ぎ目で 2×limit が通る(境界バーストは仕様であって不具合でない)
ℹ tests 6
ℹ pass 6
ℹ fail 0

六本、すべて緑。固定窓は窓の中では正しく止まり、継ぎ目では二倍を通した。器は、同じ叩き方でも継ぎ目で二倍を通さず、汲み切ったあとは速さに律され、長く遊んでも容量で頭を打ち、雫が無ければ静かに捨てた。

街に、水が戻る

私は、器を源の汲み口に据えた。雫が、絶え間なく溜まりはじめる。

沈黙していた街じゅうの蛇口に、水が戻っていった。一気に噴き出しはしない。だが、涸らされることもない。台所の蛇口にも、鍛冶場の冷却樋にも、街灯の魔力線にも、一定の速さで、水が回りはじめる。誰かが継ぎ目で二度汲んで、街ごと干上がらせることは、もう無い。

「私は、上限を守ることばかり数えていました」と私は言った。「でも、街が要っていたのは——一刻に汲める量が、継ぎ目でも裏切られないこと。器の大きさと、雫の溜まる速さ。私が決めるべきだったのは、その二つだったんですね」

カイナは、器に溜まりゆく雫から目を離さず、言った。

「汲める速さは、お前が上限と呼んで数えるものじゃない。雫が溜まる速さが、決める。器は、時間に、汲ませてもらうんだ」

私は帳簿を閉じた。升目に並んだ「五、五、五」は、もう答えではなかった。源に溜まりはじめた雫を、しばらく見つめた。街に、水が戻っていく音がする。蛇口の一つひとつが、また誰かの一日を、動かしはじめていた。


📜 カイナの魔獣契約録(Tamer’s Registry)

  • 魔獣名(クラス/パターン名): アクア・トークン(溢れ出す水精)/ レート超過の暴走(Token Bucket=連続補充で流量を律する/Fixed Window=離散リセットが招く境界バースト)
  • 危険度(難易度/バグの影響度): ★★★★☆(窓の中では完璧に上限を守る。継ぎ目をまたぐ一続きの刻にだけ、上限の2倍の流量が通って共有源を涸らす。データは壊れない=可用性・公平性の障害)
  • 主な生態(アンチパターンの特徴):
    • 固定窓カウンタは窓内では決して上限を超えない(正しく動く)。だが窓ごとにカウンタを0へリセット=前窓を忘れるため、継ぎ目をまたぐローリング窓には 2×limit(前窓の終わり際の limit + 次窓の頭の limit)が通る(境界バースト=固定窓の仕様であって不具合ではない)
    • 源を涸らすのは「同時に何人が汲んでいるか(並行数)」でなく「一続きの刻に何杯通ったか(時間あたり流量)」。前回の門番(同時占有=空間)とは測る軸が違う(空間 vs 時間)
    • 平時・窓の真ん中では露見せず、継ぎ目に汲みが集中した刻だけ源を涸らす(再現しづらい)
  • 契約のポイント(設計の要点):
    • Token Bucket=容量 capacity の器に毎刻 refillPerMs の雫が連続で溜まる。汲むたび遅延補充(tokens = min(capacity, tokens + elapsed * refillPerMs))してから1つ消費。窓の「0リセット」が無く継ぎ目が消える=境界バーストの不連続を構造から排除。capacity がバースト上限、refillPerMs が長期平均レートを律する。番人を巡回路に立たせ続けず、汲みに来た刻だけ経過ぶんを勘定する一定手間(O(1))
    • 1:1:同一インタフェース tryAcquire(now): boolean・同一の平均レートを保ち、差分は時間の数え方(窓の離散リセット → 経過差分の連続補充)のみ。汲み口の作法は不変
    • 容量の頭打ち(Math.min)を忘れると、長い遊休で雫が溜まりすぎ、結局もっと大きな一気汲みを許す。連続補充と容量頭打ちの二つが揃って初めて流量が律される
  • 契約外事項(保証しないこと):
    • 「雫が無ければ捨てる(shed)」のみ実装。「溜まるまで待たせる(queue/wait)」は待ち行列・待機中の離脱・公平順という別の難所=待ち変種は契約外
    • 継ぎ目を消す別解にスライディングウィンドウ。バースト上限を capacity で明示に決められるのがトークンバケットの取り柄(唯一解ではない)
    • ひとつの器は一配水所のローカル状態。複数配水所が各自の器を持つと互いの汲みを知らない=分散レート制限は状態整合の領分(別の獣・後日)
    • 源全体を丸ごと律する最小形。家・工房ごとに別の上限を課すなら、汲み手を見分ける識別の鍵が要る
    • 満杯から始める設計=起動直後は容量ぶんの初回バーストを意図して許す(tokens = capacity)。立ち上がりから流量を絞りたいなら、空の器(tokens = 0)で始めて溜まるのを待たせる
  • 現在のステータス: 🟢 窓の継ぎ目を消し、流量を「容量+速さ」で律する契約成立(境界バーストの不連続を構造から排除)/待たせる変種と、複数配水所の足並みは別の獣として後日。同時の数(門番)・にらみ合いの解き方(鍵の順)・一刻の流量(器)で、源を守る三つの締めが揃った
comments powered by Disqus
Hugo で構築されています。
テーマ StackJimmy によって設計されています。