~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
378 lines · 13.2 KB Raw History
//! 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
    }
}