Crate lsm_engine

A rust implementation of a key-value store using Log Structured Merge Trees

Example Usage

use lsm_engine::{LSMEngine, LSMBuilder} ;
fn main() -> Result<(), Box< dyn std::error::Error>> {

  let mut lsm = LSMBuilder::new().
        persist_data(false).
       segment_size(2).
       inmemory_capacity(1).
       sparse_offset(2).
       build();

   lsm.write("k1".to_owned(), "v1".to_owned())?;
   lsm.write("k2".to_owned(), "k2".to_owned())?;
   lsm.write("k1".to_owned(), "v_1_1".to_owned())?;
   let value = lsm.read("k1")?;
   assert_eq!(value, Some("v_1_1".to_owned()));
   Ok(())
}

Design

lsm_engine is an embedded key-value store that uses LSM-trees and leverages a Write-Ahead log (WAL) file for data recovery.

The basic architecture is illustrated below:

Write

When a write comes in, the following happens:

• The entry is written into the WAL file (unless an explicit request is made not to)
• If the size of the internal is at full capacity, the contents are dumped into a segment file, with compaction performed in the end.
• The entry is then inserted into the now-empty memtable.

Read

When a request for a read is made, the following happens:

• It first checks its internal memtable for the value corresponding to the requested key. If it exists, it returns the value
• Otherwise, it looks up the offset of the closest key with its sparse memory index. This is a balanced tree that maintains the position of 1 out of every sparse_offset entries in memeory.
• It then linearly scans forward from that offset, looking for the desired key-value entry.

Delete

This is just a special case of write, with value being a special tombstone string. For more details with visual illustrations, check out this blog post

Structs

LSMBuilder
LSMEngine

Enums

Error

Type Definitions

Result