Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_core/src/time/hlc.rs

10.3 KiB, 1 run

created by r1870400018:74435, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A hybrid logical clock: a stamp that follows the wall clock when the wall clock moves, a counter
2//! when it does not, and the larger of its own and a peer's reading when a message arrives, so that
3//! a stamp taken after receiving another is always greater than it.
4//!
5//! The wall reading is a [`WallClock`] (a [`ClockSource`] is one, so a rig's driven clock drives the
6//! stamp) plus an offset the caller measures against a reference clock, so that a device whose own
7//! clock is wrong still stamps near the reference's time. A peer's wall more than `delta` ahead of
8//! the corrected wall is not believed: the merge keeps only its own counter step and answers a
9//! [`ClockFault`] for the caller to raise. Built for Daimond's records (design (2), 16 Oct 2026,
10//! §4.1); Ore's Lamport stamp and Ozone's process-local stamp are its other candidate callers.
11//!
12//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
13//! Anthropic Claude
14
15use crate::{
16 prelude::*,
17 time::ClockSource,
18};
19
20use std::{
21 fmt,
22 str::FromStr,
23 sync::Arc,
24};
25
26
27/// The default bound on how far a peer's wall may run ahead of ours and still be believed.
28pub const DELTA_MS_DEFAULT: u64 = 60_000;
29
30/// `Hlc::to_bytes` length: 8 wall, 4 counter, 8 node.
31pub const ENCODED_LEN: usize = 20;
32
33/// One stamp. The derived order is `(wall_ms, ctr, node)`, field by field, which is the clock's
34/// total order; `node` only breaks a tie between two nodes stamping the same `(wall_ms, ctr)`.
35///
36/// Widths: milliseconds since the Unix epoch in a `u64`; a `u32` counter, four billion stamps in
37/// one millisecond before the clock moves its wall on by one (see [`HlcClock::now`]); a `u64` node,
38/// room for a random id with no registry.
39#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
40pub struct Hlc {
41 pub wall_ms: u64,
42 pub ctr: u32,
43 pub node: u64,
44}
45
46impl Hlc {
47 pub fn new(wall_ms: u64, ctr: u32, node: u64) -> Self {
48 Self { wall_ms, ctr, node }
49 }
50
51 /// Big-endian throughout, so the byte order of two encodings is the order of the stamps and
52 /// an encoding can be a store key.
53 pub fn to_bytes(&self) -> [u8; ENCODED_LEN] {
54 let mut b = [0u8; ENCODED_LEN];
55 b[0..8].copy_from_slice(&self.wall_ms.to_be_bytes());
56 b[8..12].copy_from_slice(&self.ctr.to_be_bytes());
57 b[12..20].copy_from_slice(&self.node.to_be_bytes());
58 b
59 }
60
61 pub fn from_bytes(b: &[u8]) -> Outcome<Self> {
62 if b.len() != ENCODED_LEN {
63 return Err(err!(
64 "An encoded Hlc is {} bytes, not {}.", ENCODED_LEN, b.len();
65 Invalid, Input, Size));
66 }
67 let mut w = [0u8; 8];
68 let mut c = [0u8; 4];
69 let mut n = [0u8; 8];
70 w.copy_from_slice(&b[0..8]);
71 c.copy_from_slice(&b[8..12]);
72 n.copy_from_slice(&b[12..20]);
73 Ok(Self {
74 wall_ms: u64::from_be_bytes(w),
75 ctr: u32::from_be_bytes(c),
76 node: u64::from_be_bytes(n),
77 })
78 }
79}
80
81/// `<wall_ms>.<ctr>@<node as 16 hex digits>`, e.g. `1760659200000.3@00000000000000a1`.
82impl fmt::Display for Hlc {
83 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
84 write!(f, "{}.{}@{:016x}", self.wall_ms, self.ctr, self.node)
85 }
86}
87
88impl FromStr for Hlc {
89 type Err = Error<ErrTag>;
90
91 fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
92 let (time, node) = match s.trim().split_once('@') {
93 Some(p) => p,
94 None => return Err(err!(
95 "Hlc '{}' has no '@' before its node.", s;
96 Invalid, Input, Missing)),
97 };
98 let (wall, ctr) = match time.split_once('.') {
99 Some(p) => p,
100 None => return Err(err!(
101 "Hlc '{}' has no '.' between its wall and counter.", s;
102 Invalid, Input, Missing)),
103 };
104 let wall_ms = match wall.parse::<u64>() {
105 Ok(n) => n,
106 Err(e) => return Err(err!(e, "Hlc '{}': the wall '{}'.", s, wall; Invalid, Input)),
107 };
108 let ctr = match ctr.parse::<u32>() {
109 Ok(n) => n,
110 Err(e) => return Err(err!(e, "Hlc '{}': the counter '{}'.", s, ctr; Invalid, Input)),
111 };
112 let node = match u64::from_str_radix(node, 16) {
113 Ok(n) => n,
114 Err(e) => return Err(err!(e, "Hlc '{}': the node '{}'.", s, node; Invalid, Input)),
115 };
116 Ok(Self { wall_ms, ctr, node })
117 }
118}
119
120/// Where an [`HlcClock`] reads its wall, in milliseconds since the Unix epoch.
121pub trait WallClock {
122 fn wall_ms(&self) -> Outcome<u64>;
123}
124
125impl WallClock for ClockSource {
126 fn wall_ms(&self) -> Outcome<u64> {
127 self.now_millis()
128 }
129}
130
131impl<W: WallClock + ?Sized> WallClock for &W {
132 fn wall_ms(&self) -> Outcome<u64> {
133 (**self).wall_ms()
134 }
135}
136
137impl<W: WallClock + ?Sized> WallClock for Arc<W> {
138 fn wall_ms(&self) -> Outcome<u64> {
139 (**self).wall_ms()
140 }
141}
142
143/// A peer's stamp whose wall ran more than `delta_ms` ahead of the corrected local wall, and was
144/// therefore not merged.
145#[derive(Clone, Copy, Debug, PartialEq, Eq)]
146pub struct ClockFault {
147 pub remote: Hlc, // the stamp received
148 pub local_ms: u64, // the corrected local wall at receipt
149 pub ahead_ms: u64, // remote.wall_ms - local_ms
150 pub delta_ms: u64, // the bound in force
151}
152
153impl fmt::Display for ClockFault {
154 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
155 write!(f,
156 "a peer stamp {} is {} ms ahead of the local wall {} (bound {} ms); its wall was ignored",
157 self.remote, self.ahead_ms, self.local_ms, self.delta_ms)
158 }
159}
160
161/// What [`HlcClock::recv`] answers: the stamp for the receipt, and a fault when the peer's wall was
162/// not believed.
163#[derive(Clone, Copy, Debug, PartialEq, Eq)]
164pub struct Recv {
165 pub stamp: Hlc,
166 pub fault: Option<ClockFault>,
167}
168
169/// The clock of one node. It takes `&mut self`; a caller sharing one between threads puts it
170/// behind its own lock, so a stamp and the state it advances change together.
171#[derive(Debug)]
172pub struct HlcClock<W: WallClock> {
173 wall: W,
174 node: u64,
175 offset_ms: i64, // reference clock - local wall, as last measured
176 delta_ms: u64,
177 last: Hlc, // the greatest stamp handed out or merged
178}
179
180impl<W: WallClock> HlcClock<W> {
181 pub fn new(wall: W, node: u64) -> Self {
182 Self {
183 wall,
184 node,
185 offset_ms: 0,
186 delta_ms: DELTA_MS_DEFAULT,
187 last: Hlc::new(0, 0, node),
188 }
189 }
190
191 pub fn with_delta_ms(mut self, delta_ms: u64) -> Self {
192 self.delta_ms = delta_ms;
193 self
194 }
195
196 /// Resumes from a stamp kept across a restart, so the clock never hands out one at or below it.
197 pub fn with_last(mut self, last: Hlc) -> Self {
198 self.last = Hlc::new(last.wall_ms, last.ctr, self.node);
199 self
200 }
201
202 /// Sets the measured offset of a reference clock from the local wall (reference - local), so
203 /// that `local + offset` reads near the reference. A smaller offset than before does not move
204 /// stamps back; they run on the counter until the corrected wall passes the last one.
205 pub fn set_offset_ms(&mut self, offset_ms: i64) {
206 self.offset_ms = offset_ms;
207 }
208
209 pub fn offset_ms(&self) -> i64 { self.offset_ms }
210 pub fn delta_ms(&self) -> u64 { self.delta_ms }
211 pub fn node(&self) -> u64 { self.node }
212 pub fn last(&self) -> Hlc { self.last }
213
214 /// The local wall plus the offset, held inside `0..=u64::MAX`.
215 pub fn corrected_ms(&self) -> Outcome<u64> {
216 let w = res!(self.wall.wall_ms());
217 Ok(if self.offset_ms >= 0 {
218 w.saturating_add(self.offset_ms as u64)
219 } else {
220 w.saturating_sub(self.offset_ms.unsigned_abs())
221 })
222 }
223
224 /// A stamp greater than every stamp this clock has handed out or merged. Its wall is the
225 /// larger of the corrected wall and the last stamp's; when that is the last stamp's, the counter
226 /// steps. A counter at `u32::MAX` moves the wall on by one millisecond and restarts at zero
227 /// (the wall bump), rather than failing; only a wall at `u64::MAX` is an error.
228 pub fn now(&mut self) -> Outcome<Hlc> {
229 let pt = res!(self.corrected_ms());
230 let next = if pt > self.last.wall_ms {
231 Hlc::new(pt, 0, self.node)
232 } else {
233 res!(self.step(self.last.wall_ms, self.last.ctr))
234 };
235 self.last = next;
236 Ok(next)
237 }
238
239 /// Merges a peer's stamp and answers a stamp greater than both it and every local one. When
240 /// the peer's wall is more than `delta_ms` ahead of the corrected wall it is not believed: the
241 /// stamp is what [`now`](Self::now) would give, so it can be below the peer's, and the fault is
242 /// answered for the caller to raise.
243 pub fn recv(&mut self, remote: &Hlc) -> Outcome<Recv> {
244 let pt = res!(self.corrected_ms());
245 let ahead = remote.wall_ms.saturating_sub(pt);
246 if ahead > self.delta_ms {
247 let stamp = res!(self.now());
248 return Ok(Recv {
249 stamp,
250 fault: Some(ClockFault {
251 remote: *remote,
252 local_ms: pt,
253 ahead_ms: ahead,
254 delta_ms: self.delta_ms,
255 }),
256 });
257 }
258 let l = self.last;
259 let wall = pt.max(l.wall_ms).max(remote.wall_ms);
260 let next = if wall == l.wall_ms && wall == remote.wall_ms {
261 res!(self.step(wall, l.ctr.max(remote.ctr)))
262 } else if wall == l.wall_ms {
263 res!(self.step(wall, l.ctr))
264 } else if wall == remote.wall_ms {
265 res!(self.step(wall, remote.ctr))
266 } else {
267 Hlc::new(wall, 0, self.node)
268 };
269 self.last = next;
270 Ok(Recv { stamp: next, fault: None })
271 }
272
273 // The stamp after (wall, ctr): the counter's next value, or the wall bump when it is spent.
274 fn step(&self, wall: u64, ctr: u32) -> Outcome<Hlc> {
275 match ctr.checked_add(1) {
276 Some(c) => Ok(Hlc::new(wall, c, self.node)),
277 None => match wall.checked_add(1) {
278 Some(w) => Ok(Hlc::new(w, 0, self.node)),
279 None => Err(err!(
280 "The hybrid logical clock of node {:016x} is spent: wall {} and counter {}.",
281 self.node, wall, ctr;
282 Overflow)),
283 },
284 }
285 }
286}