10 Jun 01:15

2d81da9

Latest

lsm-db v1.0.0 — Stable

The engine is done. v1.0.0 is the first stable release of lsm-db. The
public API is frozen until 2.0 and the on-disk format is frozen for the
1.x series. What you build against today keeps working for the life of the 1.x
line.

This release is the close of a milestone-by-milestone build: a single-run
foundation (0.2), multi-run levels with compaction and a frozen format (0.3),
crash-safe durability (0.4), bloom-filtered reads and a feature freeze (0.5), a
block cache and a head-to-head benchmark (0.6), hostile-input hardening and the
API freeze (0.7), and an alpha → beta → RC soak (0.8 – 0.9.5). 1.0 is the
definition-of-done audit and the cut.

What is lsm-db?

A log-structured merge-tree storage engine for Rust — the write path that powers
RocksDB, LevelDB, Cassandra, and ScyllaDB, packaged as a small, audited library.
Writes land in an in-memory memtable (optionally fronted by a write-ahead log);
when it fills, it is flushed to an immutable sorted run on disk; a background
thread compacts runs to keep reads fast and space bounded. It is the storage
layer the portfolio's database crates (txn-db, Hive DB) build on, and it stands
alone as an embedded key-value store.

The 1.0 surface

The common case is four calls — no builder, no generics to name:

use lsm_db::Lsm;

let db = Lsm::open("my-db")?;
db.put(b"user:1", b"alice")?;
assert_eq!(db.get(b"user:1")?, Some(b"alice".to_vec()));
db.delete(b"user:1")?;
for (key, value) in db.scan(b"user:".to_vec()..b"user;".to_vec())? {
    println!("{}", String::from_utf8_lossy(&key));
}
db.flush()?;
# Ok::<(), lsm_db::Error>(())

Tuning lives behind LsmConfig (write-buffer size, compaction trigger, block-cache
size); grouped atomic writes behind Batch. Two opt-in features extend the
engine without changing the surface: durability (every write hits a wal-db
log before acknowledgment, replayed on open — no acknowledged write lost across a
crash) and bloom (per-run filters let a point read skip any run that cannot
contain the key). The full reference, with a runnable example per item, is in
docs/API.md.

What the 1.0 audit changed

The definition-of-done audit was not a rubber stamp — it found and fixed real
issues:

Removed the inert framing feature and its unused pack-io optional
dependency. The flag gated no code, so shipping it into the frozen 1.0 surface
would have been dead weight that pulled a dependency for nothing. If typed
on-disk framing is implemented later, it returns as a new additive feature.
Corrected the documented MSRV to 1.85 — the declared, CI-verified minimum
(Rust 2024 edition's floor) — where release notes had drifted to 1.87.
Refreshed stale documentation: the README status blockquote still read
"pre-1.0" and listed durability and bloom filters as upcoming (both shipped in
0.4 and 0.5), and the feature tables still tagged the shipped bloom feature
"(planned)".

No code behaviour changed; the engine is identical to the 0.9.x line.

What's frozen

Public API — every item in docs/API.md — frozen until 2.0. No breaking
change in the 1.x series.
On-disk format — the sorted-run layout (LSMTBL01), the MANIFEST, the
bloom sidecar envelope, and the durability write-ahead log — frozen for 1.x.
A 1.0 database opens on any later 1.x release. The run format is specified in
docs/SSTABLE_FORMAT.md.

Quality bar

#![forbid(unsafe_code)] — zero unsafe in the crate.
#![deny(warnings)] and the full clippy restriction set, including no
unwrap/expect/panic/todo/dbg in library code.
Property tests against a reference model for every engine invariant; loom
model checks for the read-versus-compaction swap.
Adversarial tests that corrupt the run, manifest, WAL, and bloom sidecar and
assert the engine never panics or over-allocates (this caught and fixed a real
panic on a corrupt sidecar in 0.7).
Single- and multi-threaded soak tests across restarts, checked against a
BTreeMap model.
Benchmarks with locked 1.0 baselines (docs/PERFORMANCE.md); a >5% regression
on a tracked metric blocks a release.

Breaking changes

From 0.9.5: the framing feature flag is removed. It gated no code, so no
working build depended on it; enabling it was a no-op that only pulled an unused
dependency. Everything else is unchanged.

Verification

Green on Windows x86_64 and Linux (WSL2), Rust stable and MSRV 1.85; macOS via the
CI matrix:

cargo fmt --all -- --check
cargo clippy --all-targets -- -D warnings
cargo clippy --all-targets --all-features -- -D warnings
cargo test
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo +1.85 clippy --all-targets --all-features -- -D warnings
cargo +1.85 test --all-features
cargo build --examples --all-features
cargo build --benches --all-features
RUSTFLAGS="--cfg loom" cargo test --test loom_lsm
cargo deny check
cargo audit

All green.

Installation

[dependencies]
lsm-db = "1.0"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "1.0", features = ["durability", "bloom"] }

MSRV: Rust 1.85 (2024 edition).

Documentation

Full diff: v0.9.5...v1.0.0.
Changelog: CHANGELOG.md.

Assets 2

0 Join discussion

08 Jun 14:53

jamesgober

v0.9.5

249760e

v0.9.5 — Release candidate Pre-release

Pre-release

lsm-db v0.9.5 — Release candidate

Doc polish, last call before 1.0. v0.9.5 is the RC. No behaviour, no API, no
test change — just a documentation review pass that caught a few stale snippets
and one inaccurate claim. The engine is feature-complete, hardened, API-frozen,
and soak-tested; what stands between it and 1.0 is the Definition-of-Done audit
and the release cut.

What is lsm-db?

A log-structured merge-tree storage engine for Rust — the write path that powers
RocksDB, LevelDB, Cassandra, and ScyllaDB, packaged as a small, audited library.
It is the storage layer the portfolio's database crates (txn-db, Hive DB) build
on, so the durability and read/write contract is implemented and tested once.

What's new in 0.9.5

A documentation review of the full doc set found and fixed:

Three stale install snippets in docs/API.md that still showed old versions
(0.2, 0.4, 0.5) — now 0.9.
A "Tier 3 — extension traits / comparators (planned)" line in the tiered-API
section that contradicted the recorded decision to leave a pluggable comparator
out of the 1.0 surface. The section now states plainly that there is no Tier-3
seam: keys are ordered lexicographically and the engine is concrete (encode
keys to sort when a custom order is needed, as with sled / redb).

Nothing else changed — the code, tests, benchmarks, and on-disk format are
identical to 0.9.0.

Breaking changes

None. Documentation only.

Verification

Green on Windows x86_64 and Linux (WSL2), Rust stable and MSRV 1.87; macOS via the
CI matrix:

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo +1.87 clippy --all-targets --all-features -- -D warnings
cargo +1.87 test --all-features
RUSTFLAGS="--cfg loom" cargo test --test loom_lsm
cargo deny check
cargo audit

All green. The test suite is unchanged from 0.9.0.

What's next

1.0.0 — Stable. Definition-of-Done audit, the final release note, and
publication. The engine is feature-complete, hardened, API-frozen, and
soak-tested; 1.0 re-affirms the frozen public surface and the 1.x-frozen
on-disk format and cuts the release.

Installation

[dependencies]
lsm-db = "0.9"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.9", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.9.0...v0.9.5.
Changelog: CHANGELOG.md.

Assets 2

08 Jun 13:43

jamesgober

v0.9.0

8506df9

v0.9.0 — Beta Pre-release

Pre-release

lsm-db v0.9.0 — Beta

Concurrency under load, and the numbers locked. v0.9.0 is the beta in the run
to 1.0. The engine is feature-complete, hardened, and API-frozen; this release
broadens testing to a multi-threaded soak and freezes the benchmark baselines for
the 1.0 line. No behaviour or API change.

What is lsm-db?

What's new in 0.9.0

A multi-threaded soak

tests/concurrency_soak.rs runs six writer threads and three reader threads over
one shared engine while background compaction churns throughout. Each writer owns
a disjoint slice of the key space and follows a deterministic put-then-delete
pattern, so the final live set is exactly computable. The readers scan
continuously and must observe only strictly-ascending, duplicate-free results —
never a torn merge across the moving run set. When the writers finish, a full scan
must equal the exact union of what every writer left behind, and survive a reopen.
Under --all-features it runs with the write-ahead log and bloom filters active.

This complements the loom model of the read-versus-compaction swap (which proves
the protocol exhaustively for a small interleaving) with a large, real, threaded
workload.

Benchmark baselines locked

docs/PERFORMANCE.md now records its numbers as the locked baselines for the
1.0 line, confirmed at this beta. The hot paths are unchanged since the block
cache landed in 0.6, and a regression beyond 5% on any tracked metric blocks a
release. Representative single-threaded hot-path numbers (Windows x86_64,
release):

Operation	time
`get` hit (from a run)	~180 ns
`get` miss (from a run)	~97 ns
`put` into the memtable	~160 ns
full scan, 10k keys	~1.28 ms
negative lookup over 16 runs	~6.5 µs

The head-to-head against sled and redb is in
docs/PERFORMANCE.md.

Breaking changes

None. This release adds a test and documentation only.

Verification

Green on Windows x86_64 and Linux (WSL2), Rust stable and MSRV 1.87; macOS via the
CI matrix:

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo +1.87 clippy --all-targets --all-features -- -D warnings
cargo +1.87 test --all-features
RUSTFLAGS="--cfg loom" cargo test --test loom_lsm
cargo bench --bench lsm_bench
cargo deny check
cargo audit

All green. The default and --all-features suites add one concurrency-soak test
over 0.8.0; loom is unchanged at 2 model checks.

What's next

0.9.5 — RC. Critical fixes and documentation polish only.
1.0.0 — Stable. Definition-of-Done audit and publication. The engine is
feature-complete, hardened, and API-frozen; what stands between it and 1.0 is
the RC soak and the release cut.

Installation

[dependencies]
lsm-db = "0.9"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.9", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.8.0...v0.9.0.
Changelog: CHANGELOG.md.

Assets 2

08 Jun 12:54

jamesgober

v0.8.0

4a5e032

v0.8.0 — Alpha Pre-release

Pre-release

lsm-db v0.8.0 — Alpha

The soak begins. v0.8.0 is the alpha in the run to 1.0. The engine is
feature-complete, hardened, and API-frozen; this release adds no behaviour and no
public surface — it broadens coverage to a sustained, consumer-shaped workload
across restarts, the way a real consumer exercises an index. From here to 1.0 is
soak and polish.

What is lsm-db?

What's new in 0.8.0

A sustained workload across restarts

tests/soak.rs drives the engine the way a real consumer does: tens of thousands
of interleaved puts, overwrites, and deletes over a bounded key space, with a
small write buffer and a low compaction trigger so flushes and background
compactions run throughout — punctuated by close-and-reopen cycles standing in
for process restarts. After every phase the engine is checked, key for key and
over a full scan, against a BTreeMap reference model: no key lost, duplicated,
or resurrected across flushes, compactions, and reopens. Under --all-features
the same workload exercises the write-ahead log and bloom filters together, and a
companion test pins ranged scans to the model under churn.

Why no new API

The alpha phase is for integrating against real consumers and fixing what they
surface. The embedded key-value contract — open, put, get, delete, scan, flush,
plus tunable buffer / compaction / cache and the optional durability and bloom
features — already covers that surface, so nothing new was added. The API stays
frozen.

Breaking changes

None. This release adds tests only.

Verification

Green on Windows x86_64 and Linux (WSL2), Rust stable and MSRV 1.87; macOS via the
CI matrix:

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test
cargo test --all-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo +1.87 clippy --all-targets --all-features -- -D warnings
cargo +1.87 test --all-features
RUSTFLAGS="--cfg loom" cargo test --test loom_lsm
cargo deny check
cargo audit

All green. Counts at this tag:

Default features: 59 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 4 adversarial + 5 edge-case + 2 soak + 25 doctests.
--all-features: 74 unit + 6 bloom + 8 durability + 4 integration +
2 compaction + 6 recovery + 3 property + 6 adversarial + 5 edge-case +
2 soak + 25 doctests.
loom: 2 model checks.

What's next

0.9.0 — Beta. Bug fixes only; final benchmarks captured; broader testing.
0.9.5 — RC. Critical fixes and documentation polish only.
1.0.0 — Stable. Definition-of-Done audit and publication.

Installation

[dependencies]
lsm-db = "0.8"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.8", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.7.0...v0.8.0.
Changelog: CHANGELOG.md.

Assets 2

08 Jun 11:46

jamesgober

v0.7.0

4f8608a

v0.7.0 — Hardening & API freeze Pre-release

Pre-release

lsm-db v0.7.0 — Hardening & API freeze

Run at it with hostile input, then locked down. v0.7.0 puts the engine
through adversarial property tests and edge cases, adds a fuzz harness, and
freezes the public API — no breaking change until 2.0. The hardening pass
found and fixed a real panic. The on-disk format, frozen since 0.3, is unchanged.

What is lsm-db?

What's new in 0.7.0

Hostile-input hardening — and a real bug fixed

Library code must never panic on a corrupted or truncated on-disk file, nor be
tricked into an unbounded allocation by a hostile length prefix. New property
tests (tests/adversarial.rs) apply arbitrary corruption — bit-flips,
truncation, whole-file garbage — to the run file, the manifest, the write-ahead
log, and the bloom sidecar, then reopen the database, asserting only that it
returns a Result: Ok, or a corruption Err, never a panic.

That pass found a real panic. A bloom sidecar filled with arbitrary bytes
could postcard-deserialize into an internally-inconsistent bloom-lib filter
that then panicked (out-of-bounds) the moment it was queried. The fix wraps the
sidecar in a magic + CRC32C integrity envelope, so only bytes this crate actually
wrote — which always encode a self-consistent filter — are ever handed to the
deserializer. A corrupt or hostile sidecar fails the envelope and is discarded;
the run is consulted directly, with identical results.

Edge cases

tests/edge_cases.rs covers the awkward inputs: multi-megabyte values that span
many blocks, fifty un-compacted runs the read path must merge across, empty keys
and values, a 64 KiB key, and an I/O failure mid-flush (the database directory
removed under the engine) surfacing as an Error rather than a panic.

Fuzz harness

A standalone cargo-fuzz harness lives in fuzz/ (its own workspace, never
built by CI). Two targets — recover (the sorted-run parser) and sidecar (the
bloom sidecar) — drive arbitrary bytes through the public Lsm::open
parse/recovery path:

cargo +nightly fuzz run recover
cargo +nightly fuzz run sidecar

API freeze

The public API is frozen as of 0.7.0 — no breaking change until a 2.0 major.
The on-disk run format, manifest, sidecar, and write-ahead-log layouts are
frozen for 1.x. The remaining 0.x releases make only additive, non-breaking
changes; the full frozen surface is recorded in dev/ROADMAP.md.

Testing

Adversarial property tests over corrupted run / manifest / WAL / sidecar:
never panic, never over-allocate.
Edge-case tests for large values, many runs, unusual keys, and I/O failure.
The fuzz harness type-checks on Linux; all prior suites continue to pass.

Counts at this tag:

Default features: 59 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 4 adversarial + 5 edge-case + 25 doctests.
--all-features: 74 unit + 6 bloom + 8 durability + 4 integration +
2 compaction + 6 recovery + 3 property + 6 adversarial + 5 edge-case +
25 doctests.
loom (under RUSTFLAGS="--cfg loom"): 2 model checks.

All green on stable and MSRV (1.87) across Windows and Linux (WSL2); cargo fmt,
cargo clippy -D warnings, cargo doc -D warnings, cargo deny check, and
cargo audit clean. Zero unsafe (#![forbid(unsafe_code)]).

Breaking changes

None. This release is additive (tests, a fuzz harness, the sidecar integrity
envelope). The sidecar envelope changes the sidecar file format, but a sidecar is
a rebuildable hint — old sidecars are simply discarded and rewritten — so no
data is affected.

What's next

0.8.x → 0.9.x — Alpha / Beta → RC. Integrate against real consumers and fix
what they surface (additive only); broaden testing; capture final benchmarks;
doc polish.
1.0.0 — Stable. Definition-of-Done audit and publication. The engine is
feature-complete, hardened, and API-frozen; what stands between it and 1.0 is
soak time and the release cut.

Installation

[dependencies]
lsm-db = "0.7"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.7", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.6.0...v0.7.0.
Changelog: CHANGELOG.md.

Assets 2

08 Jun 09:09

jamesgober

v0.6.0

2357286

v0.6.0 — Optimization Pre-release

Pre-release

lsm-db v0.6.0 — Optimization

A block cache, and an honest comparison. v0.6.0 adds a shared cache of
decoded run blocks so repeat point reads do no I/O, and measures lsm-db
against sled and redb on the same workload — with the numbers recorded
honestly, gaps and all. No new public behaviour; one additive config knob.

What is lsm-db?

What's new in 0.6.0

Block cache

A point lookup that reaches a run decodes one data block — a positioned read, a
CRC32C check, and a parse. The new block cache (on by default, 8 MiB) keeps
recently-read decoded blocks so a repeat lookup over a hot working set returns
its block from cache with none of that work.

use lsm_db::{Lsm, LsmConfig};
# fn main() -> Result<(), Box<dyn std::error::Error>> {
// A 64 MiB cache; or `.block_cache_capacity(0)` to turn it off.
let db = Lsm::open_with(
    tempfile::tempdir()?.path(),
    LsmConfig::new().block_cache_capacity(64 << 20),
)?;
# let _ = db;
# Ok(())
# }

The cache is shared across an engine's runs and uses sharded CLOCK eviction —
the classic O(1) buffer-pool policy — so it adds no new runtime dependency.
Sequential scans and compaction read each block once and bypass the cache rather
than pollute it. A CI-enforced test asserts that a repeat lookup of the same key
reads zero data blocks, while a lookup with the cache disabled reads one.

Measured against `sled` and `redb`

A fair-shape comparison (identical keys, values, counts) over a 10,000-key set,
recorded in docs/PERFORMANCE.md:

Operation	`lsm-db`	`sled` 0.34	`redb` 2.6
Point read (hit)	125 ns	215 ns	156 ns
Bulk insert (10k)	11.0 ms	24.9 ms	22.9 ms
Full scan (10k)	1.80 ms	1.61 ms	0.39 ms

lsm-db leads point reads and bulk inserts — the LSM tree's home turf. redb's
in-place B-tree scan is faster than lsm-db's, which materialises a consistent
snapshot of the range. That is the one place lsm-db trails, and it is called
out plainly rather than buried.

Notes

Range scan still materialises a snapshot. Streaming it lazily would close
the scan gap but requires a fallible Scan iterator (block I/O would move
into iteration), which conflicts with the simplified-API mandate (today's
Scan is infallible) and the upcoming 0.7 API freeze. It is recorded as a 2.0
consideration; the snapshot semantics will not change within 1.x.
The cache only touches the point-read path, so there is no regression on the
write or scan paths.

Testing

CI-enforced cache behaviour: a repeat lookup reads zero data blocks; a lookup
with the cache disabled reads one.
Block-cache unit tests (hit/miss, distinct keys, eviction bound, re-insert,
disabled).
All prior suites pass with the cache on by default.

Counts at this tag:

Default features: 59 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 23 doctests.
--all-features: 72 unit + 6 bloom + 8 durability + 4 integration +
2 compaction + 6 recovery + 3 property + 23 doctests.
loom (under RUSTFLAGS="--cfg loom"): 2 model checks.

Breaking changes

None. LsmConfig::block_cache_capacity / block_cache_capacity_bytes and
DEFAULT_BLOCK_CACHE_CAPACITY are additive.

What's next

0.7.0 — Hardening + API freeze. Adversarial and corrupted-input tests
(truncated runs, garbage blocks — no panic, no over-allocation), edge cases
(disk-full during flush/compaction, very large values), cross-platform
re-verification; the public API formally frozen.

Installation

[dependencies]
lsm-db = "0.6"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.6", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.5.0...v0.6.0.
Changelog: CHANGELOG.md.

Assets 2

08 Jun 08:44

jamesgober

v0.5.0

524ffd3

v0.5.0 — Bloom filters & feature freeze Pre-release

Pre-release

lsm-db v0.5.0 — Bloom filters & feature freeze

The engine is feature-complete. v0.5.0 adds optional per-run bloom filters
that let a point read skip any run that cannot contain the key — a negative
lookup across many runs now reads no data blocks at all — and declares the
feature freeze. From here to 1.0 the work is optimization (0.6) and hardening
with the API frozen (0.7), not new surface.

What is lsm-db?

What's new in 0.5.0

Bloom-filtered point reads (`bloom` feature)

[dependencies]
lsm-db = { version = "0.5", features = ["bloom"] }

With the feature enabled, every sorted run carries a bloom filter over its keys.
A point lookup that misses the memtable checks each run's filter first and skips
the run entirely when the filter rejects the key — no data block is read. Filters
never produce false negatives, so a skip is always safe; a false positive merely
falls through to a normal, correct lookup. The public API is identical with or
without the feature, and it is a zero-cost no-op when off.

The win is on negative lookups across many runs. A benchmark of misses over 16
runs:

	negative lookup
without `bloom`	~280 µs
with `bloom`	~3 µs

A deterministic, CI-enforced test asserts that a negative lookup reads zero
data blocks under the feature.

Sidecar persistence keeps the frozen format intact

The on-disk run format has been frozen for the 1.x series since 0.3, so the
filter is not embedded in the run. It lives in a sidecar file
(<run>.sst.bloom, encoded with postcard), written before the manifest commit
so any run the manifest names is guaranteed to have its filter, loaded when the
run is reopened, and removed with the run during compaction. A sidecar is a pure
acceleration hint: if it is missing or corrupt, the run is consulted directly
with identical results, and orphan sidecars from a crashed compaction are
reclaimed on open.

# fn main() -> Result<(), Box<dyn std::error::Error>> {
let dir = tempfile::tempdir()?;
let db = lsm_db::Lsm::open(dir.path())?;
db.put(b"present", b"1")?;
db.flush()?;
// With `bloom`, this miss is answered from the filter — no data block read.
assert_eq!(db.get(b"absent")?, None);
# Ok(())
# }

Feature freeze

With bloom filters in place the engine is feature-complete. The public surface is
frozen against new features; 0.6 is optimization and 0.7 is hardening with the
API formally frozen.

Testing

A deterministic, CI-enforced check that a negative lookup reads zero data
blocks under bloom (and a positive lookup reads at least one).
Sidecar round-trip, missing-sidecar and corrupt-sidecar graceful-degradation,
orphan-sidecar reclamation, and sidecar/compaction lifecycle tests.
A negative-lookup benchmark across 16 runs.
All prior suites continue to pass with the feature on: compaction property
test, concurrent-writer stress, manifest crash recovery, durability recovery,
and the loom read-versus-compaction model.

Counts at this tag:

Default features: 54 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 23 doctests.
--all-features: 67 unit + 6 bloom + 8 durability + 4 integration +
2 compaction + 6 recovery + 3 property + 23 doctests.
loom (under RUSTFLAGS="--cfg loom"): 2 model checks.

Breaking changes

None. The bloom feature and its dependencies (bloom-lib, postcard) are
additive.

A note on the pluggable comparator

The roadmap listed a pluggable comparator for this phase. It is dropped from
the 1.0 scope: it would require threading a generic comparator parameter
through every public type (Lsm<C>, Scan, …), which conflicts with the
crate's simplified-API mandate. Lexicographic byte ordering covers the common
case — callers encode keys to sort — matching sled and redb. The decision is
recorded in dev/ROADMAP.md.

What's next

0.6.0 — Optimization. Profile the flush, compaction, and read paths;
block cache for hot run blocks; batched group commit on the durable path; lazy
scan streaming. Comparative benchmarks vs sled / redb.
0.7.0 — Hardening + API freeze. Adversarial and corrupted-input tests,
edge cases (disk-full, huge values), cross-platform re-verification; the API
formally frozen.

Installation

[dependencies]
lsm-db = "0.5"
# Crash-safe writes and/or bloom-filtered point reads:
lsm-db = { version = "0.5", features = ["durability", "bloom"] }

MSRV: Rust 1.87 (2024 edition).

Documentation

Full diff: v0.4.0...v0.5.0.
Changelog: CHANGELOG.md.

Assets 2

07 Jun 17:17

jamesgober

v0.4.0

d723333

v0.4.0 — Durability and Crash Recovery Pre-release

Pre-release

lsm-db v0.4.0 — Durability and Crash Recovery

No acknowledged write is lost across a crash. v0.4.0 adds an optional
write-ahead log: under the durability feature, every write is logged and
fsynced before it is acknowledged, and the log is replayed on open — so a write
survives a crash even if it never reached a flush. The feature is additive and
the public API is unchanged; with it off, the engine behaves exactly as in 0.3.

What is lsm-db?

What's new in 0.4.0

The `durability` feature

[dependencies]
lsm-db = { version = "0.4", features = ["durability"] }

With it enabled, each put / delete / write is appended to a wal-db
write-ahead log and made durable before the call returns; a batch is logged as a
single atomic record. On open, the log is replayed into the memtable and
checkpointed to a run, so recovery only ever replays the writes since the most
recent flush.

# fn main() -> Result<(), Box<dyn std::error::Error>> {
let dir = tempfile::tempdir()?;
{
    let db = lsm_db::Lsm::open(dir.path())?;
    db.put(b"k", b"v")?;   // durable before this returns (with `durability`)
    // process exits here — no explicit flush
}
let db = lsm_db::Lsm::open(dir.path())?;
assert_eq!(db.get(b"k")?, Some(b"v".to_vec())); // recovered from the log
# Ok(())
# }

The same source compiles and runs with or without the feature: the durability
layer is a zero-sized no-op when it is off, so the non-durable path — ideal for
caches and tests — pays nothing.

How recovery stays consistent

A flush makes the buffered writes durable in a sorted run, so the log that held
them is rotated (emptied) at that point. Combined with the manifest-based run
recovery from 0.3, a crash at any moment recovers to a consistent state: flushed
runs come from the manifest, and the un-flushed tail comes from the log. Because
a clean Drop does not flush — it only stops the background compactor — the
recovery tests reproduce exactly the un-flushed-but-acknowledged state a crash
leaves, then reopen and check every write is present.

Testing

Crash recovery (under --all-features): un-flushed writes, overwrites,
deletes, and a 200-op batch all survive drop-without-flush and reopen; a
1,000-write / 200-delete workload recovers to the exact live set; reopening
twice does not duplicate; writes continue and stay durable after recovery.
Log codec: encode/decode round-trips, and rejection of truncated or
trailing-garbage records.
The 0.3 suites — compaction property test, concurrent-writer stress, manifest
crash recovery, corruption detection, and the loom read-versus-compaction
model — all run again with durability on.

Counts at this tag:

Default features: 54 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 23 doctests.
--all-features: 59 unit + 8 durability + 4 integration + 2 compaction +
6 recovery + 3 property + 23 doctests.
loom (under RUSTFLAGS="--cfg loom"): 2 model checks.

All green on stable and MSRV (1.85) across Linux, macOS, and Windows; cargo fmt,
cargo clippy -D warnings, cargo doc -D warnings, cargo deny check, and
cargo audit clean. Zero unsafe (#![forbid(unsafe_code)]).

What's next

0.5.0 — Bloom filters + feature freeze. Per-run bloom-lib filters under
the bloom feature to skip runs that cannot contain a key on negative
lookups, plus a pluggable comparator for custom key ordering.

Installation

[dependencies]
lsm-db = "0.4"
# or, for crash-safe writes:
lsm-db = { version = "0.4", features = ["durability"] }

MSRV: Rust 1.85 (2024 edition).

Documentation

Full diff: v0.3.0...v0.4.0.
Changelog: CHANGELOG.md.

Assets 2

07 Jun 05:17

jamesgober

v0.3.0

46c9cb9

v0.3.0 — Levels, Compaction, and a Frozen Format Pre-release

Pre-release

lsm-db v0.3.0 — Levels, Compaction, and a Frozen Format

The real engine. v0.3.0 turns the single-run foundation into a proper
log-structured merge store: flushes append immutable sorted runs, reads merge
across the memtable and every run, and a background thread compacts runs into one
when they accumulate — concurrent with reads and writes. A manifest makes the run
set crash-recoverable, and the on-disk format is now frozen for the 1.x
series.

The Tier-1 API is unchanged; the only public addition is configuration.

What is lsm-db?

What's new in 0.3.0

Multiple runs and a newest-wins merge

Each flush now writes a new immutable run instead of rewriting one. Point reads
consult the memtable, then each run from newest to oldest; range
scans merge the memtable and every run into one
ascending stream, with the newest source winning per key and tombstones resolved
away. The merge surfaces a corruption error rather than silently truncating if a
run's block fails its checksum.

# fn main() -> Result<(), Box<dyn std::error::Error>> {
# let db = lsm_db::Lsm::open(tempfile::tempdir()?.path())?;
db.put(b"k", b"first")?;
db.flush()?;          // run 1
db.put(b"k", b"second")?;
db.flush()?;          // run 2 — newer
assert_eq!(db.get(b"k")?, Some(b"second".to_vec())); // newest wins
# Ok(())
# }

Background compaction

A dedicated thread merges the runs into one when their count reaches the
configured trigger (default four). The expensive merge runs with no lock
held; only the final swap takes the engine lock, so compaction never blocks
reads or writes for the duration of the merge. A run superseded by compaction is
reference counted — its file is deleted only once the last reader still holding it
has finished. Dropping the Lsm stops and joins the compactor.

use lsm_db::{Lsm, LsmConfig};
# fn main() -> Result<(), Box<dyn std::error::Error>> {
// Compact whenever six runs accumulate.
let db = Lsm::open_with(
    tempfile::tempdir()?.path(),
    LsmConfig::new().compaction_trigger(6),
)?;
# let _ = db;
# Ok(())
# }

A frozen, block-structured on-disk format

Runs are now block-structured: data blocks (~4 KiB) with a block index, a
per-block CRC32C verified on read, and a per-index CRC32C in the footer.
Tombstones are stored on disk so a deletion can mask older runs until compaction
resolves it. Opening a run reads only the footer and index; values are read one
block at a time with a single positioned read.

The byte layout is frozen for the 1.x series and specified in
docs/SSTABLE_FORMAT.md.

Crash recovery via a manifest

A MANIFEST file records the live runs in recency order and the next sequence
number, rewritten atomically on every flush and compaction. It is the single
source of truth: on open, the engine opens exactly the runs it names and reclaims
any temporary file or run file it does not — the orphans a crash mid-flush or
mid-compaction leaves behind. Because both runs and the manifest are installed by
atomic rename, recovery always lands on a consistent state.

Testing

Property test: a randomized put/delete workload against a small,
frequently-compacting engine matches a BTreeMap model exactly — no live key
lost or duplicated through compaction.
Concurrency stress: four writer threads and a scanning reader against an
engine with a low compaction trigger; the final state is exact and scans are
always strictly increasing (no torn or duplicated keys).
Crash recovery: ungraceful exit, stale temporary file, orphan run, missing
run, and corrupted block are all handled correctly.
loom model: exhaustive interleavings of a reader versus a compaction swap
confirm a reader never observes a torn merge, for both a live value and a
deletion.

Counts at this tag:

Default features: 54 unit + 4 integration + 2 compaction + 6 recovery +
3 property + 23 doctests.
loom (under RUSTFLAGS="--cfg loom"): 2 model checks.

What's next

0.4.0 — Durability + crash recovery. A wal-db-backed write path under the
durability feature: log before the memtable insert, and replay the log on
open so no acknowledged write is lost across a crash.

Installation

[dependencies]
lsm-db = "0.3"

MSRV: Rust 1.85 (2024 edition).

Documentation

Full diff: v0.2.0...v0.3.0.
Changelog: CHANGELOG.md.

Assets 2

06 Jun 22:10

jamesgober

v0.2.0

62b5257

v0.2.0 — Foundation Pre-release

Pre-release

lsm-db v0.2.0 — Foundation

The first working engine. v0.2.0 turns the scaffold into a real
log-structured merge store: writes buffer in a sorted in-memory memtable and
flush to an immutable, fsynced sorted run on disk, reads check the buffer and
fall through to the run, and deletes are tombstones that resolve away on flush.
The Tier-1 API — open, put, get, delete, scan — is locked in and
tested against a reference model. Flushed data survives reopening.

This is a pre-1.0 foundation release. The on-disk format is not frozen yet
(that happens in 0.3 alongside multi-level compaction), and un-flushed writes are
not yet crash-safe (write-ahead logging lands in 0.4).

What is lsm-db?

What's new in 0.2.0

The `Lsm` engine — the Tier-1 API

The whole common case is five calls over one type. Keys and values are arbitrary
bytes; keys are ordered lexicographically.

use lsm_db::Lsm;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let db = Lsm::open("my-db")?;

    db.put(b"user:1", b"alice")?;
    assert_eq!(db.get(b"user:1")?, Some(b"alice".to_vec()));

    db.delete(b"user:1")?;
    assert_eq!(db.get(b"user:1")?, None);
    Ok(())
}

Lsm is Send + Sync and every method takes &self, so one engine can be
shared across threads behind an Arc — readers run in parallel, writes
serialize, and a scan is a consistent snapshot that never blocks writers.

Range scans

scan merges the buffer and the on-disk run into one ascending stream over any
Vec<u8> range. The returned Scan is an ExactSizeIterator and
DoubleEndedIterator.

# fn main() -> Result<(), Box<dyn std::error::Error>> {
# let db = lsm_db::Lsm::open(tempfile::tempdir()?.path())?;
db.put(b"a", b"1")?;
db.put(b"b", b"2")?;
db.put(b"c", b"3")?;

// Half-open range [a, c).
let pairs: Vec<_> = db.scan(b"a".to_vec()..b"c".to_vec())?.collect();
assert_eq!(pairs, vec![(b"a".to_vec(), b"1".to_vec()), (b"b".to_vec(), b"2".to_vec())]);

// Prefix scan, full scan, reverse — all work.
assert_eq!(db.scan(..)?.count(), 3);
# Ok(())
# }

Grouped, atomic writes with `Batch`

A Batch collects puts and deletes and applies them under a single lock
acquisition, so concurrent readers see either none or all of the group.

# fn main() -> Result<(), Box<dyn std::error::Error>> {
use lsm_db::Batch;
# let db = lsm_db::Lsm::open(tempfile::tempdir()?.path())?;
let mut batch = Batch::new();
batch.put(b"a", b"1");
batch.put(b"b", b"2");
batch.delete(b"c");
db.write(batch)?;
# Ok(())
# }

Tunable write buffer with `LsmConfig`

Tier-2 tuning controls how large the memtable grows before it flushes. The
default is 4 MiB (DEFAULT_MEMTABLE_CAPACITY).

use lsm_db::{Lsm, LsmConfig};
# fn main() -> Result<(), Box<dyn std::error::Error>> {
let db = Lsm::open_with(
    tempfile::tempdir()?.path(),
    LsmConfig::new().memtable_capacity(64 * 1024),
)?;
# let _ = db;
# Ok(())
# }

Durable, atomic flush

A flush writes the new run to a temporary file, fsyncs it, drops the old run's
handle, and atomically renames the new file into place. A crash leaves either the
old run or the new one, never a torn file, and a leftover temporary file from an
interrupted flush is discarded on the next open. On-disk reads use positioned
reads (pread on Unix, seek_read on Windows) so concurrent readers share one
file handle without seeking over each other.

Error type integrated with `error-forge`

Every fallible call returns Result<T, Error>. Error implements
error_forge::ForgeError (kind / caption / is_fatal) and exposes the
underlying io::Error as its source. Corruption is the only fatal variant.

Testing

Property tests (proptest) check get and scan against a BTreeMap
reference model across three memtable sizes (in-memory, frequent flush, flush
every write), plus a flush-and-reopen check and randomized sub-range scans.
Integration tests cover multi-flush workloads with overwrites and deletes,
reopen, atomic batches, and concurrent readers running alongside a writer.
criterion benchmarks cover point write, point read (hit and miss), and scan.

Counts at this tag:

Default features: 43 unit + 4 integration + 3 property + 21 doctests.
--all-features: identical (the optional integrations add no tested code yet).

What's next

0.3.0 — Levels + compaction + format freeze. Multiple sorted-run levels, a
merge-iterator across them, background compaction concurrent with reads and
writes, and the byte-level on-disk format specified and frozen for 1.x.

Installation

[dependencies]
lsm-db = "0.2"

MSRV: Rust 1.85 (2024 edition).

Documentation

Changelog: CHANGELOG.md.

Assets 2

Releases: jamesgober/lsm-db

v1.0.0 — Stable API

lsm-db v1.0.0 — Stable

What is lsm-db?

The 1.0 surface

What the 1.0 audit changed

What's frozen

Quality bar

Breaking changes

Verification

Installation

Documentation

Uh oh!

v0.9.5 — Release candidate

lsm-db v0.9.5 — Release candidate

What is lsm-db?

What's new in 0.9.5

Breaking changes

Verification

What's next

Installation

Documentation

Uh oh!

v0.9.0 — Beta

lsm-db v0.9.0 — Beta

What is lsm-db?

What's new in 0.9.0

A multi-threaded soak

Benchmark baselines locked

Breaking changes

Verification

What's next

Installation

Documentation

Uh oh!

v0.8.0 — Alpha

lsm-db v0.8.0 — Alpha

What is lsm-db?

What's new in 0.8.0

A sustained workload across restarts

Why no new API

Breaking changes

Verification

What's next

Installation

Documentation

Uh oh!

v0.7.0 — Hardening & API freeze

lsm-db v0.7.0 — Hardening & API freeze

What is lsm-db?

What's new in 0.7.0

Hostile-input hardening — and a real bug fixed

Edge cases

Fuzz harness

API freeze

Testing

Breaking changes

What's next

Installation

Documentation

Uh oh!

v0.6.0 — Optimization

lsm-db v0.6.0 — Optimization

What is lsm-db?

What's new in 0.6.0

Block cache

Measured against sled and redb

Notes

Testing

Breaking changes

What's next

Installation

Documentation

Uh oh!

v0.5.0 — Bloom filters & feature freeze

lsm-db v0.5.0 — Bloom filters & feature freeze

What is lsm-db?

What's new in 0.5.0

Bloom-filtered point reads (bloom feature)

Sidecar persistence keeps the frozen format intact

Measured against `sled` and `redb`

Bloom-filtered point reads (`bloom` feature)

The `durability` feature