Featured image of post コードテイマー【Semaphore】一斉になだれ込む群れが、宝の通路を圧し潰す〜門番が通すのはN体、溢れは行列で待たせる〜

コードテイマー【Semaphore】一斉になだれ込む群れが、宝の通路を圧し潰す〜門番が通すのはN体、溢れは行列で待たせる〜

採れ高を上げようと、監督官は使い魔を一斉に坑道へ放った。群れは宝の通路を同時に塞ぎ、坑道ごと圧し潰す。鍵は総数でも投入の間隔でもなく、同時に通路を占める数だった。入口に門番を立て、同時に通すのをN体に絞り、溢れた群れは行列で待たせる——同時占有ピークを物差しにした模擬戦で、有界並行こそ最速の持続採掘だと確かめるTypeScriptの契約の物語。

数を、教えて

私が呼んだその女は、潰れた本坑のかたわらに掘った試掘坑の入口で、しゃがみ込んでいた。こちらが名乗るのも待たず、岩肌へ細い鏨のような計器を、黙って挿している。私は採れ高の帳面を、その背中に突きつけた。

「結論だけでいい。使い魔を、いくつにすればいいの。一度に何体まで坑道へ放てば、二度とあれが起きないのか。その数だけ、教えて」

女は——カイナと名乗った——顔も上げずに、計器の角度を直した。

「壊れ方を、先に見る」

「見てる時間が惜しいのよ」私は声を尖らせた。「鉱脈の納期は、待ってくれない。もう三日、坑道を止めてる。止めてるあいだも、損は出続けてるの」

「止まってるなら、ちょうどいい」カイナは平然と言った。「動いてる坑道は、壊し方を見せてくれん」

速さは、放つ数だと思っていた

私は、北の魔力鉱山で採掘の監督をしている。仕事は単純だ。鉱脈の一覧を使い魔に割り振り、坑道の奥へ放つ。一体が一本の脈につき、魔術触媒を掘り出して、運び戻す。何年も、そうやって数字を作ってきた。

先の四半期、ノルマが上がった。私は単純な算術で応えた。使い魔の数を増やせばいい。一度に放つ数を、倍に、また倍に。最初の数週は、面白いように採れ高が伸びた。「速さは、放つ数だ」——私はそう信じて疑わなかった。一度に多く放てば、多く掘れる。当たり前のことに思えた。

崩れたのは、いちばん深い脈だった。いちばん細い通路の、その奥に、いちばん良い触媒が眠っている。繁忙の山場、私はありったけの使い魔を一度に放った。群れは我先に、同じ狭い通路へなだれ込み——通路は、その同時の重みに耐えきれず、魔力を噴いて圧し潰れた。坑道ごと、潰れた。

断っておくと、掘った触媒が化けたわけじゃない。採れた鉱石の中身が壊れたんじゃない。通路そのものが——一度に多くを通そうとした、その通路が——潰れたのだ。

カイナのことは、その落盤を見にきた老いた堀子から聞いた。瓦礫を眺めて、彼はぽつりと言った。「昔、別の山で、同じ潰れ方をした坑があった。群れを御す者が来て、直したよ」。紹介状もない、ただの口伝だ。半信半疑のまま、私はその名を頼った。

私は採掘の術式(コード)を写した巻物を、いくらか得意げに広げてみせた。単純なのが自慢だった。

「ほら、単純でしょう。脈の一覧を渡して、全部いっぺんに放つ。それだけ」

1
2
3
4
5
6
7
8
type Vein = { id: string };                     // 鉱脈(処理すべき1件)
type Ore = { veinId: string; amount: number };  // 採れた鉱石(結果)
type Extract = (vein: Vein) => Promise<Ore>;    // 使い魔の一掘り(非同期I/O:通路=共有資源を占有する)

// Before: 群れを一斉に放つ。通路に何体入るかを誰も見ていない。
async function harvestAll(veins: Vein[], extract: Extract): Promise<Ore[]> {
  return Promise.all(veins.map((vein) => extract(vein))); // map が全件を同期で発火
}

カイナは巻物を端まで目で追って、すぐには名を下さなかった。Promise.all の一行を、指の背で軽く叩いた。

「これは、速いんじゃない。——こらえ性が、ないだけだ」

こらえ性、と私は繰り返した。意味が掴めなかった。速いことの、何が悪いのか。一刻も早く掘り出すのが、私の仕事なのに。

Promise.all が速いのは、知ってる」私は食い下がった。「なのに、なぜ速さが坑道を潰すの。それが分からないから、あなたを呼んだのよ」

カイナは答えず、計器のほうへ戻っていった。

計器を、坑道に挿す

カイナのいう「壊れ方を見る」とは、模擬戦のことだった。坑道を本当に潰すわけにはいかない。潰れる一歩手前の混み具合を、この試掘坑の中に小さく作る仕掛けだ。

肝は、坑道に挿したあの計器だった。「今この瞬間、通路に何体の使い魔が同時に入っているか」を数える。そして、その最高記録——同時にいた数の、てっぺん——を覚えておく。カイナはそれを peak と呼んだ。

「通路を潰すのは、何脈ぶん掘ったかじゃない。今この瞬間、何体が同時に通路を塞いでいるか、だ。だから、それを数える」

使い魔の一掘り(extract)は、外から「いつ掘り終えるか」を握れる作り物に差し替えた。掘り終えの合図を私が握れば、通路に何体を同時に閉じ込めるかを、こちらの手で決められる。カイナはその合図の握りを deferred と呼んだ。外から終わらせ時を握れる約束(Promise)のことだ、と。

 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
34
35
36
// 掘り終えの「合図」を外から握る小道具(Deferred)
function deferred<T>() {
  let resolve!: (value: T) => void;
  let reject!: (reason: unknown) => void;
  const promise = new Promise<T>((res, rej) => { resolve = res; reject = rej; });
  return { promise, resolve, reject };
}

// 坑道に計器を挿した採掘術。入坑で live++/peak 更新、退出で live--。
function makeShaft() {
  let live = 0;          // いま通路に入っている数
  let peak = 0;          // 同時占有のてっぺん(物差し)
  let enteredCount = 0;  // これまでに入坑した総数(累積。退出しても減らない=行列の存在証明)
  const gates: Array<{ resolve: () => void; reject: (e: unknown) => void }> = [];

  const extract: Extract = (vein) => {
    live++;
    enteredCount++;
    if (live > peak) peak = live;          // てっぺんを記録
    const d = deferred<void>();
    gates.push({ resolve: d.resolve, reject: d.reject });
    return d.promise.then(
      () => { live--; return { veinId: vein.id, amount: 1 }; }, // 掘り終え=退出
      (e) => { live--; throw e; },                              // 失敗でも退出
    );
  };

  return {
    extract,
    peak: () => peak,
    live: () => live,
    entered: () => enteredCount,            // 入坑の累積(退出で減らない)
    finishOne: () => { gates.shift()?.resolve(); }, // 入坑順に1体だけ掘り終えさせる
    failOne: () => { gates.shift()?.reject(new Error("落盤")); },
  };
}

少しなら、平気だった

「まだ分からん」とカイナは言った。意外だった。私はてっきり、巻物を見た時点で答えは出ているものと思っていた。「まず、少なく放って、数えてみる」

彼女は二体だけ放った。計器の針は、二で止まった。通路は、平気な顔をしている。

「ほら」私はかえって苛立った。「少なければ、何ともないじゃない。なら本番は、もっと多く放てばいいだけでしょう。数を増やせば、増やしただけ採れる」——私はまだ、自分の信念を疑っていなかった。

カイナは無言で、放つ数を増やしていった。五体。十体。harvestAll は、脈の一覧を map で配ると、その全部を——一体ずつ順にではなく——同じ一拍のうちに放つ。だから放った瞬間、計器の針が、放った数のところまで一息に振り切れた。少ないうちは、あれほど何ともなかったのに。

カイナは針を指してから、初めて口を開いた。

「見ろ。今この瞬間、通路にいる数——この針が、放った数と、ぴたり同じだ。お前が見ていたのは『何脈ぶん掘ったか』。だが通路が見ているのは、『今、何体いるか』。こっちだ」

彼女は、その針の振り切れを、檻の中で必ず起こせる形にして残した。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
it("群れを一斉に放つと、同時占有が件数まで膨れる(圧壊を招く同時占有の再現)", async () => {
  const shaft = makeShaft();
  const veins: Vein[] = Array.from({ length: 5 }, (_, i) => ({ id: "v" + i }));

  const all = harvestAll(veins, shaft.extract); // map が全件を同期で発火
  assert.equal(shaft.live(), 5); // 放った瞬間、5体すべてが通路の中
  assert.equal(shaft.peak(), 5); // 同時占有のてっぺん = 件数(通路の限界 2 をはるかに超える)

  for (let i = 0; i < 5; i++) shaft.finishOne(); // 後始末
  const ores = await all;
  assert.equal(ores.length, 5);
  assert.equal(shaft.peak(), 5); // 最後までてっぺんは件数のまま
});

断っておくと、この模擬戦が起こしているのは、坑道の崩落そのものではない。計器が映すのは、崩落を招く原因——同時占有の針——だ。「繁忙の山場でだけ、たまに」起きていたあの潰れ方を、狙えば必ず針が振り切れる形にして、卓の上に捕まえた。それだけでも、私には十分すぎる収穫だった。本番なら、この針が振り切れる刻、坑道の通路は——外の世界でいう、つなぎ口やら接続やらの、数に限りのある狭い資源は——飽和して、潰れる。

「総数を減らせば、針も下がる」とカイナ。「だが、それは——」

「採れ高を、半分捨てるだけ」私はその先を引き取った。苦々しかった。「通路が耐える数で、全部採りたい。それが私の仕事なのよ」

間隔を空けても、たまっていく

「なら」と私は、次の近道を口にした。「放つ間隔を空ければいい。一度にどっと出すから潰れる。なら、少し時間をずらして、一体ずつ間を置いて放てば、通路は空くでしょう」

カイナは、すぐには頷かなかった。一度、計器に目をやってから、低く言った。

「通路に同時にいる数は、入る速さから、出る速さを引いた残りで決まる。掘りに手間取る——出が遅い——なら、入る間隔をいくら空けても、出が追いつかない。たまっていく」

例えば、と彼女は岩肌に数を刻んだ。一秒おきに一体ずつ放っても、一掘りに十秒かかるなら、十秒後には、通路の中に十体近くがたまっている。間隔を空けたのに、だ。

「間隔を空けるのは、『一刻あたり、何体放つか』を絞る話だ。だが今、通路を潰しているのは、『同時に、何体いるか』。別の物差しだ。この二つを、混ぜるな」

Gatekeeper regulating wisp traffic with two permits and keeping an orderly FIFO queue

二つの光景を並べてみれば、その差は一目瞭然だった。門番のいない世界では、五体が同じ刻に通路へなだれ込み、針が五まで膨れて通路を圧壊させる。しかし門番を立てれば、通路にいるのは常に約束された二体まで。一体が出て行けば、行列の先頭が交代するように一体入る。群れは整然と列を成し、滞りなく、しかし決して上限を超えずに通っていくのだ。

「それに」とカイナは続けた。「間隔で同時数を抑えようとすると、その同時数は、一掘りにかかる刻の長さしだいで上下する。掘りが速ければ少なく済むが、掘りが手間取った刻、跳ね上がる。間隔では、通路が耐える上限を、約束できない。同時数そのものを N で縛れば、一掘りがどれだけ長引こうと、通路にいる数は N を超えない。上限を保証したいなら、縛るのは間隔じゃない、同時数のほうだ」

私は黙った。一刻あたりの本数と、同時にいる数。言われてみれば、まるで違う。私はずっと、その二つを同じものだと思い込んで、間隔ばかりをいじろうとしていた。

カイナは立ち上がって、潰れた通路の壁を撫でた。そこには、無数の引っ掻き傷が、同じ狭い口へ向かって束になって走っていた。群れが我先に、同時に押し通ろうとした痕だ。

「これは、暴食の群れ蟻だ」と彼女は言った。「一匹なら、無害だ。だが餌——仕事を見ると、群れの全部が、同じ狭い口へ、一斉になだれ込む。通路は、その同時の重みで潰れる。蟻が悪いんじゃない。全部を一度に放った、その放ち方が悪い」

そして、術式の理屈そのものを、淡々と続けた。聞き取れた範囲で書き留めておく。

「型は、この潰れを見張れない。extract の戻り値が Promise<Ore> だと、型は教えてくれる。だが、それを『同時に何本走らせているか』は、型のどこにも書かれていない。同時占有の数は、術式を走らせて、初めて立ち上がる量だ。型が綺麗に整っていることと、通路が潰れないことは、別の話だ」

彼女は手元の羊皮紙に、群れが一斉になだれ込み、通路が自重で歪んでいく様を素早く線で描いてみせた。後で私が手記に描き写したものが、これだ。

Dungeon passage collapsing under the weight of five simultaneously invading magic wisps

速さだと思っていたものは、ただの「こらえ性のなさ」だった。総数でもない、間隔でもない。同時に通路を占める数。それを、私は——誰も——見張っていなかった。

門番を、ひとり立てる

カイナの手当ては、術式を組み替えることでも、どこか一行を動かすことでもなかった。彼女は、通路の入口に、門番をひとり立てた。

門番は、許可証を N 枚だけ持っている。坑道へ入りたい使い魔は、まず門番から許可証を一枚もらう。なければ、行列に並んで待つ。中の一体が掘り終えて出てきたら、許可証を門番に返す。門番はそれを、行列の先頭の一体に、そのまま手渡す。——これだけだ。

「掘り方には、指一本触れん」とカイナ。「extract は、前のままだ。変えるのは、入る前に門番をくぐらせることと、出たら必ず許可証を返すこと。その作法だけだ」

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 門番:同時に通すのは N 体まで。許可証を配り、出たら次へ渡す(counting semaphore)。
class Semaphore {
  private available: number;                    // いま配れる許可証の枚数
  private readonly limit: number;
  private readonly waiters: Array<() => void> = []; // 行列(FIFO):待たせた acquire を解く resolve

  constructor(limit: number) {
    if (limit < 1) throw new RangeError("門番が通せる数は 1 以上でなければならない");
    this.limit = limit;
    this.available = limit;
  }

  acquire(): Promise<void> {
    if (this.available > 0) {
      this.available--;             // 空きあり:許可証を1枚渡して即通す
      return Promise.resolve();
    }
    // 空きなし:行列の末尾に並んで待つ(Deferred を積む)
    return new Promise<void>((resolve) => {
      this.waiters.push(resolve);
    });
  }

  release(): void {
    const next = this.waiters.shift();   // 行列の先頭を1体だけ
    if (next) {
      next();            // 許可証をそのまま手渡す(available は据え置き=枠は埋まったまま)
    } else {
      this.available++;  // 待ち手なし:許可証を棚に戻す
    }
  }
}

// 門番をくぐらせる定型。finally で必ず許可証を返す(返却は“一点”だけ)。
async function withSemaphore<T>(sem: Semaphore, task: () => Promise<T>): Promise<T> {
  await sem.acquire();
  try {
    return await task();
  } finally {
    sem.release();       // 成功でも失敗でも、必ず1回だけ返す
  }
}

// After: 門番を立てて N 体ずつ通す。掘り方は同じ。全件は完遂する(取りこぼし0)。
async function harvestLimited(veins: Vein[], extract: Extract, limit: number): Promise<Ore[]> {
  const gate = new Semaphore(limit);
  return Promise.all(veins.map((vein) => withSemaphore(gate, () => extract(vein))));
}

私が見たのは、許可証と行列、それだけだった。だがカイナは、術式と向き合うと、もう少し冷たく、細かいことを言った。聞き取れた範囲で、そのまま書き留めておく。

release がやることは、行列を見てから決まる。待っている一体がいれば、許可証は棚に戻さず、その先頭へ、そのまま手渡す。枠は埋まったまま、持ち手だけが替わる。待ち手が一人もいなければ、そのとき初めて、許可証を棚に戻す。——この坑道(JavaScript)では、release は一息に走り切る同期の処理だ。途中で誰かが割り込む隙はない。だが、順序そのものが効く。もし無造作に、先に棚へ戻してから待ち手に手渡せば、棚に戻した一枚と、手渡した一枚で、許可証が一枚ぶん増える。通せる数が、こっそり N+1 に化けるんだ。だから、戻すより先に行列を見て、待ち手がいれば棚に戻さず手渡す。そうすれば、許可証の総数は、いつ数えても N のまま狂わない。後でこの待ち受けに非同期を挟むことになっても、この作法なら崩れない」

「取った許可証は、必ず一枚返す。同じ許可証を、二度は返さない。——この二つは、型では見張れない。release を書き忘れても、術式は組み上がってしまう。二度呼んでも、咎められん。だから返す場所を、finally のただ一点に閉じ込める。取った所から返す所まで、経路を散らさない」

私には半分も分からなかった。だが、許可証を一枚取ったら一枚返す、というところだけは、腑に落ちた。出納が合わなければ、いつか棚は空になる。それくらいは、帳面を預かる身に染みている。

もう一度、計器の前で

カイナは、同じ計器つきの坑道に、今度は門番を立てて、五体を放った。許可証は二枚。

放った直後、不思議なことに、計器の針は動かなかった。許可証は二枚空いている。最初の二体は、すぐに受け取れるはずだ。だが、許可証を即もらえても、その先の入坑——針が上がる所——は、その場では走らない。次の手番(マイクロタスク)に回る。だから放った瞬間は、まだ全員が門の手前にいて、針は零のままだった。カイナがマイクロタスクをひと掃きすると(彼女はその小道具を flush と呼んだ)、許可証を得た最初の二体だけが、ようやく通路へ入った。針は、二。残りの三体は、行列に並んだまま。

 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
// マイクロタスクを数段進める小道具(release→行列先頭のresolve→acquire継続→task の連鎖を掃く)
const flush = async (): Promise<void> => {
  for (let i = 0; i < 4; i++) await Promise.resolve();
};

it("同時占有はNで頭打ち、行列で待たせ、全件さばける(取りこぼし0)", async () => {
  const shaft = makeShaft();
  const veins: Vein[] = Array.from({ length: 5 }, (_, i) => ({ id: "v" + i }));

  const all = harvestLimited(veins, shaft.extract, 2); // 門番つき。N=2
  await flush();
  assert.equal(shaft.live(), 2);    // 同時に通路へ入れたのは2体だけ
  assert.equal(shaft.peak(), 2);    // てっぺんは2
  assert.equal(shaft.entered(), 2); // 入坑したのも2体だけ=残り3体は行列で待機

  shaft.finishOne();                // 1体掘り終え→許可証が返る
  await flush();
  assert.equal(shaft.live(), 2);    // すぐ行列先頭の1体が入り、また2体
  assert.equal(shaft.peak(), 2);    // てっぺんは2を超えない
  assert.equal(shaft.entered(), 3); // 3体目がここで初めて入坑

  while (shaft.live() > 0) { shaft.finishOne(); await flush(); } // 残りを順に
  const ores = await all;
  assert.equal(ores.length, 5);     // 取りこぼし0=全件完遂
  assert.equal(shaft.peak(), 2);    // 最後まで同時占有はNで頭打ち
});

一体が掘り終えると、finally が許可証を返し、その返却が——同じ手番のうちに、同期で——行列の先頭の acquireresolve する。ただし、resolve を呼んでも、待っていた await sem.acquire() の続きは、その場では走らない。Promiseresolve は、続きを今この場で実行せず、次の手番(マイクロタスク)へ回す決まりだからだ。だから「許可証を返す(枠は埋まったまま、持ち手だけ替わる)」のは今の手番、「行列の先頭が入坑する(針が上がる)」のは次の手番。この『resolve は同期、続きは後回し』のずれがあるから、一体が出るのと次の一体が入るのは、決して重ならない。だから、同時に通路にいる数は、二を超えない。

flushPromise.resolve() を四回 await しているのは、この連鎖を掃ききるためだ。許可証の返却 → withSemaphore の続き → 次の extract の発火 → その then で針が動く、と、一度の解放で高々三つの手番を跨ぐ。四回は、その最長より一つ多めに取った安全側の段数だ(三回でも足りるが、余裕をみている)。実時間を待つ setTimeout には頼らない。掃くのは、あくまで手番(マイクロタスク)だ。

「前に、別の山で数えた鍵は」とカイナが、ふと言った。「片付けたはずなのに積もり続けて、二度と零に戻らなかった。あれは、漏れだ。だが、この門番の針は逆だ。二で頭打ちになって、一体ずつ掃けて、必ず零に戻る。同じ『数える』でも、片や戻らない漏れ、片や頭打ちで戻る有界——測っている量の、形が逆なんだ」

門番が「二体までは即、三体目は行列、解放した瞬間に先頭だけを通す」という規則を厳格に守れているか。カイナは最も小さな模擬戦で、その正確さを確かめた。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
it("門番:N体は即時、N+1体目は行列で待ち、解放した瞬間に先頭が通る(決定性)", async () => {
  const gate = new Semaphore(2);
  const log: string[] = [];
  void gate.acquire().then(() => log.push("a")); // 即時(許可証1枚目)
  void gate.acquire().then(() => log.push("b")); // 即時(許可証2枚目)
  void gate.acquire().then(() => log.push("c")); // 空きなし→行列で待つ
  await flush();
  assert.deepEqual(log, ["a", "b"]); // c はまだ通れていない(行列)
  gate.release(); // 保持者(a相当)が掘り終え、許可証を1枚返した、とみなす
  await flush();
  assert.deepEqual(log, ["a", "b", "c"]); // 解放した瞬間、行列先頭の c だけが通る
});
	sequenceDiagram
    participant Q as 行列(FIFO)
    participant K as 門番(許可証N=2)
    participant S as 通路(同時はN体まで)
    Q->>K: 5体が許可証を求める
    K->>S: 1体目に許可証 → 入坑(live=1)
    K->>S: 2体目に許可証 → 入坑(live=2)
    K-->>Q: 残り3体は行列で待機(許可証なし)
    S-->>K: 1体目 掘り終え→許可証を返す(release)
    K->>S: 行列先頭(3体目)へ手渡し→入坑(live=2のまま)
    Note over K,S: 「1体出る」と「1体入る」が一拍ずれて連なる→peakはNを超えない
    S-->>K: 以降も release のたびに先頭を1体ずつ通す
    Note over Q,S: 全件さばけて取りこぼし0/peakはNで頭打ち&0へ戻る

図の上では、門番のいない世界で、五体が同じ刻に通路へなだれ込み、針が五まで膨れて潰れる。門番を立てると、通路にいるのは常に二体まで。一体出れば、行列の先頭が一体入る。群れは、行列を成して、一体ずつ、絶やさず通っていく。

落盤しても、許可証は返る

「掘りの途中で、落盤したら?」私は実務の問いを挟んだ。「掘り終える前に死んだ使い魔の許可証は、返らないんじゃないの。それきり、枠が一つ減ったままになるんじゃ」

カイナは、一体をわざと落盤させる模擬戦を足した。withSemaphore は、掘りが失敗しても、finally が許可証を返す。だから、次の一体はちゃんと通る。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
it("採取に失敗しても許可証は必ず返る(finallyで送還)", async () => {
  const shaft = makeShaft();
  const veins: Vein[] = [{ id: "x0" }, { id: "x1" }];
  const gate = new Semaphore(1);

  const p0 = withSemaphore(gate, () => shaft.extract(veins[0])).catch(() => "failed");
  const p1 = withSemaphore(gate, () => shaft.extract(veins[1])); // N=1 なので行列で待つ
  await flush();
  assert.equal(shaft.entered(), 1); // まず1体目だけ入坑

  shaft.failOne();                  // 1体目が落盤(reject)
  await flush();
  assert.equal(shaft.entered(), 2); // 許可証が返り、2体目が入坑できた
  shaft.finishOne();                // 2体目は無事
  assert.equal(await p0, "failed");
  await p1;
});

「もし、その finally を省いて、掘りが成功したときだけ許可証を返す、と書いたら——」カイナは、わざと壊した門番を、もう一つこしらえた。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 誤実装:成功時だけ許可証を返す(finally なし)。失敗すると返らない。
async function withSemaphoreBroken<T>(sem: Semaphore, task: () => Promise<T>): Promise<T> {
  await sem.acquire();
  const result = await task(); // ← ここで reject すると、下の release に到達しない
  sem.release();
  return result;
}

it("finally無しの門番は、失敗で許可証が返らず後続が永久に待つ(誤実装)", async () => {
  const shaft = makeShaft();
  const gate = new Semaphore(1);
  const p0 = withSemaphoreBroken(gate, () => shaft.extract({ id: "x0" })).catch(() => "failed");
  // p1 は永久に未解決のまま=誤実装の証明。await しない。
  const p1 = withSemaphoreBroken(gate, () => shaft.extract({ id: "x1" })).catch(() => {});
  void p1;
  await flush();
  assert.equal(shaft.entered(), 1);

  shaft.failOne();                  // 1体目が落盤→release に到達しない
  await flush();
  assert.equal(shaft.entered(), 1); // ★2体目は永久に行列で待つ(デッドロック化)
  assert.equal(await p0, "failed");
});

針は、一のまま動かなかった。落盤した一体の許可証は、返らない。行列の先頭は、来ない許可証を、永久に待ち続ける。最後の一枚が宙に消えれば、やがて誰も通れなくなる——門番が、坑道を開ける番人から、坑道を閉ざす番人に変わる瞬間だ。これは、二体が互いに相手を待ち合って固まるのとは違う。許可証が、ただ枯れて戻らないだけだ。原因は逆を向いているのに、止まるという結末は、変わらない。

「取ったら、返す」とカイナは、壊した門番を脇へ寄せた。「掘りが失敗しようが、何だろうが、必ず返す。だから finally だ。出納を、運に任せるな」

この門番が、通せないもの

「これで」と私は、最後にそれを確かめたかった。「もう、坑道は潰れない?」

カイナは、はっきりとは請け合わなかった。許可証を一枚、岩の上に置くと、低く、順に説きはじめた。

「この門番が縛るのは、一つの通路の、同時の数だ。同時にいる数は、N で頭打ちになる。全部の脈は、ちゃんと採り終える。それは、確かにやった」

「だが」と彼女は、別の通路のほうへ目をやった。「通路が二つあって、一体が、こっちの許可証とあっちの許可証を、両方欲しがったら——そして、二体が逆の順で取り合ったら——互いに、相手の返す許可証を待って、どちらも動けなくなる。石になる。それは、門番一人の話じゃない。許可証を取る順番の話だ。別の獣だ」

「それから」とカイナは続けた。「この門番が絞るのは、『同時に何体』だ。『一刻あたり何体』じゃない。掘りが速ければ、同時数を二に抑えても、一刻のうちに何十体も通り抜ける。下流が『一刻に N 本まで』と音を上げるなら、それは門番じゃ抑えられん。一定の刻ごとに滴がたまる水瓶——滴がある時だけ通す器が要る。それも、また別の話だ」

最後に、彼女はひとつ釘を刺した。「行列で待っているあいだに、待つのをやめたくなったら——その一体を、行列から自分で抜く後始末が要る。中で掘っている最中にやめるのとは、訳が違う。この門番は、いちばん小さな形だ。そこまでは、持たせていない」

通せるものと、通せないもの。その仕分けがついて、私は今日手にした門番が、どこまでを守れるのかを、ようやく見定められた。万能の門ではない。だが、あの通路はもう、群れの重みで潰れない。

試運転

カイナは、群れを一斉に放つ古い術式と、門番を立てた術式の、両方の模擬戦を、まとめて走らせた。潰れる方には「針が件数まで膨れる」ことを、手懐けた方には「N で頭打ちになる」ことを、それぞれ記録として残してある。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
$ node --test
▶ After: harvestLimited(門番+行列=counting semaphore)
  ✔ 同時占有はNで頭打ち、行列で待たせ、全件さばける(取りこぼし0)
  ✔ 門番:N体は即時、N+1体目は行列で待ち、解放した瞬間に先頭が通る(決定性)
  ✔ 採取に失敗しても許可証は必ず返る(finallyで送還)
▶ Before: harvestAll(暴食の群れ蟻・無制限並列)
  ✔ 群れを一斉に放つと、同時占有が件数まで膨れる(圧壊を招く同時占有の再現)
  ✔ finally無しの門番は、失敗で許可証が返らず後続が永久に待つ(誤実装)
ℹ tests 5
ℹ pass 5
ℹ fail 0

試運転、合格。圧壊を招く同時占有も、その頭打ちも、これからはこの模擬戦が見張り続ける。次に誰かが——あるいは私自身が、また採れ高に目が眩んで——群れを一度に放とうとすれば、針が件数まで振り切れるその姿が、卓の上で先に捕まる。

速さは、絶やさず流すことだった

私は、門番を立てた術式で、潰れた坑道の採掘を再開した。N は二。使い魔は、もう一度にどっとは出ない。行列を成して、一体出れば一体入る、その拍子で、静かに通路を流れていく。

最初、私は「遅くなった」と感じた。一度に二体ずつなんて、まどろっこしい。だがカイナが、採れ高の帳面を指した。

潰れないので、坑道は止まらない。止まらないので、結局——前のどのやり方よりも早く、私は脈を全部、採り終えていた。

速さは、一度に放つ数ではなかった。通路が耐える数を超えて詰め込めば、潰れて、採れ高は零になる。通路が耐える数で、絶やさず流し続ける——それが、いちばん早く全部を採る道だった。私がずっと「速さ」と呼んでいたものは、ただ、いちばん最初に通路を潰す近道だったのだ。

私は、門番の許可証を手に取った。次に掘る坑道は、もっと細い。私は、瓦礫の通路の幅を目で測って、自分で許可証の枚数を数えた。

「この通路なら……四枚」

開幕で、私はこの女に「数を教えて」と詰め寄った。今は、自分で数えている。

カイナは、それを覗き込みもしなかった。岩から計器を抜きながら、短く言った。

「通路に訊いて、決めろ。潰れる手前が、その通路の数だ」

私は許可証を、四枚に数え直した。今度は、放つ前に。


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

  • 魔獣名(クラス/パターン名): セマフォ・アント(暴食の群れ蟻)/ 無制限並列の破綻(Semaphore=同時実行数制限/Queue で馴致)
  • 危険度(難易度/バグの影響度): ★★★★☆(平時・少数なら無害。繁忙の山場で群れが一斉に同じ狭い資源へなだれ込んだ刻にだけ、通路=共有資源を同時占有で圧し潰す)
  • 主な生態(アンチパターンの特徴):
    • Promise.all(items.map(task)) で全件を同時発火し、同時占有数(peak)が件数まで膨れる。コネクションプール・ファイル記述子・下流レートなど“狭い通路”が飽和して EMFILE・接続枯渇・429・OOM で破綻する(=資源枯渇クラッシュ。採取結果のデータは壊れない)
    • 平時の少数試掘では再現せず、本番相当の件数・遅延でだけ露見する
    • “総数を減らす”は採れ高を捨てるだけ、“投入間隔を空ける”は時間あたり流量(レート)を絞るだけで、同時占有(並行)は絞れない——潰しているのは並行数
  • 契約のポイント(設計の要点):
    • 入口に門番(counting semaphore)を立て、許可証 N 枚で同時占有を N に頭打ちにする。溢れは行列(FIFO)で待たせ、出た一体が許可証を返した瞬間に行列先頭へ手渡す(release 駆動の drain)。peak は N で頭打ち、必ず 0 に戻る(=有界。“戻らない漏れ”とは測る量の形が逆)
    • 採掘術(extract)には触れず、入退出の作法だけを足す構造変更。許可証の取り(acquire)と返し(finallyrelease)を対にし、返却を一点に閉じ込めて、デクリメント漏れ・reject 時の release 漏れ・二重 release を封じる
    • 取り/返しの対称性と二重 release の防止は、型では検証できない実行時の不変条件。同時占有の数も、走らせて初めて立つ実行時の量で、型注釈はインタフェースの形しか守らない
  • 契約外事項(保証しないこと):
    • 複数の門番を別々の順で取り合うと石化(デッドロック)しうる=ロック獲得順序(Lock Ordering)の領分
    • 絞るのは同時数であって時間あたり流量ではない。レート制限は別の器(Token Bucket)の領分
    • 待機中(行列で待つあいだ)のキャンセルは、行列からの自己削除が要る。実行中のキャンセルと対称でなく、この最小形には持たせていない
  • 現在のステータス: 🟢 群れを N 体ずつ通す契約成立(同時占有を有界化・全件完遂)/複数門番の石化と、時間あたり流量は、別の獣として後日
comments powered by Disqus
Hugo で構築されています。
テーマ StackJimmy によって設計されています。