turbo_persistence/
sst_filter.rs

1use std::collections::hash_map::Entry;
2
3use rustc_hash::{FxHashMap, FxHashSet};
4
5use crate::meta_file::MetaFile;
6
7enum SstState {
8    Active,
9    UnusedObsolete,
10    Obsolete,
11}
12
13pub struct SstFilter(FxHashMap<u32, SstState>);
14
15impl SstFilter {
16    pub fn new() -> Self {
17        Self(FxHashMap::default())
18    }
19
20    /// Phase 1: Apply the filter to the meta file and update the state in the filter.
21    pub fn apply_filter(&mut self, meta: &mut MetaFile) {
22        // Already obsolete entries need to be considered for usage computation
23        for seq in meta.obsolete_entries() {
24            if let Some(state) = self.0.get_mut(seq)
25                && matches!(state, SstState::UnusedObsolete)
26            {
27                // the obsolete state is used now
28                *state = SstState::Obsolete;
29            }
30        }
31        meta.retain_entries(|seq| match self.0.entry(seq) {
32            Entry::Occupied(mut e) => {
33                let state = e.get_mut();
34                if matches!(state, SstState::UnusedObsolete) {
35                    // the obsolete state is used now
36                    *state = SstState::Obsolete;
37                }
38                false
39            }
40            Entry::Vacant(e) => {
41                e.insert(SstState::Active);
42                true
43            }
44        });
45        for seq in meta.obsolete_sst_files() {
46            self.0.entry(*seq).or_insert(SstState::UnusedObsolete);
47        }
48    }
49
50    /// Like [`apply_filter`](Self::apply_filter) but only updates the filter state without
51    /// modifying the MetaFile. Returns the set of SST sequence numbers that should be removed
52    /// from this meta file's entries (they are superseded by a newer meta). Call
53    /// `meta.retain_entries(|seq| !obsolete.contains(&seq))` later to apply.
54    pub fn apply_filter_collect(&mut self, meta: &MetaFile) -> FxHashSet<u32> {
55        let mut to_remove = FxHashSet::default();
56        // Already obsolete entries need to be considered for usage computation
57        for seq in meta.obsolete_entries() {
58            if let Some(state) = self.0.get_mut(seq)
59                && matches!(state, SstState::UnusedObsolete)
60            {
61                // the obsolete state is used now
62                *state = SstState::Obsolete;
63            }
64        }
65        for entry in meta.entries() {
66            let seq = entry.sequence_number();
67            match self.0.entry(seq) {
68                Entry::Occupied(mut e) => {
69                    let state = e.get_mut();
70                    if matches!(state, SstState::UnusedObsolete) {
71                        *state = SstState::Obsolete;
72                    }
73                    to_remove.insert(seq);
74                }
75                Entry::Vacant(e) => {
76                    e.insert(SstState::Active);
77                }
78            }
79        }
80        for seq in meta.obsolete_sst_files() {
81            self.0.entry(*seq).or_insert(SstState::UnusedObsolete);
82        }
83        to_remove
84    }
85
86    /// Phase 2: Check if the meta file can be removed based on the filter state after phase 1.
87    /// Updates the filter state for the next meta file. Returns true if the meta file can be
88    /// removed.
89    pub fn apply_and_get_remove(&mut self, meta: &MetaFile) -> bool {
90        self.apply_and_get_remove_after_removing(meta, &FxHashSet::default())
91    }
92
93    /// Like [`apply_and_get_remove`](Self::apply_and_get_remove), but treats entries in
94    /// `entries_to_remove` as already removed. Commit uses this while its in-memory mutations are
95    /// deferred until after `CURRENT` is durable, so a newly-subsumed meta file can be retired in
96    /// the same commit.
97    pub fn apply_and_get_remove_after_removing(
98        &mut self,
99        meta: &MetaFile,
100        entries_to_remove: &FxHashSet<u32>,
101    ) -> bool {
102        let mut used = false;
103        for seq in meta.obsolete_sst_files() {
104            if let Entry::Occupied(e) = self.0.entry(*seq) {
105                if matches!(e.get(), SstState::Obsolete) {
106                    // This obsolete sst entry was used, so we need to keep the meta file.
107                    used = true;
108                }
109                // Only the first obsolete sst entry is needed, so we can clear this flag, so
110                // that following meta files won't see it as used anymore.
111                e.remove();
112            }
113        }
114
115        !used
116            && !meta
117                .entries()
118                .iter()
119                .any(|entry| !entries_to_remove.contains(&entry.sequence_number()))
120    }
121}
122
123impl Default for SstFilter {
124    fn default() -> Self {
125        Self::new()
126    }
127}
turbo_persistence/sst_filter.rs

turbo_persistence/
sst_filter.rs
