LCOV - code coverage report
Current view: top level - pageserver/src/tenant/layer_map - historic_layer_coverage.rs (source / functions) Coverage Total Hit
Test: 07bee600374ccd486c69370d0972d9035964fe68.info Lines: 96.6 % 470 454
Test Date: 2025-02-20 13:11:02 Functions: 91.9 % 37 34

            Line data    Source code
       1              : use std::collections::BTreeMap;
       2              : use std::ops::Range;
       3              : 
       4              : use tracing::info;
       5              : 
       6              : use crate::tenant::storage_layer::PersistentLayerDesc;
       7              : 
       8              : use super::layer_coverage::LayerCoverageTuple;
       9              : 
      10              : /// Layers in this module are identified and indexed by this data.
      11              : ///
      12              : /// This is a helper struct to enable sorting layers by lsn.start.
      13              : ///
      14              : /// These three values are enough to uniquely identify a layer, since
      15              : /// a layer is obligated to contain all contents within range, so two
      16              : /// deltas (or images) with the same range have identical content.
      17              : #[derive(Debug, PartialEq, Eq, Clone)]
      18              : pub struct LayerKey {
      19              :     // TODO I use i128 and u64 because it was easy for prototyping,
      20              :     //      testing, and benchmarking. If we can use the Lsn and Key
      21              :     //      types without overhead that would be preferable.
      22              :     pub key: Range<i128>,
      23              :     pub lsn: Range<u64>,
      24              :     pub is_image: bool,
      25              : }
      26              : 
      27              : impl PartialOrd for LayerKey {
      28            0 :     fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
      29            0 :         Some(self.cmp(other))
      30            0 :     }
      31              : }
      32              : 
      33              : impl Ord for LayerKey {
      34       297314 :     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
      35       297314 :         // NOTE we really care about comparing by lsn.start first
      36       297314 :         self.lsn
      37       297314 :             .start
      38       297314 :             .cmp(&other.lsn.start)
      39       297314 :             .then(self.lsn.end.cmp(&other.lsn.end))
      40       297314 :             .then(self.key.start.cmp(&other.key.start))
      41       297314 :             .then(self.key.end.cmp(&other.key.end))
      42       297314 :             .then(self.is_image.cmp(&other.is_image))
      43       297314 :     }
      44              : }
      45              : 
      46              : impl From<&PersistentLayerDesc> for LayerKey {
      47        10844 :     fn from(layer: &PersistentLayerDesc) -> Self {
      48        10844 :         let kr = layer.get_key_range();
      49        10844 :         let lr = layer.get_lsn_range();
      50        10844 :         LayerKey {
      51        10844 :             key: kr.start.to_i128()..kr.end.to_i128(),
      52        10844 :             lsn: lr.start.0..lr.end.0,
      53        10844 :             is_image: !layer.is_incremental(),
      54        10844 :         }
      55        10844 :     }
      56              : }
      57              : 
      58              : /// Efficiently queryable layer coverage for each LSN.
      59              : ///
      60              : /// Allows answering layer map queries very efficiently,
      61              : /// but doesn't allow retroactive insertion, which is
      62              : /// sometimes necessary. See BufferedHistoricLayerCoverage.
      63              : pub struct HistoricLayerCoverage<Value> {
      64              :     /// The latest state
      65              :     head: LayerCoverageTuple<Value>,
      66              : 
      67              :     /// All previous states
      68              :     historic: BTreeMap<u64, LayerCoverageTuple<Value>>,
      69              : }
      70              : 
      71              : impl<T: Clone> Default for HistoricLayerCoverage<T> {
      72            0 :     fn default() -> Self {
      73            0 :         Self::new()
      74            0 :     }
      75              : }
      76              : 
      77              : impl<Value: Clone> HistoricLayerCoverage<Value> {
      78          940 :     pub fn new() -> Self {
      79          940 :         Self {
      80          940 :             head: LayerCoverageTuple::default(),
      81          940 :             historic: BTreeMap::default(),
      82          940 :         }
      83          940 :     }
      84              : 
      85              :     /// Add a layer
      86              :     ///
      87              :     /// Panics if new layer has older lsn.start than an existing layer.
      88              :     /// See BufferedHistoricLayerCoverage for a more general insertion method.
      89        10348 :     pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
      90              :         // It's only a persistent map, not a retroactive one
      91        10348 :         if let Some(last_entry) = self.historic.iter().next_back() {
      92         9488 :             let last_lsn = last_entry.0;
      93         9488 :             if layer_key.lsn.start < *last_lsn {
      94            0 :                 panic!("unexpected retroactive insert");
      95         9488 :             }
      96          860 :         }
      97              : 
      98              :         // Insert into data structure
      99        10348 :         let target = if layer_key.is_image {
     100         4148 :             &mut self.head.image_coverage
     101              :         } else {
     102         6200 :             &mut self.head.delta_coverage
     103              :         };
     104              : 
     105        10348 :         target.insert(layer_key.key, layer_key.lsn.clone(), value);
     106        10348 : 
     107        10348 :         // Remember history. Clone is O(1)
     108        10348 :         self.historic.insert(layer_key.lsn.start, self.head.clone());
     109        10348 :     }
     110              : 
     111              :     /// Query at a particular LSN, inclusive
     112      1088204 :     pub fn get_version(&self, lsn: u64) -> Option<&LayerCoverageTuple<Value>> {
     113      1088204 :         match self.historic.range(..=lsn).next_back() {
     114       634832 :             Some((_, v)) => Some(v),
     115       453372 :             None => None,
     116              :         }
     117      1088204 :     }
     118              : 
     119              :     /// Remove all entries after a certain LSN (inclusive)
     120         2864 :     pub fn trim(&mut self, begin: &u64) {
     121         2864 :         self.historic.split_off(begin);
     122         2864 :         self.head = self
     123         2864 :             .historic
     124         2864 :             .iter()
     125         2864 :             .next_back()
     126         2864 :             .map(|(_, v)| v.clone())
     127         2864 :             .unwrap_or_default();
     128         2864 :     }
     129              : }
     130              : 
     131              : /// This is the most basic test that demonstrates intended usage.
     132              : /// All layers in this test have height 1.
     133              : #[test]
     134            4 : fn test_persistent_simple() {
     135            4 :     let mut map = HistoricLayerCoverage::<String>::new();
     136            4 :     map.insert(
     137            4 :         LayerKey {
     138            4 :             key: 0..5,
     139            4 :             lsn: 100..101,
     140            4 :             is_image: true,
     141            4 :         },
     142            4 :         "Layer 1".to_string(),
     143            4 :     );
     144            4 :     map.insert(
     145            4 :         LayerKey {
     146            4 :             key: 3..9,
     147            4 :             lsn: 110..111,
     148            4 :             is_image: true,
     149            4 :         },
     150            4 :         "Layer 2".to_string(),
     151            4 :     );
     152            4 :     map.insert(
     153            4 :         LayerKey {
     154            4 :             key: 5..6,
     155            4 :             lsn: 120..121,
     156            4 :             is_image: true,
     157            4 :         },
     158            4 :         "Layer 3".to_string(),
     159            4 :     );
     160            4 : 
     161            4 :     // After Layer 1 insertion
     162            4 :     let version = map.get_version(105).unwrap();
     163            4 :     assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
     164            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
     165              : 
     166              :     // After Layer 2 insertion
     167            4 :     let version = map.get_version(115).unwrap();
     168            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
     169            4 :     assert_eq!(version.image_coverage.query(8), Some("Layer 2".to_string()));
     170            4 :     assert_eq!(version.image_coverage.query(11), None);
     171              : 
     172              :     // After Layer 3 insertion
     173            4 :     let version = map.get_version(125).unwrap();
     174            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
     175            4 :     assert_eq!(version.image_coverage.query(5), Some("Layer 3".to_string()));
     176            4 :     assert_eq!(version.image_coverage.query(7), Some("Layer 2".to_string()));
     177            4 : }
     178              : 
     179              : /// Cover simple off-by-one edge cases
     180              : #[test]
     181            4 : fn test_off_by_one() {
     182            4 :     let mut map = HistoricLayerCoverage::<String>::new();
     183            4 :     map.insert(
     184            4 :         LayerKey {
     185            4 :             key: 3..5,
     186            4 :             lsn: 100..110,
     187            4 :             is_image: true,
     188            4 :         },
     189            4 :         "Layer 1".to_string(),
     190            4 :     );
     191            4 : 
     192            4 :     // Check different LSNs
     193            4 :     let version = map.get_version(99);
     194            4 :     assert!(version.is_none());
     195            4 :     let version = map.get_version(100).unwrap();
     196            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
     197            4 :     let version = map.get_version(110).unwrap();
     198            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
     199              : 
     200              :     // Check different keys
     201            4 :     let version = map.get_version(105).unwrap();
     202            4 :     assert_eq!(version.image_coverage.query(2), None);
     203            4 :     assert_eq!(version.image_coverage.query(3), Some("Layer 1".to_string()));
     204            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
     205            4 :     assert_eq!(version.image_coverage.query(5), None);
     206            4 : }
     207              : 
     208              : /// White-box regression test, checking for incorrect removal of node at key.end
     209              : #[test]
     210            4 : fn test_regression() {
     211            4 :     let mut map = HistoricLayerCoverage::<String>::new();
     212            4 :     map.insert(
     213            4 :         LayerKey {
     214            4 :             key: 0..5,
     215            4 :             lsn: 0..5,
     216            4 :             is_image: false,
     217            4 :         },
     218            4 :         "Layer 1".to_string(),
     219            4 :     );
     220            4 :     map.insert(
     221            4 :         LayerKey {
     222            4 :             key: 0..5,
     223            4 :             lsn: 1..2,
     224            4 :             is_image: false,
     225            4 :         },
     226            4 :         "Layer 2".to_string(),
     227            4 :     );
     228            4 : 
     229            4 :     // If an insertion operation improperly deletes the endpoint of a previous layer
     230            4 :     // (which is more likely to happen with layers that collide on key.end), we will
     231            4 :     // end up with an infinite layer, covering the entire keyspace. Here we assert
     232            4 :     // that there's no layer at key 100 because we didn't insert any layer there.
     233            4 :     let version = map.get_version(100).unwrap();
     234            4 :     assert_eq!(version.delta_coverage.query(100), None);
     235            4 : }
     236              : 
     237              : /// Cover edge cases where layers begin or end on the same key
     238              : #[test]
     239            4 : fn test_key_collision() {
     240            4 :     let mut map = HistoricLayerCoverage::<String>::new();
     241            4 : 
     242            4 :     map.insert(
     243            4 :         LayerKey {
     244            4 :             key: 3..5,
     245            4 :             lsn: 100..110,
     246            4 :             is_image: true,
     247            4 :         },
     248            4 :         "Layer 10".to_string(),
     249            4 :     );
     250            4 :     map.insert(
     251            4 :         LayerKey {
     252            4 :             key: 5..8,
     253            4 :             lsn: 100..110,
     254            4 :             is_image: true,
     255            4 :         },
     256            4 :         "Layer 11".to_string(),
     257            4 :     );
     258            4 :     map.insert(
     259            4 :         LayerKey {
     260            4 :             key: 3..4,
     261            4 :             lsn: 200..210,
     262            4 :             is_image: true,
     263            4 :         },
     264            4 :         "Layer 20".to_string(),
     265            4 :     );
     266            4 : 
     267            4 :     // Check after layer 11
     268            4 :     let version = map.get_version(105).unwrap();
     269            4 :     assert_eq!(version.image_coverage.query(2), None);
     270            4 :     assert_eq!(
     271            4 :         version.image_coverage.query(3),
     272            4 :         Some("Layer 10".to_string())
     273            4 :     );
     274            4 :     assert_eq!(
     275            4 :         version.image_coverage.query(5),
     276            4 :         Some("Layer 11".to_string())
     277            4 :     );
     278            4 :     assert_eq!(
     279            4 :         version.image_coverage.query(7),
     280            4 :         Some("Layer 11".to_string())
     281            4 :     );
     282            4 :     assert_eq!(version.image_coverage.query(8), None);
     283              : 
     284              :     // Check after layer 20
     285            4 :     let version = map.get_version(205).unwrap();
     286            4 :     assert_eq!(version.image_coverage.query(2), None);
     287            4 :     assert_eq!(
     288            4 :         version.image_coverage.query(3),
     289            4 :         Some("Layer 20".to_string())
     290            4 :     );
     291            4 :     assert_eq!(
     292            4 :         version.image_coverage.query(5),
     293            4 :         Some("Layer 11".to_string())
     294            4 :     );
     295            4 :     assert_eq!(
     296            4 :         version.image_coverage.query(7),
     297            4 :         Some("Layer 11".to_string())
     298            4 :     );
     299            4 :     assert_eq!(version.image_coverage.query(8), None);
     300            4 : }
     301              : 
     302              : /// Test when rectangles have nontrivial height and possibly overlap
     303              : #[test]
     304            4 : fn test_persistent_overlapping() {
     305            4 :     let mut map = HistoricLayerCoverage::<String>::new();
     306            4 : 
     307            4 :     // Add 3 key-disjoint layers with varying LSN ranges
     308            4 :     map.insert(
     309            4 :         LayerKey {
     310            4 :             key: 1..2,
     311            4 :             lsn: 100..200,
     312            4 :             is_image: true,
     313            4 :         },
     314            4 :         "Layer 1".to_string(),
     315            4 :     );
     316            4 :     map.insert(
     317            4 :         LayerKey {
     318            4 :             key: 4..5,
     319            4 :             lsn: 110..200,
     320            4 :             is_image: true,
     321            4 :         },
     322            4 :         "Layer 2".to_string(),
     323            4 :     );
     324            4 :     map.insert(
     325            4 :         LayerKey {
     326            4 :             key: 7..8,
     327            4 :             lsn: 120..300,
     328            4 :             is_image: true,
     329            4 :         },
     330            4 :         "Layer 3".to_string(),
     331            4 :     );
     332            4 : 
     333            4 :     // Add wide and short layer
     334            4 :     map.insert(
     335            4 :         LayerKey {
     336            4 :             key: 0..9,
     337            4 :             lsn: 130..199,
     338            4 :             is_image: true,
     339            4 :         },
     340            4 :         "Layer 4".to_string(),
     341            4 :     );
     342            4 : 
     343            4 :     // Add wide layer taller than some
     344            4 :     map.insert(
     345            4 :         LayerKey {
     346            4 :             key: 0..9,
     347            4 :             lsn: 140..201,
     348            4 :             is_image: true,
     349            4 :         },
     350            4 :         "Layer 5".to_string(),
     351            4 :     );
     352            4 : 
     353            4 :     // Add wide layer taller than all
     354            4 :     map.insert(
     355            4 :         LayerKey {
     356            4 :             key: 0..9,
     357            4 :             lsn: 150..301,
     358            4 :             is_image: true,
     359            4 :         },
     360            4 :         "Layer 6".to_string(),
     361            4 :     );
     362            4 : 
     363            4 :     // After layer 4 insertion
     364            4 :     let version = map.get_version(135).unwrap();
     365            4 :     assert_eq!(version.image_coverage.query(0), Some("Layer 4".to_string()));
     366            4 :     assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
     367            4 :     assert_eq!(version.image_coverage.query(2), Some("Layer 4".to_string()));
     368            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
     369            4 :     assert_eq!(version.image_coverage.query(5), Some("Layer 4".to_string()));
     370            4 :     assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
     371            4 :     assert_eq!(version.image_coverage.query(8), Some("Layer 4".to_string()));
     372              : 
     373              :     // After layer 5 insertion
     374            4 :     let version = map.get_version(145).unwrap();
     375            4 :     assert_eq!(version.image_coverage.query(0), Some("Layer 5".to_string()));
     376            4 :     assert_eq!(version.image_coverage.query(1), Some("Layer 5".to_string()));
     377            4 :     assert_eq!(version.image_coverage.query(2), Some("Layer 5".to_string()));
     378            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 5".to_string()));
     379            4 :     assert_eq!(version.image_coverage.query(5), Some("Layer 5".to_string()));
     380            4 :     assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
     381            4 :     assert_eq!(version.image_coverage.query(8), Some("Layer 5".to_string()));
     382              : 
     383              :     // After layer 6 insertion
     384            4 :     let version = map.get_version(155).unwrap();
     385            4 :     assert_eq!(version.image_coverage.query(0), Some("Layer 6".to_string()));
     386            4 :     assert_eq!(version.image_coverage.query(1), Some("Layer 6".to_string()));
     387            4 :     assert_eq!(version.image_coverage.query(2), Some("Layer 6".to_string()));
     388            4 :     assert_eq!(version.image_coverage.query(4), Some("Layer 6".to_string()));
     389            4 :     assert_eq!(version.image_coverage.query(5), Some("Layer 6".to_string()));
     390            4 :     assert_eq!(version.image_coverage.query(7), Some("Layer 6".to_string()));
     391            4 :     assert_eq!(version.image_coverage.query(8), Some("Layer 6".to_string()));
     392            4 : }
     393              : 
     394              : /// Wrapper for HistoricLayerCoverage that allows us to hack around the lack
     395              : /// of support for retroactive insertion by rebuilding the map since the
     396              : /// change.
     397              : ///
     398              : /// Why is this needed? We most often insert new layers with newer LSNs,
     399              : /// but during compaction we create layers with non-latest LSN, and during
     400              : /// GC we delete historic layers.
     401              : ///
     402              : /// Even though rebuilding is an expensive (N log N) solution to the problem,
     403              : /// it's not critical since we do something equally expensive just to decide
     404              : /// whether or not to create new image layers.
     405              : /// TODO It's not expensive but it's not great to hold a layer map write lock
     406              : ///      for that long.
     407              : ///
     408              : /// If this becomes an actual bottleneck, one solution would be to build a
     409              : /// segment tree that holds PersistentLayerMaps. Though this would mean that
     410              : /// we take an additional log(N) performance hit for queries, which will probably
     411              : /// still be more critical.
     412              : ///
     413              : /// See this for more on persistent and retroactive techniques:
     414              : /// <https://www.youtube.com/watch?v=WqCWghETNDc&t=581s>
     415              : pub struct BufferedHistoricLayerCoverage<Value> {
     416              :     /// A persistent layer map that we rebuild when we need to retroactively update
     417              :     historic_coverage: HistoricLayerCoverage<Value>,
     418              : 
     419              :     /// We buffer insertion into the PersistentLayerMap to decrease the number of rebuilds.
     420              :     buffer: BTreeMap<LayerKey, Option<Value>>,
     421              : 
     422              :     /// All current layers. This is not used for search. Only to make rebuilds easier.
     423              :     layers: BTreeMap<LayerKey, Value>,
     424              : }
     425              : 
     426              : impl<T: std::fmt::Debug> std::fmt::Debug for BufferedHistoricLayerCoverage<T> {
     427            0 :     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
     428            0 :         f.debug_struct("RetroactiveLayerMap")
     429            0 :             .field("buffer", &self.buffer)
     430            0 :             .field("layers", &self.layers)
     431            0 :             .finish()
     432            0 :     }
     433              : }
     434              : 
     435              : impl<T: Clone> Default for BufferedHistoricLayerCoverage<T> {
     436          912 :     fn default() -> Self {
     437          912 :         Self::new()
     438          912 :     }
     439              : }
     440              : 
     441              : impl<Value: Clone> BufferedHistoricLayerCoverage<Value> {
     442          920 :     pub fn new() -> Self {
     443          920 :         Self {
     444          920 :             historic_coverage: HistoricLayerCoverage::<Value>::new(),
     445          920 :             buffer: BTreeMap::new(),
     446          920 :             layers: BTreeMap::new(),
     447          920 :         }
     448          920 :     }
     449              : 
     450         9836 :     pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
     451         9836 :         self.buffer.insert(layer_key, Some(value));
     452         9836 :     }
     453              : 
     454         1036 :     pub fn remove(&mut self, layer_key: LayerKey) {
     455         1036 :         self.buffer.insert(layer_key, None);
     456         1036 :     }
     457              : 
     458         3584 :     pub fn rebuild(&mut self) {
     459              :         // Find the first LSN that needs to be rebuilt
     460         3584 :         let rebuild_since: u64 = match self.buffer.iter().next() {
     461         2864 :             Some((LayerKey { lsn, .. }, _)) => lsn.start,
     462          720 :             None => return, // No need to rebuild if buffer is empty
     463              :         };
     464              : 
     465              :         // Apply buffered updates to self.layers
     466         2864 :         let num_updates = self.buffer.len();
     467        10872 :         self.buffer.retain(|layer_key, layer| {
     468        10872 :             match layer {
     469         9836 :                 Some(l) => {
     470         9836 :                     self.layers.insert(layer_key.clone(), l.clone());
     471         9836 :                 }
     472         1036 :                 None => {
     473         1036 :                     self.layers.remove(layer_key);
     474         1036 :                 }
     475              :             };
     476        10872 :             false
     477        10872 :         });
     478         2864 : 
     479         2864 :         // Rebuild
     480         2864 :         let mut num_inserted = 0;
     481         2864 :         self.historic_coverage.trim(&rebuild_since);
     482        10288 :         for (layer_key, layer) in self.layers.range(
     483         2864 :             LayerKey {
     484         2864 :                 lsn: rebuild_since..0,
     485         2864 :                 key: 0..0,
     486         2864 :                 is_image: false,
     487         2864 :             }..,
     488        10288 :         ) {
     489        10288 :             self.historic_coverage
     490        10288 :                 .insert(layer_key.clone(), layer.clone());
     491        10288 :             num_inserted += 1;
     492        10288 :         }
     493              : 
     494              :         // TODO maybe only warn if ratio is at least 10
     495         2864 :         info!(
     496            0 :             "Rebuilt layer map. Did {} insertions to process a batch of {} updates.",
     497              :             num_inserted, num_updates,
     498              :         )
     499         3584 :     }
     500              : 
     501              :     /// Iterate all the layers
     502         7324 :     pub fn iter(&self) -> impl '_ + Iterator<Item = Value> {
     503         7324 :         // NOTE we can actually perform this without rebuilding,
     504         7324 :         //      but it's not necessary for now.
     505         7324 :         if !self.buffer.is_empty() {
     506            0 :             panic!("rebuild pls")
     507         7324 :         }
     508         7324 : 
     509         7324 :         self.layers.values().cloned()
     510         7324 :     }
     511              : 
     512              :     /// Return a reference to a queryable map, assuming all updates
     513              :     /// have already been processed using self.rebuild()
     514      1088136 :     pub fn get(&self) -> anyhow::Result<&HistoricLayerCoverage<Value>> {
     515      1088136 :         // NOTE we error here instead of implicitly rebuilding because
     516      1088136 :         //      rebuilding is somewhat expensive.
     517      1088136 :         // TODO maybe implicitly rebuild and log/sentry an error?
     518      1088136 :         if !self.buffer.is_empty() {
     519            0 :             anyhow::bail!("rebuild required")
     520      1088136 :         }
     521      1088136 : 
     522      1088136 :         Ok(&self.historic_coverage)
     523      1088136 :     }
     524              : 
     525          936 :     pub(crate) fn len(&self) -> usize {
     526          936 :         self.layers.len()
     527          936 :     }
     528              : }
     529              : 
     530              : #[test]
     531            4 : fn test_retroactive_regression_1() {
     532            4 :     let mut map = BufferedHistoricLayerCoverage::new();
     533            4 : 
     534            4 :     map.insert(
     535            4 :         LayerKey {
     536            4 :             key: 0..21267647932558653966460912964485513215,
     537            4 :             lsn: 23761336..23761457,
     538            4 :             is_image: false,
     539            4 :         },
     540            4 :         "sdfsdfs".to_string(),
     541            4 :     );
     542            4 : 
     543            4 :     map.rebuild();
     544            4 : 
     545            4 :     let version = map.get().unwrap().get_version(23761457).unwrap();
     546            4 :     assert_eq!(
     547            4 :         version.delta_coverage.query(100),
     548            4 :         Some("sdfsdfs".to_string())
     549            4 :     );
     550            4 : }
     551              : 
     552              : #[test]
     553            4 : fn test_retroactive_simple() {
     554            4 :     let mut map = BufferedHistoricLayerCoverage::new();
     555            4 : 
     556            4 :     // Append some images in increasing LSN order
     557            4 :     map.insert(
     558            4 :         LayerKey {
     559            4 :             key: 0..5,
     560            4 :             lsn: 100..101,
     561            4 :             is_image: true,
     562            4 :         },
     563            4 :         "Image 1".to_string(),
     564            4 :     );
     565            4 :     map.insert(
     566            4 :         LayerKey {
     567            4 :             key: 3..9,
     568            4 :             lsn: 110..111,
     569            4 :             is_image: true,
     570            4 :         },
     571            4 :         "Image 2".to_string(),
     572            4 :     );
     573            4 :     map.insert(
     574            4 :         LayerKey {
     575            4 :             key: 4..6,
     576            4 :             lsn: 120..121,
     577            4 :             is_image: true,
     578            4 :         },
     579            4 :         "Image 3".to_string(),
     580            4 :     );
     581            4 :     map.insert(
     582            4 :         LayerKey {
     583            4 :             key: 8..9,
     584            4 :             lsn: 120..121,
     585            4 :             is_image: true,
     586            4 :         },
     587            4 :         "Image 4".to_string(),
     588            4 :     );
     589            4 : 
     590            4 :     // Add a delta layer out of order
     591            4 :     map.insert(
     592            4 :         LayerKey {
     593            4 :             key: 2..5,
     594            4 :             lsn: 105..106,
     595            4 :             is_image: false,
     596            4 :         },
     597            4 :         "Delta 1".to_string(),
     598            4 :     );
     599            4 : 
     600            4 :     // Rebuild so we can start querying
     601            4 :     map.rebuild();
     602            4 : 
     603            4 :     {
     604            4 :         let map = map.get().expect("rebuilt");
     605            4 : 
     606            4 :         let version = map.get_version(90);
     607            4 :         assert!(version.is_none());
     608            4 :         let version = map.get_version(102).unwrap();
     609            4 :         assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
     610              : 
     611            4 :         let version = map.get_version(107).unwrap();
     612            4 :         assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
     613            4 :         assert_eq!(version.delta_coverage.query(4), Some("Delta 1".to_string()));
     614              : 
     615            4 :         let version = map.get_version(115).unwrap();
     616            4 :         assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
     617              : 
     618            4 :         let version = map.get_version(125).unwrap();
     619            4 :         assert_eq!(version.image_coverage.query(4), Some("Image 3".to_string()));
     620              :     }
     621              : 
     622              :     // Remove Image 3
     623            4 :     map.remove(LayerKey {
     624            4 :         key: 4..6,
     625            4 :         lsn: 120..121,
     626            4 :         is_image: true,
     627            4 :     });
     628            4 :     map.rebuild();
     629            4 : 
     630            4 :     {
     631            4 :         // Check deletion worked
     632            4 :         let map = map.get().expect("rebuilt");
     633            4 :         let version = map.get_version(125).unwrap();
     634            4 :         assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
     635            4 :         assert_eq!(version.image_coverage.query(8), Some("Image 4".to_string()));
     636              :     }
     637            4 : }
        

Generated by: LCOV version 2.1-beta