lsm_tree/compaction/
mod.rs

1// Copyright (c) 2024-present, fjall-rs
2// This source code is licensed under both the Apache 2.0 and MIT License
3// (found in the LICENSE-* files in the repository)
4
5//! Contains compaction strategies
6
7pub(crate) mod fifo;
8pub(crate) mod leveled;
9// pub(crate) mod maintenance;
10pub(crate) mod drop_range;
11pub mod filter;
12mod flavour;
13pub(crate) mod major;
14pub(crate) mod movedown;
15pub(crate) mod pulldown;
16pub(crate) mod state;
17pub(crate) mod stream;
18pub(crate) mod tiered;
19pub(crate) mod worker;
20
21pub use fifo::Strategy as Fifo;
22pub use filter::{CompactionFilter, Factory, ItemAccessor, Verdict};
23pub use leveled::Strategy as Leveled;
24pub use tiered::Strategy as SizeTiered;
25
26pub use {
27    fifo::NAME as FIFO_COMPACTION_NAME, leveled::NAME as LEVELED_COMPACTION_NAME,
28    tiered::NAME as TIERED_COMPACTION_NAME,
29};
30
31/// Alias for `Leveled`
32pub type Levelled = Leveled;
33
34#[doc(hidden)]
35pub use movedown::Strategy as MoveDown;
36
37#[doc(hidden)]
38pub use pulldown::Strategy as PullDown;
39
40use crate::{
41    compaction::state::CompactionState, config::Config, version::Version, HashSet, KvPair, TableId,
42};
43
44/// The action taken during a compaction run.
45#[derive(Debug, Clone, Copy, PartialEq, Eq)]
46pub enum CompactionAction {
47    /// Strategy chose to do nothing.
48    Nothing,
49
50    /// Tables were merged (rewritten) into a destination level.
51    Merged,
52
53    /// Tables were moved to a deeper level without rewriting.
54    Moved,
55
56    /// Tables were dropped without compaction.
57    Dropped,
58}
59
60/// Result of a compaction operation, describing what happened.
61///
62/// Returned by [`crate::AbstractTree::compact`] to give callers
63/// observability into which compaction path was taken.
64#[derive(Debug, Clone, PartialEq, Eq)]
65pub struct CompactionResult {
66    /// The action that was taken.
67    pub action: CompactionAction,
68
69    /// The destination level, if applicable.
70    pub dest_level: Option<u8>,
71
72    /// Number of input tables consumed.
73    pub tables_in: usize,
74
75    /// Number of output tables produced.
76    pub tables_out: usize,
77}
78
79impl CompactionResult {
80    /// Creates a result for the "do nothing" case.
81    #[must_use]
82    pub fn nothing() -> Self {
83        Self {
84            action: CompactionAction::Nothing,
85            dest_level: None,
86            tables_in: 0,
87            tables_out: 0,
88        }
89    }
90}
91
92/// Input for compactor
93///
94/// The compaction strategy chooses which tables to compact and how.
95/// That information is given to the compactor.
96#[derive(Debug, Eq, PartialEq)]
97pub struct Input {
98    /// Tables to compact
99    pub table_ids: HashSet<TableId>,
100
101    /// Level to put the created tables into
102    pub dest_level: u8,
103
104    /// The logical level the tables are part of
105    pub canonical_level: u8,
106
107    /// Table target size
108    ///
109    /// If a table merge reaches the size threshold, a new table is started.
110    /// This results in a sorted "run" of tables.
111    pub target_size: u64,
112}
113
114/// Describes what to do (compact or not)
115#[derive(Debug, Eq, PartialEq)]
116pub enum Choice {
117    /// Just do nothing.
118    DoNothing,
119
120    /// Moves tables into another level without rewriting.
121    Move(Input),
122
123    /// Compacts some tables into a new level.
124    Merge(Input),
125
126    /// Delete tables without doing compaction.
127    ///
128    /// This may be used by a compaction strategy that wants to delete old data
129    /// without having to compact it away, like [`fifo::Strategy`].
130    Drop(HashSet<TableId>),
131}
132
133/// Trait for a compaction strategy
134///
135/// The strategy receives the levels of the LSM-tree as argument
136/// and emits a choice on what to do.
137#[expect(clippy::module_name_repetitions)]
138pub trait CompactionStrategy {
139    /// Gets the compaction strategy name.
140    fn get_name(&self) -> &'static str;
141
142    #[doc(hidden)]
143    fn get_config(&self) -> Vec<KvPair> {
144        vec![]
145    }
146
147    /// Decides on what to do based on the current state of the LSM-tree's levels
148    fn choose(&self, version: &Version, config: &Config, state: &CompactionState) -> Choice;
149}
lsm_tree/compaction/mod.rs

lsm_tree/compaction/
mod.rs
