[−][src]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). // don't create a "write-ahead log" segment_size(2000). // each sst file will have up to 2000 entries inmemory_capacity(100). //store only 100 entries in memory sparse_offset(20). //store one out of every 20 entries written into segments in memory build(); let default_lsm = LSMBuilder::new().build(); //an lsm engine with default parameters 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 |