dbx_core/transaction/mvcc/
version.rs

1use crate::error::{DbxError, DbxResult};
2use std::convert::TryInto;
3
4/// A versioned key for MVCC storage.
5///
6/// Encodes a user key and a timestamp into a single byte array,
7/// allowing for efficient range scans and version retrieval.
8///
9/// Format: `[UserKey bytes] + [!Timestamp (8 bytes, Big Endian)]`
10///
11/// The timestamp is stored as bit-inverted (`!ts`) big-endian to ensure
12/// that newer versions (higher timestamps) appear first in lexicographical order.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct VersionedKey {
15    pub user_key: Vec<u8>,
16    pub commit_ts: u64,
17}
18
19impl PartialOrd for VersionedKey {
20    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
21        Some(self.cmp(other))
22    }
23}
24
25impl Ord for VersionedKey {
26    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
27        match self.user_key.cmp(&other.user_key) {
28            std::cmp::Ordering::Equal => {
29                // Descending order for timestamp: higher TS comes first
30                other.commit_ts.cmp(&self.commit_ts)
31            }
32            ord => ord,
33        }
34    }
35}
36
37impl VersionedKey {
38    /// Create a new versioned key.
39    pub fn new(user_key: Vec<u8>, commit_ts: u64) -> Self {
40        Self {
41            user_key,
42            commit_ts,
43        }
44    }
45
46    /// Encode into bytes for storage.
47    pub fn encode(&self) -> Vec<u8> {
48        let mut bytes = Vec::with_capacity(self.user_key.len() + 10);
49        bytes.extend_from_slice(&self.user_key);
50        // Invert timestamp for descending order (latest first)
51        let inverted_ts = !self.commit_ts;
52        bytes.extend_from_slice(&inverted_ts.to_be_bytes());
53        // Magic suffix to securely identify MVCC VersionedKeys [0xDB, 0x58]
54        bytes.extend_from_slice(&[0xDB, 0x58]);
55        bytes
56    }
57
58    /// Decode from storage bytes.
59    pub fn decode(bytes: &[u8]) -> DbxResult<Self> {
60        if bytes.len() < 10 {
61            return Err(DbxError::Storage("Invalid versioned key length".into()));
62        }
63
64        // Check magic suffix
65        if bytes[bytes.len() - 2..] != [0xDB, 0x58] {
66            return Err(DbxError::Storage("Missing MVCC magic suffix".into()));
67        }
68
69        let split_idx = bytes.len() - 10;
70        let user_key = bytes[..split_idx].to_vec();
71
72        let ts_bytes: [u8; 8] = bytes[split_idx..split_idx + 8].try_into().unwrap(); // Safe due to len check
73        let inverted_ts = u64::from_be_bytes(ts_bytes);
74        let commit_ts = !inverted_ts;
75
76        Ok(Self {
77            user_key,
78            commit_ts,
79        })
80    }
81
82    /// Extract user key from encoded bytes without full decoding.
83    pub fn extract_user_key(bytes: &[u8]) -> Option<&[u8]> {
84        if bytes.len() < 10 || bytes[bytes.len() - 2..] != [0xDB, 0x58] {
85            None
86        } else {
87            Some(&bytes[..bytes.len() - 10])
88        }
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn test_versioned_key_encoding() {
98        let key = b"key1".to_vec();
99        let ts = 100;
100        let vk = VersionedKey::new(key.clone(), ts);
101        let encoded = vk.encode();
102
103        assert_eq!(encoded.len(), key.len() + 10);
104
105        let decoded = VersionedKey::decode(&encoded).unwrap();
106        assert_eq!(decoded, vk);
107    }
108
109    #[test]
110    fn test_version_ordering() {
111        let key = b"key".to_vec();
112        // Newer version (higher TS)
113        let v2 = VersionedKey::new(key.clone(), 200);
114        // Older version (lower TS)
115        let v1 = VersionedKey::new(key.clone(), 100);
116
117        // Lexicographical order: encoded v2 < encoded v1 because of inverted TS
118        // !200 < !100
119        assert!(v2.encode() < v1.encode());
120    }
121}
dbx_core/transaction/mvcc/version.rs

dbx_core/transaction/mvcc/
version.rs
