sochdb_core/
version_chain.rs

1// SPDX-License-Identifier: AGPL-3.0-or-later
2// SochDB - LLM-Optimized Embedded Database
3// Copyright (C) 2026 Sushanth Reddy Vanagala (https://github.com/sushanthpy)
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU Affero General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU Affero General Public License for more details.
14//
15// You should have received a copy of the GNU Affero General Public License
16// along with this program. If not, see <https://www.gnu.org/licenses/>.
17
18//! Unified MVCC Version Chain Interface
19//!
20//! This module defines the canonical interface for MVCC version chains across SochDB.
21//! Multiple implementations exist for different subsystems, but they share these traits.
22//!
23//! ## Implementations
24//!
25//! | Implementation | Location | Use Case |
26//! |---------------|----------|----------|
27//! | `VersionChain` | `sochdb_core::epoch_gc` | Epoch-based GC with VecDeque |
28//! | `VersionChain` | `sochdb_storage::mvcc_snapshot` | Snapshot-based visibility |
29//! | `VersionChain` | `sochdb_storage::version_store` | Generic key-value MVCC |
30//! | `VersionChain` | `sochdb_storage::durable_storage` | Binary-search optimized |
31//!
32//! ## Visibility Semantics
33//!
34//! All implementations follow these MVCC visibility rules:
35//!
36//! 1. **Read Committed**: A version is visible if its creating transaction has committed
37//!    before the reader's start timestamp.
38//!
39//! 2. **Snapshot Isolation**: A version is visible if:
40//!    - It was committed before the reader's snapshot timestamp
41//!    - It was not deleted, or deleted after the snapshot timestamp
42//!
43//! 3. **Serializable (SSI)**: Adds read-write conflict detection on top of SI.
44
45/// Transaction identifier type
46pub type TxnId = u64;
47
48/// Logical timestamp type
49pub type Timestamp = u64;
50
51/// Version visibility context
52/// 
53/// Provides the information needed to determine if a version is visible
54/// to a particular reader/transaction.
55#[derive(Debug, Clone)]
56pub struct VisibilityContext {
57    /// Reader's transaction ID
58    pub reader_txn_id: TxnId,
59    /// Reader's snapshot timestamp
60    pub snapshot_ts: Timestamp,
61    /// Set of transaction IDs that are still active (not committed)
62    pub active_txn_ids: std::collections::HashSet<TxnId>,
63}
64
65impl VisibilityContext {
66    /// Create a new visibility context
67    pub fn new(reader_txn_id: TxnId, snapshot_ts: Timestamp) -> Self {
68        Self {
69            reader_txn_id,
70            snapshot_ts,
71            active_txn_ids: std::collections::HashSet::new(),
72        }
73    }
74
75    /// Create with active transaction set
76    pub fn with_active_txns(
77        reader_txn_id: TxnId,
78        snapshot_ts: Timestamp,
79        active_txn_ids: std::collections::HashSet<TxnId>,
80    ) -> Self {
81        Self {
82            reader_txn_id,
83            snapshot_ts,
84            active_txn_ids,
85        }
86    }
87
88    /// Check if a transaction was committed before this snapshot
89    pub fn is_committed_before(&self, txn_id: TxnId, commit_ts: Option<Timestamp>) -> bool {
90        match commit_ts {
91            Some(ts) => ts < self.snapshot_ts && !self.active_txn_ids.contains(&txn_id),
92            None => false,
93        }
94    }
95}
96
97/// Version metadata
98/// 
99/// Common metadata for all version chain implementations.
100#[derive(Debug, Clone)]
101pub struct VersionMeta {
102    /// Transaction that created this version
103    pub created_by: TxnId,
104    /// Timestamp when this version was created
105    pub created_ts: Timestamp,
106    /// Transaction that deleted this version (0 = not deleted)
107    pub deleted_by: TxnId,
108    /// Timestamp when this version was deleted (0 = not deleted)
109    pub deleted_ts: Timestamp,
110    /// Commit timestamp (0 = not yet committed)
111    pub commit_ts: Timestamp,
112}
113
114impl VersionMeta {
115    /// Create metadata for a new uncommitted version
116    pub fn new_uncommitted(created_by: TxnId, created_ts: Timestamp) -> Self {
117        Self {
118            created_by,
119            created_ts,
120            deleted_by: 0,
121            deleted_ts: 0,
122            commit_ts: 0,
123        }
124    }
125
126    /// Check if this version is visible according to the context
127    pub fn is_visible(&self, ctx: &VisibilityContext) -> bool {
128        // Must be committed before snapshot
129        if self.commit_ts == 0 {
130            // Uncommitted - only visible to creating transaction
131            return self.created_by == ctx.reader_txn_id;
132        }
133
134        if self.commit_ts >= ctx.snapshot_ts {
135            return false;
136        }
137
138        // Must not be deleted, or deleted after snapshot
139        if self.deleted_by != 0 && self.deleted_ts < ctx.snapshot_ts {
140            return false;
141        }
142
143        true
144    }
145
146    /// Mark as committed
147    pub fn commit(&mut self, commit_ts: Timestamp) {
148        self.commit_ts = commit_ts;
149    }
150
151    /// Mark as deleted
152    pub fn delete(&mut self, deleted_by: TxnId, deleted_ts: Timestamp) {
153        self.deleted_by = deleted_by;
154        self.deleted_ts = deleted_ts;
155    }
156
157    /// Check if version is committed
158    pub fn is_committed(&self) -> bool {
159        self.commit_ts != 0
160    }
161
162    /// Check if version is deleted
163    pub fn is_deleted(&self) -> bool {
164        self.deleted_by != 0
165    }
166}
167
168/// Trait for MVCC version chain implementations
169/// 
170/// Implementors store multiple versions of a value and provide
171/// visibility-based access according to MVCC semantics.
172pub trait MvccVersionChain {
173    /// The value type stored in versions
174    type Value;
175
176    /// Get the visible version for the given context
177    fn get_visible(&self, ctx: &VisibilityContext) -> Option<&Self::Value>;
178
179    /// Get the latest version (regardless of visibility)
180    fn get_latest(&self) -> Option<&Self::Value>;
181
182    /// Number of versions in the chain
183    fn version_count(&self) -> usize;
184
185    /// Check if the chain is empty
186    fn is_empty(&self) -> bool {
187        self.version_count() == 0
188    }
189}
190
191/// Trait for mutable version chain operations
192pub trait MvccVersionChainMut: MvccVersionChain {
193    /// Add a new uncommitted version
194    fn add_uncommitted(&mut self, value: Self::Value, txn_id: TxnId);
195
196    /// Commit a version
197    fn commit_version(&mut self, txn_id: TxnId, commit_ts: Timestamp) -> bool;
198
199    /// Mark the latest visible version as deleted
200    fn delete_version(&mut self, txn_id: TxnId, delete_ts: Timestamp) -> bool;
201
202    /// Garbage collect versions older than the given timestamp
203    /// Returns (versions_removed, bytes_freed)
204    fn gc(&mut self, min_visible_ts: Timestamp) -> (usize, usize);
205}
206
207/// Trait for detecting write conflicts
208pub trait WriteConflictDetection {
209    /// Check if there's a write-write conflict with another transaction
210    fn has_write_conflict(&self, txn_id: TxnId) -> bool;
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216
217    #[test]
218    fn test_version_meta_visibility() {
219        let mut meta = VersionMeta::new_uncommitted(1, 100);
220        
221        // Uncommitted - only visible to creator
222        let ctx = VisibilityContext::new(1, 200);
223        assert!(meta.is_visible(&ctx));
224        
225        let ctx2 = VisibilityContext::new(2, 200);
226        assert!(!meta.is_visible(&ctx2));
227        
228        // After commit - visible to later snapshots
229        meta.commit(150);
230        assert!(meta.is_visible(&ctx2));
231        
232        // Not visible to earlier snapshots
233        let ctx3 = VisibilityContext::new(3, 100);
234        assert!(!meta.is_visible(&ctx3));
235    }
236
237    #[test]
238    fn test_version_meta_deletion() {
239        let mut meta = VersionMeta::new_uncommitted(1, 100);
240        meta.commit(150);
241        meta.delete(2, 200);
242        
243        // Visible before deletion
244        let ctx = VisibilityContext::new(3, 180);
245        assert!(meta.is_visible(&ctx));
246        
247        // Not visible after deletion
248        let ctx2 = VisibilityContext::new(3, 250);
249        assert!(!meta.is_visible(&ctx2));
250    }
251
252    #[test]
253    fn test_visibility_context_committed_before() {
254        let mut active = std::collections::HashSet::new();
255        active.insert(5);
256        
257        let ctx = VisibilityContext::with_active_txns(1, 200, active);
258        
259        // Committed before snapshot
260        assert!(ctx.is_committed_before(2, Some(100)));
261        
262        // Committed after snapshot
263        assert!(!ctx.is_committed_before(3, Some(250)));
264        
265        // Active transaction - not committed
266        assert!(!ctx.is_committed_before(5, Some(100)));
267        
268        // No commit timestamp
269        assert!(!ctx.is_committed_before(6, None));
270    }
271}
sochdb_core/version_chain.rs

sochdb_core/
version_chain.rs
