kevy_embedded/
ops_reconcile.rs

1//! Reconcile derived keys against the rows that imply them.
2//!
3//! A consumer asked for this: they had to write boot-time verification
4//! that rebuilds every derived key from the rows and diffs, and observed
5//! that everyone maintaining link or claim keys needs exactly the same
6//! thing and will write it slightly differently and slightly wrong.
7//!
8//! The recipe it checks is `docs/cookbook.md` §21 — derived state as a
9//! pure function of the row. Pass that same function here and the
10//! checker is the function; there is nothing to keep in step.
11//!
12//! Two things a hand-rolled version usually gets wrong, both handled
13//! here by construction:
14//!
15//! 1. **It scans the live keyspace**, so a write landing mid-scan is
16//!    reported as drift. This runs against a [`Snapshot`], which is
17//!    frozen under every shard lock, so a clean system is always clean.
18//! 2. **It only looks for missing keys.** A claim left behind by a
19//!    half-applied update is an orphan, not an absence, and it is the
20//!    failure that silently blocks a later insert. This diffs both ways.
21
22use crate::ops_snapshot_view::Snapshot;
23use std::collections::HashSet;
24
25/// How many example keys each direction of the diff carries. Counts are
26/// exact regardless; the samples exist to be actionable in a log line,
27/// not to be a second copy of the keyspace.
28const MAX_SAMPLES: usize = 1000;
29
30/// The result of [`Snapshot::reconcile`].
31#[derive(Debug, Default, Clone)]
32pub struct ReconcileReport {
33    /// Rows visited under the row prefix.
34    pub rows: u64,
35    /// Distinct derived keys the rows imply.
36    pub expected: u64,
37    /// Implied by a row, absent from the store — lost derived state.
38    /// Exact count; `missing` holds up to [`MAX_SAMPLES`] examples.
39    pub missing_count: u64,
40    /// Example missing keys.
41    pub missing: Vec<Vec<u8>>,
42    /// Present under a derived prefix but implied by no row — a claim
43    /// or link left behind. Exact count; `orphaned` holds examples.
44    pub orphaned_count: u64,
45    /// Example orphaned keys.
46    pub orphaned: Vec<Vec<u8>>,
47}
48
49impl ReconcileReport {
50    /// Whether the rows and their derived keys agree exactly.
51    pub fn is_clean(&self) -> bool {
52        self.missing_count == 0 && self.orphaned_count == 0
53    }
54
55    /// Whether the sample lists were cut short — the counts are still
56    /// exact, so a caller logging only samples should say so.
57    pub fn truncated(&self) -> bool {
58        self.missing.len() as u64 != self.missing_count
59            || self.orphaned.len() as u64 != self.orphaned_count
60    }
61}
62
63impl Snapshot {
64    /// Rebuild every derived key from the rows under `rows_prefix` and
65    /// diff it against what actually exists under `derived_prefixes`.
66    ///
67    /// `derived` is the function from a row to the keys it implies —
68    /// the same one the write path uses (cookbook §21). Whatever it
69    /// returns for a row is what that row is entitled to; anything else
70    /// under `derived_prefixes` is an orphan.
71    ///
72    /// `derived_prefixes` must cover everywhere derived keys live. A
73    /// derived key outside them is invisible to both directions of the
74    /// diff: it cannot be reported missing (nothing looks for it) and
75    /// it cannot be reported orphaned (nothing enumerates it). This is
76    /// the one way to get a falsely clean report, so the prefixes are a
77    /// required argument rather than an option with a default.
78    ///
79    /// The snapshot is frozen, so a clean system reports clean no
80    /// matter what writers are doing.
81    ///
82    /// ```no_run
83    /// # use kevy_embedded::{Store, Config};
84    /// # let store = Store::open(Config::default()).unwrap();
85    /// let report = store.snapshot().reconcile(
86    ///     b"user:",
87    ///     &[b"email:", b"dept:"],
88    ///     |key, _row| vec![[b"email:".as_slice(), key].concat()],
89    /// );
90    /// assert!(report.is_clean());
91    /// ```
92    pub fn reconcile(
93        &self,
94        rows_prefix: &[u8],
95        derived_prefixes: &[&[u8]],
96        mut derived: impl FnMut(&[u8], &kevy_store::Value) -> Vec<Vec<u8>>,
97    ) -> ReconcileReport {
98        let mut report = ReconcileReport::default();
99        let mut expected: HashSet<Vec<u8>> = HashSet::new();
100        self.each_prefix(rows_prefix, |k, v, _ttl| {
101            report.rows += 1;
102            expected.extend(derived(k, v));
103        });
104        report.expected = expected.len() as u64;
105
106        let mut present: HashSet<Vec<u8>> = HashSet::new();
107        for p in derived_prefixes {
108            self.each_prefix(p, |k, _v, _ttl| {
109                present.insert(k.to_vec());
110            });
111        }
112
113        collect(expected.difference(&present), &mut report.missing_count, &mut report.missing);
114        collect(present.difference(&expected), &mut report.orphaned_count, &mut report.orphaned);
115        report
116    }
117}
118
119/// Count everything, keep the first [`MAX_SAMPLES`].
120fn collect<'a>(
121    keys: impl Iterator<Item = &'a Vec<u8>>,
122    count: &mut u64,
123    samples: &mut Vec<Vec<u8>>,
124) {
125    for k in keys {
126        *count += 1;
127        if samples.len() < MAX_SAMPLES {
128            samples.push(k.clone());
129        }
130    }
131}
kevy_embedded/ops_reconcile.rs

kevy_embedded/
ops_reconcile.rs
