lsm_tree/compaction/leveled/
primitives.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (c) 2026-present, Dmitry Prudnikov
3
4//! The four choices a compaction strategy makes for each level, each set on
5//! its own.
6//!
7//! Every compaction strategy answers four questions per level (Sarkar et al.,
8//! "Constructing and Analyzing the LSM Compaction Design Space", PVLDB 14(11)):
9//! when the level compacts (its [`Trigger`]), how its data lies (its
10//! [`Layout`]: one run, or runs that accumulate), how much one compaction out
11//! of it takes (its [`Granularity`]), and which data that is (its
12//! [`Movement`]). No combination is best for every workload, so each is a
13//! setting of its own. The leveled defaults are one combination of them.
14
15/// When a level compacts.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum Trigger {
18    /// When its runs reach `runs`, or its tables reach `tables`: a level of
19    /// runs that accumulate, read once per run, compacts by its shape.
20    ///
21    /// Runs are counted as a read meets them: tables that overlap no table of
22    /// a run join it, so batches of disjoint keys make one run, read once.
23    /// `tables` is what bounds such a level's size.
24    Shape {
25        /// The run count that triggers it.
26        runs: u8,
27        /// The table count that triggers it whatever the run count.
28        tables: u16,
29    },
30    /// When its bytes pass the target the level's place in the tree gives
31    /// it, by how far past.
32    Size,
33    /// Never on its own: the level only receives compactions. It takes no
34    /// free move either, into the level below or into the last.
35    Never,
36}
37
38/// How a level holds its data.
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
40pub enum Layout {
41    /// One run: a compaction into the level merges with the tables of it
42    /// that it overlaps.
43    Leveled,
44    /// Runs that accumulate: a compaction into the level takes in nothing of
45    /// it and writes its output beside the runs there. Output overlapping no
46    /// table of a run joins that run, as any level below L0 lays its tables
47    /// out: a read visits disjoint tables once, whichever run holds them.
48    Tiered,
49}
50
51/// How much one compaction out of a level takes.
52#[derive(Clone, Copy, Debug, PartialEq, Eq)]
53pub enum Granularity {
54    /// Every table of the level. With `through_full_next`, when the level it
55    /// compacts into is past its own target, that level goes along into the
56    /// one below it, so its bytes are not written twice in a row.
57    Level {
58        /// Whether a level past its target is compacted through.
59        through_full_next: bool,
60    },
61    /// The tables of the level a window of the next level's tables
62    /// contains, the window chosen by the level's [`Movement`].
63    Window,
64}
65
66/// Which data a compaction out of a level takes, when it takes part of it.
67#[derive(Clone, Copy, Debug, PartialEq, Eq)]
68pub enum Movement {
69    /// The window that rewrites least per byte it moves down, among those
70    /// that move no more than the level's overshoot plus `slack` bytes;
71    /// `None` = one table target.
72    LeastRewrite {
73        /// The bytes past the overshoot a window may move and still be
74        /// preferred.
75        slack: Option<u64>,
76    },
77    /// The window whose tables were read the most per byte rewritten: the
78    /// data reads touch is compacted first, and a cold range is left as it
79    /// is. Ties fall to the least rewrite, as [`Self::LeastRewrite`] ranks.
80    Hottest,
81}
82
83/// The four choices for one level.
84#[derive(Clone, Copy, Debug, PartialEq, Eq)]
85pub struct LevelPolicy {
86    /// When the level compacts.
87    pub trigger: Trigger,
88    /// How it holds its data.
89    pub layout: Layout,
90    /// How much one compaction out of it takes.
91    pub granularity: Granularity,
92    /// Which data that is.
93    pub movement: Movement,
94}
lsm_tree/compaction/leveled/primitives.rs

lsm_tree/compaction/leveled/
primitives.rs
