English | 简体中文

MoonBit Bitcask

A Bitcask key-value storage engine implemented in MoonBit — the same design used as Riak's default storage backend.

Features

• Append-only writes: one sequential write + one in-memory hash index update per put. No random IO on the write path.
• Read amplification of 1: the in-memory index (keydir) points straight at the record's (file_id, offset); a read is a single seek + read.
• Tombstone deletes: deletes write a tombstone record; nothing is mutated in place.
• File rotation: data files are named with incrementing IDs (0.data, 1.data, …); the active file rolls over once it reaches max_file_size.
• Crash-safe recovery: on open, files are replayed in ID order (later wins); a torn tail (CRC mismatch / truncation) stops at that file only, keeping all previously synced data.
• Merge (compaction): reclaims space from overwritten/deleted records by rewriting the newest version of each key into a fresh file; the new file is synced before old files are removed.
• Hint files: after a merge, a {id}.hint file stores key→position metadata, so recovery scales with the number of keys instead of total data size.

Usage

let db = @bitcask.open("my-data") // default max_file_size = 256 MiB, no per-write fsync
db.put(b"hello", b"world")
let value = db.get(b"hello") // Some(b"world")
db.delete(b"hello")
db.merge() // reclaim space
db.close()

Open with options:

// rotate at 64 MiB, fdatasync every write (write-ahead durability)
let db = @bitcask.open("my-data", max_file_size=67108864L, sync=@fs.SyncMode.Data)

Run the interactive CLI:

moon run cmd/main

Disk format

Each record (little-endian):

+-------+------+---------+-----------+-----------+-----+-------+
| crc32 | ts   | key_len | value_len | tombstone | key | value |
| 4B    | 8B   | 4B      | 4B        | 1B        | var | var   |
+-------+------+---------+-----------+-----------+-----+-------+

Hint records: key_len(4B) | value_len(4B) | offset(8B) | ts(8B) | key.

Limitations (inherent to Bitcask)

• All keys must fit in memory.
• No range scans: the index is an unordered hash map.
• Space is reclaimed only by merge().

Development

moon check --target native   # type check
moon test --target native    # run tests