lsm_tree/compaction/tiered.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
5use super::{Choice, CompactionStrategy, Input as CompactionInput};
6use crate::{level_manifest::LevelManifest, segment::Segment, Config, HashSet};
7
8fn desired_level_size_in_bytes(level_idx: u8, ratio: u8, base_size: u32) -> usize {
9 (ratio as usize).pow(u32::from(level_idx + 1)) * (base_size as usize)
10}
11
12/// Size-tiered compaction strategy (STCS)
13///
14/// If a level reaches a threshold, it is merged into a larger segment to the next level.
15///
16/// STCS suffers from high read and temporary doubled space amplification, but has good write amplification.
17#[derive(Clone)]
18pub struct Strategy {
19 /// Base size
20 pub base_size: u32,
21
22 /// Size ratio between levels of the LSM tree (a.k.a fanout, growth rate).
23 ///
24 /// This is the exponential growth of the from one
25 /// level to the next
26 ///
27 /// A level target size is: base_size * level_ratio.pow(#level + 1)
28 #[allow(clippy::doc_markdown)]
29 pub level_ratio: u8,
30}
31
32impl Strategy {
33 /// Creates a new STCS strategy with custom base size
34 #[must_use]
35 pub fn new(base_size: u32, level_ratio: u8) -> Self {
36 Self {
37 base_size,
38 level_ratio,
39 }
40 }
41}
42
43impl Default for Strategy {
44 fn default() -> Self {
45 Self {
46 base_size: 64 * 1_024 * 1_024,
47 level_ratio: 4,
48 }
49 }
50}
51
52impl CompactionStrategy for Strategy {
53 fn get_name(&self) -> &'static str {
54 "TieredStrategy"
55 }
56
57 fn choose(&self, levels: &LevelManifest, config: &Config) -> Choice {
58 todo!()
59 }
60}
61/*
62#[cfg(test)]
63mod tests {
64 use super::Strategy;
65 use crate::{
66 cache::Cache,
67 compaction::{Choice, CompactionStrategy, Input as CompactionInput},
68 config::Config,
69 descriptor_table::FileDescriptorTable,
70 file::LEVELS_MANIFEST_FILE,
71 level_manifest::LevelManifest,
72 segment::{
73 block::offset::BlockOffset,
74 block_index::{two_level_index::TwoLevelBlockIndex, BlockIndexImpl},
75 file_offsets::FileOffsets,
76 meta::{Metadata, SegmentId},
77 SegmentInner,
78 },
79 super_segment::Segment,
80 HashSet, KeyRange, SeqNo,
81 };
82 use std::sync::{atomic::AtomicBool, Arc};
83 use test_log::test;
84
85 #[allow(clippy::expect_used)]
86 fn fixture_segment(id: SegmentId, size_mib: u64, max_seqno: SeqNo) -> Segment {
87 todo!()
88
89 /* let cache = Arc::new(Cache::with_capacity_bytes(10 * 1_024 * 1_024));
90
91 let block_index = TwoLevelBlockIndex::new((0, id).into(), cache.clone());
92 let block_index = Arc::new(BlockIndexImpl::TwoLevel(block_index));
93
94 SegmentInner {
95 tree_id: 0,
96 descriptor_table: Arc::new(FileDescriptorTable::new(512, 1)),
97 block_index,
98
99 offsets: FileOffsets {
100 bloom_ptr: BlockOffset(0),
101 range_filter_ptr: BlockOffset(0),
102 index_block_ptr: BlockOffset(0),
103 metadata_ptr: BlockOffset(0),
104 range_tombstones_ptr: BlockOffset(0),
105 tli_ptr: BlockOffset(0),
106 pfx_ptr: BlockOffset(0),
107 },
108
109 metadata: Metadata {
110 data_block_count: 0,
111 index_block_count: 0,
112 data_block_size: 4_096,
113 index_block_size: 4_096,
114 created_at: 0,
115 id,
116 file_size: size_mib * 1_024 * 1_024,
117 compression: crate::segment::meta::CompressionType::None,
118 table_type: crate::segment::meta::TableType::Block,
119 item_count: 0,
120 key_count: 0,
121 key_range: KeyRange::new((vec![].into(), vec![].into())),
122 tombstone_count: 0,
123 range_tombstone_count: 0,
124 uncompressed_size: size_mib * 1_024 * 1_024,
125 seqnos: (0, max_seqno),
126 },
127 cache,
128
129 bloom_filter: Some(BloomFilter::with_fp_rate(1, 0.1)),
130
131 path: "a".into(),
132 is_deleted: AtomicBool::default(),
133 }
134 .into() */
135 }
136
137 #[test]
138 fn tiered_empty_levels() -> crate::Result<()> {
139 let tempdir = tempfile::tempdir()?;
140
141 let compactor = Strategy {
142 base_size: 8 * 1_024 * 1_024,
143 level_ratio: 8,
144 };
145
146 let levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
147
148 assert_eq!(
149 compactor.choose(&levels, &Config::default()),
150 Choice::DoNothing
151 );
152
153 Ok(())
154 }
155
156 #[test]
157 fn tiered_default_l0() -> crate::Result<()> {
158 let tempdir = tempfile::tempdir()?;
159
160 let compactor = Strategy {
161 base_size: 8 * 1_024 * 1_024,
162 level_ratio: 4,
163 };
164 let config = Config::default();
165
166 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
167
168 levels.add(fixture_segment(1, 8, 5));
169 assert_eq!(compactor.choose(&levels, &config), Choice::DoNothing);
170
171 levels.add(fixture_segment(2, 8, 6));
172 assert_eq!(compactor.choose(&levels, &config), Choice::DoNothing);
173
174 levels.add(fixture_segment(3, 8, 7));
175 assert_eq!(compactor.choose(&levels, &config), Choice::DoNothing);
176
177 levels.add(fixture_segment(4, 8, 8));
178
179 assert_eq!(
180 compactor.choose(&levels, &config),
181 Choice::Merge(CompactionInput {
182 dest_level: 1,
183 segment_ids: set![1, 2, 3, 4],
184 target_size: u64::MAX,
185 })
186 );
187
188 Ok(())
189 }
190
191 #[test]
192 fn tiered_ordering() -> crate::Result<()> {
193 let tempdir = tempfile::tempdir()?;
194
195 let compactor = Strategy {
196 base_size: 8 * 1_024 * 1_024,
197 level_ratio: 2,
198 };
199 let config = Config::default();
200
201 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
202
203 levels.add(fixture_segment(1, 8, 0));
204 levels.add(fixture_segment(2, 8, 1));
205 levels.add(fixture_segment(3, 8, 2));
206 levels.add(fixture_segment(4, 8, 3));
207
208 assert_eq!(
209 compactor.choose(&levels, &config),
210 Choice::Merge(CompactionInput {
211 dest_level: 1,
212 segment_ids: set![1, 2],
213 target_size: u64::MAX,
214 })
215 );
216
217 Ok(())
218 }
219
220 #[test]
221 fn tiered_more_than_min() -> crate::Result<()> {
222 let tempdir = tempfile::tempdir()?;
223
224 let compactor = Strategy {
225 base_size: 8 * 1_024 * 1_024,
226 level_ratio: 4,
227 };
228 let config = Config::default();
229
230 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
231 levels.add(fixture_segment(1, 8, 5));
232 levels.add(fixture_segment(2, 8, 6));
233 levels.add(fixture_segment(3, 8, 7));
234 levels.add(fixture_segment(4, 8, 8));
235
236 levels.insert_into_level(1, fixture_segment(5, 8 * 4, 9));
237 levels.insert_into_level(1, fixture_segment(6, 8 * 4, 10));
238 levels.insert_into_level(1, fixture_segment(7, 8 * 4, 11));
239 levels.insert_into_level(1, fixture_segment(8, 8 * 4, 12));
240
241 assert_eq!(
242 compactor.choose(&levels, &config),
243 Choice::Merge(CompactionInput {
244 dest_level: 2,
245 segment_ids: set![5, 6, 7, 8],
246 target_size: u64::MAX,
247 })
248 );
249
250 Ok(())
251 }
252
253 #[test]
254 fn tiered_many_segments() -> crate::Result<()> {
255 let tempdir = tempfile::tempdir()?;
256
257 let compactor = Strategy {
258 base_size: 8 * 1_024 * 1_024,
259 level_ratio: 2,
260 };
261 let config = Config::default();
262
263 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
264 levels.add(fixture_segment(1, 8, 5));
265 levels.add(fixture_segment(2, 8, 6));
266 levels.add(fixture_segment(3, 8, 7));
267 levels.add(fixture_segment(4, 8, 8));
268
269 assert_eq!(
270 compactor.choose(&levels, &config),
271 Choice::Merge(CompactionInput {
272 dest_level: 1,
273 segment_ids: set![1, 2],
274 target_size: u64::MAX,
275 })
276 );
277
278 Ok(())
279 }
280
281 #[test]
282 fn tiered_deeper_level() -> crate::Result<()> {
283 let tempdir = tempfile::tempdir()?;
284
285 let compactor = Strategy {
286 base_size: 8 * 1_024 * 1_024,
287 level_ratio: 2,
288 };
289 let config = Config::default();
290
291 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
292 levels.add(fixture_segment(1, 8, 5));
293
294 levels.insert_into_level(1, fixture_segment(2, 8 * 2, 6));
295 levels.insert_into_level(1, fixture_segment(3, 8 * 2, 7));
296
297 assert_eq!(
298 compactor.choose(&levels, &config),
299 Choice::Merge(CompactionInput {
300 dest_level: 2,
301 segment_ids: set![2, 3],
302 target_size: u64::MAX,
303 })
304 );
305
306 let tempdir = tempfile::tempdir()?;
307 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
308
309 levels.insert_into_level(2, fixture_segment(2, 8 * 4, 5));
310 levels.insert_into_level(2, fixture_segment(3, 8 * 4, 6));
311
312 assert_eq!(
313 compactor.choose(&levels, &config),
314 Choice::Merge(CompactionInput {
315 dest_level: 3,
316 segment_ids: set![2, 3],
317 target_size: u64::MAX,
318 })
319 );
320
321 Ok(())
322 }
323
324 #[test]
325 fn tiered_last_level() -> crate::Result<()> {
326 let tempdir = tempfile::tempdir()?;
327
328 let compactor = Strategy {
329 base_size: 8 * 1_024 * 1_024,
330 level_ratio: 2,
331 };
332 let config = Config::default();
333
334 let mut levels = LevelManifest::create_new(4, tempdir.path().join(LEVELS_MANIFEST_FILE))?;
335 levels.insert_into_level(3, fixture_segment(2, 8, 5));
336 levels.insert_into_level(3, fixture_segment(3, 8, 5));
337
338 assert_eq!(compactor.choose(&levels, &config), Choice::DoNothing);
339
340 Ok(())
341 }
342}
343 */