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() + 8);
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        bytes
54    }
55
56    /// Decode from storage bytes.
57    pub fn decode(bytes: &[u8]) -> DbxResult<Self> {
58        if bytes.len() < 8 {
59            return Err(DbxError::Storage("Invalid versioned key length".into()));
60        }
61
62        let split_idx = bytes.len() - 8;
63        let user_key = bytes[..split_idx].to_vec();
64
65        let ts_bytes: [u8; 8] = bytes[split_idx..].try_into().unwrap(); // Safe due to len check
66        let inverted_ts = u64::from_be_bytes(ts_bytes);
67        let commit_ts = !inverted_ts;
68
69        Ok(Self {
70            user_key,
71            commit_ts,
72        })
73    }
74
75    /// Extract user key from encoded bytes without full decoding.
76    pub fn extract_user_key(bytes: &[u8]) -> Option<&[u8]> {
77        if bytes.len() < 8 {
78            None
79        } else {
80            Some(&bytes[..bytes.len() - 8])
81        }
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_versioned_key_encoding() {
91        let key = b"key1".to_vec();
92        let ts = 100;
93        let vk = VersionedKey::new(key.clone(), ts);
94        let encoded = vk.encode();
95
96        assert_eq!(encoded.len(), key.len() + 8);
97
98        let decoded = VersionedKey::decode(&encoded).unwrap();
99        assert_eq!(decoded, vk);
100    }
101
102    #[test]
103    fn test_version_ordering() {
104        let key = b"key".to_vec();
105        // Newer version (higher TS)
106        let v2 = VersionedKey::new(key.clone(), 200);
107        // Older version (lower TS)
108        let v1 = VersionedKey::new(key.clone(), 100);
109
110        // Lexicographical order: encoded v2 < encoded v1 because of inverted TS
111        // !200 < !100
112        assert!(v2.encode() < v1.encode());
113    }
114}
dbx_core/transaction/mvcc/version.rs

dbx_core/transaction/mvcc/
version.rs
