use std::fmt;
use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};
use anyhow::{Result, ensure};
use rusqlite::{Connection, OptionalExtension, params};
pub const INCARNATION_EPOCH_SECS: i64 = 1_767_225_600;
pub const HLC_CEILING_MICROS: i64 = (INCARNATION_EPOCH_SECS + INCARNATION_LIMIT) * 1_000_000;
pub const NEW_LAYOUT_MIN: i64 = 1 << 32;
const INCARNATION_LIMIT: i64 = (1 << 31) - (1 << 24);
const N_LIMIT: i64 = 1 << 32;
const LAST: &str = "clock_last";
const BASIS: &str = "clock_basis";
const INCARNATION: &str = "clock_incarnation";
const INCARNATION_N: &str = "clock_incarnation_n";
const HELD_ORIGIN_SEQ: &str = "clock_held_origin_seq";
const AUTHORED: &str = "clock_authored_last";
pub trait WallClock: Send + Sync + std::panic::RefUnwindSafe {
fn now_micros(&self) -> Option<i64>;
}
pub struct SystemClock;
impl WallClock for SystemClock {
fn now_micros(&self) -> Option<i64> {
Some(match SystemTime::now().duration_since(UNIX_EPOCH) {
Ok(since) => since.as_micros() as i64,
Err(before) => -(before.duration().as_micros() as i64),
})
}
}
#[derive(Debug)]
pub struct ClockUntrusted;
impl fmt::Display for ClockUntrusted {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str("wall clock not yet trusted: writes are held")
}
}
impl std::error::Error for ClockUntrusted {}
#[derive(Debug)]
pub struct ClockFloorRejected(pub String);
impl fmt::Display for ClockFloorRejected {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.0)
}
}
impl std::error::Error for ClockFloorRejected {}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct ClockFloors {
pub basis_micros: Option<i64>,
pub last_seq: Option<i64>,
pub held_origin_seq: Option<i64>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
pub struct ClockState {
pub last: i64,
pub basis: i64,
pub incarnation: i64,
pub incarnation_n: i64,
pub incarnation_floor: i64,
}
pub(super) fn is_new_layout(origin: &str, origin_seq: i64) -> bool {
origin_seq >= NEW_LAYOUT_MIN || origin.starts_with("snap:") || origin.starts_with("replay:")
}
pub(super) fn wall_now(clock: &dyn WallClock) -> Result<i64> {
match clock.now_micros() {
Some(wall) => Ok(wall.min(HLC_CEILING_MICROS)),
None => Err(ClockUntrusted.into()),
}
}
pub(super) fn meta(conn: &Connection, key: &str) -> Result<Option<i64>> {
let value: Option<String> = conn
.query_row(
"SELECT value FROM index_meta WHERE key = ?1",
params![key],
|r| r.get(0),
)
.optional()?;
value
.map(|v| {
v.parse::<i64>()
.map_err(|e| anyhow::anyhow!("index_meta {key} = {v:?}: {e}"))
})
.transpose()
}
pub(super) fn set_meta(conn: &Connection, key: &str, value: i64) -> Result<()> {
conn.execute(
"INSERT OR REPLACE INTO index_meta (key, value) VALUES (?1, ?2)",
params![key, value.to_string()],
)?;
Ok(())
}
fn last(conn: &Connection) -> Result<i64> {
match meta(conn, LAST)? {
Some(last) => Ok(last),
None => Ok(conn.query_row(
"SELECT COALESCE(MAX(local_seq), 0) FROM sync_log",
[],
|r| r.get(0),
)?),
}
}
pub(super) fn state(conn: &Connection) -> Result<ClockState> {
Ok(ClockState {
last: last(conn)?,
basis: meta(conn, BASIS)?.unwrap_or(0),
incarnation: meta(conn, INCARNATION)?.unwrap_or(0),
incarnation_n: meta(conn, INCARNATION_N)?.unwrap_or(0),
incarnation_floor: meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0) >> 32,
})
}
pub(super) fn mint_local_seq(conn: &Connection, wall: i64) -> Result<i64> {
let basis = meta(conn, BASIS)?.unwrap_or(0);
let seq = (last(conn)? + 1).max(wall).max(basis);
set_meta(conn, LAST, seq)?;
Ok(seq)
}
pub(super) fn mint_authored(conn: &Connection, wall: i64) -> Result<i64> {
let basis = meta(conn, BASIS)?.unwrap_or(0);
let previous = meta(conn, AUTHORED)?.unwrap_or(0);
let authored = (previous + 1).max(wall).max(basis);
set_meta(conn, AUTHORED, authored)?;
Ok(authored)
}
pub(super) fn observe_authored(conn: &Connection, micros: i64) -> Result<()> {
let seen = micros.min(HLC_CEILING_MICROS);
if seen > meta(conn, AUTHORED)?.unwrap_or(0) {
set_meta(conn, AUTHORED, seen)?;
}
Ok(())
}
pub(super) fn mint_origin_seq(
conn: &Connection,
wall: i64,
drawn: &Mutex<Option<i64>>,
) -> Result<i64> {
let stored = meta(conn, INCARNATION)?.unwrap_or(0);
let n = meta(conn, INCARNATION_N)?.unwrap_or(0);
let held = meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0);
let mut drawn = drawn.lock().unwrap();
let keeps = *drawn == Some(stored) && held <= stored << 32 | n && n + 1 < N_LIMIT;
let (incarnation, n) = if keeps {
(stored, n + 1)
} else {
let basis = meta(conn, BASIS)?.unwrap_or(0);
let from_clock = wall.max(basis) / 1_000_000 - INCARNATION_EPOCH_SECS;
let incarnation = (stored + 1).max(from_clock).max((held >> 32) + 1).max(1);
ensure!(
incarnation < 1 << 31,
"incarnation {incarnation} does not fit an origin_seq"
);
(incarnation, 1)
};
set_meta(conn, INCARNATION, incarnation)?;
set_meta(conn, INCARNATION_N, n)?;
*drawn = Some(incarnation);
Ok(incarnation << 32 | n)
}
pub(super) fn raise_floors(conn: &Connection, floors: &ClockFloors) -> Result<()> {
for (what, value) in [
("peer time", floors.basis_micros),
("peer cursor", floors.last_seq),
] {
if let Some(v) = value
&& v > HLC_CEILING_MICROS
{
return Err(ClockFloorRejected(format!(
"{what} {v} is past the clock ceiling {HLC_CEILING_MICROS}"
))
.into());
}
}
if let Some(held) = floors.held_origin_seq
&& held >> 32 >= INCARNATION_LIMIT
{
return Err(ClockFloorRejected(format!(
"held origin_seq {held} has an incarnation past the clock ceiling"
))
.into());
}
if let Some(basis) = floors.basis_micros
&& basis > meta(conn, BASIS)?.unwrap_or(0)
{
set_meta(conn, BASIS, basis)?;
}
if let Some(cursor) = floors.last_seq
&& cursor > last(conn)?
{
set_meta(conn, LAST, cursor)?;
}
if let Some(held) = floors.held_origin_seq
&& held > meta(conn, HELD_ORIGIN_SEQ)?.unwrap_or(0)
{
set_meta(conn, HELD_ORIGIN_SEQ, held)?;
}
Ok(())
}
#[cfg(test)]
mod tests {
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicI64, Ordering};
use super::{
ClockFloors, ClockUntrusted, HLC_CEILING_MICROS, INCARNATION_EPOCH_SECS, INCARNATION_LIMIT,
WallClock, set_meta,
};
use crate::schema::{Memory, MemoryType, SyncNodeType, SyncOp, SyncRecord};
use crate::sqlite_store::SqliteStore;
use crate::store::{Store, StoreAdmin};
const SECOND: i64 = 1_000_000;
const T0: i64 = (INCARNATION_EPOCH_SECS + 20_000_000) * SECOND;
const T0_INCARNATION: i64 = 20_000_000;
struct TestClock {
micros: AtomicI64,
trusted: AtomicBool,
}
impl WallClock for TestClock {
fn now_micros(&self) -> Option<i64> {
self.trusted
.load(Ordering::SeqCst)
.then(|| self.micros.load(Ordering::SeqCst))
}
}
fn store_at(micros: i64) -> (SqliteStore, Arc<TestClock>) {
let clock = Arc::new(TestClock {
micros: AtomicI64::new(micros),
trusted: AtomicBool::new(true),
});
let store = SqliteStore::in_memory("m".to_string())
.unwrap()
.with_wall_clock(clock.clone());
(store, clock)
}
fn write(store: &SqliteStore) -> (i64, i64) {
store
.store_memory(&Memory::new(
"clock test".to_string(),
MemoryType::Semantic,
"test".to_string(),
String::new(),
))
.unwrap();
let entries = store.sync_log_since(0).unwrap();
let last = entries.last().unwrap();
(last.local_seq, last.origin_seq)
}
fn split(origin_seq: i64) -> (i64, i64) {
(origin_seq >> 32, origin_seq & 0xffff_ffff)
}
fn reopen(store: &SqliteStore) {
*store.incarnation.lock().unwrap() = None;
}
#[test]
fn local_seq_is_the_highest_of_last_plus_one_wall_and_basis() {
let (store, clock) = store_at(T0);
assert_eq!(write(&store).0, T0);
assert_eq!(write(&store).0, T0 + 1);
clock.micros.store(T0 - 3600 * SECOND, Ordering::SeqCst);
assert_eq!(write(&store).0, T0 + 2, "a clock stepped back carries on");
store
.raise_clock_floors(&ClockFloors {
basis_micros: Some(T0 + 60 * SECOND),
..Default::default()
})
.unwrap();
assert_eq!(write(&store).0, T0 + 60 * SECOND);
clock
.micros
.store(HLC_CEILING_MICROS + 3600 * SECOND, Ordering::SeqCst);
assert_eq!(write(&store).0, HLC_CEILING_MICROS, "the clock is capped");
}
fn authored(store: &SqliteStore) -> i64 {
write(store);
let entries = store.sync_log_since(0).unwrap();
entries.last().unwrap().timestamp.timestamp_micros()
}
#[test]
fn authored_time_is_the_highest_of_previous_plus_one_wall_and_basis() {
let (store, clock) = store_at(T0);
assert_eq!(authored(&store), T0);
assert_eq!(
authored(&store),
T0 + 1,
"writes in one microsecond never tie"
);
clock.micros.store(T0 - 3600 * SECOND, Ordering::SeqCst);
assert_eq!(
authored(&store),
T0 + 2,
"a clock stepped back never writes in the past"
);
store
.raise_clock_floors(&ClockFloors {
basis_micros: Some(T0 + 60 * SECOND),
..Default::default()
})
.unwrap();
assert_eq!(authored(&store), T0 + 60 * SECOND);
clock.micros.store(T0 + 120 * SECOND, Ordering::SeqCst);
assert_eq!(authored(&store), T0 + 120 * SECOND);
}
#[test]
fn a_relay_keeps_the_incoming_authored_time() {
let (store, _) = store_at(T0);
let memory = Memory::new(
"relayed".to_string(),
MemoryType::Semantic,
"test".to_string(),
String::new(),
);
let authored = chrono::DateTime::from_timestamp_micros(T0 - 7 * SECOND).unwrap();
let record = SyncRecord {
local_seq: 1,
origin_machine_id: "peer".to_string(),
origin_seq: (13u64 << 32) | 1,
op: SyncOp::Create,
node_type: SyncNodeType::Memory,
node_id: memory.id.to_string(),
timestamp: authored,
data: Some(serde_json::to_value(&memory).unwrap()),
};
store.apply_record(&record).unwrap();
let entries = store.sync_log_since(0).unwrap();
assert_eq!(entries.last().unwrap().timestamp, authored);
}
#[test]
fn an_open_draws_one_incarnation_and_counts_within_it() {
let (store, _) = store_at(T0);
assert_eq!(split(write(&store).1), (T0_INCARNATION, 1));
assert_eq!(split(write(&store).1), (T0_INCARNATION, 2));
reopen(&store);
assert_eq!(
split(write(&store).1),
(T0_INCARNATION + 1, 1),
"a new open in the same second still draws above the last"
);
let state = store.clock_state().unwrap();
assert_eq!(
(state.incarnation, state.incarnation_n),
(T0_INCARNATION + 1, 1)
);
}
#[test]
fn a_clock_before_the_epoch_still_draws_incarnation_one() {
let (store, _) = store_at(0);
assert_eq!(split(write(&store).1), (1, 1));
}
#[test]
fn a_rolled_back_draw_is_redrawn_and_n_restarts() {
let (store, _) = store_at(T0);
assert_eq!(split(write(&store).1), (T0_INCARNATION, 1));
reopen(&store);
let failed: anyhow::Result<()> = store.with_txn(|tx| {
store.append_sync_log(tx, SyncOp::Delete, SyncNodeType::Memory, "x", None, None)?;
anyhow::bail!("roll back")
});
assert!(failed.is_err());
assert_eq!(store.clock_state().unwrap().incarnation, T0_INCARNATION);
assert_eq!(split(write(&store).1), (T0_INCARNATION + 1, 1));
}
#[test]
fn a_raised_floor_forces_a_draw_above_it() {
let (store, _) = store_at(T0);
write(&store);
let held = (T0_INCARNATION + 5) << 32 | 9;
store
.raise_clock_floors(&ClockFloors {
held_origin_seq: Some(held),
..Default::default()
})
.unwrap();
assert_eq!(split(write(&store).1), (T0_INCARNATION + 6, 1));
assert_eq!(split(write(&store).1), (T0_INCARNATION + 6, 2));
}
#[test]
fn a_peer_holding_this_stores_current_key_keeps_its_incarnation() {
let (store, _) = store_at(T0);
write(&store);
let (_, own) = write(&store);
store
.raise_clock_floors(&ClockFloors {
held_origin_seq: Some(own),
..Default::default()
})
.unwrap();
assert_eq!(split(write(&store).1), (T0_INCARNATION, 3));
assert_eq!(
store.clock_state().unwrap().incarnation_floor,
T0_INCARNATION
);
}
#[test]
fn running_out_of_n_starts_a_new_incarnation() {
let (store, _) = store_at(T0);
write(&store);
set_meta(&store.conn(), super::INCARNATION_N, (1 << 32) - 2).unwrap();
assert_eq!(split(write(&store).1), (T0_INCARNATION, (1 << 32) - 1));
assert_eq!(split(write(&store).1), (T0_INCARNATION + 1, 1));
}
#[test]
fn floors_only_rise() {
let (store, _) = store_at(T0);
write(&store);
let raise = |basis, last, held| {
store
.raise_clock_floors(&ClockFloors {
basis_micros: Some(basis),
last_seq: Some(last),
held_origin_seq: Some(held),
})
.unwrap()
};
raise(T0 + 10, T0 + 20, 30 << 32);
raise(T0 - 10, T0 - 20, 3 << 32);
let state = store.clock_state().unwrap();
assert_eq!(
(state.basis, state.last, state.incarnation_floor),
(T0 + 10, T0 + 20, 30)
);
}
#[test]
fn floors_past_the_ceiling_are_rejected_and_raise_nothing() {
let (store, _) = store_at(T0);
write(&store);
let before = store.clock_state().unwrap();
for floors in [
ClockFloors {
basis_micros: Some(HLC_CEILING_MICROS + 1),
last_seq: Some(T0 + 100),
held_origin_seq: None,
},
ClockFloors {
basis_micros: Some(T0 + 100),
last_seq: Some(HLC_CEILING_MICROS + 1),
held_origin_seq: None,
},
ClockFloors {
basis_micros: Some(T0 + 100),
last_seq: None,
held_origin_seq: Some(INCARNATION_LIMIT << 32),
},
] {
assert!(store.raise_clock_floors(&floors).is_err(), "{floors:?}");
assert_eq!(store.clock_state().unwrap(), before, "{floors:?}");
}
store
.raise_clock_floors(&ClockFloors {
basis_micros: Some(HLC_CEILING_MICROS),
last_seq: Some(HLC_CEILING_MICROS),
held_origin_seq: Some((INCARNATION_LIMIT - 1) << 32 | 7),
})
.unwrap();
}
#[test]
fn an_untrusted_clock_fails_own_writes_and_relays_without_writing() {
let (store, clock) = store_at(T0);
clock.trusted.store(false, Ordering::SeqCst);
let memory = Memory::new(
"held".to_string(),
MemoryType::Semantic,
"test".to_string(),
String::new(),
);
let err = store.store_memory(&memory).unwrap_err();
assert!(err.downcast_ref::<ClockUntrusted>().is_some(), "{err:#}");
let relayed = SyncRecord {
local_seq: 1,
origin_machine_id: "peer".to_string(),
origin_seq: 1,
op: SyncOp::Create,
node_type: SyncNodeType::Memory,
node_id: memory.id.to_string(),
timestamp: chrono::Utc::now(),
data: Some(serde_json::to_value(&memory).unwrap()),
};
let err = store.apply_record(&relayed).unwrap_err();
assert!(err.downcast_ref::<ClockUntrusted>().is_some(), "{err:#}");
assert_eq!(store.memory_count().unwrap(), 0);
assert!(store.sync_log_since(0).unwrap().is_empty());
assert_eq!(store.clock_state().unwrap().last, 0);
clock.trusted.store(true, Ordering::SeqCst);
store.store_memory(&memory).unwrap();
assert_eq!(store.memory_count().unwrap(), 1);
}
}