Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/seqlog.rs

18.8 KiB, 21 runs

created by r1870400018:76232, 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

1//! A numbered append log over point lookups (30 Oct 2026, first caller Daimond's per-chat log).
2//!
3//! An Ozone store cannot prefix-scan on a request path: a walk of a whole prefix on a
4//! large store takes minutes. So a log here is one INDEX record naming every batch it
5//! holds, plus one record per appended batch, and every read and write is a point lookup.
6//! The store assigns the sequence numbers: a batch of `n` rows appended at head `h` holds
7//! `h+1..=h+n`, contiguous, and nothing a caller sends can choose them.
8//!
9//! The log takes no lock of its own. Every mutating call is a read-modify-write of the
10//! index, so the caller serialises the calls on one log (one mutex per log key); reads may
11//! run beside an append, because a batch is written before the index that names it.
12//!
13//! Snapshots. A caller that has folded the log to some seq stores that fold elsewhere and
14//! registers it here as a [`SnapRef`], carried in the index. A trim never cuts a row the
15//! registered snapshot does not cover, and with no snapshot it cuts nothing, so a reader
16//! that finds the rows above its cursor gone always gets a snapshot to resume from (the
17//! Kafka-compaction and Matrix-state shape).
18//!
19//! Eviction. A hard bound (an age, a size, the index's own length) may have to hold whatever
20//! is folded. [`SeqLog::evict`] cuts the oldest batches with no snapshot bound, for a caller
21//! whose readers re-base from a fold of their own outside the log; a reader below is answered
22//! [`SeqRead::Gap`], and when the registered snapshot no longer reaches `low - 1` the rows
23//! between it and `low` are gone for good.
24//!
25//! Crash order. An append writes the batch, then the index: a crash between leaves a
26//! batch no index names, at the key the next append overwrites. A trim deletes the
27//! batches, then rewrites the index: a crash between leaves an index naming a batch that
28//! is gone, which a reader answers as a gap. Nothing is ever unreachable and still held.
29
30use oxedyne_fe2o3_core::prelude::*;
31use oxedyne_fe2o3_jdat::{
32 prelude::*,
33 map::create_dat_ordmap,
34};
35
36use std::{
37 collections::HashMap,
38 sync::{
39 Arc,
40 Mutex,
41 },
42};
43
44/// The three point operations a log needs of a store.
45pub trait SeqStore {
46 fn get(&self, key: &Dat) -> Outcome<Option<Dat>>;
47 fn put(&self, key: Dat, val: Dat) -> Outcome<()>;
48 fn delete(&self, key: &Dat) -> Outcome<bool>;
49}
50
51/// One appended batch, as the index names it.
52#[derive(Clone, Debug, Eq, PartialEq)]
53pub struct BatchRef {
54 pub first: u64, // seq of the batch's first row
55 pub last: u64, // seq of its last row
56 pub at: i64, // when it was appended, in the caller's clock
57 pub bytes: u64, // the caller's measure of its size
58}
59
60/// A registered snapshot: the log folded through `seq`, stored by the caller, who names it
61/// in `ext` (chunk addresses, fingerprint, epoch), carried whole and never read here.
62#[derive(Clone, Debug, PartialEq)]
63pub struct SnapRef {
64 pub seq: u64, // the last seq the snapshot covers, 0 for an empty fold
65 pub ext: Dat, // the caller's description of it
66}
67
68/// The index record: where the log stands, which batches it holds, its snapshot, and the
69/// caller's own fields in `ext`, carried whole and never read here.
70#[derive(Clone, Debug)]
71pub struct SeqIndex {
72 pub head: u64, // last seq assigned, 0 for a new log
73 pub low: u64, // lowest seq still held, `head + 1` when none is
74 pub batches: Vec<BatchRef>, // oldest first
75 pub snap: Option<SnapRef>, // the registered snapshot, if any
76 pub ext: Dat, // the caller's fields, `Dat::Empty` when none
77}
78
79impl Default for SeqIndex {
80 fn default() -> Self {
81 Self { head: 0, low: 1, batches: Vec::new(), snap: None, ext: Dat::Empty }
82 }
83}
84
85impl SeqIndex {
86 /// The sum of the held batches' sizes.
87 pub fn bytes(&self) -> u64 {
88 self.batches.iter().map(|b| b.bytes).sum()
89 }
90
91 /// When the batch holding `seq` was appended, or `None` when no held batch holds it.
92 pub fn at(&self, seq: u64) -> Option<i64> {
93 let i = self.batches.partition_point(|b| b.last < seq);
94 self.batches.get(i).filter(|b| b.first <= seq).map(|b| b.at)
95 }
96
97 pub fn to_dat(&self) -> Dat {
98 let batches = self.batches.iter().map(|b| Dat::List(vec![
99 Dat::U64(b.first),
100 Dat::U64(b.last),
101 Dat::I64(b.at),
102 Dat::U64(b.bytes),
103 ])).collect();
104 let mut fields = vec![
105 (dat!("head"), Dat::U64(self.head)),
106 (dat!("low"), Dat::U64(self.low)),
107 (dat!("batches"), Dat::List(batches)),
108 (dat!("ext"), self.ext.clone()),
109 ];
110 if let Some(s) = &self.snap {
111 fields.push((dat!("snap"), Dat::List(vec![Dat::U64(s.seq), s.ext.clone()])));
112 }
113 create_dat_ordmap(fields)
114 }
115
116 pub fn from_dat(d: &Dat) -> Outcome<Self> {
117 let head = res!(d.map_get_u64(&dat!("head")));
118 let low = res!(d.map_get_u64(&dat!("low")));
119 let mut batches = Vec::new();
120 for (i, b) in res!(d.map_get_list(&dat!("batches"))).iter().enumerate() {
121 let parts = match b {
122 Dat::List(p) if p.len() == 4 => p,
123 _ => return Err(err!(
124 "seqlog: batch entry {} of the index is not a four-part list.", i;
125 Invalid, Input)),
126 };
127 let num = |j: usize| parts[j].get_u64().ok_or_else(|| err!(
128 "seqlog: part {} of batch entry {} is not a non-negative integer.", j, i;
129 Invalid, Input));
130 batches.push(BatchRef {
131 first: res!(num(0)),
132 last: res!(num(1)),
133 at: res!(parts[2].get_i64().ok_or_else(|| err!(
134 "seqlog: the time of batch entry {} is not an integer.", i;
135 Invalid, Input))),
136 bytes: res!(num(3)),
137 });
138 }
139 let ext = match res!(d.map_get(&dat!("ext"))) {
140 Some(e) => e.clone(),
141 None => Dat::Empty,
142 };
143 // An index written before snapshots existed has no "snap": it loads as none.
144 let snap = match res!(d.map_get(&dat!("snap"))) {
145 None => None,
146 Some(Dat::List(p)) if p.len() == 2 => Some(SnapRef {
147 seq: res!(p[0].get_u64().ok_or_else(|| err!(
148 "seqlog: the snap seq of the index is not a non-negative integer.";
149 Invalid, Input))),
150 ext: p[1].clone(),
151 }),
152 Some(_) => return Err(err!(
153 "seqlog: the snap of the index is not a two-part list."; Invalid, Input)),
154 };
155 Ok(Self { head, low, batches, snap, ext })
156 }
157}
158
159/// What a read finds above a cursor.
160#[derive(Clone, Debug)]
161pub enum SeqRead {
162 Gap { low: u64, snap: Option<SnapRef> }, // rows above the cursor are gone; resume from `snap`
163 Rows { rows: Vec<(u64, Dat)>, more: bool }, // `(seq, row)` in order; `more` when the limit stopped it
164}
165
166/// What an append that names the head it expects did.
167#[derive(Clone, Debug, PartialEq)]
168pub enum Appended {
169 At { first: u64 }, // appended: the seq of the batch's first row
170 Moved { head: u64 }, // refused, nothing written: the head found, below `expected`
171 // when the store lost rows the writer saw
172}
173
174/// What a snapshot registration did.
175#[derive(Clone, Debug, PartialEq)]
176pub enum SnapReg {
177 Registered { prev: Option<SnapRef> }, // stored; `prev` is the one it supersedes
178 Same, // the snapshot already registered: nothing written
179 Behind { least: u64 }, // refused: the lowest seq that would be accepted
180 Ahead { head: u64 }, // refused: beyond the log's head
181 Conflict { snap: SnapRef }, // refused: another snapshot holds this seq
182}
183
184/// One log: its index key and the prefix its batch keys take.
185#[derive(Clone, Debug)]
186pub struct SeqLog {
187 index: Dat,
188 prefix: String,
189}
190
191impl SeqLog {
192 /// A log whose index is at `index_key` and whose batches are at `batch_prefix` followed
193 /// by the batch's first seq.
194 pub fn new(index_key: &str, batch_prefix: &str) -> Self {
195 Self { index: dat!(index_key.to_string()), prefix: batch_prefix.to_string() }
196 }
197
198 pub fn index_key(&self) -> &Dat { &self.index }
199
200 pub fn batch_key(&self, first: u64) -> Dat {
201 dat!(fmt!("{}{}", self.prefix, first))
202 }
203
204 /// The index, or a new log's when none is stored.
205 pub fn load<S: SeqStore>(&self, store: &S) -> Outcome<SeqIndex> {
206 match res!(store.get(&self.index)) {
207 Some(d) => SeqIndex::from_dat(&d),
208 None => Ok(SeqIndex::default()),
209 }
210 }
211
212 /// Store the index as it stands, for a change to `ext` alone.
213 pub fn save<S: SeqStore>(&self, store: &S, idx: &SeqIndex) -> Outcome<()> {
214 store.put(self.index.clone(), idx.to_dat())
215 }
216
217 /// Append `rows` as one batch, answering the seq of its first row. The caller holds
218 /// the log's lock. An empty batch writes nothing and answers `head + 1`.
219 pub fn append<S: SeqStore>(
220 &self,
221 store: &S,
222 idx: &mut SeqIndex,
223 rows: Vec<Dat>,
224 at: i64,
225 bytes: u64,
226 )
227 -> Outcome<u64>
228 {
229 let head = idx.head;
230 match res!(self.append_at(store, idx, rows, at, bytes, head)) {
231 Appended::At { first } => Ok(first),
232 Appended::Moved { head } => Err(err!(
233 "seqlog: an append at the index's own head {} was refused.", head; Bug)),
234 }
235 }
236
237 /// [`SeqLog::append`] only while the head is `expected`, tested under the log's lock,
238 /// which the caller holds; any other head answers [`Appended::Moved`] and writes nothing.
239 pub fn append_at<S: SeqStore>(
240 &self,
241 store: &S,
242 idx: &mut SeqIndex,
243 rows: Vec<Dat>,
244 at: i64,
245 bytes: u64,
246 expected: u64,
247 )
248 -> Outcome<Appended>
249 {
250 if idx.head != expected {
251 return Ok(Appended::Moved { head: idx.head });
252 }
253 let first = idx.head + 1;
254 if rows.is_empty() {
255 return Ok(Appended::At { first });
256 }
257 let last = idx.head + rows.len() as u64;
258 let batch = create_dat_ordmap(vec![
259 (dat!("first"), Dat::U64(first)),
260 (dat!("rows"), Dat::List(rows)),
261 ]);
262 res!(store.put(self.batch_key(first), batch));
263 if idx.batches.is_empty() {
264 idx.low = first;
265 }
266 idx.head = last;
267 idx.batches.push(BatchRef { first, last, at, bytes });
268 res!(self.save(store, idx));
269 Ok(Appended::At { first })
270 }
271
272 /// The rows above `since` (the last seq the reader holds), at most `max_rows` of them.
273 /// A cursor below what the log still holds answers [`SeqRead::Gap`].
274 pub fn read<S: SeqStore>(&self, store: &S, idx: &SeqIndex, since: u64, max_rows: usize)
275 -> Outcome<SeqRead>
276 {
277 if since >= idx.head {
278 return Ok(SeqRead::Rows { rows: Vec::new(), more: false });
279 }
280 if since + 1 < idx.low {
281 return Ok(SeqRead::Gap { low: idx.low, snap: idx.snap.clone() });
282 }
283 let mut rows = Vec::new();
284 for b in idx.batches.iter().filter(|b| b.last > since) {
285 let rec = match res!(store.get(&self.batch_key(b.first))) {
286 Some(d) => d,
287 // Deleted by a trim whose index write did not land: the rows are gone.
288 None => return Ok(SeqRead::Gap { low: b.last + 1, snap: idx.snap.clone() }),
289 };
290 let list = res!(rec.map_get_list(&dat!("rows")));
291 for (i, row) in list.iter().enumerate() {
292 let seq = b.first + i as u64;
293 if seq <= since {
294 continue;
295 }
296 if rows.len() >= max_rows {
297 return Ok(SeqRead::Rows { rows, more: true });
298 }
299 rows.push((seq, row.clone()));
300 }
301 }
302 Ok(SeqRead::Rows { rows, more: false })
303 }
304
305 /// The newest rows below `before` (`u64::MAX` for the head), at most `max_rows` of them,
306 /// in seq order, reading only the batches they lie in. `more` says older rows exist, held
307 /// or folded into the snapshot; once trimmed, a `before` at or below `low` answers
308 /// [`SeqRead::Gap`], and so does a missing batch the page would start in.
309 pub fn read_back<S: SeqStore>(&self, store: &S, idx: &SeqIndex, before: u64, max_rows: usize)
310 -> Outcome<SeqRead>
311 {
312 let before = std::cmp::min(before, idx.head + 1);
313 let mut rows = Vec::new();
314 for b in idx.batches.iter().rev().filter(|b| b.first < before) {
315 if rows.len() >= max_rows {
316 break;
317 }
318 let rec = match res!(store.get(&self.batch_key(b.first))) {
319 Some(d) => d,
320 None if rows.is_empty() =>
321 return Ok(SeqRead::Gap { low: b.last + 1, snap: idx.snap.clone() }),
322 None => break,
323 };
324 let list = res!(rec.map_get_list(&dat!("rows")));
325 for (i, row) in list.iter().enumerate().rev() {
326 let seq = b.first + i as u64;
327 if seq < before && rows.len() < max_rows {
328 rows.push((seq, row.clone()));
329 }
330 }
331 }
332 if rows.is_empty() && before <= idx.low && idx.low > 1 {
333 return Ok(SeqRead::Gap { low: idx.low, snap: idx.snap.clone() });
334 }
335 rows.reverse();
336 let more = rows.first().map(|(s, _)| *s > 1).unwrap_or(false);
337 Ok(SeqRead::Rows { rows, more })
338 }
339
340 /// Register a snapshot of the log folded through `seq`. The caller holds the log's lock.
341 /// It must lie above the current snapshot, at or below the head, and no lower than the
342 /// row before `low`, so that the rows above it are all still held; seq 0 is accepted
343 /// only on an empty log. A repeat of the registered snapshot answers [`SnapReg::Same`].
344 pub fn register_snap<S: SeqStore>(&self, store: &S, idx: &mut SeqIndex, seq: u64, ext: Dat)
345 -> Outcome<SnapReg>
346 {
347 if let Some(s) = &idx.snap {
348 if seq == s.seq {
349 return Ok(if s.ext == ext { SnapReg::Same } else { SnapReg::Conflict { snap: s.clone() } });
350 }
351 }
352 if seq > idx.head {
353 return Ok(SnapReg::Ahead { head: idx.head });
354 }
355 let least = match &idx.snap {
356 Some(s) => s.seq + 1,
357 None if idx.head == 0 => 0,
358 None => 1,
359 };
360 let least = std::cmp::max(least, idx.low.saturating_sub(1));
361 if seq < least {
362 return Ok(SnapReg::Behind { least });
363 }
364 let prev = idx.snap.replace(SnapRef { seq, ext });
365 res!(self.save(store, idx));
366 Ok(SnapReg::Registered { prev })
367 }
368
369 /// Drop the oldest batches while `drop` holds for them, answering how many went. Only
370 /// batches the registered snapshot covers are ever dropped, and with no snapshot none
371 /// is; `drop` sees the index, snapshot included, for the caller's own bounds. The
372 /// caller holds the log's lock.
373 pub fn trim<S, F>(&self, store: &S, idx: &mut SeqIndex, drop: F) -> Outcome<usize>
374 where
375 S: SeqStore,
376 F: Fn(&BatchRef, &SeqIndex) -> bool,
377 {
378 let cover = match &idx.snap {
379 Some(s) => s.seq,
380 None => return Ok(0),
381 };
382 let mut n = 0;
383 while n < idx.batches.len()
384 && idx.batches[n].last <= cover
385 && drop(&idx.batches[n], idx)
386 {
387 n += 1;
388 }
389 self.cut(store, idx, n)
390 }
391
392 /// Drop the oldest batches while `drop` holds for them, answering how many went, whatever
393 /// the snapshot covers: the hard bound of the module's Eviction. `drop` is called once a
394 /// batch, oldest first, with the index as it stood. The caller holds the log's lock.
395 pub fn evict<S, F>(&self, store: &S, idx: &mut SeqIndex, mut drop: F) -> Outcome<usize>
396 where
397 S: SeqStore,
398 F: FnMut(&BatchRef, &SeqIndex) -> bool,
399 {
400 let mut n = 0;
401 while n < idx.batches.len() && drop(&idx.batches[n], idx) {
402 n += 1;
403 }
404 self.cut(store, idx, n)
405 }
406
407 /// Delete the oldest `n` batches, then rewrite the index (the module's crash order).
408 fn cut<S: SeqStore>(&self, store: &S, idx: &mut SeqIndex, n: usize) -> Outcome<usize> {
409 if n == 0 {
410 return Ok(0);
411 }
412 for b in &idx.batches[..n] {
413 res!(store.delete(&self.batch_key(b.first)));
414 }
415 idx.batches.drain(..n);
416 idx.low = match idx.batches.first() {
417 Some(b) => b.first,
418 None => idx.head + 1,
419 };
420 res!(self.save(store, idx));
421 Ok(n)
422 }
423
424 /// Drop the oldest batches holding seqs up to and including `seq`, within the bound
425 /// [`SeqLog::trim`] keeps.
426 pub fn truncate_through<S: SeqStore>(&self, store: &S, idx: &mut SeqIndex, seq: u64)
427 -> Outcome<usize>
428 {
429 self.trim(store, idx, |b, _| b.last <= seq)
430 }
431
432 /// Delete every batch and the index, and a batch a cut-short append left above the head.
433 pub fn purge<S: SeqStore>(&self, store: &S, idx: &SeqIndex) -> Outcome<()> {
434 for b in &idx.batches {
435 res!(store.delete(&self.batch_key(b.first)));
436 }
437 res!(store.delete(&self.batch_key(idx.head + 1)));
438 res!(store.delete(&self.index));
439 Ok(())
440 }
441}
442
443/// One mutex per log key, held only while some caller is inside it, so the map is bounded
444/// by the logs in use rather than every log ever touched.
445#[derive(Default)]
446pub struct SeqLocks {
447 map: Mutex<HashMap<String, Arc<Mutex<()>>>>,
448}
449
450impl SeqLocks {
451 pub fn new() -> Self { Self::default() }
452
453 /// Run `f` holding the lock for `key`.
454 pub fn with<T, F>(&self, key: &str, f: F) -> Outcome<T>
455 where
456 F: FnOnce() -> Outcome<T>,
457 {
458 let one = {
459 let mut map = lock_mutex!(self.map);
460 map.entry(key.to_string()).or_insert_with(|| Arc::new(Mutex::new(()))).clone()
461 };
462 let out = {
463 let _held = lock_mutex!(one);
464 f()
465 };
466 drop(one);
467 // The entry goes once the map holds the only handle: nobody waits on it.
468 let mut map = lock_mutex!(self.map);
469 if map.get(key).map(|m| Arc::strong_count(m) == 1).unwrap_or(false) {
470 map.remove(key);
471 }
472 out
473 }
474
475 /// How many keys are currently held or waited on.
476 pub fn len(&self) -> Outcome<usize> {
477 Ok(lock_mutex!(self.map).len())
478 }
479}