Skip to main content

memfork_core/
journal.rs

1//! The write-ahead journal seam (DESIGN §4.5).
2//!
3//! The engine does no I/O. When a caller wants durability it supplies a
4//! [`Journal`], and the engine hands it one [`Record`] per change *before* the
5//! change becomes visible. If the process dies between the append and the
6//! head swap, replaying the record reproduces the same state; if it dies
7//! before the append, the change never happened. Either way there is no state
8//! a reader could have seen that recovery cannot rebuild.
9//!
10//! **Commit ids are never written down.** A record carries the parents, the
11//! message and the operations, and replay recomputes the id from them exactly
12//! as the original commit did. That is what makes "recovery reproduces
13//! identical commit ids" a property worth testing rather than a tautology
14//! about copying bytes back.
15//!
16//! Encoding lives here, beside the record it encodes, but produces bytes
17//! rather than writing them: where those bytes go is the caller's business.
18
19use core::fmt;
20
21use smallvec::SmallVec;
22
23use crate::encode::Bytes;
24use crate::entry::{Op, Value};
25use crate::id::CommitId;
26
27/// One durable change to the database.
28#[derive(Debug, Clone, PartialEq)]
29pub enum Record {
30    /// A commit was made on a branch.
31    Commit {
32        /// The branch whose head moved to this commit.
33        branch: String,
34        /// The commit's parents.
35        parents: SmallVec<[CommitId; 2]>,
36        /// The commit's sequence number on that branch.
37        seq: u64,
38        /// The commit message.
39        message: Option<String>,
40        /// The change set.
41        ops: Vec<Op>,
42    },
43    /// A branch was created, pointing at an existing commit.
44    BranchCreated {
45        /// The new branch's name.
46        name: String,
47        /// The commit it points at.
48        at: CommitId,
49    },
50    /// A branch was deleted.
51    BranchDiscarded {
52        /// The branch that was deleted.
53        name: String,
54    },
55    /// A branch head moved without a new commit, as a fast-forward merge does.
56    HeadMoved {
57        /// The branch whose head moved.
58        branch: String,
59        /// Where it moved to.
60        to: CommitId,
61    },
62}
63
64/// Somewhere durable to put records.
65///
66/// `append` returns only when the record is as durable as the journal's policy
67/// promises. A journal that buffers must say so in its own documentation,
68/// because the engine treats a successful append as "this will survive".
69pub trait Journal: Send + Sync + fmt::Debug {
70    /// Record one change. An error aborts the change that provoked it.
71    fn append(&self, record: &Record) -> Result<(), JournalError>;
72}
73
74/// Why a record could not be recorded.
75#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
76#[error("cannot record the change durably: {0}")]
77pub struct JournalError(pub String);
78
79impl JournalError {
80    /// A journal failure with the given reason.
81    pub fn new(reason: impl Into<String>) -> Self {
82        JournalError(reason.into())
83    }
84}
85
86/// Tag bytes. Explicit rather than derived from declaration order, so
87/// reordering the enum cannot silently change the format.
88mod tag {
89    pub const COMMIT: u8 = 1;
90    pub const BRANCH_CREATED: u8 = 2;
91    pub const BRANCH_DISCARDED: u8 = 3;
92    pub const HEAD_MOVED: u8 = 4;
93}
94
95/// Encode a record to bytes.
96pub fn encode(record: &Record) -> Vec<u8> {
97    let mut b = Bytes::new();
98    match record {
99        Record::Commit {
100            branch,
101            parents,
102            seq,
103            message,
104            ops,
105        } => {
106            b.u8(tag::COMMIT);
107            b.str(branch);
108            b.u64(parents.len() as u64);
109            for p in parents {
110                b.commit_id(p);
111            }
112            b.u64(*seq);
113            b.opt_str(message.as_deref());
114            b.u64(ops.len() as u64);
115            for op in ops {
116                encode_op(&mut b, op);
117            }
118        }
119        Record::BranchCreated { name, at } => {
120            b.u8(tag::BRANCH_CREATED);
121            b.str(name);
122            b.commit_id(at);
123        }
124        Record::BranchDiscarded { name } => {
125            b.u8(tag::BRANCH_DISCARDED);
126            b.str(name);
127        }
128        Record::HeadMoved { branch, to } => {
129            b.u8(tag::HEAD_MOVED);
130            b.str(branch);
131            b.commit_id(to);
132        }
133    }
134    b.into_vec()
135}
136
137fn encode_op(b: &mut Bytes, op: &Op) {
138    match op {
139        Op::Put { key, value } => {
140            b.u8(1);
141            b.str(key);
142            b.bytes(&value.value);
143            match &value.embedding {
144                None => b.u8(0),
145                Some(v) => {
146                    b.u8(1);
147                    b.u64(v.len() as u64);
148                    for x in v {
149                        b.f32(*x);
150                    }
151                }
152            }
153            b.f32(value.importance);
154            b.opt_u64(value.ttl_commits);
155            b.u64(value.meta.len() as u64);
156            for (k, v) in &value.meta {
157                b.str(k);
158                b.str(v);
159            }
160        }
161        Op::Delete { key } => {
162            b.u8(2);
163            b.str(key);
164        }
165        Op::Evict { key } => {
166            b.u8(3);
167            b.str(key);
168        }
169    }
170}
171
172/// Why a record could not be read back.
173#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
174pub enum DecodeError {
175    /// The bytes ran out before the record did.
176    #[error("the record is truncated: wanted {wanted} more byte(s) at offset {at}")]
177    Truncated {
178        /// Where the read stopped.
179        at: usize,
180        /// How many more bytes were needed.
181        wanted: usize,
182    },
183    /// A tag byte named something this version does not know.
184    #[error("unknown {what} tag {tag} at offset {at}")]
185    UnknownTag {
186        /// What was being read.
187        what: &'static str,
188        /// The tag that was found.
189        tag: u8,
190        /// Where it was found.
191        at: usize,
192    },
193    /// A string was not UTF-8.
194    #[error("a string in the record is not valid UTF-8, at offset {at}")]
195    BadUtf8 {
196        /// Where the string started.
197        at: usize,
198    },
199    /// The record decoded, but bytes were left over.
200    #[error("{extra} byte(s) left over after the record")]
201    TrailingBytes {
202        /// How many bytes were left.
203        extra: usize,
204    },
205    /// A length field was larger than the data that follows could possibly be.
206    #[error("a length field claims {claimed} items, which the record cannot hold")]
207    ImplausibleLength {
208        /// The length that was claimed.
209        claimed: u64,
210    },
211}
212
213/// Decode a record from bytes.
214pub fn decode(bytes: &[u8]) -> Result<Record, DecodeError> {
215    let mut r = Reader::new(bytes);
216    let record = decode_record(&mut r)?;
217    if r.remaining() != 0 {
218        return Err(DecodeError::TrailingBytes {
219            extra: r.remaining(),
220        });
221    }
222    Ok(record)
223}
224
225fn decode_record(r: &mut Reader<'_>) -> Result<Record, DecodeError> {
226    let at = r.pos;
227    match r.u8()? {
228        tag::COMMIT => {
229            let branch = r.str()?;
230            let count = r.count()?;
231            let mut parents = SmallVec::new();
232            for _ in 0..count {
233                parents.push(r.commit_id()?);
234            }
235            let seq = r.u64()?;
236            let message = r.opt_str()?;
237            let op_count = r.count()?;
238            let mut ops = Vec::with_capacity(op_count.min(1024));
239            for _ in 0..op_count {
240                ops.push(decode_op(r)?);
241            }
242            Ok(Record::Commit {
243                branch,
244                parents,
245                seq,
246                message,
247                ops,
248            })
249        }
250        tag::BRANCH_CREATED => Ok(Record::BranchCreated {
251            name: r.str()?,
252            at: r.commit_id()?,
253        }),
254        tag::BRANCH_DISCARDED => Ok(Record::BranchDiscarded { name: r.str()? }),
255        tag::HEAD_MOVED => Ok(Record::HeadMoved {
256            branch: r.str()?,
257            to: r.commit_id()?,
258        }),
259        tag => Err(DecodeError::UnknownTag {
260            what: "record",
261            tag,
262            at,
263        }),
264    }
265}
266
267fn decode_op(r: &mut Reader<'_>) -> Result<Op, DecodeError> {
268    let at = r.pos;
269    match r.u8()? {
270        1 => {
271            let key = r.str()?;
272            let value = bytes::Bytes::from(r.bytes()?.to_vec());
273            let embedding = match r.u8()? {
274                0 => None,
275                1 => {
276                    let n = r.count()?;
277                    let mut v = Vec::with_capacity(n.min(4096));
278                    for _ in 0..n {
279                        v.push(r.f32()?);
280                    }
281                    Some(v)
282                }
283                tag => {
284                    return Err(DecodeError::UnknownTag {
285                        what: "embedding presence",
286                        tag,
287                        at: r.pos,
288                    })
289                }
290            };
291            let importance = r.f32()?;
292            let ttl_commits = r.opt_u64()?;
293            let meta_count = r.count()?;
294            let mut meta = std::collections::BTreeMap::new();
295            for _ in 0..meta_count {
296                let k = r.str()?;
297                let v = r.str()?;
298                meta.insert(k, v);
299            }
300            Ok(Op::Put {
301                key,
302                value: Value {
303                    value,
304                    embedding,
305                    importance,
306                    ttl_commits,
307                    meta,
308                },
309            })
310        }
311        2 => Ok(Op::Delete { key: r.str()? }),
312        3 => Ok(Op::Evict { key: r.str()? }),
313        tag => Err(DecodeError::UnknownTag {
314            what: "operation",
315            tag,
316            at,
317        }),
318    }
319}
320
321/// A bounds-checked cursor over a record's bytes.
322struct Reader<'a> {
323    bytes: &'a [u8],
324    pos: usize,
325}
326
327impl<'a> Reader<'a> {
328    fn new(bytes: &'a [u8]) -> Self {
329        Reader { bytes, pos: 0 }
330    }
331
332    fn remaining(&self) -> usize {
333        self.bytes.len() - self.pos
334    }
335
336    fn take(&mut self, n: usize) -> Result<&'a [u8], DecodeError> {
337        if self.remaining() < n {
338            return Err(DecodeError::Truncated {
339                at: self.pos,
340                wanted: n - self.remaining(),
341            });
342        }
343        let out = &self.bytes[self.pos..self.pos + n];
344        self.pos += n;
345        Ok(out)
346    }
347
348    fn u8(&mut self) -> Result<u8, DecodeError> {
349        Ok(self.take(1)?[0])
350    }
351
352    fn u64(&mut self) -> Result<u64, DecodeError> {
353        let b = self.take(8)?;
354        let mut a = [0u8; 8];
355        a.copy_from_slice(b);
356        Ok(u64::from_le_bytes(a))
357    }
358
359    fn f32(&mut self) -> Result<f32, DecodeError> {
360        let b = self.take(4)?;
361        let mut a = [0u8; 4];
362        a.copy_from_slice(b);
363        Ok(f32::from_bits(u32::from_le_bytes(a)))
364    }
365
366    /// A count of items still to be read.
367    ///
368    /// Rejected up front when it exceeds what the remaining bytes could hold,
369    /// so a corrupted length cannot make the decoder allocate wildly before it
370    /// notices the record is short.
371    fn count(&mut self) -> Result<usize, DecodeError> {
372        let claimed = self.u64()?;
373        if claimed > self.remaining() as u64 {
374            return Err(DecodeError::ImplausibleLength { claimed });
375        }
376        Ok(claimed as usize)
377    }
378
379    fn bytes(&mut self) -> Result<&'a [u8], DecodeError> {
380        let n = self.count()?;
381        self.take(n)
382    }
383
384    fn str(&mut self) -> Result<String, DecodeError> {
385        let at = self.pos;
386        let b = self.bytes()?;
387        core::str::from_utf8(b)
388            .map(str::to_owned)
389            .map_err(|_| DecodeError::BadUtf8 { at })
390    }
391
392    fn opt_str(&mut self) -> Result<Option<String>, DecodeError> {
393        match self.u8()? {
394            0 => Ok(None),
395            1 => Ok(Some(self.str()?)),
396            tag => Err(DecodeError::UnknownTag {
397                what: "optional string presence",
398                tag,
399                at: self.pos,
400            }),
401        }
402    }
403
404    fn opt_u64(&mut self) -> Result<Option<u64>, DecodeError> {
405        match self.u8()? {
406            0 => Ok(None),
407            1 => Ok(Some(self.u64()?)),
408            tag => Err(DecodeError::UnknownTag {
409                what: "optional number presence",
410                tag,
411                at: self.pos,
412            }),
413        }
414    }
415
416    fn commit_id(&mut self) -> Result<CommitId, DecodeError> {
417        let b = self.take(32)?;
418        let mut a = [0u8; 32];
419        a.copy_from_slice(b);
420        Ok(CommitId::from_bytes(a))
421    }
422}