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 894395 : fn cmp(&self, other: &Self) -> std::cmp::Ordering {
34 894395 : // NOTE we really care about comparing by lsn.start first
35 894395 : self.lsn
36 894395 : .start
37 894395 : .cmp(&other.lsn.start)
38 894395 : .then(self.lsn.end.cmp(&other.lsn.end))
39 894395 : .then(self.key.start.cmp(&other.key.start))
40 894395 : .then(self.key.end.cmp(&other.key.end))
41 894395 : .then(self.is_image.cmp(&other.is_image))
42 894395 : }
43 : }
44 :
45 : impl From<&PersistentLayerDesc> for LayerKey {
46 32712 : fn from(layer: &PersistentLayerDesc) -> Self {
47 32712 : let kr = layer.get_key_range();
48 32712 : let lr = layer.get_lsn_range();
49 32712 : LayerKey {
50 32712 : key: kr.start.to_i128()..kr.end.to_i128(),
51 32712 : lsn: lr.start.0..lr.end.0,
52 32712 : is_image: !layer.is_incremental(),
53 32712 : }
54 32712 : }
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 2916 : pub fn new() -> Self {
80 2916 : Self {
81 2916 : head: LayerCoverageTuple::default(),
82 2916 : historic: BTreeMap::default(),
83 2916 : }
84 2916 : }
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 31380 : pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
91 : // It's only a persistent map, not a retroactive one
92 31380 : if let Some(last_entry) = self.historic.iter().next_back() {
93 28704 : let last_lsn = last_entry.0;
94 28704 : if layer_key.lsn.start < *last_lsn {
95 0 : panic!("unexpected retroactive insert");
96 28704 : }
97 2676 : }
98 :
99 : // Insert into data structure
100 31380 : let target = if layer_key.is_image {
101 12648 : &mut self.head.image_coverage
102 : } else {
103 18732 : &mut self.head.delta_coverage
104 : };
105 :
106 31380 : target.insert(layer_key.key, layer_key.lsn.clone(), value);
107 31380 :
108 31380 : // Remember history. Clone is O(1)
109 31380 : self.historic.insert(layer_key.lsn.start, self.head.clone());
110 31380 : }
111 :
112 : /// Query at a particular LSN, inclusive
113 7759662 : pub fn get_version(&self, lsn: u64) -> Option<&LayerCoverageTuple<Value>> {
114 7759662 : match self.historic.range(..=lsn).next_back() {
115 5747922 : Some((_, v)) => Some(v),
116 2011740 : None => None,
117 : }
118 7759662 : }
119 :
120 : /// Remove all entries after a certain LSN (inclusive)
121 8772 : pub fn trim(&mut self, begin: &u64) {
122 8772 : self.historic.split_off(begin);
123 8772 : self.head = self
124 8772 : .historic
125 8772 : .iter()
126 8772 : .next_back()
127 8772 : .map(|(_, v)| v.clone())
128 8772 : .unwrap_or_default();
129 8772 : }
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 12 : fn test_persistent_simple() {
136 12 : let mut map = HistoricLayerCoverage::<String>::new();
137 12 : map.insert(
138 12 : LayerKey {
139 12 : key: 0..5,
140 12 : lsn: 100..101,
141 12 : is_image: true,
142 12 : },
143 12 : "Layer 1".to_string(),
144 12 : );
145 12 : map.insert(
146 12 : LayerKey {
147 12 : key: 3..9,
148 12 : lsn: 110..111,
149 12 : is_image: true,
150 12 : },
151 12 : "Layer 2".to_string(),
152 12 : );
153 12 : map.insert(
154 12 : LayerKey {
155 12 : key: 5..6,
156 12 : lsn: 120..121,
157 12 : is_image: true,
158 12 : },
159 12 : "Layer 3".to_string(),
160 12 : );
161 12 :
162 12 : // After Layer 1 insertion
163 12 : let version = map.get_version(105).unwrap();
164 12 : assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
165 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
166 :
167 : // After Layer 2 insertion
168 12 : let version = map.get_version(115).unwrap();
169 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
170 12 : assert_eq!(version.image_coverage.query(8), Some("Layer 2".to_string()));
171 12 : assert_eq!(version.image_coverage.query(11), None);
172 :
173 : // After Layer 3 insertion
174 12 : let version = map.get_version(125).unwrap();
175 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
176 12 : assert_eq!(version.image_coverage.query(5), Some("Layer 3".to_string()));
177 12 : assert_eq!(version.image_coverage.query(7), Some("Layer 2".to_string()));
178 12 : }
179 :
180 : /// Cover simple off-by-one edge cases
181 : #[test]
182 12 : fn test_off_by_one() {
183 12 : let mut map = HistoricLayerCoverage::<String>::new();
184 12 : map.insert(
185 12 : LayerKey {
186 12 : key: 3..5,
187 12 : lsn: 100..110,
188 12 : is_image: true,
189 12 : },
190 12 : "Layer 1".to_string(),
191 12 : );
192 12 :
193 12 : // Check different LSNs
194 12 : let version = map.get_version(99);
195 12 : assert!(version.is_none());
196 12 : let version = map.get_version(100).unwrap();
197 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
198 12 : let version = map.get_version(110).unwrap();
199 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
200 :
201 : // Check different keys
202 12 : let version = map.get_version(105).unwrap();
203 12 : assert_eq!(version.image_coverage.query(2), None);
204 12 : assert_eq!(version.image_coverage.query(3), Some("Layer 1".to_string()));
205 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 1".to_string()));
206 12 : assert_eq!(version.image_coverage.query(5), None);
207 12 : }
208 :
209 : /// White-box regression test, checking for incorrect removal of node at key.end
210 : #[test]
211 12 : fn test_regression() {
212 12 : let mut map = HistoricLayerCoverage::<String>::new();
213 12 : map.insert(
214 12 : LayerKey {
215 12 : key: 0..5,
216 12 : lsn: 0..5,
217 12 : is_image: false,
218 12 : },
219 12 : "Layer 1".to_string(),
220 12 : );
221 12 : map.insert(
222 12 : LayerKey {
223 12 : key: 0..5,
224 12 : lsn: 1..2,
225 12 : is_image: false,
226 12 : },
227 12 : "Layer 2".to_string(),
228 12 : );
229 12 :
230 12 : // If an insertion operation improperly deletes the endpoint of a previous layer
231 12 : // (which is more likely to happen with layers that collide on key.end), we will
232 12 : // end up with an infinite layer, covering the entire keyspace. Here we assert
233 12 : // that there's no layer at key 100 because we didn't insert any layer there.
234 12 : let version = map.get_version(100).unwrap();
235 12 : assert_eq!(version.delta_coverage.query(100), None);
236 12 : }
237 :
238 : /// Cover edge cases where layers begin or end on the same key
239 : #[test]
240 12 : fn test_key_collision() {
241 12 : let mut map = HistoricLayerCoverage::<String>::new();
242 12 :
243 12 : map.insert(
244 12 : LayerKey {
245 12 : key: 3..5,
246 12 : lsn: 100..110,
247 12 : is_image: true,
248 12 : },
249 12 : "Layer 10".to_string(),
250 12 : );
251 12 : map.insert(
252 12 : LayerKey {
253 12 : key: 5..8,
254 12 : lsn: 100..110,
255 12 : is_image: true,
256 12 : },
257 12 : "Layer 11".to_string(),
258 12 : );
259 12 : map.insert(
260 12 : LayerKey {
261 12 : key: 3..4,
262 12 : lsn: 200..210,
263 12 : is_image: true,
264 12 : },
265 12 : "Layer 20".to_string(),
266 12 : );
267 12 :
268 12 : // Check after layer 11
269 12 : let version = map.get_version(105).unwrap();
270 12 : assert_eq!(version.image_coverage.query(2), None);
271 12 : assert_eq!(
272 12 : version.image_coverage.query(3),
273 12 : Some("Layer 10".to_string())
274 12 : );
275 12 : assert_eq!(
276 12 : version.image_coverage.query(5),
277 12 : Some("Layer 11".to_string())
278 12 : );
279 12 : assert_eq!(
280 12 : version.image_coverage.query(7),
281 12 : Some("Layer 11".to_string())
282 12 : );
283 12 : assert_eq!(version.image_coverage.query(8), None);
284 :
285 : // Check after layer 20
286 12 : let version = map.get_version(205).unwrap();
287 12 : assert_eq!(version.image_coverage.query(2), None);
288 12 : assert_eq!(
289 12 : version.image_coverage.query(3),
290 12 : Some("Layer 20".to_string())
291 12 : );
292 12 : assert_eq!(
293 12 : version.image_coverage.query(5),
294 12 : Some("Layer 11".to_string())
295 12 : );
296 12 : assert_eq!(
297 12 : version.image_coverage.query(7),
298 12 : Some("Layer 11".to_string())
299 12 : );
300 12 : assert_eq!(version.image_coverage.query(8), None);
301 12 : }
302 :
303 : /// Test when rectangles have nontrivial height and possibly overlap
304 : #[test]
305 12 : fn test_persistent_overlapping() {
306 12 : let mut map = HistoricLayerCoverage::<String>::new();
307 12 :
308 12 : // Add 3 key-disjoint layers with varying LSN ranges
309 12 : map.insert(
310 12 : LayerKey {
311 12 : key: 1..2,
312 12 : lsn: 100..200,
313 12 : is_image: true,
314 12 : },
315 12 : "Layer 1".to_string(),
316 12 : );
317 12 : map.insert(
318 12 : LayerKey {
319 12 : key: 4..5,
320 12 : lsn: 110..200,
321 12 : is_image: true,
322 12 : },
323 12 : "Layer 2".to_string(),
324 12 : );
325 12 : map.insert(
326 12 : LayerKey {
327 12 : key: 7..8,
328 12 : lsn: 120..300,
329 12 : is_image: true,
330 12 : },
331 12 : "Layer 3".to_string(),
332 12 : );
333 12 :
334 12 : // Add wide and short layer
335 12 : map.insert(
336 12 : LayerKey {
337 12 : key: 0..9,
338 12 : lsn: 130..199,
339 12 : is_image: true,
340 12 : },
341 12 : "Layer 4".to_string(),
342 12 : );
343 12 :
344 12 : // Add wide layer taller than some
345 12 : map.insert(
346 12 : LayerKey {
347 12 : key: 0..9,
348 12 : lsn: 140..201,
349 12 : is_image: true,
350 12 : },
351 12 : "Layer 5".to_string(),
352 12 : );
353 12 :
354 12 : // Add wide layer taller than all
355 12 : map.insert(
356 12 : LayerKey {
357 12 : key: 0..9,
358 12 : lsn: 150..301,
359 12 : is_image: true,
360 12 : },
361 12 : "Layer 6".to_string(),
362 12 : );
363 12 :
364 12 : // After layer 4 insertion
365 12 : let version = map.get_version(135).unwrap();
366 12 : assert_eq!(version.image_coverage.query(0), Some("Layer 4".to_string()));
367 12 : assert_eq!(version.image_coverage.query(1), Some("Layer 1".to_string()));
368 12 : assert_eq!(version.image_coverage.query(2), Some("Layer 4".to_string()));
369 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 2".to_string()));
370 12 : assert_eq!(version.image_coverage.query(5), Some("Layer 4".to_string()));
371 12 : assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
372 12 : assert_eq!(version.image_coverage.query(8), Some("Layer 4".to_string()));
373 :
374 : // After layer 5 insertion
375 12 : let version = map.get_version(145).unwrap();
376 12 : assert_eq!(version.image_coverage.query(0), Some("Layer 5".to_string()));
377 12 : assert_eq!(version.image_coverage.query(1), Some("Layer 5".to_string()));
378 12 : assert_eq!(version.image_coverage.query(2), Some("Layer 5".to_string()));
379 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 5".to_string()));
380 12 : assert_eq!(version.image_coverage.query(5), Some("Layer 5".to_string()));
381 12 : assert_eq!(version.image_coverage.query(7), Some("Layer 3".to_string()));
382 12 : assert_eq!(version.image_coverage.query(8), Some("Layer 5".to_string()));
383 :
384 : // After layer 6 insertion
385 12 : let version = map.get_version(155).unwrap();
386 12 : assert_eq!(version.image_coverage.query(0), Some("Layer 6".to_string()));
387 12 : assert_eq!(version.image_coverage.query(1), Some("Layer 6".to_string()));
388 12 : assert_eq!(version.image_coverage.query(2), Some("Layer 6".to_string()));
389 12 : assert_eq!(version.image_coverage.query(4), Some("Layer 6".to_string()));
390 12 : assert_eq!(version.image_coverage.query(5), Some("Layer 6".to_string()));
391 12 : assert_eq!(version.image_coverage.query(7), Some("Layer 6".to_string()));
392 12 : assert_eq!(version.image_coverage.query(8), Some("Layer 6".to_string()));
393 12 : }
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 2832 : fn default() -> Self {
442 2832 : Self::new()
443 2832 : }
444 : }
445 :
446 : impl<Value: Clone> BufferedHistoricLayerCoverage<Value> {
447 2856 : pub fn new() -> Self {
448 2856 : Self {
449 2856 : historic_coverage: HistoricLayerCoverage::<Value>::new(),
450 2856 : buffer: BTreeMap::new(),
451 2856 : layers: BTreeMap::new(),
452 2856 : }
453 2856 : }
454 :
455 29688 : pub fn insert(&mut self, layer_key: LayerKey, value: Value) {
456 29688 : self.buffer.insert(layer_key, Some(value));
457 29688 : }
458 :
459 3108 : pub fn remove(&mut self, layer_key: LayerKey) {
460 3108 : self.buffer.insert(layer_key, None);
461 3108 : }
462 :
463 10932 : pub fn rebuild(&mut self) {
464 : // Find the first LSN that needs to be rebuilt
465 10932 : let rebuild_since: u64 = match self.buffer.iter().next() {
466 8772 : Some((LayerKey { lsn, .. }, _)) => lsn.start,
467 2160 : None => return, // No need to rebuild if buffer is empty
468 : };
469 :
470 : // Apply buffered updates to self.layers
471 8772 : let num_updates = self.buffer.len();
472 32796 : self.buffer.retain(|layer_key, layer| {
473 32796 : match layer {
474 29688 : Some(l) => {
475 29688 : self.layers.insert(layer_key.clone(), l.clone());
476 29688 : }
477 3108 : None => {
478 3108 : self.layers.remove(layer_key);
479 3108 : }
480 : };
481 32796 : false
482 32796 : });
483 8772 :
484 8772 : // Rebuild
485 8772 : let mut num_inserted = 0;
486 8772 : self.historic_coverage.trim(&rebuild_since);
487 31200 : for (layer_key, layer) in self.layers.range(
488 8772 : LayerKey {
489 8772 : lsn: rebuild_since..0,
490 8772 : key: 0..0,
491 8772 : is_image: false,
492 8772 : }..,
493 31200 : ) {
494 31200 : self.historic_coverage
495 31200 : .insert(layer_key.clone(), layer.clone());
496 31200 : num_inserted += 1;
497 31200 : }
498 :
499 : // TODO maybe only warn if ratio is at least 10
500 8772 : info!(
501 0 : "Rebuilt layer map. Did {} insertions to process a batch of {} updates.",
502 : num_inserted, num_updates,
503 : )
504 10932 : }
505 :
506 : /// Iterate all the layers
507 22152 : pub fn iter(&self) -> impl ExactSizeIterator<Item = Value> {
508 22152 : // NOTE we can actually perform this without rebuilding,
509 22152 : // but it's not necessary for now.
510 22152 : if !self.buffer.is_empty() {
511 0 : panic!("rebuild pls")
512 22152 : }
513 22152 :
514 22152 : self.layers.values().cloned()
515 22152 : }
516 :
517 : /// Return a reference to a queryable map, assuming all updates
518 : /// have already been processed using self.rebuild()
519 7759458 : pub fn get(&self) -> anyhow::Result<&HistoricLayerCoverage<Value>> {
520 7759458 : // NOTE we error here instead of implicitly rebuilding because
521 7759458 : // rebuilding is somewhat expensive.
522 7759458 : // TODO maybe implicitly rebuild and log/sentry an error?
523 7759458 : if !self.buffer.is_empty() {
524 0 : anyhow::bail!("rebuild required")
525 7759458 : }
526 7759458 :
527 7759458 : Ok(&self.historic_coverage)
528 7759458 : }
529 :
530 2928 : pub(crate) fn len(&self) -> usize {
531 2928 : self.layers.len()
532 2928 : }
533 : }
534 :
535 : #[test]
536 12 : fn test_retroactive_regression_1() {
537 12 : let mut map = BufferedHistoricLayerCoverage::new();
538 12 :
539 12 : map.insert(
540 12 : LayerKey {
541 12 : key: 0..21267647932558653966460912964485513215,
542 12 : lsn: 23761336..23761457,
543 12 : is_image: false,
544 12 : },
545 12 : "sdfsdfs".to_string(),
546 12 : );
547 12 :
548 12 : map.rebuild();
549 12 :
550 12 : let version = map.get().unwrap().get_version(23761457).unwrap();
551 12 : assert_eq!(
552 12 : version.delta_coverage.query(100),
553 12 : Some("sdfsdfs".to_string())
554 12 : );
555 12 : }
556 :
557 : #[test]
558 12 : fn test_retroactive_simple() {
559 12 : let mut map = BufferedHistoricLayerCoverage::new();
560 12 :
561 12 : // Append some images in increasing LSN order
562 12 : map.insert(
563 12 : LayerKey {
564 12 : key: 0..5,
565 12 : lsn: 100..101,
566 12 : is_image: true,
567 12 : },
568 12 : "Image 1".to_string(),
569 12 : );
570 12 : map.insert(
571 12 : LayerKey {
572 12 : key: 3..9,
573 12 : lsn: 110..111,
574 12 : is_image: true,
575 12 : },
576 12 : "Image 2".to_string(),
577 12 : );
578 12 : map.insert(
579 12 : LayerKey {
580 12 : key: 4..6,
581 12 : lsn: 120..121,
582 12 : is_image: true,
583 12 : },
584 12 : "Image 3".to_string(),
585 12 : );
586 12 : map.insert(
587 12 : LayerKey {
588 12 : key: 8..9,
589 12 : lsn: 120..121,
590 12 : is_image: true,
591 12 : },
592 12 : "Image 4".to_string(),
593 12 : );
594 12 :
595 12 : // Add a delta layer out of order
596 12 : map.insert(
597 12 : LayerKey {
598 12 : key: 2..5,
599 12 : lsn: 105..106,
600 12 : is_image: false,
601 12 : },
602 12 : "Delta 1".to_string(),
603 12 : );
604 12 :
605 12 : // Rebuild so we can start querying
606 12 : map.rebuild();
607 12 :
608 12 : {
609 12 : let map = map.get().expect("rebuilt");
610 12 :
611 12 : let version = map.get_version(90);
612 12 : assert!(version.is_none());
613 12 : let version = map.get_version(102).unwrap();
614 12 : assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
615 :
616 12 : let version = map.get_version(107).unwrap();
617 12 : assert_eq!(version.image_coverage.query(4), Some("Image 1".to_string()));
618 12 : assert_eq!(version.delta_coverage.query(4), Some("Delta 1".to_string()));
619 :
620 12 : let version = map.get_version(115).unwrap();
621 12 : assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
622 :
623 12 : let version = map.get_version(125).unwrap();
624 12 : assert_eq!(version.image_coverage.query(4), Some("Image 3".to_string()));
625 : }
626 :
627 : // Remove Image 3
628 12 : map.remove(LayerKey {
629 12 : key: 4..6,
630 12 : lsn: 120..121,
631 12 : is_image: true,
632 12 : });
633 12 : map.rebuild();
634 12 :
635 12 : {
636 12 : // Check deletion worked
637 12 : let map = map.get().expect("rebuilt");
638 12 : let version = map.get_version(125).unwrap();
639 12 : assert_eq!(version.image_coverage.query(4), Some("Image 2".to_string()));
640 12 : assert_eq!(version.image_coverage.query(8), Some("Image 4".to_string()));
641 : }
642 12 : }
|
