uqa_storage/mvcc/
tombstones.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Scoped physical tombstone retirement preserves absence observations through epochs.
8
9use uqa_core::memory::BudgetedVec;
10
11use crate::read_control::StorageReadControl;
12
13use super::{CommitSequence, VersionError, VersionResult};
14
15mod conformance;
16pub use conformance::{verify_tombstone_reclamation, verify_tombstone_reclamation_pages};
17mod maintenance;
18pub use maintenance::{reclaim_key_value_diskann_tombstones, reclaim_tombstone_prefix};
19
20/// Autonomous metadata namespaces; providers update them in the same physical transaction as tombstone deletion, without advancing record visibility or transaction allocation.
21pub const RECLAMATION_EPOCH_NAMESPACE: &[u8] = b"\0uqa-reclamation-epoch-v1\0";
22pub const RECLAMATION_DOMAIN_PREFIX: &[u8] = b"\0uqa-reclamation-domain-v1\0";
23pub const TOMBSTONE_RECLAMATION_PAGE: usize = 64;
24
25/// One finite pass keeps its original prefix and visibility cutoff. Later writes cannot join its candidate set; each step visits at most 64 eligible metadata entries. Run ordinary history reclamation first: only fully pruned current tombstones may be retired.
26pub struct TombstoneReclamationRequest<'a> {
27    pub prefix: &'a [u8],
28    pub after: Option<&'a [u8]>,
29    pub through: CommitSequence,
30}
31
32impl TombstoneReclamationRequest<'_> {
33    pub fn validate(&self, control: &StorageReadControl) -> VersionResult<()> {
34        control.check()?;
35        if self.prefix.is_empty()
36            || self.prefix.len() > 1024
37            || self.after.is_some_and(|key| !key.starts_with(self.prefix))
38        {
39            return Err(VersionError::InvalidEncoding(
40                "invalid tombstone reclamation range",
41            ));
42        }
43        Ok(())
44    }
45
46    pub fn domain_namespace(&self, control: &StorageReadControl) -> VersionResult<BudgetedVec<u8>> {
47        self.validate(control)?;
48        let mut namespace = BudgetedVec::new(control.memory());
49        namespace.extend_from_slice(RECLAMATION_DOMAIN_PREFIX)?;
50        namespace.extend_from_slice(self.prefix)?;
51        Ok(namespace)
52    }
53}
54
55pub enum TombstoneReclamationStep {
56    /// A live snapshot retains exact revision identities, including deleted rows. Stop this pass and reconsider on the next maintenance invocation.
57    Retained,
58    Complete {
59        removed: usize,
60    },
61    More {
62        after: BudgetedVec<u8>,
63        removed: usize,
64    },
65}
66
67/// Charged metadata for one bounded provider page; graph payloads and old histories never enter this workspace.
68pub struct TombstoneReclamationPage {
69    keys: BudgetedVec<(BudgetedVec<u8>, u64)>,
70    after: BudgetedVec<u8>,
71    inspected: usize,
72}
73
74impl TombstoneReclamationPage {
75    pub fn new(control: &StorageReadControl) -> VersionResult<Self> {
76        control.check()?;
77        let mut keys = BudgetedVec::new(control.memory());
78        keys.reserve(TOMBSTONE_RECLAMATION_PAGE)?;
79        Ok(Self {
80            keys,
81            after: BudgetedVec::new(control.memory()),
82            inspected: 0,
83        })
84    }
85
86    /// Record an eligible identity in key order. Providers may retire only a deleted head whose older history has already been reclaimed.
87    pub fn visit(
88        &mut self,
89        key: &[u8],
90        revision: u64,
91        retire: bool,
92        control: &StorageReadControl,
93    ) -> VersionResult<()> {
94        control.check()?;
95        if self.is_full() || (self.inspected != 0 && key <= &*self.after) {
96            return Err(VersionError::InvalidEncoding(
97                "invalid tombstone page order",
98            ));
99        }
100        self.after.clear();
101        self.after.extend_from_slice(key)?;
102        if retire {
103            let mut owned = BudgetedVec::new(control.memory());
104            owned.extend_from_slice(key)?;
105            self.keys.push((owned, revision))?;
106        }
107        self.inspected += 1;
108        Ok(())
109    }
110
111    pub fn is_full(&self) -> bool {
112        self.inspected == TOMBSTONE_RECLAMATION_PAGE
113    }
114
115    pub fn retired(&self) -> impl ExactSizeIterator<Item = (&[u8], u64)> {
116        self.keys.iter().map(|(key, revision)| (&**key, *revision))
117    }
118
119    pub fn finish(self) -> TombstoneReclamationStep {
120        let removed = self.keys.len();
121        if self.is_full() {
122            TombstoneReclamationStep::More {
123                after: self.after,
124                removed,
125            }
126        } else {
127            TombstoneReclamationStep::Complete { removed }
128        }
129    }
130}
131
132#[cfg(test)]
133mod tests;
uqa_storage/mvcc/tombstones.rs

uqa_storage/mvcc/
tombstones.rs
