Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/seqlog.rs

16.2 KiB, 18 runs

created by r1870400018:76234, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1use oxedyne_fe2o3_o3db_sync::seqlog::{
2 Appended,
3 SeqLog,
4 SeqRead,
5 SeqStore,
6 SnapReg,
7};
8
9use oxedyne_fe2o3_core::prelude::*;
10use oxedyne_fe2o3_jdat::prelude::*;
11
12use std::{
13 cell::{
14 Cell,
15 RefCell,
16 },
17 collections::BTreeMap,
18};
19
20/// A store in memory, keyed by the key's debug form.
21#[derive(Default)]
22struct Mem {
23 map: RefCell<BTreeMap<String, Dat>>,
24 gets: Cell<usize>, // lookups made
25 cut: Cell<Option<usize>>, // puts left before the store stops, when set
26}
27
28impl SeqStore for Mem {
29 fn get(&self, key: &Dat) -> Outcome<Option<Dat>> {
30 self.gets.set(self.gets.get() + 1);
31 Ok(self.map.borrow().get(&fmt!("{:?}", key)).cloned())
32 }
33 fn put(&self, key: Dat, val: Dat) -> Outcome<()> {
34 if self.cut.get() == Some(0) { return Err(err!("Mem: the store stopped."; Test)); }
35 self.cut.set(self.cut.get().map(|n| n - 1));
36 self.map.borrow_mut().insert(fmt!("{:?}", key), val);
37 Ok(())
38 }
39 fn delete(&self, key: &Dat) -> Outcome<bool> {
40 Ok(self.map.borrow_mut().remove(&fmt!("{:?}", key)).is_some())
41 }
42}
43
44fn rows(names: &[&str]) -> Vec<Dat> {
45 names.iter().map(|n| dat!(n.to_string())).collect()
46}
47
48fn seqs(r: &SeqRead) -> Vec<u64> {
49 match r {
50 SeqRead::Rows { rows, .. } => rows.iter().map(|(s, _)| *s).collect(),
51 SeqRead::Gap { .. } => Vec::new(),
52 }
53}
54
55#[test]
56fn appends_take_contiguous_seqs_and_survive_a_reload() -> Outcome<()> {
57 let st = Mem::default();
58 let log = SeqLog::new("clog:a:c", "clbat:a:c:");
59 let mut idx = res!(log.load(&st));
60 assert_eq!(res!(log.append(&st, &mut idx, rows(&["a", "b"]), 10, 2)), 1);
61 assert_eq!(res!(log.append(&st, &mut idx, rows(&["c"]), 11, 1)), 3);
62 let idx = res!(log.load(&st));
63 assert_eq!((idx.head, idx.low, idx.batches.len(), idx.bytes()), (3, 1, 2, 3));
64 assert_eq!(seqs(&res!(log.read(&st, &idx, 0, 100))), vec![1, 2, 3]);
65 assert_eq!(seqs(&res!(log.read(&st, &idx, 2, 100))), vec![3]);
66 assert_eq!(seqs(&res!(log.read(&st, &idx, 3, 100))), Vec::<u64>::new());
67 Ok(())
68}
69
70#[test]
71fn a_read_stops_at_its_limit_and_says_more() -> Outcome<()> {
72 let st = Mem::default();
73 let log = SeqLog::new("i", "b:");
74 let mut idx = res!(log.load(&st));
75 res!(log.append(&st, &mut idx, rows(&["a", "b", "c"]), 1, 3));
76 match res!(log.read(&st, &idx, 0, 2)) {
77 SeqRead::Rows { rows, more } => {
78 assert_eq!(rows.len(), 2);
79 assert!(more);
80 }
81 SeqRead::Gap { .. } => return Err(err!("A full log answered a gap."; Test)),
82 }
83 Ok(())
84}
85
86#[test]
87fn a_cursor_below_a_trim_answers_gap() -> Outcome<()> {
88 let st = Mem::default();
89 let log = SeqLog::new("i", "b:");
90 let mut idx = res!(log.load(&st));
91 res!(log.append(&st, &mut idx, rows(&["a", "b"]), 1, 2));
92 res!(log.append(&st, &mut idx, rows(&["c"]), 2, 1));
93 res!(log.register_snap(&st, &mut idx, 3, dat!("s3".to_string())));
94 assert_eq!(res!(log.truncate_through(&st, &mut idx, 2)), 1);
95 assert_eq!(idx.low, 3);
96 assert!(res!(st.get(&log.batch_key(1))).is_none(), "the trimmed batch is deleted");
97 match res!(log.read(&st, &idx, 0, 10)) {
98 SeqRead::Gap { low, .. } => assert_eq!(low, 3),
99 other => return Err(err!("Expected a gap, read {:?}.", other; Test)),
100 }
101 assert_eq!(seqs(&res!(log.read(&st, &idx, 2, 10))), vec![3]);
102 // Trimmed empty: the next append still numbers on from the head.
103 res!(log.trim(&st, &mut idx, |_, _| true));
104 assert_eq!((idx.low, idx.head), (4, 3));
105 assert_eq!(res!(log.append(&st, &mut idx, rows(&["d"]), 3, 1)), 4);
106 assert_eq!(idx.low, 4);
107 Ok(())
108}
109
110#[test]
111fn ext_round_trips_and_purge_leaves_nothing() -> Outcome<()> {
112 let st = Mem::default();
113 let log = SeqLog::new("i", "b:");
114 let mut idx = res!(log.load(&st));
115 idx.ext = dat!("caller".to_string());
116 res!(log.append(&st, &mut idx, rows(&["a"]), 1, 1));
117 let back = res!(log.load(&st));
118 assert_eq!(back.ext, dat!("caller".to_string()));
119 res!(log.purge(&st, &back));
120 assert!(st.map.borrow().is_empty());
121 Ok(())
122}
123
124#[test]
125fn a_lock_entry_goes_when_its_last_holder_leaves() -> Outcome<()> {
126 let locks = oxedyne_fe2o3_o3db_sync::seqlog::SeqLocks::new();
127 let n = res!(locks.with("a:c", || {
128 locks.with("a", || Ok(7))
129 }));
130 assert_eq!(n, 7);
131 assert_eq!(res!(locks.len()), 0, "an idle key stays in the map");
132 Ok(())
133}
134
135fn ext(s: &str) -> Dat { dat!(s.to_string()) }
136
137/// A log of four single-row batches, seqs 1 to 4, appended at times 1 to 4.
138fn four(st: &Mem, log: &SeqLog) -> Outcome<oxedyne_fe2o3_o3db_sync::seqlog::SeqIndex> {
139 let mut idx = res!(log.load(st));
140 for (i, n) in ["a", "b", "c", "d"].iter().enumerate() {
141 res!(log.append(st, &mut idx, rows(&[n]), i as i64 + 1, 1));
142 }
143 Ok(idx)
144}
145
146#[test]
147fn a_snapshot_registers_and_survives_a_reload() -> Outcome<()> {
148 let st = Mem::default();
149 let log = SeqLog::new("i", "b:");
150 let mut idx = res!(four(&st, &log));
151 match res!(log.register_snap(&st, &mut idx, 2, ext("s2"))) {
152 SnapReg::Registered { prev: None } => (),
153 other => return Err(err!("Expected a first registration, got {:?}.", other; Test)),
154 }
155 let back = res!(log.load(&st));
156 let snap = res!(back.snap.ok_or_else(|| err!("The snap did not survive a reload."; Test)));
157 assert_eq!((snap.seq, snap.ext), (2, ext("s2")));
158 // A higher one supersedes it and hands the old one back for its refs to be released.
159 match res!(log.register_snap(&st, &mut idx, 4, ext("s4"))) {
160 SnapReg::Registered { prev: Some(p) } => assert_eq!((p.seq, p.ext), (2, ext("s2"))),
161 other => return Err(err!("Expected a superseding registration, got {:?}.", other; Test)),
162 }
163 assert_eq!(res!(log.load(&st)).snap.map(|s| s.seq), Some(4));
164 Ok(())
165}
166
167#[test]
168fn a_snapshot_at_or_below_the_current_or_above_the_head_is_refused() -> Outcome<()> {
169 let st = Mem::default();
170 let log = SeqLog::new("i", "b:");
171 let mut idx = res!(four(&st, &log));
172 res!(log.register_snap(&st, &mut idx, 3, ext("s3")));
173 match res!(log.register_snap(&st, &mut idx, 2, ext("s2"))) {
174 SnapReg::Behind { least } => assert_eq!(least, 4),
175 other => return Err(err!("A snap below the current one was {:?}.", other; Test)),
176 }
177 match res!(log.register_snap(&st, &mut idx, 5, ext("s5"))) {
178 SnapReg::Ahead { head } => assert_eq!(head, 4),
179 other => return Err(err!("A snap above the head was {:?}.", other; Test)),
180 }
181 // Same seq, same ext: idempotent. Same seq, other ext: a conflict.
182 match res!(log.register_snap(&st, &mut idx, 3, ext("s3"))) {
183 SnapReg::Same => (),
184 other => return Err(err!("A retried snap was {:?}.", other; Test)),
185 }
186 match res!(log.register_snap(&st, &mut idx, 3, ext("x3"))) {
187 SnapReg::Conflict { snap } => assert_eq!(snap.ext, ext("s3")),
188 other => return Err(err!("A same-seq different snap was {:?}.", other; Test)),
189 }
190 assert_eq!(res!(log.load(&st)).snap.map(|s| (s.seq, s.ext)), Some((3, ext("s3"))));
191 Ok(())
192}
193
194#[test]
195fn seq_zero_registers_once_and_only_on_an_empty_log() -> Outcome<()> {
196 let st = Mem::default();
197 let log = SeqLog::new("i", "b:");
198 let mut idx = res!(log.load(&st));
199 match res!(log.register_snap(&st, &mut idx, 0, ext("m"))) {
200 SnapReg::Registered { prev: None } => (),
201 other => return Err(err!("Seq 0 on an empty log was {:?}.", other; Test)),
202 }
203 match res!(log.register_snap(&st, &mut idx, 0, ext("m"))) {
204 SnapReg::Same => (),
205 other => return Err(err!("A same-ext repeat at 0 was {:?}.", other; Test)),
206 }
207 match res!(log.register_snap(&st, &mut idx, 0, ext("other"))) {
208 SnapReg::Conflict { .. } => (),
209 other => return Err(err!("A different repeat at 0 was {:?}.", other; Test)),
210 }
211 // On a log with rows and no snap, seq 0 is refused.
212 let st2 = Mem::default();
213 let mut idx2 = res!(four(&st2, &log));
214 match res!(log.register_snap(&st2, &mut idx2, 0, ext("m"))) {
215 SnapReg::Behind { least } => assert_eq!(least, 1),
216 other => return Err(err!("Seq 0 on a log with rows was {:?}.", other; Test)),
217 }
218 assert!(idx2.snap.is_none());
219 Ok(())
220}
221
222#[test]
223fn a_read_below_low_answers_the_snapshot() -> Outcome<()> {
224 let st = Mem::default();
225 let log = SeqLog::new("i", "b:");
226 let mut idx = res!(four(&st, &log));
227 res!(log.register_snap(&st, &mut idx, 2, ext("s2")));
228 assert_eq!(res!(log.trim(&st, &mut idx, |_, _| true)), 2);
229 assert_eq!(idx.low, 3);
230 match res!(log.read(&st, &idx, 0, 10)) {
231 SeqRead::Gap { low, snap: Some(s) } => assert_eq!((low, s.seq, s.ext), (3, 2, ext("s2"))),
232 other => return Err(err!("Expected a gap with the snap, read {:?}.", other; Test)),
233 }
234 // From the snap's seq the tail reads whole.
235 assert_eq!(seqs(&res!(log.read(&st, &idx, 2, 10))), vec![3, 4]);
236 Ok(())
237}
238
239#[test]
240fn a_trim_never_cuts_above_the_snapshot_whatever_the_predicate() -> Outcome<()> {
241 let st = Mem::default();
242 let log = SeqLog::new("i", "b:");
243 let mut idx = res!(log.load(&st));
244 // Batches 1-5, 6-10, 11-12, 13-15, all old enough for any ttl.
245 for n in [5usize, 5, 2, 3] {
246 let names: Vec<&str> = std::iter::repeat("r").take(n).collect();
247 res!(log.append(&st, &mut idx, rows(&names), 0, n as u64));
248 }
249 res!(log.register_snap(&st, &mut idx, 10, ext("s10")));
250 // A ttl backstop that would cut everything, and that sees the snap.
251 let saw = std::cell::Cell::new(None);
252 assert_eq!(res!(log.trim(&st, &mut idx, |_, i| {
253 saw.set(i.snap.as_ref().map(|s| s.seq));
254 true
255 })), 2);
256 assert_eq!(saw.get(), Some(10), "the predicate sees the snap");
257 assert_eq!(idx.low, 11);
258 assert_eq!(seqs(&res!(log.read(&st, &idx, 10, 100))), (11..=15).collect::<Vec<u64>>());
259 // truncate_through goes through the same bound.
260 assert_eq!(res!(log.truncate_through(&st, &mut idx, 15)), 0);
261 assert_eq!(idx.low, 11);
262 Ok(())
263}
264
265#[test]
266fn a_trim_with_no_snapshot_keeps_everything() -> Outcome<()> {
267 let st = Mem::default();
268 let log = SeqLog::new("i", "b:");
269 let mut idx = res!(four(&st, &log));
270 assert_eq!(res!(log.trim(&st, &mut idx, |_, _| true)), 0);
271 assert_eq!(res!(log.truncate_through(&st, &mut idx, 4)), 0);
272 assert_eq!((idx.low, idx.batches.len()), (1, 4));
273 assert_eq!(seqs(&res!(log.read(&st, &idx, 0, 100))), vec![1, 2, 3, 4]);
274 Ok(())
275}
276
277#[test]
278fn an_eviction_cuts_with_no_snapshot_and_past_one() -> Outcome<()> {
279 let st = Mem::default();
280 let log = SeqLog::new("i", "b:");
281 let mut idx = res!(four(&st, &log));
282 // A bound on the index's length, counting down as batches go.
283 let mut count = idx.batches.len();
284 assert_eq!(res!(log.evict(&st, &mut idx, |_, _| { let over = count > 3; count -= 1; over })), 1);
285 assert_eq!((idx.low, idx.batches.len()), (2, 3));
286 assert!(matches!(res!(log.read(&st, &idx, 0, 10)), SeqRead::Gap { low: 2, snap: None }));
287 assert_eq!(res!(st.get(&log.batch_key(1))), None, "the evicted batch is still held");
288 // Past the snapshot: the gap carries it, and the rows between are gone.
289 res!(log.register_snap(&st, &mut idx, 2, ext("s2")));
290 assert_eq!(res!(log.evict(&st, &mut idx, |b, _| b.last <= 3)), 2);
291 match res!(log.read(&st, &res!(log.load(&st)), 2, 10)) {
292 SeqRead::Gap { low, snap: Some(s) } => assert_eq!((low, s.seq), (4, 2)),
293 other => return Err(err!("Expected a gap with the snap, read {:?}.", other; Test)),
294 }
295 assert_eq!(seqs(&res!(log.read(&st, &idx, 3, 10))), vec![4]);
296 Ok(())
297}
298
299#[test]
300fn each_row_reads_the_time_of_its_batch() -> Outcome<()> {
301 let st = Mem::default();
302 let log = SeqLog::new("i", "b:");
303 let mut idx = res!(four(&st, &log));
304 res!(log.append(&st, &mut idx, rows(&["e", "f"]), 50, 2));
305 let at: Vec<_> = (0..=7).map(|q| idx.at(q)).collect();
306 assert_eq!(at, vec![None, Some(1), Some(2), Some(3), Some(4), Some(50), Some(50), None]);
307 // An evicted batch's rows have no time; the rest keep theirs.
308 res!(log.evict(&st, &mut idx, |b, _| b.last <= 2));
309 assert_eq!((idx.at(2), idx.at(3), idx.at(6)), (None, Some(3), Some(50)));
310 Ok(())
311}
312
313#[test]
314fn an_append_at_any_other_head_writes_nothing() -> Outcome<()> {
315 let st = Mem::default();
316 let log = SeqLog::new("i", "b:");
317 let mut idx = res!(log.load(&st));
318 assert_eq!(res!(log.append_at(&st, &mut idx, rows(&["a", "b"]), 1, 2, 0)), Appended::At { first: 1 });
319 let before = st.map.borrow().clone();
320 // Behind (another writer got there) and ahead (the store lost rows the writer saw).
321 for expected in [0, 1, 9] {
322 assert_eq!(res!(log.append_at(&st, &mut idx, rows(&["x"]), 2, 1, expected)),
323 Appended::Moved { head: 2 });
324 }
325 assert_eq!(*st.map.borrow(), before, "a refused append wrote");
326 // A retry whose answer was lost: one read bounded by the batch shows it applied.
327 assert_eq!(seqs(&res!(log.read(&st, &idx, 0, 2))), vec![1, 2]);
328 // Neither a snapshot nor a trim moves the head.
329 res!(log.register_snap(&st, &mut idx, 2, ext("s2")));
330 assert_eq!(res!(log.append_at(&st, &mut idx, rows(&["c"]), 3, 1, 2)), Appended::At { first: 3 });
331 assert_eq!(res!(log.trim(&st, &mut idx, |_, _| true)), 1);
332 assert_eq!(res!(log.append_at(&st, &mut idx, rows(&["d"]), 4, 1, 2)), Appended::Moved { head: 3 });
333 Ok(())
334}
335
336#[test]
337fn an_append_cut_short_leaves_nothing_a_reader_sees() -> Outcome<()> {
338 let st = Mem::default();
339 let log = SeqLog::new("i", "b:");
340 let mut idx = res!(four(&st, &log));
341 // Stopped before the batch is written, then between the batch and the index.
342 for left in [0, 1] {
343 st.cut.set(Some(left));
344 assert!(log.append_at(&st, &mut idx, rows(&["x", "y", "z"]), 5, 3, 4).is_err());
345 st.cut.set(None);
346 idx = res!(log.load(&st));
347 assert_eq!(res!(st.get(&log.batch_key(5))).is_some(), left == 1);
348 assert_eq!(seqs(&res!(log.read(&st, &idx, 0, 10))), vec![1, 2, 3, 4]);
349 assert_eq!(seqs(&res!(log.read_back(&st, &idx, u64::MAX, 10))), vec![1, 2, 3, 4]);
350 }
351 // The same expected head appends over the leftover, a shorter batch replacing it whole.
352 assert_eq!(res!(log.append_at(&st, &mut idx, rows(&["p"]), 5, 1, 4)), Appended::At { first: 5 });
353 assert!(matches!(res!(log.read(&st, &idx, 4, 10)),
354 SeqRead::Rows { rows, more: false } if rows == vec![(5, ext("p"))]));
355 st.cut.set(Some(1));
356 assert!(log.append_at(&st, &mut idx, rows(&["r"]), 6, 1, 5).is_err());
357 st.cut.set(None);
358 res!(log.purge(&st, &res!(log.load(&st))));
359 assert!(st.map.borrow().is_empty(), "a purge left the cut-short batch");
360 Ok(())
361}
362
363#[test]
364fn read_back_pages_newest_first_reading_only_its_batches() -> Outcome<()> {
365 let st = Mem::default();
366 let log = SeqLog::new("i", "b:");
367 let mut idx = res!(log.load(&st));
368 assert!(matches!(res!(log.read_back(&st, &idx, u64::MAX, 10)),
369 SeqRead::Rows { ref rows, more: false } if rows.is_empty()));
370 let ten: Vec<&str> = std::iter::repeat("r").take(10).collect();
371 for i in 0..500 { res!(log.append(&st, &mut idx, rows(&ten), i, 10)); }
372 st.gets.set(0);
373 let t = std::time::Instant::now();
374 let page = res!(log.read_back(&st, &idx, u64::MAX, 50));
375 println!("read_back: 50 of 5,000 rows, {} lookups, {:?}", st.gets.get(), t.elapsed());
376 assert_eq!(st.gets.get(), 5, "a page reads only the batches it lies in");
377 assert_eq!(seqs(&page), (4951..=5000).collect::<Vec<u64>>());
378 assert!(matches!(page, SeqRead::Rows { more: true, .. }));
379 // Across a trim: the rows still held, then the snapshot.
380 res!(log.register_snap(&st, &mut idx, 100, ext("s100")));
381 assert_eq!(res!(log.truncate_through(&st, &mut idx, 100)), 10);
382 let page = res!(log.read_back(&st, &idx, 106, 50));
383 assert_eq!(seqs(&page), (101..=105).collect::<Vec<u64>>());
384 assert!(matches!(page, SeqRead::Rows { more: true, .. }), "the snapshot holds older rows");
385 assert!(matches!(res!(log.read_back(&st, &idx, 101, 50)),
386 SeqRead::Gap { low: 101, snap: Some(ref s) } if s.seq == 100));
387 // A trim cut short after its first delete: the rows above it, then a gap.
388 res!(st.delete(&log.batch_key(101)));
389 assert_eq!(seqs(&res!(log.read_back(&st, &idx, 116, 50))), (111..=115).collect::<Vec<u64>>());
390 assert!(matches!(res!(log.read_back(&st, &idx, 111, 50)), SeqRead::Gap { low: 111, .. }));
391 Ok(())
392}