Sled: Thoughts on rust-brotli

[Th3Whit3Wolf]

Use Case:

• Compression without zstd dependency
• Compression within a rust kernel

Proposed Change:

Add the rust-brotli compression (Brotli compressor and decompressor written in rust that optionally avoids the stdlib).

It should be noted that this version, according to dropbox. . .

we were able to compress a file at 3x the rate of vanilla Google Brotli using multiple cores to compress the file and then concatenating each chunk

I don't know if there are any benchmarks comparing this specific version of Brotli to zstd so I can't speak for what the performance difference may be.

Who Benefits From The Change(s)?

• User who need rust without zstd dependency (maybe embedded?)
• Compressing within a rust kernel

[spacejam]

In general, I'm very interested in getting rid of the zstd dependency. I've also experienced a lot of friction with the rust wrapper for it. I'm actually considering writing my own compression system, taking heavy inspiration from zstd, but leaning into adaptive dictionary compression and trying to apply some self-tuning techniques where appropriate. This may sound like a terrible idea, but I see some significant opportunities for increasing the compression ratio in a seamless way.

The main issue is that in sled, we're writing a ton of small records for most workloads. We don't want to compress larger blocks than the values that users are writing, because that would mean we need to read a lot more data off of disk in order to serve one read request, and we would need to also decompress a huge chunk, possibly keeping a decompressed block cache similar to rocksdb etc... Tiny compressed keys and values get terrible compression ratios, usually, because the substitution tables that are generated during compression are not able to be shared across tiny compressed buffers. Dictionary compression allows us to share these symbol tables across many tiny updates. zstd supports creating these dictionaries, but the provided interfaces are a bit cumbersome, and I'd like to possibly explore a novel approach to dictionary creation. After learning a bit about some of the theory behind how zstd works, guided by the zstd author's entropy table code, blog, and some relevant academic papers it doesn't seem like a prohibitive amount of work to just write a pure-rust compression library that will utilize similar techniques, compile fast, have great support for dynamic dictionary creation and ultimately build auto-tuning dictionaries for the log, and most importantly it would be a fun process that seems to potentially be aligned with a better db in the end.

re zstd vs brotli, I'm mainly concerned about some of the decompression benchmarks I've seen posted in comparison to zstd. I don't have a lot of context for this yet, but if I go down this path I'd like to fully understand why brotli seems to achieve similar compression speed and ratios to zstd in many cases but achieves like 1/3 the decompression speed. brotli uses a precomputed dictionary, and I'm not sure how hard it would be to create a custom one to fit a particular data set.

re using parallelism to compress, this is not useful for the sled use case because we compress and decompress tiny buffers often. there is a certain overhead associated with distributing and then collecting a parallelized compression workload, and it makes sense when the volume reaches a certain point, but sled operates on small buffers that are likely to be well below that point. This point can also be auto-tuned based on runtime-gathered statistics, but as far as I know, nobody is doing this yet, and it seems like maybe not the best place to spend a complexity budget for the time being. While tree nodes are compressed together and in larger buffers, delta updates written to disk are much smaller. while some systems like rocksdb don't compress recently written data, and only add compression to later levels of an lsm, I've measured that sled's write throughput can increase significantly if threads perform compression on recently written data as well.

One principle I like a lot is that you should align the human time spent with the actual interesting problems you want to solve. I see dynamic dictionary compression as potentially being a really powerful technique to apply to storage engines that are expected to run over long periods of time and with potentially shifting usage patterns, and I've started to learn a bit about the underlying theories about this to see if it feels feasible to go forwards with my own thing. But it's possible I'll put a few days of effort into it, see that my code has months of effort left to become competitive with off-the-self options, and maybe abandon the approach. But from my current perspective it doesn't seem too outlandish.

[Th3Whit3Wolf]

Thank you for the very in depth response. I'd love to see sled able to use a compression method that not only doesn't require and external dependencies but is also optimized for it's use case!