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        let mut used = false;
91        for seq in meta.obsolete_sst_files() {
92            if let Entry::Occupied(e) = self.0.entry(*seq) {
93                if matches!(e.get(), SstState::Obsolete) {
94                    // This obsolete sst entry was used, so we need to keep the meta file.
95                    used = true;
96                }
97                // Only the first obsolete sst entry is needed, so we can clear this flag, so
98                // that following meta files won't see it as used anymore.
99                e.remove();
100            }
101        }
102
103        !used && !meta.has_active_entries()
104    }
105}
106
107impl Default for SstFilter {
108    fn default() -> Self {
109        Self::new()
110    }
111}
turbo_persistence/sst_filter.rs

turbo_persistence/
sst_filter.rs
