lsm_engine

一个使用日志结构合并树和利用预写日志 (WAL) 进行数据恢复的关键值存储的Rust实现。

安装

[dependencies]
lsm_engine = "*"

文档

https://docs.rs/lsm_engine/0.1.1/lsm_engine/

lib.rs:

使用日志结构合并树的Rust实现

示例用法

use lsm_engine::{LSMEngine, LSMBuilder} ;
use std::fs::File;


fn main() -> Result<(), Box< dyn std::error::Error>> {

  let mut lsm = LSMBuilder::new().
       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
       wal_path("my_write_ahead_log.txt"). //path
       build();

  let mut default_lsm = LSMBuilder::new().build(); //an lsm engine with default parameters

  let dataset = vec![("k1", "v1"), ("k2", "v2"), ("k1", "v_1_1")];

  for (k, v) in dataset.iter() {
       lsm.write(String::from(*k), String::from(*v));
   }
   assert_eq!(lsm.read("k1")?, Some("v_1_1".to_owned()));


   let mut wal  = File::open("my_write_ahead_log.txt")?;
   default_lsm.recover_from(wal)?;
   for (k, v) in dataset {
       assert!(default_lsm.contains(k)?);
   }

   //cleanup
  std::fs::remove_file("my_write_ahead_log.txt")?;




   Ok(())
}

设计

lsm_engine是一个嵌入式的键值存储，使用LSM树并利用预写日志 (WAL) 文件进行数据恢复。

基本架构如下所示

写入

当写入数据时，以下是所发生的过程

• 条目被写入WAL文件（除非明确请求不写入）
• 如果内部大小达到满容量，则内容会被转储到段文件中，并在最后进行压缩。
• 然后将条目插入到现在的空memtable中。

读取

当请求读取时，以下是所发生的过程

• 它首先检查其内部memtable以找到与请求的键相对应的值。如果存在，则返回该值
• 否则，它通过其稀疏内存索引查找最近键的偏移量。这是一个平衡树，维护内存中每sparse_offset个条目的位置。
• 然后从该偏移量开始线性扫描，寻找所需的键值条目。

删除

这只是一个特殊的写入情况，值是一个特殊的墓碑字符串。更多详细信息和视觉说明，请查看这篇博客文章