cvx_storage/
keys.rs

1//! Big-endian key encoding for RocksDB with correct lexicographic ordering.
2//!
3//! Keys are encoded as `entity_id (8B) + space_id (4B) + timestamp (8B) = 20 bytes`.
4//! All integers use big-endian encoding so that lexicographic byte comparison
5//! matches numeric ordering.
6//!
7//! Timestamps (`i64`) use a **sign-bit flip** (XOR 0x80 on the first byte) so
8//! that negative timestamps sort correctly:
9//! - Without flip: `-1` = `FF..FF` sorts after `1` = `00..01` (wrong)
10//! - With flip: `-1` = `7F..FF` sorts before `1` = `80..01` (correct)
11//!
12//! # Example
13//!
14//! ```
15//! use cvx_storage::keys;
16//!
17//! let key = keys::encode_key(42, 0, 1_000_000);
18//! let (entity_id, space_id, timestamp) = keys::decode_key(&key);
19//! assert_eq!(entity_id, 42);
20//! assert_eq!(space_id, 0);
21//! assert_eq!(timestamp, 1_000_000);
22//! ```
23
24/// Total size of an encoded key in bytes.
25pub const KEY_SIZE: usize = 20;
26
27/// Prefix size for entity_id + space_id (used for prefix bloom filters).
28pub const PREFIX_SIZE: usize = 12;
29
30/// Encode a key as 20 big-endian bytes with sign-bit flip on timestamp.
31pub fn encode_key(entity_id: u64, space_id: u32, timestamp: i64) -> [u8; KEY_SIZE] {
32    let mut key = [0u8; KEY_SIZE];
33    key[0..8].copy_from_slice(&entity_id.to_be_bytes());
34    key[8..12].copy_from_slice(&space_id.to_be_bytes());
35    key[12..20].copy_from_slice(&encode_timestamp(timestamp));
36    key
37}
38
39/// Decode a 20-byte key back into its components.
40pub fn decode_key(key: &[u8]) -> (u64, u32, i64) {
41    let entity_id = u64::from_be_bytes(key[0..8].try_into().unwrap());
42    let space_id = u32::from_be_bytes(key[8..12].try_into().unwrap());
43    let timestamp = decode_timestamp(key[12..20].try_into().unwrap());
44    (entity_id, space_id, timestamp)
45}
46
47/// Encode an entity_id + space_id prefix (12 bytes) for prefix scans.
48pub fn encode_prefix(entity_id: u64, space_id: u32) -> [u8; PREFIX_SIZE] {
49    let mut prefix = [0u8; PREFIX_SIZE];
50    prefix[0..8].copy_from_slice(&entity_id.to_be_bytes());
51    prefix[8..12].copy_from_slice(&space_id.to_be_bytes());
52    prefix
53}
54
55/// Encode a timestamp with sign-bit flip for correct lexicographic ordering.
56fn encode_timestamp(ts: i64) -> [u8; 8] {
57    let mut bytes = ts.to_be_bytes();
58    bytes[0] ^= 0x80;
59    bytes
60}
61
62/// Decode a sign-bit-flipped timestamp.
63fn decode_timestamp(bytes: &[u8; 8]) -> i64 {
64    let mut b = *bytes;
65    b[0] ^= 0x80;
66    i64::from_be_bytes(b)
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn roundtrip_basic() {
75        let (e, s, t) = (42u64, 1u32, 1_000_000i64);
76        let key = encode_key(e, s, t);
77        let (e2, s2, t2) = decode_key(&key);
78        assert_eq!((e, s, t), (e2, s2, t2));
79    }
80
81    #[test]
82    fn roundtrip_negative_timestamp() {
83        let key = encode_key(1, 0, -5_000_000);
84        let (_, _, ts) = decode_key(&key);
85        assert_eq!(ts, -5_000_000);
86    }
87
88    #[test]
89    fn roundtrip_extremes() {
90        for ts in [i64::MIN, i64::MIN + 1, -1, 0, 1, i64::MAX - 1, i64::MAX] {
91            let key = encode_key(0, 0, ts);
92            let (_, _, decoded) = decode_key(&key);
93            assert_eq!(ts, decoded, "failed for ts={ts}");
94        }
95    }
96
97    #[test]
98    fn timestamp_ordering_preserved() {
99        let timestamps = [i64::MIN, -1_000_000, -1, 0, 1, 1_000_000, i64::MAX];
100        let keys: Vec<[u8; KEY_SIZE]> = timestamps.iter().map(|&ts| encode_key(1, 0, ts)).collect();
101
102        for window in keys.windows(2) {
103            assert!(
104                window[0] < window[1],
105                "ordering broken: {:?} should be < {:?}",
106                window[0],
107                window[1]
108            );
109        }
110    }
111
112    #[test]
113    fn entity_ordering_preserved() {
114        let k1 = encode_key(1, 0, 0);
115        let k2 = encode_key(2, 0, 0);
116        assert!(k1 < k2);
117    }
118
119    #[test]
120    fn space_ordering_preserved() {
121        let k1 = encode_key(1, 0, 0);
122        let k2 = encode_key(1, 1, 0);
123        assert!(k1 < k2);
124    }
125
126    #[test]
127    fn prefix_matches_key_start() {
128        let key = encode_key(42, 5, 1000);
129        let prefix = encode_prefix(42, 5);
130        assert_eq!(&key[..PREFIX_SIZE], &prefix);
131    }
132
133    #[test]
134    fn key_size_is_20() {
135        assert_eq!(KEY_SIZE, 20);
136        assert_eq!(encode_key(0, 0, 0).len(), 20);
137    }
138}
139
140#[cfg(test)]
141mod proptests {
142    use super::*;
143    use proptest::prelude::*;
144
145    proptest! {
146        #[test]
147        fn roundtrip_arbitrary(
148            entity_id in any::<u64>(),
149            space_id in any::<u32>(),
150            timestamp in any::<i64>(),
151        ) {
152            let key = encode_key(entity_id, space_id, timestamp);
153            let (e, s, t) = decode_key(&key);
154            prop_assert_eq!(entity_id, e);
155            prop_assert_eq!(space_id, s);
156            prop_assert_eq!(timestamp, t);
157        }
158
159        #[test]
160        fn ordering_preserved(
161            entity_id in any::<u64>(),
162            space_id in any::<u32>(),
163            t1 in any::<i64>(),
164            t2 in any::<i64>(),
165        ) {
166            let k1 = encode_key(entity_id, space_id, t1);
167            let k2 = encode_key(entity_id, space_id, t2);
168            prop_assert_eq!(t1.cmp(&t2), k1.cmp(&k2));
169        }
170    }
171}
cvx_storage/keys.rs

cvx_storage/
keys.rs
