Tired LSM Tree

A simple tired compacting Log-Structured Merge Tree(LSM Tree) Ruby implementation which is inspired by cs265-lsm-tree.

Data Structures

Operations

LSM::LSMTree#put is for writing key value pair into DB.

LSM::LSMTree#get is for query key into DB.

Demo

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.

Status

Current Status

Basic implementation.

Future Plan

• Crash Recovery
• Benchmark and Optimization
  • use skip list/AVL tree for Memtable
  • mmap
  • paralle
  • read disk ahead
  • ...
• Leveled Compaction Strategy