lnc_core/
sort_key.rs

1//! Sort key for total ordering of records across a distributed cluster.
2//!
3//! The `SortKey` provides a 128-bit composite key that ensures deterministic
4//! ordering even when multiple nodes produce events at the same logical time.
5//!
6//! # Structure
7//!
8//! - **HLC timestamp (64 bits)**: Hybrid Logical Clock for causal ordering
9//! - **Node ID (16 bits)**: Tie-breaker for concurrent events (lower wins)
10//! - **Sequence (48 bits)**: Per-node monotonic counter for total ordering
11
12use crate::hlc::HlcTimestamp;
13use zerocopy::{FromBytes, IntoBytes};
14
15/// 128-bit composite sort key for total ordering across distributed nodes.
16///
17/// Records are ordered by:
18/// 1. HLC timestamp (causal ordering)
19/// 2. Node ID (tie-breaker, lower wins)
20/// 3. Sequence number (per-node ordering)
21#[repr(C)]
22#[derive(
23    Copy, Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash, IntoBytes, FromBytes,
24)]
25pub struct SortKey {
26    /// HLC timestamp (64 bits) - provides causal ordering across nodes.
27    pub hlc: HlcTimestamp,
28    /// Packed `node_id` (16 bits) + sequence (48 bits).
29    /// Layout: [`node_id`: 16 bits][sequence: 48 bits]
30    pub node_seq: u64,
31}
32
33impl SortKey {
34    /// Bits allocated to the sequence counter.
35    const SEQUENCE_BITS: u32 = 48;
36
37    /// Mask for extracting the sequence counter.
38    const SEQUENCE_MASK: u64 = (1 << Self::SEQUENCE_BITS) - 1;
39
40    /// Create a new sort key from components.
41    ///
42    /// # Arguments
43    ///
44    /// * `hlc` - Hybrid Logical Clock timestamp
45    /// * `node_id` - Node identifier (lower wins in tie-breaks)
46    /// * `sequence` - Per-node monotonic sequence (only lower 48 bits used)
47    #[inline]
48    #[must_use]
49    pub const fn new(hlc: HlcTimestamp, node_id: u16, sequence: u64) -> Self {
50        let node_seq = ((node_id as u64) << Self::SEQUENCE_BITS) | (sequence & Self::SEQUENCE_MASK);
51        Self { hlc, node_seq }
52    }
53
54    /// Create a sort key from raw timestamp (legacy compatibility).
55    ///
56    /// Converts nanosecond timestamp to HLC milliseconds with zero logical counter.
57    #[inline]
58    #[must_use]
59    pub const fn from_timestamp_ns(timestamp_ns: u64, sequence: u32) -> Self {
60        let physical_ms = timestamp_ns / 1_000_000;
61        let hlc = HlcTimestamp::new(physical_ms, 0);
62        Self::new(hlc, 0, sequence as u64)
63    }
64
65    /// Create a zero (minimum) sort key.
66    #[inline]
67    #[must_use]
68    pub const fn zero() -> Self {
69        Self {
70            hlc: HlcTimestamp::zero(),
71            node_seq: 0,
72        }
73    }
74
75    /// Create a maximum sort key.
76    #[inline]
77    #[must_use]
78    pub const fn max() -> Self {
79        Self {
80            hlc: HlcTimestamp::max(),
81            node_seq: u64::MAX,
82        }
83    }
84
85    /// Get the HLC timestamp component.
86    #[inline]
87    #[must_use]
88    pub const fn hlc(&self) -> HlcTimestamp {
89        self.hlc
90    }
91
92    /// Get the node ID component.
93    #[inline]
94    #[must_use]
95    pub const fn node_id(&self) -> u16 {
96        (self.node_seq >> Self::SEQUENCE_BITS) as u16
97    }
98
99    /// Get the sequence number component.
100    #[inline]
101    #[must_use]
102    pub const fn sequence(&self) -> u64 {
103        self.node_seq & Self::SEQUENCE_MASK
104    }
105
106    /// Get approximate timestamp in nanoseconds (for compatibility).
107    ///
108    /// Note: This loses precision since HLC uses milliseconds internally.
109    #[inline]
110    #[must_use]
111    pub const fn timestamp_ns(&self) -> u64 {
112        self.hlc.to_nanos_approx()
113    }
114
115    /// Convert to a 128-bit integer for atomic operations or serialization.
116    #[inline]
117    #[must_use]
118    pub const fn to_u128(&self) -> u128 {
119        ((self.hlc.as_u64() as u128) << 64) | (self.node_seq as u128)
120    }
121
122    /// Create from a 128-bit integer.
123    #[inline]
124    #[must_use]
125    #[allow(clippy::cast_possible_truncation)]
126    pub const fn from_u128(value: u128) -> Self {
127        let hlc = HlcTimestamp::from_raw((value >> 64) as u64);
128        let node_seq = value as u64;
129        Self { hlc, node_seq }
130    }
131
132    /// Get the size of a sort key in bytes.
133    #[inline]
134    #[must_use]
135    pub const fn size() -> usize {
136        std::mem::size_of::<Self>()
137    }
138}
139
140impl std::fmt::Display for SortKey {
141    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
142        write!(
143            f,
144            "SortKey({}, node={}, seq={})",
145            self.hlc,
146            self.node_id(),
147            self.sequence()
148        )
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    #[test]
157    fn test_sort_key_ordering() {
158        let hlc1 = HlcTimestamp::new(100, 0);
159        let hlc2 = HlcTimestamp::new(100, 1);
160        let hlc3 = HlcTimestamp::new(200, 0);
161
162        let k1 = SortKey::new(hlc1, 1, 0);
163        let k2 = SortKey::new(hlc2, 1, 0);
164        let k3 = SortKey::new(hlc3, 1, 0);
165
166        assert!(k1 < k2, "Higher logical counter should be greater");
167        assert!(k2 < k3, "Higher physical time should be greater");
168        assert!(k1 < k3);
169    }
170
171    #[test]
172    fn test_sort_key_node_id_tiebreak() {
173        let hlc = HlcTimestamp::new(100, 0);
174
175        let k1 = SortKey::new(hlc, 1, 0);
176        let k2 = SortKey::new(hlc, 2, 0);
177
178        assert!(k1 < k2, "Lower node_id should win tie-break");
179    }
180
181    #[test]
182    fn test_sort_key_sequence_ordering() {
183        let hlc = HlcTimestamp::new(100, 0);
184
185        let k1 = SortKey::new(hlc, 1, 0);
186        let k2 = SortKey::new(hlc, 1, 1);
187        let k3 = SortKey::new(hlc, 1, 100);
188
189        assert!(k1 < k2);
190        assert!(k2 < k3);
191    }
192
193    #[test]
194    fn test_sort_key_component_extraction() {
195        let hlc = HlcTimestamp::new(12345, 42);
196        let key = SortKey::new(hlc, 7, 999);
197
198        assert_eq!(key.hlc().physical_ms(), 12345);
199        assert_eq!(key.hlc().logical(), 42);
200        assert_eq!(key.node_id(), 7);
201        assert_eq!(key.sequence(), 999);
202    }
203
204    #[test]
205    fn test_sort_key_u128_roundtrip() {
206        let hlc = HlcTimestamp::new(12345, 42);
207        let original = SortKey::new(hlc, 7, 999);
208
209        let as_u128 = original.to_u128();
210        let restored = SortKey::from_u128(as_u128);
211
212        assert_eq!(original, restored);
213    }
214
215    #[test]
216    fn test_sort_key_size() {
217        assert_eq!(SortKey::size(), 16);
218    }
219
220    #[test]
221    fn test_sort_key_legacy_compatibility() {
222        let key = SortKey::from_timestamp_ns(1_000_000_000, 42);
223
224        // 1 second in nanoseconds = 1000 milliseconds
225        assert_eq!(key.hlc().physical_ms(), 1000);
226        assert_eq!(key.sequence(), 42);
227    }
228}
lnc_core/sort_key.rs

lnc_core/
sort_key.rs
