sochdb_core/
version_chain.rs

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

sochdb_core/
version_chain.rs
