A simple tired compacting Log-Structured Merge Tree(LSM Tree) Ruby implementation which is inspired by cs265-lsm-tree.
LSM::LSMTree#put
is for writing key value pair into DB.
LSM::LSMTree#get
is for query key into DB.
Entry will be inserted into memtable first if the memtable is not full.
When the memtable is full, if we want to insert one more entry, DB will write the memtable to disk.
If level 0 is full, when we want to add one more sstable in level 0, DB will merge all level0's sstables into a big sstable, then the big sstable will be written into level 1.
This demo can be generated by the ./bin/demo
script.
Basic implementation.
- Crash Recovery
- Benchmark and Optimization
- use skip list/AVL tree for Memtable
- mmap
- paralle
- read disk ahead
- ...
- Leveled Compaction Strategy