//! The commits the parts write: of random bytes, as the write part's first //! tables and the first replay table have them, and realistic ones, the same //! for the same seed, wherever what the bytes are matters (sizes, //! compression, reads). And an account's state after so many of the //! realistic ones: its records and the tree over them. //! //! A realistic commit is a post of about 300 bytes of DAG-CBOR (a `$type`, //! a text of common words, `langs`, a `createdAt`, and three times in ten a //! reply's two CIDs and URIs), two MST nodes of about 1 KB (entries of a //! key with its prefix shared, a CID, and sometimes a subtree's), a commit //! block of about 190 bytes (a DID, a rev, the tree's CID, a signature of //! 64 random bytes) and its event's frame, about 3 KB: a `#commit` with //! those blocks again in a CAR, and the DID, rev and path as strings. //! Every CID is the four bytes a CID of a DAG-CBOR block begins with and //! 32 random ones. use crate::util::Rng; use std::sync::LazyLock; /// The seed of every realistic commit the script writes. pub const SEED: u64 = 1; /// A createRecord's blocks, in bytes, as the random commits have them: the /// commit, the record, two MST nodes; and its event's frame. const BLOCKS: [usize; 4] = [180, 100, 1000, 1000]; const EVENT: usize = 2500; /// `n` bytes that do not compress, the same for the same seed. fn bytes(n: usize, seed: u64) -> Vec { let mut x = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1; (0..n) .map(|_| { x ^= x << 13; x ^= x >> 7; x ^= x << 17; x as u8 }) .collect() } /// One commit: its rev, its record's path, its blocks by CID (the commit's, /// the record's, then the MST nodes), and its event's frame. pub struct Commit { pub op: u64, pub rev: String, pub path: String, pub blocks: Vec<(Vec, Vec)>, pub event: Vec, } /// A commit of random bytes. pub fn random(op: u64) -> Commit { let rev = format!("3l{op:011}"); Commit { op, path: format!("{COLLECTION}/{rev}"), rev, blocks: BLOCKS .iter() .enumerate() .map(|(i, &n)| { ( bytes(36, op * 8 + i as u64 + 1), bytes(n, op * 8 + i as u64 + 5), ) }) .collect(), event: bytes(EVENT, op * 8 + 7), } } /// The MST nodes a commit made, which the account's next takes out. pub fn nodes(c: &Commit) -> Vec> { c.blocks[2..].iter().map(|(cid, _)| cid.clone()).collect() } // ---- Realistic commits ---------------------------------------------------- const COLLECTION: &str = "app.bsky.feed.post"; /// When the first commit is made, in microseconds since the epoch, how long /// after it each next one is, and a day. const BASE: u64 = 1_700_000_000_000_000; const STEP: u64 = 250_000; const DAY: u64 = 86_400_000_000; const WORDS: &str = "the be to of and a in that have I it for not on with he as you do at \ this but his by from they we say her she or an will my one all would there their what so up \ out if about who get which go me when make can like time no just him know take people into \ year your good some could them see other than then now look only come its over think also \ back after use two how our work first well way even new want because any these give day most \ us is was are been has had were said did get may made find long down day did come part over \ new sound take only little work know place year live me back give most very after thing our \ just name good sentence man think say great where help through much before line right too \ mean old any same tell boy follow came want show also around form three small set put end \ does another well large must big even such because turn here why ask went men read need land \ different home move try kind hand picture again change off play spell air away animal house \ point page letter mother answer found study still learn should world high every near add \ food between own below country plant last school father keep tree never start city earth eye \ light thought head under story saw left few while along might close something seem next hard \ open example begin life always those both paper together got group often run important until \ children side feet car mile night walk white sea began grow took river four carry state once \ book hear stop without second later miss idea enough eat face watch far real almost let above \ girl sometimes mountain cut young talk soon list song being leave family morning today \ really love coffee weather music game friend happy week tonight thanks maybe actually"; static LIST: LazyLock> = LazyLock::new(|| WORDS.split_ascii_whitespace().collect()); const B32: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz"; /// A TID: 13 characters that sort as their time does. fn tid(micros: u64, clock: u64) -> String { let v = (micros << 10) | (clock & 0x3ff); (0..13) .map(|i| B32[((v >> (60 - 5 * i)) & 31) as usize] as char) .collect() } /// An account's DID. pub fn did(seed: u64, account: u64) -> String { let mut r = Rng::of(&[seed, 3, account]); let mut s = String::from("did:plc:"); s.extend((0..24).map(|_| B32[r.below(32) as usize] as char)); s } /// A CID of a DAG-CBOR block: 36 bytes. fn cid(r: &mut Rng) -> Vec { let mut out = vec![0x01, 0x71, 0x12, 0x20]; r.fill(&mut out, 32); out } /// A time as a record's `createdAt` has it. fn iso(micros: u64) -> String { let (secs, millis) = (micros / 1_000_000, micros / 1000 % 1000); let (days, rem) = (secs / 86400, secs % 86400); // The civil date of a day since the epoch (Howard Hinnant's). let z = days + 719_468; let (era, doe) = (z / 146_097, z % 146_097); let yoe = (doe - doe / 1460 + doe / 36524 - doe / 146_096) / 365; let doy = doe - (365 * yoe + yoe / 4 - yoe / 100); let mp = (5 * doy + 2) / 153; let (d, m) = (doy - (153 * mp + 2) / 5 + 1, (mp + 2) % 12 + 1); let y = yoe + era * 400 + u64::from(m <= 2); format!( "{y:04}-{m:02}-{d:02}T{:02}:{:02}:{:02}.{millis:03}Z", rem / 3600, rem / 60 % 60, rem % 60 ) } // DAG-CBOR, as much of it as these blocks need. fn head(out: &mut Vec, major: u8, n: u64) { let m = major << 5; match n { 0..=23 => out.push(m | n as u8), 24..=0xff => out.extend_from_slice(&[m | 24, n as u8]), 0x100..=0xffff => { out.push(m | 25); out.extend_from_slice(&(n as u16).to_be_bytes()); } 0x1_0000..=0xffff_ffff => { out.push(m | 26); out.extend_from_slice(&(n as u32).to_be_bytes()); } _ => { out.push(m | 27); out.extend_from_slice(&n.to_be_bytes()); } } } fn text(out: &mut Vec, s: &str) { head(out, 3, s.len() as u64); out.extend_from_slice(s.as_bytes()); } fn blob(out: &mut Vec, b: &[u8]) { head(out, 2, b.len() as u64); out.extend_from_slice(b); } /// A link to a block: tag 42 over its CID. fn link(out: &mut Vec, cid: &[u8]) { out.extend_from_slice(&[0xd8, 42]); head(out, 2, cid.len() as u64 + 1); out.push(0); out.extend_from_slice(cid); } const NULL: u8 = 0xf6; const FALSE: u8 = 0xf4; fn varint(out: &mut Vec, mut n: u64) { while n >= 0x80 { out.push(n as u8 | 0x80); n >>= 7; } out.push(n as u8); } /// When commit `op`, of `account`, is made. fn micros(seed: u64, op: u64, account: u64) -> u64 { BASE + op * STEP + Rng::of(&[seed, 1, op, account]).below(STEP) } /// The path of the record commit `op`, of `account`, puts. pub fn path(seed: u64, op: u64, account: u64) -> String { format!("{COLLECTION}/{}", tid(micros(seed, op, account), account)) } /// A record: where it is, the rev of the commit that put it, its CID and /// its bytes. pub struct Record { pub path: String, pub rev: String, pub cid: Vec, pub bytes: Vec, } /// The record commit `op`, of `account`, puts; or, with `version` over 0, /// what a later commit put in its place, at the same path. pub fn record(seed: u64, op: u64, account: u64, version: u64) -> Record { let made = micros(seed, op, account); let at = made + version * DAY; let mut r = Rng::of(&[seed, 2, op, account, version]); let own = cid(&mut r); let mut out = Vec::with_capacity(640); let reply = r.below(10) < 3; head(&mut out, 5, 4 + u64::from(reply)); text(&mut out, "text"); let list = &*LIST; let n = list.len() as u64; let mut body = String::new(); for i in 0..10 + r.below(46) { if i > 0 { body.push(' '); } // The first of the list more often than the last, as words go. body.push_str(list[(r.below(n) * r.below(n) / n) as usize]); } text(&mut out, &body); text(&mut out, "$type"); text(&mut out, COLLECTION); text(&mut out, "langs"); head(&mut out, 4, 1); text(&mut out, "en"); if reply { text(&mut out, "reply"); head(&mut out, 5, 2); let other = did(seed, r.below(1 << 20)); for name in ["root", "parent"] { text(&mut out, name); head(&mut out, 5, 2); text(&mut out, "cid"); let c = cid(&mut r); link(&mut out, &c); text(&mut out, "uri"); let uri = format!("at://{other}/{COLLECTION}/{}", tid(at - r.below(DAY), 0)); text(&mut out, &uri); } } text(&mut out, "createdAt"); text(&mut out, &iso(at)); Record { path: format!("{COLLECTION}/{}", tid(made, account)), rev: tid(at, account), cid: own, bytes: out, } } /// An entry of an MST node: a key, its record's CID, and the subtree after /// it, if there is one. struct Entry<'a> { key: &'a str, value: &'a [u8], tree: Option<&'a [u8]>, } /// An MST node: its left subtree, if any, and its entries, each key less /// the prefix it shares with the one before. fn node(left: Option<&[u8]>, entries: &[Entry]) -> Vec { let mut out = Vec::with_capacity(1280); head(&mut out, 5, 2); text(&mut out, "e"); head(&mut out, 4, entries.len() as u64); let mut before = ""; for e in entries { let shared = before .bytes() .zip(e.key.bytes()) .take_while(|(a, b)| a == b) .count(); head(&mut out, 5, 4); text(&mut out, "k"); blob(&mut out, &e.key.as_bytes()[shared..]); text(&mut out, "p"); head(&mut out, 0, shared as u64); text(&mut out, "t"); match e.tree { Some(c) => link(&mut out, c), None => out.push(NULL), } text(&mut out, "v"); link(&mut out, e.value); before = e.key; } text(&mut out, "l"); match left { Some(c) => link(&mut out, c), None => out.push(NULL), } out } /// A node of a tree no one holds whole: entries of keys before `own`, each /// with a subtree one time in `trees`, then `own`. fn loose_node(r: &mut Rng, at: u64, clock: u64, own: (&str, &[u8]), trees: u64) -> Vec { let n = 10 + r.below(5) as usize; let mut times: Vec = (0..n).map(|_| r.below(4 * 3_600_000_000) + 1).collect(); // Each key so long before the next. for i in (0..n - 1).rev() { times[i] += times[i + 1]; } let keys: Vec = times .iter() .map(|back| format!("{COLLECTION}/{}", tid(at - back, clock))) .collect(); let cids: Vec<(Vec, Option>)> = (0..n) .map(|_| (cid(r), (r.below(trees) == 0).then(|| cid(r)))) .collect(); let mut entries: Vec = keys .iter() .zip(&cids) .map(|(key, (value, tree))| Entry { key, value, tree: tree.as_deref(), }) .collect(); entries.push(Entry { key: own.0, value: own.1, tree: None, }); let left = (r.below(2) == 0).then(|| cid(r)); node(left.as_deref(), &entries) } /// A commit's block: what a signed commit holds. fn commit_block(r: &mut Rng, did: &str, rev: &str, data: &[u8]) -> Vec { let mut out = Vec::with_capacity(200); head(&mut out, 5, 6); text(&mut out, "did"); text(&mut out, did); text(&mut out, "rev"); text(&mut out, rev); text(&mut out, "sig"); head(&mut out, 2, 64); r.fill(&mut out, 64); text(&mut out, "data"); link(&mut out, data); text(&mut out, "prev"); out.push(NULL); text(&mut out, "version"); head(&mut out, 0, 3); out } /// A commit's event as the firehose sends it: a `#commit` frame, its /// blocks in a CAR. fn event(c: &Commit, did: &str, since: &str, time: &str) -> Vec { let commit = &c.blocks[0].0; let mut car = Vec::with_capacity(3200); let mut header = Vec::with_capacity(64); head(&mut header, 5, 2); text(&mut header, "roots"); head(&mut header, 4, 1); link(&mut header, commit); text(&mut header, "version"); head(&mut header, 0, 1); varint(&mut car, header.len() as u64); car.extend_from_slice(&header); for (cid, block) in &c.blocks { varint(&mut car, (cid.len() + block.len()) as u64); car.extend_from_slice(cid); car.extend_from_slice(block); } let mut out = Vec::with_capacity(car.len() + 320); head(&mut out, 5, 2); text(&mut out, "t"); text(&mut out, "#commit"); text(&mut out, "op"); head(&mut out, 0, 1); head(&mut out, 5, 11); text(&mut out, "ops"); head(&mut out, 4, 1); head(&mut out, 5, 3); text(&mut out, "cid"); link(&mut out, &c.blocks[1].0); text(&mut out, "path"); text(&mut out, &c.path); text(&mut out, "action"); text(&mut out, "create"); text(&mut out, "rev"); text(&mut out, &c.rev); text(&mut out, "seq"); head(&mut out, 0, c.op); text(&mut out, "repo"); text(&mut out, did); text(&mut out, "time"); text(&mut out, time); text(&mut out, "blobs"); head(&mut out, 4, 0); text(&mut out, "since"); text(&mut out, since); text(&mut out, "blocks"); blob(&mut out, &car); text(&mut out, "commit"); link(&mut out, commit); text(&mut out, "rebase"); out.push(FALSE); text(&mut out, "tooBig"); out.push(FALSE); out } /// Realistic commit `op`, of `account`: the same for the same seed. pub fn real(seed: u64, op: u64, account: u64) -> Commit { let rec = record(seed, op, account, 0); let at = micros(seed, op, account); let mut r = Rng::of(&[seed, 4, op, account]); let did = did(seed, account); let own = (rec.path.as_str(), rec.cid.as_slice()); // The node the record is in, and one above it. let leaf = (cid(&mut r), loose_node(&mut r, at, account, own, 4)); let above = (cid(&mut r), loose_node(&mut r, at, account, own, 2)); let commit = (cid(&mut r), commit_block(&mut r, &did, &rec.rev, &above.0)); let since = tid(at - r.below(DAY) - 1, account); let mut c = Commit { op, rev: rec.rev, path: rec.path, blocks: vec![commit, (rec.cid, rec.bytes), leaf, above], event: Vec::new(), }; c.event = event(&c, &did, &since, &iso(at)); c } // ---- An account's state --------------------------------------------------- /// The entries of a node at the tree's foot, and of one above. const LEAF: usize = 16; const FAN: usize = 10; /// A block of the tree: its CID, its bytes, and the rev of the commit that /// put it there. #[derive(Clone)] pub struct Block { pub cid: Vec, pub bytes: Vec, pub rev: String, } /// What an account holds after its commits: its records in order of path, /// and the tree over them, a node at the foot for each 16 records, one /// above for each 10 of those, and the root. pub struct State { seed: u64, account: u64, accounts: u64, pub records: Vec, leaves: Vec, above: Vec, root: Block, } impl State { /// The state of `account`, one of `accounts`, after `records` commits: /// its record `i` is commit `i * accounts + account + 1`'s, the /// accounts' commits taking turns. pub fn new(seed: u64, account: u64, accounts: u64, records: usize) -> State { let records: Vec = (0..records as u64) .map(|i| record(seed, i * accounts + account + 1, account, 0)) .collect(); let empty = Block { cid: Vec::new(), bytes: Vec::new(), rev: String::new(), }; let mut s = State { seed, account, accounts, leaves: vec![empty.clone(); records.len().div_ceil(LEAF)], above: vec![empty.clone(); records.len().div_ceil(LEAF).div_ceil(FAN)], root: empty, records, }; for i in 0..s.leaves.len() { s.leaf(i, 0); } for i in 0..s.above.len() { s.over(i, 0); } s.top(0); s } fn cid(&self, level: u64, i: usize, version: u64) -> Vec { cid(&mut Rng::of(&[ self.seed, 5, self.account, level, i as u64, version, ])) } /// The rev of the latest commit to a record among `records`. fn rev(records: &[Record]) -> String { records .iter() .map(|r| r.rev.as_str()) .max() .unwrap_or_default() .to_string() } /// Make node `i` at the foot again, of the records it holds now. fn leaf(&mut self, i: usize, version: u64) { let mine = &self.records[i * LEAF..self.records.len().min((i + 1) * LEAF)]; let entries: Vec = mine .iter() .map(|r| Entry { key: &r.path, value: &r.cid, tree: None, }) .collect(); self.leaves[i] = Block { cid: self.cid(0, i, version), bytes: node(None, &entries), rev: State::rev(mine), }; } /// Make node `i` above the foot again, of the nodes under it now. fn over(&mut self, i: usize, version: u64) { let under = i * FAN..self.leaves.len().min((i + 1) * FAN); let entries: Vec = under .clone() .map(|l| Entry { key: &self.records[l * LEAF].path, value: &self.records[l * LEAF].cid, tree: Some(&self.leaves[l].cid), }) .collect(); self.above[i] = Block { cid: self.cid(1, i, version), bytes: node(None, &entries), rev: State::rev( &self.records[under.start * LEAF..self.records.len().min(under.end * LEAF)], ), }; } /// Make the root again, of the nodes under it now. fn top(&mut self, version: u64) { let entries: Vec = (0..self.above.len()) .map(|a| Entry { key: &self.records[a * FAN * LEAF].path, value: &self.records[a * FAN * LEAF].cid, tree: Some(&self.above[a].cid), }) .collect(); self.root = Block { cid: self.cid(2, 0, version), bytes: node(None, &entries), rev: State::rev(&self.records), }; } /// The tree's nodes. pub fn nodes(&self) -> impl Iterator { self.leaves .iter() .chain(&self.above) .chain(std::iter::once(&self.root)) } /// Put another record in record `i`'s place, as a commit does: answers /// the CIDs of the blocks that takes out of the tree (the record's, and /// each node's from it to the root) and the nodes put in their place. /// The record is `records[i]` after. pub fn rewrite(&mut self, i: usize, version: u64) -> (Vec>, Vec) { let (l, a) = (i / LEAF, i / LEAF / FAN); let gone = vec![ self.records[i].cid.clone(), self.leaves[l].cid.clone(), self.above[a].cid.clone(), self.root.cid.clone(), ]; let op = i as u64 * self.accounts + self.account + 1; self.records[i] = record(self.seed, op, self.account, version); // A version of a node for each record under it and each time. let v = version * self.records.len() as u64 + i as u64 + 1; self.leaf(l, v); self.over(a, v); self.top(v); let made = vec![ self.leaves[l].clone(), self.above[a].clone(), self.root.clone(), ]; (gone, made) } } #[cfg(test)] mod tests { use super::*; /// The realistic commits are the sizes the README gives them, and the /// same every time. #[test] fn realistic_commits_are_as_described() { let n = 2000u64; let mut sums = [0usize; 4]; for op in 1..=n { let c = real(SEED, op, op % 40); assert_eq!(c.event, real(SEED, op, op % 40).event); sums[0] += c.blocks[0].1.len(); sums[1] += c.blocks[1].1.len(); sums[2] += c.blocks[2].1.len() + c.blocks[3].1.len(); sums[3] += c.event.len(); } let mean = sums.map(|s| s as u64 / n); assert!( (170..=200).contains(&mean[0]), "a commit block of {}", mean[0] ); assert!((270..=330).contains(&mean[1]), "a record of {}", mean[1]); assert!((1800..=2200).contains(&mean[2]), "two nodes of {}", mean[2]); assert!((2500..=3100).contains(&mean[3]), "an event of {}", mean[3]); } /// An account's state is its commits' records, in order of path, under /// a tree whose nodes are about 1 KB. #[test] fn a_state_holds_its_commits_records() { let s = State::new(SEED, 3, 40, 500); assert!(s.records.windows(2).all(|w| w[0].path < w[1].path)); assert_eq!( s.records[7].bytes, real(SEED, 7 * 40 + 3 + 1, 3).blocks[1].1 ); assert_eq!(s.records[7].path, path(SEED, 7 * 40 + 3 + 1, 3)); let nodes: Vec<&Block> = s.nodes().collect(); let mean = nodes.iter().map(|n| n.bytes.len()).sum::() / nodes.len(); assert!((800..=1200).contains(&mean), "nodes of {mean}"); } }