chadtmiller.com/monolith
An atproto PDS
0
0
//! The space repos' sections of an account's table, what the memtable
//! keeps of them, and how they are read: memtable, then table.
//!
//! Every key of these sections is its section's letter, the space's URI, a
//! zero byte, and the rest: a space repo's entries are together, in the
//! order its reads go in, and no URI's are among another's, as no URI
//! holds a zero byte. The rest is, of a record (`R`, `V`), its path; of an
//! operation (`O`), its commit's rev and its index in that commit, 4 bytes
//! big-endian; of a blob reference (`C`), the blob's CID as a string, a
//! zero byte, and the referencing record's path.
//!
//! The memtable (`SpaceMem`) keeps each record the log wrote with what its
//! `R` entry holds and where its frame is, or that it is deleted; each
//! commit with operations with where its frame is; and each blob reference
//! made or taken away. A `clearRecords`, an import or a drop makes a `Void`
//! of its space repo: the table's entries of it count for nothing from then
//! on, and what the memtable kept of it before is let go.
use super::{Disk, Rows, Want, frame_item, key, read_at};
use crate::space_repo::Op;
use pds_repo::data::cid_string;
use pds_store::Pos;
use pds_store::table::{BlockCache, Table};
use serde_json::Value as Json;
use sha2::{Digest, Sha256};
use std::collections::{BTreeMap, HashMap};
use std::fs::File;
use std::io;
use std::iter::Peekable;
use std::ops::Bound;
use std::sync::Arc;
/// The sections' letters: blob references, operations, records and their bytes.
pub(super) const REFS: u8 = b'C';
pub(super) const OPS: u8 = b'O';
pub(super) const RECORDS: u8 = b'R';
pub(super) const VALUES: u8 = b'V';
/// A key after every key of these sections, less its section's letter: a
/// URI begins `at://`.
const END: &[u8] = &[0xff];
/// A key of a space repo's, less its section's letter.
pub(crate) fn space_key(uri: &str, rest: &[u8]) -> Vec<u8> {
[uri.as_bytes(), &[0], rest].concat()
}
/// The first key after every one of a space repo's.
fn space_end(uri: &str) -> Vec<u8> {
[uri.as_bytes(), &[1]].concat()
}
/// A key's space URI and the rest.
fn split(k: &[u8]) -> Option<(&str, &[u8])> {
let i = k.iter().position(|b| *b == 0)?;
Some((std::str::from_utf8(&k[..i]).ok()?, &k[i + 1..]))
}
/// The first string after every one that begins with `prefix`.
pub(crate) fn after_prefix(prefix: &str) -> Vec<u8> {
let mut b = prefix.as_bytes().to_vec();
while let Some(l) = b.pop() {
if l < 0xff {
b.push(l + 1);
break;
}
}
b
}
fn varint(out: &mut Vec<u8>, mut n: usize) {
while n >= 0x80 {
out.push((n as u8) | 0x80);
n >>= 7;
}
out.push(n as u8);
}
fn sized(out: &mut Vec<u8>, b: &[u8]) {
varint(out, b.len());
out.extend_from_slice(b);
}
/// The bytes `sized` wrote at `at`, which it moves past them.
fn take<'a>(v: &'a [u8], at: &mut usize) -> Option<&'a [u8]> {
let mut n = 0usize;
for shift in (0..35).step_by(7) {
let b = *v.get(*at)?;
*at += 1;
n |= usize::from(b & 0x7f) << shift;
if b & 0x80 == 0 {
let got = v.get(*at..at.checked_add(n)?)?;
*at += n;
return Some(got);
}
}
None
}
fn text(b: &[u8]) -> Option<String> {
String::from_utf8(b.to_vec()).ok()
}
/// What a record's `R` entry holds: its CID, the rev of the commit or
/// import that last wrote it, and the CIDs of the blobs it references, each
/// once, in order.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Meta {
pub cid: Vec<u8>,
pub rev: String,
pub refs: Vec<String>,
}
impl Meta {
/// Its `R` value: the CID, the rev and each blob's CID, each after its length.
pub(super) fn encode(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(self.cid.len() + self.rev.len() + 2);
sized(&mut out, &self.cid);
sized(&mut out, self.rev.as_bytes());
for r in &self.refs {
sized(&mut out, r.as_bytes());
}
out
}
pub(super) fn decode(v: &[u8]) -> Option<Meta> {
let mut at = 0;
let cid = take(v, &mut at)?.to_vec();
let rev = text(take(v, &mut at)?)?;
let mut refs = Vec::new();
while at < v.len() {
refs.push(text(take(v, &mut at)?)?);
}
Some(Meta { cid, rev, refs })
}
}
/// A blob reference's `C` key, less the letter: its space, the blob's CID
/// as a string, and the referencing record's path.
pub(super) fn ref_key(uri: &str, cid: &str, path: &str) -> Vec<u8> {
space_key(uri, &[cid.as_bytes(), &[0], path.as_bytes()].concat())
}
/// An operation's `O` key, less the letter: its space, its rev and its index.
pub(super) fn op_key(uri: &str, rev: &str, index: usize) -> Vec<u8> {
let index = u32::try_from(index).unwrap_or(u32::MAX);
space_key(uri, &[rev.as_bytes(), &index.to_be_bytes()].concat())
}
/// An operation's `O` value: the CID after and the CID before, each after
/// its length, `0` for none, then the path.
pub(super) fn op_value(o: &Op) -> Vec<u8> {
let mut out = Vec::with_capacity(o.path.len() + 80);
sized(&mut out, o.cid.as_deref().unwrap_or_default());
sized(&mut out, o.prev.as_deref().unwrap_or_default());
out.extend_from_slice(o.path.as_bytes());
out
}
/// An operation, from the rest of its key and its value.
pub(super) fn read_op(rest: &[u8], v: &[u8]) -> Option<Op> {
let (rev, index) = rest.split_at(rest.len().checked_sub(4)?);
let mut at = 0;
let some = |b: &[u8]| (!b.is_empty()).then(|| b.to_vec());
let cid = some(take(v, &mut at)?);
let prev = some(take(v, &mut at)?);
Some(Op {
rev: text(rev)?,
index: u32::from_be_bytes(index.try_into().ok()?) as usize,
path: text(&v[at..])?,
cid,
prev,
})
}
fn name(parts: &[&str]) -> [u8; 32] {
let mut h = Sha256::new();
for p in parts {
h.update(p.as_bytes());
h.update([0]);
}
h.finalize().into()
}
/// The name a frame's index has a space record by: of its space, the rev
/// of the commit or import that wrote it, and its path.
pub(super) fn record_name(uri: &str, rev: &str, path: &str) -> [u8; 32] {
name(&[uri, rev, path])
}
/// The name a frame's index has a space commit's operations by.
pub(super) fn ops_name(uri: &str, rev: &str) -> [u8; 32] {
name(&[uri, rev])
}
/// A space commit's operations, from their list as its entry has it.
fn commit_ops(rev: &str, list: &[u8]) -> Result<Vec<Op>, String> {
let list: Vec<Json> =
serde_json::from_slice(list).map_err(|e| format!("a space commit's operations: {e}"))?;
crate::space_repo::ops_of(rev, &list)
}
// ---- The memtable's part ----------------------------------------------------------
/// A record the log wrote: what its `R` entry holds, and where its frame is.
#[derive(Clone, Debug)]
pub(crate) struct MemRecord {
pub meta: Meta,
pub pos: Pos,
}
/// The table's entries of a space repo that count for nothing since an
/// entry of the log of `generation`: every operation; every blob
/// reference, if `refs`; and every record but those whose path begins with
/// one of `keep`, or none if `keep` is none.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Void {
pub generation: u64,
pub keep: Option<Vec<String>>,
pub refs: bool,
}
/// What the log after the table changed of the account's space repos, each
/// map by its section's key less the letter.
#[derive(Default)]
pub(crate) struct SpaceMem {
/// Each record written, or none once deleted, and the generation of the
/// log that last changed it.
pub records: BTreeMap<Vec<u8>, (Option<MemRecord>, u64)>,
/// Each commit with operations, by its space and rev: where its frame
/// is, and how many it has.
pub commits: BTreeMap<Vec<u8>, (Pos, u32)>,
/// Each blob reference: the rev of the commit that wrote the referencing
/// record, or none once it is gone, and the generation that changed it.
pub refs: BTreeMap<Vec<u8>, (Option<String>, u64)>,
/// What of the table is void, by space: at most one for each generation
/// of the log, in their order.
pub voids: BTreeMap<String, Vec<Void>>,
/// The bytes all of it is counted as in the cache.
cost: u64,
}
/// About the bytes a record's entry takes: its key and its place in the
/// map, and of one written, its CID, rev and blob refs, each an allocation
/// of its own.
fn record_cost(k: &[u8], r: &Option<MemRecord>) -> u64 {
let held = r.as_ref().map_or(0, |r| {
160 + r.meta.cid.len()
+ r.meta.rev.len()
+ r.meta.refs.iter().map(|c| c.len() + 40).sum::<usize>()
});
(k.len() + 144 + held) as u64
}
fn commit_cost(k: &[u8]) -> u64 {
(k.len() + 96) as u64
}
fn ref_cost(k: &[u8]) -> u64 {
(k.len() + 112) as u64
}
const VOID_COST: u64 = 256;
/// The prefixes both lists keep: those of each that one of the other covers.
fn both(a: Vec<String>, b: &[String]) -> Vec<String> {
let mut out: Vec<String> = b
.iter()
.filter(|q| a.iter().any(|p| q.starts_with(p.as_str()) && *q != p))
.cloned()
.collect();
out.extend(
a.into_iter()
.filter(|p| b.iter().any(|q| p.starts_with(q.as_str()))),
);
out
}
/// The prefixes of the records' paths every one of `voids` keeps: none if
/// none of them voids records.
fn kept(voids: &[Void]) -> Option<Vec<String>> {
voids
.iter()
.filter_map(|v| v.keep.as_ref())
.fold(None, |all, k| {
Some(match all {
None => k.clone(),
Some(a) => both(a, k),
})
})
}
impl SpaceMem {
/// The bytes it is counted as in the cache.
pub fn cost(&self) -> u64 {
self.cost
}
/// A record of the space `uri` written at `path`, or deleted, by an
/// entry of the log of `generation`.
pub fn record(&mut self, uri: &str, path: &str, r: Option<MemRecord>, generation: u64) {
let k = space_key(uri, path.as_bytes());
self.cost += record_cost(&k, &r);
if let Some((k, (old, _))) = self.records.remove_entry(&k) {
self.cost -= record_cost(&k, &old);
}
self.records.insert(k, (r, generation));
}
/// A commit of the space `uri` at `rev`, of `n` operations, in the frame at `pos`.
pub fn commit(&mut self, uri: &str, rev: &str, pos: Pos, n: u32) {
let k = space_key(uri, rev.as_bytes());
let cost = commit_cost(&k);
if self.commits.insert(k, (pos, n)).is_none() {
self.cost += cost;
}
}
/// The reference of the record at `path` of the space `uri` to the blob
/// `cid`: made by a commit at `rev`, or with none, gone.
pub fn reference(
&mut self,
uri: &str,
cid: &str,
path: &str,
rev: Option<String>,
generation: u64,
) {
let k = ref_key(uri, cid, path);
let cost = ref_cost(&k);
if self.refs.insert(k, (rev, generation)).is_none() {
self.cost += cost;
}
}
/// Void the table's entries of the space `uri`, as `v` says, and let go
/// of what the memtable kept of them.
pub fn void(&mut self, uri: &str, v: Void) {
let (lo, hi) = (space_key(uri, b""), space_end(uri));
let within = |k: &&Vec<u8>| k.as_slice() < hi.as_slice();
let commits: Vec<Vec<u8>> = self
.commits
.range(lo.clone()..)
.map(|(k, _)| k)
.take_while(within)
.cloned()
.collect();
for k in commits {
self.commits.remove(&k);
self.cost -= commit_cost(&k);
}
if v.refs {
let refs: Vec<Vec<u8>> = self
.refs
.range(lo.clone()..)
.map(|(k, _)| k)
.take_while(within)
.cloned()
.collect();
for k in refs {
self.refs.remove(&k);
self.cost -= ref_cost(&k);
}
}
if let Some(keep) = &v.keep {
let stays = |k: &[u8]| keep.iter().any(|p| k[lo.len()..].starts_with(p.as_bytes()));
let records: Vec<Vec<u8>> = self
.records
.range(lo.clone()..)
.map(|(k, _)| k)
.take_while(within)
.filter(|k| !stays(k))
.cloned()
.collect();
for k in records {
if let Some((old, _)) = self.records.remove(&k) {
self.cost -= record_cost(&k, &old);
}
}
}
let list = self.voids.entry(uri.to_string()).or_default();
match list.last_mut() {
Some(last) if last.generation == v.generation => {
last.refs |= v.refs;
last.keep = match (last.keep.take(), v.keep) {
(Some(a), Some(b)) => Some(both(a, &b)),
(a, b) => a.or(b),
};
}
_ => {
list.push(v);
self.cost += VOID_COST;
}
}
}
/// Let go of what the log's generations before `generation` changed,
/// which a table of that generation holds.
pub(super) fn folded(&mut self, generation: u64) {
self.records.retain(|_, r| r.1 >= generation);
self.commits.retain(|_, c| c.0.generation >= generation);
self.refs.retain(|_, r| r.1 >= generation);
self.voids.retain(|_, list| {
list.retain(|v| v.generation >= generation);
!list.is_empty()
});
let records: u64 = self
.records
.iter()
.map(|(k, (r, _))| record_cost(k, r))
.sum();
let commits: u64 = self.commits.keys().map(|k| commit_cost(k)).sum();
let refs: u64 = self.refs.keys().map(|k| ref_cost(k)).sum();
let voids = self.voids.values().map(|l| l.len() as u64).sum::<u64>() * VOID_COST;
self.cost = records + commits + refs + voids;
}
/// Whether the table's entry at `k` of `section` is void; if it is,
/// the key its entries not void go on from, or with `reverse`, are before.
fn skip(&self, section: u8, k: &[u8], reverse: bool) -> Option<Vec<u8>> {
if self.voids.is_empty() {
return None;
}
let (uri, rest) = split(k)?;
let voids = self.voids.get(uri)?;
let all = || {
Some(if reverse {
space_key(uri, b"")
} else {
space_end(uri)
})
};
match section {
OPS => all(),
REFS if voids.iter().any(|v| v.refs) => all(),
REFS => None,
_ => {
let keep = kept(voids)?;
if keep.iter().any(|p| rest.starts_with(p.as_bytes())) {
return None;
}
let next = if reverse {
keep.iter()
.map(|p| after_prefix(p))
.filter(|e| e.as_slice() <= rest)
.max()
} else {
keep.iter()
.map(|p| p.as_bytes().to_vec())
.filter(|p| p.as_slice() > rest)
.min()
};
next.map(|p| space_key(uri, &p)).or_else(all)
}
}
}
}
// ---- Reading: memtable, then table ---------------------------------------------------
/// The table's entries of these sections, if it has one, read from its
/// file opened if given.
#[derive(Clone, Copy)]
pub(crate) enum Old<'a> {
None,
Table(&'a Table, Option<&'a File>),
}
/// What the memtable keeps of a section, in the order a scan reads it.
type MemRows<'a, M> = Peekable<Box<dyn Iterator<Item = (&'a Vec<u8>, &'a M)> + 'a>>;
/// What reads an item of the frame at a place, for a fold.
pub(super) type Items<'a> = dyn FnMut(Pos, Want) -> Result<Option<Vec<u8>>, String> + 'a;
/// What takes each entry of the table a fold makes, in order of key.
pub(super) type Put<'a> = dyn FnMut(&[u8], &[u8]) -> Result<(), String> + 'a;
impl<'a> Old<'a> {
fn get(&self, k: &[u8], cache: &BlockCache) -> Result<Option<Vec<u8>>, String> {
match self {
Old::None => Ok(None),
Old::Table(t, file) => {
#[cfg(test)]
tests::READS.with(|n| n.set(n.get() + 1));
t.get_in(k, *file, cache).map_err(|e| e.to_string())
}
}
}
/// Its entries from `from` on, or with `reverse`, before it, the last first.
fn iter(&self, from: &[u8], reverse: bool, cache: &'a BlockCache) -> Rows<'a, String> {
match *self {
Old::None => Box::new(std::iter::empty()),
Old::Table(t, file) => {
let it = if reverse {
t.iter_back(from, file, cache)
} else {
t.iter(from, file, cache)
};
Box::new(it.map(|r| {
#[cfg(test)]
tests::READS.with(|n| n.set(n.get() + 1));
r.map_err(|e| e.to_string())
}))
}
}
}
}
/// An entry as a scan meets it: what the memtable keeps of it, or the table's value.
pub(crate) enum Row<'a, M> {
Mem(&'a M),
Old(Vec<u8>),
}
/// The entries of a section between two keys, in order or the last first:
/// the memtable's, and the table's that the memtable neither has nor
/// voids, each read as it is reached. Each is given with its key less the
/// section's letter.
pub(crate) struct Scan<'a, M> {
view: View<'a>,
section: u8,
mem: MemRows<'a, M>,
rows: Peekable<Rows<'a, String>>,
lo: Vec<u8>,
hi: Vec<u8>,
reverse: bool,
}
impl<'a, M> Scan<'a, M> {
/// The table's entries within the bounds, on from `at`.
fn old(&self, at: &[u8]) -> Peekable<Rows<'a, String>> {
let section = self.section;
let rows = self
.view
.old
.iter(&key(section, at), self.reverse, self.view.cache);
let bound = if self.reverse {
self.lo.clone()
} else {
self.hi.clone()
};
let reverse = self.reverse;
let within = move |r: &Result<(Vec<u8>, Vec<u8>), String>| {
r.as_ref().map_or(true, |(k, _)| {
k.first() == Some(§ion)
&& if reverse {
k[1..] >= bound[..]
} else {
k[1..] < bound[..]
}
})
};
(Box::new(rows.take_while(within)) as Rows<'a, String>).peekable()
}
}
impl<'a, M> Iterator for Scan<'a, M> {
type Item = Result<(Vec<u8>, Row<'a, M>), String>;
fn next(&mut self) -> Option<Self::Item> {
loop {
// A table's entry the memtable voids: on from where it voids none.
if let Some(Ok((k, _))) = self.rows.peek()
&& let Some(to) = self.view.mem.skip(self.section, &k[1..], self.reverse)
{
self.rows = self.old(&to);
continue;
}
let mine = match (self.mem.peek(), self.rows.peek()) {
(None, None) => return None,
(_, Some(Err(_))) => false,
(Some(_), None) => true,
(None, Some(_)) => false,
(Some((m, _)), Some(Ok((k, _)))) => match m.as_slice().cmp(&k[1..]) {
std::cmp::Ordering::Equal => {
self.rows.next();
true
}
order => (order == std::cmp::Ordering::Greater) == self.reverse,
},
};
return Some(if mine {
let (k, m) = self.mem.next()?;
Ok((k.clone(), Row::Mem(m)))
} else {
self.rows
.next()?
.map(|(k, v)| (k[1..].to_vec(), Row::Old(v)))
});
}
}
}
/// An operation log's entries as a scan meets them: a commit of the log's,
/// its rev and where its frame is, or an operation of the table's.
pub(crate) enum Ops {
Commit(String, Pos),
Row(Op),
}
/// The space repos' sections as they are now: what the memtable keeps,
/// over the table's entries.
#[derive(Clone, Copy)]
pub(crate) struct View<'a> {
pub mem: &'a SpaceMem,
pub old: Old<'a>,
pub cache: &'a BlockCache,
}
impl<'a> View<'a> {
/// The entries of `section` from `lo` and before `hi`, `map` the
/// memtable's of them, the last first if `reverse`.
fn scan<M>(
self,
map: &'a BTreeMap<Vec<u8>, M>,
section: u8,
lo: Vec<u8>,
hi: Vec<u8>,
reverse: bool,
) -> Scan<'a, M> {
let within = (Bound::Included(&lo[..]), Bound::Excluded(&hi[..]));
let mem: Box<dyn Iterator<Item = (&'a Vec<u8>, &'a M)> + 'a> = if lo >= hi {
Box::new(std::iter::empty())
} else if reverse {
Box::new(map.range::<[u8], _>(within).rev())
} else {
Box::new(map.range::<[u8], _>(within))
};
let mut scan = Scan {
view: self,
section,
mem: mem.peekable(),
rows: (Box::new(std::iter::empty()) as Rows<'a, String>).peekable(),
lo,
hi,
reverse,
};
if scan.lo < scan.hi {
scan.rows = scan.old(if reverse { &scan.hi } else { &scan.lo });
}
scan
}
/// Every entry of `section`, of every space repo, in order of key.
pub(super) fn all<M>(self, map: &'a BTreeMap<Vec<u8>, M>, section: u8) -> Scan<'a, M> {
self.scan(map, section, Vec::new(), END.to_vec(), false)
}
/// The record at `path` of the space `uri`: what its `R` entry holds,
/// and where its frame is, if its bytes are in the log.
pub fn record(self, uri: &str, path: &str) -> Result<Option<(Meta, Option<Pos>)>, String> {
let k = space_key(uri, path.as_bytes());
match self.mem.records.get(&k) {
Some((r, _)) => Ok(r.as_ref().map(|r| (r.meta.clone(), Some(r.pos)))),
None if self.mem.skip(RECORDS, &k, false).is_some() => Ok(None),
None => match self.old.get(&key(RECORDS, &k), self.cache)? {
None => Ok(None),
Some(v) => Meta::decode(&v)
.map(|m| Some((m, None)))
.ok_or_else(|| "a space record's entry that does not parse".into()),
},
}
}
/// The records of the space `uri` whose paths are within the bounds, in
/// order of path or the last first: each one's path, what its `R` entry
/// holds, and where its frame is, if its bytes are in the log.
pub fn records(
self,
uri: &str,
lo: Bound<&[u8]>,
hi: Bound<&[u8]>,
reverse: bool,
) -> impl Iterator<Item = Result<(String, Meta, Option<Pos>), String>> + use<'a> {
let lo = match lo {
Bound::Unbounded => space_key(uri, b""),
Bound::Included(x) => space_key(uri, x),
Bound::Excluded(x) => space_key(uri, &[x, &[0]].concat()),
};
let hi = match hi {
Bound::Unbounded => space_end(uri),
Bound::Excluded(x) => space_key(uri, x),
Bound::Included(x) => space_key(uri, &[x, &[0]].concat()),
};
let at = uri.len() + 1;
self.scan(&self.mem.records, RECORDS, lo, hi, reverse)
.filter_map(move |r| {
let (k, row) = match r {
Ok(x) => x,
Err(e) => return Some(Err(e)),
};
let found = match row {
Row::Mem((None, _)) => return None,
Row::Mem((Some(r), _)) => Some((r.meta.clone(), Some(r.pos))),
Row::Old(v) => Meta::decode(&v).map(|m| (m, None)),
};
Some(match (text(&k[at..]), found) {
(Some(path), Some((meta, pos))) => Ok((path, meta, pos)),
_ => Err("a space record's entry that does not parse".into()),
})
})
}
/// The blob references of the records of the space `uri`, from the
/// blob `from` on, in order of the blob's CID and then the record's
/// path: each one's CID, path, and the rev that wrote the record.
pub fn refs(
self,
uri: &str,
from: &[u8],
) -> impl Iterator<Item = Result<(String, String, String), String>> + use<'a> {
let at = uri.len() + 1;
self.scan(
&self.mem.refs,
REFS,
space_key(uri, from),
space_end(uri),
false,
)
.filter_map(move |r| {
let (k, row) = match r {
Ok(x) => x,
Err(e) => return Some(Err(e)),
};
let rev = match row {
Row::Mem((None, _)) => return None,
Row::Mem((Some(rev), _)) => Some(rev.clone()),
Row::Old(v) => text(&v),
};
let parts =
split(&k[at..]).and_then(|(cid, path)| Some((cid.to_string(), text(path)?)));
Some(match (parts, rev) {
(Some((cid, path)), Some(rev)) => Ok((cid, path, rev)),
_ => Err("a blob reference's entry that does not parse".into()),
})
})
}
/// Whether a record of the space `uri` references the blob `cid`.
pub fn refers(self, uri: &str, cid: &str) -> Result<bool, String> {
let from = [cid.as_bytes(), &[0]].concat();
match self.refs(uri, &from).next() {
Some(r) => Ok(r?.0 == cid),
None => Ok(false),
}
}
/// The operation log of the space `uri` from `from` on, the rest of an
/// `O` key: each operation of the table's, and each commit of the log's.
pub fn ops(
self,
uri: &str,
from: &[u8],
) -> impl Iterator<Item = Result<Ops, String>> + use<'a> {
let at = uri.len() + 1;
self.scan(
&self.mem.commits,
OPS,
space_key(uri, from),
space_end(uri),
false,
)
.map(move |r| {
let (k, row) = r?;
let found = match row {
Row::Mem((pos, _)) => text(&k[at..]).map(|rev| Ops::Commit(rev, *pos)),
Row::Old(v) => read_op(&k[at..], &v).map(Ops::Row),
};
found.ok_or_else(|| "an operation's entry that does not parse".into())
})
}
}
// ---- The store's reads -----------------------------------------------------------------
impl Disk {
/// Its space repos' sections as they are now.
pub fn spaces<'a>(&'a self, cache: &'a BlockCache) -> View<'a> {
View {
mem: &self.mem.spaces,
old: match &self.table {
Some(t) => Old::Table(t, None),
None => Old::None,
},
cache,
}
}
/// The bytes of the record at `path` of the space `uri`, which `meta`
/// is of: from its frame at `pos`, or with none, from the table.
pub fn space_bytes(
&self,
cache: &BlockCache,
uri: &str,
path: &str,
meta: &Meta,
pos: Option<Pos>,
) -> Arc<[u8]> {
let found = match pos {
Some(pos) => {
let name = record_name(uri, &meta.rev, path);
self.log_item(cache, pos, Want::SpaceRecord(&name, &meta.cid))
}
None => self
.table_get(cache, &key(VALUES, &space_key(uri, path.as_bytes())))
.map(Arc::from),
};
found.unwrap_or_else(|| self.fail(format!("space record {uri} {path} is not held")))
}
/// The operations of the commit at `rev` of the space `uri`, in the frame at `pos`.
pub fn space_commit(&self, cache: &BlockCache, uri: &str, rev: &str, pos: Pos) -> Vec<Op> {
let name = ops_name(uri, rev);
let list = self
.log_item(cache, pos, Want::SpaceOps(&name))
.unwrap_or_else(|| self.fail(format!("space commit {uri} {rev} is not held")));
commit_ops(rev, &list).unwrap_or_else(|e| self.fail(e))
}
/// What reads the records of the space `uri` while they change: its
/// files open, and what the memtable keeps of them now.
pub fn space_snapshot(&self, uri: &str) -> io::Result<SpaceSnapshot> {
let table = match &self.table {
Some(t) => Some((t.clone(), t.file()?)),
None => None,
};
let m = &self.mem.spaces;
let mem = SpaceMem {
records: m
.records
.range(space_key(uri, b"")..space_end(uri))
.map(|(k, r)| (k.clone(), r.clone()))
.collect(),
voids: m
.voids
.get_key_value(uri)
.map(|(k, v)| (k.clone(), v.clone()))
.into_iter()
.collect(),
..Default::default()
};
let mut logs = HashMap::new();
for (r, _) in mem.records.values() {
if let Some(r) = r
&& let std::collections::hash_map::Entry::Vacant(v) = logs.entry(r.pos.generation)
{
v.insert((
File::open(self.layout.log(r.pos.generation))?,
self.number(r.pos.generation),
));
}
}
Ok(SpaceSnapshot {
uri: uri.to_string(),
table,
mem,
logs,
})
}
}
/// A space repo's records as they were when taken, read as they are sent.
pub(crate) struct SpaceSnapshot {
uri: String,
table: Option<(Arc<Table>, Arc<File>)>,
/// What the memtable kept of its records, and voided of the table's.
mem: SpaceMem,
/// Each log it reads, by generation, and the number the cache holds it by.
logs: HashMap<u64, (File, u64)>,
}
impl SpaceSnapshot {
/// Give `emit` each record's path and bytes, in order of path, each
/// read as it is reached; stop when `emit` says to.
pub fn run(
self,
cache: &BlockCache,
mut emit: impl FnMut(&[u8], &[u8]) -> bool,
) -> io::Result<()> {
let invalid = |e: String| io::Error::new(io::ErrorKind::InvalidData, e);
let view = View {
mem: &self.mem,
old: match &self.table {
Some((t, f)) => Old::Table(t, Some(&**f)),
None => Old::None,
},
cache,
};
let at = self.uri.len() + 1;
let (lo, hi) = (space_key(&self.uri, b""), space_end(&self.uri));
for r in view.scan(&self.mem.records, VALUES, lo, hi, false) {
let (k, row) = r.map_err(invalid)?;
let path = &k[at..];
let bytes = match row {
Row::Mem((None, _)) => continue,
Row::Old(v) => v,
Row::Mem((Some(r), _)) => {
let (file, number) = self
.logs
.get(&r.pos.generation)
.ok_or_else(|| io::Error::other("a log not open"))?;
let read = |offset: u64, len: usize| read_at(file, offset, len);
let path = std::str::from_utf8(path).map_err(|e| invalid(e.to_string()))?;
let name = record_name(&self.uri, &r.meta.rev, path);
let want = Want::SpaceRecord(&name, &r.meta.cid);
frame_item(cache, *number, r.pos, &read, want)
.map_err(invalid)?
.ok_or_else(|| invalid("a space record missing from its frame".into()))?
}
};
if !emit(path, &bytes) {
return Ok(());
}
}
Ok(())
}
}
// ---- Folding -----------------------------------------------------------------------------
/// Give `out` the entries of the space repos' section `section` of the
/// table a fold makes, in order of key: the table's before, but those
/// `mem` voids or changed, and `mem`'s, their bytes read by `item` from the
/// frames they are in.
pub(super) fn fold(
section: u8,
view: View<'_>,
item: &mut Items<'_>,
out: &mut Put<'_>,
) -> Result<(), String> {
let mem = view.mem;
let parts = |k: &[u8]| {
split(k)
.and_then(|(uri, rest)| Some((uri.to_string(), text(rest)?)))
.ok_or_else(|| "a key of the memtable's that does not parse".to_string())
};
match section {
REFS => {
for r in view.all(&mem.refs, REFS) {
match r? {
(k, Row::Mem((Some(rev), _))) => out(&key(REFS, &k), rev.as_bytes())?,
(_, Row::Mem((None, _))) => {}
(k, Row::Old(v)) => out(&key(REFS, &k), &v)?,
}
}
}
OPS => {
for r in view.all(&mem.commits, OPS) {
match r? {
(k, Row::Old(v)) => out(&key(OPS, &k), &v)?,
(k, Row::Mem((pos, _))) => {
let (uri, rev) = parts(&k)?;
let list = item(*pos, Want::SpaceOps(&ops_name(&uri, &rev)))?.ok_or_else(
|| format!("space commit {uri} {rev} missing from its frame"),
)?;
for o in commit_ops(&rev, &list)? {
out(&key(OPS, &op_key(&uri, &rev, o.index)), &op_value(&o))?;
}
}
}
}
}
_ => {
for r in view.all(&mem.records, section) {
match r? {
(_, Row::Mem((None, _))) => {}
(k, Row::Old(v)) => out(&key(section, &k), &v)?,
(k, Row::Mem((Some(r), _))) if section == RECORDS => {
out(&key(RECORDS, &k), &r.meta.encode())?
}
(k, Row::Mem((Some(r), _))) => {
let (uri, path) = parts(&k)?;
let name = record_name(&uri, &r.meta.rev, &path);
let bytes = item(r.pos, Want::SpaceRecord(&name, &r.meta.cid))?
.ok_or_else(|| {
format!(
"space record {uri} {path} ({}) missing from its frame",
cid_string(&r.meta.cid)
)
})?;
out(&key(VALUES, &k), &bytes)?;
}
}
}
}
}
Ok(())
}
/// How many entries of the sections `mem` holds, for a table's bloom filter.
pub(super) fn entries(mem: &SpaceMem) -> u64 {
let ops: u64 = mem.commits.values().map(|(_, n)| u64::from(*n)).sum();
(mem.records.len() * 2 + mem.refs.len()) as u64 + ops
}
#[cfg(test)]
pub(crate) mod tests {
use super::*;
thread_local! {
/// The table's entries of these sections this thread read: each
/// one looked up by key, and each one a scan reached.
pub(crate) static READS: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
}
fn void(generation: u64, keep: Option<&[&str]>, refs: bool) -> Void {
Void {
generation,
keep: keep.map(|k| k.iter().map(|p| p.to_string()).collect()),
refs,
}
}
fn rows(view: View<'_>, uri: &str, reverse: bool) -> Vec<String> {
view.records(uri, Bound::Unbounded, Bound::Unbounded, reverse)
.map(|r| r.unwrap().0)
.collect()
}
/// A void keeps what every void of its space keeps, of the table's
/// entries and of the memtable's before it, in either order of reading,
/// and no other space's entries are voided; once a table holds a
/// generation, its voids and entries are let go.
#[test]
fn voids_keep_only_what_each_keeps() {
let (a, b) = ("at://did:plc:a/space/x.y/k", "at://did:plc:a/space/x.y/k2");
let meta = Meta {
cid: vec![1; 36],
rev: "3l3s4fxs7ft22".into(),
refs: vec![],
};
let mut table = BTreeMap::new();
for (uri, path) in [
(a, "a.b/1"),
(a, "keep.it/1"),
(a, "keep.it/2"),
(a, "z.z/1"),
(b, "a.b/1"),
] {
table.insert(
key(RECORDS, &space_key(uri, path.as_bytes())),
meta.encode(),
);
}
let dir = crate::testing::scratch("spaces-voids");
std::fs::create_dir_all(&dir).unwrap();
let file = dir.join("table");
let mut w =
pds_store::table::TableWriter::new(File::create(&file).unwrap(), table.len() as u64);
for (k, v) in &table {
w.add(k, v).unwrap();
}
w.finish().unwrap();
let cache = BlockCache::new(1 << 20);
let table = Table::open(&file, &cache).unwrap();
let pos = Pos {
generation: 3,
offset: 0,
len: 0,
};
let mut mem = SpaceMem::default();
let put = |mem: &mut SpaceMem, path: &str, g: u64| {
let r = MemRecord {
meta: meta.clone(),
pos: Pos {
generation: g,
..pos
},
};
mem.record(a, path, Some(r), g);
};
put(&mut mem, "a.b/2", 3);
put(&mut mem, "keep.it/3", 3);
mem.record(a, "keep.it/1", None, 3);
let view = |mem: &'_ SpaceMem| -> Vec<String> {
let v = View {
mem,
old: Old::Table(&table, None),
cache: &cache,
};
let all = rows(v, a, false);
let mut back = rows(v, a, true);
back.reverse();
assert_eq!(all, back);
for p in [
"a.b/1",
"a.b/2",
"keep.it/1",
"keep.it/2",
"keep.it/3",
"z.z/1",
] {
assert_eq!(
v.record(a, p).unwrap().is_some(),
all.iter().any(|x| x == p),
"{p}"
);
}
assert_eq!(rows(v, b, false), ["a.b/1"]);
all
};
assert_eq!(
view(&mem),
["a.b/1", "a.b/2", "keep.it/2", "keep.it/3", "z.z/1"]
);
// Operations alone are void: the records stay.
mem.void(a, void(3, None, false));
assert_eq!(view(&mem).len(), 5);
mem.void(a, void(3, Some(&["keep.it/"]), true));
assert_eq!(view(&mem), ["keep.it/2", "keep.it/3"]);
put(&mut mem, "a.b/1", 4);
assert_eq!(view(&mem), ["a.b/1", "keep.it/2", "keep.it/3"]);
// A later void that keeps nothing voids what the first kept.
mem.void(a, void(4, Some(&[]), true));
assert!(view(&mem).is_empty());
put(&mut mem, "z.z/9", 4);
assert_eq!(view(&mem), ["z.z/9"]);
// A table of generation 4 holds what the logs before it left: what
// generation 4 voided of it is void still.
mem.folded(4);
assert_eq!(mem.voids[a], [void(4, Some(&[]), true)]);
assert_eq!(view(&mem), ["z.z/9"]);
mem.folded(5);
assert!(mem.voids.is_empty() && mem.records.is_empty());
assert_eq!(mem.cost(), 0);
assert_eq!(view(&mem), ["a.b/1", "keep.it/1", "keep.it/2", "z.z/1"]);
let _ = std::fs::remove_dir_all(&dir);
}
/// What an entry's value holds is read back as it was written.
#[test]
fn values_round_trip() {
for refs in [vec![], vec!["bafkrei".to_string(), "x".repeat(300)]] {
let m = Meta {
cid: vec![7; 36],
rev: "3l3s4fxs7ft22".into(),
refs,
};
assert_eq!(Meta::decode(&m.encode()), Some(m));
}
let uri = "at://did:plc:a/space/x.y/k";
for (cid, prev) in [(None, Some(vec![2; 36])), (Some(vec![1; 36]), None)] {
let o = Op {
rev: "3l3s4fxs7ft22".into(),
index: 258,
path: "a.b.c/k".into(),
cid,
prev,
};
let k = op_key(uri, &o.rev, o.index);
assert_eq!(read_op(&k[uri.len() + 1..], &op_value(&o)), Some(o));
}
assert_eq!(after_prefix("a.b/"), b"a.b0");
}
}