Build your own toy LSM Tree in Rust.

This library implements a toy LSM Tree implementation

Part of rootconf-25 workshop.

Link to slides: https://gamma.app/docs/Build-your-own-LSM-Tree-in-Rust-o76zgbwlwsd10nv?mode=present#card-8jgga5spmbcqxok

Getting started

• Clone this repository

git clone git@github.com:creativcoder/rootconf-25-lsmtree.git

There are 4 phases for this implementation, each phase and it's solution/fix is marked in git commits with tags. To show the available git tags in the repository, run:

git tag

Here are the following phases of implementation:

• Git tag phase1 - where we build our in-memory LSM Tree.
• Git tag phase2 - where we flush our in-memory data to disk as SSTables.
• Git tag phase3 - where we add support to read from SSTables and also recover older sstable files on restart.
• Git tag phase4 - where we add support for SSTable compactions.

Each phase has a few tests you need to make them pass to mark it as fixed.

Each phase above also contains a git tag phase1_fix that contains a fix to the exercises/todos in the code. If you cannot get past the exercises at a given phase, feel free to checkout the subsequent phases or the fix for that phase using git checkout <tag name>.

To check the final version of the code and run tests: git checkout phase4_fix and run: cargo test -- --test-threads=1 (test-threads flag is required to ensure they run in sequence)

Development environment setup

Install rust compiler toolchain from: https://rustup.rs

Install rust analyzer (language server protocol) on your IDE: https://rust-analyzer.github.io/

If you are on Ubuntu, and on a fresh box, don't forget to run: sudo apt-get install build-essential.

Further resources on LSM Tree:

Academic paper and foundations:

The original LSM tree paper: "The Log-Structured Merge-Tree" by Patrick O'Neil et al. https://www.cs.umb.edu/~poneil/lsmtree.pdf

Books:

Database internals: https://www.goodreads.com/book/show/44647144-database-internals

Blog posts:

What is a lsm tree: https://www.creativcoder.dev/blog/what-is-a-lsm-tree

Wiki:

RocksDB wiki: https://github.com/facebook/rocksdb/wiki/RocksDB-Overview

Implementation guides:

Mini LSM - https://skyzh.github.io/mini-lsm/