ThomasWaldmann
commented
1 year ago Thanks for the information and doing so much testing.
I see you used misc. VPSes - how can you know they provide consistent CPU and I/O performance, so your benchmark timings are comparable? Even on bare hardware, timings might fluctuate quite a bit due to other stuff the machine is doing in parallel.
Also: did these VPSes offer sha2 hw acceleration? This is quite importing when using sha256, which is otherwise quite slow. Without sha2 hw accel, blake2 is better (in case of borg).
You need to use a strong cryptographic hash - there is no point in using a fast weak hash if you have a higher risk of hash collisions.
At "extraction" time, one needs to assert chunkid_we_wanted == chunkid_hash(chunk_content_we_got) or a repo side attacker might give you a wrong chunk and not the one you wanted. for encrypted repos "hash" actually means a MAC here, computed with a secret key that a repo side attacker can't know. I initially thought I could get rid of that check by using AEAD crypto, but that's not the case.
Maybe for comparisons of misc tools, it would be better to just focus on one compression algorithm and level and have less result data to review. Of course that should be a fast one as we are not testing for compression performance, but rather for tool performance, so I'ld suggest lz4 or zstd,1.
safinaskar
jdchristensen
dbaarda
Glandos
UPD 2023-06-26 14:30 UTC: this is useless benchmark, see https://github.com/borgbackup/borg/issues/7674#issuecomment-1606015655 . I did proper benchmark here: https://github.com/borgbackup/borg/issues/7674#issuecomment-1607612493 .
Hi. I did many speed comparisons. Here are results:
borg --chunker-params fixedhas x2.5 slower compression speed than my own trivial single-threaded Rust program for data deduplication on same settings/algorithms (compression ratio is same). Decompression for borg is x4.5 slower"Compression" above means "all steps needed for putting given file (VM image) to deduplicator's storage". "Decompression" means opposite action, i. e. extracting from such storage. And everywhere I say borg I mean borg2.
Now let me give details. I'm writing "something like docker, but for VMs" for Linux. And I need deduplicating storage for this, i. e. something like what borg and casync do. So I did benchmark of various deduplicating solutions (and wrote my own trivial single-threaded Rust program). Test data is sequence of 12 snapshots of same VM. The zeroth snapshot (numbered 00) is VM created after fresh Debian install. Snapshot 01 is the same machine after execution of command
echo deb http://deb.debian.org/debian sid main > /etc/apt/sources.list. Snapshot 02 is snapshot 01 after commandapt-get update && apt-get install -y debootstrap && debootstrap sid /debian http://deb.debian.org/debian && : > /OLD && : > /debian/NEW && echo systemctl switch-root /debian /bin/bash > /root/.bash_history && apt-get install -y systemd, etc.Of course, all this snapshots are very similar, and there are a lot of redundancy here.
Test was performed so: I created fresh deduplicating storage, for example, by
borg2 rcreate .... Then I stored snapshot 00 to it using command likeborg2 create .... Then 01, etc. Then I extracted them back one by one. I recorded time of each storing and extracting. And size of resulting storage.The programs under test are these:
zstd -4 -T0(this command uses all available cores)--chunker-params fixedand--chunker-params buzhashwas tested. borg is single-threaded, according to docs.caibxas part of its storage. I. e. raw chunks only counted from casync's point of view. But (for fair comparison with borg) I counted them as part of storage. casync uses same chunking algorithm as borg2, i. e. buzhash. As it seems from docs, casync is single-threadedborg2 --chunker-params fixed), then deduplicates them and compresses using zstd. Similarly to casync the program manages chunks storage, but doesn't manage index files (i. e. user should manage index files somehow on its own, similarly to casync). But for fair comparison with other solutions index file sizes was counted as part of storage. The program is absolutely trivial and does bare minimum. Also it cheats: it compares chunks using weak murmur3 hash instead of some cryptographic hash (this is possible reason for good speed). But this should not affect decompression speed, because there is no reason to compute hashes when decompressing. The program is single-threaded. Unfortunately, there is no analog of casync'scasync gc(garbage collector) command, so proper deletion of data is not supported, i. e. chunk storage is effectively append-only (of course, this feature can be added if needed)The systems for testing was these:
The same versions of software used for both tests (expect for zstd, i. e. "control group", I'm sorry about that). All software was installed from debian repos (except for my solution, of course).
Okay, so here are some particular facts from this experiment.
Let's compare casync's default chunker settings with exact same borg's chunker settings. Here is result (DO):
As well as I understand from casync's sources, casync uses 48 as its window size, so I set same window size for borg. So, everything is same, chunker is same, compression is same (level 3 is default for
casync make --compression=zstd). So, we (predictably) get nearly same repo size. But compression speed is way bigger for borg. And decompression speed is way bigger for casync.Now let's compare
borg2 --chunker-params=fixedwith my dedupper with same chunk size and same compression (AWS):So, everything is same. And predictably we got nearly same compressed size. But my dedupper is way faster than borg both in compression and decompression (if we cheat using murmur3 for chunk comparision). Compression is x2.5 faster. And decompression is x4.5 faster. I don't compute hashes during decompression (I think there is no reason to do so), so even in sha256 mode decompression is still x4.5 faster than borg. But with sha256 compression becomes x2.3 slower than borg (it seems I chose slow sha256 implementation from crates.io or maybe the reason is
overflow-checks = true).Both casync and borg can achieve compression level similar to zpaq's default settings (if properly configured). But in such case casync and borg become better in compression speed or in decompression speed (DO):
Conclusions:
If I had blog, I would post everything there. But I don't have a blog, so I post everything here, to borg bug tracker. I hope this report will be useful to borg devs. If you want to write me, but don't want to pollute borg bug tracker, just write me directly to safinaskar@gmail.com .
Okay, now let me show you code and raw data.
Code for my dedupper:
Cargo.toml
```toml [package] name = "my-chunker" version = "0.1.0" edition = "2021" [profile.release] overflow-checks = true [dependencies] fastmurmur3 = "0.2.0" hex = "0.4.3" libc = "0.2.146" ring = "0.16.20" zstd = "0.12.3" ```src/main.rs
```rust #![feature(fs_try_exists)] #![feature(file_create_new)] use std::io::Read; use std::io::Write; struct Killed; // "kill" just means "completely drop this value". I. e. we drop it and then shadow it to make sure we will not be able to access it even if it is Copy. I. e. when you see "kill!", assume it is drop macro_rules! kill { ($x:ident) => { #[allow(dropping_references)] #[allow(dropping_copy_types)] std::mem::drop($x); #[allow(unused_variables)] let $x = Killed; } } #[derive(Clone, Copy)] enum Hash { MurMur3, Sha256, } fn calc_hash(hash_type: Hash, data: &[u8]) -> VecNow program for executing benchmark
Cargo.toml
```toml [package] name = "rust" version = "0.1.0" edition = "2021" [dependencies] regex = "1.8.4" serde_json = { version = "1.0.79", features = ["preserve_order"] } serde = { version = "1.0.136", features = ["derive"] } ```src/main.rs
```rust #![feature(exit_status_error)] // "[()] = [...]" is needed because of clippy bug: https://github.com/rust-lang/rust-clippy/issues/9048 . So when you see "[()] = [f()]", just assume "() = f()" fn run(s: &str) { [()] = [std::process::Command::new("bash").arg("-ec").arg(s).status().unwrap().exit_ok().unwrap()]; } fn main() { const REPO: &str = "/home/user/dedup-bench/fs/repo"; const CMP_ME: &str = "/home/user/dedup-bench/fs/cmp-me"; #[derive(Debug)] enum Method { ZStd, Borg { chunker_params: String, compression: String, }, Casync { chunker_params: String, }, Zpaq, MyChunker { block_bytes: usize, zstd: i32, hash: String }, } let range = 0..=11; // let range = 0..=2; // let range = 0..=5; run(&format!("rm -rf {REPO}")); run(&format!("rm -rf {CMP_ME}")); #[derive(Debug)] struct Run { method: Method, size: usize, compression: Vec[0-9]+)\t/[-/a-z]+\n$"##).unwrap().captures_iter(&x).collect::>();
assert!(caps.len() == 1);
size = caps[0]["s"].parse().unwrap();
}
{
let len = size
.to_string()
.chars()
.collect::>()
.rchunks(3)
.map(|x|x.into_iter().collect::())
.rev()
.collect::>()
.join("_");
println!("size: {len}");
}
let mut decompression = vec![];
for i in range.clone() {
run(&format!("sync -f {REPO}/; sync -f {CMP_ME}/"));
println!("**** {method:?} {i} decompression...");
let now = std::time::Instant::now();
match method {
Method::ZStd => run(&format!("zstd -d -T0 < {REPO}/{i:02}.zst > {CMP_ME}/data")),
Method::Borg { .. } => run(&format!("cd {CMP_ME}; borg2 extract --repo {REPO} {i:02} {i:02}; mv -i {i:02} data")),
Method::Casync { .. } => run(&format!("casync extract --store={REPO}/storage.castr {REPO}/index/{i:02}.caibx {CMP_ME}/data")),
Method::Zpaq => run(&format!("cd {CMP_ME}; zpaq extract {REPO}/repo.zpaq {i:02}; mv -i {i:02} data")),
Method::MyChunker { block_bytes: _, zstd: _, ref hash } => run(&format!("/my-chunker extract --chunks={REPO}/chunks --strong-hash={hash} < {REPO}/index/{i:02} > {CMP_ME}/data")),
}
run(&format!("sync -f {REPO}/; sync -f {CMP_ME}/"));
decompression.push(now.elapsed());
println!("**** {method:?} {i} decompression: {:?}", now.elapsed());
run(&format!("cmp /home/user/dedup-bench/sto/{i:02} {CMP_ME}/data"));
run(&format!("rm {CMP_ME}/data"));
}
run(&format!("rm -r {REPO}"));
run(&format!("rm -r {CMP_ME}"));
let total_compression = compression.iter().sum();
let total_decompression = decompression.iter().sum();
runs.push(Run { method, size, compression, decompression, total_compression, total_decompression });
}
for i in &runs {
println!("{:?}", i);
}
#[derive(Debug, serde::Serialize)]
struct JsonRun {
method: String,
size: usize,
compression: Vec,
decompression: Vec,
total_compression: u128,
total_decompression: u128,
}
for i in runs {
let Run { method, size, compression, decompression, total_compression, total_decompression } = i;
println!("{}", serde_json::to_string(&JsonRun {
method: format!("{:?}", method),
size,
compression: compression.into_iter().map(|x|x.as_micros()).collect(),
decompression: decompression.into_iter().map(|x|x.as_micros()).collect(),
total_compression: total_compression.as_micros(),
total_decompression: total_decompression.as_micros(),
}).unwrap());
}
}
```
Now snapshots. All snapshots are raw GPT disk images with single ext4 partition. Snapshot 00 is 2 GiB fresh install of debian sid from https://snapshot.debian.org/archive/debian/20220917T224346Z . Next snapshots are produced by executing the following sequence of commands:
I. e. snapshot 04 is snapshot 03 plus
apt-get install -y git build-essential. These snapshots naturally appeared when I attempted to reproduce particular systemd bug, so data is 100% realistic.The snapshot contain nothing confidential, so if you want, I can send them to you, just write me.
Now full benchmark results. (JSON is in the end.)
DO: https://paste.gg/p/anonymous/063883027e9848d8b7f53a046c4bd3cf AWS: https://paste.gg/p/anonymous/bd6d25d5906f4c0fb94b78af605fb475
(Unfortunately, I used
dufor calculating storage size, but, as well as I remember,duutils from DO and AWS seem to produce slightly different results, i. e. these twodu's use different algorithms)Assume all this code as public domain. If you want me to release any of my mentioned software as proper free software project (say, to crates.io), just write me.
Exact commands for invoking borg and other programs under test:
Is this a BUG / ISSUE report or a QUESTION?
I think borg is slower than needed. Possible bug