Preface

Banner Banner

This course teaches you how to build a simple LSM-tree storage engine in Rust.

What Is an LSM Tree, and Why Use One?

Log-structured merge trees are data structures for maintaining key-value pairs. They are widely used as the underlying storage engines in distributed database systems such as TiDB and CockroachDB. RocksDB, which is based on LevelDB, is an LSM-tree storage engine that provides a rich key-value interface and is used in many production systems.

Generally speaking, an LSM tree is an append-friendly data structure. It is easiest to understand by comparing it with other key-value data structures, such as red-black trees and B-trees. In those structures, updates happen in place: when you update the value associated with a key, the engine overwrites the value in its original memory or disk location. In an LSM tree, however, writes—including insertions, updates, and deletions—are applied to persistent storage lazily. The engine batches these operations into sorted-string table (SST) files and writes them to disk. Once written, SST files are immutable. A background process called compaction merges these files and applies their updates and deletions.

This architectural design makes LSM trees easy to work with.

Data on persistent storage is immutable, which makes concurrency control more straightforward. Compaction can be offloaded to remote servers, and data can be stored and served directly from cloud-native storage systems such as S3.
Changing the compaction algorithm lets the storage engine balance read, write, and space amplification. By tuning compaction parameters, we can optimize the LSM tree for different workloads.

This course will teach you how to build an LSM-tree-based storage engine in the Rust programming language.

Prerequisites

You should know the basics of the Rust programming language. Reading The Rust Programming Language is sufficient.
You should understand the basic concepts behind key-value storage engines, including why persistence requires a more complex design. If you have no prior experience with database or storage systems, consider implementing Bitcask through the PingCAP Talent Plan.
You do not need to know how an LSM tree works, but we recommend reading an introduction, such as an overview of LevelDB. This background will familiarize you with concepts such as mutable and immutable memtables, SSTs, compaction, and write-ahead logs (WALs).

What Should You Expect from This Course?

After completing this course, you should have a deep understanding of how an LSM-based storage system works and hands-on experience designing one. You will learn the tradeoffs involved and how to choose a design that meets the requirements of a particular workload. Drawing on the author’s experience with several LSM-based systems, the course covers the essential implementation details and design choices found in modern storage systems such as RocksDB. You can apply what you learn in both industry and academia.

Structure

The course consists of several parts, or weeks. Each week has seven chapters, and you can complete each chapter in two to three hours. The first six chapters of each week guide you through building a working system. The final chapter is a snack time chapter in which you implement a few approachable improvements to what you built over the previous six days. Each chapter includes required tasks, Test Your Understanding questions, and bonus tasks.

Testing

We provide a comprehensive test suite and several command-line tools to help you validate your solution. The test suite is not exhaustive, so passing every test does not guarantee that your solution is completely correct. You might need to fix earlier bugs while implementing later parts of the system. Think carefully about your implementation, especially when it involves multithreaded operations and potential race conditions.

Solution

The main Mini-LSM repository contains a reference solution that implements all functionality required by the course. We also maintain a solution-checkpoint repository in which each commit corresponds to a chapter.

Keeping the checkpoint repository synchronized with the Mini-LSM course is challenging because every bug fix or new feature must be applied to every relevant commit. Consequently, this repository might not use the latest starter code or include the course’s latest features.

TL;DR: We do not guarantee that the solution-checkpoint repository contains a correct solution, passes every test, or has accurate documentation comments. For the complete reference implementation, see the mini-lsm crate in the main repository.

If you get stuck or need help determining where to implement functionality, you can consult the checkpoint repository. Compare adjacent commits to see what changed in each chapter. Because you will modify some functions several times during the course, these diffs can clarify exactly what each chapter expects you to implement.

You may access the solution checkpoint repo at https://github.com/skyzh/mini-lsm-solution-checkpoint.

Feedback

Your feedback is greatly appreciated. In 2024, we rewrote the entire course from scratch in response to student feedback. Please share your learning experience and help us continue improving the course in the Discord community.

Here is the longer story behind the rewrite. The original course offered general guidance: students started with an empty directory and implemented their own designs from our specifications. A minimal test suite checked the resulting behavior. This approach proved too open-ended and created significant obstacles to learning. Without an overview of the complete system—and with instructions that were sometimes vague—students found it difficult to understand why a design decision was made or what they needed to accomplish. Some sections were also too dense to fit comfortably into a single chapter.

We therefore redesigned the course to provide a gentler learning curve and clearer goals. The original one-week course is now split into two weeks: the first covers storage formats, and the second takes a deep dive into compaction. A third part covers MVCC. We hope you find the course interesting and useful in your studies and career. We thank everyone who commented on Feedback after coding day 1 and Hello, when is the next update plan for the course?—your feedback greatly helped us improve the course.

License

The source code of this course is licensed under Apache 2.0, while the book is licensed under CC BY-NC-SA 4.0.

Will this course be free forever?

Yes! Everything that is publicly available now will remain free and receive ongoing updates and bug fixes. We might also provide paid code-review and office-hours services. As of 2024, we had no plans to finish the downloadable-content portion (the rest of your life chapters) and had not decided whether it would be publicly available.

Community

You may join skyzh’s Discord server and study with the mini-lsm community.

Get Started

Next, read the Mini-LSM Course Overview for an introduction to the LSM structure.

About the Author

At the time of writing in early 2024, Chi held a master’s degree in computer science from Carnegie Mellon University and a bachelor’s degree from Shanghai Jiao Tong University. He had worked on several database systems, including TiKV, AgateDB, TerarkDB, RisingWave, and Neon. Beginning in 2022, he served for three semesters as a teaching assistant for CMU’s Database Systems course, working on the BusTub educational system. There, he added new features and challenges to the course, including the redesigned query execution project and the demanding multi-version concurrency control project. He also maintains the RisingLight educational database system. Chi is interested in exploring Rust’s role in the database world. If you share that interest, see his earlier courses on building a vectorized expression framework, type-exercise-in-rust, and a vector database, write-you-a-vector-db.

Your feedback is greatly appreciated. Welcome to join our Discord Community.
Found an issue? Create an issue / pull request on github.com/skyzh/mini-lsm.
mini-lsm-book © 2022-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.

Mini-LSM Course Overview

Course Structure

Course Overview

This course has three parts, or weeks. In the first week, you will focus on the structure and storage format of an LSM storage engine. In the second week, you will explore compaction in depth and add persistence to the storage engine. In the third week, you will implement multiversion concurrency control (MVCC).

Follow Environment Setup to prepare your development environment.

Overview of LSM

An LSM storage engine generally has three components:

A write-ahead log that persists recent data for recovery.
SSTs on disk that form the LSM-tree structure.
Memtables in memory that batch small writes.

The storage engine generally provides the following interfaces:

Put(key, value): Stores a key-value pair in the LSM tree.
Delete(key): Removes a key and its corresponding value.
Get(key): Retrieves the value associated with a key.
Scan(range): Retrieves a range of key-value pairs.

It may also provide an operation that establishes a persistence boundary:

Sync(): Ensures that all preceding operations have been persisted to disk.

Some engines combine Put and Delete into a single operation called WriteBatch, which accepts a batch of updates.

The overview diagrams assume a leveled compaction layout, which is common in production systems. In Week 2, you will implement and compare several compaction strategies.

Write Path

The LSM write path has four steps:

Write the key-value pair to the write-ahead log so that it can be recovered after a crash.
Write the key-value pair to the mutable memtable. After steps 1 and 2 are complete, the engine can report that the write has completed.
In the background, freeze a full mutable memtable, making it immutable, and flush it to disk as an SST file.
Also in the background, compact files from one or more levels into lower levels. This maintains the shape of the LSM tree and limits read amplification.

Read Path

To read a key, the engine:

Probes the memtables from newest to oldest.
If the memtables do not determine the result, searches the SSTs in the LSM tree.

There are two types of reads: lookups and scans. A lookup finds one key in the LSM tree, whereas a scan iterates over all keys within a range. The course covers both.

Environment Setup

The starter code and reference solution are available in the Mini-LSM repository.

Install Rust

See https://rustup.rs for more information.

Clone the Repository

git clone https://github.com/skyzh/mini-lsm

Open the Starter Code

cd mini-lsm/mini-lsm-starter
code .

Install Tools

The repository pins the required Rust toolchain in rust-toolchain.toml. If you use rustup, Cargo will select and install that toolchain automatically.

cargo x install-tools

Run the Tests

cargo x copy-test --week 1 --day 1
cargo x scheck

You are now ready to begin Week 1: Mini-LSM.

Week 1 Overview: Mini-LSM

Chapter Overview

In the first week, you will build the storage engine’s core formats, read path, and write path. By the end of its seven chapters, you will have a working LSM-based key-value store.

Chapter	Before	After
Day 1: Memtable	The storage interfaces are stubs.	The engine supports in-memory point reads, writes, deletes, and memtable freezing.
Day 2: Merge Iterator	The engine can query one key at a time.	It can scan an ordered range across multiple memtables.
Day 3: Block Encoding	All data structures are in memory.	Key-value pairs can be encoded into and decoded from an on-disk block format.
Day 4: SST Encoding	The engine has individual blocks.	Blocks form seekable SSTs whose data is loaded on demand and cached.
Day 5: Read Path	Memtables and SSTs have separate iterators.	Point reads and scans produce one logical view across both.
Day 6: Write Path	The test harness creates SSTs for you.	The engine flushes frozen memtables to L0 and filters irrelevant SSTs.
Day 7: SST Optimizations	The engine is correct but performs avoidable I/O and stores repeated key bytes.	Bloom filters reduce point-read I/O, and prefix encoding makes blocks smaller.

How to Use This Week

The implementation is the laboratory in which you explore the design. Passing the tests is an important checkpoint, but it is not the final learning goal: the provided tests cannot cover every boundary condition, malformed input, or concurrent execution.

For each chapter:

Read the capability and core-invariant sections before writing code.
Predict the behavior of the small examples without running them.
Implement the tasks and run the chapter tests.
Answer the correctness questions with evidence from your implementation. When a question asks what can go wrong, construct a minimal counterexample or test.
Compare with the reference solution only after making a serious attempt. A different implementation can still be correct if it preserves the same invariants.

You may use an LLM or other coding tools, but treat generated code as an untrusted contribution: identify the invariants first, review the result against them, and add tests that exercise behavior not covered by the supplied suite. The ability to explain, challenge, and validate an implementation matters more than who typed it.

At the end of the week, your storage engine should be able to handle get, scan, put, and delete requests. The remaining work is to persist the LSM state across restarts and organize SSTs on disk more efficiently. You will have a working Mini-LSM storage engine.

Before moving to Week 2, check that you can explain:

why each component introduced this week is necessary;
the central correctness invariant of each component;
one plausible bug in each component and a test that exposes it;
which data is in memory, which data is on disk, and which structure owns each piece;
how the read and write paths choose the newest visible value for a key.

Memtables

Chapter Overview

By the end of this chapter, you will be able to:

Implement memtables based on skiplists.
Implement the logic for freezing memtables.
Implement the memtable portion of the LSM get read path.
Explain how snapshot ordering, tombstones, and the two state locks preserve correct point reads during concurrent writes.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 1
cargo x scheck

Before You Begin

The starter engine exposes get, put, and delete, but it does not yet have a functioning storage structure. This chapter introduces its first source of truth: one mutable memtable, followed by zero or more immutable memtables awaiting a flush.

Keep these invariants in mind while implementing the tasks:

The engine has exactly one current mutable memtable.
imm_memtables is ordered from newest to oldest.
The first version of a key found while probing from newest to oldest determines the result. An empty value is a tombstone and therefore determines that the key is absent; the search must not continue to an older value.
Structural changes such as replacing the mutable memtable are serialized, even though reads and writes within a memtable can proceed concurrently.

Predict before coding: Suppose the mutable memtable contains a -> delete, the newest immutable memtable contains a -> 2, and the oldest contains a -> 1. What should get(a) return? Which result would you get if you probed the memtables in the opposite order?

Task 1: SkipList Memtable

In this task, you will need to modify:

src/mem_table.rs

First, let us implement the in-memory structure of an LSM storage engine: the memtable. We use crossbeam-skiplist because it supports lock-free concurrent reads and writes. We will not explore skiplists in depth. For this course, you can think of a skiplist as an ordered key-value map that supports concurrent access efficiently.

crossbeam-skiplist provides methods similar to those on the Rust standard library’s BTreeMap, including insert, get, and iter. The important difference is that mutating methods such as insert require only an immutable reference to the skiplist, rather than a mutable one. Your memtable implementation therefore does not need an additional mutex.

You will also notice that MemTable does not have a delete method. In Mini-LSM, a key associated with an empty value represents a deletion.

In this task, implement MemTable::get and MemTable::put. The put method should overwrite an existing entry with the same key, so a single memtable never contains multiple entries for one key.

We use the bytes crate to store data in the memtable. bytes::Bytes is similar to Arc<[u8]>: cloning or slicing a Bytes value does not copy its underlying data, so both operations are inexpensive. Instead, each operation creates another reference to the same storage, which is freed when no references remain.

Task 2: A Single Memtable in the Engine

In this task, you will need to modify:

src/lsm_storage.rs

Now, add the memtable to the LSM state. LsmStorageState::create initializes memtable 0, which is the initial mutable memtable. At any point in time, the engine has exactly one mutable memtable. A memtable usually has a size limit—for example, 256 MB—and is frozen into an immutable memtable when it reaches that limit.

In lsm_storage.rs, two structs represent the storage engine: MiniLsm and LsmStorageInner. MiniLsm is a thin wrapper around LsmStorageInner. Until you begin implementing compaction in Week 2, you will add most functionality to LsmStorageInner.

LsmStorageState describes the current structure of the LSM storage engine. For now, you will use only its memtable field, which stores the current mutable memtable. Implement LsmStorageInner::get, LsmStorageInner::put, and LsmStorageInner::delete, dispatching each request directly to that memtable.

one memtable LSM

Your delete implementation should store an empty slice for the key. This entry is called a deletion tombstone. Your get implementation should recognize the tombstone and report that the key does not exist.

To access the memtable, acquire the state lock. Because MemTable::put requires only an immutable reference, you need only a read lock on state, even when writing to the memtable. This design allows multiple threads to access the memtable concurrently.

Task 3: Write Path - Freezing a Memtable

In this task, you will need to modify:

src/lsm_storage.rs
src/mem_table.rs

one memtable LSM

A memtable cannot grow indefinitely, so you must freeze it—and later flush it to disk—when it reaches its size limit. LsmStorageOptions::target_sst_size serves as both the target SST size and the approximate memtable capacity. Do not confuse it with num_memtable_limit. This capacity is a soft limit, so freezing is a best-effort operation.

In this task, track the approximate memtable size whenever you put or delete a key. You can estimate it by adding the key and value lengths on every call to put. If a key is written twice, you may count both writes even though the skiplist retains only the latest value. Once the memtable reaches the limit, call force_freeze_memtable to freeze it and create a new mutable memtable.

The state: Arc<RwLock<Arc<LsmStorageState>>> field in LsmStorageInner uses a copy-on-write (CoW) strategy to manage the LSM tree’s structural state safely and concurrently:

Inner Arc<LsmStorageState>: This holds a structurally immutable snapshot of LsmStorageState, including the memtable lists and SST references. Cloning the Arc is inexpensive—it only increments an atomic reference count—and gives a reader a consistent view of the structure for the duration of an operation.
RwLock<Arc<LsmStorageState>>: This read-write lock protects the pointer to the active snapshot.
- Readers acquire a read lock, clone the Arc<LsmStorageState>, and promptly release the lock. They can then work from their snapshot without holding the global state lock.
- Writers acquire the write lock, clone the underlying LsmStorageState, apply structural changes to the clone, wrap it in a new Arc, and replace the active snapshot.
Outer Arc<RwLock<...>>: This lets multiple threads safely share the lock and, through it, access and update the active snapshot.

This CoW approach gives readers a valid, consistent snapshot with minimal blocking. Writers atomically replace the entire structural snapshot, which keeps critical sections short and improves concurrency.

Because multiple threads can write to the storage engine, they might call force_freeze_memtable concurrently. You must prevent races between those calls.

Several operations modify the LSM state: freezing a mutable memtable, flushing a memtable to an SST, and performing garbage collection or compaction. These operations can involve I/O. One intuitive locking strategy is to perform the entire state change under the write lock:

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) {
    let mut guard = self.state.write();
    let mut snapshot = guard.as_ref().clone();
    let old_memtable = std::mem::replace(
        &mut snapshot.memtable,
        Arc::new(MemTable::create(self.next_sst_id())),
    );
    snapshot.imm_memtables.insert(0, old_memtable);
    *guard = Arc::new(snapshot);
}
}

This approach works for now. However, consider creating a write-ahead log file for every memtable:

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) -> Result<()> {
    let mut guard = self.state.write();
    let id = self.next_sst_id();
    let memtable = Arc::new(MemTable::create_with_wal(
        id,
        self.path_of_wal(id),
    )?); // <- Could take several milliseconds.
    // Clone and update the structural snapshot here.
    // ...
    Ok(())
}
}

While the memtable is being frozen, no other thread can access the LSM state for several milliseconds, creating a latency spike.

To avoid this problem, perform I/O outside the critical section:

#![allow(unused)]
fn main() {
fn freeze_memtable(&self) -> Result<()> {
    let id = self.next_sst_id();
    let memtable = Arc::new(MemTable::create_with_wal(
        id,
        self.path_of_wal(id),
    )?); // <- Could take several milliseconds.
    {
        let mut guard = self.state.write();
        let mut snapshot = guard.as_ref().clone();
        let old_memtable = std::mem::replace(&mut snapshot.memtable, memtable);
        snapshot.imm_memtables.insert(0, old_memtable);
        *guard = Arc::new(snapshot);
    }
    Ok(())
}
}

The state write lock now contains no expensive operations. Next, suppose that a memtable is about to reach its capacity and two threads each add a key. Both threads observe that the memtable has reached its capacity and decide to freeze it. Without additional synchronization, one of them might freeze the newly created empty memtable immediately after the other thread installs it.

To prevent this race, serialize all state modifications with state_lock and recheck the condition after acquiring it:

#![allow(unused)]
fn main() {
fn put(&self, key: &[u8], value: &[u8]) {
    // Write to the memtable, check its capacity, and release the state read lock.
    if memtable_reaches_capacity_on_put {
        let state_lock = self.state_lock.lock();
        if /* the current memtable still exceeds its capacity */ {
            self.freeze_memtable(&state_lock)?;
        }
    }
}
}

You will see this pattern often in later chapters. For example, an L0 flush follows this outline:

#![allow(unused)]
fn main() {
fn force_flush_next_imm_memtable(&self) {
    let state_lock = self.state_lock.lock();
    // Get the oldest memtable, then release the state read lock.
    // Write the contents to disk.
    // Acquire the state write lock and install the updated snapshot.
}
}

This approach ensures that only one thread modifies the LSM state at a time while still allowing concurrent access to the storage engine.

Modify put and delete to respect the memtable’s soft capacity limit. When the memtable reaches that limit, call force_freeze_memtable. The test suite does not cover this concurrent scenario, so consider the possible races carefully. Keep each critical section as small as possible.

Assign the next memtable ID with self.next_sst_id(). The imm_memtables vector stores memtables from newest to oldest, so imm_memtables.first() is the most recently frozen memtable.

Task 4: Read Path - Get

In this task, you will need to modify:

src/lsm_storage.rs

Now that you have multiple memtables, update the read-path get method to retrieve the latest version of a key. Probe the memtables from newest to oldest.

Chapter Checkpoint

Your engine should now support put, delete, and get across one mutable and several immutable memtables. It should freeze a full memtable without blocking unrelated state access during expensive work or immediately freezing the replacement memtable.

In addition to passing the tests, verify that you can locate the code responsible for each invariant from the beginning of the chapter. Construct a two-memtable example for an overwritten key and another for a tombstone, then confirm that reversing the probe order would produce the wrong result.

Test Your Understanding

Answer the correctness questions with reference to your implementation. For questions about a possible race or wrong result, give a concrete execution or input rather than only a general explanation.

Correctness and Concurrency

Why doesn’t the memtable provide a delete API?
Does it make sense for a memtable to store every write instead of only the latest version of a key? For example, suppose a user writes a -> 1, a -> 2, and a -> 3 to the same memtable.
Why do we need a combination of state and state_lock? Can we only use state.read() and state.write()?
Construct the smallest example in which probing memtables in the wrong order returns a stale value. Then construct one in which it resurrects a deleted value.
After a memtable is frozen, could a thread that still holds an old LSM-state snapshot write to that now-immutable memtable? How does your solution prevent this?
In several places, you might acquire a state read lock, release it, and then acquire a write lock. The two operations may occur in different functions that call one another. How does this differ from directly upgrading a read lock to a write lock? Is an upgrade necessary, and what does it cost?

Performance and Design

Could an LSM tree use other data structures for its memtable? What are the advantages and disadvantages of a skiplist?
Is the memtable’s memory layout efficient? Does it have good data locality? Consider how Bytes is implemented and stored in the skiplist. How could you optimize the memtable’s layout?
This course uses parking_lot locks. Is its read-write lock fair? What might happen to readers waiting to acquire the lock when a writer is already waiting for the current readers to release it?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

More Memtable Formats. Implement other memtable formats, such as B-tree, vector, or adaptive radix tree (ART) memtables.

Merge Iterator

Chapter Overview

By the end of this chapter, you will be able to:

Implement a memtable iterator.
Implement a merge iterator.
Implement the memtable portion of the LSM scan read path.
Explain how cursor validity, source precedence, and tombstone filtering combine to produce one logical sorted view.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 2
cargo x scheck

Before You Begin

The engine can now resolve a point lookup across multiple memtables, but it cannot return a range of keys. A scan must combine several independently sorted sources without materializing their full contents.

The iterator stack divides that responsibility across layers:

MemTableIterator exposes one sorted memtable.
MergeIterator combines sources of the same type, removes duplicate versions, and gives lower-indexed—that is, newer—sources precedence.
LsmIterator removes tombstones from the user-visible stream.
FusedIterator makes invalid and errored states safe for callers.

The core invariant is: the output is sorted, and each user key appears at most once with the value from the newest input containing that key. Tombstones participate in precedence before LsmIterator hides them.

Predict before coding: Merge iter1 = [b->delete, c->4] with iter2 = [a->1, b->2, c->3], where iter1 is newer. Write the internal merged stream first, including tombstones, and then the user-visible stream. What breaks if tombstones are removed before duplicate versions are resolved?

Task 1: Memtable Iterator

In this chapter, you will implement the LSM scan interface, which uses an iterator to return an ordered range of key-value pairs. In the previous chapter, you implemented get and the logic for creating immutable memtables, so your LSM state can now contain several memtables. You will first create an iterator over one memtable, then merge iterators from all memtables, and finally enforce the requested key range.

In this task, you will need to modify:

src/mem_table.rs

All LSM iterators implement the StorageIterator trait. Its four core methods are key, value, next, and is_valid. If you are familiar with Rust’s standard-library Iterator trait, you will notice that StorageIterator works differently. It uses a cursor-based API, a pattern common in database systems and inspired by RocksDB’s iterators. See iterator_base.h and iterator.h for reference.

When an iterator is created, its cursor points to the first entry in the memtable, block, or SST that satisfies the lower bound. The value method returns &[u8], while key returns the iterator’s associated borrowed key type—for example, KeySlice. These borrowed return values avoid copying key and value data.

From the caller’s perspective, the typical usage pattern is:

#![allow(unused)]
fn main() {
let mut iter: impl StorageIterator = ...;
while iter.is_valid() {
    let key = iter.key();
    let value = iter.value();
    // Process key and value
    iter.next()?; // Advance to the next item, handling potential errors
}
}

The core StorageIterator methods have distinct responsibilities:

next(): Attempts to move the cursor to the next element. It returns a Result so that it can report errors such as I/O failures. A successful call does not guarantee that the new position is valid; the cursor may have reached the end.
is_valid(): Reports whether the current cursor points to a valid data element. It does not advance the iterator.

After every call to next(), including a successful one, your implementation must update its internal state so that is_valid() accurately reports whether the new cursor position contains an item.

In summary, next advances the cursor, and is_valid reports whether that cursor still identifies an item. You may assume that callers invoke next only while is_valid returns true. Later, you will implement a FusedIterator wrapper that normalizes behavior after an iterator becomes invalid or returns an error.

Now return to the memtable iterator. You may have noticed that its public type has no lifetime parameter. If you create a Vec<u64> and call vec.iter(), the iterator’s type contains a lifetime such as VecIterator<'a>, where 'a is tied to the vector. The same is true of SkipMap::iter. For Mini-LSM, however, we avoid exposing such lifetimes on storage iterators because doing so would complicate the entire system.

Because the iterator has no lifetime parameter, it must ensure that the underlying skiplist remains alive for as long as the iterator is in use. We do this by storing an Arc<SkipMap> inside the iterator itself. A first attempt might look like this:

#![allow(unused)]
fn main() {
pub struct MemtableIterator {
    map: Arc<SkipMap<Bytes, Bytes>>,
    iter: SkipMapRangeIter<'???>,
}
}

The problem is that we need to express that iter borrows map, another field in the same struct. How can we represent that relationship?

This is the first particularly tricky Rust concept in the course: a self-referential struct. If Rust allowed us to write the following, the problem would be solved:

#![allow(unused)]
fn main() {
pub struct MemtableIterator { // <- with lifetime 'this
    map: Arc<SkipMap<Bytes, Bytes>>,
    iter: SkipMapRangeIter<'this>,
}
}

Third-party crates such as ouroboros provide a safe interface for defining this kind of self-referential struct. You could also implement it with unsafe Rust; in fact, ouroboros uses unsafe Rust internally.

We have used ouroboros to define the self-referential fields of MemTableIterator for you. Implement its iterator logic and the MemTable::scan API using the provided structure.

Task 2: Merge Iterator

In this task, you will need to modify:

src/iterators/merge_iterator.rs

Because the LSM state can contain multiple memtables, a scan creates multiple memtable iterators. Merge their results and return only the latest version of each key.

MergeIterator maintains a binary heap internally. A binary heap is a natural way to merge n sorted iterators because it efficiently identifies the iterator whose current key is smallest. The heap orders the iterator with the smallest current key first. When several iterators have the same current key, it orders the newest one first. Handle errors and exhausted iterators carefully, and ensure that the merge emits only the latest version of each key-value pair.

For example, if we have the following data:

iter1: b->del, c->4, d->5
iter2: a->1, b->2, c->3
iter3: e->4

The merge iterator should produce:

a->1, b->del, c->4, d->5, e->4

The merge iterator’s constructor accepts a vector of iterators. An iterator with a lower index—closer to the front of the vector—contains newer data.

When using Rust’s binary heap, you may find peek_mut useful:

#![allow(unused)]
fn main() {
let Some(mut inner) = heap.peek_mut() {
    *inner += 1; // Modify the top item.
}
// When PeekMut is dropped, the binary heap is reordered automatically.

let Some(mut inner) = heap.peek_mut() {
    PeekMut::pop(inner) // Remove the top item from the heap.
}
}

A common pitfall involves error handling. For example:

#![allow(unused)]
fn main() {
let Some(mut inner_iter) = self.iters.peek_mut() {
    inner_iter.next()?; // Problematic.
}
}

If next returns an error—for example, because of a disk, network, or checksum failure—the iterator must no longer remain in the heap. When the scope exits, however, PeekMut::drop attempts to restore the heap order and may access that invalid iterator. Handle the error explicitly and remove the iterator instead of using ? while the PeekMut guard is alive.

We avoid dynamic dispatch where practical, so the system does not use Box<dyn StorageIterator>. Instead, it uses generics and static dispatch. StorageIterator also uses a generic associated type (GAT) for its borrowed key type, allowing different iterators to return types such as KeySlice or &[u8]. In Week 3, KeySlice will include a timestamp; introducing the key abstraction now makes that transition smoother.

From this section onward, use Key<T> for LSM keys so that the type system can distinguish keys from values. Use the provided Key<T> methods instead of accessing the wrapped value directly. In Week 3, you will add a timestamp to this type, and the abstraction will make that transition smoother. For now, KeySlice wraps &[u8], KeyVec wraps Vec<u8>, and KeyBytes wraps Bytes.

Task 3: LSM Iterator + Fused Iterator

In this task, you will need to modify:

src/lsm_iterator.rs

LsmIterator represents the storage engine’s internal iterator. You will modify it several times as you add more iterator types. For now, the engine contains only memtables, so its inner type should be:

#![allow(unused)]
fn main() {
type LsmIteratorInner = MergeIterator<MemTableIterator>;
}

Implement LsmIterator by delegating to the inner iterator and skipping deletion tombstones.

This task does not test LsmIterator directly; Task 4 includes an integration test.

Next, add safeguards against iterator misuse. Callers must not invoke key or value while an iterator is invalid, and they must not continue using it after next returns an error. FusedIterator wraps another iterator to normalize these behaviors. Implement it using the contract documented in the starter code.

Task 4: Read Path - Scan

In this task, you will need to modify:

src/lsm_storage.rs

With these iterators in place, you can implement the LSM engine’s scan interface. Construct an LsmIterator from the memtable iterators, placing the newest memtable first in the merge iterator. The storage engine will then be able to serve scan requests.

Chapter Checkpoint

The engine should now scan any requested range across its mutable and immutable memtables. A scan returns sorted, unique, live keys and respects the same newest-first precedence as get.

After the tests pass, trace one key that appears in three memtables through every iterator layer. Identify exactly where its older versions are discarded and where its tombstone, if present, becomes invisible to the caller. Also confirm that next() returning Ok(()) does not imply that the iterator remains valid.

Test Your Understanding

Correctness

If a key is removed (there is a delete tombstone), do you need to return it to the user? Where did you handle this logic?
If a key has multiple versions, will the user see all of them? Where did you handle this logic?
What happens if your key comparator cannot give the binary heap implementation a stable order?
Why must the merge iterator resolve duplicate keys according to iterator construction order?
Construct a minimal input that produces a duplicate key if MergeIterator::next advances only the currently visible child and not every child positioned at that key.

Rust and API Design

Why do we need a self-referential struct for the memtable iterator?
If we replace the self-referential struct with a lifetime on the memtable iterator—for example, MemTableIterator<'a>, where 'a is tied to a memtable or LsmStorageInner—can we still implement scan?
Could you implement a Rust-style iterator—for example, one with next(&mut self) -> Option<(Key, Value)>—for LSM iterators? What are the advantages and disadvantages?
The scan interface resembles fn scan(&self, lower: Bound<&[u8]>, upper: Bound<&[u8]>). How could you make it accept Rust range syntax such as key_a..key_b? If you implement this API, try passing the full range .. and observe what happens.
The starter code provides the merge iterator interface to store Box<I> instead of I. What might be the reason behind that?

Performance and Concurrent Behavior

What are the time and space complexities of building and advancing your merge iterator in terms of the number of input iterators?
Suppose that (1) you create an iterator over the skiplist memtable and (2) another thread inserts keys into that memtable. Will the iterator see the new keys? Design a small experiment rather than relying only on the type signature.

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

Foreground Iterator. This course assumes that all operations are short, so an iterator can retain a reference to a memtable. If a user holds an iterator for a long time, the entire memtable—which might occupy 256 MB—remains in memory even after it has been flushed to disk. To address this issue, provide a ForegroundIterator or LongIterator that periodically creates a new underlying storage iterator, allowing the old resources to be reclaimed.

Block

Chapter Overview

By the end of this chapter, you will be able to:

Implement SST block encoding.
Implement SST block decoding and a block iterator.
Reason about format invariants, size accounting, lower-bound seeks, and the trust boundary of a decoder.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 3
cargo x scheck

Before You Begin

The engine currently stores every key-value pair in memtables. Blocks are the first encoded representation you will design: a compact sequence of sorted entries plus an index of their starting offsets.

Preserve these format invariants:

Encoding and decoding are inverses for every valid block.
Entry offsets are ordered and refer to valid positions in the data section.
The footer contains exactly one offset per entry and the encoded entry count.
Except when the first entry alone exceeds the target, adding an entry must not make the encoded block larger than target_size.
Seeking positions the iterator at the first key greater than or equal to the target, or makes it invalid if no such key exists.

Predict before coding: Before looking at BlockBuilder::add, write a formula for the encoded size after adding one key-value pair. Include the key length, value length, entry offset, and element count. Which bytes are paid once per block, and which are paid once per entry?

Task 1: Block Builder

In the previous two chapters, you implemented the in-memory structures for an LSM storage engine. Now it is time to build the on-disk structures. Their basic unit is the block, which stores sorted key-value pairs. Blocks are often 4 KiB—the typical size of an operating-system page and an SSD page—although the ideal size depends on the storage medium. An SST consists of multiple blocks. When enough immutable memtables accumulate, the engine flushes the oldest one to an SST. In this chapter, you will implement block encoding and decoding.

In this task, you will need to modify:

src/block/builder.rs
src/block.rs

The block encoding format in our course is as follows:

----------------------------------------------------------------------------------------------------
|             Data Section             |              Offset Section             |      Extra      |
----------------------------------------------------------------------------------------------------
| Entry #1 | Entry #2 | ... | Entry #N | Offset #1 | Offset #2 | ... | Offset #N | num_of_elements |
----------------------------------------------------------------------------------------------------

Each entry is a key-value pair.

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------

The key and value lengths are each encoded in 2 bytes as u16 values, so their maximum encoded length is 65,535 bytes.

We assume that keys are never empty, but values may be. Other parts of the system interpret an empty value as a deletion marker, or tombstone. BlockBuilder and BlockIterator simply preserve the empty value.

At the end of each block, we store the offset of every entry followed by the total number of entries. For example, suppose the first entry starts at byte 0 and the second starts at byte 12:

-------------------------------
|offset|offset|num_of_elements|
-------------------------------
|   0  |  12  |       2       |
-------------------------------

The block footer then has the layout shown above. Every number in the footer is stored as a u16.

Each block has a size limit, target_size, which corresponds to block_size in the provided code. Unless the first key-value pair alone exceeds this limit, ensure that the encoded block is no larger than target_size.

When BlockBuilder::build is called, it produces the raw data section and the unencoded entry offsets, which are stored in a Block. Keeping raw key-value data contiguous and storing offsets separately avoids unnecessary allocations and decoding work. Copy the raw block data into the data vector and decode one entry offset every 2 bytes, rather than materializing all entries as a structure such as Vec<(Vec<u8>, Vec<u8>)>. This compact layout is efficient.

Implement Block::encode and Block::decode according to the format above.

Task 2: Block Iterator

In this task, you will need to modify:

src/block/iterator.rs

Now that you have an encoded block, implement BlockIterator so that callers can look up and scan keys within it.

Create a BlockIterator from an Arc<Block>. create_and_seek_to_first positions it at the first key in the block. create_and_seek_to_key positions it at the first key greater than or equal to the requested key. For example, suppose a block contains 1, 3, and 5:

#![allow(unused)]
fn main() {
let mut iter = BlockIterator::create_and_seek_to_key(block, b"2");
assert_eq!(iter.key(), b"3");
}

Seeking to 2 positions the iterator at the next available key, which is 3.

The iterator should copy the current key from the block and store it internally; this will be necessary when you add key compression. For the value, store only its start and end offsets instead of copying its bytes.

When next is called, advance the iterator by one entry. At the end of the block, set key to empty so that is_valid returns false; the caller can then move to another block if one is available.

Chapter Checkpoint

You should now be able to build a block, serialize it, decode it, iterate from its first key, and seek to any lower bound. Test keys that exist, keys between entries, and keys before and after the block’s range.

Passing the supplied tests demonstrates behavior for valid blocks. It does not prove that arbitrary bytes can be decoded safely. Identify which assumptions your decoder makes about trusted input and which checks a production decoder would need before indexing or allocating.

Test Your Understanding

Correctness and Format

What is the time complexity of seeking a key in the block?
Where does the cursor stop when you seek a non-existent key in your implementation?
What endianness does your implementation use for numbers written to blocks?
Can a block contain duplicated keys?
What happens if the user adds a key larger than the target block size?

Safety and Robustness

Is your implementation vulnerable to a maliciously constructed block? Could invalid input cause an out-of-bounds access or an out-of-memory condition?
Construct three malformed blocks: one with an impossible entry count, one with a non-monotonic or out-of-range offset, and one with a length that extends beyond the data section. Where would the current decoder fail for each input, and what validation would reject it cleanly?

Performance and Design

Block is simply a vector of raw data and a vector of offsets. Could we change them to Bytes and Arc<[u16]>, then change the iterator interfaces to return Bytes instead of &[u8]? Assume that we use Bytes::slice to return a slice without copying. What are the advantages and disadvantages?
Suppose the LSM engine uses an object-storage service such as S3. How would you adapt the block format and its parameters to suit that environment?

Snack Break

Do you love bubble tea? Why or why not?

We do not provide reference answers to these questions. Feel free to discuss them in the Discord community.

Bonus Tasks

Backward Iterators. Implement prev for BlockIterator to iterate over key-value pairs in reverse. You can also implement backward variants of the merge iterator and, in the next chapter, the SST iterator so that the storage engine can perform reverse scans.

Sorted String Table (SST)

Chapter Overview

By the end of this chapter, you will be able to:

Implement SST encoding and metadata encoding.
Implement SST decoding and an SST iterator.
Explain how block metadata, lazy loading, and caching support lower-bound seeks without loading an entire SST.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 4
cargo x scheck

Before You Begin

A block provides sorted storage and seeks within a small byte range. An SST composes many blocks into an immutable file and adds enough metadata to locate the block that may contain a requested key.

The main invariants are:

Blocks and their metadata appear in the same key order.
Each BlockMeta records the encoded block’s offset and its actual first and last keys.
An iterator directly retains only the block it currently needs and advances to the next block when a seek lands beyond the current one. The cache may retain other blocks independently.
A lower-bound seek never skips a key greater than or equal to the target.
The block cache identifies a block by both its SST ID and block index; blocks from different SSTs must never collide.

Predict before coding: An SST contains block 1 with [a, b, c] and block 2 with [e, f, g]. If block selection uses only first-key metadata, which block is initially selected by seek(d)? What must the iterator do next to satisfy lower-bound seek semantics?

Task 1: SST Builder

In this task, you will need to modify:

src/table/builder.rs
src/table.rs

SSTs consist of data blocks and index information stored on disk. Data blocks are usually loaded lazily: they remain on disk until a read requires them. Index blocks can also be loaded on demand, but this course assumes that the metadata for every SST fits in memory; we do not implement separate index blocks. An SST file is commonly around 256 MB.

The SST builder resembles the block builder: callers add entries through add. Maintain a BlockBuilder within SsTableBuilder and finish the current block when necessary. You must also maintain BlockMeta for each block, including its offset and its first and last keys. The build function encodes the SST, writes it to disk with FileObject::create, and returns an SsTable.

The SST encoding has the following layout:

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block |            metadata           | meta block offset (u32) |
-------------------------------------------------------------------------------------------

Implement SsTableBuilder::estimated_size so that callers can decide when to begin a new SST. The estimate does not need to be exact. Because the data blocks are much larger than the metadata, returning the size of the encoded data blocks is sufficient.

You must also implement block-metadata encoding and decoding so that SsTableBuilder::build can produce a valid SST file.

Task 2: SST Iterator

In this task, you will need to modify:

src/table/iterator.rs
src/table.rs

As with BlockIterator, implement an iterator over an SST. Load data blocks on demand: while the iterator is in block 1, for example, it should not retain any other block’s contents.

SsTableIterator should implement the StorageIterator trait, so that it can be composed with other iterators in the future.

Pay particular attention to seek_to_key. Use a binary search over block metadata to find the block that may contain the requested key. Because the key might not exist, the block iterator may become invalid immediately after the seek. For example:

--------------------------------------
| block 1 | block 2 |   block meta   |
--------------------------------------
| a, b, c | e, f, g | 1: a/c, 2: e/g |
--------------------------------------

To keep the implementation simple, we recommend using only the first key of each block in the binary search. For seek(b), the search shows that block 1 covers the candidate range a <= key < e. Load block 1 and seek its iterator to the appropriate position.

For seek(d), however, searching only the first keys also selects block 1, and seeking within that block reaches its end. After a seek, check whether the iterator is invalid and advance to the next block if necessary. Alternatively, use the last-key metadata to select the correct block directly.

Task 3: Block Cache

In this task, you will need to modify:

src/table/iterator.rs
src/table.rs

Implement a new read_block_cached function on SsTable.

We use moka-rs for the block cache, with (sst_id, block_id) as the cache key. Use try_get_with to return a cached block on a hit or load and cache it on a miss. If concurrent requests miss on the same block, try_get_with performs one disk read and shares the result among the requests.

Update the table iterator to call read_block_cached instead of read_block.

Chapter Checkpoint

You should now be able to build and reopen a multi-block SST, seek across block boundaries, and iterate without keeping every data block in memory. Run seeks for the first and last key of each block, for a key between two blocks, and for a key greater than the SST’s last key.

Inspect the block-reading path after the tests pass. Explain when a disk read occurs, what remains resident because of the iterator, and what remains reachable through the cache. These lifetimes are related but not identical.

Test Your Understanding

Correctness and Format

What is the time complexity of seeking a key in the SST?
Where does the cursor stop when you seek a non-existent key in your implementation?
Is it possible (or necessary) to do in-place updates of SST files?

Caching and Memory

An SST is usually large—for example, 256 MB—so repeatedly copying or growing its Vec can be expensive. Does your implementation reserve enough space for the SST builder in advance? How?
Looking at the moka block cache, why does it return Arc<Error> instead of the original Error?
Does using a block cache guarantee that at most a fixed number of blocks exist in memory? For example, with a 4 GB moka cache and 4 KiB blocks, can more than 4 GB / 4 KiB blocks be alive at once? Account for references held outside the cache.

Storage Design

Can an LSM engine store columnar data, such as a table with 100 integer columns? Would the current SST format still be a good choice?
Suppose the LSM engine uses an object-storage service such as S3. How would you adapt the SST format, its parameters, and the block cache to suit that environment?
For now, we load the metadata for every SST into memory. If 16 GB of memory is reserved for this metadata, can you estimate the maximum database size the LSM system could support? This limitation motivates an index cache.

We do not provide reference answers to these questions. Feel free to discuss them in the Discord community.

Bonus Tasks

Explore Different SST Encodings and Layouts. For example, the authors of Lethe: Enabling Efficient Deletes in LSMs add secondary-key support to SSTs.
- Alternatively, use a B+ tree rather than sorted blocks as the SST format.
Index Blocks. Split block indexes and block metadata into index blocks, and load them on-demand.
Index Cache. Use a separate cache for indexes apart from the data block cache.
I/O Optimizations. Align blocks to 4 KiB boundaries and use direct I/O to bypass the system page cache.

Read Path

Chapter Overview

By the end of this chapter, you will be able to:

Integrate SST into the LSM read path.
Implement LSM read path get with SSTs.
Implement LSM read path scan with SSTs.
Trace how recency, tombstones, range bounds, and state snapshots determine the logical result across memory and disk.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 5
cargo x scheck

Before You Begin

Memtables and SSTs can each be queried independently. The storage engine must now combine them into one logical view in which implementation details—how many structures contain a key or where they reside—are invisible to the user.

Preserve these read-path invariants:

Mutable and immutable memtables take precedence over L0 SSTs, and newer sources take precedence over older sources within each group.
A tombstone in a newer source hides every older value for the same key.
scan returns sorted, unique, live keys within the exact requested bounds.
A seek may land on the next greater key, so get returns a value only after checking for exact key equality.
Creating and seeking SST iterators may perform I/O and therefore happens after releasing the state lock, using a consistent cloned snapshot.

Predict before coding: The mutable memtable contains b -> delete and d -> 4; an immutable memtable contains a -> 1 and b -> 2; the newest L0 SST contains a -> 0, c -> 3, and d -> 3. What should get(a), get(b), and a scan with both a and d included return? For each result, identify the source that wins.

Task 1: Two Merge Iterator

In this task, you will need to modify:

src/iterators/two_merge_iterator.rs

You have already implemented a merge iterator for iterators of the same type, such as memtable iterators. Now that the SST format is implemented, the engine has both in-memory memtables and on-disk SSTs. A scan must merge memtable and SST iterators into a single stream. For this purpose, implement TwoMergeIterator<X, Y>, which can merge two different iterator types.

Because there are only two iterators, TwoMergeIterator does not need a binary heap. A flag can indicate which iterator currently has precedence. As in MergeIterator, when both iterators contain the same key, the first iterator takes precedence.

Task 2: Read Path - Scan

In this task, you will need to modify:

src/lsm_iterator.rs
src/lsm_storage.rs

After implementing TwoMergeIterator, we can change the LsmIteratorInner to have the following type:

#![allow(unused)]
fn main() {
type LsmIteratorInner =
    TwoMergeIterator<MergeIterator<MemTableIterator>, MergeIterator<SsTableIterator>>;
}

This type combines data from memtables and SSTs into the storage engine’s internal iterator.

The SST iterator does not support an end bound for scans. Enforce that bound in LsmIterator by updating its constructor to accept an end_bound:

#![allow(unused)]
fn main() {
pub(crate) fn new(iter: LsmIteratorInner, end_bound: Bound<Bytes>) -> Result<Self> {}
}

Then update the iteration logic to stop according to the bound’s semantics: before an excluded end key, or after an included end key.

The tests create memtables and SSTs referenced by l0_sstables; your scan must return their combined contents correctly. You do not need to implement flushing until the next chapter. For now, update LsmStorageInner::scan to create a merge iterator over all memtables and L0 SSTs, completing the engine’s scan path.

Creating and initially seeking an SsTableIterator may perform I/O, so do not do it while holding the state lock. First acquire the read lock and clone the Arc containing the state snapshot. Release the lock, then create an iterator for each L0 SST and merge the resulting streams.

#![allow(unused)]
fn main() {
fn scan(&self) {
    let snapshot = {
        let guard = self.state.read();
        Arc::clone(&guard)
    };
    // create iterators and seek them
}
}

The l0_sstables vector stores only SST IDs. Retrieve the corresponding SsTable objects from the sstables map.

Task 3: Read Path - Get

In this task, you will need to modify:

src/lsm_storage.rs

Process a get as direct lookups in the memtables followed, if necessary, by a seek over a merge iterator of the SSTs. A seek may land on the requested key or on the next greater key, so return a value only if the iterator’s key exactly matches the requested key. As in the scan path, minimize the state lock’s critical section. Preserve newest-to-oldest precedence, and treat an empty value as a tombstone rather than continuing to older data.

Chapter Checkpoint

The engine should now present one consistent read view across all mutable, immutable, and on-disk structures. Verify both point reads and scans for a key that appears in several sources, a key deleted by a newer source, and a key absent from every source.

Exercise all four combinations of included and excluded scan bounds, plus unbounded ranges. For each test, predict the first and last returned keys before running it. Finally, inspect the lifetime of the state read guard and confirm that no SST iterator is created while that guard is held.

Test Your Understanding

Correctness

In the prediction example above, how would each result change if the two inputs to TwoMergeIterator were reversed?
Construct the smallest state in which continuing to search after finding a tombstone resurrects a deleted key.
A seek for b lands on c. Which explicit comparison prevents get(b) from returning c’s value?
Where are included and excluded upper bounds enforced? Write a boundary test that would fail if the implementation used < for both variants.

Resource Lifetime and Performance

Suppose a user creates an iterator over the entire 1 TB storage engine, and the scan takes about an hour. What problems could this cause? We will revisit this question at several points in the course.
Some LSM-tree storage engines provide a multi-get, or vectored-get, interface. The caller supplies a list of keys and receives a value for each one; for example, multi_get(vec!["a", "b", "c", "d"]) -> a=1,b=2,c=3,d=4. The simplest implementation performs one get per key. How would you implement multi-get, and what could you optimize? Hint: some work in the get path needs to be performed only once for the entire batch. You can also consider an improved disk-I/O interface designed for multi-get.

We do not provide reference answers to these questions. Feel free to discuss them in the Discord community.

Bonus Tasks

The Cost of Dynamic Dispatch. Implement a Box<dyn StorageIterator> version of merge iterators and benchmark to see the performance differences.
Parallel Seek. Creating a merge iterator requires loading the first relevant block from every underlying SST when you create each SsTableIterator. Consider creating these iterators in parallel.

Write Path

Chapter Overview

By the end of this chapter, you will be able to:

Implement the LSM write path with L0 flush.
Implement the logic to correctly update the LSM state.
Explain the state transition that makes a flushed SST visible without losing or duplicating an immutable memtable.
Use key-range metadata to skip SSTs without changing read results.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 6
cargo x scheck

Before You Begin

The read path can consume SSTs, but the Day 5 tests created those SSTs directly. This chapter completes the write path: the engine itself will turn the oldest immutable memtable into an SST and atomically install it in L0.

The important invariants are:

Only the oldest immutable memtable is selected for the next flush.
state_lock serializes the flush with other structural changes.
Building and writing the SST occurs outside the state read-write lock.
Installing the SST removes exactly the memtable that was flushed, inserts the SsTable into sstables, and inserts its ID at the front—the newest side—of l0_sstables in one snapshot update.
SST filtering may exclude a file only when its key range cannot contribute to the request. An optimization must not change query results.

Predict before coding: Suppose imm_memtables contains IDs [7, 6, 5] from newest to oldest and l0_sstables contains [4, 3]. Write both vectors after one correct flush. Which assertions would detect flushing the wrong memtable or installing the wrong SST ID?

Task 1: Flush Memtable to SST

At this point, the in-memory and on-disk structures are ready, and the storage engine can read and merge data from them. You will now implement flushing—the process of moving data from memory to disk—and complete Week 1 of Mini-LSM.

In this task, you will need to modify:

src/lsm_storage.rs
src/mem_table.rs

Modify LsmStorageInner::force_flush_next_imm_memtable and MemTable::flush. In LsmStorageInner::open, create the database directory if it does not exist. Flushing a memtable requires three steps:

Select a memtable to flush.
Create an SST file from that memtable.
Remove the memtable from the immutable-memtable list and add the new SST to L0.

We have not yet discussed level 0 (L0). It contains SST files produced directly by memtable flushes, so their key ranges may overlap. During Week 1, all on-disk SSTs remain in L0. In Week 2, you will explore how leveled and tiered compaction strategies organize SSTs efficiently.

Creating an SST is computationally expensive and involves I/O. Do not hold the state read-write lock throughout this work: doing so could block other operations and cause large latency spikes. The state_lock mutex serializes operations that modify the LSM-tree state. Use both locks carefully to prevent races while keeping critical sections short.

The test suite does not exercise all concurrent cases, so reason carefully about synchronization. The last memtable in imm_memtables is the oldest and therefore the one to flush.

Spoiler: L0 Flush Pseudocode

#![allow(unused)]
fn main() {
fn force_flush_next_imm_memtable(&self) -> Result<()> {
    let _state_lock = self.state_lock.lock();

    let memtable_to_flush = {
        let guard = self.state.read();
        guard.imm_memtables.last().unwrap().clone()
    };

    let sst_id = memtable_to_flush.id();
    let sst = build_sst_from_memtable(&memtable_to_flush, sst_id)?;

    {
        let mut guard = self.state.write();
        let mut snapshot = guard.as_ref().clone();
        let removed = snapshot.imm_memtables.pop().unwrap();
        assert_eq!(removed.id(), sst_id);
        snapshot.l0_sstables.insert(0, sst_id);
        snapshot.sstables.insert(sst_id, sst);
        *guard = Arc::new(snapshot);
    }

    Ok(())
}
}

Task 2: Flush Trigger

In this task, you will need to modify:

src/lsm_storage.rs
src/compact.rs

When the number of immutable memtables reaches the num_memtable_limit configured in the storage options, flush the oldest one to disk. A background flush thread performs this work. The MiniLsm wrapper already contains the code needed to start the thread and signal it to stop.

Implement LsmStorageInner::trigger_flush in compact.rs and MiniLsm::close in lsm_storage.rs. The background thread calls trigger_flush every 50 milliseconds. When the number of memtables reaches the limit, call force_flush_next_imm_memtable. When the user calls close, signal the background threads to stop and wait for the flush thread—and, in Week 2, the compaction thread—to finish.

Task 3: Filter the SSTs

Now that you have a working storage engine, use mini-lsm-cli to interact with it:

cargo run --bin mini-lsm-cli -- --compaction none

At the prompt, run:

fill 1000 3000
get 2333
flush
fill 1000 3000
get 2333
flush
get 2333
scan 2000 2333

If you insert more data, you can observe the background thread automatically flushing memtables to L0 without an explicit flush command.

Finally, implement a simple SST-filtering optimization. Using the requested key or key range and each SST’s first and last keys, exclude SSTs that cannot contribute any results. The merge iterator then avoids reading those files.

In this task, you will need to modify:

src/lsm_storage.rs
src/iterators/*
src/lsm_iterator.rs

Update the read path to skip SSTs that cannot contain the requested key or overlap the requested range. Also implement num_active_iterators so the tests can verify the optimization. For MergeIterator and TwoMergeIterator, return the sum of their children’s active-iterator counts. If you retained the starter code’s MergeIterator fields, remember to include MergeIterator::current. For LsmIterator and FusedIterator, delegate to the inner iterator.

You can implement helper functions like range_overlap and key_within to simplify your code.

Chapter Checkpoint

Mini-LSM should now create its own SSTs, flush automatically when the immutable-memtable limit is reached, shut down its background threads cleanly, and avoid opening SSTs whose key ranges cannot affect a read.

After the tests pass, record the state before and after a manual flush: the mutable memtable ID, immutable-memtable IDs, L0 IDs, and keys in the sstables map. Confirm that one logical copy of every key remains visible throughout the transition. Then run the same reads with SST filtering disabled and confirm that only the iterator count—not the results—changes.

Test Your Understanding

Correctness and State Transitions

What happens if a user requests to delete a key twice?
Why must the state update verify that the memtable removed from imm_memtables has the ID used to build the SST?
Construct an interleaving that would corrupt the state if two flushes selected the same oldest memtable without state_lock.
For each combination of included, excluded, and unbounded scan bounds, state the condition under which an SST range can be safely excluded.

Memory and Performance

How much memory, or how many blocks, are loaded at the same time when an iterator is initialized? Measure num_active_iterators during a scan and explain why it changes.

Production Design

Suppose users want to fork an LSM tree: after ingesting data, they create two identical datasets and modify them independently. A simple but inefficient implementation copies every SST and in-memory structure to a new directory. Because on-disk SSTs are immutable, the fork can instead reuse its parent’s files. How could you implement this efficiently without copying data? See Neon Branching.
Imagine a multitenant LSM system hosting 10,000 databases on one machine with 128 GB of memory. If each memtable has a 256 MB size limit, how much memory would all memtables require?
- You clearly do not have enough memory for all of them to reach that limit simultaneously. If each tenant still has a separate memtable, how could you design the flush policy to fit within the global memory budget? Would sharing one memtable among tenants—for example, by encoding a tenant ID in each key prefix—make sense?

We do not provide reference answers to these questions. Feel free to discuss them in the Discord community.

Bonus Tasks

Implement Write/L0 Stalls. When the number of memtables grows too far beyond the limit, pause user writes. After implementing compaction in Week 2, you can also add write stalls based on the number of L0 SSTs.
Prefix Scan. You may filter more SSTs by implementing the prefix scan interface and using the prefix information.

Snack Time: SST Optimizations

Chapter Overview

In the previous chapter, you completed a storage engine that supports get, scan, and put. To finish the week, you will implement two approachable but important SST-format optimizations. Welcome to Week 1’s snack-time chapter!

By the end of this chapter, you will be able to:

Implement Bloom filters for SSTs and integrate them into the get path.
Implement key-prefix compression in the SST block format.
Explain why both optimizations preserve correctness despite discarding lookup work or repeated bytes.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 1 --day 7
cargo x scheck

Before You Begin

The engine completed in Day 6 is functionally correct. Today’s changes must preserve its results while reducing I/O and storage space.

Keep these invariants in mind:

A Bloom-filter negative result must be definitive: an SST skipped after a negative probe cannot contain the key. Positive results may be false and therefore still require a lookup.
The builder and reader hash exactly the same key bytes with the same function.
Prefix encoding followed by decoding reconstructs every original key exactly.
Each compressed key is defined relative to the first key in its block, so it can be decoded without decoding every preceding entry.
These optimizations may change I/O counts and encoded sizes, but never the key-value pairs returned by get or scan.

Predict before coding: A Bloom filter returns “may contain” for a key that is absent from an SST. What extra work occurs, and why is the final result still correct? Now consider a filter that incorrectly returns “definitely absent” for a present key. Which storage-engine guarantee is violated?

Task 1: Bloom Filters

A Bloom filter is a probabilistic data structure that represents set membership. After adding keys, you can ask whether a key may belong to the set or definitely does not belong to it. False positives are possible; false negatives are not.

Constructing a Bloom filter requires hashing each key, usually to several bit positions. Consider the following example, in which each key has two hashes and the filter contains 7 bits:

For a more detailed introduction, see Bloom Filters by Example.

hash1 = ((character - a) * 13) % 7
hash2 = ((character - a) * 11) % 7
b -> 6 4
c -> 5 1
d -> 4 5
e -> 3 2
g -> 1 3
h -> 0 0

Inserting b, c, and d produces this filter:

    bit  0123456
insert b     1 1
insert c  1   1
insert d     11
result   0101111

To probe the filter, hash the key and inspect the corresponding bits. If every bit is set, the key may belong to the original set. If any bit is clear, the key definitely does not belong to the set.

For e -> 3 2, bit 2 is clear, so e is definitely absent. For g -> 1 3, both bits are set, so g may or may not be present. For h -> 0 0, the single referenced bit is clear, so h is definitely absent.

b -> maybe (actual: yes)
c -> maybe (actual: yes)
d -> maybe (actual: yes)
e -> MUST not (actual: no)
g -> maybe (actual: no)
h -> MUST not (actual: no)

In the previous chapter, you filtered SSTs by key range. On the get path, a Bloom filter can additionally exclude SSTs that definitely do not contain the requested key, reducing disk reads.

In this task, you will need to modify:

src/table/bloom.rs

Build the Bloom filter from u32 key hashes. For each hash, set k bits using the following sequence:

#![allow(unused)]
fn main() {
let delta = (h >> 17) | (h << 15); // h is the key hash
for _ in 0..k {
    // TODO: use the hash to set the corresponding bit
    h = h.wrapping_add(delta);
}
}

The starter code provides the remaining calculations. Implement the procedures for building and probing the filter.

Task 2: Integrate Bloom Filter on the Read Path

In this task, you will need to modify:

src/table/builder.rs
src/table.rs
src/lsm_storage.rs

Append the encoded Bloom filter to the SST file and store its offset at the end. Account for that new section when reading the metadata offset.

-----------------------------------------------------------------------------------------------------
|         Block Section         |                            Meta Section                           |
-----------------------------------------------------------------------------------------------------
| data block | ... | data block | metadata | meta block offset | bloom filter | bloom filter offset |
|                               |  varlen  |         u32       |    varlen    |        u32          |
-----------------------------------------------------------------------------------------------------

Use the farmhash crate to hash keys. While building the SST, compute each key’s hash with farmhash::fingerprint32, then build and encode the Bloom filter. When opening an SST, decode both its block metadata and its Bloom filter. Use a false-positive rate of 0.01. Add fields to the provided structures as needed.

Then update the get path to filter SSTs with their Bloom filters.

There is no integration test specifically for this optimization, so ensure that all tests from earlier chapters still pass.

Task 3: Key Prefix Encoding + Decoding

In this task, you will need to modify:

src/block/builder.rs
src/block/iterator.rs

Because an SST stores keys in sorted order, nearby keys often share a prefix. Encoding that prefix only once can save space.

Compare each key with the first key in its block, and encode it as follows:

key_overlap_len (u16) | rest_key_len (u16) | key (rest_key_len)

key_overlap_len is the length of the shared prefix, in bytes. For example, if the first key is mini-something, the record 5|3|LSM reconstructs the key mini-LSM.

After implementing the encoding, update the block iterator to reconstruct keys while decoding. Add fields to the provided structures as needed.

Chapter Checkpoint

Your Week 1 engine should now avoid many unnecessary SST reads on point lookups and avoid storing shared key-prefix bytes repeatedly. All tests from earlier chapters should continue to pass because neither optimization changes logical behavior.

Measure or inspect three things: the encoded size of a block containing keys with a long shared prefix, the number of SST iterators created by a point lookup rejected by several Bloom filters, and the result of probing known-present and known-absent keys. Explain why each observation follows from the invariants above.

Test Your Understanding

Correctness

How does a Bloom filter help filter SSTs? Which claims can it make about a key: may not exist, may exist, must exist, or must not exist?
If we need a backward iterator, how does this key compression affect it?
Can Bloom filters help with scans?

Format and Design

What are the advantages and disadvantages of prefix-encoding each key relative to the previous key rather than the first key in the block?
Why must the first key in a block have an overlap length of zero? What malformed or circular representation could result otherwise?
Compare the encoded sizes of keys that share a long prefix, keys that share no prefix, and one key larger than the target block size. When does prefix encoding provide little or no benefit?

We do not provide reference answers to these questions. Feel free to discuss them in the Discord community.

Week 2 Overview: Compaction and Persistence

Chapter Overview

In Week 1, you built the core structures of an LSM storage engine and implemented its read and write interfaces. This week, you will organize SSTs on disk, compare compaction strategies, and make the engine recoverable. The first four chapters progress from the mechanics of one compaction to increasingly realistic scheduling policies. The final three chapters persist the LSM state and unflushed writes, then protect every on-disk format with checksums.

Chapter	Before	After
Day 1: Compaction Implementation	Every flushed SST remains in L0.	The engine can merge L0 and L1 into a non-overlapping sorted run and read through it efficiently.
Day 2: Simple Leveled Compaction	Compaction runs only when requested explicitly.	A background controller maintains several levels using file-count ratios.
Day 3: Tiered/Universal Compaction	Every strategy writes new SSTs through L0.	The engine can maintain newest-to-oldest tiers and trade read and space amplification for fewer rewrites.
Day 4: Leveled Compaction	Simple leveled compaction rewrites entire levels and moves data through empty levels.	Dynamic target sizes and partial compaction reduce unnecessary rewrites and peak space usage.
Day 5: Manifest	The LSM’s file layout exists only in memory.	An append-only manifest reconstructs the durable SST layout after a restart.
Day 6: Write-Ahead Log (WAL)	Unflushed writes survive only a clean close.	WAL-backed memtables make acknowledged, synchronized writes recoverable after a crash.
Day 7: Batch Write and Checksums	Writes are submitted one at a time, and corrupted files may be consumed silently.	The engine accepts write batches and verifies the integrity of its SSTs, manifest, and WALs.

How to Use This Week

Compaction code can produce plausible-looking output while violating version order, retaining stale files, or deleting tombstones too early. Persistence code can pass restart tests while still using an unsafe write order. Treat each chapter as an exercise in preserving invariants, not only as an exercise in matching simulator output.

For each chapter:

Write down the ordering and ownership invariants before implementing the task.
Predict the next compaction task or recovered state for the chapter’s small example.
Run the focused tests and compare simulator output with the reference implementation where instructed.
Trace one overwrite and one deletion through the new structure. For persistence chapters, also trace a crash between each pair of durable writes.
Answer the correctness questions with a concrete state, execution, or corrupted byte sequence.

The simulator measures useful structural properties, but it does not prove that reads return the newest value or that concurrent flushes are retained. Likewise, a successful reopen test exercises only a few possible crash points. Use the chapter checkpoints to review the cases that automated validation does not cover.

Compaction and Read Amplification

Let us begin with compaction. In the previous part, you flushed each memtable to an L0 SST. Imagine that you have written gigabytes of data and now have 100 overlapping SSTs. Without filters, one point read might need to probe all 100 files. Read amplification is the amount of physical read work required for one logical read; in this simplified example, it is the number of blocks read from disk.

To reduce read amplification, we can merge the L0 SSTs into files with non-overlapping key ranges. A point lookup then needs to inspect at most one candidate SST in that group. The merge-and-rewrite process is compaction, and an ordered collection of non-overlapping SSTs is a sorted run.

To make this process clearer, let us take a look at this concrete example:

SST 1: key range 00000 - key 10000, 1000 keys
SST 2: key range 00005 - key 10005, 1000 keys
SST 3: key range 00010 - key 10010, 1000 keys

The three SSTs have overlapping key ranges, so a lookup for key 02333 might probe all of them. After compaction, the engine might produce these three SSTs:

SST 4: key range 00000 - key 03000, 1000 keys
SST 5: key range 03001 - key 06000, 1000 keys
SST 6: key range 06000 - key 10010, 1000 keys

The engine merges SSTs 1, 2, and 3, resolves duplicate keys, and splits the sorted result to avoid producing one oversized file. The three output SSTs have non-overlapping ranges, so a lookup for key 02333 needs to inspect only SST 4.

Two Extremes of Compaction and Write Amplification

The example suggests two extremes: never compact, or run a full compaction after every flush.

Compaction consumes CPU and I/O because it reads input files and writes replacement files. Never compacting avoids rewrites but causes high read amplification. Always running full compaction lowers read amplification but repeatedly rewrites the entire database.

no compaction

No Compaction at All

always full compaction

Always compact when new SST being flushed

Write amplification is the ratio of total physical bytes written to the logical bytes flushed into the LSM tree. With no compaction, the ratio is 1x because each SST is written once and never rewritten. Compacting everything after every flush has very high write amplification: after 100 equal-sized flushes, the engine rewrites approximately 2 + 3 + … + 100 SSTs’ worth of data. It therefore writes about 5,000 SSTs’ worth for 100 SSTs of logical input, or roughly 50x write amplification.

A good compaction strategy balances read, write, and space amplification. A general-purpose LSM storage engine cannot minimize all three simultaneously unless it can exploit a specific workload pattern. Because compaction happens in the background, the engine can select a strategy and tune its parameters as the workload changes. Compaction policy is therefore an explicit choice about which costs to trade for others.

compaction tradeoffs

A common production workload begins with a high-throughput bulk ingest and later shifts to small online transactions. During ingestion, the engine can favor low write amplification. Before serving the online workload, it can retune compaction for lower read amplification and reorganize the existing data.

For a time-series workload, users might append and expire data in time order. Such a pattern can have low amplification even with little compaction. In practice, observe the workload and its requirements rather than selecting a policy from aggregate ratios alone.

Compaction Strategies Overview

Compaction strategies control the number and sizes of sorted runs to keep read amplification within a chosen bound. They generally fall into two categories: leveled and tiered.

In leveled compaction, the user specifies a maximum number of levels, excluding L0. Each level is one sorted run. A compaction merges data from two adjacent levels and places the output in the lower one, so a relatively small sorted run is often merged into a much larger run. Target level sizes grow geometrically according to a configured multiplier.

leveled compaction

In tiered compaction, each flush can create a new sorted run, or tier, and the engine merges tiers to control their count. The policy often merges runs of similar sizes, reducing write amplification compared with repeatedly merging a small run into a large one. Allowing too many tiers, however, increases read amplification. This course implements RocksDB’s universal compaction, a tiered strategy.

tiered compaction

Space Amplification

The most intuitive measure of space amplification is the physical space used by the LSM engine divided by the logical size of the live user data. Tombstones and obsolete versions consume space until compaction can remove them.

The engine cannot know the exact logical data size without scanning for obsolete versions. One practical estimate divides the total SST size by the last level’s size. This estimate assumes a steady-state workload whose logical size remains roughly constant: the bottom level approximates an older complete snapshot, while upper levels contain subsequent changes. After a full compaction moves all live data to the bottom, the estimate approaches 1x.

Compaction also requires temporary space because its input files cannot be removed before the output is complete and durable. A full compaction may therefore require free space comparable to the current database size.

The compaction simulator visualizes each scheduling decision and reports its amplification statistics. The tests check only a few structural properties, so inspect the simulator output closely and compare it with the reference implementation.

Persistence

After implementing the compaction algorithms, you will add two persistence components: the manifest, which records structural changes to the LSM tree, and the WAL, which preserves memtable updates before they are flushed to SSTs. Together they let the engine reconstruct both its on-disk layout and its unflushed state after a restart.

If you do not want to explore every compaction policy, complete Days 1 and 2 and then continue to persistence. Universal compaction and dynamic leveled compaction are not required to build a working Week 2 engine.

Snack Time

After implementing compaction and persistence, we will have a short chapter on implementing the batch write interface and checksums.

Before moving to Week 3, check that you can explain:

how every compaction input is ordered and why the newest version wins;
when a tombstone may be discarded and why dropping it earlier can resurrect a value;
how leveled and tiered policies trade read, write, and space amplification;
how a compaction result is installed without losing an L0 flush that completed concurrently;
which facts belong in the manifest and which bytes belong in a WAL;
the required durable-write order for creating and deleting files;
what each checksum covers and how a decoder finds that exact byte range.

Compaction Implementation

Chapter Overview

By the end of this chapter, you will be able to:

Implement the compaction logic that combines some files and produces new files.
Install a compaction result without losing SSTs flushed concurrently.
Update the LSM read path to incorporate non-overlapping sorted runs.
Explain why iterator priority and the destination level determine whether a tombstone can be discarded.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 1
cargo x scheck

Read the Week 2 overview before beginning this chapter for an introduction to compaction and amplification.

Before You Begin

At the end of Week 1, every flush creates a new L0 SST. L0 files can have overlapping key ranges and are stored from newest to oldest. This chapter introduces L1, one sorted run whose SSTs have non-overlapping key ranges and are ordered by their first keys.

Keep these invariants in mind while implementing the tasks:

When several inputs contain the same key, the iterator representing the newest source must win.
L0 may overlap, but the SSTs produced for L1 must be ordered and non-overlapping.
A tombstone may be discarded only when the compaction includes every possible older version of that key. In this chapter, full compaction targets the bottom level, so that condition holds.
Merging and writing output SSTs happens outside state_lock. Installing the result happens while holding it, and must remove only the files named by the task. An L0 SST flushed after the task was created must remain in the new state.
If every surviving entry is a tombstone, compaction produces no SST rather than building an empty one.

Predict before coding: A full-compaction task captures L0 files [5, 4] and L1 files [1, 2]. While it is writing output SSTs, file 6 is flushed to the front of L0. Which files should remain in L0 after the result is installed? If the newest value of k in file 5 is a tombstone and an older value is in file 1, should either entry appear in the output?

Task 1: Compaction Implementation

In this task, implement the core compaction operation: merge a set of SSTs into a sorted run. You will need to modify:

src/compact.rs

Specifically, implement the force_full_compaction and compact functions. force_full_compaction chooses the files and installs the result in the LSM state. compact performs the merge and returns a set of new SSTs.

Use MergeIterator to merge every SST captured by the task, then write the surviving entries through SsTableBuilder. Split the output when it reaches the target SST size. After the merge finishes, install the output as the L1 sorted run and remove the obsolete inputs from the state and filesystem. At this stage, SSTs appear only in L0 or L1, so LsmStorageState::levels contains one entry.

Compaction should not block L0 flushes. Do not hold state_lock while merging files and writing outputs. Acquire it only when installing the result, and release it immediately after the structural update and manifest record are complete.

You may assume that only one compaction runs at a time. The SSTs installed in L1 must be sorted by first key and have non-overlapping key ranges.

Spoilers: Compaction Pseudo Code

#![allow(unused)]
fn main() {
fn force_full_compaction(&self) {
    let ssts_to_compact = {
        let state = self.state.read();
        state.l0_sstables + state.levels[0]
    };
    let new_ssts = self.compact(FullCompactionTask(ssts_to_compact))?;
    {
        let state_lock = self.state_lock.lock();
        let state = self.state.write();
        state.l0_sstables.remove(/* the ones being compacted */);
        state.levels[0] = new_ssts; // new SSTs added to L1
    };
    std::fs::remove(ssts_to_compact)?;
}
}

For now, compact needs to handle only ForceFullCompaction, whose task lists the input SSTs. Preserve source priority so that the newest version of each key reaches the output.

Because this task includes every SST, retain only the newest version of each key. If that version is a tombstone, omit it from the output. Later chapters compact only part of the tree, so they cannot always discard tombstones.

Before moving on, account for these two cases:

How does your implementation retain an L0 SST flushed while compaction is in progress?
Can a reader using an older state snapshot finish after the input filenames are unlinked? On Unix-like systems, an open file remains accessible until its final handle is closed.

Task 2: Concat Iterator

In this task, you will need to modify:

src/iterators/concat_iterator.rs

A sorted run does not need a merge iterator: its SSTs are ordered and have non-overlapping ranges, so a concat iterator can visit them sequentially. Store the SST objects and create only the active child iterator. Creating every child in advance would read the first block of every SST unnecessarily.

Task 3: Integrate with the Read Path

In this task, you will need to modify:

src/lsm_iterator.rs
src/lsm_storage.rs
src/compact.rs

Now update the two-level read path to use the concat iterator for L1.

Change the inner iterator type of LsmStorageIterator. Merge the memtable and L0 iterators first, then use TwoMergeIterator to combine that newer stream with the L1 concat iterator.

You can also change your compaction implementation to leverage the concat iterator.

Implement num_active_iterators for the concat iterator. For this exercise, it should always report one active iterator.

To test your implementation interactively,

cargo run --bin mini-lsm-cli-ref -- --compaction none # reference solution
cargo run --bin mini-lsm-cli -- --compaction none # your solution

And then,

fill 1000 3000
flush
fill 1000 3000
flush
full_compaction
fill 1000 3000
flush
full_compaction
get 2333
scan 2000 2333

Chapter Checkpoint

Your engine should now compact the captured L0 and L1 inputs into zero or more ordered L1 SSTs, retain L0 files created after the task snapshot, and serve get and scan through both overlapping and non-overlapping sources.

In addition to passing the tests, verify three cases explicitly:

Give two input SSTs the same key and confirm that reversing their merge priority changes the result.
Compact an input containing only tombstones and confirm that no empty SST is created.
Seek a concat iterator into the second or later SST and confirm that it opens only the active child iterator.

Test Your Understanding

Answer correctness questions with a concrete LSM state or execution. For amplification questions, state what you count in the numerator and denominator.

Correctness and Concurrency

Construct the smallest input in which reversing L0 iterator priority preserves a stale value. Then construct one in which it resurrects a deleted value.
Why is it safe to discard tombstones during this chapter’s full compaction? Give a counterexample showing why the same rule is unsafe when compacting into a non-bottom level.
How does your implementation retain an L0 SST flushed while compaction is writing its output?
What should apply_compaction_result do when compaction produces no SSTs?
If your implementation removes the original SST files immediately after installing the new state, can a reader using an older state snapshot still finish? How does the answer depend on filesystem semantics?
What ordering and non-overlap properties must hold before SstConcatIterator is safe to use?

Performance and Design

What are the definitions of read/write/space amplifications? (This is covered in the overview chapter)
What are the ways to accurately compute the read/write/space amplifications, and what are the ways to estimate them?
Is it correct that a key will take some storage space even if a user requests to delete it?
Because compaction consumes read and write bandwidth, should the engine postpone or pause it during heavy foreground traffic? What new problem could that create? Read SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores.
Is it a good idea to use/fill the block cache for compactions? Or is it better to fully bypass the block cache when compaction?
Does it make sense to have a struct ConcatIterator<I: StorageIterator> in the system?
Some researchers/engineers propose to offload compaction to a remote server or a serverless lambda function. What are the benefits, and what might be the potential challenges and performance impacts of doing remote compaction? (Think of the point when a compaction completes and what happens to the block cache on the next read request…)

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Simple Compaction Strategy

Chapter Overview

By the end of this chapter, you will be able to:

Implement a simple leveled compaction strategy and simulate it on the compaction simulator.
Run compaction as a background task and install its results safely.
Extend point reads and scans across multiple non-overlapping levels.
Explain how level ratios, merge priority, and bottom-level tombstone removal affect correctness and amplification.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 2
cargo x scheck

Read the Week 2 overview before beginning this chapter for an introduction to compaction and amplification.

Before You Begin

Day 1 compacted the entire database into L1 on demand. Simple leveled compaction introduces a controller that chooses one adjacent pair of levels at a time and a background thread that repeatedly asks the controller for work.

Keep these invariants in mind:

L0 is ordered from newest to oldest and may overlap. Each level from L1 downward is one sorted, non-overlapping run.
In a merge, the upper level contains newer versions than the lower level and must win on duplicate keys. For L0, individual files also need newest-to-oldest priority.
generate_compaction_task must eventually return None; otherwise, the simulator and background worker cannot converge.
Applying an L0 task removes exactly the captured L0 files, not files flushed after the task was generated.
Tombstones are preserved until the task’s lower level is the bottom-most level.

Predict before coding: With size_ratio_percent = 200, suppose L1 has two files, L2 has three, and L3 has eight. Which adjacent pair should be compacted next? If a new L0 file is flushed while that task runs, should applying the result change L0?

Task 1: Simple Leveled Compaction

In this task, implement the first scheduling policy: simple leveled compaction. You will need to modify:

src/compact/simple_leveled.rs

Simple leveled compaction is similar to the strategy in the original LSM-tree paper. It maintains a fixed number of levels. When a level at or below L1 is too large relative to the next level, the engine merges all of its SSTs with that lower level. Three parameters in SimpleLeveledCompactionOptions control the policy.

size_ratio_percent: the target ratio of lower-level files to upper-level files. A production system would compare byte sizes, but this exercise compares file counts for simpler simulation. Trigger compaction when the actual ratio falls below this value.
level0_file_num_compaction_trigger: when L0 contains at least this many SSTs, compact L0 with L1.
max_levels: the number of levels (excluding L0) in the LSM tree.

Consider size_ratio_percent = 200, max_levels = 3, and level0_file_num_compaction_trigger = 2. Each lower level should contain at least twice as many files as the level above it.

Assume the engine flushes two L0 SSTs. This reaches the level0_file_num_compaction_trigger, and your controller should trigger an L0->L1 compaction.

--- After Flush ---
L0 (2): [1, 2]
L1 (0): []
L2 (0): []
L3 (0): []
--- After Compaction ---
L0 (0): []
L1 (2): [3, 4]
L2 (0): []
L3 (0): []

L2 is empty while L1 has two files, so (L2 / L1) * 100 = (0 / 2) * 100 = 0, which is below 200. The controller compacts L1 with L2. The same condition then holds between L2 and L3, so a second compaction moves the two files to the bottom level.

--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (2): [5, 6]
L3 (0): []
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (2): [7, 8]

After more flushes and compactions, the state can become:

L0 (0): []
L1 (0): []
L2 (2): [13, 14]
L3 (2): [7, 8]

At this point, (L3 / L2) * 100 = (2 / 2) * 100 = 100, which is below 200. The controller compacts L2 with L3.

--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]

After additional flushes, the state might become:

--- After Flush ---
L0 (2): [19, 20]
L1 (0): []
L2 (0): []
L3 (4): [15, 16, 17, 18]
--- After Compaction ---
L0 (0): []
L1 (0): []
L2 (2): [23, 24]
L3 (4): [15, 16, 17, 18]

Because L3/L2 = (4 / 2) * 100 = 200 >= size_ratio_percent (200), we do not need to merge L2 and L3. Simple leveled compaction always compacts a full level and maintains a target fanout between adjacent levels.

The LSM state already contains max_levels levels. First implement the L0 trigger in generate_compaction_task and inspect a simulation. Then add the size-ratio trigger and implement apply_compaction_result. Run the simulator with:

cargo run --bin compaction-simulator-ref simple # Reference solution
cargo run --bin compaction-simulator simple # Your solution

The simulator flushes an L0 SST, asks the controller for a task, and applies the result. After each flush, it repeatedly invokes the controller until no task remains, so your scheduling policy must converge.

Use concat iterators for sorted runs to minimize active child iterators. Merge order still determines which version of a duplicate key survives, so construct every input in newest-to-oldest priority order.

Some values are zero-based vector indexes, while level numbers begin at one. Convert between them explicitly.

Note: we do not provide fine-grained unit tests for this part. You can run the compaction simulator and compare with the output of the reference solution to see if your implementation is correct.

Task 2: Compaction Thread

In this task, you will need to modify:

src/compact.rs

Run the controller from a background thread. trigger_compaction is called every 50 ms and should:

Generate a compaction task. If no task needs to be scheduled, return successfully.
Run the compaction and obtain a list of new SSTs.
As in force_full_compaction, install the result in the current LSM state.

Task 3: Integrate with the Read Path

In this task, you will need to modify:

src/lsm_iterator.rs
src/lsm_storage.rs

Extend both get and scan across every level below L1. Change the inner type of LsmStorageIterator so that it merges one SstConcatIterator per level.

To test your implementation interactively,

cargo run --bin mini-lsm-cli-ref -- --compaction simple # reference solution
cargo run --bin mini-lsm-cli -- --compaction simple # your solution

And then,

fill 1000 3000
flush
fill 1000 3000
flush
fill 1000 3000
flush
get 2333
scan 2000 2333

You may print something, for example, the compaction task information, when the compactor triggers a compaction.

Chapter Checkpoint

Your engine should now schedule simple leveled compactions in the background, preserve newer values across every merge, and read through all configured levels. The simulator should reach a state in which no further task is eligible.

Compare a short simulator run with the reference output, then alter one parameter at a time. Explain why each task was selected, identify whether it reaches the bottom level, and verify that the next state still contains any L0 file created after the task snapshot.

Test Your Understanding

Correctness and Scheduling

For a duplicate key present in both levels of a task, why must the upper-level iterator win? What stale result appears if the priority is reversed?
Why may a bottom-level compaction discard a tombstone while an L1-to-L2 compaction might need to retain it?
Construct a level-size configuration that causes an implementation with reversed ratio operands to select the wrong task.
What state must be rechecked when a background compaction finishes, and which concurrent change is expected rather than an error?
Can you merge L1 and L3 directly if there are SST files in L2? Does it still produce the correct result?

Amplification and Design

What is the estimated write amplification of leveled compaction?
What is the estimated read amplification of leveled compaction?
Is it correct that a key will only be purged from the LSM tree if the user requests to delete it and it has been compacted in the bottom-most level?
Is it a good strategy to periodically do a full compaction on the LSM tree? Why or why not?
Actively choosing some old files/levels to compact even if they do not violate the level amplifier would be a good choice, is it true? (Look at the Lethe paper!)
If the storage device can achieve a sustainable 1GB/s write throughput and the write amplification of the LSM tree is 10x, how much throughput can the user get from the LSM key-value interfaces?
So far, SST filenames have used monotonically increasing IDs. What problems might arise from naming a file <level>_<begin_key>_<end_key>.sst instead? Revisit this question in Week 3.
What is your favorite boba shop in your city? (If you answered yes in week 1 day 3…)

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Tiered Compaction Strategy

Chapter Overview

By the end of this chapter, you will be able to:

Implement a tiered compaction strategy and simulate it on the compaction simulator.
Incorporate tiered compaction into the engine’s flush, compaction, and read paths.
Explain how universal compaction’s three triggers trade write, read, and space amplification.
Preserve newest-to-oldest tier order and determine whether a task includes the bottom tier.

This chapter’s tiered policy is RocksDB’s universal compaction. The chapter uses the two terms interchangeably.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 3
cargo x scheck

Read the Week 2 overview before beginning this chapter for an introduction to compaction and amplification.

Before You Begin

Unlike leveled compaction, tiered compaction treats each flush as a new sorted run. The levels vector is repurposed to store tiers from newest to oldest; the numeric ID names a tier rather than describing a fixed depth.

Keep these invariants in mind:

levels[0] is the newest tier, and every tier is internally sorted and non-overlapping.
A tiered task selects a contiguous prefix of tiers. The merge iterator must use the same newest-to-oldest order so that newer versions win.
The controller considers triggers in order: minimum tier count, space amplification, size ratio, then reduction of sorted runs.
bottom_tier_included is true only if the selected prefix contains the oldest tier. Tombstones must remain when an older tier is left out.
A flush creates a one-SST tier at the front of levels; it does not add an L0 file.

Predict before coding: Suppose the tiers from newest to oldest have sizes [1, 1, 3, 20], and the reduce-sorted-runs trigger is capped at max_merge_width = 2. Which tiers are selected? Does the task include the bottom tier, and may it discard a tombstone whose older value could be in the 20-file tier?

Task 1: Universal Compaction

You will implement a simplified form of RocksDB’s universal compaction. As in simple leveled compaction, the controller uses file counts rather than byte sizes. A task always includes each selected tier in full.

Task 1.0: Precondition

In this task, you will need to modify:

src/compact/tiered.rs

In universal compaction, the LSM state does not use L0. Instead, each memtable flush creates a single-SST sorted run, or tier. The levels vector stores all tiers, with the newest tier at the lowest index. Each element is a tuple containing a tier ID and the SST IDs in that tier. Place every newly flushed SST in a tier at the front of the vector. The compaction simulator uses the first output SST ID as the tier ID; your implementation should do the same.

Universal compaction will only trigger tasks when the number of tiers (sorted runs) reaches num_tiers. Otherwise, it does not trigger any compaction.

Task 1.1: Triggered by Space Amplification Ratio

The first trigger of universal compaction is by space amplification ratio. As we discussed in the overview chapter, space amplification can be estimated by engine_size / last_level_size. In our implementation, we compute the space amplification ratio by all levels except last level size / last level size, so that the ratio can be scaled to [0, +inf) instead of [1, +inf]. This is also consistent with the RocksDB implementation.

This estimate models a fixed logical dataset—for example, 100 GB—that receives repeated updates. The bottom tier approximates the logical dataset, while upper tiers contain newer changes that have not yet reached the bottom. The implementation expresses excess space as upper_tier_size / bottom_tier_size, producing a range from zero upward.

Trigger full compaction when upper_tier_size / bottom_tier_size is at least max_size_amplification_percent / 100. For example:

Tier 3: 1
Tier 2: 1 ; all levels except last level size = 2
Tier 1: 1 ; last level size = 1, 2/1=2

Assume max_size_amplification_percent = 200, we should trigger a full compaction now.

After you implement this trigger, you can run the compaction simulator. You will see:

cargo run --bin compaction-simulator tiered --iterations 10

=== Iteration 2 ===
--- After Flush ---
L3 (1): [3]
L2 (1): [2]
L1 (1): [1]
--- Compaction Task ---
compaction triggered by space amplification ratio: 200
L3 [3] L2 [2] L1 [1] -> [4, 5, 6]
--- After Compaction ---
L4 (3): [3, 2, 1]

With only this trigger implemented, the end of the simulation includes states like:

cargo run --bin compaction-simulator tiered

=== Iteration 7 ===
--- After Flush ---
L8 (1): [8]
L7 (1): [7]
L6 (1): [6]
L5 (1): [5]
L4 (1): [4]
L3 (1): [3]
L2 (1): [2]
L1 (1): [1]
--- Compaction Task ---
--- Compaction Task ---
compaction triggered by space amplification ratio: 700
L8 [8] L7 [7] L6 [6] L5 [5] L4 [4] L3 [3] L2 [2] L1 [1] -> [9, 10, 11, 12, 13, 14, 15, 16]
--- After Compaction ---
L9 (8): [8, 7, 6, 5, 4, 3, 2, 1]
--- Compaction Task ---
1 compaction triggered in this iteration
--- Statistics ---
Write Amplification: 16/8=2.000x
Maximum Space Usage: 16/8=2.000x
Read Amplification: 1x

=== Iteration 49 ===
--- After Flush ---
L82 (1): [82]
L81 (1): [81]
L80 (1): [80]
L79 (1): [79]
L78 (1): [78]
L77 (1): [77]
L76 (1): [76]
L75 (1): [75]
L74 (1): [74]
L73 (1): [73]
L72 (1): [72]
L71 (1): [71]
L70 (1): [70]
L69 (1): [69]
L68 (1): [68]
L67 (1): [67]
L66 (1): [66]
L65 (1): [65]
L64 (1): [64]
L63 (1): [63]
L62 (1): [62]
L61 (1): [61]
L60 (1): [60]
L59 (1): [59]
L58 (1): [58]
L57 (1): [57]
L33 (24): [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 9, 10, 11, 12, 13, 14, 15, 16]
--- Compaction Task ---
--- Compaction Task ---
no compaction triggered
--- Statistics ---
Write Amplification: 82/50=1.640x
Maximum Space Usage: 50/50=1.000x
Read Amplification: 27x

The simulator sets num_tiers to 8, but the state can still grow far beyond eight tiers because the threshold only enables scheduling; the space trigger does not guarantee that it will choose a task. This causes high read amplification.

The current trigger controls space amplification only. The next two triggers limit read amplification.

Task 1.2: Triggered by Size Ratio

The size-ratio trigger maintains geometric growth between tiers. Starting with the newest tier, compare each next tier’s size with the total size of all newer tiers. At the first ratio greater than (100 + size_ratio) / 100, compact the newer prefix but exclude the tier that satisfied the ratio. Schedule the task only when the prefix contains at least min_merge_width tiers.

For example, with size_ratio = 1 and min_merge_width = 2, compact when the ratio exceeds 101%:

Tier 3: 1
Tier 2: 1 ; 1 / 1 = 1
Tier 1: 1 ; 1 / (1 + 1) = 0.5, no compaction triggered

Example 2:

Tier 3: 1
Tier 2: 1 ; 1 / 1 = 1
Tier 1: 3 ; 3 / (1 + 1) = 1.5, compact tier 2+3

Tier 4: 2
Tier 1: 3

Example 3:

Tier 3: 1
Tier 2: 2 ; 2 / 1 = 2, however, it does not make sense to compact only one tier; also note that min_merge_width=2
Tier 1: 4 ; 4 / 3 = 1.33, compact tier 2+3

Tier 4: 3
Tier 1: 4

With this trigger, you will observe the following in the compaction simulator:

cargo run --bin compaction-simulator tiered

=== Iteration 49 ===
--- After Flush ---
L119 (1): [119]
L118 (1): [118]
L114 (4): [113, 112, 111, 110]
L105 (5): [104, 103, 102, 101, 100]
L94 (6): [93, 92, 91, 90, 89, 88]
L81 (7): [80, 79, 78, 77, 76, 75, 74]
L48 (26): [47, 46, 45, 44, 43, 37, 38, 39, 40, 41, 42, 24, 25, 26, 27, 28, 29, 30, 9, 10, 11, 12, 13, 14, 15, 16]
--- Compaction Task ---
--- Compaction Task ---
no compaction triggered
--- Statistics ---
Write Amplification: 119/50=2.380x
Maximum Space Usage: 52/50=1.040x
Read Amplification: 7x

cargo run --bin compaction-simulator tiered --iterations 200 --size-only

=== Iteration 199 ===
--- After Flush ---
Levels: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 10 15 21 28 78
no compaction triggered
--- Statistics ---
Write Amplification: 537/200=2.685x
Maximum Space Usage: 200/200=1.000x
Read Amplification: 38x

This trigger produces fewer one-SST tiers and tends to keep tiers ordered from smaller to larger. The state can still exceed num_tiers, so one final trigger is required.

Task 1.3: Reduce Sorted Runs

If none of the previous triggers produce a task, merge the first max_merge_width tiers into one tier to reduce the number of sorted runs. If max_merge_width is not set, select all tiers. Remember that a capped prefix does not include the bottom tier when older tiers remain.

With this compaction trigger enabled, you will see:

cargo run --bin compaction-simulator-ref tiered --iterations 200 --size-only

=== Iteration 199 ===
--- After Flush ---
Levels: 0 1 1 4 5 21 28 140
no compaction triggered
--- Statistics ---
Write Amplification: 742/200=3.710x
Maximum Space Usage: 280/200=1.400x
Read Amplification: 7x

You can also try tiered compaction with a larger tier limit:

cargo run --bin compaction-simulator tiered --iterations 200 --size-only --num-tiers 16

=== Iteration 199 ===
--- After Flush ---
Levels: 0 1 1 1 1 1 1 1 1 1 1 15 175
no compaction triggered
--- Statistics ---
Write Amplification: 607/200=3.035x
Maximum Space Usage: 350/200=1.750x
Read Amplification: 12x

Note: we do not provide fine-grained unit tests for this part. You can run the compaction simulator and compare with the output of the reference solution to see if your implementation is correct.

Task 2: Integrate with the Read Path

In this task, you will need to modify:

src/compact.rs
src/lsm_storage.rs

Tiered compaction does not use L0, so flush each memtable directly to a new tier. Use self.compaction_controller.flush_to_l0() to choose between the leveled and tiered flush paths. Name a compacted tier with its first output SST ID, and construct the compaction merge iterators in newest-to-oldest tier order.

Chapter Checkpoint

Your engine should now flush directly into newest-first tiers, schedule the first eligible universal-compaction trigger, and retain tombstones whenever a task leaves older tiers behind. A task that includes the bottom tier may legitimately produce no SSTs when all surviving entries are tombstones.

For several simulator iterations, annotate each task with the trigger that selected it, the tiers it consumes, and whether it reaches the bottom. Then use one duplicate key to verify merge priority across tiers. Finally, test a capped max_merge_width and confirm that the task does not claim to include an unselected bottom tier.

Universal Compaction - RocksDB Wiki

Test Your Understanding

Correctness and Scheduling

Why must every task select adjacent tiers from the newest end of the state? Construct a counterexample for a task that merges two non-adjacent tiers and places the output incorrectly.
When max_merge_width limits a task to only the newest tiers, why must bottom_tier_included be false?
What should the new LSM state contain if a bottom-tier compaction produces no output because every surviving entry is a tombstone?
Construct a tier-size sequence for which the space-amplification trigger wins, and another for which the size-ratio trigger wins.
If a new tier is flushed while a task is running, where should the compacted output be inserted relative to that tier?

Amplification and Design

What is the estimated write amplification of tiered compaction? This is difficult in general; begin by ignoring the final reduce sorted runs trigger.
What is the estimated read amplification of tiered compaction?
What are the advantages and disadvantages of universal compaction compared with leveled compaction?
How much free storage space does universal compaction require relative to the logical data size?
What happens if compaction speed cannot keep up with the SST flushes for tiered compaction?
What must the system consider before scheduling multiple compaction tasks in parallel?
SSDs also write its own logs (basically it is a log-structured storage). If the SSD has a write amplification of 2x, what is the end-to-end write amplification of the whole system? Related: ZNS: Avoiding the Block Interface Tax for Flash-based SSDs.
Consider the case that the user chooses to keep a large number of sorted runs (i.e., 300) for tiered compaction. To make the read path faster, is it a good idea to keep some data structure that helps reduce the time complexity (i.e., to O(log n)) of finding SSTs to read in each layer for some key ranges? Note that normally, you will need to do a binary search in each sorted run to find the key ranges that you will need to read. (Check out Neon’s layer map implementation!)

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Leveled Compaction Strategy

Chapter Overview

By the end of this chapter, you will be able to:

Implement dynamic leveled compaction and simulate it with the compaction simulator.
Select a base level, rank overfull levels, and compact one upper-level SST with all overlapping lower-level SSTs.
Incorporate leveled compaction into the engine’s read and compaction paths.
Explain why normal execution and manifest recovery require different result-application steps.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 4
cargo x scheck

Read the Week 2 overview before beginning this chapter for an introduction to compaction and amplification.

Before You Begin

Simple leveled compaction established the basic level structure, but it rewrites whole levels and moves new data through levels whose target size is zero. This chapter makes both task selection and result application depend on SST sizes and key ranges.

Keep these invariants in mind:

L0 may overlap and is ordered newest to oldest. Every lower level is sorted by first key and contains non-overlapping SST ranges.
The first level with a positive target size is the base level. L0 compaction targets it directly and has priority over size-based tasks.
A non-L0 task selects exactly one upper-level SST and every lower-level SST whose inclusive key range overlaps it.
The upper source is newer and wins duplicate keys. Tombstones are discarded only when the lower level is the bottom-most level.
Applying the result removes exactly the selected files and restores first-key order in the lower level. During manifest replay, the SST objects are not loaded yet, so sorting must be deferred until recovery opens them.

Predict before coding: The selected upper SST covers [100, 200]; the lower level contains [50, 99], [100, 150], [151, 250], and [251, 300]. Which lower SSTs belong in the task? If the task is being replayed from the manifest before SST metadata is loaded, when can the output files be sorted by first key?

Task 1: Leveled Compaction

On Day 2, you implemented simple leveled compaction. That strategy has two important limitations:

Each task includes an entire level. Because input files cannot be removed until the output is complete and durable, full-level compaction can temporarily double the space used by the selected data. Tiered compaction has the same problem. Partial compaction reduces peak space by selecting one upper-level SST at a time.
New data moves through empty levels. Starting from an empty tree, simple leveled compaction first moves L0 to L1, then L1 to L2, and so on. Sending L0 directly to the lowest level with a positive target size avoids these unnecessary rewrites.

In this chapter, you will implement a more realistic leveled compaction strategy based on RocksDB’s design. You will need to modify:

src/compact/leveled.rs

To run the compaction simulator,

cargo run --bin compaction-simulator leveled

Task 1.1: Compute Target Sizes

This strategy needs each SST’s size and inclusive first-to-last key range. The simulator supplies mock SST metadata.

First compute the target size of each level. With base_level_size_mb = 200 and six levels below L0, an empty LSM tree has these targets:

[0 0 0 0 0 200MB]

Until the bottom level exceeds 200 MB, every intermediate level has a target size of zero. Small databases do not benefit from populating those levels.

Once the bottom level reaches the base size, work upward by dividing each lower target by level_size_multiplier. If the bottom contains 300 MB and the multiplier is 10, the targets are:

0 0 0 0 30MB 300MB

At most one level may have a positive target below base_level_size_mb. If the bottom level contains 30 GB, the targets are:

0 0 30MB 300MB 3GB 30GB

Notice in this case L1 and L2 have target size of 0, and L3 is the only level with a positive target size below base_level_size_mb.

Task 1.2: Decide Base Level

To avoid moving SSTs through empty levels, compact L0 with the first level whose target size is positive. For example, given these targets:

0 0 0 0 30MB 300MB

We will compact L0 SSTs with L5 SSTs if the number of L0 SSTs reaches the level0_file_num_compaction_trigger threshold.

Now, you can generate L0 compaction tasks and run the compaction simulator.

--- After Flush ---
L0 (1): [23]
L1 (0): []
L2 (0): []
L3 (2): [19, 20]
L4 (6): [11, 12, 7, 8, 9, 10]

...

--- After Flush ---
L0 (2): [102, 103]
L1 (0): []
L2 (0): []
L3 (18): [42, 65, 86, 87, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 61, 62, 52, 34]
L4 (6): [11, 12, 7, 8, 9, 10]

The number of levels in the compaction simulator is 4. Therefore, the SSTs should be directly flushed to L3/L4.

Task 1.3: Decide Level Priorities

After checking the L0 trigger, compute each lower level’s priority as current_size / target_size. Only ratios greater than 1.0 are eligible. Compact the level with the highest priority into the next level. For example:

L3: 200MB, target_size=20MB
L4: 202MB, target_size=200MB
L5: 1.9GB, target_size=2GB
L6: 20GB, target_size=20GB

The priority of compaction will be:

L3: 200MB/20MB = 10.0
L4: 202MB/200MB = 1.01
L5: 1.9GB/2GB = 0.95

L3 and L4 are over their targets, while L5 is not. L3 has the highest priority, so the controller selects an L3-to-L4 task. After that task completes, L4 might become eligible for compaction into L5.

Task 1.4: Select SST to Compact

To avoid compacting a full level, select only the oldest SST in the chosen upper level. SST IDs increase monotonically, so the smallest ID identifies the oldest file.

There are other ways of choosing the compacting SST, for example, by looking into the number of delete tombstones. You can implement this as part of the bonus task.

After choosing the upper SST, find every lower-level SST whose key range overlaps it. The task contains exactly one upper SST and all of those lower SSTs.

When compaction completes, remove the selected files and insert the outputs in the correct lower-level position. In every level except L0, keep SST IDs ordered by first key.

Running the compaction simulator, you should see:

--- After Compaction ---
L0 (0): []
L1 (4): [222, 223, 208, 209]
L2 (5): [206, 196, 207, 212, 165]
L3 (11): [166, 120, 143, 144, 179, 148, 167, 140, 189, 180, 190]
L4 (22): [113, 85, 86, 36, 46, 37, 146, 100, 147, 203, 102, 103, 65, 81, 105, 75, 82, 95, 96, 97, 152, 153]

The sizes of the levels should be kept under the level multiplier ratio. And the compaction task:

Upper L1 [224.sst 7cd080e..=33d79d04]
Lower L2 [210.sst 1c657df4..=31a00e1b, 211.sst 31a00e1c..=46da9e43] -> [228.sst 7cd080e..=1cd18f74, 229.sst 1cd18f75..=31d616db, 230.sst 31d616dc..=46da9e43]

…should contain only one SST from the upper level.

Note: we do not provide fine-grained unit tests for this part. You can run the compaction simulator and compare with the output of the reference solution to see if your implementation is correct.

Task 2: Integrate Leveled Compaction

In this task, you will need to modify:

src/compact.rs

Extend compaction dispatch and iterator construction for LeveledCompactionTask. The Day 2 read path already scans an arbitrary list of levels, so get and scan require no additional change here.

Chapter Checkpoint

Your controller should now compute dynamic target sizes, send L0 directly to the base level, and otherwise select one SST from the most overfull eligible level. Applying a result must preserve non-overlap and first-key order without requiring SST metadata during manifest replay.

For one simulator task, calculate the target sizes and priorities by hand. Verify the chosen upper SST and enumerate every overlapping lower SST using inclusive endpoints. Then replay the same task with in_recovery = true and explain why sorting at that point would fail.

Leveled Compaction - RocksDB Wiki

Test Your Understanding

Correctness and Scheduling

Why does L0 compaction take priority over a lower level with a larger size score?
Construct an overlap example that fails if endpoint equality is treated as non-overlapping.
Why must output SSTs be merged with untouched lower-level SSTs and sorted by first key?
What information is unavailable while manifest records are being replayed, and what phase of recovery makes it available?
If a new L0 file appears while an L0-to-base-level task runs, how does result application retain it?

Amplification and Design

What is the estimated write amplification of leveled compaction?
What is the estimated read amplification of leveled compaction?
Finding a good key split point for compaction may potentially reduce the write amplification, or it does not matter at all? (Consider that case that the user write keys beginning with some prefixes, 00 and 01. The number of keys under these two prefixes are different and their write patterns are different. If we can always split 00 and 01 into different SSTs…)
Imagine that a user was using tiered (universal) compaction before and wants to migrate to leveled compaction. What might be the challenges of this migration? And how to do the migration?
And if we do it reversely, what if the user wants to migrate from leveled compaction to tiered compaction?
What happens if compaction speed cannot keep up with the SST flushes for leveled compaction?
What must the system consider before scheduling multiple compaction tasks in parallel?
What is the peak storage usage for leveled compaction? Compared with universal compaction?
Is it true that with a lower level_size_multiplier, you can always get a lower write amplification?
What needs to be done if a user not using compaction at all decides to migrate to leveled compaction?
Some people propose to do intra-L0 compaction (compact L0 tables and still put them in L0) before pushing them to lower layers. What might be the benefits of doing so? (Might be related: PebblesDB SOSP’17)
Consider the case that the upper level has two tables of [100, 200], [201, 300] and the lower level has [50, 150], [151, 250], [251, 350]. In this case, do you still want to compact one file in the upper level at a time? Why?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

SST Ingestion. A common optimization of data migration / batch import in LSM trees is to ask the upstream to generate SST files of their data, and directly place these files in the LSM state without going through the write path.
SST Selection. Instead of selecting the oldest SST, you may think of other heuristics to choose the SST to compact.

Manifest

Chapter Overview

By the end of this chapter, you will be able to:

Encode and append structural changes to the manifest.
Order SST, directory, and manifest synchronization so recovery never references an SST that was not made durable.
Replay manifest records, open the live SSTs, and restore the next unused file ID.
Flush all memtables during a clean close when WALs are disabled.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 5
cargo x scheck

Before You Begin

Until this chapter, LsmStorageState is authoritative only while the process is running. The SST files survive a restart, but filenames alone do not say which files are live, which level or tier owns them, or which compaction replaced them.

Keep these invariants in mind:

The manifest is an ordered, append-only log of structural state changes. Replaying every record from an empty state must reconstruct the same live file layout.
An SST file and its directory entry must be durable before a manifest record is allowed to reference it.
A file made obsolete by a durable manifest record may be deleted afterward. Recovery must tolerate the old file still being present because it is no longer part of the logical state.
Manifest replay determines the live SST IDs before the engine opens SST metadata. Leveled SSTs are sorted by first key only after all live files have been opened.
next_sst_id must be greater than every ID observed in recovered SSTs and, after Day 6, memtables.

Predict before coding: The engine has written and synced a new SST but crashes before appending its flush record. What state should recovery produce, and what kind of file is left behind? Now reverse the unsafe order: the manifest is synced before the new SST’s directory entry. What can recovery attempt to open after a power loss?

Task 1: Manifest Encoding

The system uses a manifest to record structural operations in the engine. For now, there are two record types: compaction and SST flush. On restart, the engine reads the manifest, reconstructs the logical state, and opens the referenced SST files.

One simple design would rewrite the complete state as JSON after every flush or compaction. That approach becomes expensive when the database contains thousands of SSTs, so Mini-LSM uses an append-only manifest instead.

In this task, you will need to modify:

src/manifest.rs

Encode each record as JSON with serde_json::to_vec, append it, and synchronize the manifest. During recovery, serde_json::Deserializer::from_slice can stream adjacent JSON values without an explicit record length.

The manifest format is like:

| JSON record | JSON record | JSON record | JSON record |

At this stage, the format does not store each record’s byte length. Day 7 will add explicit framing and checksums.

Over time, the manifest can become large. A production engine can periodically replace it with a snapshot of the current state followed by a fresh log; this is a bonus task.

Task 2: Write Manifests

Now append manifest records whenever the LSM structure changes. You will need to modify:

src/lsm_storage.rs
src/compact.rs

For now, the manifest has two record types: SST flush and compaction. An SST flush record stores the ID written to disk. A compaction record stores the task and its output SST IDs. Whenever an operation creates files, first sync those files and the storage directory. Only then append the corresponding manifest record and sync the manifest. Delete obsolete input files after that record is durable, then sync the directory again. The manifest file should be written to <path>/MANIFEST.

Implement sync_dir with File::open(dir).sync_all()?. Synchronizing a file persists its contents; synchronizing the directory persists additions and removals of filenames.

Append a compaction record for both background compaction and a user-requested full compaction.

Task 3: Flush on Close

In this task, you will need to modify:

src/lsm_storage.rs

Implement close. When self.options.enable_wal is false, flush every non-empty memtable before stopping the engine so a clean shutdown preserves all writes.

Task 4: Recover from the State

In this task, you will need to modify:

src/lsm_storage.rs

Modify open to replay the manifest into an initially empty LSM state. Apply flush and compaction records to recover the live SST IDs, then open those files and populate the sstables map. Track the maximum ID, create a new memtable with the next ID, and advance next_sst_id again.

Leveled compaction normally sorts result IDs by first key. During manifest replay, however, the SST objects and their key ranges are not loaded yet. Honor apply_compaction_result’s in_recovery flag and defer sorting. Once every live SST is open, sort each leveled run by first key.

Alternatively, store each SST’s key range in the manifest, as systems such as RocksDB and BadgerDB do. Result application could then use the same ordering logic during recovery and normal execution.

You may use the mini-lsm-cli to test your implementation.

cargo run --bin mini-lsm-cli
fill 1000 2000
close
cargo run --bin mini-lsm-cli
get 1500

Chapter Checkpoint

After a clean close without WALs, the engine should have no non-empty memtables. Reopening it should replay the manifest, open exactly the referenced SSTs, restore leveled ordering after metadata becomes available, and allocate an ID greater than every recovered file ID.

Write down the durable events for one flush and one compaction. Insert a hypothetical crash after each event and determine whether recovery sees the old state or the new state. Both outcomes can be valid at some boundaries; a manifest state that references a missing file is not.

Test Your Understanding

Recovery and Durability

When do you need to call fsync? Why do you need to fsync the directory?
What are the places you will need to write to the manifest?
Why must newly created SSTs and their directory entries be synced before the manifest record that references them?
Why is it safe for an obsolete SST to remain on disk after the compaction record is durable? Is it safe to delete the SST before that point?
During recovery, why can leveled compaction results not be sorted by first key while manifest records are being replayed?
Construct a record sequence containing flushes and compactions, replay it by hand, and compute the next unused SST ID.

Alternative Designs

Consider an alternative implementation of an LSM engine that does not use a manifest file. Instead, it records the level/tier information in the header of each file, scans the storage directory every time it restarts, and recover the LSM state solely from the files present in the directory. Is it possible to correctly maintain the LSM state in this implementation and what might be the problems/challenges with that?
Currently, we create all SST/concat iterators before creating the merge iterator, which means that we have to load the first block of the first SST in all levels into memory before starting the scanning process. We have start/end key in the manifest, and is it possible to leverage this information to delay the loading of the data blocks and make the time to return the first key-value pair faster?
Is it possible not to store the tier/level information in the manifest? i.e., we only store the list of SSTs we have in the manifest without the level information, and rebuild the tier/level using the key range and timestamp information (SST metadata).

Bonus Tasks

Manifest Compaction. When the number of logs in the manifest file gets too large, you can rewrite the manifest file to only store the current snapshot and append new logs to that file.
Parallel Open. After you collect the list of SSTs to open, you can open and decode them in parallel, instead of doing it one by one, therefore accelerating the recovery process.

Write-Ahead Log (WAL)

Chapter Overview

By the end of this chapter, you will be able to:

Encode memtable updates in a write-ahead log and synchronize its buffered data.
Record memtable lifetimes in the manifest and recover them from WALs after a restart.
Restore newest-to-oldest memtable order and a collision-free next SST ID.
Explain the exact durability guarantee provided by sync and close.

To copy the test cases into the starter code and run them:

cargo x copy-test --week 2 --day 6
cargo x scheck

Before You Begin

The manifest makes the SST layout recoverable, but it cannot restore writes that were still in memory when the process crashed. A WAL persists the contents of each memtable until that memtable is safely represented by an SST.

Keep these invariants in mind:

Every WAL record belongs to exactly one memtable, and the WAL ID becomes the SST ID if that memtable is flushed.
The manifest records each new memtable so recovery knows which WAL files are live. A flush record retires the corresponding WAL logically before the file is removed physically.
Writes may remain in BufWriter and the operating-system page cache. They become durable only after flush() followed by sync_all().
Recovered immutable memtables are ordered newest to oldest, just like memtables created during normal execution.
next_sst_id is one greater than the maximum ID observed in either SST state or live WAL state.

Predict before coding: The manifest contains NewMemtable(7) but no Flush(7), and 00007.wal contains k -> v. What should recovery construct? If Flush(7) is durable but the old WAL file was not deleted before the crash, should recovery replay it?

Task 1: WAL Encoding

In this task, you will need to modify:

src/wal.rs

The previous chapter persisted the LSM structure and flushed every memtable during a clean close. A crash can bypass that close path. To recover unflushed data, log each memtable update to a write-ahead log. WALs are enabled only when self.options.enable_wal is true.

The WAL encoding is a list of key-value pairs.

| key_len | key | value_len | value |

Implement recover to replay the WAL into a memtable and reopen the file for appending.

The WAL uses a BufWriter to reduce the number of system calls on the write path. Updating a key does not by itself guarantee that the record has reached durable storage. The engine makes that guarantee when sync succeeds. Implement sync by first calling flush() to move bytes from BufWriter to the file and then calling get_mut().sync_all() to synchronize the file. You do not need to call sync_all() for every individual write.

Task 2: Integrate WALs

In this task, you will need to modify:

src/mem_table.rs
src/wal.rs
src/lsm_storage.rs

MemTable has an optional WAL. When it is present, append every update to that WAL. If enable_wal is true, create each memtable with create_with_wal and append ManifestRecord::NewMemtable before making the new WAL-backed memtable available for writes.

Store each WAL as <memtable_id>.wal in the database directory. If the memtable is later flushed, reuse that ID for its SST.

Task 3: Recover from the WALs

In this task, you will need to modify:

src/lsm_storage.rs

If WAL is enabled, recover live memtables from their WALs when opening the database. Also implement the database’s sync method. After sync returns successfully, writes completed before that synchronization point must be recoverable after restart. In this design, synchronizing the current memtable’s WAL provides that guarantee because frozen memtables are synchronized when they are replaced.

cargo run --bin mini-lsm-cli -- --enable-wal

Restore next_sst_id as max{memtable ID, SST ID} + 1. When WALs are enabled, close synchronizes them instead of flushing every memtable to an SST. Stop and join the compaction and flush threads before returning.

Chapter Checkpoint

With WALs enabled, synchronized writes should survive a restart even when their memtables were never flushed. Recovery should ignore stale WAL files retired by manifest flush records, rebuild live immutable memtables in newest-to-oldest order, create a fresh mutable memtable with a new WAL, and choose an unused ID.

Test more than a clean close: create several memtables, synchronize, reopen, and trace the manifest records that identify each live WAL. Explain which writes are guaranteed to survive if the process stops before sync, after sync, and after a flush record becomes durable but before its WAL file is removed.

Test Your Understanding

Recovery and Durability

When should you call fsync in your engine? What happens if you call fsync too often (i.e., on every put key request)?
How costly is the fsync operation in general on an SSD (solid state drive)?
When can you tell the user that their modifications (put/delete) have been persisted?
Why must a new memtable be recorded in the manifest before a synchronized write to its WAL can be considered recoverable?
Why should a flushed memtable’s WAL be deleted only after the manifest’s flush record is durable?
Given WAL IDs 4 and 9 plus live SST IDs 3, 7, and 12, what ID should the next memtable use?
How can you handle corrupted data in WAL?

Performance and Design

Is it possible to design an LSM engine without WAL (i.e., use L0 as WAL)? What will be the implications of this design?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Batch Write and Checksums

The previous chapter completed the persistent LSM engine. This final chapter adds a small API improvement and integrity checks for every on-disk format. Welcome to Week 2 snack time!

By the end of this chapter, you will be able to:

Implement the batch write interface.
Add checksums to data blocks, SST metadata, bloom filters, manifest records, and WAL records.
Define the exact byte range protected by each checksum and reject corrupted input.
Explain why framing information is necessary for checksummed variable-length records.

Note: The starter suite does not provide dedicated tests for this chapter. cargo x copy-test --week 2 therefore copies Days 1 through 6; requesting --day 7 reports that no dedicated test exists. Run every earlier test, inspect each encoded format, and add corruption cases that verify your checksum boundaries.

Before You Begin

This chapter changes every persistent format that the earlier chapters created. A checksum is useful only when the writer and reader agree on the exact bytes it covers and the reader can locate both those bytes and the stored checksum without trusting corrupted length fields blindly.

Keep these invariants in mind:

put and delete delegate to write_batch, so the existing single-record behavior remains unchanged. This Week 2 API processes a group of records but does not yet promise transactional atomicity.
A checksum is computed over the encoded bytes exactly as they appear on disk, including a consistent byte order for integer fields.
Each decoder isolates the same byte range that its encoder checksummed and verifies it before decoding or exposing the protected payload.
Offsets and lengths delimit variable-size sections. The checksum itself and unrelated preceding bytes are not accidentally included.
Corruption produces an error rather than silently returning data. Handling torn or truncated records without panicking is a separate robustness concern to consider.

Predict before coding: Bloom::encode appends a bloom filter to an SST buffer that already contains data blocks and metadata. If the checksum is computed over the entire buffer, what happens when Bloom::decode receives only the bloom-filter section? Which offset must the encoder remember?

Task 1: Write Batch Interface

Prepare for Week 3 by adding a write-batch API. You will need to modify:

src/lsm_storage.rs

The user passes write_batch a slice of WriteBatchRecord<T: AsRef<[u8]>>, so keys and values may use types such as Bytes, &[u8], or Vec<u8>. The two record variants are delete and put. Handle them with the same semantics as the existing delete and put methods.

Then refactor put and delete to call write_batch with one record.

All tests from earlier chapters should continue to pass.

Task 2: Block Checksum

Add a checksum after each encoded data block. You will need to modify:

src/table/builder.rs
src/table.rs

The format of the SST will be changed to:

---------------------------------------------------------------------------------------------------------------------------
|                   Block Section                     |                            Meta Section                           |
---------------------------------------------------------------------------------------------------------------------------
| data block | checksum | ... | data block | checksum | metadata | meta block offset | bloom filter | bloom filter offset |
|   varlen   |    u32   |     |   varlen   |    u32   |  varlen  |         u32       |    varlen    |        u32          |
---------------------------------------------------------------------------------------------------------------------------

Use CRC-32 through crc32fast::hash to checksum each encoded block.

Normally, the configured block size includes both content and checksum. A 4,096-byte target with a four-byte checksum would therefore leave 4,092 bytes for block content. To preserve the earlier tests, Mini-LSM continues to treat the configured size as the content target and appends the checksum afterward.

In read_block, separate the content from its checksum, verify the content, and decode it only after verification succeeds. Run every earlier test after changing the format.

Task 3: SST Meta Checksum

Add checksums for bloom filters and block metadata. You will need to modify:

src/table.rs
src/table/bloom.rs
src/table/builder.rs

----------------------------------------------------------------------------------------------------------
|                                                Meta Section                                            |
----------------------------------------------------------------------------------------------------------
| no. of block | metadata | checksum | meta block offset | bloom filter | checksum | bloom filter offset |
|     u32      |  varlen  |    u32   |        u32        |    varlen    |    u32   |        u32          |
----------------------------------------------------------------------------------------------------------

Append a checksum in Bloom::encode and verify it in Bloom::decode. Because encode appends to an existing buffer, record the bloom filter’s starting offset and checksum only the bytes added for that filter.

Then append a checksum to the block metadata. The existing block count can guide decoding; an explicit metadata length is another possible framing design.

Task 4: WAL Checksum

In this task, you will need to modify:

src/wal.rs

Protect each WAL record with its own checksum. You have two implementation choices:

Generate a buffer of the key-value record, and use crc32fast::hash to compute the checksum at once.
Write one field at a time (e.g., key length, key slice), and use a crc32fast::Hasher to compute the checksum incrementally on each field.

Choose whichever approach makes the protected byte range clearest. Both methods must produce the same checksum: incremental hashing must feed the exact encoded bytes in their on-disk byte order. The new WAL encoding is:

| key_len | key | value_len | value | checksum |

Task 5: Manifest Checksum

Finally, protect each manifest record. Unlike the WAL, the Day 5 manifest did not store record lengths. Add a length header before each JSON record and a checksum after it.

The new manifest format is like:

| len | JSON record | checksum | len | JSON record | checksum | len | JSON record | checksum |

After implementing every format change, run all previous tests and your own corruption cases.

Chapter Checkpoint

All earlier behavior should still pass after the format changes. In addition, every persistent section should round-trip successfully and fail verification when one protected byte is changed. Confirm that appending a bloom filter or metadata section to a non-empty buffer does not make its checksum depend on preceding sections.

Build a small SST and identify every offset, length, payload, and checksum by byte range. Do the same for one WAL and one manifest record. For each format, flip a payload byte and predict which decoder reports the error. Also consider a truncated length or checksum and decide whether your decoder returns an error or panics.

Test Your Understanding

Correctness and Corruption

Does write_batch in this chapter provide atomic visibility or durability for the whole batch? What additional synchronization would be needed to make that guarantee?
Why must an incremental WAL checksum hash the encoded byte order of each length rather than the integer’s native in-memory representation?
For every SST checksum, identify the first protected byte, the last protected byte, and the location of the stored checksum.
What happens if corruption changes a length or offset before the decoder has located the protected payload? How can a decoder validate bounds before slicing?
Is it okay to put all block checksums together at the end of the SST file instead of storing each checksum with its block? Why or why not?

API and Design

Consider the case that an LSM storage engine only provides write_batch as the write interface (instead of single put + delete). Is it possible to implement it as follows: there is a single write thread with an mpsc channel receiver to get the changes, and all threads send write batches to the write thread. The write thread is the single point to write to the database. What are the pros/cons of this implementation? (Congrats if you do so you get BadgerDB!)

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

Recovering from Corruption. If a checksum fails, open the database in a read-only safe mode that can retrieve unaffected data.

Week 3 Overview: Multi-Version Concurrency Control

In this part, you will implement multi-version concurrency control (MVCC) over the LSM engine from the previous two weeks. Internal keys will carry timestamps so that the engine can retain several versions of one user key. Reads will select a version from a stable timestamp, while compaction will reclaim versions only after no active reader needs them.

The general approach of the MVCC part in this course is inspired and partially based on BadgerDB.

The central representation is user_key + timestamp (u64). Versions sort by user key and then by timestamp in descending order, so the newest version of one user key appears first. User-facing APIs hide this representation and expose a snapshot through a transaction.

Before MVCC, source priority determined which duplicate key was newest. With MVCC, the timestamp makes version order explicit. Source priority still matters when two sources contain the same internal key, but compaction must not collapse distinct timestamps merely because they share a user key. This course also preserves the invariant that newer sources remain above older sources when compaction does not include both.

An MVCC engine can assign timestamps itself or accept timestamps from a caller. Using BadgerDB’s terminology, the mode that hides timestamps is unmanaged mode, while the mode that exposes timestamp control is managed mode.

Managed mode APIs

get(key, read_timestamp) -> (value, write_timestamp)
scan(key_range, read_timestamp) -> iterator<key, value, write_timestamp>
put(key, value, write_timestamp)
delete(key, write_timestamp)
write_batch(records, write_timestamp)
set_watermark(timestamp)

Unmanaged mode APIs

get(key) -> value
scan(key_range) -> iterator<key, value>
start_transaction() -> txn
txn.get/scan(key or range)
txn.put(key, value)
txn.delete(key)
txn.commit()

Managed mode requires the caller to provide timestamps. They might come from a centralized timestamp service or an upstream log such as PostgreSQL logical replication. The caller must also advance a watermark that tells the engine which historical versions are no longer needed.

In unmanaged mode, the engine chooses timestamps. A transaction records the latest committed timestamp when it begins. Later commits remain invisible to that transaction, so every read observes the same logical snapshot.

The first three chapters refactor internal formats and finish snapshot reads. The remaining chapters track active snapshots, add transactional writes and validation, and reclaim obsolete data.

Chapter	Before	After
Day 1: Timestamp Key Refactor	Internal keys contain only user bytes.	Blocks, SST metadata, iterators, and memtables preserve descending timestamp order.
Day 2: Memtables and Timestamps	Most data still uses timestamp 0.	Writes receive one commit timestamp per batch and all versions survive compaction.
Day 3: Transaction API	Reads return only the newest global state.	Transactions select the newest visible version at a fixed read timestamp, including after recovery.
Day 4: Watermark and Garbage Collection	Compaction retains every historical version.	Compaction retains exactly the versions active snapshots can still observe.
Day 5: Transactional Writes	Transaction writes are neither private nor crash-atomic.	A transaction reads its own workspace and commits one timestamped, framed WAL batch.
Day 6: Serializable Validation	Snapshot isolation permits write skew.	Commit-time validation rejects read/write conflicts for tracked keys.
Day 7: Compaction Filters	Garbage collection is based only on version age.	User-installed filters can reclaim a logical key prefix during compaction.

How to Use This Week

MVCC bugs often return a plausible value at the latest timestamp while breaking an older snapshot. For each chapter:

Write down the internal order for two user keys with several timestamps.
Trace one overwrite and one tombstone through a point read, a bounded scan, a flush, and a compaction.
Keep one old transaction alive while newer batches commit, then repeat the read after flushing and compacting.
For persistence changes, identify the durable source of the recovered commit timestamp and distinguish timestamp visibility from crash atomicity.
For serializable validation, draw the dependency that should make a transaction abort and state which read or write set records it.

Before finishing Week 3, check that you can explain:

why timestamps sort in descending order within one user key;
how included and excluded user-key bounds map to internal timestamp bounds;
which version a read at timestamp T returns when newer versions and tombstones exist;
why the watermark preserves one version at or below its value;
why a shared commit timestamp provides atomic visibility while a framed, checksummed WAL batch provides crash atomicity;
what anomaly commit-time validation prevents and which scan phantoms it does not prevent; and
why a compaction filter cannot blindly remove versions newer than the watermark.

Timestamp Key Encoding + Refactor

By the end of this chapter, you will be able to:

Encode a (user_key, timestamp) internal key in blocks and SST metadata.
Preserve the order user_key ascending, timestamp descending through every storage iterator.
Explain why Bloom filters hash only the user-key portion and why key-range checks ignore timestamps.

To copy and run the test cases:

cargo x copy-test --week 3 --day 1
cargo x scheck

Note: The MVCC subsystem is not complete until Day 2. At the end of this chapter, only the Day 1 tests and Week 1 tests are expected to pass. Week 2 compaction still uses pre-MVCC assumptions.

Before You Begin

This chapter changes representation, not visibility. Every existing layer that stores, compares, seeks, or summarizes keys must agree on the same internal ordering.

Keep these invariants in mind:

Internal keys sort by user key in ascending order and timestamp in descending order.
Prefix compression applies only to user-key bytes. The timestamp is encoded in full for every entry.
Block metadata stores complete first and last internal keys, including their timestamps.
Bloom filters hash user-key bytes only, because a lookup asks whether any version of that user key may exist.
Day 1 still writes TS_DEFAULT; seeing multiple versions through LsmIterator is temporarily acceptable until Day 2.

Predict before coding: In what order should a@7, a@3, aa@9, and b@1 appear? If a block entry shares all user-key bytes with the previous entry, which fields are still encoded for that entry?

Task 0: Use MVCC Key Encoding

You will need to replace the key encoding module to the MVCC one. We have removed some interfaces from the original key module and implemented new comparators for the keys. If you followed the instructions in the previous chapters and did not use into_inner on the key, you should pass all test cases on day 3 after all the refactors. Otherwise, you will need to look carefully on the places where you only compare the keys without looking at the timestamps.

Specifically, the key type definition has been changed from:

#![allow(unused)]
fn main() {
pub struct Key<T: AsRef<[u8]>>(T);
}

…to:

#![allow(unused)]
fn main() {
pub struct Key<T: AsRef<[u8]>>(T /* user key */, u64 /* timestamp */);
}

…where we have a timestamp associated with the keys. We only use this key representation internally in the system. On the user interface side, we do not ask users to provide a timestamp, and therefore some structures still use &[u8] instead of KeySlice in the engine. We will cover the places where we need to change the signature of the functions later. For now, you only need to run,

cp mini-lsm-mvcc/src/key.rs mini-lsm-starter/src/

There are other ways of storing the timestamp. For example, we can still use the pub struct Key<T: AsRef<[u8]>>(T); representation, but assume the last 8 bytes of the key is the timestamp. You can also implement this as part of the bonus tasks.

Alternative key representation: | user_key (varlen) | ts (8 bytes) | in a single slice
Our key representation: | user_key slice | ts (u64) |

In the key+timestamp ordering, the smallest user key appears first, and the largest timestamp for one user key appears first. For example:

("a", 233) < ("a", 0) < ("b", 233) < ("b", 0)

Task 1: Encode Timestamps in Blocks

Replacing the key module makes representation assumptions visible as compiler errors. In this task, update:

src/block/builder.rs
src/block/iterator.rs

raw_ref() and len() are removed from the key API. Use key_ref() for user-key bytes and key_len() for their length. Update the block builder and decoder to encode the timestamp explicitly. The new block entry is:

key_overlap_len (u16) | remaining_key_len (u16) | key (remaining_key_len) | timestamp (u64)

Use raw_len() to estimate the space required by the complete internal key, and store the timestamp after the remaining user-key bytes.

After you change the block encoding, update the block iterator to decode and reconstruct timestamped keys accordingly.

Task 2: Encoding Timestamps in SSTs

Then, you can go ahead and modify the table format,

src/table.rs
src/table/builder.rs

Change block metadata encoding to include the timestamps of its first and last keys. Because seek and add accept KeySlice, the key comparator then carries the same ordering into SST construction and lookup.

Use key_ref() to build the Bloom filter. All timestamped versions of one user key then share one fingerprint.

Task 3: LSM Iterators

As we use associated generic type to make most of our iterators work for different key types (i.e., &[u8] and KeySlice<'_>), we do not need to modify merge iterators and concat iterators if they are implemented correctly. The LsmIterator is the place where we strip the timestamp from the internal key representation and return the latest version of a key to the user. In this task, you will need to modify:

src/lsm_iterator.rs

For now, we do not modify the logic of LsmIterator to only keep the latest version of a key. We simply make it compile by appending a timestamp to the user key when passing the key to the inner iterator, and stripping the timestamp from a key when returning to the user. The behavior of your LSM iterator for now should be returning multiple versions of the same key to the user.

Task 4: Memtable

For now, we keep the logic of the memtable. We return a key slice to the user and flush SSTs with TS_DEFAULT. We will change the memtable to be MVCC in the next chapter. In this task, you will need to modify:

src/mem_table.rs

Task 5: Engine Read Path

In this task, you will need to modify,

src/lsm_storage.rs

Now that we have a timestamp in the key, and when creating the iterators, we will need to seek a key with a timestamp instead of only the user key. You can create a key slice with TS_RANGE_BEGIN, which is the largest ts.

When you check if a user key is in a table, you can simply compare the user key without comparing the timestamp.

At this point, all stored keys still use TS_DEFAULT (timestamp 0). The next two chapters assign real commit timestamps and select versions by read timestamp.

Chapter Checkpoint

Your engine should encode and decode timestamped keys without changing Day 1 visibility semantics.

Verify these cases explicitly:

Round-trip two entries with the same user key and different timestamps through a block and an SST.
Seek to a timestamp between two versions and confirm that descending timestamp order positions the iterator correctly.
Confirm that two versions of one user key add the same Bloom-filter fingerprint.

Test Your Understanding

Why is timestamp order reversed while user-key order is not?
Which encoded structures would become inconsistent if block metadata omitted timestamps?
Why should a point lookup for k test one user-key fingerprint rather than a separate fingerprint for every possible k@ts?
During Day 1, why is it acceptable for LsmIterator to return repeated user keys, and why must that behavior change on Day 2?
Construct a seek target that distinguishes comparing full internal keys from comparing only user keys.

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Snapshot Read - Memtables and Timestamps

By the end of this chapter, you will be able to:

Refactor your memtable/WAL to store multiple versions of a key.
Assign one unique commit timestamp to every write batch.
Preserve every version through compaction while keeping all versions of one user key in one SST.
Return the newest committed version of each user key from the latest snapshot.

During the refactor, you might need to change the signature of some functions from &self to self: &Arc<Self> as necessary.

To copy and run the test cases:

cargo x copy-test --week 3 --day 2
cargo x scheck

The supplied Day 2 test covers timestamped batches, raw version order, and latest-state reads. The compaction boundary case is exercised by the Day 4 suite, once transactions can pin a watermark and keep old versions live in the completed engine.

Note: You should also pass every checkpoint through Week 2 Day 4 after finishing this chapter.

Before You Begin

Day 1 changed the internal representation but still wrote timestamp 0. This chapter turns timestamps into a commit order. Reads still use the latest timestamp; historical snapshots arrive on Day 3.

Keep these invariants in mind:

Every record in one write batch receives the same timestamp, and different committed batches receive different timestamps.
The write lock covers timestamp allocation, the memtable/WAL update, and publication of the new latest commit timestamp.
A scan over a user-key range must include every internal version that could determine the visible value. Included and excluded user-key bounds therefore map to different timestamp sentinels.
Compaction retains all versions in this chapter. It may split output between user keys, but never between two versions of the same user key.
The WAL checksum covers key length, user-key bytes, timestamp, value length, and value bytes in their encoded byte order.

Predict before coding: A batch writes a and b at timestamp 7, while the memtable already contains a@6. What is their internal order? For the user range (a, b], which timestamp sentinels exclude every version of a while including every version of b?

Task 1: MemTable, Write-Ahead Log, and Read Path

In this task, you will need to modify:

src/wal.rs
src/mem_table.rs
src/lsm_storage.rs

We have already made most of the keys in the engine to be a KeySlice, which contains a bytes key and a timestamp. However, some part of our system still did not consider the timestamps. In our first task, you will need to modify your memtable and WAL implementation to take timestamps into account.

You will need to first change the type of the SkipMap stored in your memtable.

#![allow(unused)]
fn main() {
pub struct MemTable {
    // map: Arc<SkipMap<Bytes, Bytes>>,
    map: Arc<SkipMap<KeyBytes, Bytes>>, // Bytes -> KeyBytes
    // ...
}
}

After that, you can continue to fix all compiler errors so as to complete this task.

MemTable::get

We keep the get interface so that the test cases can still probe a specific version of a key in the memtable. This interface should not be used in your read path after finishing this task. Given that we store KeyBytes, which is (Bytes, u64) in the skiplist, while the user probe the KeySlice, which is (&[u8], u64). We have to find a way to convert the latter to a reference of the former, so that we can retrieve the data in the skiplist.

To do this, you may temporarily cast the &[u8] to a 'static slice and use Bytes::from_static to construct a lookup key without copying. This is sound only because the Bytes value is used for the synchronous lookup and cannot escape the original slice’s lifetime. Storing or returning that value would make the cast unsound.

Spoilers: Convert u8 slice to Bytes

#![allow(unused)]
fn main() {
Bytes::from_static(unsafe { std::mem::transmute(key.key_ref()) })
}

The pre-MVCC map did not need this conversion because Bytes implements Borrow<[u8]>.

MemTable::put

The signature should be changed to fn put(&self, key: KeySlice, value: &[u8]) and You will need to convert a key slice to a KeyBytes in your implementation.

MemTable::scan

The signature should be changed to fn scan(&self, lower: Bound<KeySlice>, upper: Bound<KeySlice>) -> MemTableIterator. You will need to convert KeySlice to KeyBytes and use these as SkipMap::range parameters.

MemTable::flush

Instead of using the default timestamp, you should now use the key timestamp when flushing the memtable to the SST.

MemTableIterator

It should now store (KeyBytes, Bytes) and the return key type should be KeySlice.

Wal::recover and Wal::put

The write-ahead log should now accept a key slice instead of only user-key bytes. When serializing and deserializing a WAL record, include the timestamp and checksum the exact encoded bytes for every field.

The WAL format is as follows:

| key_len (exclude ts len) (u16) | key | ts (u64) | value_len (u16) | value | checksum (u32) |

LsmStorageInner::get

Previously, get could probe sources one at a time. Now a version’s timestamp, not only its source, determines visibility. The simplest correct implementation creates the same merged stream as scan over memtables, immutable memtables, L0 SSTs, and lower levels, while using Bloom filters to avoid impossible SST probes.

LsmStorageInner::scan

Incorporate the new memtable APIs and map user-key bounds to internal-key bounds. An included lower bound starts at TS_RANGE_BEGIN; an excluded lower bound must skip every timestamp of that user key. An included upper bound ends at TS_RANGE_END; an excluded upper bound stops before TS_RANGE_BEGIN for that user key.

Task 2: Write Path

In this task, you will need to modify:

src/lsm_storage.rs

We have an mvcc field in LsmStorageInner that includes all data structures we need to use for multi-version concurrency control in this week. When you open a directory and initialize the storage engine, you will need to create that structure.

In write_batch, allocate latest_commit_ts() + 1 and use it for every record. Hold self.mvcc().write_lock.lock() across allocation, insertion, and publication so that concurrent batches cannot reuse a timestamp. After every record has been accepted by the memtable/WAL, publish the new latest commit timestamp.

Task 3: MVCC Compaction

In this task, you will need to modify:

src/compact.rs

Previous compaction retained only the newest value and could remove a bottom-level tombstone. With MVCC, older versions may still serve a snapshot, so those rules are not yet safe.

In this chapter, you may simply remove the logic to remove the keys. You may ignore compact_to_bottom_level for now, and you should keep ALL versions of a key during the compaction.

Also, you will need to implement the compaction algorithm in a way that the same key with different timestamps are put in the same SST file, even if it exceeds the SST size limit. This ensures that if a key is found in an SST in a level, it will not be in other SST files in that level, and therefore simplifying the implementation of many parts of the system.

Task 4: LSM Iterator

In this task, you will need to modify:

src/lsm_iterator.rs

In the previous chapter, we implemented the LSM iterator to act as viewing the same key with different timestamps as different keys. Now, we will need to refactor the LSM iterator to only return the latest version of a key if multiple versions of the keys are retrieved from the child iterator.

You will need to record prev_key in the iterator. If we already returned the latest version of a key to the user, we can skip all old versions and proceed to the next key.

At this point, you should pass all previous tests except the persistence tests from Week 2 Days 5 and 6.

Chapter Checkpoint

Each write batch should now create one ordered group of versions, and latest-state reads should collapse that history back to one value per user key.

Verify these cases explicitly:

Write the same key in three batches and confirm that a raw internal iterator sees all three timestamps in descending order while get returns only the newest value.
Scan each combination of included and excluded bounds around a key that has several versions.
Force an SST-size boundary in the middle of a key’s history and confirm that every version remains in one output SST.
Round-trip a WAL record and confirm its checksum covers the encoded timestamp as well as the key and value.

Test Your Understanding

What is the difference of get in the MVCC engine and the engine you built in week 2?
In week 2, you stop at the first memtable/level where a key is found when get. Can you do the same in the MVCC version?
How do you convert KeySlice into a temporary KeyBytes lookup key? Which lifetime condition makes the unsafe conversion sound?
Why must the write lock cover both timestamp selection and batch insertion?
Why does an excluded lower bound use the opposite timestamp sentinel from an included lower bound?
What observable failure occurs if compaction splits two versions of one user key across SSTs in the same level?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

Early Stop for Memtable Gets. Instead of creating a merge iterator over all memtables and SSTs, we can implement get as follows: If we find a version of a key in the memtable, we can stop searching. The same applies to SSTs.

Snapshot Read - Engine Read Path and Transaction API

By the end of this chapter, you will be able to:

Select the newest version whose timestamp is less than or equal to a transaction’s read timestamp.
Keep a snapshot alive for the lifetime of a point read or scan iterator.
Recover the latest commit timestamp from durable SST and WAL state.

At the end of the day, your engine will be able to give the user a consistent view of the storage key space.

During the refactor, you might need to change the signature of some functions from &self to self: &Arc<Self> as necessary.

To copy and run the test cases:

cargo x copy-test --week 3 --day 3
cargo x scheck

Note: You should also pass the persistence tests from Week 2 Days 5 and 6 after finishing this chapter.

Before You Begin

Day 2 stores a complete version history but always reads at the latest timestamp. A transaction now captures read_ts = latest_commit_ts when it begins and reuses that value for every read.

Keep these invariants in mind:

For each user key, skip versions with ts > read_ts, then choose the first remaining version.
If the chosen version is a tombstone, the user key is absent; older values must not be returned.
After deciding one user key, skip every remaining version of that key before returning the next result.
A TxnIterator holds the transaction alive so its read timestamp remains protected for the entire scan.
Recovery initializes the timestamp oracle to at least the largest timestamp in every live SST and recovered WAL-backed memtable.

Predict before coding: For a@7=del, a@5=v5, a@2=v2, what should reads at timestamps 8, 6, 5, and 1 return? Which iterator transitions are needed to avoid resurrecting a@5 at timestamp 8?

Task 1: LSM Iterator with Read Timestamp

The goal of this chapter is to have something like:

#![allow(unused)]
fn main() {
let snapshot1 = engine.new_txn();
// write something to the engine
let snapshot2 = engine.new_txn();
// write something to the engine
snapshot1.get(/* ... */); // we can retrieve a consistent snapshot of a previous state of the engine
}

Record the latest committed timestamp when creating the transaction. A read over that transaction may inspect newer internal versions, but it must return only versions at or below the recorded timestamp.

In this task, you will need to modify:

src/lsm_iterator.rs

To do this, you will need to record a read timestamp in LsmIterator.

#![allow(unused)]
fn main() {
impl LsmIterator {
    pub(crate) fn new(
        iter: LsmIteratorInner,
        end_bound: Bound<Bytes>,
        read_ts: u64,
    ) -> Result<Self> {
        // ...
    }
}
}

Update LsmIterator initialization and next logic to skip future versions, suppress tombstones, and return at most one result per user key.

Task 2: Multi-Version Scan and Get

In this task, you will need to modify:

src/mvcc.rs
src/mvcc/txn.rs
src/lsm_storage.rs

Now implement scan and get on Transaction so every operation uses the same read_ts.

We recommend you to create helper functions like scan_with_ts(/* original parameters */, read_ts: u64) and get_with_ts if necessary in your LsmStorageInner structure. The original get/scan on the storage engine should be implemented as creating a transaction (snapshot) and do a get/scan over that transaction. The call path would be like:

LsmStorageInner::scan -> new_txn and Transaction::scan -> LsmStorageInner::scan_with_ts

To create a transaction in LsmStorageInner::scan, we will need to provide a Arc<LsmStorageInner> to the transaction constructor. Therefore, we can change the signature of scan to take self: &Arc<Self> instead of simply &self, so that we can create a transaction with let txn = self.mvcc().new_txn(self.clone(), /* ... */).

Change scan to return a TxnIterator. The snapshot must remain live while the user consumes the scan, so TxnIterator stores the transaction object. Inside it, store a FusedIterator<LsmIterator> for now; Day 5 will add the transaction-local stream.

You do not need to implement Transaction::put/delete for now, and all modifications will still go through the engine.

Task 3: Store Largest Timestamp in SST

In this task, you will need to modify:

src/table.rs
src/table/builder.rs

Store the largest timestamp after the block metadata and recover it when opening the SST. This summary lets startup advance the timestamp oracle without scanning every entry.

Task 4: Recover Commit Timestamp

Now that we have largest timestamp information in the SSTs and timestamp information in the WAL, we can obtain the largest timestamp committed before the engine starts, and use that timestamp as the latest committed timestamp when creating the mvcc object.

If WAL is not enabled, you can simply compute the latest committed timestamp by finding the largest timestamp among SSTs. If WAL is enabled, you should further iterate all recovered memtables and find the largest timestamp.

In this task, you will need to modify:

src/lsm_storage.rs

Test this path explicitly by closing and reopening a database whose largest timestamp appears first in an SST and then in an unflushed WAL-backed memtable. The first post-recovery write must receive a strictly larger timestamp.

Chapter Checkpoint

Transactions should now retain a stable logical snapshot across later writes, flushes, compactions, and restart.

Verify these cases explicitly:

Keep three transactions at different timestamps and compare both get and scan after overwrites and deletes.
Flush and compact while the transactions remain alive, then repeat the same reads.
Start a scan, commit a newer value, and continue the scan; the iterator must stay on its original read timestamp.
Reopen with the maximum timestamp present in an SST and then in a WAL, and confirm that neither timestamp is reused.

Test Your Understanding

So far, we have assumed that our SST files use a monotonically increasing id as the file name. Is it okay to use <level>_<begin_key>_<end_key>_<max_ts>.sst as the SST file name? What might be the potential problems with that?
Consider an alternative implementation of transaction/snapshot. In our implementation, we have read_ts in our iterators and transaction context, so that the user can always access a consistent view of one version of the database based on the timestamp. Is it viable to store the current LSM state directly in the transaction context in order to gain a consistent snapshot? (i.e., all SST ids, their level information, and all memtables + ts) What are the pros/cons with that? What if the engine does not have memtables? What if the engine is running on a distributed storage system like S3 object store?
Consider that you are implementing a backup utility of the MVCC Mini-LSM engine. Is it enough to simply copy all SST files out without backing up the LSM state? Why or why not?
Why does a tombstone selected at read_ts stop the search instead of allowing an older value to become visible?
Which object owns the lifetime of a scan’s read timestamp, and what could compaction reclaim if that object were dropped too early?
Is the maximum timestamp among current SST entries always a durable history of every timestamp ever allocated? What additional metadata would be needed if timestamps must never be reused after all records at the maximum timestamp are garbage-collected?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Watermark and Garbage Collection

By the end of this chapter, you will be able to:

Track the oldest read timestamp still held by a live transaction or iterator.
Reclaim obsolete versions without changing any snapshot at or above the watermark.
Explain when a bottom-level tombstone and every older value can be removed together.

To copy and run the test cases:

cargo x copy-test --week 3 --day 4
cargo x scheck

The Day 4 suite also rechecks Day 2’s rule that compaction must not split versions of one user key across output SSTs. The live transaction in that test pins the watermark so the completed engine cannot garbage-collect the history being measured.

Before You Begin

Retaining every version is correct but unbounded. The watermark is the smallest read timestamp still in use. Compaction may remove history that no transaction at or above that timestamp can distinguish.

Keep these invariants in mind:

The tracker counts readers, not only distinct timestamps; dropping one of two readers at the same timestamp must not advance the watermark.
Creating a transaction registers its timestamp before it can race with compaction.
A scan iterator keeps its transaction alive, so abandoning the original transaction handle does not release the watermark early.
Compaction keeps every version above the watermark and the newest version at or below it.
A tombstone at or below the watermark can be removed only when the compaction reaches the bottom level, where no older value can survive outside the task.

Predict before coding: Readers exist at timestamps 3, 3, and 7. Which drops advance the watermark? For k@8=v8, k@5=del, k@2=v2 with watermark 5, which versions survive a non-bottom compaction and a bottom-level compaction?

Task 1: Implement Watermark

In this task, you will need to modify:

src/mvcc/watermark.rs

Watermark tracks the lowest read_ts in the system. A new transaction calls add_reader; the final owner of that transaction calls remove_reader when dropped. watermark() returns the lowest active timestamp, or None when no snapshot is live.

A BTreeMap can map each read_ts to its reader count. Remove entries when their count reaches zero.

Task 2: Maintain Watermark in Transactions

In this task, you will need to modify:

src/mvcc/txn.rs
src/mvcc.rs

Register read_ts when a transaction starts and remove it in Drop. Because iterators own an Arc<Transaction>, the reader remains registered until every handle and iterator is gone.

Task 3: Garbage Collection in Compaction

In this task, you will need to modify:

src/compact.rs

Now that we have a watermark for the system, we can clean up unused versions during the compaction process.

If a version of a key is above watermark, keep it.
For all versions of a key below or equal to the watermark, keep the latest version.

For example, if we have watermark=3 and the following data:

a@4=del <- above watermark
a@3=3   <- latest version below or equal to watermark
a@2=2   <- can be removed, no one will read it
a@1=1   <- can be removed, no one will read it
b@1=1   <- latest version below or equal to watermark
c@4=4   <- above watermark
d@3=del <- can be removed if compacting to bottom-most level
d@2=2   <- can be removed

If we do a compaction over these keys, we will get:

a@4=del
a@3=3
b@1=1
c@4=4
d@3=del (can be removed if compacting to bottom-most level)

Assume these are all keys in the engine. A scan at timestamp 3 returns a=3,b=1; c@4 is still in the future. A scan at timestamp 4 returns b=1,c=4 because a@4 is a tombstone. Both results must be identical before and after compaction. Compaction must not affect transactions whose read timestamp is at or above the watermark.

Chapter Checkpoint

Compaction should now reduce history as the oldest snapshot advances, while every still-live snapshot returns the same values.

Verify these cases explicitly:

Hold two transactions at the same oldest timestamp and confirm that dropping only one does not advance the watermark.
Compact the example above at each successive watermark and compare both raw internal versions and user-visible reads.
Keep only a scan iterator alive, compact, and confirm that the iterator’s snapshot is still protected.
Compare a tombstone compacted into a middle level with the same tombstone compacted into the bottom level.

Test Your Understanding

In our implementation, we manage watermarks by ourselves with the lifecycle of Transaction (so-called un-managed mode). If the user intends to manage key timestamps and the watermarks by themselves (i.e., when they have their own timestamp generator), what do you need to do in the write_batch/get/scan API to validate their requests? Is there any architectural assumption we had that might be hard to maintain in this case?
Why do we need to store an Arc of Transaction inside a transaction iterator?
What is the condition to fully remove a key from the SST file?
For now, we only remove a key when compacting to the bottom-most level. Is there any other prior time that we can remove the key? (Hint: you know the start/end key of each SST in all levels.)
Consider the case that the user creates a long-running transaction and we could not garbage collect anything. The user keeps updating a single key. Eventually, there could be a key with thousands of versions in a single SST file. How would it affect performance, and how would you deal with it?
Why must compaction keep one version at or below the watermark instead of deleting every version below it?
What race appears if a transaction reads the latest timestamp before registering itself with the watermark?

Bonus Tasks

O(1) Watermark. You may implement an amortized O(1) watermark structure by using a hash map or a cyclic queue.

Transaction and Optimistic Concurrency Control

By the end of this chapter, you will be able to:

Maintain a private transaction workspace with read-your-writes semantics.
Merge local updates and tombstones with the transaction’s stable engine snapshot.
Publish every update in a transaction with one commit timestamp and one crash-atomic WAL record.

To copy and run the test cases:

cargo x copy-test --week 3 --day 5
cargo x scheck

This chapter prepares for optimistic concurrency control; serializable conflict validation is added on Day 6.

Before You Begin

A transaction now has two sources: its private workspace and the engine snapshot at read_ts. The local source is newer and must win on duplicate user keys.

Keep these invariants in mind:

get and scan provide read-your-writes, including local deletions.
Local entries shadow the engine snapshot but remain invisible to every other transaction until commit.
Commit marks the transaction unusable before publishing any writes.
Every record collected by one commit receives the same commit timestamp and remains in one memtable and WAL, even if the batch exceeds the size target.
Recovery validates the complete WAL batch before applying any record, so a truncated transaction exposes no prefix.
The WAL batch is appended before its entries become visible in the memtable. The latest commit timestamp is published after the batch is accepted and before fallible freeze maintenance.

Predict before coding: The snapshot contains a=old,b=old; the local workspace contains a=new,b=del,c=new. What should an unbounded scan return? If the process stops after writing only part of the transaction’s WAL record, how many of those updates may recovery expose?

Task 1: Local Workspace + Put and Delete

In this task, you will need to modify:

src/mvcc/txn.rs

You can now implement put and delete by inserting the corresponding key/value to the local_storage, which is a skiplist memtable without key timestamp. Note that for deletes, you will still need to implement it as inserting an empty value, instead of removing a value from the skiplist.

Task 2: Get and Scan

In this task, you will need to modify:

src/mvcc/txn.rs

For get, probe local storage first and interpret an empty value as a deletion. For scan, implement TxnLocalIterator over the timestamp-free skiplist and merge it ahead of FusedIterator<LsmIterator>. Because the merge iterator retains tombstones, TxnIterator must suppress them without exposing the older engine value they shadow.

Task 3: Commit

In this task, you will need to modify:

src/mvcc/txn.rs

We assume that a transaction is used from one thread. As it enters commit, atomically mark it committed so later put, delete, scan, get, or repeated commit calls fail.

Your commit implementation should simply collect all key-value pairs from the local storage and submit a write batch to the storage engine.

Task 4: Atomic WAL

In this task, you will need to modify:

src/wal.rs
src/mem_table.rs
src/lsm_storage.rs

One timestamp makes a completed transaction appear at once to new readers, but it does not make the transaction durable as a unit. Encode the entire transaction as one framed WAL record:

|   HEADER   |                          BODY                                      |  FOOTER  |
|     u32    |   u16   | var | u64 |    u16    |  var  |           ...            |    u32   |
| batch_size | key_len | key | ts  | value_len | value | more key-value pairs ... | checksum |

batch_size is the byte length of the body, and checksum covers the complete body. Reject keys, values, or batches that do not fit their encoded length fields rather than truncating their lengths.

Implement Wal::put_batch and make Wal::put call it with a one-record batch. Recovery must validate the header, every field boundary, and the footer before applying any record. A truncated or corrupt batch returns an error and exposes none of its prefix.

Implement MemTable::put_batch and make MemTable::put use it. Append the complete WAL record before inserting entries into the skiplist; otherwise an I/O error can make an update visible in memory without a durable commit.

Submit the transaction to one memtable and one WAL before checking whether to freeze. A batch larger than the configured memtable target is allowed to exceed the target; it must not be split across WALs. Once the batch is accepted, publish its commit timestamp before fallible freeze maintenance so the timestamp cannot be reused after a maintenance error.

Chapter Checkpoint

Transaction-local reads should now behave like one overlay, and a successful commit should publish one indivisible logical and durable batch.

Verify these cases explicitly:

Overwrite and delete keys from the snapshot, then compare local get with included, excluded, and unbounded scans.
Confirm that another transaction cannot observe the workspace before commit and that an older transaction cannot observe it afterward.
Inspect all internal records created by one commit and confirm that they have the same timestamp.
Confirm that get, scan, put, delete, and a second commit reject use after the transaction has committed.
Commit a batch larger than the memtable target and confirm that it stays in one memtable and WAL.
Truncate the WAL batch in its header, body, and checksum; every recovery attempt must fail without exposing a prefix.

Test Your Understanding

With all the things we have implemented up to this point, does the system satisfy snapshot isolation? If not, what else do we need to do to support snapshot isolation? (Note: snapshot isolation is different from serializable snapshot isolation we will talk about in the next chapter)
What if the user wants to batch import data (i.e., 1TB?) If they use the transaction API to do that, will you give them some advice? Is there any opportunity to optimize for this case?
What is optimistic concurrency control? What would the system be like if we implement pessimistic concurrency control instead in Mini-LSM?
Why are both a shared commit timestamp and WAL framing required for transaction atomicity?
Why must WAL append happen before memtable publication? What should the caller observe if either step fails?
When can the engine safely check the memtable size and freeze it without splitting the transaction?
Should an empty transaction allocate a commit timestamp? What are the tradeoffs? This checkpoint follows the existing batch-write behavior.

Bonus Tasks

Spill to Disk. If the private workspace of a transaction gets too large, you may flush some of the data to the disk.

(A Partial) Serializable Snapshot Isolation

By the end of this chapter, you will be able to:

Detect a tracked read/write dependency against transactions committed after a snapshot began.
Serialize validation and publication under one commit lock.
Explain why key-only scan tracking does not prevent phantom anomalies.

To copy and run the test cases:

cargo x copy-test --week 3 --day 6
cargo x scheck

Before You Begin

Day 5 provides stable snapshots and crash-atomic writes, but two transactions can still make decisions from the same old state and produce write skew. Day 6 validates a transaction immediately before commit.

Keep these invariants in mind:

Validation and write publication happen under commit_lock, so no transaction can commit between the check and the write.
For a transaction at read_ts, compare its read set with the write sets committed after read_ts and before its own publication.
Record a point-read key even when get returns None; the absence influenced the transaction.
A failed validation publishes no data and no committed write-set record.
Transactions with an empty write set skip conflict validation; optimizing their timestamp and metadata path is a bonus task.
Recording only keys returned by a scan does not record gaps, so inserts into those gaps can create phantoms.

Predict before coding: Two transactions begin at timestamp 10. T1 reads b and writes a; T2 reads a and writes b. T1 commits at 11. Which set intersection must abort T2? How would the answer change if T2’s dependency came only from an empty range scan?

Let us go through an example of serializable. Consider that we have two transactions in the engine that:

txn1: put("key1", get("key2"))
txn2: put("key2", get("key1"))

The initial state of the database is key1=1, key2=2. Serializable means that the outcome of the execution has the same result of executing the transactions one by one in serial in some order. If we execute txn1 then txn2, we will get key1=2, key2=2. If we execute txn2 then txn1, we will get key1=1, key2=1.

However, with our current implementation, if the execution of these two transactions overlaps:

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit
txn2: put key2=1, commit

We will get key1=2, key2=1. This cannot be produced with a serial execution of these two transactions. This phenomenon is called write skew.

With serializable validation, we can ensure the modifications to the database corresponds to a serial execution order, and therefore, users may run some critical workloads over the system that requires serializable execution. For example, if a user runs bank transfer workloads on Mini-LSM, they would expect the sum of money at any point of time is the same. We cannot guarantee this invariant without serializable checks.

One technique of serializable validation is to record read set and write set of each transaction in the system. We do the validation before committing a transaction (optimistic concurrency control). If the read set of the transaction overlaps with any transaction committed after its read timestamp, then we fail the validation, and abort the transaction.

Back to the above example, if we have txn1 and txn2 both started at timestamp = 1.

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit ts = 2
txn2: put key2=1, start serializable verification

When we validate txn2, we will go through all transactions started before the expected commit timestamp of itself and after its read timestamp (in this case, 1 < ts < 3). The only transaction satisfying the criteria is txn1. The write set of txn1 is key1, and the read set of txn2 is key1. As they overlap, we should abort txn2.

Task 1: Track Read Set in Get and Write Set

In this task, you will need to modify:

src/mvcc/txn.rs
src/mvcc.rs

When get is called, you should add the key to the read set of the transaction. In our implementation, we store the hashes of the keys, so as to reduce memory usage and make probing the read set faster, though this might cause false positives when two keys have the same hash. You can use farmhash::hash32 to generate the hash for a key. Note that even if get returns a key is not found, this key should still be tracked in the read set.

In LsmMvccInner::new_txn, you should create an empty read/write set for the transaction if serializable=true.

Task 2: Track Read Set in Scan

In this task, you will need to modify:

src/mvcc/txn.rs

In this course, we only guarantee full serializability for get requests. You still need to track the read set for scans, but in some specific cases, you might still get non-serializable result.

To understand why this is hard, let us go through the following example.

txn1: put("key1", len(scan(..)))
txn2: put("key2", len(scan(..)))

If the database starts with an initial state of a=1,b=2, we should get either a=1,b=2,key1=2,key2=3 or a=1,b=2,key1=3,key2=2. However, if the transaction execution is as follows:

txn1: len(scan(..)) = 2
txn2: len(scan(..)) = 2
txn1: put key1 = 2, commit, read set = {a, b}, write set = {key1}
txn2: put key2 = 2, commit, read set = {a, b}, write set = {key2}

This passes our serializable validation and does not correspond to any serial order of execution! Therefore, a fully-working serializable validation will need to track key ranges, and using key hashes can accelerate the serializable check if only get is called. Please refer to the bonus tasks on how you can implement serializable checks correctly.

Task 3: Engine Interface and Serializable Validation

In this task, you will need to modify:

src/mvcc/txn.rs
src/lsm_storage.rs

Implement validation in the commit phase. Hold commit_lock across validation, timestamp allocation, write publication, and insertion into committed_txns.

You will need to go through all transactions with commit timestamp within range (read_ts, expected_commit_ts) (both excluded bounds), and see if the read set of the current transaction overlaps with the write set of any transaction satisfying the criteria. If we can commit the transaction, submit a write batch, and insert the write set of this transaction into self.inner.mvcc().committed_txns, where the key is the commit timestamp.

Skip validation if write_set is empty. The checkpoint still sends the empty batch through the common commit path; avoiding its timestamp and metadata work is the bonus below.

You should also modify the put, delete, and write_batch interface in LsmStorageInner. We recommend you define a helper function write_batch_inner that processes a write batch. If options.serializable = true, put, delete, and the user-facing write_batch should create a transaction instead of directly creating a write batch. Your write batch helper function should also return a u64 commit timestamp so that Transaction::Commit can correctly store the committed transaction data into the MVCC structure.

Task 4: Garbage Collection

In this task, you will need to modify:

src/mvcc/txn.rs

After a successful write transaction commits, remove committed transaction records strictly below the watermark; no future transaction can have an older active read_ts.

Chapter Checkpoint

Point-read dependencies should now produce an execution equivalent to commit order, while the documented scan-phantom limitation remains visible.

Verify these cases explicitly:

Reproduce write skew and confirm exactly one of the overlapping transactions aborts.
Read a missing key, let another transaction insert it, then attempt to commit a dependent write from the first transaction.
Confirm that disjoint read and write sets both commit, and that two blind writes to the same key can serialize by commit order.
Run the scan-phantom example and explain why returned-key hashes cannot represent the missing predicate.
Keep the oldest transaction alive and confirm committed write-set metadata is retained until its watermark advances.

Test Your Understanding

If you have some experience with building a relational database, you may think about the following question: assume that we build a database based on Mini-LSM where we store each row in the relation table as a key-value pair (key: primary key, value: serialized row) and enable serializable verification, does the database system directly gain ANSI serializable isolation level capability? Why or why not?
The thing we implement here is actually write snapshot-isolation (see A critique of snapshot isolation) that guarantees serializable. Is there any cases where the execution is serializable, but will be rejected by the write snapshot-isolation validation?
There are databases that claim they have serializable snapshot isolation support by only tracking the keys accessed in gets and scans (instead of key range). Do they really prevent write skews caused by phantoms? (Okay… Actually, I’m talking about BadgerDB.)
Why must commit_lock cover both validation and publication? Construct an interleaving that fails if the lock is released between them.
Why does a get miss belong in the read set?
Why can two transactions that only write the same key both commit without violating serializability?
Which committed transaction records are safe to garbage-collect at a given watermark?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

Bonus Tasks

Read-Only Transactions. Return without allocating a commit timestamp or retaining an empty validation record when the write set is empty.
Precision/Predicate Locking. The read set can be maintained using a range instead of a single key. This would be useful when a user scans the full key space. This will also enable serializable verification for scan.

Snack Time: Compaction Filters

Congratulations! The engine now supports multi-version transactions. This final chapter generalizes version garbage collection into a user-installed compaction filter.

By the end of this chapter, you will be able to:

Apply a prefix filter without reclaiming versions that an active snapshot may still need.
Remove the selected version and older versions of the same user key from one compaction output.
Explain the intentionally undefined reads for a filtered key while reclamation is still propagating through the LSM tree.

For now, our compaction will simply retain the keys above the watermark and the latest version of the keys below the watermark. We can add some magic to the compaction process to help the user collect some unused data automatically as a background job.

Consider a case that the user uses Mini-LSM to store database tables. Each row in the table are prefixed with the table name. For example,

table1_key1 -> row
table1_key2 -> row
table1_key3 -> row
table2_key1 -> row
table2_key2 -> row

Now the user executes DROP TABLE table1. The engine will need to clean up all the data beginning with table1.

There are a lot of ways to achieve the goal. The user of Mini-LSM can scan all the keys beginning with table1 and requests the engine to delete it. However, scanning a very large database might be slow, and it will generate the same number of delete tombstones as the existing keys. Therefore, scan-and-delete will not free up the space occupied by the dropped table – instead, it will add more data to the engine and the space can only be reclaimed when the tombstones reach the bottom level of the engine.

Or, they can create column families (we will talk about this in rest of your life chapter). They store each table in a column family, which is a standalone LSM state, and directly remove the SST files corresponding to the column family when the user drop the table.

In this course, we implement a third approach: compaction filters. A filter can be installed at runtime. During later compactions, matching keys become eligible for removal without first writing one tombstone per row. A prefix=table1 filter therefore reclaims table 1 incrementally as compaction visits its files.

Before You Begin

A compaction filter is a logical deletion policy, not merely a byte predicate. It must interact correctly with MVCC garbage collection.

Keep these invariants in mind:

Versions above the watermark remain untouched, even when their user key matches the filter.
When the first version at or below the watermark matches, omit it and every older version of that user key from the current compaction output.
Non-matching keys follow the ordinary watermark and bottom-level tombstone rules.
Files outside the compaction task may still contain older matching versions. Reads in a filtered prefix are therefore intentionally undefined until reclamation has propagated.
Installing a filter does not synchronously free space; only compaction rewrites and removes the affected SSTs.

Predict before coding: With watermark 5, a filtered key has k@8=v8, k@5=v5, k@2=v2. Which versions survive this compaction? What changes after the watermark advances to 8?

Task 1: Compaction Filter

In this task, you will need to modify:

src/compact.rs
src/lsm_storage.rs

Define CompactionFilter::Prefix(Bytes), store installed filters in LsmStorageInner, and expose add_compaction_filter on the engine handle. Installing a filter only records policy for future compactions.

Iterate the filters in LsmStorageInner::compaction_filters. If the first version of a key at or below the watermark matches, omit it and ensure that older versions of the same key are skipped as well.

To copy and run the test cases:

cargo x copy-test --week 3 --day 7
cargo x scheck

You may assume that the user will not call get or scan within the filtered prefix. Such reads have undefined results because matching versions can disappear from some levels before others.

Chapter Checkpoint

Compaction should now reclaim filtered prefixes only as quickly as the watermark and selected compaction tasks permit.

Verify these cases explicitly:

Hold an old snapshot, install a filter, and compact; versions needed by the snapshot must remain.
Drop the snapshot and compact again; the matching version at or below the new watermark and its older history should disappear.
Mix matching and non-matching keys, including tombstones, and confirm ordinary garbage collection still applies to the non-matching keys.
Apply the filter in a non-bottom compaction and identify any older matching versions that remain outside the task.

Test Your Understanding

Why is it unsafe to filter every matching version regardless of timestamp?
After filtering the first version at or below the watermark, why must compaction also skip older versions of that user key?
Why are reads inside the filtered prefix undefined before every relevant level has been compacted?
How would you report progress for a DROP TABLE operation backed by an asynchronous compaction filter?
What API or metadata would be needed to remove or supersede a previously installed filter safely?

We do not provide reference answers to these questions, so feel free to discuss them in the Discord community.

The Rest of Your Life (TBD)

This is an advanced part that deep dives into optimizations and applications of the LSM storage engine and will make your implementation more production-ready. We are still planning on the content, and this part will not be publicly available in near future.

Week + Chapter	Topic	Solution	Starter Code	Writeup
4.1	Benchmarking
4.2	Block Compression
4.3	Trivial Move and Parallel Compaction
4.4	Alternative Block Encodings
4.5	Rate Limiter and I/O Optimizations
4.6	Build Your Own Block Cache
4.7	Build Your Own SkipList
4.8	Async Engine
4.9	IO-uring-based I/O engine
4.10	Prefetching
4.11	Key-Value Separation
4.12	Column Families
4.13	Sharding
4.14	Compaction Optimizations
4.15	SQL over Mini-LSM

Agent Fast Forward in 3 Days (WIP)

This is an alternative course track for students who intend to use a coding agent. The agent will write much of the code, but it must not silently design the system for you. Each day is a dialogue in which you make the consequential decisions, the agent turns a few accepted decisions into a small code change, and tests challenge the shared model.

Fast forward means compressing implementation time, not compressing the design into one generated answer.

Fast-forward day	Original course material	Outcome
Day 1	Mini-LSM	A working storage engine with memtables, SSTs, reads, writes, and flushes.
Day 2	Compaction and persistence	Coming later.
Day 3	MVCC	Coming later.

The original chapters remain a reference library. This track changes the pacing and the student’s role; it does not remove the need to understand ordering, representation, concurrency, and failure modes.

Prepare the Repository and the Agent

Do all repository-wide preparation before beginning Day 1, then start the agent from the starter directory—not from the repository root.

1. Install the Toolchain and Course Tools

Install Rust with rustup if it is not already available. Then clone the repository and install the tools used by the course:

git clone https://github.com/skyzh/mini-lsm
cd mini-lsm
cargo x install-tools

The repository pins its Rust toolchain in rust-toolchain.toml, so Cargo will select it automatically when Rust is managed by rustup.

If you already have the repository and tools, update your checkout as appropriate and begin from the repository root.

2. Start the Agent from `mini-lsm-starter`

Change into the starter directory before launching your coding agent:

cd mini-lsm-starter
pwd
# Start your coding agent here using the command for your tool.

The final component of pwd should be mini-lsm-starter. This matters because repository-aware agents discover the AGENTS.md in this directory and begin with the starter as their working scope.

Starting there is not a security sandbox: an agent can still traverse to a parent directory if instructed. The local AGENTS.md therefore prohibits reading, searching, diffing, or copying ../mini-lsm, including attempts to reconstruct the solution through Git history or an online copy.

Do not open the whole repository as the agent’s workspace if your tool lets you choose a directory. The agent may consult copied tests, starter interfaces, Rust documentation, and course chapters under ../mini-lsm-book/src/.

3. Verify the Instructions Before Coding

Do not assume the tool discovered AGENTS.md. Make the first prompt a handshake that performs no implementation:

Before editing anything, confirm that your working directory is mini-lsm-starter and read ./AGENTS.md. Summarize its reference-solution boundary, test protections, and student-owned design protocol. Explain which choices require a stop and which mechanical coding choices do not. Tell me which local sources you may use, then stop without changing files.

If the response omits the reference-solution boundary, test protection, or one-decision-at-a-time stop, correct the agent before continuing. If the tool cannot load repository instructions automatically, paste AGENTS.md into its persistent project instructions.

The Design-and-Test Loop

Begin a checkpoint with an ordinary capability request:

Implement block format.

That prompt authorizes the learning process, not a one-shot patch. The agent should inspect allowed context and ask its first design question. It should not return a complete design, edit code, or run ahead to a passing suite.

Repeat this loop:

Agent asks one decision. It labels the question as a fixed contract to derive or an open design choice, gives the invariant or concrete case, explains real alternatives when they exist, and asks you to choose or predict.
Student reasons. State a choice and why. A prediction is useful even when you are uncertain.
Agent checks the reasoning. It connects the answer to interfaces, prose, or tests. If the answer violates a constraint, it shows the evidence and asks again instead of silently overriding you.
Agent records the choice. The accepted answer enters a short decision ledger.
Agent implements one slice. Once enough decisions specify a coherent slice, it previews the files, behavior, and focused test and waits for your authorization.
Tests produce evidence. A coding mistake can be fixed directly. A failure that exposes an unsettled or incorrect design returns to the dialogue.
Student reviews. Inspect the diff and test output before authorizing the next slice.

The agent must stop on topics that affect behavior or understanding: representation, ordering, ownership, size and boundary accounting, seek semantics, error behavior, synchronization, and optimization placement. Some answers are fixed by the course protocol and must be derived; others are genuine choices. It need not interrupt you over a local variable name, import order, formatting, or an obvious compiler-directed repair.

The distinction keeps the conversation educational without turning every keystroke into ceremony.

Keep a Decision Ledger

Ask the agent to maintain this table during each checkpoint:

Decision or constraint	Student’s conclusion	Invariant or evidence	Consequence
Example: exact-size block	Accept it	The limit is inclusive	Reject only when projected size is greater than the target.

The ledger makes hidden assumptions reviewable. It also prevents a required course constraint from being presented as a free preference, and lets you distinguish a coding bug from code that faithfully implements a bad decision.

You can delegate a decision when it is not where you want to spend learning time:

Choose this one for me, explain the tradeoff, and record it as delegated. Continue asking me about the remaining decisions.

Delegating one choice is not permission for the agent to decide the rest.

Review a Code Slice

Before each edit, the agent should state:

which accepted decisions determine the slice;
which files and observable behavior will change; and
which focused check it expects to exercise that behavior.

After the edit, require the exact command and result, then ask:

Treat this slice as untrusted. Connect the changed behavior to the decision ledger and supplied tests. Identify one plausible bug that could still pass, propose the smallest adversarial check, and ask me to predict its outcome before adding it.

Do not let “all tests pass” end the review. Conversely, once the contract and adversarial checks are satisfied, continue to the next unresolved decision instead of inventing unrelated refactors.

When the workspace is prepared and the instruction handshake succeeds, continue to Day 1 - Mini-LSM.

Day 1 - Mini-LSM

This is the first day of Agent Fast Forward in 3 Days. You will use a coding agent to build and defend one working storage engine from the original Mini-LSM material:

put/delete -> mutable memtable -> immutable memtables -> L0 SSTs
                     \____________ read + merge ____________/

You decide consequential behavior; the agent handles mechanical implementation. A short request begins a design interview; it must not produce a complete implementation in one turn.

The Completion Contract

At the end of this path:

put, delete, get, and bounded scan work across memory and disk;
a frozen memtable can be flushed into an L0 SST;
Bloom filters and prefix encoding improve the implementation without changing its results;
the complete supplied test suite passes; and
you can trace a key through the engine, explain why the newest value wins, and design a test for a plausible bug.

The tests are evidence, not the specification. Generated code remains untrusted until you can connect it to a decision and an invariant and try to falsify it.

Copy the Complete Test Suite

Complete the repository and agent preparation in the track overview. Leave the agent at the instruction-handshake stop, then run these commands from the repository root:

cargo x copy-test --week 1
cargo x scheck

The initial check should fail because the starter contains unfinished code. Record the first failure as a reproducible baseline. Do not ask the agent to make it disappear by changing the tests.

Start Day 1

With the agent running from mini-lsm-starter, the instruction handshake complete, and the tests copied, send:

Implement the Mini-LSM write, read, and flush paths. Follow the student-owned design protocol in AGENTS.md. Ask one design decision at a time, record my accepted choices, and do not edit until those choices specify one coherent slice. Never access ../mini-lsm.

The first useful response is a question, not an architecture essay or a patch. It will usually ask you to choose the first checkpoint. Select one of the three below and explain why it is a useful boundary.

For each checkpoint, the tables below are an audit guide for you. Do not paste a whole table back as a ready-made specification. Make the agent elicit one topic at a time, label it as a fixed contract or an open choice, and use the table afterward to check whether the dialogue covered the important ground.

Checkpoint 1: Ordered State

Ask:

Implement ordered in-memory state.

This checkpoint covers the memtable and iterator layers. Use the Memtable and Merge Iterator chapters when a question needs more context.

The agent should stop on at least these contract topics and ask you to derive the required behavior:

Decision	Case that exposes it
Memtable ordering	Insert keys out of bytewise order, then scan.
Duplicate precedence inside a memtable	Put two values for one key before reading it.
Tombstone representation	Delete a key that still has a value in older state.
Equal-key precedence across merge inputs	Reverse two inputs containing the same key.
Iterator behavior after exhaustion or error	Call `next` again and check that iteration cannot resume.
Write/freeze synchronization	Interleave insertion with a concurrent memtable freeze.

One critical outcome is that an ordinary write retains the state read guard until insertion into the mutable memtable completes. Writing through a cloned snapshot after releasing the guard permits a concurrent freeze to make that memtable immutable before the write occurs.

Once the representation and precedence choices are settled, authorize the smallest coherent slice. After its focused test passes, ask the agent to identify the exact comparison that resolves duplicate keys. Explain in your own words why changing > to >=, or reversing input order, changes the visible value.

Checkpoint 2: Durable Representation

Ask:

Implement the durable block and SST representation.

This checkpoint covers blocks, block iterators, SST builders, SST readers, SST iterators, Bloom filters, and final prefix compression. Consult Block, Sorted String Table, and SST Optimizations when a question requires deeper context.

Because this path copies all seven test suites at the start, the accepted design should converge directly on the final Day 7 prefix-compressed block format. Do not first implement the Day 3 layout and silently replace it. The agent should explicitly ask which acceptance target applies and record that choice.

First derive the parts fixed by the course contract:

Contract	Case that exposes it
Integer encoding and exact block layout	Independently decode a three-entry block.
Inclusive target-size accounting	Add an entry that makes the encoded block exactly the target size.
Oversized first entry	Try to add a single representable record larger than the target.
Prefix basis and reconstruction	Mix keys with a long shared prefix and no shared prefix.
Lower-bound seek semantics	Seek before, between, at, and after stored keys.
SST trailer placement	Locate metadata and Bloom sections from the end of the file.
Bloom-filter authority	Compare a definite negative with a possible positive.

Then make the genuinely open implementation choices, such as linear versus binary lower-bound search when both satisfy the interface, allocation versus reuse for reconstructed keys, and how much malformed-input checking to add without changing the provided API. Record required protocol facts as constraints and open selections as choices.

The high-level SST trailer grammar is:

blocks | metadata | metadata_offset:u32 | bloom | bloom_offset:u32

The final four bytes contain bloom_offset; the metadata offset is the four-byte field immediately before the Bloom section, at bloom_offset - 4.

Treat the writer and reader as two parties implementing a protocol. A round-trip test alone can miss an encoder and decoder that agree with each other but disagree with the specified bytes. Ask for at least one independently calculated byte layout.

Illustrative Dialogue: “Implement Block Format”

This is a condensed example of the expected interaction, including representative command output rather than a transcript captured from your machine. It targets the final prefix-compressed format required by fast-forward Day 1.

Student: Implement block format.

Agent: This can be split into builder/encoding and iterator/seek slices. Which slice should establish the contract first, and why?

Student: Builder and encoding first. The iterator consumes that representation, while encoding can be checked independently against exact bytes.

Agent: Contract derivation: the full Week 1 suite is installed. Should this slice implement the earlier uncompressed Day 3 entry or the final Day 7 prefix-compressed entry? What evidence decides?

Student: The final Day 7 format. Replacing an intermediate format inside the same checkpoint would be throwaway work, and the installed acceptance target includes prefix compression.

Agent: Contract derivation: a compressed key can be relative to the previous key or the first key in the block. Which basis does the course require, and what does it permit an iterator to do?

Student: Use the first key. Then any entry can be reconstructed independently once the first key is known; using the previous key would require decoding the chain before it.

Agent: Derive the projected encoded size for a new entry with rest_key_len suffix bytes and decide whether an exact fit is admitted.

Student: For n existing entries: data.len() + 2 + 2 + rest_key_len + 2 + value.len() + 2 * (n + 1) + 2. The fields are overlap length, suffix length, suffix, value length, value, all offsets after the add, and the one final count. Equality fits.

Agent: Open choice: because first-key compression makes an arbitrary entry independently decodable, lower-bound seek can scan linearly or binary-search offsets. Which do you want?

Student: Binary search. The entries are sorted, and independent reconstruction makes each comparison possible without decoding all preceding entries.

Agent: Open choice: decode has no error return. Should this checkpoint trust encoder-produced bytes, add assertions that still panic, or request an interface change to return Result?

Student: Trust encoder-produced bytes for this checkpoint and document the boundary. A production decoder should return Result and validate counts, offsets, and lengths, but changing the interface is outside scope.

Agent: The slice is specified. I will change src/block/builder.rs, src/block.rs, and src/block/iterator.rs, then run cargo test --lib tests::week1_day7::test_task3_block_key_compression. Prediction first: with empty values, mini-a encodes as an overlap of 0 plus a six-byte suffix, and mini-b as an overlap of 5 plus a one-byte suffix. What are the two entry offsets and final encoded size?

Student: The first entry is 12 bytes and starts at 0. The second is 7 bytes and starts at 12. Two offsets and the final count add 6 bytes, so the encoded block is 25 bytes. I authorize this slice.

Agent: Implemented only the authorized block slice. cargo test --lib tests::week1_day7::test_task3_block_key_compression exited 0. The entries reconstructed as mini-a and mini-b, the empty values survived, and the encoded length was 25 bytes. I did not begin the SST layer. One remaining weakness is that the supplied valid-block tests do not establish safe behavior for malformed offsets. Before I add an adversarial test, predict what the current trusted decoder would do with an offset beyond the data section.

The final agent turn contains evidence, a checkpoint stop, and a new question. It does not treat a passing test as permission to continue. In a real session, inspect the diff and actual command output before accepting that report. An unexpected test failure either reveals a mechanical bug or reopens one specific decision.

Before approving the completed checkpoint, decode three keys by hand: one with no shared prefix, one with a long shared prefix, and one with an empty value. Confirm that a seek returns the first key greater than or equal to its target and that a Bloom-filter negative can never hide a present key.

Checkpoint 3: One Logical Engine

Ask:

Connect the components into one logical engine.

This checkpoint covers the read path, write path, freezing, flushing, SST filtering, and iterator accounting. Use Read Path and Write Path when a decision needs more context.

The agent must lead contract derivations for source ordering, tombstone filtering, scan bounds, flush selection, and lifecycle behavior. It should separately ask about open implementation choices such as iterator composition, lock scope that still preserves the synchronization contract, and where to perform expensive SST construction.

The central source-priority rule should emerge from those choices:

mutable memtable
  > immutable memtables, newest to oldest
  > L0 SSTs, newest to oldest

For a duplicate key, the first visible entry wins. If it is a tombstone, the key is absent; an older value must not be resurrected.

Review the flush transition with concrete state:

before: imm = [newest, ..., oldest], L0 = [newest, ..., oldest]
flush:  build an SST from the oldest immutable memtable
after:  remove exactly that memtable and insert its SST at the newest side of L0

Expensive SST construction and I/O should happen outside the state read-write lock. Structural changes still need state_lock so two flushes cannot select and install the same memtable concurrently.

For Day 1, the lifecycle contract is fixed: close stops and joins the existing worker threads and is harmless when called again after their handles have already been taken. It does not implicitly flush the remaining mutable memtable. Treat a different contract as an explicit scope change, not an ordinary implementation preference.

Before approving this checkpoint, construct one key that appears in the mutable memtable, an immutable memtable, and an L0 SST. Predict get and scan when the newest entry is first a value and then a tombstone. Also exercise included, excluded, and unbounded scan endpoints.

Audit the Finished Engine

Run the full project check from the repository root:

cargo x scheck

Then ask the agent for a final evidence report containing:

the combined decision ledgers and any delegated choices;
the commands it ran and their outcomes;
a data-flow trace for one put, one get, one bounded scan, and one flush;
the source-priority rule used by both point reads and scans;
one concurrency risk around freezing or flushing and the synchronization that prevents it;
one optimization that must not alter logical results; and
one weakness or boundary case not established by the supplied tests.

Review actual diffs and test output, not only the report. Search for removed assertions, changed tests, broad lint suppressions, and error paths replaced with unwrap without justification.

Finally, introduce one small, deliberate fault—for example, reverse equal-key precedence in a merge iterator or make an excluded upper bound inclusive. Predict which test should fail, run it, and revert the fault. This verifies that the tests can detect at least one mistake you understand.

Day 1 Completion Checkpoint

You are ready for Day 2 when you can do these without delegating the answer back to the agent:

draw the write, read, and flush paths from memory;
explain the ordering rule that selects one value from duplicate keys;
explain the byte layout of a block and how an SST locates one;
identify where tombstones are created and where they are filtered;
explain why a Bloom-filter negative is safe and a positive is inconclusive;
describe an unsafe flush interleaving and how the implementation prevents it; and
turn a suspected invariant violation into a minimal test.

If you cannot yet do one of these, use the corresponding Mini-LSM chapter and ask the agent to quiz you with concrete states or byte layouts. The measure of success is not whether you typed the implementation. It is whether you can specify, inspect, test, and change the system with confidence.

Mini-LSM v1

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a new version of this course. We keep the legacy version in this book so that the search engine can keep the pages in the index and users can follow the links to the new version of the course.

V1 Course Overview

Course Overview

In this course, we will build the LSM tree structure in 7 days:

Day 1: Block encoding. SSTs are composed of multiple data blocks. We will implement the block encoding.
Day 2: SST encoding.
Day 3: MemTable and Merge Iterators.
Day 4: Block cache and Engine. To reduce disk I/O and maximize performance, we will use moka-rs to build a block cache for the LSM tree. In this day we will get a functional (but not persistent) key-value engine with get, put, scan, delete API.
Day 5: Compaction. Now it’s time to maintain a leveled structure for SSTs.
Day 6: Recovery. We will implement WAL and manifest so that the engine can recover after restart.
Day 7: Bloom filter and key compression. They are widely-used optimizations in LSM tree structures.

Development Guide

We provide you starter code (see mini-lsm-starter crate), where we simply replace all function body with unimplemented!(). You can start your project based on this starter code. We provide test cases, but they are very simple. We recommend you to think carefully about your implementation and write test cases by yourself.

You can use cargo x scheck to run all test cases and do style check in your codebase.
You can use cargo x copy-test dayX to copy test cases to the starter code.

Block Builder and Block Iterator

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of Mini-LSM Week 1 Day 3: Blocks.

In this part, you will need to modify:

src/block/builder.rs
src/block/iterator.rs
src/block.rs

You can use cargo x copy-test day1 to copy our provided test cases to the starter code directory. After you have finished this part, use cargo x scheck to check the style and run all test cases. If you want to write your own test cases, write a new module #[cfg(test)] mod user_tests { /* your test cases */ } in block.rs. Remember to remove #![allow(...)] at the top of the modules you modified so that cargo clippy can actually check the styles.

Task 1 - Block Builder

Block is the minimum read unit in LSM. It is of 4KB size in general, similar to database pages. In each block, we will store a sequence of sorted key-value pairs.

You will need to modify BlockBuilder in src/block/builder.rs to build the encoded data and the offset array. The block contains two parts: data and offsets.

---------------------------------------------------------------------
| data  | offsets | meta  |
| ----- | ------- | ----- |
| entry | entry   | entry | entry | offset | offset | offset | offset | num_of_elements |
---------------------------------------------------------------------

When user adds a key-value pair to a block (which is an entry), we will need to serialize it into the following format:

-----------------------------------------------------------------------
|                           Entry #1                            | ... |
-----------------------------------------------------------------------
| key_len (2B) | key (keylen) | value_len (2B) | value (varlen) | ... |
-----------------------------------------------------------------------

Key length and value length are both 2 bytes, which means their maximum lengths are 65535. (Internally stored as u16)

We assume that keys will never be empty, and values can be empty. An empty value means that the corresponding key has been deleted in the view of other parts of the system. For the BlockBuilder and BlockIterator, we just treat the empty value as-is.

At the end of each block, we will store the offsets of each entry and the total number of entries. For example, if the first entry is at 0th position of the block, and the second entry is at 12th position of the block.

-------------------------------
|offset|offset|num_of_elements|
-------------------------------
|   0  |  12  |       2       |
-------------------------------

The footer of the block will be as above. Each of the number is stored as u16.

The block has a size limit, which is target_size. Unless the first key-value pair exceeds the target block size, you should ensure that the encoded block size is always less than or equal to target_size. (In the provided code, the target_size here is essentially the block_size)

The BlockBuilder will produce the data part and unencoded entry offsets when build is called. The information will be stored in the Block struct. As key-value entries are stored in raw format and offsets are stored in a separate vector, this reduces unnecessary memory allocations and processing overhead when decoding data —— what you need to do is to simply copy the raw block data to the data vector and decode the entry offsets every 2 bytes, instead of creating something like Vec<(Vec<u8>, Vec<u8>)> to store all the key-value pairs in one block in memory. This compact memory layout is very efficient.

For the encoding and decoding part, you’ll need to modify Block in src/block.rs. Specifically, you are required to implement Block::encode and Block::decode, which will encode to / decode from the data layout illustrated in the above figures.

Task 2 - Block Iterator

Given a Block object, we will need to extract the key-value pairs. To do this, we create an iterator over a block and find the information we want.

BlockIterator can be created with an Arc<Block>. If create_and_seek_to_first is called, it will be positioned at the first key in the block. If create_and_seek_to_key is called, the iterator will be positioned at the first key that is >= the provided key. For example, if 1, 3, 5 is in a block.

#![allow(unused)]
fn main() {
let mut iter = BlockIterator::create_and_seek_to_key(block, b"2");
assert_eq!(iter.key(), b"3");
}

The above seek 2 will make the iterator to be positioned at the next available key of 2, which in this case is 3.

The iterator should copy key and value from the block and store them inside the iterator, so that users can access the key and the value without any extra copy with fn key(&self) -> &[u8], which directly returns the reference of the locally-stored key and value.

When next is called, the iterator will move to the next position. If we reach the end of the block, we can set key to empty and return false from is_valid, so that the caller can switch to another block if possible.

After implementing this part, you should be able to pass all tests in block/tests.rs.

Extra Tasks

Here is a list of extra tasks you can do to make the block encoding more robust and efficient.

Note: Some test cases might not pass after implementing this part. You might need to write your own test cases.

Implement block checksum. Verify checksum when decoding the block.
Compress / Decompress block. Compress on build and decompress on decoding.

SST Builder and SST Iterator

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of Mini-LSM Week 1 Day 4: Sorted String Table (SST).

In this part, you will need to modify:

src/table/builder.rs
src/table/iterator.rs
src/table.rs

You can use cargo x copy-test day2 to copy our provided test cases to the starter code directory. After you have finished this part, use cargo x scheck to check the style and run all test cases. If you want to write your own test cases, write a new module #[cfg(test)] mod user_tests { /* your test cases */ } in table.rs. Remember to remove #![allow(...)] at the top of the modules you modified so that cargo clippy can actually check the styles.

Task 1 - SST Builder

SST is composed of data blocks and index blocks stored on the disk. Usually, data blocks are lazily loaded – they will not be loaded into the memory until a user requests it. Index blocks can also be loaded on-demand, but in this course, we make simple assumptions that all SST index blocks (meta blocks) can fit in memory. Generally, an SST file is of 256MB size.

The SST builder is similar to block builder – users will call add on the builder. You should maintain a BlockBuilder inside SST builder and split block when necessary. Also, you will need to maintain block metadata BlockMeta, which includes the first key in each block and the offset of each block. The build function will encode the SST, write everything to disk using FileObject::create, and return an SsTable object. Note that in part 2, you don’t need to actually write the data to the disk. Just store everything in memory as a vector until we implement a block cache (Day 4, Task 5).

The encoding of SST is like:

-------------------------------------------------------------------------------------------
|         Block Section         |          Meta Section         |          Extra          |
-------------------------------------------------------------------------------------------
| data block | ... | data block | meta block | ... | meta block | meta block offset (u32) |
-------------------------------------------------------------------------------------------

You also need to implement estimated_size function of SsTableBuilder, so that the caller can know when can it start a new SST to write data. The function don’t need to be very accurate. Given the assumption that data blocks contain much more data than meta block, we can simply return the size of data blocks for estimated_size.

You can also align blocks to 4KB boundary so as to make it possible to do direct I/O in the future. This is an optional optimization.

The recommend sequence to finish Task 1 is as below:

Implement SsTableBuilder in src/table/builder.rs
- Before implementing SsTableBuilder, you may want to take a look in src/table.rs, for FileObject & BlockMeta.
- For FileObject, you should at least implement read, size and create (No need for Disk I/O) before day 4.
- For BlockMeta, you may want to add some extra fields when encoding / decoding the BlockMeta to / from a buffer.
Implement SsTable in src/table.rs
- Same as above, you do not need to worry about BlockCache until day 4.

After finishing Task 1, you should be able to pass all the current tests except two iterator tests.

Task 2 - SST Iterator

Like BlockIterator, you will need to implement an iterator over an SST. Note that you should load data on demand. For example, if your iterator is at block 1, it should not hold any other block content in memory until it reaches the next block.

SsTableIterator should implement the StorageIterator trait, so that it can be composed with other iterators in the future.

One thing to note is seek_to_key function. Basically, you will need to do binary search on block metadata to find which block might possibly contain the key. It is possible that the key doesn’t exist in the LSM tree so that the block iterator will be invalid immediately after a seek. For example,

----------------------------------
| block 1 | block 2 | block meta |
----------------------------------
| a, b, c | e, f, g | 1: a, 2: e |
----------------------------------

If we do seek(b) in this SST, it is quite simple – using binary search, we can know block 1 contains keys a <= keys < e. Therefore, we load block 1 and seek the block iterator to the corresponding position.

But if we do seek(d), we will position to block 1, but seeking d in block 1 will reach the end of the block. Therefore, we should check if the iterator is invalid after the seek, and switch to the next block if necessary.

Extra Tasks

Here is a list of extra tasks you can do to make the block encoding more robust and efficient.

Note: Some test cases might not pass after implementing this part. You might need to write your own test cases.

Implement index checksum. Verify checksum when decoding.
Explore different SST encoding and layout. For example, in the Lethe paper, the author adds secondary key support to SST.

Mem Table and Merge Iterators

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of Mini-LSM Week 1 Day 1: Memtable and Mini-LSM Week 1 Day 2: Merge Iterator

In this part, you will need to modify:

src/iterators/merge_iterator.rs
src/iterators/two_merge_iterator.rs
src/mem_table.rs

You can use cargo x copy-test day3 to copy our provided test cases to the starter code directory. After you have finished this part, use cargo x scheck to check the style and run all test cases. If you want to write your own test cases, write a new module #[cfg(test)] mod user_tests { /* your test cases */ } in table.rs. Remember to remove #![allow(...)] at the top of the modules you modified so that cargo clippy can actually check the styles.

This is the last part for the basic building blocks of an LSM tree. After implementing the merge iterators, we can easily merge data from different part of the data structure (mem table + SST) and get an iterator over all data. And in part 4, we will compose all these things together to make a real storage engine.

Task 1 - Mem Table

In this course, we use crossbeam-skiplist as the implementation of memtable. Skiplist is like linked-list, where data is stored in a list node and will not be moved in memory. Instead of using a single pointer for the next element, the nodes in skiplists contain multiple pointers and allow user to “skip some elements”, so that we can achieve O(log n) search, insertion, and deletion.

In storage engine, users will create iterators over the data structure. Generally, once user modifies the data structure, the iterator will become invalid (which is the case for C++ STL and Rust containers). However, skiplists allow us to access and modify the data structure at the same time, therefore potentially improving the performance when there is concurrent access. There are some papers argue that skiplists are bad, but the good property that data stays in its place in memory can make the implementation easier for us.

In mem_table.rs, you will need to implement a mem-table based on crossbeam-skiplist. Note that the memtable only supports get, scan, and put without delete. The deletion is represented as a tombstone key -> empty value, and the actual data will be deleted during the compaction process (day 5). Note that all get, scan, put functions only need &self, which means that we can concurrently call these operations.

Task 2 - Mem Table Iterator

You can now implement an iterator MemTableIterator for MemTable. memtable.iter(start, end) will create an iterator that returns all elements within the range start, end. Here, start is std::ops::Bound, which contains 3 variants: Unbounded, Included(key), Excluded(key). The expresiveness of std::ops::Bound eliminates the need to memorizing whether an API has a closed range or open range.

Note that crossbeam-skiplist’s iterator has the same lifetime as the skiplist itself, which means that we will always need to provide a lifetime when using the iterator. This is very hard to use. You can use the ouroboros crate to create a self-referential struct that erases the lifetime. You will find the ouroboros examples helpful.

#![allow(unused)]
fn main() {
pub struct MemTableIterator {
    /// hold the reference to the skiplist so that the iterator will be valid.
    map: Arc<SkipList>
    /// then the lifetime of the iterator should be the same as the `MemTableIterator` struct itself
    iter: SkipList::Iter<'this>
}
}

You will also need to convert the Rust-style iterator API to our storage iterator. In Rust, we use next() -> Data. But in this course, next doesn’t have a return value, and the data should be fetched by key() and value(). You will need to think a way to implement this.

Spoiler: the MemTableIterator struct

#![allow(unused)]
fn main() {
#[self_referencing]
pub struct MemTableIterator {
    map: Arc<SkipMap<Bytes, Bytes>>,
    #[borrows(map)]
    #[not_covariant]
    iter: SkipMapRangeIter<'this>,
    item: (Bytes, Bytes),
}
}

We have map serving as a reference to the skipmap, iter as a self-referential item of the struct, and item as the last item from the iterator. You might have thought of using something like iter::Peekable, but it requires &mut self when retrieving the key and value. Therefore, one approach is to (1) get the element from the iterator on initializing the MemTableIterator, store it in item (2) when calling next, we get the element from inner iter’s next and move the inner iter to the next position.

In this design, you might have noticed that as long as we have the iterator object, the mem-table cannot be freed from the memory. In this course, we assume user operations are short, so that this will not cause big problems. See extra task for possible improvements.

You can also consider using AgateDB’s skiplist implementation, which avoids the problem of creating a self-referential struct.

Task 3 - Merge Iterator

Now that you have a lot of mem-tables and SSTs, you might want to merge them to get the latest occurrence of a key. In merge_iterator.rs, we have MergeIterator, which is an iterator that merges all iterators of the same type. The iterator at the lower index position of the new function has higher priority, that is to say, if we have:

iter1: 1->a, 2->b, 3->c
iter2: 1->d
iter: MergeIterator::create(vec![iter1, iter2])

The final iterator will produce 1->a, 2->b, 3->c. The data in iter1 will overwrite the data in other iterators.

You can use a BinaryHeap to implement this merge iterator. Note that you should never put any invalid iterator inside the binary heap. One common pitfall is on error handling. For example,

#![allow(unused)]
fn main() {
let Some(mut inner_iter) = self.iters.peek_mut() {
    inner_iter.next()?; // <- will cause problem
}
}

If next returns an error (i.e., due to disk failure, network failure, checksum error, etc.), it is no longer valid. However, when we go out of the if condition and return the error to the caller, PeekMut’s drop will try move the element within the heap, which causes an access to an invalid iterator. Therefore, you will need to do all error handling by yourself instead of using ? within the scope of PeekMut.

You will also need to define a wrapper for the storage iterator so that BinaryHeap can compare across all iterators.

Task 4 - Two Merge Iterator

The LSM has two structures for storing data: the mem-tables in memory, and the SSTs on disk. After we constructed the iterator for all SSTs and all mem-tables respectively, we will need a new iterator to merge iterators of two different types. That is TwoMergeIterator.

You can implement TwoMergeIterator in two_merge_iter.rs. Similar to MergeIterator, if the same key is found in both of the iterator, the first iterator takes precedence.

In this course, we explicitly did not use something like Box<dyn StorageIter> to avoid dynamic dispatch. This is a common optimization in LSM storage engines.

Extra Tasks

Implement different mem-table and see how it differs from skiplist. i.e., BTree mem-table. You will notice that it is hard to get an iterator over the B+ tree without holding a lock of the same timespan as the iterator. You might need to think of smart ways of solving this.
Async iterator. One interesting thing to explore is to see if it is possible to asynchronize everything in the storage engine. You might find some lifetime related problems and need to workaround them.
Foreground iterator. In this course we assumed that all operations are short, so that we can hold reference to mem-table in the iterator. If an iterator is held by users for a long time, the whole mem-table (which might be 256MB) will stay in the memory even if it has been flushed to disk. To solve this, we can provide a ForegroundIterator / LongIterator to our user. The iterator will periodically create new underlying storage iterator so as to allow garbage collection of the resources.

Storage Engine and Block Cache

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of Mini-LSM Week 1 Day 5: Read Path and Mini-LSM Week 1 Day 6: Write Path

In this part, you will need to modify:

src/lsm_iterator.rs
src/lsm_storage.rs
src/table.rs
Other parts that use SsTable::read_block

You can use cargo x copy-test day4 to copy our provided test cases to the starter code directory. After you have finished this part, use cargo x scheck to check the style and run all test cases. If you want to write your own test cases, write a new module #[cfg(test)] mod user_tests { /* your test cases */ } in table.rs. Remember to remove #![allow(...)] at the top of the modules you modified so that cargo clippy can actually check the styles.

Task 1 - Put and Delete

Before implementing put and delete, let’s revisit how LSM tree works. The structure of LSM includes:

Mem-table: one active mutable mem-table and multiple immutable mem-tables.
Write-ahead log: each mem-table corresponds to a WAL.
SSTs: mem-table can be flushed to the disk in SST format. SSTs are organized in multiple levels.

In this part, we only need to take the lock, write the entry (or tombstone) into the active mem-table. You can modify lsm_storage.rs.

Task 2 - Get

To get a value from the LSM, we can simply probe from active memtable, immutable memtables (from latest to earliest), and all the SSTs. To reduce the critical section, we can hold the read lock to copy all the pointers to mem-tables and SSTs out of the LsmStorageInner structure, and create iterators out of the critical section. Be careful about the order when creating iterators and probing.

Task 3 - Scan

To create a scan iterator LsmIterator, you will need to use TwoMergeIterator to merge MergeIterator on mem-table and MergeIterator on SST. You can implement this in lsm_iterator.rs. Optionally, you can implement FusedIterator so that if a user accidentally calls next after the iterator becomes invalid, the underlying iterator won’t panic.

The sequence of key-value pairs produced by TwoMergeIterator may contain empty value, which means that the value is deleted. LsmIterator should filter these empty values. Also it needs to correctly handle the start and end bounds.

Task 4 - Sync

In this part, we will implement mem-tables and flush to L0 SSTs in lsm_storage.rs. As in task 1, write operations go directly into the active mutable mem-table. Once sync is called, we flush SSTs to the disk in two steps:

Firstly, move the current mutable mem-table to immutable mem-table list, so that no future requests will go into the current mem-table. Create a new mem-table. All of these should happen in one single critical section and stall all reads.
Then, we can flush the mem-table to disk as an SST file without holding any lock.
Finally, in one critical section, remove the mem-table and put the SST into l0_tables.

Only one thread can sync at a time, and therefore you should use a mutex to ensure this requirement.

Task 5 - Block Cache

Now that we have implemented the LSM structure, we can start writing something to the disk! Previously in table.rs, we implemented a FileObject struct, without writing anything to disk. In this task, we will change the implementation so that:

read will read from the disk without any caching using read_exact_at in std::os::unix::fs::FileExt.
The size of the file should be stored inside the struct, and size function directly returns it.
create should write the file to the disk. Generally you should call fsync on that file. But this would slow down unit tests a lot. Therefore, we don’t do fsync until day 6 recovery.
open remains unimplemented until day 6 recovery.

After that, we can implement a new read_block_cached function on SsTable so that we can leverage block cache to serve read requests. Upon initializing the LsmStorage struct, you should create a block cache of 4GB size using moka-rs. Blocks are cached by SST id + block id. Use try_get_with to get the block from cache / populate the cache if cache miss. If there are multiple requests reading the same block and cache misses, try_get_with will only issue a single read request to the disk and broadcast the result to all requests.

Remember to change SsTableIterator to use the block cache.

Extra Tasks

As you might have seen, each time we do a get, put or deletion, we will need to take a read lock protecting the LSM structure; and if we want to flush, we will need to take a write lock. This can cause a lot of problems. Some lock implementations are fair, which means as long as there is a writer waiting on the lock, no reader can take the lock. Therefore, the writer will wait until the slowest reader finishes its operation before it can actually do some work. One possible optimization is to implement WriteBatch. We don’t need to immediately write users’ requests into mem-table + WAL. We can allow users to do a batch of writes.
Align blocks to 4K and use direct I/O.

Leveled Compaction

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of:

We did not finish this chapter as part of Mini-LSM v1.

Write-Ahead Log for Recovery

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of:

We did not finish this chapter as part of Mini-LSM v1.

Bloom Filters

This is a legacy version of the Mini-LSM course and we will not maintain it anymore. We now have a better version of this course and this chapter is now part of Mini LSM Week 1 Day 7: SST Optimizations.

We did not finish this chapter as part of Mini-LSM v1.

Key Compression

We did not finish this chapter as part of Mini-LSM v1.

What’s Next

We did not finish this chapter as part of Mini-LSM v1.

Keyboard shortcuts

LSM in a Week