//! 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, 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)> { 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, 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 { 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, index: Vec, } 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 { 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, &[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) -> Vec { 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 { 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 { let count = parts(table).3; let mut again = Again::new(Version::Sha256); let mut block: Vec = 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, places: Vec, check: Check, /// The check its file holds. held: Check, kept: Option>>>, } /// What unpacks a table's blocks, if they are stored compressed. pub type Unpack<'a, 'b> = &'a mut Option>; 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, 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 { 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(&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 { 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, Vec)> { 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 } }