rudb_native/
anchor.rs

1//! The log anchor, the `RUDBWL1` catalog extension of `engine-v4/03-the-shape.md` section 3.4.
2//!
3//! A file says how much of its log it already holds. Every commit at or below the durable cut is in
4//! the file's pages, and replay starts at each lane's segment and offset and skips any Commit at or
5//! below the cut. That is what makes the order of a checkpoint safe: the file is published first
6//! and the segments behind it are recycled after, and a crash between the two leaves segments whose
7//! commits the anchor already says are in.
8//!
9//! The void list is the one thing recovery writes here (`12-recovery.md` section 12.7): timestamps
10//! above the cut that were lost with a torn tail, which a later replay must never apply. It is
11//! written and read now and stays empty until recovery has lanes that can tear.
12
13use rudb_common::Result;
14
15use super::{Cursor, invalid, put_u32, put_u64};
16
17/// The magic the anchor block starts with, after the device card.
18pub(crate) const LOG_ANCHOR: &[u8; 8] = b"RUDBWL1\0";
19
20/// The one layout of the block, which a later one would change.
21const VERSION: u8 = 1;
22
23/// The most lanes a log has, `09-the-log.md` section 9.4.
24const MAX_LANES: usize = 64;
25
26/// The most void timestamps an anchor keeps.
27const MAX_VOIDS: usize = 1 << 16;
28
29/// Where replay of one lane starts.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
31pub struct LaneStart {
32    /// The segment's sequence.
33    pub sequence: u64,
34    /// The byte offset in it.
35    pub offset: u64,
36}
37
38/// How much of the log a file holds.
39#[derive(Debug, Clone, PartialEq, Eq, Default)]
40pub struct LogAnchor {
41    /// The id every segment header of this database's log carries.
42    pub database: u64,
43    /// The durable cut: every commit at or below it is in the file.
44    pub durable: u64,
45    /// Where replay starts, one entry per lane.
46    pub lanes: Vec<LaneStart>,
47    /// Timestamps above the cut that were lost and must never be replayed, in order.
48    pub voids: Vec<u64>,
49}
50
51impl LogAnchor {
52    /// Whether a commit at `ts` is one replay applies: above the cut and not void.
53    #[must_use]
54    pub fn replays(&self, ts: u64) -> bool {
55        ts > self.durable && self.voids.binary_search(&ts).is_err()
56    }
57
58    /// Appends the block, magic first.
59    pub(crate) fn encode(&self, out: &mut Vec<u8>) -> Result<()> {
60        if self.lanes.len() > MAX_LANES || self.voids.len() > MAX_VOIDS {
61            return Err(invalid("log anchor holds more lanes or voids than it can"));
62        }
63        out.extend_from_slice(LOG_ANCHOR);
64        out.push(VERSION);
65        put_u64(out, self.database);
66        put_u64(out, self.durable);
67        out.push(self.lanes.len() as u8);
68        for lane in &self.lanes {
69            put_u64(out, lane.sequence);
70            put_u64(out, lane.offset);
71        }
72        put_u32(out, self.voids.len() as u32);
73        for &ts in &self.voids {
74            put_u64(out, ts);
75        }
76        Ok(())
77    }
78
79    /// Reads the block after its magic.
80    pub(crate) fn decode(cur: &mut Cursor<'_>) -> Result<Self> {
81        if cur.u8()? != VERSION {
82            return Err(invalid("log anchor version differs"));
83        }
84        let database = cur.u64()?;
85        let durable = cur.u64()?;
86        let count = cur.u8()? as usize;
87        if count > MAX_LANES {
88            return Err(invalid("log anchor names more lanes than a log has"));
89        }
90        let mut lanes = Vec::with_capacity(count);
91        for _ in 0..count {
92            lanes.push(LaneStart { sequence: cur.u64()?, offset: cur.u64()? });
93        }
94        let count = cur.u32()? as usize;
95        if count > MAX_VOIDS {
96            return Err(invalid("log anchor holds more voids than it can"));
97        }
98        let mut voids = Vec::with_capacity(count);
99        for _ in 0..count {
100            voids.push(cur.u64()?);
101        }
102        if voids.windows(2).any(|pair| pair[0] >= pair[1])
103            || voids.first().is_some_and(|&ts| ts <= durable)
104        {
105            return Err(invalid("log anchor voids are out of order or under the cut"));
106        }
107        Ok(Self { database, durable, lanes, voids })
108    }
109}
rudb_native/anchor.rs

rudb_native/
anchor.rs
