Skip to main content

second_brain_core/sqlite_store/
clock.rs

1use std::fmt;
2use std::sync::Mutex;
3use std::time::{SystemTime, UNIX_EPOCH};
4
5use anyhow::{Result, ensure};
6use rusqlite::{Connection, OptionalExtension, params};
7
8/// 2026-01-01T00:00:00Z: incarnations count seconds from here.
9pub const INCARNATION_EPOCH_SECS: i64 = 1_767_225_600;
10
11/// The time at which a wall-clock incarnation would reach 2^31 - 2^24. No
12/// clock reading, peer basis or cursor above it is accepted, so
13/// `incarnation << 32 | n` always fits an i64, and the value stays below
14/// 2^53 for JSON.
15pub const HLC_CEILING_MICROS: i64 = (INCARNATION_EPOCH_SECS + INCARNATION_LIMIT) * 1_000_000;
16
17/// Every origin_seq minted with an incarnation is at least this, and every
18/// legacy one (a local_seq from before clock seqs) is below it.
19pub 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    /// Wall-clock reading in microseconds since the Unix epoch, or None while
33    /// time is untrusted.
34    fn now_micros(&self) -> Option<i64>;
35}
36
37/// Always trusted, so an embedder that never configures a clock is never
38/// held.
39pub 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/// A write that would mint a seq while the store's `WallClock` returns
51/// None fails with this error inside its `anyhow::Error`.
52#[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/// A peer report `raise_clock_floors` refused because a value lies past the
64/// clock ceiling, as opposed to a store failure.
65#[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/// What a peer's handshake reports, each raising its own floor: the HLC
77/// basis (µs), `last` (the local_seq space, from the peer's cursor on this
78/// log) and the incarnation floor (from the highest origin_seq of this
79/// store's own records the peer holds).
80#[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
131/// A store from before clock seqs has no `clock_last`; its log's top seq is
132/// where it carries on.
133fn 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
161/// A local write's authored time: strictly monotone per store, never behind
162/// the peer basis, so a device whose clock lags or steps back never writes
163/// in the past.
164pub(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
172/// The receive half of authored time: a write that landed here, applied or
173/// seeded, moves the next local write past it, so a local delete or update
174/// never carries a stamp older than the state it replaces. Only the clock
175/// ceiling bounds it, so a record authored by a clock running ahead carries
176/// every later local write that far ahead too.
177pub(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
185/// `drawn` is the incarnation this open drew. It is redrawn when the
186/// persisted one differs (the transaction that drew it rolled back), when a
187/// peer holds a key above the last one minted here (this store is a restored
188/// copy), or when `n` runs out.
189pub(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}