Line data Source code
1 : use std::collections::BTreeSet;
2 :
3 : use itertools::Itertools;
4 : use pageserver_compaction::helpers::overlaps_with;
5 :
6 : use super::storage_layer::LayerName;
7 :
8 : /// Checks whether a layer map is valid (i.e., is a valid result of the current compaction algorithm if nothing goes wrong).
9 : ///
10 : /// The function implements a fast path check and a slow path check.
11 : ///
12 : /// The fast path checks if we can split the LSN range of a delta layer only at the LSNs of the delta layers. For example,
13 : ///
14 : /// ```plain
15 : /// | | | |
16 : /// | 1 | | 2 | | 3 |
17 : /// | | | | | |
18 : /// ```
19 : ///
20 : /// This is not a valid layer map because the LSN range of layer 1 intersects with the LSN range of layer 2. 1 and 2 should have
21 : /// the same LSN range.
22 : ///
23 : /// The exception is that when layer 2 only contains a single key, it could be split over the LSN range. For example,
24 : ///
25 : /// ```plain
26 : /// | | | 2 | | |
27 : /// | 1 | |-------| | 3 |
28 : /// | | | 4 | | |
29 : ///
30 : /// If layer 2 and 4 contain the same single key, this is also a valid layer map.
31 : ///
32 : /// However, if a partial compaction is still going on, it is possible that we get a layer map not satisfying the above condition.
33 : /// Therefore, we fallback to simply check if any of the two delta layers overlap. (See "A slow path...")
34 292 : pub fn check_valid_layermap(metadata: &[LayerName]) -> Option<String> {
35 292 : let mut lsn_split_point = BTreeSet::new(); // TODO: use a better data structure (range tree / range set?)
36 292 : let mut all_delta_layers = Vec::new();
37 1308 : for name in metadata {
38 1016 : if let LayerName::Delta(layer) = name {
39 524 : all_delta_layers.push(layer.clone());
40 524 : }
41 : }
42 816 : for layer in &all_delta_layers {
43 524 : if layer.key_range.start.next() != layer.key_range.end {
44 360 : let lsn_range = &layer.lsn_range;
45 360 : lsn_split_point.insert(lsn_range.start);
46 360 : lsn_split_point.insert(lsn_range.end);
47 360 : }
48 : }
49 524 : for (idx, layer) in all_delta_layers.iter().enumerate() {
50 524 : if layer.key_range.start.next() == layer.key_range.end {
51 164 : continue;
52 360 : }
53 360 : let lsn_range = layer.lsn_range.clone();
54 360 : let intersects = lsn_split_point.range(lsn_range).collect_vec();
55 360 : if intersects.len() > 1 {
56 : // A slow path to check if the layer intersects with any other delta layer.
57 0 : for (other_idx, other_layer) in all_delta_layers.iter().enumerate() {
58 0 : if other_idx == idx {
59 : // do not check self intersects with self
60 0 : continue;
61 0 : }
62 0 : if overlaps_with(&layer.lsn_range, &other_layer.lsn_range)
63 0 : && overlaps_with(&layer.key_range, &other_layer.key_range)
64 : {
65 0 : let err = format!(
66 0 : "layer violates the layer map LSN split assumption: layer {} intersects with layer {}",
67 0 : layer, other_layer
68 0 : );
69 0 : return Some(err);
70 0 : }
71 : }
72 360 : }
73 : }
74 292 : None
75 292 : }
|