didbot_schema/

tid.rs

//! Timestamp identifiers: the sortable keys this server mints records under.
//!
//! `didbot-pds`'s record store mints TIDs, and this module reads one back. A
//! minter with no matching parser is a format nothing can check, and the
//! first thing a wrong bit in an rkey costs is the ordering the whole store is
//! built on.
//!
//! A TID is a 64-bit integer rendered as thirteen characters of a base32
//! alphabet ordered so that ASCII order matches numeric order. The layout is
//! one clear top bit, 53 bits of microseconds since the Unix epoch, and a
//! 10-bit clock identifier.
//!
//! [`Minter`] is the other half: the one place a TID is made. Record keys
//! come from it and so do the revisions a commit is stamped with, and they
//! come from the same one per store so that neither can repeat the other.

use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};

/// The alphabet a TID is written in: base32 with the digits and letters
/// reordered so that string order matches numeric order.
pub const BASE32_SORTABLE: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz";

/// How many characters a TID always is. Not a maximum: a TID is never padded
/// and never abbreviated.
pub const TID_LENGTH: usize = 13;

/// Why a string is not a TID.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum TidError {
    /// Not exactly [`TID_LENGTH`] characters.
    #[error("tid is {0} characters, must be exactly {TID_LENGTH}")]
    WrongLength(usize),
    /// A character outside [`BASE32_SORTABLE`]. Case matters: `3JZFCIJPJ2Z2A`
    /// is not the same string as `3jzfcijpj2z2a` and is not a TID.
    #[error("invalid character {0:?} in tid: not sortable base32")]
    InvalidCharacter(char),
    /// The top bit of the 64-bit value is set.
    ///
    /// The leading character therefore has to fall in the first half of the
    /// alphabet, which is what rules out `zzzzzzzzzzzzz`. The bit is reserved,
    /// and a value that uses it is a different format wearing this one's
    /// shape.
    #[error("tid has its high bit set: leading character {0:?} is out of range")]
    HighBitSet(char),
}

/// A parsed TID: the timestamp it carries and the clock that minted it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Tid {
    micros: u64,
    clock_id: u16,
}

impl Tid {
    /// Microseconds since the Unix epoch, as the key encodes them.
    ///
    /// This is what the minter's clock said, not a verified time. A TID says
    /// when its writer believed it was writing.
    pub fn micros(self) -> u64 {
        self.micros
    }

    /// The 10-bit clock identifier that distinguishes concurrent minters.
    pub fn clock_id(self) -> u16 {
        self.clock_id
    }
}

/// Checks a string against the TID rules.
///
/// ```
/// use didbot_schema::tid::validate;
/// assert!(validate("3jzfcijpj2z2a").is_ok());
/// assert!(validate("3JZFCIJPJ2Z2A").is_err()); // case-sensitive
/// assert!(validate("zzzzzzzzzzzzz").is_err()); // high bit set
/// ```
pub fn validate(tid: &str) -> Result<(), TidError> {
    parse(tid).map(|_| ())
}

/// Decodes a TID into the timestamp and clock identifier it carries.
pub fn parse(tid: &str) -> Result<Tid, TidError> {
    // Length is counted in characters rather than bytes so that a string of
    // thirteen multi-byte characters is rejected for its characters and not
    // for a byte count that would read as a puzzling off-by-26.
    let length = tid.chars().count();
    if length != TID_LENGTH {
        return Err(TidError::WrongLength(length));
    }
    let mut value: u64 = 0;
    for (index, ch) in tid.chars().enumerate() {
        let digit = BASE32_SORTABLE
            .iter()
            .position(|candidate| u32::from(*candidate) == u32::from(ch))
            .ok_or(TidError::InvalidCharacter(ch))?;
        // The leading character contributes bits 63..=59, and bit 63 is
        // reserved. Only the first sixteen letters of the alphabet leave it
        // clear.
        if index == 0 && digit >= 16 {
            return Err(TidError::HighBitSet(ch));
        }
        value = (value << 5) | digit as u64;
    }
    Ok(Tid {
        micros: (value >> 10) & ((1 << 53) - 1),
        clock_id: (value & 0x3ff) as u16,
    })
}

/// Encodes a 64-bit value as 13 characters of [`BASE32_SORTABLE`].
///
/// The alphabet's ordering is the whole point: it lets a store keep records in
/// a plain ordered map and get newest-first listing from the key alone.
fn encode_key(value: u64) -> String {
    let mut out = [b'2'; 13];
    let mut remaining = value;
    for slot in out.iter_mut().rev() {
        *slot = BASE32_SORTABLE[(remaining & 0x1f) as usize];
        remaining >>= 5;
    }
    // Every byte came out of a 32-entry ASCII table.
    String::from_utf8_lossy(&out).into_owned()
}

/// Reads back a key [`encode_key`] produced, if the string is one.
///
/// Used only on replay, to move a fresh minter past the keys a previous run
/// of this process already handed out. Anything that is not thirteen
/// characters of the sortable alphabet is not a key this server minted, and
/// answers `None` rather than a number derived from part of it.
fn decode_key(key: &str) -> Option<u64> {
    if key.len() != 13 {
        return None;
    }
    let mut value = 0u64;
    for byte in key.bytes() {
        let digit = BASE32_SORTABLE
            .iter()
            .position(|candidate| *candidate == byte)?;
        value = (value << 5) | digit as u64;
    }
    Some(value)
}

/// Mints TIDs that sort in the order they were minted.
///
/// A TID as atproto specifies it: microseconds since the Unix epoch in the
/// low 53 bits above a 10-bit clock identifier, with the top bit clear,
/// rendered in [`BASE32_SORTABLE`]. Two properties matter. It is timestamped,
/// so a TID says when it was minted without a second field beside it; and it
/// is sortable as a string, so newest-first is a reverse iteration of an
/// ordered map rather than a sort.
///
/// One minter serves a store's record keys and its commit revisions together.
/// They are separate sequences to a reader and the same sequence here, which
/// costs nothing — a revision is not required to be dense — and buys the one
/// property both need: that nothing this store hands out ever repeats or
/// sorts backwards, whatever the clock does.
#[derive(Debug)]
pub struct Minter {
    clock_id: u64,
    last: Mutex<u64>,
}

impl Minter {
    /// A minter with a fixed clock identifier.
    ///
    /// The clock id is derived from the process start rather than randomly,
    /// because this store is per-process and never merges with another: its
    /// only job is to keep two processes writing the same logical repository
    /// from colliding, which cannot happen to an in-memory store anyway.
    #[must_use]
    pub fn new() -> Self {
        Self {
            clock_id: micros_now() & 0x3ff,
            last: Mutex::new(0),
        }
    }

    /// The next TID, strictly greater than every one this minter has returned.
    ///
    /// The clock is only read, never trusted for ordering. Two writes inside
    /// one microsecond, or a clock that steps backwards, would otherwise
    /// produce a key that sorts before an earlier record and silently reorder
    /// a listing.
    pub fn next(&self) -> String {
        let mut last = self
            .last
            .lock()
            .unwrap_or_else(|poisoned| poisoned.into_inner());
        let micros = micros_now().max(*last + 1);
        *last = micros;
        encode_key((micros << 10) | self.clock_id)
    }

    /// Notes a TID somebody else minted, so this minter never repeats it.
    ///
    /// A restart replays keys a previous process wrote, and the clock is the
    /// only thing that would otherwise keep the new process past them. That
    /// is enough while the clock moves forward and is exactly the assumption
    /// [`Minter::next`] already refuses to make, so replay states it here
    /// instead: a key that sorted after everything when it was written must
    /// still sort after everything when the log is read back.
    pub fn observe(&self, minted: &str) {
        let Some(value) = decode_key(minted) else {
            return;
        };
        let mut last = self
            .last
            .lock()
            .unwrap_or_else(|poisoned| poisoned.into_inner());
        *last = (*last).max(value >> 10);
    }
}

impl Default for Minter {
    fn default() -> Self {
        Self::new()
    }
}

/// Microseconds since the Unix epoch, clamped into a TID's 53 bits.
///
/// A clock before the epoch reads as the epoch. It is not worth an error
/// path: the resulting key is still unique and still sorts, because
/// [`Minter::next`] enforces both regardless of what the clock says.
fn micros_now() -> u64 {
    let micros = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .map(|since| since.as_micros())
        .unwrap_or_default();
    u64::try_from(micros).unwrap_or(u64::MAX) & ((1 << 53) - 1)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn keys_mint_in_ascending_order_even_within_one_microsecond() {
        let minter = Minter::new();
        let keys: Vec<String> = (0..1000).map(|_| minter.next()).collect();
        let mut sorted = keys.clone();
        sorted.sort();
        assert_eq!(keys, sorted, "record keys must sort in minting order");
        sorted.dedup();
        assert_eq!(sorted.len(), keys.len(), "record keys must be unique");
    }

    #[test]
    fn keys_are_thirteen_characters_of_the_sortable_alphabet() {
        let key = Minter::new().next();
        assert_eq!(key.len(), 13, "a tid is 13 characters: {key}");
        assert!(
            key.bytes().all(|b| BASE32_SORTABLE.contains(&b)),
            "{key} is not base32-sortable"
        );
    }

    #[test]
    fn a_key_decodes_back_to_what_it_encoded() {
        for value in [0u64, 1, 31, 32, 1 << 40, (1 << 63) - 1] {
            assert_eq!(decode_key(&encode_key(value)), Some(value));
        }
    }

    #[test]
    fn anything_that_is_not_a_minted_key_decodes_to_nothing() {
        assert_eq!(decode_key("self"), None);
        assert_eq!(decode_key(""), None);
        // Thirteen characters, but `0`, `1`, `8` and `9` are not in the
        // sortable alphabet — it starts at `2` so that the digits and the
        // letters sort in one run.
        assert_eq!(decode_key("1111111111111"), None);
        assert_eq!(decode_key("9999999999999"), None);
    }

    /// A restart replays keys a previous process minted. A fresh minter must
    /// come out above them even if the clock says otherwise, or a listing
    /// silently reorders across the restart.
    #[test]
    fn a_minter_never_repeats_a_key_it_was_shown() {
        let minter = Minter::new();
        let ahead = encode_key(((micros_now() + 60_000_000) << 10) | 7);
        minter.observe(&ahead);
        let next = minter.next();
        assert!(next > ahead, "{next} should sort after {ahead}");
    }

    #[test]
    fn encoding_preserves_numeric_order() {
        assert!(encode_key(1) < encode_key(2));
        assert!(encode_key(31) < encode_key(32));
        assert!(encode_key(1 << 40) < encode_key(1 << 41));
    }
}