skyzh/mini-lsm

This system is an educational course repository for building a database storage engine in Rust, centered around an LSM-tree architecture. It provides a scaffolded starter project for students to implement core components like memtables, SSTables, and compaction strategies, alongside a complete reference implementation featuring MVCC transaction support and durable write-ahead logging. The project also includes a companion mdBook for instruction, CLI tools for interactive testing, and automation utilities for managing the course workflow and continuous integration.

12 changes.

This period established the Mini-LSM educational project, rebranding the course and configuring the Rust workspace with comprehensive starter scaffolds for LSM tree components. It simultaneously delivered a complete storage engine implementation featuring compaction strategies, WAL, MVCC, and optimized block iteration with key overlap compression.

15 changes.

This period focused on implementing a Multi-Version Concurrency Control (MVCC) storage engine with serializable transaction isolation and watermark-based snapshot management. It also introduced leveled and tiered compaction strategies across the main and starter crates, supported by comprehensive test suites and CLI tools for simulation and interaction.

The table module now includes a Bloom filter implementation to reduce unnecessary disk reads by checking key existence before accessing blocks. SsTableBuilder has been added to construct SSTable files, integrating block building, metadata encoding, and Bloom filter generation. Additionally, SsTableIterator provides a way to traverse SSTable contents, supporting seek-to-first and seek-to-key operations across blocks.

mini-lsm/src/table · high confidence

New executable binaries have been added to the project: \mini-lsm-cli\, an interactive REPL for managing an LSM tree (supporting put, get, delete, scan, flush, and compaction commands with configurable storage paths and compaction strategies), and \compaction-simulator\, a tool for visualizing and debugging leveled, tiered, and simple compaction behaviors with configurable parameters and reproducible random seeds.

mini-lsm-starter/src/bin · high confidence

The \mini-lsm-starter\ now includes initial scaffolding for Multi-Version Concurrency Control (MVCC) in the \src/mvcc\ module. This adds a \Transaction\ struct with stubbed methods for \get\, \scan\, \put\, \delete\, and \commit\, along with supporting iterator types (\TxnIterator\, \TxnLocalIterator\) that merge local and storage data. It also introduces a \Watermark\ struct to track active readers and determine retention snapshots. These components are currently unimplemented (returning \unimplemented!()\ or default values) and serve as a starting point for implementing MVCC logic.

mini-lsm-starter/src/mvcc · high confidence

The \mini-lsm-starter/src/iterators\ module now includes three new starter files: \concat\_iterator.rs\, \merge\_iterator.rs\, and \two\_merge\_iterator.rs\. These provide the structural scaffolding for \SstConcatIterator\, \MergeIterator\, and \TwoMergeIterator\ respectively, implementing the \StorageIterator\ trait with \unimplemented!()\ placeholders. This allows users to implement logic for concatenating non-overlapping SSTable iterators, merging multiple iterators of the same type using a binary heap, and merging two iterators of different types while handling key deduplication.

mini-lsm-starter/src/iterators · high confidence

The \mini-lsm-mvcc/src/iterators\ module now includes three new iterator implementations to support multi-level data traversal: \SstConcatIterator\ for sequentially traversing non-overlapping SSTable ranges, \MergeIterator\ for merging multiple iterators of the same type using a binary heap, and \TwoMergeIterator\ for merging two iterators of different types while prioritizing entries from the first source.

mini-lsm-mvcc/src/iterators · high confidence

The storage engine now supports two new compaction strategies: leveled and tiered. The leveled strategy (including a simple variant) manages data across multiple levels, triggering compactions based on L0 file counts or size ratios between levels to maintain sorted runs. The tiered strategy merges data across tiers based on space amplification ratios or size thresholds, helping to reduce read amplification. These changes introduce new controllers and task structures that allow the system to automatically reorganize SST files for better performance.

mini-lsm/src/compact · high confidence

The \mini-lsm-mvcc/src/compact\ module now includes three new compaction strategies: \LeveledCompactionController\, \SimpleLeveledCompactionController\, and \TieredCompactionController\. These controllers implement the logic for generating and applying compaction tasks based on specific policies (standard leveled, simple leveled with size ratios, and tiered with space amplification checks), allowing the storage engine to manage SSTable organization and reduce read/write amplification.

mini-lsm-mvcc/src/compact · high confidence

The book theme now includes Open Graph and Twitter Card meta tags in the page head. This ensures that when links to the book or its chapters are shared on social platforms, they display a consistent title, description, and a specific social preview image, improving discoverability and presentation in feeds.

mini-lsm-book/theme · high confidence

The \mini-lsm-starter/src/table\ module now includes new starter files for Bloom filters, SSTable building, and SSTable iteration. These additions provide the structural foundation (structs, traits, and method signatures) for students to implement core LSM-Tree table operations, including bloom filter logic, SSTable construction from key-value pairs, and iteration over SSTable contents.

mini-lsm-starter/src/table · high confidence

New files \builder.rs\ and \iterator.rs\ were added to the \mini-lsm-starter/src/block\ module, providing the \BlockBuilder\ and \BlockIterator\ structs with their method signatures. These files serve as a starting point for implementing block-level data storage and traversal, with core logic currently marked as unimplemented for the user to fill in.

mini-lsm-starter/src/block · high confidence

New starter files have been added to the \mini-lsm-starter/src/compact\ directory to support leveled and tiered compaction implementations. \leveled.rs\ and \simple\_leveled.rs\ provide the \LeveledCompactionController\ and \SimpleLeveledCompactionController\ structs along with their respective options and task definitions, serving as templates for leveled compaction logic. \tiered.rs\ introduces the \TieredCompactionController\ and associated structures for tiered compaction. All controllers currently contain \unimplemented!()\ stubs for \generate\_compaction\_task\ and \apply\_compaction\_result\, providing the necessary data structures and method signatures for students to implement the compaction algorithms.

mini-lsm-starter/src/compact · high confidence

A new wrapper binary (wrapper.rs) is introduced that re-exports the mini\_lsm crate under a specific module namespace, alongside symlinks pointing the compaction-simulator and mini-lsm-cli binaries to their counterparts in the mini-lsm-starter directory.

mini-lsm/src/bin · high confidence

The \mini-lsm-mvcc/src/block\ module now includes the core components for managing data blocks in the MVCC storage engine. A new \BlockBuilder\ handles the serialization of key-value pairs, utilizing key-prefix compression to optimize storage space and enforcing size limits to ensure blocks remain within configured bounds. Complementing this, a \BlockIterator\ provides efficient traversal of these blocks, supporting sequential access as well as binary-search-based lookups to seek to specific keys. These additions establish the foundational read and write paths for block-level operations within the storage layer.

mini-lsm-mvcc/src/block · high confidence

The \mini-lsm-mvcc\ crate introduces a new Multi-Version Concurrency Control (MVCC) storage engine built on the LSM-tree architecture. This change adds core components including timestamp-aware key handling, block and SSTable encoding/decoding, and a comprehensive iterator system that supports time-travel reads and range scans. It also implements MVCC-specific transaction management, write-ahead logging (WAL) with batch atomicity, and multiple compaction strategies (Leveled, Tiered, and Simple) to manage data versions and garbage collection.

mini-lsm-mvcc/src · high confidence

The \mini-lsm-mvcc/src/table\ module now includes the core components for reading and writing SSTables. This adds a Bloom filter implementation (\bloom.rs\) to optimize lookups, an SSTable builder (\builder.rs\) that constructs SSTable files with block metadata and Bloom filter indices, and an SSTable iterator (\iterator.rs\) that allows sequential traversal and key-based seeking across the table's blocks.

mini-lsm-mvcc/src/table · high confidence

The repository is initialized with the Apache 2.0 license for the starter code and solutions, alongside a dedicated license snippet file for source headers. The project configures the Rust toolchain to use the stable channel with rustfmt and clippy components, replacing a previous nightly configuration. Additionally, the repository includes a README outlining the Mini-LSM course structure, a solutions list for community contributions, and a gitignore file excluding IDE and build artifacts.

(repo-wide) · high confidence

The mini-lsm/src module now provides a complete LSM tree storage engine implementation. It introduces a unified compaction system supporting Leveled, Tiered, and Simple Leveled strategies via the CompactionController, along with a ForceFullCompaction option. The storage layer (LsmStorageInner) manages state transitions including memtable flushing, SSTable creation, and manifest recording for durability. A Write-Ahead Log (WAL) ensures atomicity for write batches and enables recovery. The engine supports Multi-Version Concurrency Control (MVCC) through dedicated modules (mvcc, txn, watermark) and provides robust iterator chains (LsmIterator, FusedIterator) for range scans with proper bound handling. Block-level integrity is enforced via checksums in both SST metadata and WAL records, with recovery logic that truncates incomplete tails.

mini-lsm/src · high confidence

The \mini-lsm-starter/src\ directory now contains the complete initial scaffold for the MiniLSM storage engine, providing the structural foundation for the course exercises. This includes the core storage interface in \lsm\_storage.rs\ (defining \MiniLsm\, \LsmStorageInner\, and \LsmStorageOptions\), the in-memory \MemTable\ backed by \crossbeam-skiplist\, and the on-disk \SsTable\ and \Block\ structures with serialization stubs. It introduces a modular compaction system in \compact.rs\ supporting Leveled, Simple Leveled, and Tiered strategies, alongside a \Manifest\ for durability tracking. The codebase also establishes the iterator hierarchy (\StorageIterator\, \LsmIterator\, \FusedIterator\) and a \Key\ abstraction layer, while adding \WAL\ (Write-Ahead Log) and \MVCC\ (Multi-Version Concurrency Control) skeletons to support Week 2 and Week 3 features.

mini-lsm-starter/src · high confidence

Added three new iterator types in the \mini-lsm/src/iterators\ module to support complex read paths: \SstConcatIterator\ for sequentially reading non-overlapping SSTables without seeking all at once, \MergeIterator\ for merging multiple iterators of the same type using a binary heap while preferring lower-index entries on key collisions, and \TwoMergeIterator\ for merging two iterators of different types, preferring entries from the first iterator when keys match.

mini-lsm/src/iterators · high confidence

The xtask utility now includes several new subcommands to support the course workflow: \Book\ builds and serves the mdbook documentation, \Ci\ runs the full CI pipeline (formatting, checking, testing, and linting), \Sync\ updates the starter repository and reference solution while performing semver checks, \Scheck\ validates the starter code, and \CopyTest\ copies test cases from the main project to the starter repo for specific weeks or days. These additions streamline the setup and maintenance of the learning environment.

xtask · high confidence

The block builder and iterator in \mini-lsm/src/block\ have been updated to support key overlap compression. The builder now stores only the delta (non-overlapping suffix) of each key relative to the previous one, reducing storage size for sorted keys. The iterator has been updated to reconstruct full keys by combining the stored overlap length and delta with the block's first key. This change modifies the on-disk block format and the in-memory iteration logic to leverage this compression.

mini-lsm/src/block · high confidence

The Mini-LSM course has been rebranded from "LSM in a Week" to "Mini-LSM — Build a Database Storage Engine in Rust" with a new description highlighting its hands-on database internals focus. The content is now licensed under CC BY-NC-SA 4.0, replacing the previous license. A new sponsor page has been added with custom CSS styling for sponsor cards and call-to-action links. The mdBook configuration now includes custom CSS, a GitHub repository link, and URL redirects to reorganize chapter paths. Additionally, a sitemap generation script has been added to maintain XML and TXT sitemaps for the site.

mini-lsm-book · high confidence

The MVCC module now enforces serializable isolation by tracking read and write sets per transaction and validating them at commit time against previously committed transactions. Additionally, a new watermark mechanism tracks active readers to determine the oldest retained snapshot timestamp, allowing the system to safely clean up committed transaction data that is no longer needed for consistency checks.

mini-lsm-mvcc/src/mvcc · high confidence

Added comprehensive test suite for Mini-LSM storage components; Added test directory placeholder; Expanded test coverage for MVCC, compaction, and durability.

The project has been upgraded to the Rust 2024 edition (rust-version 1.97.1) and updated to use Cargo resolver version 3. This change includes significant dependency updates across the workspace, such as bumping \clap\ to version 4.6, \rand\ to 0.10, \nom\ to 8, and \rustyline\ to 18, alongside updates to \anyhow\, \bytes\, and \console\. New workspace members \mini-lsm-starter\ and \mini-lsm-mvcc\ have been added to the Cargo workspace, and the \xtask\ utility has been updated to use \duct\ version 1.

(dependencies) · high confidence

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

• CAI 61 → 57 (-4.0)
• Rubric changed (rubric-2026.09.11 → rubric-2026.09.18) — scores are not directly comparable.

• Code Health 82 → 84 (+2.1)
• Architecture 100 → 100 (+0.0)
• Maturity 70 → 69 (-0.2)
• Readiness 44 → 35 (-8.8)
• Security 74 → 81 (+7.3)

• Hotspot: mini-lsm-mvcc/src/lsm_storage.rs (mini-lsm-mvcc/src/lsm_storage.rs)
• Hotspot: mini-lsm-starter/src/bin/compaction-simulator.rs (mini-lsm-starter/src/bin/compaction-simulator.rs)
• Hotspot: mini-lsm/src/lsm_storage.rs (mini-lsm/src/lsm_storage.rs)
• Off-boarding risk: anonymized user #1

• Inconsistent key type for MemTable.get between mini_lsm and mini_lsm_mvcc. The base library uses &[u8] while the MVCC version uses KeySlice. This forces callers to convert keys or maintain different code paths depending on which module they are using.
• Inconsistent key type for MemTable.put between mini_lsm and mini_lsm_mvcc. The base library uses &[u8] while the MVCC version uses KeySlice.
• Inconsistent key type for Wal.put between mini_lsm and mini_lsm_mvcc. The base library uses &[u8] while the MVCC version uses KeySlice.
• Inconsistent naming for key length retrieval. The base Key type uses len() while the MVCC Key type uses key_len(). This creates confusion for users switching between the two modules.
• Inconsistent naming for key reference retrieval. The base Key type uses raw_ref() while the MVCC Key type uses key_ref(). This is confusing as 'raw' usually implies unprocessed bytes, while 'key' might imply logical key. The semantics are unclear if they differ.
• Inconsistent parameter naming in Wal.put_batch. The base library names the parameter _data (implying unused or internal) while the MVCC version names it data. While functionally identical, this suggests a copy-paste inconsistency or differing intent regarding the parameter's usage.
• Inconsistent signature for BlockMeta.encode_block_meta. The base library version takes 3 arguments, while the MVCC version takes 4 (adding max_ts). This breaks API compatibility if these types are meant to be interchangeable or if the base version is a simplified interface.
• Off-boarding risk: anonymized user #1
• Outdated: clap
• Outdated: console
• Outdated: crc32fast
• Outdated: crossbeam-channel
• Outdated: crossbeam-epoch
• Outdated: duct
• Outdated: moka
• Outdated: rand
• Outdated: serde_json

• 2 commits — 2 feature/other, 0 fixes

• (repo) — 1 commit
• mini-lsm-book/src — 1 commit

• change: Merge pull request #234 from skyzh/sentinel/task-106-week1-freeze-question
• change: Move stale-snapshot prompt to Week 1 write path

Written by watchdog.canine.dev from the codebase's own history, inside the signed delivery this page is composed from.

skyzh/mini-lsm was measured the same way every project in this corpus was: the same rubric, at a pinned commit, with the result published in full. Point a surveyor at a repository you know and see whether you agree with it.