subms-lsm-tree 0.8.1

submillisecond.com cookbook recipe - storage: subms-lsm-tree. A working LSM tree (memtable, immutable SSTables, bloom-filter trailer) with sub-millisecond reads at p99 on a 50k-entry workload.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use super::*;

fn run(id: u64, kvs: &[(&str, Option<&[u8]>)]) -> TieredRun {
    TieredRun::new(
        id,
        kvs.iter()
            .map(|(k, v)| (k.to_string(), v.map(|b| b.to_vec())))
            .collect(),
    )
}

#[test]
fn pick_level_finds_full_level() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("a", Some(b"1"))]));
    m.push(0, run(2, &[("b", Some(b"2"))]));
    m.push(0, run(3, &[("c", Some(b"3"))]));
    let planner = TieredCompactionPlanner::new(3);
    assert_eq!(planner.pick_level(&m), Some(0));
}

#[test]
fn pick_level_returns_none_when_no_level_full() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("a", Some(b"1"))]));
    m.push(1, run(2, &[("b", Some(b"2"))]));
    let planner = TieredCompactionPlanner::new(3);
    assert!(planner.pick_level(&m).is_none());
}

#[test]
fn merge_promotes_to_next_level() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("a", Some(b"1"))]));
    m.push(0, run(2, &[("b", Some(b"2"))]));
    m.push(0, run(3, &[("c", Some(b"3"))]));
    let planner = TieredCompactionPlanner::new(3);
    planner.merge(&mut m, 0, 100);
    assert_eq!(m.level_run_count(0), 0, "level 0 emptied");
    assert_eq!(m.level_run_count(1), 1, "level 1 gained the merged run");
    let merged = &m.levels[1][0];
    assert_eq!(merged.id, 100);
    let keys: Vec<&str> = merged.entries.iter().map(|(k, _)| k.as_str()).collect();
    assert_eq!(keys, vec!["a", "b", "c"]);
}

#[test]
fn newer_run_wins_on_key_collision() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("k", Some(b"old"))]));
    m.push(0, run(2, &[("k", Some(b"new"))]));
    let planner = TieredCompactionPlanner::new(2);
    planner.merge(&mut m, 0, 50);
    let merged = &m.levels[1][0];
    assert_eq!(merged.entries.len(), 1);
    assert_eq!(merged.entries[0].1.as_deref(), Some(&b"new"[..]));
}

#[test]
fn tombstone_is_preserved_in_merge() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("k", Some(b"v"))]));
    m.push(0, run(2, &[("k", None)]));
    let planner = TieredCompactionPlanner::new(2);
    planner.merge(&mut m, 0, 50);
    let merged = &m.levels[1][0];
    assert_eq!(merged.entries.len(), 1);
    assert!(merged.entries[0].1.is_none(), "tombstone wins");
}

#[test]
fn runs_per_level_floor_is_two() {
    let planner = TieredCompactionPlanner::new(0);
    assert_eq!(planner.runs_per_level(), 2);
    let planner = TieredCompactionPlanner::new(1);
    assert_eq!(planner.runs_per_level(), 2);
}

#[test]
fn merge_handles_non_overlapping_keys() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("a", Some(b"1")), ("c", Some(b"3"))]));
    m.push(0, run(2, &[("b", Some(b"2")), ("d", Some(b"4"))]));
    let planner = TieredCompactionPlanner::new(2);
    planner.merge(&mut m, 0, 99);
    let merged = &m.levels[1][0];
    let keys: Vec<&str> = merged.entries.iter().map(|(k, _)| k.as_str()).collect();
    assert_eq!(keys, vec!["a", "b", "c", "d"]);
}

#[test]
fn total_run_count_sums_across_levels() {
    let mut m = TieredManifest::new();
    m.push(0, run(1, &[("a", Some(b"1"))]));
    m.push(0, run(2, &[("b", Some(b"2"))]));
    m.push(1, run(3, &[("c", Some(b"3"))]));
    assert_eq!(m.total_run_count(), 3);
}

#[test]
fn cascading_compaction_via_repeated_pick_and_merge() {
    let mut m = TieredManifest::new();
    for i in 0..4 {
        m.push(0, run(i, &[(&format!("k{i}"), Some(b"v"))]));
    }
    let planner = TieredCompactionPlanner::new(4);
    let lvl = planner.pick_level(&m).unwrap();
    planner.merge(&mut m, lvl, 10);
    assert_eq!(
        planner.pick_level(&m),
        None,
        "single merged run does not trigger again"
    );
    assert_eq!(m.level_run_count(1), 1);
    assert_eq!(m.levels[1][0].entries.len(), 4);
}