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_frees, 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 ( 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 )

API

: i MT_MAXLVL 12

: i MT_PUT 1

: i MT_DEL 0

: MemTable

: MemTable {
    ( 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
}

@ 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 * MemTable m → v

@ _mt_iat ( Vec i ) v i idx → i

@ mt_seq * MemTable m i node → i

@ mt_kind * MemTable m i node → i

@ mt_count * MemTable m → i

@ mt_bytes * MemTable m → 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 i node → ( Vec u )

@ mt_val * MemTable m i node → ( Vec u )

@ mt_put * MemTable m ( 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 ( 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 ( 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 → i

@ mt_next * MemTable m i node → i

@ mt_kptr * MemTable m → *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 i node → i

@ mt_klen * MemTable m i node → i

---

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.

---

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 )

API

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

: Lsm

: Lsm {
    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
}

: 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 LsmGet g → v

@ lsm_open s dir → !*Lsm String

@ lsm_close * Lsm db → v

@ lsm_seq * Lsm db → i

@ lsm_sync * Lsm db → !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 b on → v

@ lsm_set_memlimit * Lsm db i n → v

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

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

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

@ lsm_get_at * Lsm db ( 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.

: LsmIter

: LsmIter {
    * MemTable mem
    i usemem
    i mnode
    ( Vec * SstCursor ) curs
    i src  // -1 memtable, >=0 cursor index, -2 exhausted
    i failed
    String err
}

: 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 LsmScan s → v

@ 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 ( 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 → !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 → !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 → LsmStats

---

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_close w ) → v ( wal_replay path m ) → !WalStat String → memtable ( wal_reset path ) → !v String truncate to empty

API

: Wal

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

: 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 → i

@ wal_close * Wal w → v

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

@ wal_sync * Wal w → !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.

---

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 )

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