nodedb_types/
hlc.rs

1//! Hybrid Logical Clock.
2//!
3//! Canonical timestamp for replicated metadata entries, descriptor
4//! modification times, and descriptor lease expiry. Monotonic across
5//! wall-clock skew: `update` folds a remote HLC into the local clock so
6//! causally later events always receive a strictly greater timestamp.
7//!
8//! Metadata DDL is not a hot path (hundreds per second at most), so the
9//! clock is backed by a short-lived mutex rather than atomics.
10
11use std::cmp::Ordering;
12use std::sync::Mutex;
13use std::time::{SystemTime, UNIX_EPOCH};
14
15use serde::{Deserialize, Serialize};
16
17/// Hybrid Logical Clock timestamp.
18#[derive(
19    Debug,
20    Clone,
21    Copy,
22    Default,
23    PartialEq,
24    Eq,
25    Hash,
26    Serialize,
27    Deserialize,
28    zerompk::ToMessagePack,
29    zerompk::FromMessagePack,
30)]
31pub struct Hlc {
32    /// Wall-clock component: nanoseconds since the Unix epoch.
33    pub wall_ns: u64,
34    /// Logical counter incremented when two events share a wall-clock tick.
35    pub logical: u32,
36}
37
38impl Hlc {
39    pub const ZERO: Hlc = Hlc {
40        wall_ns: 0,
41        logical: 0,
42    };
43
44    pub const fn new(wall_ns: u64, logical: u32) -> Self {
45        Self { wall_ns, logical }
46    }
47}
48
49impl PartialOrd for Hlc {
50    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
51        Some(self.cmp(other))
52    }
53}
54
55impl Ord for Hlc {
56    fn cmp(&self, other: &Self) -> Ordering {
57        match self.wall_ns.cmp(&other.wall_ns) {
58            Ordering::Equal => self.logical.cmp(&other.logical),
59            other => other,
60        }
61    }
62}
63
64/// Thread-safe HLC source. One instance per node.
65#[derive(Debug, Default)]
66pub struct HlcClock {
67    state: Mutex<Hlc>,
68}
69
70impl HlcClock {
71    pub fn new() -> Self {
72        Self {
73            state: Mutex::new(Hlc::ZERO),
74        }
75    }
76
77    /// Return a new HLC strictly greater than any previously returned value
78    /// and ≥ the current wall clock.
79    pub fn now(&self) -> Hlc {
80        let wall = wall_now_ns();
81        let mut st = self.state.lock().unwrap_or_else(|p| p.into_inner());
82        let next = if wall > st.wall_ns {
83            Hlc::new(wall, 0)
84        } else {
85            Hlc::new(st.wall_ns, st.logical.saturating_add(1))
86        };
87        *st = next;
88        next
89    }
90
91    /// Fold a remote HLC into the local clock and return a strictly greater HLC
92    /// than both the prior local state and the remote observation.
93    pub fn update(&self, remote: Hlc) -> Hlc {
94        let wall = wall_now_ns();
95        let mut st = self.state.lock().unwrap_or_else(|p| p.into_inner());
96        let prev = *st;
97        let max_wall = wall.max(prev.wall_ns).max(remote.wall_ns);
98        let next_logical = if max_wall == prev.wall_ns && max_wall == remote.wall_ns {
99            prev.logical.max(remote.logical).saturating_add(1)
100        } else if max_wall == prev.wall_ns {
101            prev.logical.saturating_add(1)
102        } else if max_wall == remote.wall_ns {
103            remote.logical.saturating_add(1)
104        } else {
105            0
106        };
107        let next = Hlc::new(max_wall, next_logical);
108        *st = next;
109        next
110    }
111
112    /// Read the last observed HLC without advancing.
113    pub fn peek(&self) -> Hlc {
114        *self.state.lock().unwrap_or_else(|p| p.into_inner())
115    }
116}
117
118fn wall_now_ns() -> u64 {
119    SystemTime::now()
120        .duration_since(UNIX_EPOCH)
121        .map(|d| d.as_nanos() as u64)
122        .unwrap_or(0)
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128
129    #[test]
130    fn monotonic_within_tick() {
131        let clock = HlcClock::new();
132        let mut prev = clock.now();
133        for _ in 0..1_000 {
134            let next = clock.now();
135            assert!(next > prev);
136            prev = next;
137        }
138    }
139
140    #[test]
141    fn update_produces_strictly_greater() {
142        let clock = HlcClock::new();
143        let local = clock.now();
144        let remote = Hlc::new(local.wall_ns + 1_000_000, 7);
145        let merged = clock.update(remote);
146        assert!(merged > remote);
147        assert!(merged > local);
148    }
149
150    #[test]
151    fn ordering_is_total() {
152        let a = Hlc::new(10, 0);
153        let b = Hlc::new(10, 1);
154        let c = Hlc::new(11, 0);
155        assert!(a < b);
156        assert!(b < c);
157        assert!(a < c);
158    }
159}
nodedb_types/hlc.rs

nodedb_types/
hlc.rs
