tessarikv 0.1.0

A pure-Rust, lock-free-first LSM key-value storage engine
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

//! The steps a range request takes over given levels.

use super::super::pick::Busy;
use super::super::pick_tests::{SHAPE, ids, levels, table};
use super::{Active, Request, Step};
use crate::CompactionStyle;

fn request(start: &[u8], end: Option<&[u8]>, fresh_from: u64) -> Active {
    let (request, _) = Request::new(0, start, end);
    Active::new(request, fresh_from)
}

/// Level 0 is newer than every level below it: it lands at the first level holding data when
/// that is above the base level, never below it.
#[test]
fn level_zero_lands_no_lower_than_the_first_level_holding_data() {
    let tables = levels(vec![
        table(9, 0, b"a", b"z", 10),
        table(5, 3, b"a", b"m", 1000),
        table(1, 6, b"a", b"z", 10_000),
    ]);
    let active = request(b"", None, 10);
    let Step::Run(pick, next) =
        active.next(&tables, CompactionStyle::Leveled, SHAPE, &Busy::default())
    else {
        panic!("level 0 touches the range");
    };
    assert_eq!((pick.output_level, next), (3, 3));
    assert_eq!((ids(&pick.inputs), ids(&pick.overlaps)), (vec![9], vec![5]));
}

/// The bottom tables a range touches are rewritten in place, one table included, unless they
/// were written after the request began; tables outside the range stay.
#[test]
fn bottom_tables_in_the_range_are_rewritten_in_place() {
    let tables = levels(vec![
        table(1, 6, b"a", b"c", 100),
        table(2, 6, b"d", b"f", 100),
        table(7, 6, b"g", b"i", 100),
    ]);
    let active = request(b"b", Some(b"e"), 5);
    let Step::Run(pick, _) =
        active.next(&tables, CompactionStyle::Leveled, SHAPE, &Busy::default())
    else {
        panic!("bottom tables touch the range");
    };
    assert_eq!((pick.output_level, ids(&pick.inputs)), (6, vec![1, 2]));
    let one = request(b"a", Some(b"b"), 5);
    let Step::Run(single, _) = one.next(&tables, CompactionStyle::Leveled, SHAPE, &Busy::default())
    else {
        panic!("one bottom table touches the range");
    };
    assert!(
        !single.is_move(),
        "a table rewritten in its level is not a move"
    );
    let fresh = request(b"g", None, 5);
    assert!(matches!(
        fresh.next(&tables, CompactionStyle::Leveled, SHAPE, &Busy::default()),
        Step::Done
    ));
}

/// A step whose tables a running compaction holds waits.
#[test]
fn a_step_waits_while_its_tables_are_busy() {
    let tables = levels(vec![table(1, 6, b"a", b"c", 100)]);
    let busy = Busy {
        tables: vec![1],
        ranges: Vec::new(),
    };
    let active = request(b"", None, 5);
    assert!(matches!(
        active.next(&tables, CompactionStyle::Leveled, SHAPE, &busy),
        Step::Blocked
    ));
}