English | [简体中文](README.md)

# MoonBit Bitcask

A [Bitcask](https://riak.com/assets/bitcask-intro.pdf) 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

```mbt nocheck
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:

```mbt nocheck
// 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:

```sh
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

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