🥮 mooncakes.io
    Sign in

    regolith

    月壤：纯 MoonBit LSM-tree 嵌入式 KV 存储（WAL + 跳表 MemTable + SSTable + 合并压缩）。

    database
    kv
    lsm
    storage
    embedded
    Download zip
    Author
    Version
    0.2.1
    License
    Apache-2.0
    Repository
    Last updated
    7 hours ago
    Downloads
    19

    #regolith（月壤）

    CI

    纯 MoonBit 的嵌入式 LSM-tree 键值存储引擎。零 FFI、零 unsafe，仅依赖 moonbitlang/x 的 @fs 做文件访问，可在 MoonBit 支持的任意后端运行。

    名称取自月球表面覆盖的松散岩屑层「月壤」（lunar regolith）——写入如 月壤般层层堆积，压缩则如压实成岩。

    #特性

    • LSM-tree 架构：跳表 MemTable + WAL + SSTable + 分级合并压缩（L0 → L1 → L2）
    • 原子批量写：Db::write(WriteBatch) 一次提交多键，WAL 单条记录承载，恢复时整批全有或全无
    • 快照与迭代器句柄：Db::snapshot() 冻结一致性视图，活库继续写/flush/压缩期间，快照上的读与迭代器保持同一视图，可暂停可恢复
    • 崩溃一致性：WAL 组提交 + 恢复不变量（恢复后的状态 = 某次写入序列的前缀）
    • 确定性：跳表高度由固定种子的 xorshift64 流生成，行为跨后端可复现
    • 范围扫描：scan_prefix(p) / scan_range(start, end) 利用键序提前终止，不遍历范围之外的数据
    • 故障注入测试：200 种子 × 40 步确定性崩溃套件，覆盖 LostWrite / TornWrite（WAL / L0 / L1 / L2）
    • 三后端 CI：js / wasm-gc / native 测试全绿，moon check 零警告

    #快速开始

    moon add QYF795/regolith   # 依赖方式使用（mooncakes.io 已发布）

    fn main raise {
      let db = @QYF795/regolith.Db::open("data")
      db.put(b"key", b"value")
      println(db.get(b"key").to_string()) // Some(Some(b"value"))
      db.flush() // 落盘确认
    }

    本地开发与自测：

    moon test --target js
moon test --target wasm-gc

    #CLI

    moon run --target js src/cli -- set hello regolith
moon run --target js src/cli -- get hello          # regolith
moon run --target js src/cli -- scan
moon run --target js src/cli -- scan_prefix hel    # hello=regolith
moon run --target js src/cli -- scan_range h i     # hello=regolith
moon run --target js src/cli -- stats

    命令：set <key> <value> / get <key> / del <key> / scan / scan_prefix <prefix> / scan_range <start> <end>（end 为空串 = 无上界）/ flush / compact（归并全部数据到底层 L2）/ stats。set/del 返回 ok 时数据已落盘。数据目录 regolith-data/ 已 git-ignore。

    #API

    fn main raise {
      let db = Db::open("demo-data") // 默认选项
      db.put(b"key", b"value")
      println(db.get(b"key").to_string()) // Some(Some(b"value"))
      // 多键一次原子提交（全有或全无）
      db.write(WriteBatch::new().put(b"a", b"1").delete(b"key"))
      db.flush() // 主动落盘
      // 快照：冻结当前状态；后续写入不影响快照上的读写
      let snap = db.snapshot()
      db.put(b"key", b"other")
      println(snap.get(b"key").to_string()) // 仍是 Some(Some(b"value"))
      snap.close() // 释放快照钉住的表文件
    }

    Db::get 返回 Option[Option[Bytes]]：None = 键不存在，Some(None) = 墓碑（已删除），Some(Some(v)) = 值。

    #目录结构

    src/           引擎实现（WAL / MemTable / SSTable / Db / 合并迭代器 / CLI / demo）
tools/         开发工具（sim_crash.py：崩溃一致性全状态模拟器）
docs/          [磁盘格式](docs/format.md) / [验收清单](docs/acceptance.md) / [设计文档](docs/design.md)

    #许可证

    Apache-2.0

    DbError

    source
    pub(all) suberror DbError {
      Io(String)
      Corrupt(String)
      Fault(String)
    }

    VarintError

    source
    pub(all) suberror VarintError {
      Truncated
      Overflow
    }

    Bloom

    source
    pub(all) struct Bloom {
      m_bits : Int
      bits : Bytes
    }
    A key filter over the table. Built with LevelDB-style double hashing:

    h = crc32_init(key, BLOOM_SEED) gi = (h + i * delta) % m, delta = (h >> 17) | (h << 15)

    k=7 probes into m=10·n bits gives ~0.8% false positives. A bloom "no" is authoritative — the key is definitely absent; a bloom "yes" only decides that the real lookup is worth doing.

    Bloom::may_contain

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

    pub(all) struct Db {
      storage : Storage
      opts : Options
      memtable : MemTable
      wal : Wal
      next_seq : 
    Ref    [UInt64]
      l0_counter : 
    Ref    [Int]
      l0_names : 
    Ref    [Array[String]]
      l0_readers : 
    Ref    [Array[SstReader]]
      l1_seq : 
    Ref    [UInt64?]
      l1_name : 
    Ref    [String?]
      l1_reader : 
    Ref    [SstReader?]
      l2_seq : 
    Ref    [UInt64?]
      l2_name : 
    Ref    [String?]
      l2_reader : 
    Ref    [SstReader?]
      l1_bytes : 
    Ref    [Int]
      l2_bytes : 
    Ref    [Int]
      snapshots : 
    Ref    [Array[Snapshot]]
      next_snap_id : 
    Ref    [UInt64]
      pending : 
    Ref    [Array[String]]
    }

    Db::close

    source
    fn Db::close(self : Db) -> Unit raise DbError
    Flushes any pending writes; safe to call any number of times.

    Db::compact

    source
    fn Db::compact(self : Db) -> Unit raise DbError
    Merges the memtable, every L0 table and the current L1 into a single L1_ table, where S is the largest sequence number it contains. The new table is written and validated before any old file is removed.

    This is a non-bottom merge: tombstones are retained (MergeIterator next_raw) because L2 may still hold older versions of a deleted key — dropping the tombstone here would resurrect them.

    Db::compact_l2

    source
    fn Db::compact_l2(self : Db) -> Unit raise DbError
    The bottom merge: memtable + every L0 + L1 + the current L2 into a single L2_ table. Tombstones are suppressed here — every older version is in the merge, so nothing is left for a dropped tombstone to cover. The new table lands (and validates) before any input file is removed; its S becomes the coverage watermark every level checks against on recovery.

    Db::delete

    source
    fn Db::delete(self : Db, key : Bytes) -> Unit raise DbError
    Deletes a key (a tombstone write).

    Db::flush

    source
    fn Db::flush(self : Db) -> Unit raise DbError
    Seals the memtable into an L0 table (see the header comment for order).

    Db::get

    source
    fn Db::get(self : Db, key : Bytes) -> Bytes?? raise DbError
    Reads a key: None absent, Some(None) deleted, Some(Some(v)) live.

    Db::open

    source
    fn Db::open(dir : String) -> Db raise DbError
    Opens a database rooted at a directory on the local filesystem.

    Db::open_memory

    source
    fn Db::open_memory() -> Db raise DbError
    Opens an in-memory database (tests and embedders).

    Db::open_with_options

    source
    fn Db::open_with_options(storage : Storage, opts : Options) -> Db raise DbError
    Opens a database over the given storage, recovering its state.

    Db::put

    source
    fn Db::put(self : Db, key : Bytes, value : Bytes) -> Unit raise DbError
    Writes a key. A later put or delete of the same key supersedes it.

    Db::release_snapshot

    source
    fn Db::release_snapshot(self : Db, id : UInt64) -> Unit raise DbError
    Unregisters a closed snapshot and sweeps the pending list: files no snapshot holds any more are deleted now.

    Db::scan

    source
    fn Db::scan(self : Db) -> MergeIterator
    Returns a merge iterator over all live entries, in ascending key order.

    Db::scan_prefix

    source
    fn Db::scan_prefix(self : Db, prefix : Bytes) -> RangeIterator
    Scans every live entry whose key starts with prefix, in ascending key order. Stops early at the first key outside the prefix, so iterating a small key range does not walk the whole store.

    Db::scan_range

    source
    fn Db::scan_range(self : Db, start : Bytes, end : Bytes?) -> RangeIterator
    Scans every live entry with start <= key < end, in ascending key order. end = None means no upper bound. Stops early at the first key ≥ end.

    Db::snapshot

    source
    fn Db::snapshot(self : Db) -> Snapshot
    Creates a snapshot of the database's current state. The snapshot keeps working (and keeps seeing the same data) while the Db keeps mutating; call close when done so pinned table files can be reclaimed.

    Db::stats

    source
    fn Db::stats(self : Db) -> Stats

    Db::write

    source
    fn Db::write(self : Db, batch : WriteBatch) -> Unit raise DbError
    Applies every write in the batch at once. Writes within one batch win over earlier ones by sequence number, like single writes do.

    Entry

    source
    pub(all) struct Entry {
      key : Bytes
      seq : UInt64
      value : Bytes?
    }

    FailpointStorage

    source
    pub(all) struct FailpointStorage {
      inner : MemoryStorage
      armed_kind : 
    Ref    [FaultKind?]
      armed_name : 
    Ref    [String?]
      fired : 
    Ref    [Bool]
    }

    FailpointStorage::arm

    source
    fn FailpointStorage::arm(self : FailpointStorage, kind : FaultKind) -> Unit
    Arms a one-shot fault on the next matching operation, any file.

    FailpointStorage::arm_on

    source
    fn FailpointStorage::arm_on(self : FailpointStorage, kind : FaultKind, name_prefix : String) -> Unit
    Arms a one-shot fault that only fires for files whose name starts with name_prefix (e.g. "WAL", "L0_", "L1_"). Other operations pass through.

    FailpointStorage::armed

    source
    fn FailpointStorage::armed(self : FailpointStorage) -> Bool
    True while an armed fault has not fired yet.

    FailpointStorage::disarm

    source
    fn FailpointStorage::disarm(self : FailpointStorage) -> Unit

    FailpointStorage::new

    source

    FaultKind

    source
    pub(all) enum FaultKind {
      FailRead
      TornWrite
      LostWrite
    } derive(Eq, 
    Debug    )
    Fault kinds injectable through a FailpointStorage. LostWrite models a write that reported success but never reached the medium (a lost fsync); it only ever fires on WAL writes, because losing a table write silently would be indistinguishable from corruption of the whole file.

    FaultKind::equal

    source
    fn FaultKind::equal(FaultKind, FaultKind) -> Bool
    automatically derived

    FaultKind::not_equal

    source
    fn FaultKind::not_equal(x : FaultKind, y : FaultKind) -> Bool

    FaultKind::to_repr

    source
    automatically derived

    FileStorage

    source
    pub(all) struct FileStorage {
      dir : String
    }

    FileStorage::new

    source
    fn FileStorage::new(dir : String) -> FileStorage

    MemIter

    source
    pub(all) struct MemIter {
      cur : Node?
    }
    A position inside a memtable, used by the merge iterator.

    MemIter::advance

    source
    fn MemIter::advance(self : MemIter) -> Unit

    MemIter::error

    source
    fn MemIter::error(_self : MemIter) -> DbError?

    MemIter::peek

    source
    fn MemIter::peek(self : MemIter) -> Entry?

    MemTable

    source
    pub(all) struct MemTable {
      head : Node
      rng : 
    Ref    [UInt64]
      size_bytes : 
    Ref    [Int]
      max_seq : 
    Ref    [UInt64]
    }

    MemTable::get

    source
    fn MemTable::get(self : MemTable, key : Bytes) -> Bytes??
    None = absent, Some(None) = tombstone, Some(Some(v)) = live value.

    MemTable::is_empty

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

    MemTable::iter

    source
    fn MemTable::iter(self : MemTable) -> MemIter

    MemTable::max_seq

    source
    fn MemTable::max_seq(self : MemTable) -> UInt64

    MemTable::new

    source
    fn MemTable::new() -> MemTable

    MemTable::put

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

    MemTable::size_bytes

    source
    fn MemTable::size_bytes(self : MemTable) -> Int

    MemoryStorage

    source
    pub(all) struct MemoryStorage {
      files : 
    HashMap    [String, Bytes]
    }

    MemoryStorage::new

    source

    MergeIterator

    source
    pub(all) struct MergeIterator {
      streams : Array[Stream]
      heads : Array[Entry?]
      err : DbError?
    }

    MergeIterator::error

    source
    fn MergeIterator::error(self : MergeIterator) -> DbError?
    The first failure reported by any source, if any.

    MergeIterator::new

    source
    fn MergeIterator::new(streams : Array[Stream]) -> MergeIterator

    MergeIterator::next

    source
    fn MergeIterator::next(self : MergeIterator) -> Entry?
    Returns the next live entry in ascending key order, skipping tombstones. Returns None when all sources are exhausted (or a source failed — check error).

    Node

    source
    type Node

    Options

    source
    pub(all) struct Options {
      memtable_limit : Int
      block_size : Int
      l0_compaction_trigger : Int
      l2_size_trigger : Int
      l2_size_ratio : Int
    }

    Options::default

    source
    fn Options::default() -> Options

    Options::with_compaction_trigger

    source
    fn Options::with_compaction_trigger(self : Options, n : Int) -> Options

    Options::with_l2_size_ratio

    source
    fn Options::with_l2_size_ratio(self : Options, n : Int) -> Options
    Sets the L1/L2 size ratio that gates L2 compaction (see l2_size_ratio).

    Options::with_l2_size_trigger

    source
    fn Options::with_l2_size_trigger(self : Options, n : Int) -> Options
    Sets the minimum L1 byte size before L2 compaction is considered.

    Options::with_memtable_limit

    source
    fn Options::with_memtable_limit(self : Options, n : Int) -> Options

    RangeIterator

    source
    pub(all) struct RangeIterator {
      inner : MergeIterator
      lo : Bytes
      hi : Bytes?
      prefix : Bytes?
    }
    A merge iterator bounded to one key range [lo, hi). Skips keys below lo and stops at the first key >= hi — keys arrive in ascending order, so no in-range key can follow an out-of-range one. scan_prefix is the same mechanism: lo = prefix, hi = the first key not starting with the prefix. When no finite hi exists (a prefix of all 0xFF bytes), a fallback prefix check plays the upper bound.

    RangeIterator::error

    source
    fn RangeIterator::error(self : RangeIterator) -> DbError?
    The first failure reported by any underlying source, if any.

    RangeIterator::new

    source
    fn RangeIterator::new(inner : MergeIterator, lo : Bytes, hi : Bytes?) -> RangeIterator
    An iterator over [lo, hi); hi = None means no upper bound.

    RangeIterator::new_prefix

    source
    fn RangeIterator::new_prefix(inner : MergeIterator, prefix : Bytes) -> RangeIterator
    An iterator over every key that starts with prefix (see prefix_upper).

    RangeIterator::next

    source
    fn RangeIterator::next(self : RangeIterator) -> Entry?
    The next live entry in the range, or None once the range is exhausted (or a source failed — check error).

    Snapshot

    source
    pub(all) struct Snapshot {
      db : Db
      id : UInt64
      mem : MemTable
      l0_names : Array[String]
      l0_readers : Array[SstReader]
      l1_name : String?
      l1_reader : SstReader?
      l2_name : String?
      l2_reader : SstReader?
      closed : 
    Ref    [Bool]
    }

    Snapshot::close

    source
    fn Snapshot::close(self : Snapshot) -> Unit raise DbError
    Releases the snapshot. Idempotent; afterwards the Db may delete the table files this snapshot was pinning.

    Snapshot::get

    source
    fn Snapshot::get(self : Snapshot, key : Bytes) -> Bytes?? raise DbError
    Reads a key as of snapshot creation: None absent, Some(None) deleted, Some(Some(v)) live.

    Snapshot::scan

    source
    fn Snapshot::scan(self : Snapshot) -> MergeIterator
    Iterates the frozen view in ascending key order. The iterator stays valid while the live Db mutates — a stable handle.

    Snapshot::scan_prefix

    source
    fn Snapshot::scan_prefix(self : Snapshot, prefix : Bytes) -> RangeIterator
    Prefix scan over the frozen view; see Db::scan_prefix.

    Snapshot::scan_range

    source
    fn Snapshot::scan_range(self : Snapshot, start : Bytes, end : Bytes?) -> RangeIterator
    Range scan over the frozen view; see Db::scan_range. Pausing an iteration and resuming from the last seen key = calling this again with start = that key (or its successor).

    SstBuilder

    source
    pub(all) struct SstBuilder {
      data : 
    Buffer
      block : 
    Buffer
      index : 
    Buffer
      block_count : 
    Ref    [Int]
      index_count : 
    Ref    [Int]
      last_key : 
    Ref    [Bytes?]
      bloom_hashes : Array[UInt]
      block_size : Int
    }
    Builds an SSTable v2 from entries added in ascending key order.

    SstBuilder::add

    source
    fn SstBuilder::add(self : SstBuilder, entry : Entry) -> Unit
    Adds one entry. Keys must be strictly ascending.

    SstBuilder::finish

    source
    fn SstBuilder::finish(self : SstBuilder) -> Bytes
    Finishes the table and returns the serialized bytes (v2, with bloom).

    SstBuilder::new

    source
    fn SstBuilder::new(block_size? : Int) -> SstBuilder

    SstCursor

    source
    pub(all) struct SstCursor {
      reader : SstReader
      block_idx : 
    Ref    [Int]
      pos : 
    Ref    [Int]
      entries_left : 
    Ref    [Int]
      current : 
    Ref    [Entry?]
      last_key : 
    Ref    [Bytes?]
      done : 
    Ref    [Bool]
      err : 
    Ref    [DbError?]
    }
    A lazy forward cursor over one table: entries are parsed on demand, one block at a time, so scanning a large file holds no extra materialized state. Parse failures are reported through error rather than raised. Every entry must be strictly greater than the previous one — a duplicate or out-of-order key is a form of corruption that CRC cannot see (e.g. a table written by a buggy old version), and it would otherwise be merged silently forward by compactions. The cursor rejects it with Corrupt.

    SstCursor::advance

    source
    fn SstCursor::advance(self : SstCursor) -> Unit

    SstCursor::error

    source
    fn SstCursor::error(self : SstCursor) -> DbError?

    SstCursor::peek

    source
    fn SstCursor::peek(self : SstCursor) -> Entry?

    SstReader

    source
    pub(all) struct SstReader {
      bytes : Bytes
      idx_off : Int
      index_keys : Array[Bytes]
      index_offsets : Array[Int]
      bloom : Bloom?
    }
    A validated, read-only view of an SSTable file.

    SstReader::cursor

    source
    fn SstReader::cursor(self : SstReader) -> SstCursor

    SstReader::get

    source
    fn SstReader::get(self : SstReader, key : Bytes) -> Bytes?? raise DbError
    Looks up a key. None = absent, Some(None) = tombstone, Some(Some(v)) = live value.

    SstReader::may_contain

    source
    fn SstReader::may_contain(self : SstReader, key : Bytes) -> Bool
    The bloom filter says the key is absent, or the table has no filter (v1). A false answer is authoritative; true only avoids a wasted lookup.

    Stats

    source
    pub(all) struct Stats {
      memtable_bytes : Int
      wal_bytes : Int
      l0_files : Int
      l1_files : Int
      l1_bytes : Int
      l2_files : Int
      l2_bytes : Int
    }

    Storage

    source
    pub(all) enum Storage {
      Memory(MemoryStorage)
      File(FileStorage)
      Failpoint(FailpointStorage)
    }

    Stream

    source
    pub(all) enum Stream {
      Mem(MemIter)
      Sst(SstCursor)
    }

    Wal

    source
    pub(all) struct Wal {
      buf : 
    Buffer
    }

    Wal::append

    source
    fn Wal::append(self : Wal, key : Bytes, value : Bytes?, seq : UInt64) -> Unit

    Wal::append_batch

    source
    fn Wal::append_batch(self : Wal, ops : Array[(Bytes, Bytes?)], base : UInt64) -> Unit
    Appends one batch record: ops share the contiguous sequence range base..base+n-1 and are replayed together on recovery.

    Wal::clear

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

    Wal::encode

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

    Wal::from_bytes

    source
    fn Wal::from_bytes(bytes : BytesView) -> Wal
    Rebuilds the WAL buffer from bytes recovered from storage, so the next seal rewrites the surviving records along with any new ones.

    Wal::is_empty

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

    Wal::length

    source
    fn Wal::length(self : Wal) -> Int

    Wal::new

    source
    fn Wal::new() -> Wal

    WalRecord

    source
    pub(all) struct WalRecord {
      key : Bytes
      value : Bytes?
      seq : UInt64
    }

    WriteBatch

    source
    pub(all) struct WriteBatch {
      ops : Array[(Bytes, Bytes?)]
    }
    A group of writes applied atomically: the memtable gets one contiguous sequence range and the WAL one batch record, so recovery replays the whole batch or none of it.

    WriteBatch::delete

    source
    fn WriteBatch::delete(self : WriteBatch, key : Bytes) -> WriteBatch

    WriteBatch::is_empty

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

    WriteBatch::new

    source
    fn WriteBatch::new() -> WriteBatch

    WriteBatch::put

    source
    fn WriteBatch::put(self : WriteBatch, key : Bytes, value : Bytes) -> WriteBatch

    crc32

    source
    fn crc32(data : BytesView) -> UInt
    CRC-32 of data with the standard init and final-xor values.

    crc32_init

    source
    fn crc32_init(data : BytesView, init : UInt) -> UInt
    CRC-32 of data with a custom init seed (final xor still applied). The seed selects an independent hash stream, which the bloom filter uses for double hashing.

    ensure_ready

    source
    fn ensure_ready(storage : Storage) -> Unit raise DbError
    Prepares the storage for use (creates the directory of a File storage).

    exists

    source
    fn exists(storage : Storage, name : String) -> Bool raise DbError
    True if the named file exists.

    list

    source
    fn list(storage : Storage, prefix : String) -> Array[String] raise DbError
    Lists file names with the given prefix, sorted by name.

    parse

    source
    fn parse(bytes : Bytes) -> SstReader raise DbError
    Validates magic, both checksums and the index, then returns the reader. v1 files (no bloom) are still accepted; they answer may_contain with true and behave exactly as before.

    parse_wal

    source
    fn parse_wal(bytes : Bytes) -> (Array[WalRecord], Int)
    Parses a WAL image into records plus the length of the valid prefix. Parsing stops cleanly at the first torn or corrupted record.

    put_varint

    source
    fn put_varint(buf : 
    Buffer    , v : UInt64) -> Unit
    Appends the varint encoding of v to buf.

    read

    source
    fn read(storage : Storage, name : String) -> Bytes? raise DbError
    Reads a whole file; None means the file does not exist.

    read_varint

    source
    fn read_varint(bytes : Bytes, pos : 
    Ref    [Int]) -> UInt64 raise VarintError
    Reads one varint from bytes starting at pos.val, advancing pos past it. Raises Truncated if the input ends mid-varint and Overflow if the encoding exceeds 10 bytes.

    remove

    source
    fn remove(storage : Storage, name : String) -> Unit raise DbError
    Removes a file; removing a missing file is a no-op.

    write

    source
    fn write(storage : Storage, name : String, data : Bytes) -> Unit raise DbError
    Writes a whole file, creating or replacing it.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io