chadtmiller.com/monolith
An atproto PDS
0
0
//! A table's file (`pds_store::table`) taken apart and put together other
//! ways, to measure what the server's does not do: its blocks compressed,
//! its blocks of another size with each one's last key whole in the index
//! in a table of the version before, and a reader with a check of its
//! choice that holds its file open, or opens it for each block. What these
//! write, `pds_store::table::Table` reads, but for blocks compressed; what
//! the reader reads is any of them.
use crate::check::Check;
use pds_store::table::Version;
use sha2::{Digest, Sha256};
use std::collections::HashMap;
use std::fs::File;
use std::hint::black_box;
use std::os::unix::fs::FileExt;
use std::path::{Path, PathBuf};
use std::sync::{Arc, Mutex, PoisonError};
/// The bytes of a file's end that hold a table's footer, whichever its
/// version.
const TAIL: usize = 48;
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);
}
fn read_varint(bytes: &[u8], pos: &mut usize) -> u64 {
let mut n = 0u64;
for shift in (0..64).step_by(7) {
let b = bytes[*pos];
*pos += 1;
n |= u64::from(b & 0x7f) << shift;
if b & 0x80 == 0 {
break;
}
}
n
}
/// The entries of a block, each with where it begins and ends in it.
fn entries(block: &[u8]) -> impl Iterator<Item = (&[u8], &[u8], std::ops::Range<usize>)> {
let mut pos = 0;
std::iter::from_fn(move || {
(pos < block.len()).then(|| {
let start = pos;
let k = read_varint(block, &mut pos) as usize;
let key = &block[pos..pos + k];
pos += k;
let v = read_varint(block, &mut pos) as usize;
let value = &block[pos..pos + v];
pos += v;
(key, value, start..pos)
})
})
}
/// One data block's place: its key in the index (its last key, or a
/// shorter one after it and before the next block's first), its offset
/// and its length, check and all.
struct Place {
last: Vec<u8>,
offset: u64,
len: usize,
}
/// The check a table of `version` holds.
pub fn held(version: Version) -> Check {
match version {
Version::Sha256 => Check::Sha256,
Version::Xxh3 => Check::Xxh3,
}
}
/// What the footer of a table that ends as `tail` does holds: its version,
/// and four numbers: where its index is, the bytes of its index and of
/// its bloom filter, and its entries.
fn footer(tail: &[u8]) -> (Version, [u64; 4]) {
let version = Version::of(tail).expect("a table");
let numbers = &tail[tail.len() - version.footer() + 8..];
let n = |i: usize| u64::from_le_bytes(numbers[i * 8..i * 8 + 8].try_into().expect("8"));
(version, [0, 1, 2, 3].map(n))
}
/// A table's version, its index and its bloom filter, each with its
/// check, and its count of entries.
fn parts(table: &[u8]) -> (Version, &[u8], &[u8], u64) {
let (version, [index_at, index_len, filter_len, count]) = footer(table);
let (index_at, filter_at) = (index_at as usize, (index_at + index_len) as usize);
let filter = &table[filter_at..filter_at + filter_len as usize];
(version, &table[index_at..filter_at], filter, count)
}
/// A table's index: where each data block is.
fn places(index: &[u8]) -> Vec<Place> {
let index = &index[..index.len() - 8];
let mut out = Vec::new();
let mut pos = 0;
while pos < index.len() {
let k = read_varint(index, &mut pos) as usize;
let last = index[pos..pos + k].to_vec();
pos += k;
let offset = read_varint(index, &mut pos);
let len = read_varint(index, &mut pos) as usize;
out.push(Place { last, offset, len });
}
out
}
/// A table being put together again, of a version: its blocks as they are
/// given, each with that version's check over what is stored, and the
/// index of where they are.
struct Again {
version: Version,
out: Vec<u8>,
index: Vec<u8>,
}
impl Again {
fn new(version: Version) -> Again {
Again {
version,
out: Vec::new(),
index: Vec::new(),
}
}
fn block(&mut self, last: &[u8], stored: &[u8]) {
varint(&mut self.index, last.len() as u64);
self.index.extend_from_slice(last);
varint(&mut self.index, self.out.len() as u64);
varint(&mut self.index, stored.len() as u64 + 8);
self.out.extend_from_slice(stored);
self.out.extend_from_slice(&held(self.version).of(stored));
}
/// The file: the blocks, the index, `filter`, a bloom filter of its
/// version with its check, and the footer, with the `count` of entries
/// and, in a version whose footer has one, its check.
fn finish(mut self, filter: &[u8], count: u64) -> Vec<u8> {
let blocks = self.out.len() as u64;
let c = held(self.version).of(&self.index);
self.index.extend_from_slice(&c);
self.out.extend_from_slice(&self.index);
self.out.extend_from_slice(filter);
let mut footer = self.version.magic().to_vec();
for n in [blocks, self.index.len() as u64, filter.len() as u64, count] {
footer.extend_from_slice(&n.to_le_bytes());
}
if self.version.footer() > footer.len() {
let c = held(self.version).of(&footer);
footer.extend_from_slice(&c);
}
self.out.extend_from_slice(&footer);
self.out
}
}
/// The entries of each of a table's data blocks, in order.
fn blocks(table: &[u8]) -> impl Iterator<Item = (Vec<u8>, &[u8])> {
places(parts(table).1).into_iter().map(move |p| {
(
p.last,
&table[p.offset as usize..p.offset as usize + p.len - 8],
)
})
}
/// The same table, of the same version, with each data block's entries
/// put through `pack`.
pub fn packed(table: &[u8], mut pack: impl FnMut(&[u8]) -> Vec<u8>) -> Vec<u8> {
let (version, _, filter, count) = parts(table);
let mut again = Again::new(version);
for (last, block) in blocks(table) {
again.block(&last, &pack(block));
}
again.finish(filter, count)
}
/// The bloom filter a table of the version before has over the keys of
/// `table`, with its check, as `pds_store::table` made one: 10 bits an
/// entry, 64 at least, and 7 of them a key's, numbered by the first 16
/// bytes of SHA-256 of the key.
fn filter_before(table: &[u8], count: u64) -> Vec<u8> {
let mut filter = vec![0u8; 1 + (count.max(1) * 10).div_ceil(8).max(8) as usize];
filter[0] = 7;
let m = (filter.len() as u64 - 1) * 8;
for (_, block) in blocks(table) {
for (key, _, _) in entries(block) {
let d = Sha256::digest(key);
let a = u64::from_le_bytes(d[..8].try_into().expect("8"));
let b = u64::from_le_bytes(d[8..16].try_into().expect("8")) | 1;
for i in 0..7 {
let p = (a.wrapping_add(b.wrapping_mul(i)) % m) as usize;
filter[1 + p / 8] |= 1 << (p % 8);
}
}
}
let c = Check::Sha256.of(&filter);
filter.extend_from_slice(&c);
filter
}
/// The same entries in a table of the version before, its checks and its
/// bloom filter SHA-256's, in blocks of `size` bytes, ended as
/// `pds_store::table::TableWriter` ends its own, each block's last key
/// whole in the index: with a `size` of 16 KiB, the layout before.
pub fn reblocked(table: &[u8], size: usize) -> Vec<u8> {
let count = parts(table).3;
let mut again = Again::new(Version::Sha256);
let mut block: Vec<u8> = Vec::with_capacity(size * 2);
let mut last: &[u8] = &[];
for (_, old) in blocks(table) {
for (key, value, at) in entries(old) {
if !block.is_empty() && block.len() + key.len() + value.len() > size {
again.block(last, &block);
block.clear();
}
block.extend_from_slice(&old[at]);
last = key;
if block.len() >= size {
again.block(last, &block);
block.clear();
}
}
}
if !block.is_empty() {
again.block(last, &block);
}
again.finish(&filter_before(table, count), count)
}
/// A table read by this benchmark: its index held, no bloom filter, each
/// block read checked with the check of its choice, unpacked if it is
/// stored compressed, and searched. Its file is held open, or opened for
/// each block it reads. It keeps every block it has read, or none: with
/// none, every read is of a block from the file.
///
/// A file holds the checks of its version: XXH3-64, or SHA-256 in a table
/// of the version before. The reader's check is compared with the file's
/// where it is that one; another is computed over the same bytes and
/// compared with nothing: what it costs, not what it finds.
pub struct Reader {
path: PathBuf,
/// The file, if it is held open.
file: Option<File>,
places: Vec<Place>,
check: Check,
/// The check its file holds.
held: Check,
kept: Option<Mutex<HashMap<usize, Arc<[u8]>>>>,
}
/// What unpacks a table's blocks, if they are stored compressed.
pub type Unpack<'a, 'b> = &'a mut Option<zstd::bulk::Decompressor<'b>>;
impl Reader {
/// The table at `path`, read with `check`, or with the check its file
/// holds if it is given none.
pub fn open(path: &Path, check: Option<Check>, keep: bool) -> Reader {
let file = File::open(path).expect("a table");
let size = file.metadata().expect("a table").len();
let mut tail = [0u8; TAIL];
file.read_exact_at(&mut tail, size - TAIL as u64)
.expect("a footer");
let (version, [index_at, index_len, _, _]) = footer(&tail);
let held = held(version);
let mut index = vec![0u8; index_len as usize];
file.read_exact_at(&mut index, index_at).expect("an index");
let r = Reader {
path: path.to_path_buf(),
places: places(&index),
file: Some(file),
check: check.unwrap_or(held),
held,
kept: keep.then(Mutex::default),
};
let (body, c) = index.split_at(index.len() - 8);
r.checked(body, c);
r
}
/// The same reader with its file closed: opened for each block it reads.
pub fn opening_each(mut self) -> Reader {
self.file = None;
self
}
/// Compute the check of `bytes`, and see that it is `stored` if that
/// is the check the file holds.
fn checked(&self, bytes: &[u8], stored: &[u8]) {
let c = black_box(self.check.of(bytes));
assert!(self.check != self.held || c == stored, "a check");
}
/// Block `i`'s entries, read from the file.
fn read(&self, i: usize, unpack: Unpack) -> Vec<u8> {
let p = &self.places[i];
let mut stored = vec![0u8; p.len];
match &self.file {
Some(file) => file.read_exact_at(&mut stored, p.offset),
None => File::open(&self.path)
.expect("a table")
.read_exact_at(&mut stored, p.offset),
}
.expect("a block");
let (body, c) = stored.split_at(p.len - 8);
self.checked(body, c);
match unpack {
Some(z) => {
let mut plain = Vec::with_capacity(1 << 16);
z.decompress_to_buffer(body, &mut plain)
.expect("a block unpacked");
plain
}
None => {
stored.truncate(p.len - 8);
stored
}
}
}
/// Give `f` block `i`'s entries: those kept, or read now.
fn with<T>(&self, i: usize, unpack: Unpack, f: impl FnOnce(&[u8]) -> T) -> T {
let Some(kept) = &self.kept else {
return f(&self.read(i, unpack));
};
let held = kept
.lock()
.unwrap_or_else(PoisonError::into_inner)
.get(&i)
.cloned();
let block = held.unwrap_or_else(|| {
let block: Arc<[u8]> = self.read(i, unpack).into();
kept.lock()
.unwrap_or_else(PoisonError::into_inner)
.insert(i, block.clone());
block
});
f(&block)
}
/// The value of `key`, which the table holds.
pub fn get(&self, key: &[u8], unpack: Unpack) -> Vec<u8> {
let i = self.places.partition_point(|p| p.last.as_slice() < key);
self.with(i, unpack, |block| {
entries(block)
.find(|(k, _, _)| *k == key)
.map(|(_, v, _)| v.to_vec())
.expect("a key the table holds")
})
}
/// The first `n` entries from `from` on whose keys begin as it does.
pub fn list(&self, from: &[u8], n: usize) -> Vec<(Vec<u8>, Vec<u8>)> {
let mut out = Vec::with_capacity(n);
let mut i = self.places.partition_point(|p| p.last.as_slice() < from);
while out.len() < n && i < self.places.len() {
let ended = self.with(i, &mut None, |block| {
for (k, v, _) in entries(block).filter(|(k, _, _)| *k >= from) {
if k[0] != from[0] || out.len() == n {
return true;
}
out.push((k.to_vec(), v.to_vec()));
}
false
});
if ended {
break;
}
i += 1;
}
out
}
}