Learn Database Internals

Mini-LSM is a hands-on course for systems and backend engineers. You will build an LSM-tree storage engine in Rust, from its in-memory write path and on-disk format to compaction, crash recovery, MVCC, and transactions.

Week 1 produces a working storage engine. Weeks 2 and 3 add production-inspired durability, background maintenance, and concurrency control. If you use a coding agent, a separate guided track lets the agent handle much of the mechanical implementation while you retain ownership of the representation, ordering, failure, and testing decisions.

Choose Your Path

Both paths build the same small storage system. The difference is who types most of the code, not who owns the understanding.

Is This Course for You?

Mini-LSM is designed for you if you have used PostgreSQL, MySQL, Redis, RocksDB, or another data system and want to understand what happens below its API. It is also a practical starting point if you want to read production storage-engine code but first need a complete system small enough to hold in your head.

You will learn about:

• storage layout, ordered in-memory state, blocks, and SSTs;
• read and write paths over several physical data sources;
• compaction and its read, write, and space tradeoffs;
• durability through manifests, write-ahead logging, and recovery; and
• snapshots, MVCC, garbage collection, and concurrency control.

Mini-LSM focuses on a database storage engine. It does not include a SQL parser, query optimizer, replication, or distributed consensus. Those are valuable next steps, but keeping them outside this course makes it possible to understand the storage layer end to end.

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 creates several useful engineering properties.

1. 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.
2. 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.

Prerequisites

• You should know the basics of the Rust programming language. Reading The Rust Programming Language is sufficient. The course introduces less common Rust patterns when they appear, but you should be comfortable reading compiler errors and consulting crate documentation.
• You should understand a small persistent key-value store such as Bitcask: appending updates to a log, keeping an in-memory index that points to the newest record, representing deletion with a marker, reclaiming obsolete records by merging files, and rebuilding state after a restart. If these ideas are unfamiliar, consider implementing Bitcask through the PingCAP Talent Plan.
• You do not need prior knowledge of LSM trees, compaction strategies, MVCC, or transaction isolation. The course overview bridges the Bitcask model to Mini-LSM, and each week introduces its own storage concepts. An external LevelDB or RocksDB overview is optional enrichment rather than required preparation.

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.

How to Use the Learning Checks

The book uses four kinds of checks for different purposes:

1. Predict before coding asks you to trace a small state before implementation details distract you. If your code later disagrees, first decide which invariant your prediction or implementation missed.
2. Chapter checkpoints combine tests with cases that the supplied suite may not cover. Record the state, execution, or byte layout that supports your conclusion; passing tests alone is not sufficient evidence.
3. Test Your Understanding begins with questions that have a concrete answer in the chapter’s model, then broadens into performance and production-design prompts. For an open-ended prompt, state the workload and system assumptions before defending a tradeoff.
4. End-of-week self-checks provide small integrated scenarios with collapsed answer criteria. Use them as calibration after answering the chapter questions, not as an implementation recipe.

Questions that require an external API detail or paper should link the relevant primary source. If a question still seems underspecified, identify the missing assumption instead of guessing a universal answer.

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.