🥮 mooncakes.io

    moonlsm

    Embedded LSM-tree storage engine for MoonBit

    lsm
    storage
    database
    embedded
    wal
    key-value
    Download zip
    Version
    0.3.2
    License
    MIT
    Repository
    Last updated
    8 days ago
    Downloads
    66

    No dependencies

    #PingGuoMiaoMiao/moonlsm

    MoonBit 生态里的嵌入式 LSM 存储引擎。

    社区项目，非 MoonBit 官方出品。

    MoonBit 现有的 KV 存储都是 Bitcask 风格（追加文件 + 全量内存索引），内存随数据线性增长，没有分层合并。moonlsm 补的是 LSM-tree（memtable + SSTable + compaction）这块空白。

    「嵌入式」指 embedded database —— 像 SQLite 那样链接进宿主进程， 不是跑在单片机 / MCU 上。它依赖 libc 与带 fsync 语义的文件系统。

    #状态

    可用。kill -9 不丢已确认的写入（crash_test.py --rounds 20 全 20 轮通过）， 215 条单元测试覆盖 WAL 截断恢复、MANIFEST 原子切换、三层归并、损坏注入。

    #设计

    put(k, v)
   ├─→ WAL（顺序追加，fsync 成功后才回 ack）
   └─→ MemTable（内存有序数组）
          └─ flush ─→ L0 SSTable（可重叠）
                        └─ 满 4 个 ─→ L1（不重叠）
                                        └─ 超 1 MiB ─→ L2（最底层，墓碑在这里丢弃）

    读路径：MemTable → L0 → L1 → L2，从新到旧命中即停，每层先查 Bloom filter 跳过无关文件。

    三条路径的关键性质：

    • 写：fsync 在返回 ack 之前，且 fsync 在改 MemTable 之前 —— 失败时写入完全不可见， 不会出现「读得到、断电就没」的脏读。
    • 读：命中第一个就返回，不比较 seq。所以内存里的文件顺序必须严格「新在前」， 由 MANIFEST 的版本快照唯一决定。
    • 归并：同一 key 取 seq 最大的一条（不是按文件顺序）。墓碑只在写进最底层时丢弃 —— 上层还有更旧版本时丢了会让数据复活。

    #示例

    let db = @moonlsm.Db::open(@moonlsm.NativeStorage::new("./data"), 8 * 1024 * 1024)

    let seq = db.put(b"key", b"value")   // 返回即代表已落盘（fsync 已成功）
    let v = db.get(b"key")               // Bytes?，删除也是 None
    let rows = db.scan(b"a", b"z", 100)  // [start, end)
    db.flush()                           // memtable -> L0，必要时触发归并
    db.close()

    这些调用会 raise，所以要放在 fn main raise { ... } 里，或者自己处理 LsmError。

    批量写走组提交，一批只 fsync 一次：

    for i in 0..<200 {
      db.put_deferred(key(i), value(i)) |> ignore
    }
    db.sync()                            // 返回即代表整批已落盘

    完整可跑的例子见仓库的 examples/basic/main.mbt。

    #性能（100 万条 · 每批 1000 · value 100 字节）

    指标数值
    顺序写55 658 ops/s
    随机写（覆盖写）12 699 ops/s
    读延迟 P50 / P990.053 / 0.111 ms
    范围扫描117 483 rows/s
    空间放大1.13×

    组提交让「每批一次 fsync」只比不同步慢 1.40×；把批次改成 1（每条都等 fsync） 则掉到 76 ops/s —— 39 倍差距。完整数据见仓库的 docs/engineering/BENCHMARK.md。

    #完整文档

    设计文档、能力矩阵、崩溃测试方案、路线图都在 GitHub 仓库：

    https://github.com/PingGuoMiaoMiao/moonlsm

    #License

    MIT

    Storage

    source
    pub trait Storage {
      fn prepare(Self) -> Unit raise LsmError
      fn read_file(Self, String) -> Bytes? raise LsmError
      fn write_file(Self, String, Bytes) -> Unit raise LsmError
      fn append_file(Self, String, Bytes) -> Unit raise LsmError
      fn append_frames(Self, String, Array[Bytes]) -> Unit raise LsmError
      fn sync_file(Self, String) -> Unit raise LsmError
      fn rename_file(Self, String, String) -> Unit raise LsmError
      fn remove_file(Self, String) -> Unit raise LsmError
      fn file_size(Self, String) -> Int? raise LsmError
      fn list_files(Self, String) -> Array[String] raise LsmError
    }

    存储后端抽象。

    引擎只依赖这个 trait，不直接碰任何 IO 原语。这不是为了「可插拔」这种 架构洁癖，而是为了两件具体的事：

    1. 崩溃契约可以测。C1「已确认的写入必不丢」要验证「fsync 之后 断电还在」，就必须能模拟断电。用真进程 + kill -9 只能测到「进程 死了数据还在」，测不出「忘了 fsync」——kill -9 不清 OS 页缓存。 MemStorage 维护「当前内容」和「已落盘内容」两份影子， power_loss() 回滚到后者，于是断电语义可以在 moon test 里 确定性地跑，还能在 wasm-gc / js 后端上跑。

    2. 平台差异被关在一处。fsync 在 POSIX 存在、Windows 没有 （只有 _commit）；ftruncate 同理。这两个符号名不同、 Windows 的 CRT 里根本没有 POSIX 那个名字，链接期就会失败。 差异全部收在 fs_native.mbt，核心逻辑一行平台判断都没有。

    所有名字都是相对路径，由后端自己决定根目录。

    LsmError

    source
    pub suberror LsmError {
      Io(String)
      Corruption(String)
      Closed
    }

    所有可能失败的地方都走这个错误类型。 关键原则：恢复路径上遇到坏数据要「降级」而不是 panic（ADR-0003 不变量 I3）。

    LsmError::closed

    source
    fn LsmError::closed() -> LsmError

    LsmError::corruption

    source
    fn LsmError::corruption(msg : String) -> LsmError

    LsmError::io

    source
    fn LsmError::io(msg : String) -> LsmError

    便捷构造。写 raise LsmError::io("...") 比 raise Io("...") 更明确， 跨包调用时也不用写 @moonlsm.Io(...) 这种看不出语义的形式。

    LsmError::message

    source
    fn LsmError::message(self : LsmError) -> String

    人类可读的错误描述。CLI 与日志用它，而不是自己 match 一遍—— 错误类型的构造器将来会增加，散落各处的 match 会漏。

    AppendHandle

    source
    type AppendHandle

    常开的追加句柄。只记 name 和 FILE*：模式永远是 "ab"， 因为只有追加路径需要它（见 NativeStorage::handle_for）。

    Block

    source
    pub struct Block {
      data : Bytes
      restarts : Array[Int]
      limit : Int
    }

    一个已编码的 block。持有原始字节，按需解码。

    Block::entries

    source
    fn Block::entries(self : Block) -> Array[Entry] raise LsmError

    解出全部条目（按 key 升序）。用于全扫描、校验和测试。

    生产读路径不该走这里 —— 它会把整个 block 解完。 单 key 查询请用 get。

    Block::first

    source
    fn Block::first(self : Block) -> Entry?

    第一条 entry。空 block 返回 None。

    与 seek(b"") 的区别：seek 要跑一次 restart_index_for 的二分， 而「第一条」根本不需要比较 —— 直接从第一个 restart 点解即可。

    Block::get

    source
    fn Block::get(self : Block, key : Bytes) -> Entry?

    按 key 精确查找。

    两步：先在 restart 数组上二分（找最后一个首 key ≤ 目标的 restart 点）， 再从那里线性扫到下一个 restart 点。最坏解 16 条 entry。

    返回墓碑条目（deleted = true）时不要当命中处理—— 调用方必须看 deleted 字段，否则删除会失效。

    Block::last

    source
    fn Block::last(self : Block) -> Entry?

    最后一条 entry。空 block 返回 None。

    用于「文件的最大 key」这个边界：index 里存的是每块的 last_key， 所以最后一个 index 条目的 key 就是整个文件的最大 key， 但要拿到它就得能取 block 的最后一条 —— seek 做不到这件事 （key 是任意二进制，没有「比所有 key 都大」的哨兵值可传）。

    Block::num_restarts

    source
    fn Block::num_restarts(self : Block) -> Int

    restart 点个数。

    Block::seek

    source
    fn Block::seek(self : Block, target : Bytes) -> Entry?

    下界查找：返回第一个 key >= target 的条目。

    这是 index block 需要的语义 —— 索引里存的是每个 data block 的 最大 key，找「第一个 ≥ 目标的 last_key」就等于找到「可能包含目标的块」。 也用于 scan 的起始定位。

    与 get 的区别只在终点判断：get 遇到更大的 key 就返回 None， seek 则把它返回出去。

    BlockBuilder

    source
    pub struct BlockBuilder {
      buf : 
    Buffer
      restarts : Array[Int]
      counter : Int
      last_key : Bytes
      count : Int
    }

    按 key 升序逐条追加，最后 finish() 出完整 block 字节。

    使用契约：add 的 key 必须严格升序。违反会直接抛 Corruption， 而不是静默写出一个坏 block —— 排序错了说明上层归并逻辑有 bug， 让它早点炸比让它写进磁盘好。

    BlockBuilder::add

    source
    fn BlockBuilder::add(self : BlockBuilder, entry : Entry) -> Unit raise LsmError

    追加一条。key 必须严格大于上一条。

    BlockBuilder::entry_count

    source
    fn BlockBuilder::entry_count(self : BlockBuilder) -> Int

    已追加的条目数。

    BlockBuilder::estimated_size

    source
    fn BlockBuilder::estimated_size(self : BlockBuilder) -> Int

    估算编码后的字节数（含 restart 数组、计数与 CRC），用于判断是否该切块。 估算而不是精确值：restart 数组长度依赖 counter，这里按当前状态算， 差几个字节不影响「是否超过 4 KiB」的判断。

    BlockBuilder::finish

    source
    fn BlockBuilder::finish(self : BlockBuilder) -> Bytes

    产出完整 block 字节（entry 区 + restart 数组 + 计数 + CRC）。

    每次调用都基于当前状态重新拼装，不修改 builder 自身， 所以可以在不 reset 的情况下多次调用（拿到的内容相同）。

    BlockBuilder::is_empty

    source
    fn BlockBuilder::is_empty(self : BlockBuilder) -> Bool

    是否一条都没写。

    BlockBuilder::last_key

    source
    fn BlockBuilder::last_key(self : BlockBuilder) -> Bytes

    最后一条的 key（也就是这个 block 的最大 key）。 SST 写索引时需要它作为 last_key；空 block 返回空 key。

    BlockBuilder::new

    source

    新建一个空 block。初始就带一个 restart 点 0， 保证第一个 entry 一定可以独立解码。

    BlockBuilder::reset

    source
    fn BlockBuilder::reset(self : BlockBuilder) -> Unit

    清空，复用同一个 builder 写下一个 block。

    BlockBuilder::should_finish

    source
    fn BlockBuilder::should_finish(self : BlockBuilder) -> Bool

    是否已经达到切块阈值。

    BloomFilter

    source
    pub struct BloomFilter {
      bits : Array[Byte]
      num_bits : Int
      k : Int
    }

    位图在内存里就是打包好的字节，与磁盘布局一一对应。 num_bits 单独存一份：末尾那个字节的高位可能没用满， 探测时只能落在 [0, num_bits) 内。

    BloomFilter::encode

    source
    fn BloomFilter::encode(self : BloomFilter) -> Bytes

    编码成格式规范 §3.3 的字节布局（v2）： k(1B) | num_bits(varint32) | bits[num_bits/8] | crc32c(4B)

    因为内存里已经是打包好的位图，这里只做整段拷贝， 不再逐位重排 —— 早先的实现每 8 个 bool 要跑一轮内层循环。

    尾部 CRC 是 v2 加的（ADR-0010）。理由不是「顺手统一」： filter 没有 CRC 时，一个坏掉的位图会让 may_contain 返回 false， 于是「数据明明在，却查不到」—— 这是唯一一种会主动丢数据的损坏方向， 比报错难查得多。fuzz 也证实了：加 CRC 之前，整个 filter 区域 80 个位置 全部漏检。

    BloomFilter::k

    source
    fn BloomFilter::k(self : BloomFilter) -> Int

    哈希个数。

    BloomFilter::may_contain

    source
    fn BloomFilter::may_contain(self : BloomFilter, key : Bytes) -> Bool

    返回 false 表示「一定不在」；返回 true 表示「可能在」。

    BloomFilter::may_contain_hashes

    source
    fn BloomFilter::may_contain_hashes(self : BloomFilter, h1 : UInt64, h2 : UInt64) -> Bool

    用预算好的哈希查询。一次点查探 N 个 SST 时，哈希只需算一次。

    BloomFilter::new

    source
    fn BloomFilter::new(expected : Int) -> BloomFilter

    expected 是预期元素个数，按默认参数（10 bit / 7 哈希）建 filter。

    BloomFilter::new_with

    source
    fn BloomFilter::new_with(expected : Int, bits_per_key : Int, k : Int) -> BloomFilter

    显式指定每个元素的位数与哈希个数。给调参和测试用。

    生产路径只用 new；new_with 存在的意义是让「为什么是 10 bit」 这个问题能用一组可复现的对照实验回答，而不是引用一句经验值。

    BloomFilter::num_bits

    source
    fn BloomFilter::num_bits(self : BloomFilter) -> Int

    位图总位数。给调参与统计用 —— 它决定了 filter 的空间开销。

    BloomFilter::popcount

    source
    fn BloomFilter::popcount(self : BloomFilter) -> Int

    已置位的 bit 数。只用于测试与统计。

    BloomFilter::put

    source
    fn BloomFilter::put(self : BloomFilter, key : Bytes) -> Unit

    BloomFilter::put_hashes

    source
    fn BloomFilter::put_hashes(self : BloomFilter, h1 : UInt64, h2 : UInt64) -> Unit

    用预算好的哈希写入。与 put 等价，省一次哈希。
    pub struct Db[S] {
      storage : S
      mem : MemTable
      ssts : Array[LoadedSst]
      mem_limit : Int
      seq : UInt64
      flush_count : Int
      version : Version
      current_manifest : String
      sync_on_write : Bool
      pending : Array[Bytes]
      wal_bytes : Int
      closed : Bool
    }

    M2 阶段的数据库：WAL + memtable + 若干 SST，全部通过 Storage 落盘。

    写入顺序（这个顺序是崩溃契约 C1 的全部内容）：

    分配 seq → 追加 WAL 帧 → fsync WAL → 写 memtable → 可能刷盘

    三个关键点：

    1. 先 WAL 后 memtable。反过来的话，进程在两者之间死掉， 内存里的数据会消失而 WAL 里没有记录，重启后这条写入凭空消失。
    2. fsync 成功之后才能对外返回 seq。fsync 失败就抛错， 调用方拿不到 ack，也就不会认为写成功了。
    3. 刷盘时先让 SST 落盘，再清 WAL。中间崩溃只会导致 WAL 被重放一次， 而重放是幂等的（同样的 seq、同样的值），不会产生错误结果。

    读路径的新旧顺序：memtable → ssts[0] → ssts[1] → … 越靠前越新。注意这只是短路优化的依据，正确性依据永远是 seq —— 归并时用 seq 判断新旧，而不是数组下标。

    写入 API 分成两组，对应两种 fsync 粒度：

    • put / delete：写 + fsync，返回即持久。适合单条写。
    • put_deferred / delete_deferred + sync：批量追加后一次 fsync。 适合 putmany，把 N 次刷盘压成 1 次（组提交）。

    两组都满足 C1：ack 发出之前 fsync 一定已经成功。区别只在 「一批里 fsync 几次」，不在「要不要 fsync」。

    但两组的失败可见性不同，这是批量的固有代价： put 把 fsync 放在改 memtable 之前，失败时写入完全不可见； put_deferred 做不到（写第一条时还不知道最后的 sync 会不会成功）， 所以 sync 失败时那批数据会留在内存里可读、但没有 ack、断电必丢。

    Db::check_version_invariants

    source
    fn[S] Db::check_version_invariants(self : Db[S]) -> Bool

    版本快照是否满足全部语义不变量。测试用它确认归并之后 L1 仍不重叠。

    Db::close

    source
    fn[S] Db::close(self : Db[S]) -> Unit

    关闭。v1 不保持常开句柄，所以这里只标记状态； 关闭之后任何读写都抛 Closed，而不是静默继续用。

    Db::compact_l0

    source
    fn[S : Storage] Db::compact_l0(self : Db[S]) -> Unit raise LsmError

    把 L0 全部 + 与 L0 范围重叠的 L1 文件，归并成新的 L1。

    保留这个名字是因为它是最常用的入口（测试也直接调它）。

    Db::compact_level

    source
    fn[S : Storage] Db::compact_level(self : Db[S], src : Int) -> Unit raise LsmError

    把第 src 层的全部文件，连同第 src + 1 层里与之范围重叠的文件， 归并成新的 src + 1 层文件。

    顺序（每一步的崩溃点都有明确恢复路径）：

    1. 算出 src 层覆盖的 key 范围，找出 dst 层里与之重叠的文件
2. 读入全部输入条目 → 归并（同 key 取 seq 最大）→ 到最底层时丢墓碑
3. 按大小切成若干 SST，逐个写盘 + fsync
4. 更新 version：src 清空、dst = 未参与的文件 + 新文件
5. persist_version()   ← 原子点
6. 删除输入文件
7. 重建内存里的 ssts 视图

    5 之前崩溃：CURRENT 仍指向旧 MANIFEST，输入文件都还在 → 数据完好， 新写的 SST 是孤儿（bump_file_number_past_existing 会跳过它们的编号）。 5 之后崩溃：新 MANIFEST 只引用新文件，输入文件成了垃圾， 但它们不影响恢复，下次启动会被忽略（后续可加孤儿清理）。

    第 6 步必须在第 5 步之后。 提前删输入文件的话，一旦 5 失败， 旧 MANIFEST 引用的文件已经没了 —— 数据库直接打不开。

    Db::delete

    source
    fn[S : Storage] Db::delete(self : Db[S], key : Bytes) -> UInt64 raise LsmError

    删。写墓碑，不是移除条目。

    与 put 一样，fsync 在 memtable 之前：删失败时旧值必须仍然可读， 而不是「删了一半」。

    Db::delete_deferred

    source
    fn[S : Storage] Db::delete_deferred(self : Db[S], key : Bytes) -> UInt64 raise LsmError

    删，但不 fsync。与 put_deferred 对称，同样要配合 sync() 使用。

    Db::flush

    source
    fn[S : Storage] Db::flush(self : Db[S]) -> Unit raise LsmError

    把 memtable 刷成一个 SST，并推进版本。

    这是整个引擎里唯一会改 MANIFEST 的地方，也是唯一依赖 文件系统 rename 原子性的地方。顺序一步都不能换：

    1. 写 sst/<n>.sst → fsync        （数据先变成持久事实）
2. 建 wal/<m>.wal 空文件 → fsync  （新 WAL 必须存在才能被 MANIFEST 引用）
3. 更新 version（L0 加一项、log_number=m、last_seq）
4. persist_version()             （写 MANIFEST + 原子切换 CURRENT）
5. 删旧 WAL                      （CURRENT 已经不再指向它）
6. 清 memtable / pending

    崩溃点分析：
    • 1 之前/之中崩：MANIFEST 仍指旧 WAL，旧 WAL 里有全部记录 → 重放能恢复； 半截的 SST 是孤儿，没人引用
    • 1 之后、4 之前崩：同上，SST 是孤儿
    • 4 之后崩：CURRENT 指向新 MANIFEST，它引用的 SST 已 fsync、 新 WAL 也已存在 → 恢复成功；旧 WAL 是垃圾，下次启动会被清掉
    • 5 之后崩：与 4 之后等价

    memtable 只能在 4 成功之后清空。 提前清空的话， 「SST 写好了但 MANIFEST 没写」这种状态下崩溃，重启后 SST 无人引用， 数据就真丢了。

    Db::flush_count

    source
    fn[S] Db::flush_count(self : Db[S]) -> Int

    Db::get

    source
    fn[S] Db::get(self : Db[S], key : Bytes) -> Bytes?

    读。返回 None 表示「不存在」或「已删除」—— 对使用者来说这两种没有区别，墓碑是实现细节。

    Db::last_seq

    source
    fn[S] Db::last_seq(self : Db[S]) -> UInt64

    当前最大 seq。每次写入自增，跨 memtable 与 SST 全局单调。

    Db::level_count

    source
    fn[S] Db::level_count(self : Db[S]) -> Int

    版本快照里有几层。

    Db::level_sst_count

    source
    fn[S] Db::level_sst_count(self : Db[S], idx : Int) -> Int

    某一层有几个 SST。层不存在返回 0。

    Db::manifest_name

    source
    fn[S] Db::manifest_name(self : Db[S]) -> String

    当前 MANIFEST 的名字（MANIFEST-000007）。空串表示还没写过。

    Db::maybe_compact

    source
    fn[S : Storage] Db::maybe_compact(self : Db[S]) -> Unit raise LsmError

    检查每一层，该归并就归并。在 flush 末尾调用。

    顺序是从上往下：先把 L0 并进 L1，再判断 L1 是不是又满了。 反过来（先看 L1）会让刚被 L0 推下来的数据多等一轮 flush 才下沉。

    Db::mem_entry_count

    source
    fn[S] Db::mem_entry_count(self : Db[S]) -> Int

    memtable 里的条目数（含墓碑）。stats 命令用它区分 「内存里有多少条」和「已经刷到 SST 的有多少条」。

    Db::next_file_number

    source
    fn[S] Db::next_file_number(self : Db[S]) -> UInt64

    版本快照里的 next_file_number。测试用它验证「编号不复用」。

    Db::open

    source
    fn[S : Storage] Db::open(storage : S, mem_limit : Int) -> Db[S] raise LsmError

    打开（或新建）数据库。mem_limit 是 memtable 的字节阈值。

    每次都立刻 fsync。要关掉它（只用于压测）用 Db::open_with。

    Db::open_with

    source
    fn[S : Storage] Db::open_with(storage : S, mem_limit : Int, sync_on_write : Bool) -> Db[S] raise LsmError

    同 Db::open，但可以关掉每次写入的 fsync。

    sync_on_write = false 时崩溃会丢已确认的数据，只应该用于 性能对比实验。所有正确性测试都必须用 true。

    Db::put

    source
    fn[S : Storage] Db::put(self : Db[S], key : Bytes, value : Bytes) -> UInt64 raise LsmError

    写。返回本次写入的 seq —— 返回即代表已持久（sync_on_write = true 时）。

    顺序是 追加帧 → fsync → 改 memtable，fsync 在 memtable 之前。 这不是随手写的：fsync 失败时这条写入必须「完全不可见」， 否则会出现「读得到、但断电就消失」的脏读 —— 比直接报错严重得多。

    Db::put_deferred

    source
    fn[S : Storage] Db::put_deferred(self : Db[S], key : Bytes, value : Bytes) -> UInt64 raise LsmError

    写，但不 fsync。返回的 seq 不代表已持久。

    这是组提交（group commit）的一半。另一半是 sync()。

    为什么需要它：putmany 一批 200 条，如果每条都 fsync， 在 Windows 的 _commit 上就是 200 次真实刷盘（实测约 2.3 秒一批）。 而契约 C1 只要求「返回 ack 之前 fsync 成功」，从没要求每条一次。 正确用法：

    for item in batch { db.put_deferred(k, v) }   // 只追加，不刷盘
db.sync()                                     // 一次刷盘
// ← 到这里才能返回 ok

    安全性说明：中途如果 memtable 满了触发 flush，flush 会把 SST 落盘 并清空 WAL —— 那批数据已经通过 SST 持久化，不会因为「还没 sync」而丢。

    与 put 的可见性差异（有意为之）：这里没法在写第一条时预知 后面的 sync() 会不会成功，所以条目先进 memtable。万一 sync() 失败， 这批数据会留在内存里可读，但没有 ack、断电必丢。 调用方拿到错误后应当丢弃这批数据并重新打开数据库，不要继续读。 单条写没有这个问题 —— put 把 fsync 放在 memtable 之前。

    Db::scan

    source
    fn[S] Db::scan(self : Db[S], start : Bytes, end : Bytes, limit : Int) -> Array[KvPair] raise LsmError

    范围扫描。start 闭、end 开（[start, end)），最多 limit 条。

    用左闭右开而不是双闭：双闭无法表达「扫到最大 key 之后」， 调用方得造一个「比所有 key 都大」的哨兵值，而 key 是任意二进制， 没有这样的哨兵。

    来源是惰性推进的（ADR-0011）：memtable 从 lower_bound(start) 起走， 每个 SST 开一个块级游标。limit 一到就停，没被用到的块根本没被解出来。 之前这里是「先把每个来源的整个区间读成数组，再归并」，于是 「要 10 条」和「要 10 万条」付同样的解码成本。

    Db::sst_count

    source
    fn[S] Db::sst_count(self : Db[S]) -> Int

    Db::sync

    source
    fn[S : Storage] Db::sync(self : Db[S]) -> Unit raise LsmError

    把 WAL 刷到稳定存储。这是 C1 的最后一道闸门。

    先把 put_deferred 攒下的帧一次性写出去（一次 fopen），再 fsync。 失败一律抛出：fsync 没成功就不能让调用方以为写成功了。

    没有待写帧时调用它是安全的（代价 = 一次 fsync）。

    Db::wal_bytes

    source
    fn[S] Db::wal_bytes(self : Db[S]) -> Int

    当前 WAL 文件字节数（含文件头）。stats 命令用它。

    Db::wal_name

    source
    fn[S] Db::wal_name(self : Db[S]) -> String

    当前活跃 WAL 的路径（wal/000008.wal）。

    Entry

    source
    pub struct Entry {
      key : Bytes
      value : Bytes
      seq : UInt64
      deleted : Bool
    }

    一条内部记录。seq 是全局单调递增序号， 用于判断同一 key 的新旧（越大越新）。

    deleted 是墓碑标记。不能用「value 长度为 0」表示删除 —— 那样就无法区分「写入了空字符串」和「删除了这个 key」， 是 LSM 实现里最常见的一个静默数据错误。 对应磁盘格式里 data block 每条记录前的 1 字节 type（见 format.md §3.2）。

    Entry::to_pair

    source
    fn Entry::to_pair(self : Entry) -> KvPair

    把内部条目转成对外键值。 调用方必须先过滤掉 deleted = true 的条目，否则墓碑会泄漏出去。

    KvPair

    source
    pub struct KvPair {
      key : Bytes
      value : Bytes
    }

    对外返回的一条键值。scan 的返回单元。

    与 Entry 的区别：没有 seq、没有 deleted —— 对外部使用者来说 多版本和墓碑都是实现细节，不该暴露。

    KvPair::new

    source
    fn KvPair::new(key : Bytes, value : Bytes) -> KvPair

    直接构造一条键值。

    跨包不能写结构体字面量（KvPair 是只读类型），而 CLI 的 JSON 拼装、 下游的单元测试都需要「凭空造一条」的能力。Entry::to_pair 不够用： 它要求先有一个 Entry，而 Entry 带 seq 和墓碑标记， 对使用者来说是多余的。

    LoadedSst

    source
    pub struct LoadedSst {
      num : UInt64
      reader : SstReader
    }

    一个已加载的 SST。编号来自文件名，reader 是解析后的内容。

    之所以不只用 SstReader：compaction 要把「被归并掉的文件」从内存视图里 摘掉，而 SstReader 本身不记得自己叫什么。

    MemStorage

    source
    pub struct MemStorage {
      files : Map[String, Bytes]
      durable : Map[String, Bytes]
      syncs : Int
      fail_sync : Bool
      fail_write : Bool
    }

    内存后端。

    两份影子：files 是「当前内容」（含尚未落盘的），durable 是 「已 fsync 的内容」。正常读写只看 files；power_loss() 把 files 回滚到 durable，于是「断电」变成一次确定性的内存操作。

    这个模型刻意比真磁盘更严格：真磁盘上未 fsync 的页可能会幸存 （OS 迟早会写下去），也可能不会。这里一律当作「不会」， 也就是只允许更悲观的崩溃。测试因此不会假阳性。

    MemStorage::append_file

    source
    fn MemStorage::append_file(self : MemStorage, name : String, data : Bytes) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::append_frames

    source
    fn MemStorage::append_frames(self : MemStorage, name : String, chunks : Array[Bytes]) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::file_size

    source
    fn MemStorage::file_size(self : MemStorage, name : String) -> Int? raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::list_files

    source
    fn MemStorage::list_files(self : MemStorage, dir : String) -> Array[String] raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::names

    source
    fn MemStorage::names(self : MemStorage) -> Array[String]

    当前所有文件名，测试断言用。

    MemStorage::new

    source
    fn MemStorage::new() -> MemStorage

    MemStorage::plant

    source
    fn MemStorage::plant(self : MemStorage, name : String, data : Bytes) -> Unit

    直接设定「磁盘上已有的内容」，同时写进两份影子。

    用于构造恢复场景：手工摆出「WAL 尾部有半条记录」「MANIFEST 指向 不存在的 SST」这类状态，比用引擎自己写出这种状态可靠得多。

    MemStorage::plant_durable

    source
    fn MemStorage::plant_durable(self : MemStorage, name : String, data : Bytes) -> Unit

    只改「已落盘内容」，不动当前视图。用于构造「磁盘上有一份旧数据， 而当前视图是新的」这种不一致状态。

    MemStorage::power_loss

    source
    fn MemStorage::power_loss(self : MemStorage) -> Unit

    模拟断电：所有未 sync 的改动消失，已 sync 的回到 sync 时的样子。

    注意顺序：先删掉「只在 files 里、durable 里没有」的文件（写了一半 就断电，文件本身都不该存在），再把 durable 的内容覆盖回去。

    MemStorage::prepare

    source
    fn MemStorage::prepare(_self : MemStorage) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::read_file

    source
    fn MemStorage::read_file(self : MemStorage, name : String) -> Bytes? raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::remove_file

    source
    fn MemStorage::remove_file(self : MemStorage, name : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::rename_file

    source
    fn MemStorage::rename_file(self : MemStorage, from : String, to : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::set_fail_sync

    source
    fn MemStorage::set_fail_sync(self : MemStorage, v : Bool) -> Unit

    让下一次 sync_file 失败。用来测「fsync 失败时不能对外确认」。

    MemStorage::set_fail_write

    source
    fn MemStorage::set_fail_write(self : MemStorage, v : Bool) -> Unit

    让下一次 append_file / write_file 失败。

    MemStorage::sync_file

    source
    fn MemStorage::sync_file(self : MemStorage, name : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemStorage::syncs

    source
    fn MemStorage::syncs(self : MemStorage) -> Int

    已经发生的 sync_file 次数。用来断言「批量写只 sync 一次」这类行为。

    MemStorage::write_file

    source
    fn MemStorage::write_file(self : MemStorage, name : String, data : Bytes) -> Unit raise LsmError

    显式声明「trait 方法同时作为 MemStorage 的普通方法可用」。

    不写这行的后果（新版工具链）：[0079] implicit_impl_as_method —— impl 里的方法被隐式提升为类型自身的普通方法，这个隐式行为已废弃。 本地 0.1.20260827 没有这条检查，所以本地零警告、CI 全红。

    MemTable

    source
    pub struct MemTable {
      entries : Array[Entry]
      bytes : Int
      limit : Int
    }

    内存写缓冲。当前用「有序数组 + 二分」，够跑通全部正确性测试。 Week 3 若性能不够，再换成跳表（接口不变）。

    MemTable::apply

    source
    fn MemTable::apply(self : MemTable, rec : WalRecord) -> Unit

    重放一条 WAL 记录。恢复路径的唯一入口。

    MemTable::clear

    source
    fn MemTable::clear(self : MemTable) -> Unit

    清空。只在 flush 成功后调用 —— 先落盘、再清空，顺序反了就是丢数据。

    MemTable::delete

    source
    fn MemTable::delete(self : MemTable, key : Bytes, seq : UInt64) -> Unit

    删除的便捷形式。写一条墓碑，不真的移除条目 —— 真的移除会让更底层的旧值「复活」。

    MemTable::get

    source
    fn MemTable::get(self : MemTable, key : Bytes) -> Entry?

    读。返回 None 表示这个 memtable 里没有（不代表全局没有）。

    MemTable::insert

    source
    fn MemTable::insert(self : MemTable, entry : Entry) -> Unit

    插入一条已构造好的条目（可能是墓碑）。 WAL 重放走这条路径：mt.insert(rec.to_entry())。

    同一个 key 后写的覆盖先写的。这里不做 seq 比较 —— 调用方必须保证按 seq 升序插入（WAL 是追加写，天然有序）。

    MemTable::is_full

    source
    fn MemTable::is_full(self : MemTable) -> Bool

    是否该刷盘了。

    MemTable::new

    source
    fn MemTable::new(limit : Int) -> MemTable

    MemTable::put

    source
    fn MemTable::put(self : MemTable, key : Bytes, value : Bytes, seq : UInt64) -> Unit

    写入的便捷形式。走 Op::Put 而不是直接构造 Entry： 所有写入都经过「外部意图 → 内部条目」这一层转换， 墓碑语义只在 Op::to_entry 一处定义，不会出现两个地方各写一套。

    MemTable::to_entries

    source
    fn MemTable::to_entries(self : MemTable) -> Array[Entry]

    按 key 升序导出，供刷盘和归并迭代使用。

    MergeIterator

    source
    pub struct MergeIterator {
      sources : Array[Source]
    }

    k 路归并迭代器。

    LSM 的读路径本质上是「把 N 个各自有序的来源合成一个有序流」。 这里有三个必须同时满足的语义，任何一个错了都会产生静默数据错误：

    1. 同一个 key 只输出一次，取 seq 最大的那条（新覆盖旧）。 只按来源顺序取（sources[0] 优先）在 compaction 之后就错了 —— L1 的文件编号和 seq 顺序没有保证关系。
    2. 墓碑必须参与归并，但不能出现在结果里。 如果直接丢掉墓碑，底下那层 SST 里的旧值就会「复活」。 正确做法是：先让墓碑赢下归并（压掉旧值），再由上层把它过滤掉。
    3. 输出严格按 key 升序，否则上层的 scan 顺序和 SST 写入的 「key 严格升序」前提都会崩。

    实现是 O(k) 扫描每个 key（k = 来源数）。k 通常是个位数 （memtable + 几个 SST），堆优化的收益不值得多一层复杂度。

    来源是惰性推进的（ADR-0011）：归并器只看每个来源的「当前头部」， 不假设它们已经全在内存里。这让 Db::scan 的 limit 第一次真正生效 —— 取够 N 条就停，后面那些块根本没被解出来。

    MergeIterator::collect

    source
    fn MergeIterator::collect(self : MergeIterator) -> Array[Entry]

    把归并结果全部取出（含墓碑）。测试与 compaction 用。

    MergeIterator::new

    source
    fn MergeIterator::new(sources : Array[Array[Entry]]) -> MergeIterator

    用「已经全在内存里的有序数组」构造归并器。compaction 与测试走这条。

    数组的先后顺序只用于「seq 相同时取谁」这种异常情况的兜底， 不参与新旧判断 —— 新旧一律由 seq 决定。

    MergeIterator::next

    source
    fn MergeIterator::next(self : MergeIterator) -> Entry?

    取下一个 key 的最新版本。

    返回的可能是墓碑（deleted = true）。这是故意的： 调用方需要知道「这个 key 在这里被删了」，才能正确地压制更底层的旧值。 面向用户的 scan 必须自己过滤墓碑，Db::scan 就是这么做的。

    NativeStorage

    source
    pub struct NativeStorage {
      root : String
      handle : AppendHandle?
    }

    文件系统后端。

    追加路径保持一个常开句柄（ADR-0009）。同场 A/B：单条 put 56–64 → 384–399 ops/s（约 6.3×）。

    成本在「每条写开关两次文件」上：这台机器上 fopen+写+fclose 要 7.10 ms， fopen+fsync+fclose 要 1.62 ms，两步连起来 9.97 ms（500 次 × 3 轮中位数）。 常开句柄把两次开关压成零，只剩「同一个句柄上 fflush + fsync」的 2.03 ms。

    只缓存一个句柄，不做句柄表：
    • 写路径上真正反复打开的只有活跃 WAL；SST / MANIFEST 是一次成型文件， 缓存它们只是增加「什么时候失效」的状态。
    • 一个句柄的失效规则简单到可以逐条列出来（write_file / rename_file / remove_file 全部先关），不会出现「表里某个条目忘了失效」的漏洞。

    失效是无条件的，不判断文件名是否相同：这三个操作都很少发生， 多关一次的代价只是一次 fopen，而漏关一次的代价是 Windows 上 「删不掉 / 改不了名」——那种 bug 只在特定平台特定顺序下出现。

    语义没有任何变化：append_* 仍然不隐含 fsync，sync_file 仍然是 C1 的唯一实现点。fflush 在每次追加后立刻调用，所以「另开句柄读」 看到的仍然是已写入的全部字节。

    NativeStorage::append_file

    source
    fn NativeStorage::append_file(self : NativeStorage, name : String, data : Bytes) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::append_frames

    source
    fn NativeStorage::append_frames(self : NativeStorage, name : String, chunks : Array[Bytes]) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::close

    source
    fn NativeStorage::close(self : NativeStorage) -> Unit

    关掉常开句柄。没有缓存时是空操作。

    调用时机由内部逻辑决定（写覆盖 / 改名 / 删除前）；外部只在 「确定不再写这个目录」时调用，比如测试收尾、进程退出前。 不调用也不会丢数据 —— 未 fsync 的数据在 OS 页缓存里， 而句柄本身由 OS 在进程退出时回收。

    NativeStorage::file_size

    source
    fn NativeStorage::file_size(self : NativeStorage, name : String) -> Int? raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::list_files

    source
    fn NativeStorage::list_files(self : NativeStorage, dir : String) -> Array[String] raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::new

    source
    fn NativeStorage::new(root : String) -> NativeStorage

    root 是数据目录。传空串表示当前目录。 所有文件路径都是 root + "/" + name，Windows 也接受 / 作为分隔符。

    NativeStorage::prepare

    source
    fn NativeStorage::prepare(self : NativeStorage) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::read_file

    source
    fn NativeStorage::read_file(self : NativeStorage, name : String) -> Bytes? raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::remove_file

    source
    fn NativeStorage::remove_file(self : NativeStorage, name : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::rename_file

    source
    fn NativeStorage::rename_file(self : NativeStorage, from : String, to : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::root

    source
    fn NativeStorage::root(self : NativeStorage) -> String

    数据目录路径，测试和错误信息里要用。

    NativeStorage::sync_file

    source
    fn NativeStorage::sync_file(self : NativeStorage, name : String) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。

    NativeStorage::write_file

    source
    fn NativeStorage::write_file(self : NativeStorage, name : String, data : Bytes) -> Unit raise LsmError

    显式声明「trait 方法同时作为 NativeStorage 的普通方法可用」。 理由见 storage.mbt 里 MemStorage 那处同样的声明。
    pub enum Op {
      Put(Bytes, Bytes)
      Delete(Bytes)
    }

    写入操作。删除不是「移除」，而是写一条墓碑。

    Op::to_entry

    source
    fn Op::to_entry(self : Op, seq : UInt64) -> Entry

    把一条写入操作转成 memtable 条目。 Delete 生成的条目 value 为空，且 deleted = true。

    Source

    source
    type Source

    归并的一个来源。

    两种构造器对应两种真实来源，差别在于数据在哪里：

    • FromArray：已经全在内存里、且已按 key 升序排好（memtable 的有序数组、 compaction 的输入）。取一条就是一次数组下标。
    • FromSst：在磁盘文件的内存副本里，按块惰性解码。取一条可能要解一块。

    之所以要这层抽象，是因为 Db::scan 带 limit：要 10 条时， 不该把整个区间的条目都解出来。而「只取需要的」这件事必须发生在来源一侧 —— 归并层无法提前知道哪条会进前 10。

    SstFooter

    source
    pub struct SstFooter {
      filter_offset : Int
      filter_size : Int
      index_offset : Int
      index_size : Int
      smallest_seq : UInt64
      version : Int
    }

    解析出来的 footer。

    SstMeta

    source
    pub struct SstMeta {
      number : UInt64
      file_size : UInt64
      smallest : Bytes
      largest : Bytes
    }

    一个 SST 的元信息。不含内容——内容在 sst/<n>.sst 里。

    smallest / largest 是这一层做「要不要读这个文件」判断的依据： 没有它们就只能打开每个文件问一遍，读放大会变成 O(文件数)。

    SstMeta::new

    source
    fn SstMeta::new(number : UInt64, file_size : UInt64, smallest : Bytes, largest : Bytes) -> SstMeta

    SstReader

    source
    pub struct SstReader {
      data : Bytes
      footer : SstFooter
      index : Block
      bloom : BloomFilter
      range : (Bytes, Bytes)?
    }

    一个已打开的 SST。持有整个文件字节与解析好的 index / filter。

    SstReader::block_count

    source
    fn SstReader::block_count(self : SstReader) -> Int raise LsmError

    data block 个数（等于索引条目数）。

    SstReader::entries

    source
    fn SstReader::entries(self : SstReader) -> Array[Entry] raise LsmError

    按 key 顺序解出全部条目。用于全扫描、校验与测试。

    SstReader::footer

    source
    fn SstReader::footer(self : SstReader) -> SstFooter

    SstReader::get

    source
    fn SstReader::get(self : SstReader, key : Bytes) -> Entry?

    按 key 查找。命中墓碑时返回 deleted = true 的条目， 调用方必须自己判断（上层要知道「这里有一个删除」，而不是「查不到」）。

    三步：bloom 快速否定 → index 定位 block → block 内二分。

    SstReader::get_hashed

    source
    fn SstReader::get_hashed(self : SstReader, key : Bytes, h1 : UInt64, h2 : UInt64) -> Entry?

    同 get，但复用调用方算好的双哈希。

    一次点查要探 N 个 SST 的 filter，用的是同一条 key —— 让每个文件各算一遍 FNV 是纯浪费。N 个文件时哈希成本从 N 次降到 1 次。

    SstReader::scan_range

    source
    fn SstReader::scan_range(self : SstReader, start : Bytes, end : Bytes) -> Array[Entry] raise LsmError

    只解出 [start, end) 区间里的条目，顺序与 entries() 一致。

    这是 scan 的性能关键。 entries() 会把整个文件解出来 —— 一个 1 MiB 的 SST 大约 1 万条，扫 500 条也要付 1 万条的解码成本。 数据量一大，scan 就退化成 O(整个库)，而调用方往往只要一小段。

    做法是拿索引做块级剪枝：索引里每条记录的是该 block 的 last_key， 于是

    • 二分找到第一个 last_key >= start 的 block —— 它之前的所有 block 最大 key 都小于 start，整块可以跳过
    • 往后逐块解，块内逐条过滤（只有首尾两块可能部分越界）
    • 遇到 last_key >= end 的 block，解完它就停 —— block 之间按 key 严格递增，后面每一块的 first_key 都更大，必然全部越界

    块内过滤而不是块内二分：一个 block 只有 4 KiB / 一百多条， 解出来再线性筛比再写一套「块内定位 + 向后遍历」简单得多， 而且这部分成本与块大小同阶，不是瓶颈。

    不接 limit：单看一个文件，无法判断「前 N 条」是不是全局的前 N 条 （多路归并要跨文件比较）。限制由调用方在归并之后施加。

    SstWriter

    source
    pub struct SstWriter {
      out : 
    Buffer
      block : BlockBuilder
      index : BlockBuilder
      count : Int
      block_count : Int
      smallest_seq : UInt64
      keys : Array[Bytes]
      version : Int
    }

    逐条追加、最后 finish() 出整个 SST 字节。

    使用契约：add 的 key 必须严格升序（与 BlockBuilder 一致）。 SST 内部按 key 有序，这是「二分查 index」和「归并 compaction」的前提。

    已知取舍：keys 把所有 key 留在内存里，因为 bloom 需要在 finish 时知道元素个数才能定位图大小。1 万条 × 10 字节 = 100 KB， 可以接受；到百万级需要改成「两遍写」或「可增长的 bloom」。 这条记在 PLAN.md 的技术债里，不是忘了。

    SstWriter::add

    source
    fn SstWriter::add(self : SstWriter, entry : Entry) -> Unit raise LsmError

    追加一条。key 必须严格大于上一条。

    SstWriter::block_count

    source
    fn SstWriter::block_count(self : SstWriter) -> Int

    已封盘的 data block 数。

    SstWriter::entry_count

    source
    fn SstWriter::entry_count(self : SstWriter) -> Int

    已写入的条目数。

    SstWriter::finish

    source
    fn SstWriter::finish(self : SstWriter) -> Bytes raise LsmError

    产出完整 SST 字节。

    顺序严格按 §3.1：data blocks → filter → index → footer。 filter 要等所有 key 都写完才能建（需要知道元素个数来定位图大小）， 所以它只能在 finish 里生成。

    SstWriter::new

    source
    fn SstWriter::new() -> SstWriter

    Version

    source
    pub struct Version {
      last_seq : UInt64
      log_number : UInt64
      next_file_number : UInt64
      levels : Array[Array[SstMeta]]
    }

    版本快照。levels[0] 是 L0。

    L0 的 SST 之间 key 范围可以重叠（它们各自来自不同时刻的 memtable）， 所以 L0 必须全部扫；L1 及以下由 compaction 保证同层不重叠， 因此可以按 smallest/largest 二分定位。 这个差异是 Version::overlaps 存在的唯一理由。

    Version::alloc_file_number

    source
    fn Version::alloc_file_number(self : Version) -> UInt64

    从编号空间里取一个新编号。

    Version::check_invariants

    source
    fn Version::check_invariants(self : Version) -> Bool

    检查版本快照的语义不变量。decode_manifest 只保证「结构读得通」， 这里检查「这些内容合不合理」。

    分成两步是因为职责不同：结构错误只能拒绝，语义错误还可以尝试 退回上一个 MANIFEST。而且把语义检查放在解码里会让解码变慢， 而解码每次启动都要跑。

    检查的三条：
    1. log_number < next_file_number —— 活跃 WAL 的编号必须在编号空间内
    2. L1 及以下同层不重叠 —— 否则二分查找会漏数据
    3. L1 及以下同层按 smallest 升序 —— 二分查找的前提

    L0 不检查重叠：L0 的 SST 来自不同时刻的 memtable，范围天然可以重叠。 把它们也要求不重叠，等于要求「memtable 的 key 范围互不相交」， 这在真实负载下不可能成立。

    Version::level

    source
    fn Version::level(self : Version, idx : Int) -> Array[SstMeta]

    取某一层的 SST 列表。层不存在时返回空数组而不是 panic —— 「这一层还没有文件」是正常状态，不是错误。

    Version::level_bytes

    source
    fn Version::level_bytes(self : Version, idx : Int) -> UInt64

    某一层所有 SST 的字节数之和。

    归并触发条件用它，而不是「文件个数」—— 除了 L0。原因： L0 的文件大小由 memtable 上限决定，个数就能代表体量；而 L1 及以下 的文件是按 COMPACT_TARGET_SST 切的，个数多只说明数据多， 真正决定「这层该不该往下沉」的是总字节数。

    Version::level_count

    source
    fn Version::level_count(self : Version) -> Int

    层数。

    Version::new

    source
    fn Version::new() -> Version

    新建一个空版本。log_number / next_file_number 从 1 开始， 0 留给「还没有任何文件」这个状态。

    Version::push_to_level

    source
    fn Version::push_to_level(self : Version, idx : Int, meta : SstMeta) -> Unit

    往某一层追加一个 SST。flush 用它把新刷出的文件挂到 L0。

    追加到 L0 的顺序就是「从旧到新」—— 所以 Db 加载时要倒序遍历， 才能让 get 的短路优化先看到最新的文件。

    Version::set_level

    source
    fn Version::set_level(self : Version, idx : Int, ssts : Array[SstMeta]) -> Unit

    把某一层的 SST 列表整体换掉。compaction 用它。

    传入的数组会被复制一份：调用方后面可能还要改动自己的数组， 如果这里直接持有引用，「版本快照」就不再是快照了。

    Version::total_ssts

    source
    fn Version::total_ssts(self : Version) -> Int

    全部 SST 总数。

    Version::with_header

    source
    fn Version::with_header(last_seq : UInt64, log_number : UInt64, next_file_number : UInt64) -> Version

    带头部字段构造。Db 每次写 MANIFEST 都用它， 因为这三个字段总是「一起从当前状态推出来」的。

    不给 last_seq / log_number 加 mut：它们只有在 「生成一份新快照」时才会变，而不是在快照上原地改。 快照应该是不可变的 —— 可变快照是并发 bug 的温床。

    WalRecord

    source
    pub struct WalRecord {
      seq : UInt64
      op : Op
    }

    一条 WAL 记录：操作 + 序号。 WAL 里存的是操作而不是条目，因为操作更小（Delete 不带 value）。

    WalRecord::new

    source
    fn WalRecord::new(seq : UInt64, op : Op) -> WalRecord

    构造一条 WAL 记录。WAL 编码与恢复解码都走这里， 保证「写进去的」和「读出来的」是同一个类型。

    WalRecord::to_entry

    source
    fn WalRecord::to_entry(self : WalRecord) -> Entry

    重放时把 WAL 记录还原成 memtable 条目。

    WalReplay

    source
    pub struct WalReplay {
      records : Array[WalRecord]
      good_bytes : Int
      truncated : Bool
      header_ok : Bool
    }

    恢复结果。

    WalReplay::good_bytes

    source
    fn WalReplay::good_bytes(self : WalReplay) -> Int

    WalReplay::header_ok

    source
    fn WalReplay::header_ok(self : WalReplay) -> Bool

    WalReplay::is_truncated

    source
    fn WalReplay::is_truncated(self : WalReplay) -> Bool

    WalReplay::len

    source
    fn WalReplay::len(self : WalReplay) -> Int

    记录条数。

    WalReplay::records

    source
    fn WalReplay::records(self : WalReplay) -> Array[WalRecord]

    WalReplay::replay_into

    source
    fn WalReplay::replay_into(self : WalReplay, mem : MemTable, min_seq : UInt64) -> Int

    把重放结果灌进 memtable，只应用 seq > min_seq 的记录。

    min_seq 来自 MANIFEST 的 last_seq：WAL 里可能有已经刷进 SST 的记录， 重复应用不会错（值一样），但会浪费内存、也会让 seq 判断变复杂。 返回实际应用的条数。

    WalWriter

    source
    pub struct WalWriter {
      out : 
    Buffer
    }

    写 WAL。当前产出的是完整文件字节，落盘由边界层负责。

    WalWriter::append

    source
    fn WalWriter::append(self : WalWriter, rec : WalRecord) -> Unit

    追加一条记录。一条逻辑记录 = 一帧，不跨帧拆分（ADR-0002）。

    不拆分意味着单条记录不能超过 WAL_MAX_RECORD。v1 接受这个限制： 拆帧需要引入「首段/续段/尾段」三态和「重放中途又崩溃」的处理， 复杂度换来的收益（支持 64 MiB 以上的单条写入）不成比例。

    WalWriter::new

    source
    fn WalWriter::new() -> WalWriter

    新建一个 WAL，写入 8 字节文件头。

    WalWriter::size

    source
    fn WalWriter::size(self : WalWriter) -> Int

    已写入的字节数（含文件头）。

    WalWriter::to_bytes

    source
    fn WalWriter::to_bytes(self : WalWriter) -> Bytes

    取出完整文件字节。

    BLOCK_CRC_SIZE

    source
    let BLOCK_CRC_SIZE : Int

    block 尾部 CRC 的长度（v2 起）。校验范围是它之前的所有字节 —— entry 区、restart 数组、num_restarts 全在里面。

    只保护 entry 区是不够的：num_restarts 被改成一个仍然能通过边界检查的值时， 读端会把 entry 区当 restart 数组读，得到一个「结构合法但内容错乱」的 block。

    BLOCK_TARGET_SIZE

    source
    let BLOCK_TARGET_SIZE : Int

    data block 的目标大小。超过它就切下一块（切点必须落在 entry 边界）。 4 KiB 是 LevelDB / RocksDB 的默认值，也是「一次读放大」与 「索引条目数」之间的平衡点。

    CURRENT_FILE

    source
    let CURRENT_FILE : String

    L0_COMPACT_TRIGGER

    source
    let L0_COMPACT_TRIGGER : Int

    L0 的 SST 个数达到这个值就归并到 L1。

    太小（比如 2）会让每次 flush 都跟着一次 compaction，写放大明显； 太大则读放大上升。4 是 LevelDB 的默认值附近，且在 v1 的测试规模下 不会频繁触发 —— 让 compaction 成为「可观测的偶发事件」比 「一直在后台跑」更容易在测试里定位问题。

    LEVEL1_TARGET_BYTES

    source
    let LEVEL1_TARGET_BYTES : UInt64

    L1 的容量上限。超过就把 L1 整个并进 L2。

    1 MiB 是刻意选小的：v1 的定位是「能跑、能测、能讲清楚」， 而不是「扛住生产流量」。这个值小到让 L1 → L2 在测试里真的会发生 （否则那条路径永远只有代码没有验证），大到不会每次 flush 都触发。

    MANIFEST_VERSION

    source
    let MANIFEST_VERSION : Int

    NUM_LEVELS

    source
    let NUM_LEVELS : Int

    层数。L0 / L1 / L2，NUM_LEVELS - 1 是最底层。

    SST_DIR

    source
    let SST_DIR : String

    let SST_FOOTER_SIZE : Int

    footer 固定 48 字节（§3.5）。

    SST_VERSION

    source
    let SST_VERSION : Int

    当前写出的 SST 版本。读到更大的版本必须拒绝打开（§5.2）。

    2 = data block / index block 尾部带 CRC32C（ADR-0010）。 写端永远写这个版本，读端同时认 1（老库）与 2。

    SST_VERSION_V1

    source
    let SST_VERSION_V1 : Int

    唯一仍然支持的旧版本：block 没有尾部 CRC。

    留着它是为了「升级不炸库」—— 读到 v1 文件照常能读， 但不做内容校验。下一次 compaction 会把数据重写成 v2。

    WAL_DIR

    source
    let WAL_DIR : String

    磁盘布局（docs/design/format.md §1）：

    <db_path>/
├── CURRENT              # 文本，内容是当前 MANIFEST 的文件名 + "\n"
├── MANIFEST-000007      # 版本快照
├── wal/
│   └── 000008.wal       # 活跃 WAL
└── sst/
    └── 000004.sst

    文件编号全局共享：WAL、SST、MANIFEST 从同一个单调递增计数器取号 （存在 MANIFEST 的 next_file_number 里）。这样任何两个文件不会撞名， 恢复时也只需比较编号大小。

    早期版本用的是根目录扁平的 WAL-000001 / SST-000001，两个独立计数器。 那种布局在引入 WAL 轮转（每次 flush 换一个新 WAL）之后就不成立了： 两个计数器会各自撞上对方已经用过的号。

    WAL_HEADER_SIZE

    source
    let WAL_HEADER_SIZE : Int

    WAL_MAX_RECORD

    source
    let WAL_MAX_RECORD : Int

    单帧 payload 上限（64 MiB）。

    必须有这个上限：length 是磁盘上读来的，一个坏值（比如 0x7FFFFFFF） 会让恢复过程尝试分配 2 GB 内存，直接 OOM。这不是理论风险， 是「尾部有半条记录」时最容易踩到的一种表现。

    WAL_VERSION

    source
    let WAL_VERSION : Int

    bloom_hashes

    source
    fn bloom_hashes(key : Bytes) -> (UInt64, UInt64)

    由一条 key 算出双哈希对 (h1, h2)。

    单独暴露出来是为了让调用方复用：一次点查要探 N 个 SST 的 filter， 而这 N 次用的是同一条 key。把哈希提到循环外面，N 次变 1 次。

    FNV-1a 出来必须再过一遍 mix64。 这不是保险，是必需的： FNV-1a 最后一步是 (h ^ byte) * prime，末字节只影响乘数的低 8 位， 高位几乎不随它变化。实测「10000 条只差末几位的 key」直接取高 32 位， 只落进约 1000 个不同位置（理论值 9516），误判率因此只有理论值的一半。 换成低位也有同样的隐患，正确做法是先做一次完整雪崩。

    compare_bytes

    source
    fn compare_bytes(a : Bytes, b : Bytes) -> Int

    字节序比较：逐字节比，前缀相同时短的小。 必须自己写 —— 不能依赖 String 的字典序，因为 key 是二进制。

    返回值恒为 -1 / 0 / 1，不返回长度差值。 这样调用方可以安全地写 == -1 判断，而不只是依赖符号。

    compare_strings

    source
    fn compare_strings(a : String, b : String) -> Int

    字符串 key 的字节序比较。

    存在的意义：把 UTF-8 编码细节收在库内，调用方（dbcli / 测试）不用自己 处理 Bytes 转换，也不会误用 String::compare（它按长度优先，不是字节序）。

    crc32c

    source
    fn crc32c(data : Bytes) -> UInt64

    计算一段字节的 CRC32C，返回值在 [0, 0xFFFFFFFF] 范围内。

    标准校验向量：crc32c("123456789") == 0xE3069283， crc32c("") == 0。这两条在测试里硬编码断言 —— 它们是 「我的实现和别人能互通」的唯一证据。

    decode_block

    source
    fn decode_block(raw : Bytes) -> Block?

    解析一个格式版本 2 的 block：先校验尾部 CRC，再解析结构。

    校验顺序是「CRC 在前，结构在后」，因为 CRC 是唯一的内容校验。 先跑结构检查会让「结构碰巧仍然合法、内容已经错了」的损坏漏过去 —— 那正是没有 CRC 时 58% 的静默接受是怎么来的。

    返回 None 的两种情形（CRC 不符 / 结构不合法）在读端是同一个后果： 这个 block 不可信。调用方一律当损坏处理，不去猜。

    decode_block_v1

    source
    fn decode_block_v1(raw : Bytes) -> Block?

    解析一个格式版本 1 的 block（尾部没有 CRC，只有 num_restarts）。

    只在读 v1 文件时走这条路（ADR-0010）。它不做任何内容校验 —— 这正是 v1 的已知短板，保留它是为了能读老库，不是为了继续用。

    decode_bloom

    source
    fn decode_bloom(data : Bytes) -> BloomFilter?

    从字节解码 filter（格式版本 2，尾部带 CRC）。结构不一致或 CRC 不符时返回 None。

    这里校验得比较严（k 的范围、位图长度必须与 num_bits 精确匹配）： filter 读错不会直接导致数据错误，但会让「假阴性」出现 —— 而假阴性意味着「数据明明在，却查不到」，这是 LSM 里最不可接受的错误。 宁可判定文件损坏、拒绝打开，也不要拿着一个半信半疑的 filter 去过滤。

    decode_bloom_v1

    source
    fn decode_bloom_v1(data : Bytes) -> BloomFilter?

    解码格式版本 1 的 filter（没有尾部 CRC）。只在读 v1 文件时走这里。

    decode_manifest

    source
    fn decode_manifest(data : Bytes) -> Version?

    反序列化。任何结构问题都返回 None，不抛错也不 panic。

    校验顺序刻意从「最便宜、最能早退」开始： 长度 → magic → version → CRC → 逐字段解析。

    CRC 放在解析之前是关键：如果先解析再校验，一份随机垃圾数据会先 让解析器分配一堆数组、走一堆分支，最后才发现「这是垃圾」。 先校验的话，坏数据在 4 次整数比较内就被否掉。

    empty_wal_bytes

    source
    fn empty_wal_bytes() -> Bytes

    空 WAL 的文件字节（只有文件头）。创建新 WAL 时用。

    encode_frame

    source
    fn encode_frame(rec : WalRecord) -> Bytes

    编码单帧，不含 8 字节文件头。

    追加写 WAL 时用：文件头只在创建时写一次，之后的每一次 put 都只是 往文件尾追加一帧。如果每次都调 WalWriter::new() 再整体写出， 文件头会被反复追加，恢复时第一帧就会解错。

    encode_manifest

    source
    fn encode_manifest(v : Version) -> Bytes

    把一个版本序列化成完整文件字节（含文件头和 CRC）。

    一次性产出全部内容，不做流式写：快照本身只有几百 KB， 而「流式写一半崩了」又要引入一套部分写入的恢复逻辑。

    flush_stdio

    source
    fn flush_stdio() -> Unit

    把 stdio 缓冲推到 OS。CLI 每输出一行就要调一次——管道下的 stdout 是块缓冲的，不推的话驱动脚本读不到输出。

    ⚠️ 不要在别处再声明一次 fflush。

    同一个 C 符号被两处不同签名的 extern "C" 声明时，编译器只会保留 其中一个原型。如果其中一处写的是 Int（32 位），而库内按 UInt64 传 FILE*，指针会在调用点被截断成 32 位——症状是 fflush 内部 段错误，而崩溃点跟调用方看起来毫无关系。

    这个 bug 真的发生过：cmd/dbcli 自己声明了一份 extern "C" fn fflush(Int) -> Int，结果整个 CLI 一启动就 0xc0000005，排查了很久才定位到「两个签名不一致」。 统一从这里出去，就只有一个声明点了。

    is_bottom_level

    source
    fn is_bottom_level(lv : Int) -> Bool

    最底层不再往下沉 —— 它的数据要等到被覆盖写或删除才会消失。

    level_target_bytes

    source
    fn level_target_bytes(lv : Int) -> UInt64

    第 lv 层的容量上限。L0 返回 0 —— 它按文件个数触发，不看字节数。

    open_native

    source
    fn open_native(dir : String, mem_limit : Int) -> Db[NativeStorage] raise LsmError

    用 native 后端打开数据库。

    这是一个非泛型入口，专门给跨包调用方（cmd/dbcli）用。 直接跨包调 Db::open(storage, ...) 会在进入函数体之前就段错误—— 泛型结构体按值跨包传递在这个工具链版本上不可靠。 包一层非泛型函数把实例化点留在库内，就绕开了这个问题。

    open_sst

    source
    fn open_sst(data : Bytes) -> SstReader?

    打开一个 SST。任何结构性问题返回 None，不 panic。

    校验顺序刻意从「最便宜、最能早退」开始：长度 → magic → version → 区域边界。 先查 magic 再查 offset 很重要 —— 如果文件根本不是 SST， 那些 offset 是垃圾值，拿它们做边界检查只是白算。

    read_fixed16

    source
    fn read_fixed16(data : Bytes, pos : Int) -> Int?

    从 data[pos..] 读 2 字节小端定长整数。

    read_fixed32

    source
    fn read_fixed32(data : Bytes, pos : Int) -> Int?

    从 data[pos..] 读 4 字节小端定长整数。 不做 limit 参数：定长读取的长度是已知的，越界判断用 pos + 4 > length() 就够。

    read_fixed32u

    source
    fn read_fixed32u(data : Bytes, pos : Int) -> UInt64?

    从 data[pos..] 读 4 字节小端为无符号 32 位值（0 .. 0xFFFFFFFF）。

    read_fixed64

    source
    fn read_fixed64(data : Bytes, pos : Int) -> UInt64?

    从 data[pos..] 读 8 字节小端定长整数。

    read_varint32

    source
    fn read_varint32(data : Bytes, pos : Int, limit : Int) -> (Int, Int)?

    从 data[pos..limit] 读一个 varint32，返回 (值, 新位置)。

    limit 是硬边界而不是 data.length()：调用方传入的是一段逻辑区域 （比如 data block 的 entry 区，后面还跟着 restart 数组）， 越过 limit 就等于读到了别的结构，必须当越界处理。

    read_varint64

    source
    fn read_varint64(data : Bytes, pos : Int, limit : Int) -> (UInt64, Int)?

    从 data[pos..limit] 读一个 varint64，返回 (值, 新位置)。

    recover_wal

    source
    fn recover_wal(data : Bytes) -> WalReplay

    恢复 WAL。永不抛错、永不 panic，坏数据只会让重放提前结束。

    按 format.md §2.4 的顺序实现：读 crc → 读 length → 读 type+payload → 校验 crc → 应用。任何一步失败就跳到 truncate。

    should_compact_level

    source
    fn should_compact_level(lv : Int, sst_count : Int, bytes : UInt64) -> Bool

    第 lv 层该不该归并。

    纯策略函数，不做任何 IO。 单独抽出来是为了能用任意数字做单测： 「L1 超过 1 MiB 就下沉」这条规则如果用真数据测，得先写 1 MiB， 而验证边界（>= 还是 >）要写两个 1 MiB 的库。

    varint32_len

    source
    fn varint32_len(value : Int) -> Int

    varint32 编码后的字节数。用于估算 block 大小，不做实际写入。

    write_fixed16

    source
    fn write_fixed16(buf : 
    Buffer    , value : Int) -> Unit

    写 2 字节小端定长整数。WAL / MANIFEST 的文件头 version 字段用它。

    write_fixed32

    source
    fn write_fixed32(buf : 
    Buffer    , value : Int) -> Unit

    写 4 字节小端定长整数（格式规范 §0：所有定长整数小端序）。

    write_fixed32u

    source
    fn write_fixed32u(buf : 
    Buffer    , value : UInt64) -> Unit

    写 4 字节小端定长整数，无符号语义（值域 0 .. 0xFFFFFFFF）。 CRC32C 的校验和用它 —— 用 write_fixed32 也能写出同样的字节， 但那个函数接受的是有符号 Int，0xE3069283 这样的值传进去是负数， 读代码的人会以为哪里算错了。

    write_fixed64

    source
    fn write_fixed64(buf : 
    Buffer    , value : UInt64) -> Unit

    写 8 字节小端定长整数。footer 的 offset / size / seq 都用它。

    write_varint32

    source
    fn write_varint32(buf : 
    Buffer    , value : Int) -> Unit

    写 varint32。要求 value >= 0。

    负数在 LEB128 里没有意义（格式规范 §0 明确规定是无符号变长整数）， 传负数是调用方的 bug，不是数据的问题，所以这里不静默截断成 0 —— 静默截断会让「-1 变成 0」这种错误一路走到磁盘上。

    write_varint64

    source
    fn write_varint64(buf : 
    Buffer    , value : UInt64) -> Unit

    写 varint64。

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io