memtable.nu

packages/lsmdb/src/memtable.nu — the write buffer of the LSM tree: a skip list over a byte arena.

Every write lands here first (after the WAL). The structure has to be three things at once: ordered (so a flush emits a sorted SSTable and a range scan needs no sorting), versioned (so a snapshot read can see the database as it was N writes ago), and cheap to build (a database does millions of these).

The layout is index-based, not pointer-based: keys and values are appended to ONE growable arena, and a node is a row of integers — (key offset, key length, value offset, value length, sequence, kind) plus its forward links. Nothing is individually allocated or freed, so dropping the whole memtable is a handful of Vec drops, and a node is never invalidated by the arena growing under it (offsets, not pointers).

Ordering is LevelDB's: key ascending, and for equal keys sequence DESCENDING — the newest version of a key sorts first. That single rule gives both "get the current value" (take the first match) and "get the value as of sequence S" (take the first match with seq <= S) from the same search.

( mt_new seed ) → MemTable a handle: every copy is the same table, the last owner releases it ( mt_put m key val seq kind ) → v kind: MT_PUT / MT_DEL ( mt_find m key snap ) → i node index, 0 = miss ( mt_seek m key snap ) → i first node >= key ( mt_first m ) / ( mt_next m n ) → i ordered walk, 0 = end ( mt_key m n ) / ( mt_val m n ) → ( Vec u ) owned copies ( mt_seq m n ) / ( mt_kind m n ) → i ( mt_count m ) / ( mt_bytes m ) → i ( mt_free m ) → v early release (optional)

API

: i MT_MAXLVL 12

: i MT_PUT 1

: i MT_DEL 0

: MemTableImpl

: MemTableImpl {
    ( Vec u ) arena
    ( Vec i ) koff
    ( Vec i ) klen
    ( Vec i ) voff
    ( Vec i ) vlen
    ( Vec i ) nseq
    ( Vec i ) nkind
    ( Vec i ) nlvl
    ( Vec i ) links
    i level
    i count
    i rng
}

: MemTable { s ctl }

A MemTable is a handle on its state in an rcbox (stdlib/core/rcbox.nu): every copy is the same state, and the last owner releases it.

@ MemTable_share MemTable h → MemTable

@ MemTable_drop sink MemTable h → v

@ lsm_bytes_cmp_raw * u ap i aoff i alen * u bp i boff i blen → i

@ lsm_bytes_cmp ( Vec u ) a ( Vec u ) b → i

Compare two whole byte vectors.

@ mt_new i seed → MemTable

@ mt_free sink MemTable m → v

Let go of m now rather than at the end of its owner's scope.

@ _mt_iat ( Vec i ) v i idx → i

@ mt_seq MemTable m__h i node → i

@ mt_kind MemTable m__h i node → i

@ mt_count MemTable m__h → i

@ mt_bytes MemTable m__h → i

Bytes held: the arena plus the per-node integer rows. The store compares this against its memtable budget, so it has to count the index too — a million tiny keys is mostly index.

@ _mt_slice ( Vec u ) src i off i n → ( Vec u )

@ mt_key MemTable m__h i node → ( Vec u )

@ mt_val MemTable m__h i node → ( Vec u )

@ mt_put MemTable m__h ( Vec u ) key ( Vec u ) val i seq i kind → v

Append (key, val) as a new version. Both are COPIED into the arena; the caller keeps ownership of the vectors it passed in.

@ mt_seek MemTable m__h ( Vec u ) key i snap → i

First node with (key, seq) >= (probe, snap) — i.e. the newest version of key no newer than snap, or the next key after it. 0 = end.

@ mt_find MemTable m__h ( Vec u ) key i snap → i

The node holding key as of snap, or 0. The caller still has to ask mt_kind: a tombstone is a hit that means "deleted", not "not found".

@ mt_first MemTable m__h → i

@ mt_next MemTable m__h i node → i

@ mt_kptr MemTable m__h → *u

Borrowed view of a node's key, for merge comparisons that must not allocate. Valid until the next mt_put (which may move the arena).

@ mt_koff MemTable m__h i node → i

@ mt_klen MemTable m__h i node → i

---

wal.nu

packages/lsmdb/src/wal.nu — the write-ahead log.

The memtable lives in RAM, so between a write being acknowledged and the next flush there is nothing on disk that remembers it. The log is that memory: every write is appended here and fsynced BEFORE the memtable is touched, so a database that is killed — kill -9, power loss, a full disk mid-write — comes back holding exactly the writes it said yes to.

Record framing: [u32 crc32(payload)][u32 payload_len][payload] payload = [u64 seq][u8 kind][u32 klen][key][u32 vlen][value]

The checksum is what makes the tail case safe. A crash in the middle of an append leaves a short or half-written record, and replay MUST treat that as "this write never happened" rather than as corruption of the whole log or, worse, as a record with a garbage length. Replay therefore stops at the first record that is short, over-long or fails its CRC, keeps everything before it, and reports the truncation.

( wal_open path ) → !Wal String append mode ( wal_append w key val seq kind ) → !v String ( wal_sync w ) → !v String durability point ( wal_bytes w ) → i ( wal_reopen w path ) → !v String close, open again ( wal_close w ) → v early release (optional) ( wal_replay path m ) → !WalStat String → memtable ( wal_reset path ) → !v String truncate to empty

A Wal is a handle: every copy is the same log, and the last owner closes its file.

API

: WalImpl

: WalImpl {
    File f
    ( Vec u ) buf
    i bytes
    Crc32 crc
}

% Drop WalImpl { @ drop WalImpl w → v { ( file_close . w f ) } }

The log file is the one part the compiler does not manage: the last owner closes it (the buffer and the CRC table go with the drop glue).

: Wal { s ctl }

@ Wal_share Wal h → Wal

@ Wal_drop sink Wal h → v

: WalStat

: WalStat {
    i records
    i maxseq
    i truncated  // 1 if a torn tail was dropped
    i bytes
}

@ wal_open s path → !Wal String

@ wal_bytes Wal w__h → i

@ wal_reopen Wal w__h s path → !v String

Close the log file and open path again for appending — what a flush does once it has reset the log. If the reopen fails the log stays closed, and every append after it is an error rather than a lost write.

@ wal_close sink Wal w → v

Let go of w now rather than at the end of its owner's scope.

@ wal_append Wal w__h ( Vec u ) key ( Vec u ) val i seq i kind → !v String

@ wal_sync Wal w__h → !v String

The durability point. Returning from here means the OS has the bytes on the device — everything appended so far survives a power cut.

@ wal_truncate s path i len → !v String

Cut the log back to len bytes — the end of the last intact record.

Recovery MUST do this before appending again. A torn tail left in place is not merely untidy: replay stops there, so every write made after the crash would land behind bytes that the next replay refuses to walk past, and would be silently invisible from then on.

@ wal_reset s path → !v String

@ wal_replay s path MemTable m → !WalStat String

Replay every intact record into m. A missing log is an empty one — a database that has never been written to is not an error.

---

main.nu

lsmdb — a crash-safe embedded key/value store on the command line.

lsmdb put user:42 '{"name":"ada"}' # write (fsynced before it returns) lsmdb get user:42 # read lsmdb del user:42 # delete lsmdb scan --from user: --limit 20 # ordered range lsmdb load < dump.tsv # bulk import, key<TAB>value lines lsmdb get user:42 --at 7 # read the database as of write #7 lsmdb compact # merge tables, reclaim space lsmdb stats # what is on disk lsmdb bench -n 100000 # writes/s and reads/s here

The database is a directory (-d, $LSMDB_DIR, or ./lsmdb). Values are written and printed as raw bytes, so binary values survive the round trip; get exits 1 when the key is absent, which makes it usable in a shell conditional.

---

sst.nu

packages/lsmdb/src/sst.nu — the immutable on-disk table.

An SSTable is what a memtable becomes when it stops changing: entries sorted by (key ascending, sequence descending), cut into ~4 KiB blocks, each block CRC-32'd, with a block index and a Bloom filter at the tail and a fixed 48-byte footer that names them.

[data block 0][data block 1]…[index block][bloom block][footer 48B]

Data block payload — entries back to back, sorted: [u32 klen][u32 vlen][u64 seq][u8 kind][key bytes][value bytes] followed on disk by [u32 crc32(payload)]. A block is closed once its payload reaches SST_BLOCK bytes, so one oversized value still gets a block of its own rather than being rejected.

Index block payload — one entry per data block, carrying that block's LAST key: [u32 nblocks] then [u32 klen][key][u64 off][u32 payload_len]… The last key (not the first) is what makes the search correct when a key's versions straddle a block boundary: "first block whose last key

= probe" always lands on the block holding the NEWEST version, and the

reader then continues into the next block for the rest of the run.

Bloom block payload: [u32 nbits][u32 k][bit bytes]. A negative lookup that the filter rejects costs no disk read at all — the reason a get for an absent key does not have to touch every table in the tree.

Footer: [u64 index_off][u32 index_len][u64 bloom_off][u32 bloom_len] [u64 nentries][u64 max_seq]["LSMDBv1\n"]

Nothing here is read wholesale: open() loads only the index and the filter, and every get pulls exactly the one block it needs. A table larger than RAM is an ordinary table.

( sst_create path ) → !SstWriter String ( sst_add w key val seq kind ) → !v String keys must arrive sorted ( sst_finish w ) → !i String entries written ( sst_open path ) → !SstReader String ( sst_get r key snap ) → !SstHit String ( sst_cursor r ) / ( sc_seek ) / ( sc_next ) / ( sc_valid ) … ( sst_close r ) / ( sc_free c ) early release (optional)

SstWriter, SstReader and SstCursor are handles: every copy is the same object, and the last owner releases it — a writer or reader closes its file, a cursor lets go of the reader it walks (it holds a share, so a table outlives every cursor over it).

API

: i SST_BLOCK 4096

: i SST_HDR 17 // u32 klen + u32 vlen + u64 seq + u8 kind

: i SST_FOOTER 48

: i SST_BLOOM_BITS 10 // bits per key → ~1 % false positives at k=7

: i SST_BLOOM_K 7

: i SST_CACHE 32 // resident data blocks per open table

---

lsmdb.nu

packages/lsmdb/src/lsmdb.nu — the store: an LSM tree that survives being killed.

Writes go to the write-ahead log (fsynced), then into the memtable. When the memtable fills it is flushed into an immutable SSTable and the log is reset. Reads consult the memtable first, then the tables from newest to oldest, and stop at the first version they find — including a tombstone, which means "deleted here, look no further". Compaction merges every table into one, keeping only the newest version of each key and dropping tombstones.

Crash safety comes from the ORDER of those steps, not from hoping:

put → log append → fsync → memtable (acknowledged = durable) flush → write table → fsync → publish manifest (rename+dir fsync) → reset log compact → write merged table → fsync → publish manifest → unlink old

Every crash point in that sequence lands on a state the next open() reads correctly. A table written but not yet named by the manifest is an orphan file and its writes are still in the log; a manifest naming a table whose writes are ALSO still in the log replays them into the memtable at their original sequence numbers, where they shadow the identical versions in the table. Nothing is lost, nothing is doubled.

Sequence numbers are the other half of the design: every write gets one, versions of a key sort newest-first, and a read at sequence S sees the database exactly as it was after write S — a snapshot, for free.

( lsm_open dir ) → !Lsm String ( lsm_put db key val ) → !v String ( lsm_del db key ) → !v String ( lsm_get db key ) → !LsmGet String ( lsm_get_at db key snap ) → !LsmGet String time travel ( lsm_scan db from to limit snap ) → !LsmScan String ( lsm_flush db ) / ( lsm_compact db ) → !i String ( lsm_stats db ) → LsmStats ( lsm_close db ) → v early release (optional)

An Lsm is a handle: every copy is the same open database, and the last owner closes it — the log, every table file, the memtable. LsmGet and LsmScan are plain values; nothing here is released by hand.

API

: i LSM_MEMLIMIT 4194304 // 4 MiB of memtable before an auto-flush

: LsmImpl

: LsmImpl {
    String dir
    String walpath
    String manpath
    MemTable mem
    ( Vec String ) names  // table file names, NEWEST FIRST
    ( Vec SstReader ) tables  // parallel to names
    Wal wal
    i seq
    i nextfile
    i memlimit
    i durable
    i flushes
    i compactions
}

: Lsm { s ctl }

@ Lsm_share Lsm h → Lsm

@ Lsm_drop sink Lsm h → v

: LsmGet

: LsmGet {
    i found
    i seq
    ( Vec u ) val
}

: LsmStats

: LsmStats {
    i tables
    i entries
    i memcount
    i membytes
    i seq
    i filebytes
    i blockreads
    i filtered
}

@ lsm_get_free sink LsmGet g → v

Let go of g now rather than at the end of its owner's scope.

@ lsm_open s dir → !Lsm String

@ lsm_close sink Lsm db → v

Let go of db now rather than at the end of its owner's scope. The last owner closes the database: the log, every table, the memtable.

@ lsm_seq Lsm db__h → i

@ lsm_sync Lsm db__h → !v String

Force everything written so far to the device. Only needed after running with durability switched off — a bulk import that wants one fsync at the end instead of one per row.

@ lsm_set_durable Lsm db__h b on → v

@ lsm_set_memlimit Lsm db__h i n → v

@ lsm_put Lsm db__h ( Vec u ) key ( Vec u ) val → !v String

@ lsm_del Lsm db__h ( Vec u ) key → !v String

@ lsm_get Lsm db__h ( Vec u ) key → !LsmGet String

@ lsm_get_at Lsm db__h ( Vec u ) key i snap → !LsmGet String

The read path in full: memtable, then tables newest to oldest. The FIRST version found wins, and a tombstone counts as found — that is what stops an older table's stale value from resurrecting a deleted key.

: LsmIterImpl

: LsmIterImpl {
    MemTable mem  // a share: the memtable it walks stays alive with it
    i usemem
    i mnode
    ( Vec SstCursor ) curs
    i src  // -1 memtable, >=0 cursor index, -2 exhausted
    * SstCursorImpl cur  // cursor `src`, opened by the pick (curs owns it)
    i failed
    String err
}

: LsmIter { s ctl }

@ LsmIter_share LsmIter h → LsmIter

@ LsmIter_drop sink LsmIter h → v

: LsmScan

: LsmScan {
    ( Vec u ) keys
    ( Vec i ) koff
    ( Vec i ) klen
    ( Vec u ) vals
    ( Vec i ) voff
    ( Vec i ) vlen
    i count
}

@ lsm_scan_free sink LsmScan s → v

Let go of s now rather than at the end of its owner's scope.

@ lsm_scan_count LsmScan s → i

@ lsm_scan_key LsmScan s i k → ( Vec u )

@ lsm_scan_val LsmScan s i k → ( Vec u )

@ lsm_scan Lsm db__h ( Vec u ) from ( Vec u ) to i limit i snap → !LsmScan String

Every live key in [from, to) as of snap, in order. An empty from starts at the beginning; an empty to runs to the end; limit <= 0 means no limit.

@ lsm_flush Lsm db__h → !i String

Turn the memtable into a table. EVERY version is written, not just the newest — the memtable is the newest data in the database, and throwing away its history here would silently break snapshot reads that the tables themselves still support.

@ lsm_compact Lsm db__h → !i String

Merge every table into one, keeping only the newest version of each key and dropping tombstones. This is where space actually comes back: overwritten values and deleted keys stop existing.

It also throws history away, deliberately — a snapshot read older than this point can no longer be served, exactly as in LevelDB. Compaction is a choice to trade the past for space.

@ lsm_stats Lsm db__h → LsmStats