chadtmiller.com/monolith
An atproto PDS
0
0
//! 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<u8> {
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<u8>, Vec<u8>)>,
pub event: Vec<u8>,
}
/// 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<Vec<u8>> {
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<Vec<&'static str>> =
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<u8> {
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<u8>, 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<u8>, s: &str) {
head(out, 3, s.len() as u64);
out.extend_from_slice(s.as_bytes());
}
fn blob(out: &mut Vec<u8>, 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<u8>, 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<u8>, 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<u8>,
pub bytes: Vec<u8>,
}
/// 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<u8> {
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<u8> {
let n = 10 + r.below(5) as usize;
let mut times: Vec<u64> = (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<String> = times
.iter()
.map(|back| format!("{COLLECTION}/{}", tid(at - back, clock)))
.collect();
let cids: Vec<(Vec<u8>, Option<Vec<u8>>)> = (0..n)
.map(|_| (cid(r), (r.below(trees) == 0).then(|| cid(r))))
.collect();
let mut entries: Vec<Entry> = 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<u8> {
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<u8> {
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<u8>,
pub bytes: Vec<u8>,
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<Record>,
leaves: Vec<Block>,
above: Vec<Block>,
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<Record> = (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<u8> {
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<Entry> = 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<Entry> = 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<Entry> = (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<Item = &Block> {
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<u8>>, Vec<Block>) {
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::<usize>() / nodes.len();
assert!((800..=1200).contains(&mean), "nodes of {mean}");
}
}