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

Generated by: LCOV version 2.1-beta