TechPrufer
Get started
Dropbox
Dropbox logoDropbox · Feature trail

Block Compression Optimization

3 posts · Jun 2016 – Aug 2020

What this trail covers

Dropbox has implemented a modified Brotli encoder, codenamed Broccoli, to compress files before syncing. This optimization, layered into the block sync protocol, leverages redundancies in common file formats to reduce data on the wire, decrease bandwidth usage and latency, and decrease storage costs. The system allows for faster compression using multiple cores and in-process integration, and has led to significant reductions in median latencies and data transfer sizes. DivANS is a new framework for Brotli compression. Additionally, Dropbox developed a Rust-based decompressor for Brotli to ensure safety, determinism, and performance, sandboxing it with SECCOMP for enhanced security.

All Dropbox trails
  1. Broccoli: Syncing faster by syncing lessThis post details the development and implementation of Broccoli, a modified Brotli encoder for optimizing file sync. It describes the evaluation of various compression algorithms (7zip, zstd, zlib, Brotli), the selection of Brotli due to its file size advantages, security (Rust implementation), familiarity, and HTTP support. The post explains the 'Broccoli' modification to enable faster, multi-core compression and in-process integration, and how it's layered into the block sync protocol for both uploads and downloads. Results show median latency reductions of over 30% and data transfer reductions of the same amount, with significant bandwidth savings for users.
  2. Building better compression together with DivANSIntroduced DivANS, a new framework for structuring compression programs into independent stages (IR generation, IR optimization, and final bitstream conversion) to encourage community innovation and achieve better compression ratios. DivANS uses an LZ-based Intermediate Representation (IR) and Asymmetric Numeral System (ANS) for efficient serialization. Preliminary studies show concrete gains of 2% in compression ratios for many file types.
  3. Lossless compression with Brotli in Rust for a bit of Pied Piper on the backendThis post details the development of a modified Brotli compressor (Broccoli) that achieves faster compression speeds by excluding optimal block splits, leading to a 4.4% bandwidth saving. It also describes the creation of a new Brotli decompressor in Rust, focusing on safety, determinism, and performance, and its sandboxing using SECCOMP for enhanced security. The Rust decompressor achieves 72% of the speed of the C version, with further optimizations for memory zeroing and bounds checks.