1use std::fmt;
2use std::sync::Mutex;
3use std::time::{SystemTime, UNIX_EPOCH};
4
5use anyhow::{Result, ensure};
6use rusqlite::{Connection, OptionalExtension, params};
7
8pub const INCARNATION_EPOCH_SECS: i64 = 1_767_225_600;
10
11pub const HLC_CEILING_MICROS: i64 = (INCARNATION_EPOCH_SECS + INCARNATION_LIMIT) * 1_000_000;
16
17pub const NEW_LAYOUT_MIN: i64 = 1 << 32;
20
21const INCARNATION_LIMIT: i64 = (1 << 31) - (1 << 24);
22const N_LIMIT: i64 = 1 << 32;
23
24const LAST: &str = "clock_last";
25const BASIS: &str = "clock_basis";
26const INCARNATION: &str = "clock_incarnation";
27const INCARNATION_N: &str = "clock_incarnation_n";
28const HELD_ORIGIN_SEQ: &str = "clock_held_origin_seq";
29const AUTHORED: &str = "clock_authored_last";
30
31pub trait WallClock: Send + Sync + std::panic::RefUnwindSafe {
32 fn now_micros(&self) -> Option<i64>;
35}
36
37pub struct SystemClock;
40
41impl WallClock for SystemClock {
42 fn now_micros(&self) -> Option<i64> {
43 Some(match SystemTime::now().duration_since(UNIX_EPOCH) {
44 Ok(since) => since.as_micros() as i64,
45 Err(before) => -(before.duration().as_micros() as i64),
46 })
47 }
48}
49
50#[derive(Debug)]
53pub struct ClockUntrusted;
54
55impl fmt::Display for ClockUntrusted {
56 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57 f.write_str("wall clock not yet trusted: writes are held")
58 }
59}
60
61impl std::error::Error for ClockUntrusted {}
62
63#[derive(Debug)]
66pub struct ClockFloorRejected(pub String);
67
68impl fmt::Display for ClockFloorRejected {
69 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70 f.write_str(&self.0)
71 }
72}
73
74impl std::error::Error for ClockFloorRejected {}
75
76#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
81pub struct ClockFloors {
82 pub basis_micros: Option<i64>,
83 pub last_seq: Option<i64>,
84 pub held_origin_seq: Option<i64>,
85}
86
87#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
88pub struct ClockState {
89 pub last: i64,
90 pub basis: i64,
91 pub incarnation: i64,
92 pub incarnation_n: i64,
93 pub incarnation_floor: i64,
94}
95
96pub(super) fn is_new_layout(origin: &str, origin_seq: i64) -> bool {
97 origin_seq >= NEW_LAYOUT_MIN || origin.starts_with("snap:") || origin.starts_with("replay:")
98}
99
100pub(super) fn wall_now(clock: &dyn WallClock) -> Result<i64> {
101 match clock.now_micros() {
102 Some(wall) => Ok(wall.min(HLC_CEILING_MICROS)),
103 None => Err(ClockUntrusted.into()),
104 }
105}
106
107pub(super) fn meta(conn: &Connection, key: &str) -> Result<Option<i64>> {
108 let value: Option<String> = conn
109 .query_row(
110 "SELECT value FROM index_meta WHERE key = ?1",
111 params![key],
112 |r| r.get(0),
113 )
114 .optional()?;
115 value
116 .map(|v| {
117 v.parse::<i64>()
118 .map_err(|e| anyhow::anyhow!("index_meta {key} = {v:?}: {e}"))
119 })
120 .transpose()
121}
122
123pub(super) fn set_meta(conn: &Connection, key: &str, value: i64) -> Result<()> {
124 conn.execute(
125 "INSERT OR REPLACE INTO index_meta (key, value) VALUES (?1, ?2)",
126 params![key, value.to_string()],
127 )?;
128 Ok(())
129}
130
131fn last(conn: &Connection) -> Result<i64> {
134 match meta(conn, LAST)? {
135 Some(last) => Ok(last),
136 None => Ok(conn.query_row(
137 "SELECT COALESCE(MAX(local_seq), 0) FROM sync_log",
138 [],
139 |r| r.get(0),
140 )?),
141 }
142}
143
144pub(super) fn state(conn: &Connection) -> Result<ClockState> {
145 Ok(ClockState {
146 last: last(conn)?,
147 basis: meta(conn, BASIS)?.unwrap_or(0),
148 incarnation: meta(conn, INCARNATION)?.unwrap_or(0),
149 incarnation_n: meta(conn, INCARNATION_N)?.unwrap_or(0),
150 incarnation_floor: meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0) >> 32,
151 })
152}
153
154pub(super) fn mint_local_seq(conn: &Connection, wall: i64) -> Result<i64> {
155 let basis = meta(conn, BASIS)?.unwrap_or(0);
156 let seq = (last(conn)? + 1).max(wall).max(basis);
157 set_meta(conn, LAST, seq)?;
158 Ok(seq)
159}
160
161pub(super) fn mint_authored(conn: &Connection, wall: i64) -> Result<i64> {
165 let basis = meta(conn, BASIS)?.unwrap_or(0);
166 let previous = meta(conn, AUTHORED)?.unwrap_or(0);
167 let authored = (previous + 1).max(wall).max(basis);
168 set_meta(conn, AUTHORED, authored)?;
169 Ok(authored)
170}
171
172pub(super) fn observe_authored(conn: &Connection, micros: i64) -> Result<()> {
178 let seen = micros.min(HLC_CEILING_MICROS);
179 if seen > meta(conn, AUTHORED)?.unwrap_or(0) {
180 set_meta(conn, AUTHORED, seen)?;
181 }
182 Ok(())
183}
184
185pub(super) fn mint_origin_seq(
190 conn: &Connection,
191 wall: i64,
192 drawn: &Mutex<Option<i64>>,
193) -> Result<i64> {
194 let stored = meta(conn, INCARNATION)?.unwrap_or(0);
195 let n = meta(conn, INCARNATION_N)?.unwrap_or(0);
196 let held = meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0);
197 let mut drawn = drawn.lock().unwrap();
198 let keeps = *drawn == Some(stored) && held <= stored << 32 | n && n + 1 < N_LIMIT;
199 let (incarnation, n) = if keeps {
200 (stored, n + 1)
201 } else {
202 let basis = meta(conn, BASIS)?.unwrap_or(0);
203 let from_clock = wall.max(basis) / 1_000_000 - INCARNATION_EPOCH_SECS;
204 let incarnation = (stored + 1).max(from_clock).max((held >> 32) + 1).max(1);
205 ensure!(
206 incarnation < 1 << 31,
207 "incarnation {incarnation} does not fit an origin_seq"
208 );
209 (incarnation, 1)
210 };
211 set_meta(conn, INCARNATION, incarnation)?;
212 set_meta(conn, INCARNATION_N, n)?;
213 *drawn = Some(incarnation);
214 Ok(incarnation << 32 | n)
215}
216
217pub(super) fn raise_floors(conn: &Connection, floors: &ClockFloors) -> Result<()> {
218 for (what, value) in [
219 ("peer time", floors.basis_micros),
220 ("peer cursor", floors.last_seq),
221 ] {
222 if let Some(v) = value
223 && v > HLC_CEILING_MICROS
224 {
225 return Err(ClockFloorRejected(format!(
226 "{what} {v} is past the clock ceiling {HLC_CEILING_MICROS}"
227 ))
228 .into());
229 }
230 }
231 if let Some(held) = floors.held_origin_seq
232 && held >> 32 >= INCARNATION_LIMIT
233 {
234 return Err(ClockFloorRejected(format!(
235 "held origin_seq {held} has an incarnation past the clock ceiling"
236 ))
237 .into());
238 }
239 if let Some(basis) = floors.basis_micros
240 && basis > meta(conn, BASIS)?.unwrap_or(0)
241 {
242 set_meta(conn, BASIS, basis)?;
243 }
244 if let Some(cursor) = floors.last_seq
245 && cursor > last(conn)?
246 {
247 set_meta(conn, LAST, cursor)?;
248 }
249 if let Some(held) = floors.held_origin_seq
250 && held > meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0)
251 {
252 set_meta(conn, HELD_ORIGIN_SEQ, held)?;
253 }
254 Ok(())
255}
256
257#[cfg(test)]
258mod tests {
259 use std::sync::Arc;
260 use std::sync::atomic::{AtomicBool, AtomicI64, Ordering};
261
262 use super::{
263 ClockFloors, ClockUntrusted, HLC_CEILING_MICROS, INCARNATION_EPOCH_SECS, INCARNATION_LIMIT,
264 WallClock, set_meta,
265 };
266 use crate::schema::{Memory, MemoryType, SyncNodeType, SyncOp, SyncRecord};
267 use crate::sqlite_store::SqliteStore;
268 use crate::store::{Store, StoreAdmin};
269
270 const SECOND: i64 = 1_000_000;
271 const T0: i64 = (INCARNATION_EPOCH_SECS + 20_000_000) * SECOND;
272 const T0_INCARNATION: i64 = 20_000_000;
273
274 struct TestClock {
275 micros: AtomicI64,
276 trusted: AtomicBool,
277 }
278
279 impl WallClock for TestClock {
280 fn now_micros(&self) -> Option<i64> {
281 self.trusted
282 .load(Ordering::SeqCst)
283 .then(|| self.micros.load(Ordering::SeqCst))
284 }
285 }
286
287 fn store_at(micros: i64) -> (SqliteStore, Arc<TestClock>) {
288 let clock = Arc::new(TestClock {
289 micros: AtomicI64::new(micros),
290 trusted: AtomicBool::new(true),
291 });
292 let store = SqliteStore::in_memory("m".to_string())
293 .unwrap()
294 .with_wall_clock(clock.clone());
295 (store, clock)
296 }
297
298 fn write(store: &SqliteStore) -> (i64, i64) {
299 store
300 .store_memory(&Memory::new(
301 "clock test".to_string(),
302 MemoryType::Semantic,
303 "test".to_string(),
304 String::new(),
305 ))
306 .unwrap();
307 let entries = store.sync_log_since(0).unwrap();
308 let last = entries.last().unwrap();
309 (last.local_seq, last.origin_seq)
310 }
311
312 fn split(origin_seq: i64) -> (i64, i64) {
313 (origin_seq >> 32, origin_seq & 0xffff_ffff)
314 }
315
316 fn reopen(store: &SqliteStore) {
317 *store.incarnation.lock().unwrap() = None;
318 }
319
320 #[test]
321 fn local_seq_is_the_highest_of_last_plus_one_wall_and_basis() {
322 let (store, clock) = store_at(T0);
323 assert_eq!(write(&store).0, T0);
324 assert_eq!(write(&store).0, T0 + 1);
325 clock.micros.store(T0 - 3600 * SECOND, Ordering::SeqCst);
326 assert_eq!(write(&store).0, T0 + 2, "a clock stepped back carries on");
327 store
328 .raise_clock_floors(&ClockFloors {
329 basis_micros: Some(T0 + 60 * SECOND),
330 ..Default::default()
331 })
332 .unwrap();
333 assert_eq!(write(&store).0, T0 + 60 * SECOND);
334 clock
335 .micros
336 .store(HLC_CEILING_MICROS + 3600 * SECOND, Ordering::SeqCst);
337 assert_eq!(write(&store).0, HLC_CEILING_MICROS, "the clock is capped");
338 }
339
340 fn authored(store: &SqliteStore) -> i64 {
341 write(store);
342 let entries = store.sync_log_since(0).unwrap();
343 entries.last().unwrap().timestamp.timestamp_micros()
344 }
345
346 #[test]
347 fn authored_time_is_the_highest_of_previous_plus_one_wall_and_basis() {
348 let (store, clock) = store_at(T0);
349 assert_eq!(authored(&store), T0);
350 assert_eq!(
351 authored(&store),
352 T0 + 1,
353 "writes in one microsecond never tie"
354 );
355 clock.micros.store(T0 - 3600 * SECOND, Ordering::SeqCst);
356 assert_eq!(
357 authored(&store),
358 T0 + 2,
359 "a clock stepped back never writes in the past"
360 );
361 store
362 .raise_clock_floors(&ClockFloors {
363 basis_micros: Some(T0 + 60 * SECOND),
364 ..Default::default()
365 })
366 .unwrap();
367 assert_eq!(authored(&store), T0 + 60 * SECOND);
368 clock.micros.store(T0 + 120 * SECOND, Ordering::SeqCst);
369 assert_eq!(authored(&store), T0 + 120 * SECOND);
370 }
371
372 #[test]
373 fn a_relay_keeps_the_incoming_authored_time() {
374 let (store, _) = store_at(T0);
375 let memory = Memory::new(
376 "relayed".to_string(),
377 MemoryType::Semantic,
378 "test".to_string(),
379 String::new(),
380 );
381 let authored = chrono::DateTime::from_timestamp_micros(T0 - 7 * SECOND).unwrap();
382 let record = SyncRecord {
383 local_seq: 1,
384 origin_machine_id: "peer".to_string(),
385 origin_seq: (13u64 << 32) | 1,
386 op: SyncOp::Create,
387 node_type: SyncNodeType::Memory,
388 node_id: memory.id.to_string(),
389 timestamp: authored,
390 data: Some(serde_json::to_value(&memory).unwrap()),
391 };
392 store.apply_record(&record).unwrap();
393 let entries = store.sync_log_since(0).unwrap();
394 assert_eq!(entries.last().unwrap().timestamp, authored);
395 }
396
397 #[test]
398 fn an_open_draws_one_incarnation_and_counts_within_it() {
399 let (store, _) = store_at(T0);
400 assert_eq!(split(write(&store).1), (T0_INCARNATION, 1));
401 assert_eq!(split(write(&store).1), (T0_INCARNATION, 2));
402 reopen(&store);
403 assert_eq!(
404 split(write(&store).1),
405 (T0_INCARNATION + 1, 1),
406 "a new open in the same second still draws above the last"
407 );
408 let state = store.clock_state().unwrap();
409 assert_eq!(
410 (state.incarnation, state.incarnation_n),
411 (T0_INCARNATION + 1, 1)
412 );
413 }
414
415 #[test]
416 fn a_clock_before_the_epoch_still_draws_incarnation_one() {
417 let (store, _) = store_at(0);
418 assert_eq!(split(write(&store).1), (1, 1));
419 }
420
421 #[test]
422 fn a_rolled_back_draw_is_redrawn_and_n_restarts() {
423 let (store, _) = store_at(T0);
424 assert_eq!(split(write(&store).1), (T0_INCARNATION, 1));
425 reopen(&store);
426 let failed: anyhow::Result<()> = store.with_txn(|tx| {
427 store.append_sync_log(tx, SyncOp::Delete, SyncNodeType::Memory, "x", None, None)?;
428 anyhow::bail!("roll back")
429 });
430 assert!(failed.is_err());
431 assert_eq!(store.clock_state().unwrap().incarnation, T0_INCARNATION);
432 assert_eq!(split(write(&store).1), (T0_INCARNATION + 1, 1));
433 }
434
435 #[test]
436 fn a_raised_floor_forces_a_draw_above_it() {
437 let (store, _) = store_at(T0);
438 write(&store);
439 let held = (T0_INCARNATION + 5) << 32 | 9;
440 store
441 .raise_clock_floors(&ClockFloors {
442 held_origin_seq: Some(held),
443 ..Default::default()
444 })
445 .unwrap();
446 assert_eq!(split(write(&store).1), (T0_INCARNATION + 6, 1));
447 assert_eq!(split(write(&store).1), (T0_INCARNATION + 6, 2));
448 }
449
450 #[test]
451 fn a_peer_holding_this_stores_current_key_keeps_its_incarnation() {
452 let (store, _) = store_at(T0);
453 write(&store);
454 let (_, own) = write(&store);
455 store
456 .raise_clock_floors(&ClockFloors {
457 held_origin_seq: Some(own),
458 ..Default::default()
459 })
460 .unwrap();
461 assert_eq!(split(write(&store).1), (T0_INCARNATION, 3));
462 assert_eq!(
463 store.clock_state().unwrap().incarnation_floor,
464 T0_INCARNATION
465 );
466 }
467
468 #[test]
469 fn running_out_of_n_starts_a_new_incarnation() {
470 let (store, _) = store_at(T0);
471 write(&store);
472 set_meta(&store.conn(), super::INCARNATION_N, (1 << 32) - 2).unwrap();
473 assert_eq!(split(write(&store).1), (T0_INCARNATION, (1 << 32) - 1));
474 assert_eq!(split(write(&store).1), (T0_INCARNATION + 1, 1));
475 }
476
477 #[test]
478 fn floors_only_rise() {
479 let (store, _) = store_at(T0);
480 write(&store);
481 let raise = |basis, last, held| {
482 store
483 .raise_clock_floors(&ClockFloors {
484 basis_micros: Some(basis),
485 last_seq: Some(last),
486 held_origin_seq: Some(held),
487 })
488 .unwrap()
489 };
490 raise(T0 + 10, T0 + 20, 30 << 32);
491 raise(T0 - 10, T0 - 20, 3 << 32);
492 let state = store.clock_state().unwrap();
493 assert_eq!(
494 (state.basis, state.last, state.incarnation_floor),
495 (T0 + 10, T0 + 20, 30)
496 );
497 }
498
499 #[test]
500 fn floors_past_the_ceiling_are_rejected_and_raise_nothing() {
501 let (store, _) = store_at(T0);
502 write(&store);
503 let before = store.clock_state().unwrap();
504 for floors in [
505 ClockFloors {
506 basis_micros: Some(HLC_CEILING_MICROS + 1),
507 last_seq: Some(T0 + 100),
508 held_origin_seq: None,
509 },
510 ClockFloors {
511 basis_micros: Some(T0 + 100),
512 last_seq: Some(HLC_CEILING_MICROS + 1),
513 held_origin_seq: None,
514 },
515 ClockFloors {
516 basis_micros: Some(T0 + 100),
517 last_seq: None,
518 held_origin_seq: Some(INCARNATION_LIMIT << 32),
519 },
520 ] {
521 assert!(store.raise_clock_floors(&floors).is_err(), "{floors:?}");
522 assert_eq!(store.clock_state().unwrap(), before, "{floors:?}");
523 }
524 store
525 .raise_clock_floors(&ClockFloors {
526 basis_micros: Some(HLC_CEILING_MICROS),
527 last_seq: Some(HLC_CEILING_MICROS),
528 held_origin_seq: Some((INCARNATION_LIMIT - 1) << 32 | 7),
529 })
530 .unwrap();
531 }
532
533 #[test]
534 fn an_untrusted_clock_fails_own_writes_and_relays_without_writing() {
535 let (store, clock) = store_at(T0);
536 clock.trusted.store(false, Ordering::SeqCst);
537 let memory = Memory::new(
538 "held".to_string(),
539 MemoryType::Semantic,
540 "test".to_string(),
541 String::new(),
542 );
543 let err = store.store_memory(&memory).unwrap_err();
544 assert!(err.downcast_ref::<ClockUntrusted>().is_some(), "{err:#}");
545 let relayed = SyncRecord {
546 local_seq: 1,
547 origin_machine_id: "peer".to_string(),
548 origin_seq: 1,
549 op: SyncOp::Create,
550 node_type: SyncNodeType::Memory,
551 node_id: memory.id.to_string(),
552 timestamp: chrono::Utc::now(),
553 data: Some(serde_json::to_value(&memory).unwrap()),
554 };
555 let err = store.apply_record(&relayed).unwrap_err();
556 assert!(err.downcast_ref::<ClockUntrusted>().is_some(), "{err:#}");
557 assert_eq!(store.memory_count().unwrap(), 0);
558 assert!(store.sync_log_since(0).unwrap().is_empty());
559 assert_eq!(store.clock_state().unwrap().last, 0);
560
561 clock.trusted.store(true, Ordering::SeqCst);
562 store.store_memory(&memory).unwrap();
563 assert_eq!(store.memory_count().unwrap(), 1);
564 }
565}