# Regolith 磁盘格式规范

本文档是 regolith 的权威磁盘格式说明，描述每一个落盘字节的布局与含义。
目标是让任何第三方实现（或未来的重写）只凭本文就能读写 regolith 的数据库文件。

约定：

- 所有多字节整数为**小端序**（least significant byte first）。
- `varint` 为无符号 LEB128 编码，每字节低 7 位为数据、最高位为继续位。
- 所有长度单位为字节，偏移量为相对文件开头的绝对偏移。
- 校验和计算失败、索引越界、magic 不匹配都视为**整表损坏**：该文件不可读，读操作返回 `DbError::Corrupt`，绝不静默返回错误数据。

## §1 文件集

一个数据库目录（或内存存储镜像）由以下文件组成：

| 文件名 | 内容 |
|---|---|
| `WAL` | 预写日志，组提交格式，见 §3 |
| `L0_%06d.sst` | 第 n 次 flush 产出的 L0 表（n 为 6 位十进制计数） |
| `L1_<S>_<G>.sst` | 非底层归并压缩产出的 L1 表：`<S>` 为表中最大序列号（含墓碑），`<G>` 为全局表计数器（会话内每写一张表递增），见 §6 |
| `L2_<S>_<G>.sst` | 底层归并压缩产出的 L2 表：`<S>` 为表中存活条目的最大序列号，`<G>` 同上 |

L0 表之间键区间任意重叠；L1、L2 各由**多张表**组成，键区间两两不相交，
在内存中按 S 降序维护（新表先查）。L1 是一次 L0→L1 归并（全部 L0 + 区间
重叠的 L1）的输出，L2 是一次 L1→L2 归并（最旧的 L1 表 + 所有区间重叠的
L1/L2 表）的输出；一次归并超过 `table_size_limit`（默认 2 MiB）时按键序
**拆分**为多张区间不相交的表，每张表的名字携带自己的 S（该片最大序列号）。

旧版本（0.3.x）的单表格式 `L1_<S>.sst` / `L2_<S>.sst`（无 G 段）按 `G = 0`
解析，向后兼容，恢复规则见 §7。

快照（`Snapshot`）是纯内存的一致性视图：不产生任何磁盘文件、不改变本节
的文件集，也不影响 §7 的恢复算法——进程退出后快照随之消失，恢复照常。

## §2 通用原语

### varint（无符号 LEB128）

非负整数编码为 1–10 字节序列。每个字节的 7 个低位携带数据（低 7 位在前），
最高位为 1 表示还有后续字节。解码器必须拒绝超过 10 字节的 varint
（防止恶意输入导致 64 位溢出）。

### CRC-32

CRC-32（IEEE 802.3），参数：

- 反射多项式 `0xEDB88320`
- 初始值 `0xFFFFFFFF`
- 结果异或 `0xFFFFFFFF`

即 `zlib.crc32` 的经典参数。所有校验和字段均为该 CRC 的小端 u32。

带种子的变体 `crc32(data, seed)`（初始值替换为 seed，结果异或不变）
被 bloom 过滤器用作键哈希，见 §5。

## §3 WAL 记录格式

WAL 文件是若干记录的连续拼接，每一条记录：

```
record  := len(varint) crc(payload, u32 LE) payload
payload := op(1B) seq(varint) kl(varint) key vl(varint) value
         | op(1B) seq(varint) n(varint) entry*
entry   := op(1B) kl(varint) key vl(varint) value
op      := 1 (put) | 2 (delete；vl 恒为 0) | 3 (batch)
```

- `len` 为 payload 长度（不含 4 字节 crc）。
- `crc` 为 `payload` 的 CRC-32。
- `op = 2` 时 `vl` 必须是 0（删除记录不携带值）；`op = 1` 且 `vl = 0` 是
  空值写入，不是删除。
- `seq` 为全局递增的序列号，全库唯一。
- `op = 3`（批量记录）：`seq` 为批内首条序列号，`n` 为批内条数，批内第 i
  条（i 从 0 起）的序列号为 `seq + i`。整批在一条记录内，恢复要么整批重放
  要么整批丢弃——批量写入的原子性由有效前缀截断规则直接给出。
- 单条记录 payload 里 `entry` 的 op 字段与顶层一致（1/2），`n < 1` 或批尾
  与 payload 长度不吻合视为非法。

**尾部截断容忍**：解析器从头顺序读取，遇到第一个 `len` 越界、crc 不匹配或
payload 非法（如 op 既非 1、2 也非 3）的记录即停止，把此前解析成功的记录视为
有效日志前缀——这是对"写入中途崩溃留下半条记录"的唯一正确处理方式。
有效前缀之后的字节在下次 flush 时被重写覆盖。

## §4 SSTable v3 与 v2

当前版本（0.5.x）写入 **v3** 表，并完整兼容读取 v1、v2 表（0.4.x 及更早
写入）。三种版本的区别仅在数据块编码与 magic：footer 布局、索引与 bloom
段完全一致，版本互读不需要任何转换。**禁止降级**：能写 v3 的版本不要回退
到 0.4.x 继续写入（旧版会把 v3 表当损坏文件处理）。

SSTable 由四段组成：

```
blocks* index bloom footer
```

### 数据块（v3：前缀共享 + 块内重启点）

```
v3 block  := entry* restarts
restarts  := off(u32 LE)* num_r(u32 LE)
v3 entry  := shared(varint) unshared(varint) tomb(varint) seq(varint)
             vl(varint) suffix(unshared) value(vl)
```

- 每条目与**同块内前一条目**共享键前缀：`shared` 为共享字节数，
  `unshared` 为后缀字节数，键 = `prev_key[0..shared) ++ suffix`。
- 每 `restart_interval`（默认 16）条是**重启点**：存完整键（`shared = 0`），
  其块内偏移记入 `restarts` 数组。块首条目恒为重启点（`num_r ≥ 1`）；
  每块的重建独立（块自包含），块边界处前缀共享归零。
- `restarts` 位于块尾：`num_r` 个 u32 LE 偏移 + 一个 u32 LE 计数（无块头
  count；条目区在 `num_r` 个偏移之前结束）。偏移必须严格递增、首偏移 = 0、
  全部落在条目区内；重启键必须严格升序且每键为完整键（`shared = 0`）。
- `tomb` / `seq` / `vl` 语义与 v2 相同（见下）。
- 键**严格升序**排列；块在 `block_size`（默认 4096 字节）边界附近封块。
  升序 = 逐字节字典序（`Bytes::lexical_compare`）。注意 `Bytes::compare` 是
  长度优先比较，混合长度键时两者不一致——全库键序（跳表、索引、合并
  迭代器）一律使用字典序。
- **块内查找**：对重启键二分（上界）定位候选重启点，再线性解码至多
  `restart_interval` 条。任意 `shared > 前键长度` 都是损坏（§8）。

### 数据块（v2：未压缩，兼容读取）

```
block := count(varint) entry*
entry := tomb(varint) seq(varint) kl(varint) key vl(varint) value
```

- `tomb`：0 = 存活值，1 = 墓碑（`vl` 恒为 0，读取为已删除）。
- `seq`：该写入的全局序列号。
- 键严格升序（同 v3）。0.4.x 及更早版本写入的表用本布局。

### 索引

```
index := m(varint) (kl(varint) last_key offset(varint))*
```

- `m` 为块数（≥1）。
- 每个块一条记录：块的最后一个键 + 块起始偏移。
- `last_key` 必须严格升序，`offset` 必须严格递增且指向各块头。

### Bloom 段

```
bloom := n(varint) m_bits(varint) bits
```

- `n` 为表中键的数量；`m_bits = 10 · n` 为过滤器位长；`bits` 为
  `ceil(m_bits / 8)` 字节的位图（低位先）。
- 键哈希与探测算法见 §5。
- `n = 0` 时 `m_bits = 0` 且无位图字节（空表）。

### Footer（30 字节）

```
footer := idx_off(u64 LE) bloom_off(u64 LE) crc(u32 LE) crc2(u32 LE) magic(6B)
```

- `idx_off`：索引段起始偏移；`bloom_off`：bloom 段起始偏移。
  约束 `idx_off < bloom_off ≤ len − 30`。
- `crc`：覆盖 `[0, bloom_off)` 全部内容——所有数据块、索引和 bloom 段。
- `crc2`：footer 自校验，magic 为 `"RGSST3"`（v3）或 `"RGSST2"`（v2）。
  - **v3**：覆盖 footer 除 crc2 字段外的全部 26 字节——两个偏移 + `crc` +
    6 字节 magic（"自排除"约定）。因此 magic 与数据字段共同受保护，
    任意字段或 magic 被翻转都会使 crc2 校验失败。
  - **v2**：覆盖 footer 前 20 字节（两个偏移 + `crc`），与 0.4.x 已发布
    文件一致。
- 两层校验和保证：**文件中任意一个字节被翻转，整表不可读**，
  读操作不可能返回静默损坏的数据。

### 未来格式拒绝

打开表时若 magic 不在已知集合内，但 crc2 校验通过（按 v2 或 v3 两种约定
均不匹配才判损坏），则该文件是**更新版本**写入的合法表：以
`DbError::Corrupt` 拒绝打开（而不是当损坏删除）——撕裂写入的随机尾部
恰好通过 crc2 的概率为 2⁻³²，删除反而会误删未来版本的数据。升级到新
版本后可正常打开。

## §5 Bloom 过滤器（LevelDB 式双哈希）

对每个键 `k`：

```
h₀    = crc32(k, 0xBC9F1D34)          // §2 的带种子 CRC
delta = rotl(h₀, 15)
```

第 `i` 个探测位（i = 0 … 6，共 k = 7 次）：

```
bit(i) = (h₀ + i · delta) mod m_bits     // 全程 32 位无符号回绕运算
```

写入时置位 7 个探测位；查询时 7 位全为 1 才判"可能存在"。
**任何一个探测位为 0 即权威否定**——该键必定不在表中，可跳过整表查找；
"可能存在"仅表示值得做真实查找。10 bit/键 × 7 探测的假阳性率约 0.8%。
v1 表没有 bloom 段，查询视其恒为"可能存在"（语义不变，仅少一次短路）。

## §6 文件名与序列号覆盖规则

每条写入（含删除）分配一个全局递增序列号 `seq`，全库唯一。

- L0 表：`L0_%06d.sst`，含一次 flush 时 memtable 的全部条目。
- L1 表：`L1_<S>_<G>.sst`，`S` 是表中**最大的序列号（含墓碑条目）**，即该
  表覆盖的写入水位线；`G` 是全局表计数器（会话内递增，恢复时 = 现存最大
  G + 1）。非底层归并**保留墓碑**：L2 中可能还有被删键的旧版本，墓碑必须
  继续压制它们。
- L2 表：`L2_<S>_<G>.sst`，`S` 是表中**存活条目**的最大序列号。底层归并
  **抑制墓碑**（它们所能覆盖的一切都在归并输入内），全为墓碑时产出为空、
  只删输入。
- 覆盖判定（恢复期，见 §7）：
  - **L1 keep-all**：L1 输出不吞并所有区间重叠的 L1 表，区间覆盖推断对
    L1 不健全——所有 CRC 有效的 L1 表全部保留，读路径按 S 降序命中，
    陈旧表在下次压缩触碰其区间时被回收。
  - **L2 区间并集覆盖**：L2 表 T 若其键区间被"若干张 S ≥ S_T 的 L2 表"的
    键区间**并集**完全覆盖，则丢弃（L2 归并恒吞并所有区间重叠的 L2，重叠
    必成输入链，并集覆盖 ⇒ 数据已归入覆盖表）。
  - **L0 区间并集覆盖**：L0 表 T 若其键区间被"若干张 S ≥ T 的 max_seq 的
    L1 表"的键区间并集完全覆盖，则丢弃（compact 恒合并全部 L0）。
  - **旧格式兼容**（无 G 段，G=0）：旧 L2 是全量归并——L0 表
    `max_seq ≤ S` 即被吸收；L1 表 `S ≤ S₂` 即被吸收；新格式表之间不适用。
- 输入删除顺序（崩溃窗口读正确的关键）：新表全部写完并校验后，按 **S 升序
  （旧表先删）** 删除输入；compact_l2 先删全部 L2 输入再删 L1 输入。任何
  崩溃前缀都把最新版本（含墓碑所在的表）留在盘上，读路径按 S 降序命中，
  无复活窗口。

## §7 恢复算法

打开数据库时按序执行：

1. 枚举全部 `*.sst` 文件，按 §1 解析文件名（新旧两种格式）；文件名非法
   或表内容 CRC 校验失败的文件删除（§8）。
2. L2：全部有效表载入后，逐表检查"键区间被其余 S ≥ S_T 的 L2 表的区间
   并集覆盖"——覆盖则丢弃（§6 论证）；不覆盖则保留，并记录存活旧格式 L2
   的最大 S（`legacy_l2_s`）。
3. L1：**keep-all**，全部有效表保留；仅旧格式 L1（G=0）在存在
   `legacy_l2_s ≥ S` 时丢弃（旧 L2 全量归并）。
4. L0：逐表检查"键区间被若干张 S ≥ 该表 max_seq 的 L1 表并集覆盖"，或
   存活旧格式 L2 满足 `max_seq ≤ legacy_l2_s`——覆盖则丢弃，否则保留。
5. WAL：解析有效前缀（§3）并**全量重放**进 memtable，不做任何跳过。
   多文件下全局水位线不健全（L2 的 S 可能来自不含某键的归并）；全量重放
   健全——磁盘 WAL 只可能是最后一次封存的记录（或 LostWrite 清盘残留的
   同一批），批内后写覆盖先写，每键必得最新版本，与表中一致。若截断了
   脏尾巴，立即把有效前缀写回 WAL 文件（自愈）。
6. `table_gen = 现存最大 G + 1`；`l0_counter = 现存最大 L0 序号 + 1`；
   `next_seq = max(所有存活表 S、存活 L0 max_seq、memtable max_seq) + 1`。

恢复后数据库状态恰好等于**某个操作前缀**执行完毕的结果
（"checkpoint ∪ 一段 WAL 前缀"），这正是崩溃安全的定义，见
[design.md §4](design.md#4-崩溃安全与恢复)。

## §8 损坏处理矩阵

| 位置 | 检测 | 后果 |
|---|---|---|
| WAL 记录 | 长度越界 / crc 不匹配 / payload 非法 | 记录及其后全部丢弃（视为未提交的截断尾巴） |
| SST 任意字节 | `crc` 或 `crc2` 不匹配 | 整表不可读，`DbError::Corrupt` |
| 索引结构 | 键序、偏移序、边界、magic | 同上 |
| v3 重启段 | 计数为 0 或超出块、偏移非严格递增 / 首偏移 ≠ 0 / 指向条目区外、重启键非严格升序或非完整键（shared ≠ 0） | 同上 |
| v3 条目 | `shared` 为负或超过前键长度、`unshared`/`vl` 越出条目区 | 同上 |
| SST 块内键序 | 游标逐条比较：当前键 ≤ 前键（重复或乱序） | `DbError::Corrupt`——CRC 查不出的语义损坏（如旧版本 bug 写入的重复键），读取即报错，压缩拒绝归并传播 |
| 未来格式表 | magic 未知但 crc2 校验通过（撕裂尾部巧合通过概率 2⁻³²） | 拒绝打开（`DbError::Corrupt`），文件**原样保留**待升级后读取 |
| 文件名 | 非法 SST 名 | 恢复期忽略（未来版本可扩展文件名族） |