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 : }