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 | |
| 15 | use crate::{ |
| 16 | prelude::*, |
| 17 | time::ClockSource, |
| 18 | }; |
| 19 | |
| 20 | use 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. |
| 28 | pub const DELTA_MS_DEFAULT: u64 = 60_000; |
| 29 | |
| 30 | /// `Hlc::to_bytes` length: 8 wall, 4 counter, 8 node. |
| 31 | pub 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)] |
| 40 | pub struct Hlc { |
| 41 | pub wall_ms: u64, |
| 42 | pub ctr: u32, |
| 43 | pub node: u64, |
| 44 | } |
| 45 | |
| 46 | impl 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`. |
| 82 | impl 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 | |
| 88 | impl 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. |
| 121 | pub trait WallClock { |
| 122 | fn wall_ms(&self) -> Outcome<u64>; |
| 123 | } |
| 124 | |
| 125 | impl WallClock for ClockSource { |
| 126 | fn wall_ms(&self) -> Outcome<u64> { |
| 127 | self.now_millis() |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | impl<W: WallClock + ?Sized> WallClock for &W { |
| 132 | fn wall_ms(&self) -> Outcome<u64> { |
| 133 | (**self).wall_ms() |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | impl<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)] |
| 146 | pub 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 | |
| 153 | impl 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)] |
| 164 | pub 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)] |
| 172 | pub 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 | |
| 180 | impl<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 | } |