Skip to content

Latest commit

 

History

History
76 lines (54 loc) · 2.02 KB

README.md

File metadata and controls

76 lines (54 loc) · 2.02 KB
Raw

Mini LSM in Kotlin

⭐️⭐️ Note that this is not production ready yet ⭐️⭐

LSM database written in kotlin. Inspired by mini-lsm which is implemented in Rust.

Table of Contents

Cli

Requirements

  • Use java 21

How to start

# build jar 
$ ./gradlew :cli:build

# run cli application 
$ java -jar cli/build/libs/cli.jar

Examples

# put key value  
$ put <key> <value>  

# get key  
$ get <key>

# delete key 
$ delete <key> 

# force freeze memtable  
$ freeze 

# force flush memtable, note that this command only flushes the earliest memtable only 
$ flush

What is LSM?

Reference

LSM or LSM tree is a data structure that efficiently stores key-value pairs for retrieval in disk or flash based storage systems.Log structured merge trees optimize both read and write operations using a combination of in-memory and disk-based structures.

Characteristics

  • Organize data into multiple levels, with a sequence of increasingly larger, sorted components.
    • In-memory
      • Memtable: an in memory write buffer
    • Disk based storage
      • Level 0 sorted runs(SSTables): Memtables are periodically flushed to disk as sorted string tables( SSTables) in level 0.
  • Merge process periodically merges data for faster lookups and efficient write operations.
  • Ideal for write operations and write heavy workloads.

Related Keywords

  • Memtable: In memory write buffer.
  • SSTable(Sorted String Table): Immutable data structure created when memtables are flushed to disk(or multiple SSTables can be merged into a new SSTable).
  • Bloom filter: A probabilistic data structure used to check whether specified data exist in the system.