첫 트랜잭션과 26만 번의 클러시 리플레이 — 제로에서 만드는 COW 파일 시스템 5

가장 높은 산의 단풍은 여름 내내 준비한 후에야 비로소 선명한 색을 냅니다. 그리고 매년 그렇게 됩니다. 봄, 여름, 가을, 겨울.

이것은 제가 처음부터 작성하고 있는 파일 시스템입니다. 거인의 어깨 위에 서 있지만, 단순히 따라 하는 것은 아닙니다. 따라서 우리만의 고유한 문제를 해결해야 합니다.

• 코드를 작성하기 위한 결정은 어디에서 오는가
• 단계별로 무엇을 구현할 것인가
• 현재 틀리지 않았음을 어떻게 증명하는가

약 3주 동안, crates/에는 한 줄의 코드도 쓰지 않았습니다. 리포지토리에는 crates/ 디렉터리도, 루트의 Cargo.toml도 없었고, 매일 research/에서 연구와 테스트를 거듭하며 아흔 개가 넘는 바이너리 모델이 쌓였습니다.

프로젝트의 출발점은 21가지 군규에 더해 다음 내용들입니다: 역참조 인덱스를 가진 (D1), 가변 폭의 풀 스트라이프 (D2), 데이터와 메타데이터를 분리하지 않고 하나의 할당자로 할당하는 것 (D3), birth txg와 deadlist로 기록하는 것 (D5), 그리고 처음 몇 년 동안은 Linux 본류에 들어가지 않는 것 (D7).

그 위에서, agent의 삼자 프로세스를 통해 여러 번 결정을 거쳐 다음 내용들의 초안을 결정했습니다.

• 포맷: 장치 식별 비트, 유닛 헤더의 전체 바이트, 나무 종류, 세대를 식별하는 레코드.
• 루트 레코드: 바이트 폭과 무엇을 담을지.
• journal의 형태: 데이터 타입과 기록 방식.
• 나무 테이블: 바이트 폭, 높이, 구성 방식.

물론 포맷 상수도 있습니다. 모든 결정은 .claude/kb/decisions/에, 실험은 .claude/kb/experiments/에 두었고, 실험 장치와 삼자 논증의 자료 및 판결은 research/에 두었습니다.

착수 전 마지막 관문은 결정 전체의 총점검입니다. 28개의 결정 문서를 11개의 심사 레그(Opus 8개, Sonnet 3개)에 할당하고, 판단 기준은 단 하나였습니다. 오늘 원문의 그대로 두 사람이 각각 '새 풀/신규 파일'을 작성했습니다.

• 두 종류의 주소형을 혼합하면 컴파일이 통하지 않는다.
• 레코더가 쓰기 기록을 하나 누락하면, 건수 게이트(件数ゲート)가 실패한다.
• 동일한 파라미터로 mkfs를 두 번 수행하면, 두 개의 이미지는 바이트 단위로 일치한다.
• 다섯 가지 쓰기 경로의 세그먼트 열이 E142의 출력과 완벽하게 일치하며, journal의 역방향 체인(back_chain)은 실험 출력의 back_chain=628216162와 완벽하게 일치한다. - 루트 슬롯, journal, 데이터 유닛, 시스템 구성을 파괴하는 여덟 개의 프로브의 결과가 각각 실험 출력과 하나씩 일치한다.
• 세그먼트 내 부분집합의 열거(列挙), 세 가지 판별기 등.

역방향 체인에 대해 한 말씀 더. 실험 장치와 crates/는 같은 조항에서 개별적으로 작성되었으며, 코드를 공유하지 않습니다. 양자가 동일한 양에 대해 같은 수에 도달한다는 것은 바이트표・조항・구현의 세 가지가 그 양에 대해 일치하고 있음을 의미합니다. 어느 한 곳이라도 틀리면 비교는 실패합니다.

아래 코드의 출처는 두 군데입니다. 실험 코드는 research/의 실험 장치 E77에서, 구현 코드는 crates/에서 가져왔습니다. 발췌본에서는 첫 번째 트랜잭션과 관계없는 줄을 잘라내고, // …로 표시했습니다.

mkfs 이후의 전체 쓰기 열은 세 가지 경로로 구성됩니다.

• 번호 획득: 인스턴스 세대 1을 각 디스크의 시스템 구성에 작성합니다. 두 번의 쓰기.
• 두 번의 워밍업(빈 발행): checkpoint_txg를 0 → 1 → 2로 진행합니다. 열 번의 쓰기.
• 본격적인 발행 txg 3: 21번의 쓰기. 8 유닛을 양쪽 디스크에 16회, journal 레코드 2회, 루트 슬롯 1회, 시스템 구성 2회.

워밍업은 D16의 결정 사항 8에서 왔습니다. 첫 마운트 시에는 이 인스턴스의 루트를 양쪽 디스크에 작성한 후 fsync를 반환합니다.

어떤 발행도 동일한 순서로 디스크에 기록됩니다.

유닛과 인덱스 노드(각 디스크에 일부씩)
→ 바리아
→ journal 레코드(각 디스크에 일부씩)
...

이 순서는 코드를 작성하기 전에 E77에서 측정되었습니다. 데이터의 완전성에 필요한 것은 루트 슬롯 앞의 바리아 하나만으로 충분하며, 레코드와 루트 슬롯 사이의 바리아는 레코드 열의 완전성을 유지하기 위한 것입니다.

번호 획득, 워밍업, 발행의 세 경로는 모두 하나의 폐쇄된 열거형(enum)을 통해서 디스크에 기록됩니다. 설계 규율은 '트랜잭션 계층은 하나이며 모든 구조에서 공유한다'로, fsync를 위해 다른 것을 만드는 것은 허용되지 않습니다.

구현 코드 crates/singlefs-core/src/transaction.rs

// 와일드카드 팔(腕)은 없다. 팔을 하나 빠뜨리면 컴파일이 통하지 않는다.
pub enum CommitStep<'publish> {
WriteUnitToEveryDevice { slot: SlotNumber, unit: &'publish [u8], identity: TransactionUnit },
...

복구는 자신이 생각하는 결말만을 보고할 뿐이며, 그것이 올바른지는 audit가 영속화 집합과 대조하여 재판단합니다. 감사하는 쪽과 감사받는 쪽은 같은 코드를 사용하지 않습니다. 이 규칙은 나중에 그대로 crates/에 도입되었습니다. 네 가지 바리아 배치 결과입니다.

상태 수의 폐쇄 형식(Closed Form)

각 세그먼트는 자신의 모든 진부분집합을 기여하고, 마지막에 '모두 영속화(all persist)' 하나를 더합니다.

상태 수 = 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회와, 두 번째 전원 가동(warm-up) 시 시스템 구성 슬롯 쓰기 2회 사이에는 배리어(barrier)가 없어 같은 세그먼트에 포함됩니다. $2^{18} = 262,144$입니다. 즉, 26만이라는 숫자는 본질적으로 18번의 쓰기로 이루어진 하나의 세그먼트의 거듭제곱 집합입니다. 상태 수는 세그먼트 길이에 대해 지수적으로 증가합니다.

이 숫자는 한 단계씩 늘어났습니다. E142의 첫 번째는 트랜잭션의 21번 쓰기만을 나열했고, 세그먼트 16+2+1+2로 65,543개의 상태였습니다. 네 번째는 전원 가동이 실제로 바이트를 쓰게 되면서 262,162개가 되었고, 여섯 번째는 번호 가져오기(number acquisition)의 두 번 쓰기가 최상위 세그먼트에 포함되면서 262,165개로 늘어났습니다.

풀 레벨의 checker(crates/singlefs-checker)가 구현과 공유하는 것은 포맷 상수 모듈뿐입니다. CRC-32C는 비트 단위로 다시 쓰며, 세 가지 종류의 슬롯과 유닛 분석도 각각 따로 작성했습니다. 런타임(runtime)과 checker가 같은 코드를 사용한다면 그것은 동일한 한 번의 계산이며, 검증(verification)의 의미는 그 자리에서 사라집니다.

checker는 스스로 역방향 체인(reverse chain)을 계산하고, CRC도 비트 단위 구현을 사용하며, 구현 측의 것은 사용하지 않습니다.

구현 코드 crates/singlefs-checker/src/lib.rs

/// 비트 단위의 CRC-32C (반사 다항식 0x82F63B78). 테이블을 참조하지 않고, 구현 측 것도 호출하지 않음.
pub fn crc32_castagnoli_bitwise(bytes: &[u8]) -> u32 {
const POLYNOMIAL_REFLECTED: u32 = 0x82F6_3B78;
...

진입점은 이미지를 하나만 받아 각 불변 조건(invariant condition)을

부하는 오직 '새 풀(New Pool) 및 신규 파일' 중 하나일 뿐입니다. 덮어쓰기, 해제 후 재사용, 다중 마운트, 롤백은 한 번도 리플레이에 포함되지 않았습니다.
모델은 배리어(barrier) 이전의 모든 쓰기는 영속화되었다고 가정합니다. FLUSH를 지키지 않는 디스크는 포함되어 있지 않습니다.
손상된 쓰기가 우연히 32비트 CRC32C를 속이는 것은 인지하고 받아들입니다.
사용되는 66개의 불변 조건 중, checker가 판정하는 것은 23개입니다.
이상 모델과의 기능 비교(대조)는 아직 없습니다.

이야기는 아직 길다. 봄, 여름, 가을, 겨울.