Skip to content
jimmy-broPublic

About

A tutorial about how to build LSM-Tree storage engine by Golang

Resources

Stars

44 stars

Watchers

1 watching

Forks

Latest commit

 

History

20 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

mini-lsm

A tutorial about how to build LSM-Tree storage engine

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

Tutorial

The tutorial is available at https://jimmy-bro.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

If you changed public API in the reference solution, you might also need to synchronize it to the starter crate.

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.

About

A tutorial about how to build LSM-Tree storage engine by Golang

Resources

Stars

44 stars

Watchers

1 watching

Forks

Releases

Packages

Used by

Contributors

Languages