~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
487 lines · 19.4 KB Raw History
//! What the same accounts take on disk, each way of keeping them: their
//! commits' logs, before any compaction, with the server's frames and with
//! binary ones; what they hold after (`stores`) as tables, as tables with
//! each data block compressed, as SQLite and as RocksDB; and SQLite and
//! RocksDB once every record has been rewritten three times, with what
//! RocksDB wrote to get there. And what zstd costs a table: its speed,
//! and a read of a record through blocks that must be decompressed.

use crate::data::{self, SEED, State};
use crate::fj;
use crate::frame::Encoding;
use crate::rocks::{self, Pack};
use crate::stores::{self, block_bytes, block_value, key, path_cid};
use crate::tables::{Reader, Unpack, packed};
use crate::util::{Rng, at, cores, dir_bytes, mib, par, scratch, us};
use std::fs::File;
use std::io::Write;
use std::path::Path;
use std::time::{Duration, Instant};

/// The level the blocks are compressed at, the most bytes of a dictionary,
/// and which blocks it is trained on: each eighth.
const LEVEL: i32 = 3;
const DICTIONARY: usize = 64 << 10;
const SAMPLE: usize = 8;

/// The times every record is rewritten, and the records read through each
/// kind of table.
const REWRITES: u64 = 3;
const READS: usize = 20_000;

/// How blocks are stored: as they are, compressed, or compressed with a
/// dictionary.
struct Kind<'a> {
    name: &'a str,
    dir: &'a str,
    dictionary: Option<&'a [u8]>,
}

impl Kind<'_> {
    fn packer(&self) -> zstd::bulk::Compressor<'_> {
        match self.dictionary {
            Some(d) => zstd::bulk::Compressor::with_dictionary(LEVEL, d),
            None => zstd::bulk::Compressor::new(LEVEL),
        }
        .expect("a compressor")
    }

    fn unpacker(&self) -> zstd::bulk::Decompressor<'_> {
        match self.dictionary {
            Some(d) => zstd::bulk::Decompressor::with_dictionary(d),
            None => zstd::bulk::Decompressor::new(),
        }
        .expect("a decompressor")
    }
}

/// The median time of a record read by its path, through the tables under
/// `dir/<kind>`: two keys, so two blocks read.
fn read_records(
    dir: &Path,
    kind: &str,
    accounts: usize,
    records: usize,
    unpack: Unpack,
) -> Duration {
    crate::util::read_through(&dir.join(kind));
    let readers: Vec<Reader> = (0..accounts)
        .map(|a| Reader::open(&dir.join(format!("{kind}/{a}.table")), None, false))
        .collect();
    let mut r = Rng::of(&[SEED, 11]);
    let mut times: Vec<Duration> = (0..READS)
        .map(|_| {
            let (a, i) = (r.below(accounts as u64), r.below(records as u64));
            let path = data::path(SEED, i * accounts as u64 + a + 1, a);
            let t = &readers[a as usize];
            let started = Instant::now();
            let cid = t.get(&key(b'P', path.as_bytes()), unpack);
            let block = t.get(&key(b'B', path_cid(&cid)), unpack);
            std::hint::black_box(block_bytes(&block).len());
            started.elapsed()
        })
        .collect();
    times.sort();
    at(&times, 50)
}

/// The accounts' commits, one after another, as logs: the bytes of the
/// server's frames, and of binary ones.
fn logs(dir: &Path, accounts: usize, records: usize) -> (u64, u64) {
    for d in ["logs", "logs-binary"] {
        std::fs::create_dir_all(dir.join(d)).expect("a directory");
    }
    par(accounts, cores(), |a| {
        let create = |d: &str| {
            std::io::BufWriter::new(File::create(dir.join(format!("{d}/{a}.log"))).expect("a log"))
        };
        let (mut json, mut binary) = (create("logs"), create("logs-binary"));
        let mut gone: Vec<Vec<u8>> = Vec::new();
        for i in 0..records {
            let c = data::real(SEED, (i * accounts + a + 1) as u64, a as u64);
            json.write_all(&Encoding::Holes.frame(&c, &gone))
                .expect("an append");
            binary
                .write_all(&Encoding::Binary.frame(&c, &gone))
                .expect("an append");
            gone = data::nodes(&c);
        }
        json.flush().expect("a log");
        binary.flush().expect("a log");
    });
    let sizes = (
        dir_bytes(&dir.join("logs")),
        dir_bytes(&dir.join("logs-binary")),
    );
    for d in ["logs", "logs-binary"] {
        let _ = std::fs::remove_dir_all(dir.join(d));
    }
    sizes
}

/// Rewrite every record of the databases `REWRITES` times, each a
/// transaction as a commit's: the bytes of those for each account and of
/// the one for all, as that leaves them and then vacuumed.
fn rewritten(dir: &Path, accounts: usize, records: usize) -> [(u64, u64); 2] {
    let all = |db: &rusqlite::Connection, a: usize| {
        let mut s = State::new(SEED, a as u64, accounts as u64, records);
        for version in 1..=REWRITES {
            for i in 0..records {
                stores::rewrite(db, a, &mut s, i, version);
            }
        }
    };
    let each = |vacuum: bool| {
        par(accounts, cores().saturating_sub(1), |a| {
            let db = stores::open_db(&stores::dbs_path(dir, a), None);
            if vacuum {
                db.execute_batch("VACUUM").expect("a vacuum");
            } else {
                all(&db, a);
            }
            stores::close_db(db);
        });
        dir_bytes(&dir.join("dbs"))
    };
    let one = |vacuum: bool| {
        let db = stores::open_db(&stores::db_path(dir), None);
        if vacuum {
            db.execute_batch("VACUUM").expect("a vacuum");
        } else {
            (0..accounts).for_each(|a| all(&db, a));
        }
        stores::close_db(db);
        dir_bytes(&dir.join("db"))
    };
    std::thread::scope(|s| {
        let one = s.spawn(|| (one(false), one(true)));
        let each = (each(false), each(true));
        [each, one.join().expect("the one database rewritten")]
    })
}

/// The databases for each account, as `rewritten` left them, copied into
/// ones whose blocks are in a table with a rowid and an index on the CID:
/// their bytes. The write part's table of blocks is `WITHOUT ROWID`, which
/// keeps no more than about 1 KB of a row in its page: a tree node over
/// that takes a page more of its own.
fn with_rowid(dir: &Path, accounts: usize) -> u64 {
    std::fs::create_dir_all(dir.join("dbs-rowid")).expect("a directory");
    par(accounts, cores(), |a| {
        let db = stores::open_db(&stores::dbs_path(dir, a), None);
        let copy = dir.join(format!("dbs-rowid/{a}.sqlite"));
        db.execute("ATTACH ?1 AS copy", [copy.to_str().expect("a path")])
            .expect("a database");
        db.execute_batch(
            "PRAGMA copy.synchronous=OFF;
             BEGIN;
             CREATE TABLE copy.block(account INTEGER, cid BLOB, rev TEXT, bytes BLOB);
             CREATE TABLE copy.record(account INTEGER, path TEXT, cid BLOB, rev TEXT, PRIMARY KEY(account, path)) WITHOUT ROWID;
             INSERT INTO copy.block SELECT * FROM block;
             INSERT INTO copy.record SELECT * FROM record;
             CREATE UNIQUE INDEX copy.block_cid ON block(account, cid);
             COMMIT;",
        )
        .expect("a copy");
    });
    dir_bytes(&dir.join("dbs-rowid"))
}

/// The ways RocksDB's blocks are compressed that its size is taken in.
const PACKS: [Pack; 3] = [Pack::Snappy, Pack::None, Pack::Zstd];

/// What one RocksDB for all takes and writes, one way of compressing its
/// blocks.
struct Rocks {
    pack: Pack,
    /// Its bytes on disk once loaded, once every record is rewritten, and
    /// once it is compacted whole.
    disk: [u64; 3],
    /// The bytes it was given and wrote (`Setup::written`), up to the
    /// rewrites' end and up to the whole compaction's.
    written: [[u64; 4]; 2],
}

/// One RocksDB for all for each of `PACKS`, and one fjall database for
/// all for each of `fj::PACKS`: loaded as the databases are and left to
/// settle; every record rewritten `REWRITES` times, each a batch as a
/// commit's (the record's block and each node's from it to the root
/// deleted, new ones put, the path's value replaced), the accounts' at
/// once, and left to settle; then compacted whole (`CompactRange` over
/// every key of each family, `major_compact` of each keyspace). All
/// written through its log, unsynced. For fjall, its bytes on disk at
/// each of the three.
fn trees(dir: &Path, accounts: usize, records: usize) -> (Vec<Rocks>, Vec<(fj::Pack, [u64; 3])>) {
    let disk = || PACKS.map(|p| dir_bytes(&stores::rocks_path(dir, p)));
    let other = || fj::PACKS.map(|p| fj::disk(&stores::fjall_path(dir, p)));
    let setups = stores::build_trees(dir, accounts, records, &PACKS, &fj::PACKS);
    let open = || -> Vec<rocksdb::DB> {
        let paths = PACKS.iter().map(|p| stores::rocks_path(dir, *p));
        setups.iter().zip(paths).map(|(s, p)| s.open(&p)).collect()
    };
    let open_other = || -> Vec<fj::Store> {
        let open =
            |p: &fj::Pack| fj::Store::open(&stores::fjall_path(dir, *p), fj::CACHE, *p, false);
        fj::PACKS.iter().map(open).collect()
    };
    let (loaded, other_loaded) = (disk(), other());

    let (dbs, fjalls) = (open(), open_other());
    par(accounts, cores(), |a| {
        let mut s = State::new(SEED, a as u64, accounts as u64, records);
        for version in 1..=REWRITES {
            for i in 0..records {
                let (gone, made) = s.rewrite(i, version);
                let r = &s.records[i];
                for db in &dbs {
                    let block = rocks::family(db, rocks::BLOCK);
                    let mut batch = rocksdb::WriteBatch::default();
                    for cid in &gone {
                        batch.delete_cf(block, rocks::key(a, cid));
                    }
                    batch.put_cf(block, rocks::key(a, &r.cid), block_value(&r.rev, &r.bytes));
                    batch.put_cf(
                        rocks::family(db, rocks::RECORD),
                        rocks::key(a, r.path.as_bytes()),
                        rocks::record_value(&r.cid, &r.rev),
                    );
                    for n in &made {
                        batch.put_cf(block, rocks::key(a, &n.cid), block_value(&n.rev, &n.bytes));
                    }
                    db.write(batch).expect("a commit");
                }
                for store in &fjalls {
                    let mut batch = store.db.batch();
                    for cid in &gone {
                        batch.remove(&store.block, rocks::key(a, cid));
                    }
                    batch.insert(
                        &store.block,
                        rocks::key(a, &r.cid),
                        block_value(&r.rev, &r.bytes),
                    );
                    batch.insert(
                        &store.record,
                        rocks::key(a, r.path.as_bytes()),
                        rocks::record_value(&r.cid, &r.rev),
                    );
                    for n in &made {
                        batch.insert(
                            &store.block,
                            rocks::key(a, &n.cid),
                            block_value(&n.rev, &n.bytes),
                        );
                    }
                    batch.commit().expect("a commit");
                }
            }
        }
    });
    dbs.iter().for_each(stores::settle);
    fjalls.iter().for_each(fj::Store::settle);
    drop((dbs, fjalls));
    let (rewritten, other_rewritten) = (disk(), other());
    let wrote: Vec<[u64; 4]> = setups.iter().map(|s| s.written()).collect();

    let (dbs, fjalls) = (open(), open_other());
    for db in &dbs {
        for family in [rocks::BLOCK, rocks::RECORD, rocks::EVENT] {
            db.compact_range_cf(rocks::family(db, family), None::<&[u8]>, None::<&[u8]>);
        }
    }
    for store in &fjalls {
        for keyspace in [&store.block, &store.record, &store.event] {
            keyspace.major_compact().expect("a compaction");
        }
    }
    drop((dbs, fjalls));
    let (compacted, other_compacted) = (disk(), other());
    let rocks = (0..PACKS.len())
        .map(|i| Rocks {
            pack: PACKS[i],
            disk: [loaded[i], rewritten[i], compacted[i]],
            written: [wrote[i], setups[i].written()],
        })
        .collect();
    let fjalls = (0..fj::PACKS.len())
        .map(|i| {
            let disk = [other_loaded[i], other_rewritten[i], other_compacted[i]];
            (fj::PACKS[i], disk)
        })
        .collect();
    (rocks, fjalls)
}

pub fn size(accounts: usize, records: usize) {
    let dir = scratch("size");
    let (json, binary) = logs(&dir, accounts, records);
    stores::build(&dir, accounts, records);

    // Every table's data blocks, to train a dictionary on some and time
    // compressing all.
    let tables: Vec<Vec<u8>> = (0..accounts)
        .map(|a| std::fs::read(stores::table_path(&dir, a)).expect("a table"))
        .collect();
    let mut blocks: Vec<Vec<u8>> = Vec::new();
    for t in &tables {
        packed(t, |b| {
            blocks.push(b.to_vec());
            Vec::new()
        });
    }
    let sample: Vec<&[u8]> = blocks.iter().step_by(SAMPLE).map(Vec::as_slice).collect();
    let dictionary = zstd::dict::from_samples(&sample, DICTIONARY).expect("a dictionary");
    let plain: u64 = blocks.iter().map(|b| b.len() as u64).sum();

    let kinds = [
        Kind {
            name: "the tables, each block compressed (zstd 3)",
            dir: "tables-zstd",
            dictionary: None,
        },
        Kind {
            name: "the tables, each block compressed with a dictionary (zstd 3)",
            dir: "tables-dictionary",
            dictionary: Some(&dictionary),
        },
    ];
    // Per kind: its bytes on disk, and how long compressing and
    // decompressing every block took.
    let mut costs = Vec::new();
    for k in &kinds {
        std::fs::create_dir_all(dir.join(k.dir)).expect("a directory");
        let mut z = k.packer();
        let started = Instant::now();
        let stored: Vec<Vec<u8>> = blocks
            .iter()
            .map(|b| z.compress(b).expect("a block compressed"))
            .collect();
        let pack = started.elapsed();
        let mut z = k.unpacker();
        let mut out = Vec::with_capacity(1 << 20);
        let started = Instant::now();
        for s in &stored {
            z.decompress_to_buffer(s, &mut out)
                .expect("a block unpacked");
        }
        let unpack = started.elapsed();
        let mut next = stored.into_iter();
        for (a, t) in tables.iter().enumerate() {
            let file = packed(t, |_| next.next().expect("a block"));
            std::fs::write(dir.join(format!("{}/{a}.table", k.dir)), file).expect("a table");
        }
        let extra = k.dictionary.map_or(0, |d| d.len() as u64);
        costs.push((dir_bytes(&dir.join(k.dir)) + extra, pack, unpack));
    }
    drop(tables);
    let read_plain = read_records(&dir, "tables", accounts, records, &mut None);
    let reads: Vec<Duration> = kinds
        .iter()
        .map(|k| read_records(&dir, k.dir, accounts, records, &mut Some(k.unpacker())))
        .collect();

    let table = dir_bytes(&dir.join("tables"));
    let (each, one) = (dir_bytes(&dir.join("dbs")), dir_bytes(&dir.join("db")));
    let [each_after, one_after] = rewritten(&dir, accounts, records);
    let rowid = with_rowid(&dir, accounts);
    let (rocks, fjalls) = trees(&dir, accounts, records);

    println!(
        "{accounts} accounts of {records} realistic commits each, a record a commit. The logs hold every commit whole, its event and the tree nodes later commits took out too; the tables and SQLite hold what the commits leave, the records and the tree, and no event.\n"
    );
    println!("| kept as | MiB | KiB an account | bytes a record |");
    println!("|---|--:|--:|--:|");
    let row = |name: &str, bytes: u64| {
        println!(
            "| {name} | {:.1} | {:.0} | {:.0} |",
            mib(bytes),
            bytes as f64 / 1024.0 / accounts as f64,
            bytes as f64 / (accounts * records) as f64
        );
    };
    row(
        "a log for each account before compaction, JSON frames with holes (the server's)",
        json,
    );
    row(
        "a log for each account before compaction, binary frames",
        binary,
    );
    row("a table for each account", table);
    for (k, (bytes, _, _)) in kinds.iter().zip(&costs) {
        row(k.name, *bytes);
    }
    row("SQLite for each account", each);
    row("one SQLite for all", one);
    let times = format!("every record rewritten {REWRITES} times");
    row(&format!("SQLite for each account, {times}"), each_after.0);
    row("the same, vacuumed", each_after.1);
    row(&format!("one SQLite for all, {times}"), one_after.0);
    row("the same, vacuumed", one_after.1);
    row(
        "SQLite for each account, rewritten and vacuumed, its blocks in a table with a rowid",
        rowid,
    );
    for r in &rocks {
        let name = format!("one RocksDB for all, its blocks: {}", r.pack.name());
        row(&name, r.disk[0]);
        row(&format!("the same, {times}"), r.disk[1]);
        row("the same, compacted whole", r.disk[2]);
    }
    for (pack, disk) in &fjalls {
        let name = format!("one fjall for all, its blocks: {}", pack.name());
        row(&name, disk[0]);
        row(&format!("the same, {times}"), disk[1]);
        row("the same, compacted whole", disk[2]);
    }

    println!(
        "\nWhat RocksDB wrote to its files for what it was given, keys and values as they are, through the load and the rewrites, and then with the whole compaction too: to its log, to the files it writes from memory, and to those its compactions write.\n"
    );
    println!(
        "| RocksDB's blocks | given MiB | to its log MiB | from memory MiB | by compactions MiB | written for each byte given | with the whole compaction MiB | for each byte given |"
    );
    println!("|---|--:|--:|--:|--:|--:|--:|--:|");
    for r in &rocks {
        let [given, log, memory, compactions] = r.written[0];
        let after: u64 = r.written[1][1..].iter().sum();
        println!(
            "| {} | {:.0} | {:.0} | {:.0} | {:.0} | {:.2} | {:.0} | {:.2} |",
            r.pack.name(),
            mib(given),
            mib(log),
            mib(memory),
            mib(compactions),
            (log + memory + compactions) as f64 / given as f64,
            mib(after),
            after as f64 / r.written[1][0] as f64,
        );
    }

    println!(
        "\nThe tables' data blocks, {:.0} MiB in {} blocks, each ended at {} KiB as the server's writer ends them, compressed one at a time on one thread; the dictionary is {} bytes, trained on each {SAMPLE}th block and counted once above. A record is read by its path through two blocks, each read from its file (in the system's cache), its check computed, and searched: the median of {READS}.\n",
        mib(plain),
        blocks.len(),
        pds_store::table::BLOCK >> 10,
        dictionary.len()
    );
    println!(
        "| blocks | stored bytes of each 100 | compressing MiB per s | decompressing MiB per s | a record read µs |"
    );
    println!("|---|--:|--:|--:|--:|");
    println!("| as they are | 100 |  |  | {:.1} |", us(read_plain));
    for ((k, (_, pack, unpack)), read) in kinds.iter().zip(&costs).zip(&reads) {
        let z = dir_bytes(&dir.join(k.dir));
        // Of the blocks alone: the index, bloom filter and footer are the same.
        let stored = plain - (table - z);
        println!(
            "| {} | {:.0} | {:.0} | {:.0} | {:.1} |",
            k.name.trim_start_matches("the tables, each block "),
            stored as f64 * 100.0 / plain as f64,
            mib(plain) / pack.as_secs_f64(),
            mib(plain) / unpack.as_secs_f64(),
            us(*read)
        );
    }
    let _ = std::fs::remove_dir_all(&dir);
}