sapphire_framework_sync/
hlc.rs

1//! Hybrid logical clock.
2
3use std::time::{SystemTime, UNIX_EPOCH};
4
5use serde::{Deserialize, Serialize};
6
7/// How far ahead of the local wall clock a remote timestamp may pull the local clock.
8pub const MAX_DRIFT_MS: u64 = 24 * 60 * 60 * 1000;
9
10/// Hybrid logical clock value, ordered by wall time and then the logical counter.
11#[derive(
12    Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize,
13)]
14pub struct Hlc {
15    pub wall_ms: u64,
16    pub logical: u32,
17}
18
19/// Source of wall-clock time, injectable for tests.
20pub trait Clock: Send + Sync {
21    fn now_ms(&self) -> u64;
22}
23
24/// The system wall clock.
25#[derive(Debug, Default, Clone, Copy)]
26pub struct SystemClock;
27
28impl Clock for SystemClock {
29    fn now_ms(&self) -> u64 {
30        SystemTime::now()
31            .duration_since(UNIX_EPOCH)
32            .map(|d| u64::try_from(d.as_millis()).unwrap_or(u64::MAX))
33            .unwrap_or(0)
34    }
35}
36
37impl Hlc {
38    /// The timestamp of a new local event; strictly greater than `self`.
39    pub fn tick(self, now_ms: u64) -> Hlc {
40        if now_ms > self.wall_ms {
41            Hlc {
42                wall_ms: now_ms,
43                logical: 0,
44            }
45        } else if self.logical == u32::MAX {
46            Hlc {
47                wall_ms: self.wall_ms + 1,
48                logical: 0,
49            }
50        } else {
51            Hlc {
52                wall_ms: self.wall_ms,
53                logical: self.logical + 1,
54            }
55        }
56    }
57
58    /// Fold a received timestamp into the local clock. A remote wall time beyond
59    /// `now + MAX_DRIFT_MS` is logged and clamped, so one skewed device cannot drag
60    /// every clock forward.
61    pub fn observe(self, remote: Hlc, now_ms: u64) -> Hlc {
62        let cap = now_ms.saturating_add(MAX_DRIFT_MS);
63        let remote = if remote.wall_ms > cap {
64            tracing::warn!(
65                remote_wall_ms = remote.wall_ms,
66                now_ms,
67                "remote clock is more than 24h ahead; clamping"
68            );
69            Hlc {
70                wall_ms: cap,
71                logical: 0,
72            }
73        } else {
74            remote
75        };
76        self.max(remote)
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn tick_is_strictly_monotonic_even_when_the_wall_clock_stalls() {
86        let a = Hlc::default().tick(100);
87        let b = a.tick(100);
88        let c = b.tick(50);
89        assert!(a < b && b < c);
90        assert_eq!(
91            a,
92            Hlc {
93                wall_ms: 100,
94                logical: 0
95            }
96        );
97        assert_eq!(
98            c,
99            Hlc {
100                wall_ms: 100,
101                logical: 2
102            }
103        );
104    }
105
106    #[test]
107    fn observe_takes_the_later_clock() {
108        let local = Hlc {
109            wall_ms: 10,
110            logical: 3,
111        };
112        let remote = Hlc {
113            wall_ms: 20,
114            logical: 1,
115        };
116        assert_eq!(local.observe(remote, 15), remote);
117        assert!(local.observe(remote, 15).tick(15) > remote);
118    }
119
120    #[test]
121    fn observe_clamps_far_future_remotes() {
122        let remote = Hlc {
123            wall_ms: 1_000 + MAX_DRIFT_MS + 5,
124            logical: 0,
125        };
126        let got = Hlc::default().observe(remote, 1_000);
127        assert_eq!(
128            got,
129            Hlc {
130                wall_ms: 1_000 + MAX_DRIFT_MS,
131                logical: 0
132            }
133        );
134    }
135}
sapphire_framework_sync/hlc.rs

sapphire_framework_sync/
hlc.rs
