LSM in a Week

Build a simple key-value storage engine in a week!

Tutorial

The tutorial is available at https://skyzh.github.io/mini-lsm. You can use the provided starter code to kick off your project, and follow the tutorial to implement the LSM tree.

Development

cargo x install-tools
cargo x check
cargo x book

If you changed public API in the reference solution, you might also need to synchronize it to the starter crate. To do this, use cargo x sync.

Progress

The tutorial has 8 parts (which can be finished 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.

We have reference solution up to day 4 and tutorial up to day 4 for now.

LLVM tutorial in Rust language

Status Everything works. State corresponds to the Chapter 7 of the original tutorial (i.e. mutable variables implemented). TODO list. LLVM tutorial in

944 Dec 28, 2022

A comprehensive and FREE Online Rust hacking tutorial utilizing the x64, ARM64 and ARM32 architectures going step-by-step into the world of reverse engineering Rust from scratch.

FREE Reverse Engineering Self-Study Course HERE Hacking Rust A comprehensive and FREE Online Rust hacking tutorial utilizing the x64, ARM64 and ARM32

98 Jun 21, 2023

High concurrency, RealTime, In-memory storage inspired by erlang mnesia

DarkBird is a Document oriented, high concurrency in-memory Storage, also persist data to disk to avoid loss any data The darkbird provides the follow

25 Dec 15, 2022

A HashMap/Vector hybrid: efficient, ordered key-value data storage in Rust.

hashvec A HashVec is a hash map / dictionary whose key-value pairs are stored (and can be iterated over) in a fixed order, by default the order in whi

2 May 16, 2022

A simple local storage media library manager.

OFFFLIX A simple application to auto manage series on your local storage. Features Resume watching Play next episode Auto increment season Play random

33 Mar 7, 2023

Manas project aims to create a modular framework and ecosystem to create robust storage servers adhering to Solid protocol in rust.

मनस् | Manas Solid is a web native protocol to enable interoperable, read-write, collaborative, and decentralized web, truer to web's original vision.

17 Oct 5, 2023

Comments

no such command: `nextest`

I got an error when using cargo x scheck to check the style and run all test cases according to Tutorial:

cargo fmt
cargo check
    Finished dev [unoptimized + debuginfo] target(s) in 0.04s
cargo nextest run
error: no such command: `nextest`

        Did you mean `test`?

        View all installed commands with `cargo --list`
Error: command ["cargo", "nextest", "run"] exited with code 101

after I replace nextest with test in test(), only style checking works, no test cases run.

opened by rien7 1