最上山の紅葉は、夏のあいだずっと支度をしてから、ようやくあざやかな色を放つ。それから毎年そうなる。春、夏、秋、冬。
これはゼロから書いているファイルシステムです。巨人の肩の上に立ってはいますが、ただ真似をしているわけではありません。だから、自分たち特有の問題を解かなければなりません。
- コードを書くための決定はどこから来るのか
- 段階ごとに何を実装するのか
- いま間違っていないことをどう証明するのか
一 コードを書くための決定はどこから来るのか
およそ三週間、crates/ には一行もコードを書きませんでした。リポジトリには crates/ ディレクトリもルートの Cargo.toml もなく、毎日 research/ で研究とテストを重ね、九十あまりのバイナリモデルがたまりました。
プロジェクトの出発点は、二十一か条の軍規に加えて次のものです。逆引きインデックスを持つ（D1）、可変幅のフルストライプ（D2）、データとメタデータを分けず一つのアロケータで割り当てる（D3）、birth txg と deadlist で記帳する（D5）、最初の数年は Linux 本流に入らない（D7）。
その上で、agent の三者プロセスで何度も決定を重ね、次のものの初版を決めました。
- フォーマット：デバイス識別ビット、ユニットヘッダの全バイト、木の種類、世代を識別するレコード。
- ルートレコード：バイト幅と、何を入れるか。
- journal の形：データ型と記録の仕方。
- 木テーブル：バイト幅、高さ、構成の仕方。
もちろん、フォーマット定数もあります。決定はすべて .claude/kb/decisions/ に、実験は .claude/kb/experiments/ に置き、実験装置と三者論証の資料・判決は research/ に置きました。
着手前の最後の関門は、決定全体の総点検です。28 本の決定文書を十一本の審査レッグ（Opus 八本、Sonnet 三本）に割り振り、判断基準は一つだけでした。今日の原文どおりに二人がそれぞれ「新プール・新規ファイル」を書いたら、書き出すバイトは違ってくるか。決めるべき項目が 31 件見つかり、ユーザーが一件ずつ決めました。
決定をバイトに落とすのは実験 E142（新プール・新規ファイルの空実行）の役目です。research/ の独立した装置で、バイト表をそのままバイトとして書き出し、クラッシュモデルに沿って一つずつ復旧させます。全部で七回走らせ、走らせるたびに、バイト表どおりには書けない空白がいくつか浮かび上がりました。
こうして crates/ を書くときには、実は手元にすでに動く答えがありました。
二 段階ごとに何を実装するのか
ゼロから作る COW なので、既存の検証基準もなく、出力を比べられる参照実装もありません。そして時代の恩恵を受けているおかげで、先に FUSE を作ってマウントして確かめる必要もありません。そこで、トランザクション単位で進める段階計画に決めました。どんな機能も新しい種類のトランザクションであり、トランザクション層のない機能実装は一切受け入れません。
各段階で何を実装するか。まだ答えはありません。ただ最初のトランザクションについては迷いがないはずです。ディスクを作り、COW の書き込みを一回行う。
マイルストーン一の名前は「新プール・新規ファイル」です。二台のディスクで mkfs し、3000 バイトのファイルを書き、一回コミットし、プロセス内のものをすべて捨て、コールドスタートして読み戻します。八つのステップに分け、各ステップの受け入れテストは、まず失敗しうることを証明しなければなりません。
| ステップ | 内容 |
|---|---|
| 0 | 足場：四つの crate（フォーマット定数、コア、harness、プールレベル checker）、ブロックデバイスの抽象、レコーダ |
| 1 | mkfs：システム構成、三つのルートリング領域、journal リング、インスタンステーブル、空の木テーブル、第 0 世代ルート |
| 2 | 32 KiB のデータユニットを一つ割り当て、ファイル内容を書き込む。各ディスクに一部ずつ |
| 3 | inode 木、extent 木、割り当てレコード木、記帳木 |
| 4 | 中央マッピング：論理的な身元 → 位置 |
| 5 | 一回の発行 |
| 6 | コールドスタート復旧、ファイルの読み戻し |
| 7 | 層 0 のクラッシュ点リプレイ |
三 いま間違っていないことをどう証明するのか
参照できる前例がないので、実装に問題がないことを自分で証明する必要があります。クラッシュ復旧を同時に実装することも目標の一つでした。だからクラッシュリプレイのテストが何より重要です。簡単に言えば、クラッシュ点ごとのディスク上の状態を記録し、復旧を走らせ、判定器で検査します。
もちろん、ほかのテストもあります。
- 二種類のアドレス型を混ぜるとコンパイルが通らない。
- レコーダが書き込みを一つ記録し損ねると、件数ゲートが失敗する。
- 同じパラメータで mkfs を二回行うと、二つのイメージはバイト単位で一致する。
- 五つの書き込み経路のセグメント列が E142 の出力と完全に一致し、journal の逆方向チェーンが実験出力の
back_chain=628216162と完全に一致する。 - ルートスロット、journal、データユニット、システム構成を壊す八つのプローブの結末が、実験出力と一つずつ一致する。
- セグメント内の部分集合の列挙、三つの判定器、など。
逆方向チェーンについてもう一言。実験装置と crates/ は同じ条項から別々に書かれ、コードを共有していません。両者が同じ量について同じ数に行き着くということは、バイト表・条項・実装の三者がその量について一致しているということです。どちらかが一か所でも間違えれば、比較は失敗します。
コードと実装：最初のトランザクションと 26 万回のリプレイ
以下のコードの出所は二つです。実験コードは research/ の実験装置 E77 から、実装コードは crates/ からです。抜粋では最初のトランザクションと関係のない行を削り、// … で示しています。
1 最初のトランザクション
mkfs のあとの書き込み列全体は、三つの経路からなります。
- 番号の取得：インスタンス世代 1 を各ディスクのシステム構成に書く。2 回の書き込み。
- 二回の暖機（空の発行）：checkpoint_txg を 0 → 1 → 2 と進める。10 回の書き込み。
- 本番の発行 txg 3：21 回の書き込み。8 ユニットを両ディスクに 16 回、journal レコード 2 回、ルートスロット 1 回、システム構成 2 回。
暖機は D16 の決定事項 8 から来ています。最初のマウントでは、このインスタンスのルートを両方のディスクに書いてから fsync を返します。
どの発行も同じ順序でディスクに落ちます。
ユニットとインデックスノード（各ディスクに一部ずつ）
→ バリア
→ journal レコード（各ディスクに一部ずつ）
→ バリア
→ ルートスロットの FUA 書き込み（領域 txg mod 3 のスロット (txg div 3) mod 8）
→ システム構成スロットのローテーション（各ディスク一回、tail = jsn カウンタ）
この順序は、コードを書く前に E77 で測ってあります。データの完全性に必要なのはルートスロットの前のバリア一本だけで、レコードとルートスロットの間のバリアはレコード列の完全性を保つためのものです。
番号の取得、暖機、発行の三経路は、どれも一つの閉じた列挙型だけを通ってディスクに落ちます。設計規律は「トランザクション層は一つ、すべての構造で共有する」で、fsync のために別のものを作ることは許しません。
実装コード crates/singlefs-core/src/transaction.rs
// ワイルドカードの腕はない。腕を一つ書き忘れるとコンパイルが通らない。
pub enum CommitStep<'publish> {
WriteUnitToEveryDevice { slot: SlotNumber, unit: &'publish [u8], identity: TransactionUnit },
// トランザクションの選別：コミットマークは最後のレコードにある。接頭辞に含まれなければ不完全なので全部捨てる。
if prefix_record_count != RECORDS {
return Outcome::StateOld;
}
match replay {
Replay::Validating => {
// 適用の前に名指しされたユニットを一つずつ検証する。一つでも合わなければトランザクションごと捨てる（古い状態へ）。
for record_index in 0..RECORDS {
for unit_index in units_named_by_record(record_index) {
if !persisted(state, unit_index) {
return Outcome::StateOld;
}
}
}
Outcome::StateNew
}
// 検証せずにそのまま接ぎ木し、成功を自称する。間違っているかどうかは audit が判定し、自分では判定しない。
Replay::Naive => Outcome::StateNew,
}
}
/// 独立監査：復旧側が自称する結末が正しいかを、物理的な真実と照らして判定し直す。
/// この一歩がないと、「検証しないリプレイ」による静かな破損が成功として記録されてしまう。
fn audit(state: u16, claim: Outcome) -> Outcome {
if claim == Outcome::StateNew && (0..UNITS).any(|unit_index| !persisted(state, unit_index)) {
return Outcome::Corrupt;
}
claim
}
/// ルートスロットが永続化済み（fsync が返っているかもしれない）のに古い状態へ戻る = 約束したデータを失う。
fn is_violation(state: u16, outcome: Outcome) -> bool {
match outcome {
Outcome::BrokenRoot | Outcome::Corrupt => true,
Outcome::StateNew => false,
Outcome::StateOld => persisted(state, ROOT_SLOT_WRITE_INDEX),
}
}
復旧は自分が考える結末を報告するだけで、それが正しいかは audit が永続化集合と照らして判定し直します。監査する側とされる側は同じコードを使いません。この決まりは、のちにそのまま crates/ に持ち込まれました。四通りのバリア配置の結果です。
| バリア配置 | 状態数 | 違反（検証つきリプレイ） | 違反（検証なし） |
|---|---|---|---|
| [ユニット][レコード][ルート] | 72 | 0 | 0 |
| [ユニット][レコード+ルート] | 79 | 0 | 0 |
| [ユニット+レコード][ルート] | 513 | 0 | 63 |
| [すべて自由] | 1024 | 504 | 567 |
適用前の検証を外すと、ルートスロットの前のバリアだけを残した配置で、たちまち 63 か所の静かな接ぎ木が出ます。だから「レコードが名指しする各項目が自分のチェックサムを持つ」ことはおまけではなく、バリアを一本省くための交換条件です。
状態数の閉形式
各セグメントは自分の真部分集合をすべて寄与し、最後に「すべて永続化」の一つを足します。
状態数 = 1 + Σ (2^|セグメント| − 1)
「新プール・新規ファイル」の mkfs 後のセグメント列は 2+2+1+2+2+1+18+2+1+2、全部で 33 回の書き込みです。閉形式に代入すると：
3 + 3 + 1 + 3 + 3 + 1 + 262 143 + 3 + 1 + 3 + 1 = 262 165
8 ユニットを両ディスクに書く 16 回と、二回目の暖機のシステム構成スロット書き込み 2 回の間にはバリアがなく、同じセグメントに入ります。2^18 = 262 144。つまり 26 万という数は、本質的に 18 回の書き込みからなる一つのセグメントのべき集合です。状態数はセグメント長に対して指数的に増えます。
この数は一歩ずつ増えてきました。E142 の一回目はトランザクションの 21 回の書き込みだけを列挙し、セグメント 16+2+1+2 で 65 543 状態。四回目は暖機が実際にバイトを書くようになって 262 162。六回目は番号取得の二回の書き込みが先頭のセグメントに入り、262 165 になりました。
4 checker の実装
プールレベルの checker（crates/singlefs-checker）が実装と共有するのはフォーマット定数のモジュールだけです。CRC-32C はビット単位で書き直し、三種類のスロットとユニットの解析もそれぞれ別に書いています。実行時と checker が同じコードを使えば、それは同じ一回の計算であり、照合の意味はその場でなくなります。
同じ逆方向チェーンを checker は自分で計算し、CRC もビット単位の実装を使い、実装側のものは使いません。
実装コード crates/singlefs-checker/src/lib.rs
/// ビット単位の CRC-32C（反射多項式 0x82F63B78）。表を引かず、実装側のものも呼ばない。
pub fn crc32_castagnoli_bitwise(bytes: &[u8]) -> u32 {
const POLYNOMIAL_REFLECTED: u32 = 0x82F6_3B78;
let mut remainder = !0u32;
for byte in bytes {
remainder ^= u32::from(*byte);
for _bit in 0..8 {
remainder = if remainder & 1 == 1 {
(remainder >> 1) ^ POLYNOMIAL_REFLECTED
} else {
remainder >> 1
};
}
}
!remainder
}
/// 逆方向チェーン：前のレコードヘッダの CRC-32C。`header_csum` の 32 バイトは 0 として扱う。
pub fn back_chain_of_record_header(record: &[u8]) -> u32 {
let mut header = record[..usize::try_from(JOURNAL_HEADER_BYTES).expect("487")].to_vec();
header[JOURNAL_HEADER_CHECKSUM_OFFSET..JOURNAL_HEADER_CHECKSUM_OFFSET + 32].fill(0);
crc32_castagnoli_bitwise(&header)
}
/// スロットやユニットの自己検証チェックサム：覆う範囲でチェックサム欄を 0 として計算し、先頭 4 バイトが CRC、残りはすべて 0。
pub(crate) fn checksum_field_holds(bytes: &[u8], cover_end: usize, field_offset: usize) -> bool {
let field_width = usize::try_from(WIDE_CHECKSUM_BYTES).expect("32");
if bytes.len() < cover_end || field_offset + field_width > cover_end {
return false;
}
let mut covered = bytes[..cover_end].to_vec();
covered[field_offset..field_offset + field_width].fill(0);
let expected = crc32_castagnoli_bitwise(&covered).to_le_bytes();
let stored = &bytes[field_offset..field_offset + field_width];
stored[..4] == expected && stored[4..].iter().all(|byte| *byte == 0)
}
/// システム構成スロットを選ぶ：チェックサムが合い、世代がいちばん大きいもの。
pub fn choose_system_configuration(slots: &[&[u8]]) -> Option<(usize, SystemConfigurationView)> {
slots
.iter()
.enumerate()
.filter_map(|(index, slot)| check_system_configuration_slot(slot).ok().map(|view| (index, view)))
.max_by_key(|(_, view)| view.slot_generation)
}
入口はイメージを一つだけ受け取り、各不変条件を「成立」「不成立」「適用外」で報告します。
実装コード crates/singlefs-checker/src/walk.rs
/// プールレベル checker の入口：すべての不変条件を報告し、評価できなかったものは理由つきで「適用外」と報告する。
pub fn check_pool_image(reader: &dyn ImageReader) -> Vec<(&'static str, InvariantVerdict)> {
let system_configurations = chosen_system_configurations(reader);
// …ルートを選び、journal を走査し、木をたどって不変条件を一つずつ判定する
}
クラッシュ状態は一つずつ三つの判定器に渡されます。
| 判定器 | 何を判定するか |
|---|---|
| 復旧 + oracle | journal を見る場合と見ない場合で一回ずつ復旧する。ファイルが読めたらバイト単位で正しくなければならない。ルートスロットが永続化済みなら古い状態に戻ってはならない。木をたどる処理は失敗してはならない |
| プールレベル checker | 入口は walk::check_pool_image、23 個の不変条件を判定 |
| レコード照合器 | ルートはディスクにあるのに journal レコードがない。復旧が新しい状態に達したと自称するのにユニットがない |
レコード照合器が独立しているのは、D13 の決定事項 7 がプールレベル checker の対象を一つのイメージに限っているからです。二つ目の入力（クラッシュ前のイメージ、レコード列）を必要とする検査は、その担当ではありません。
判定器は失敗できなければならず、そうでなければ違反ゼロに意味はありません。壊したイメージを 26 個用意し、各不変条件に少なくとも一つずつ当て、どれもその条件で失敗します。ルートスロットが永続化済みの状態で 8 個のユニットを一つずつ抜くと、8 回とも失敗します。journal レコードとルートスロットの間のバリアを外すと、レコード照合器が失敗します。
結果
初めてディスクを作り、書き込みに成功しました。 二台のディスクで mkfs し、3000 バイトを書き、コミットし、プロセス内のものをすべて捨て、コールドスタートして読み戻すと、バイト単位で一致しました。
クラッシュリプレイ 26 万回、エラー 0。 262 165 個のクラッシュ状態をすべて列挙し、サンプリングはしていません。三つの判定器とも違反ゼロ、手元のマシンの release ビルドで 22.7 秒です。
ただし、これはコードにまったく問題がないという意味ではありません。クラッシュリプレイが覆うのはモデルで列挙したクラッシュ状態だけで、モデルの外の端は覆えません。
- 負荷は「新プール・新規ファイル」の一つだけです。上書き、解放後の再利用、複数回のマウント、ロールバックは、一度もリプレイに入っていません。
- モデルはバリアより前の書き込みはすべて永続化済みと仮定しています。FLUSH を守らないディスクは含まれていません。
- 裂けた書き込みがたまたま 32 ビットの CRC32C をだますことは、承知の上で受け入れています。
- 使われている 66 個の不変条件のうち、checker が判定しているのは 23 個です。
- 理想モデルとの機能の突き合わせ（対拍）は、まだありません。
物語はまだ長い。春、夏、秋、冬。