Why a new compressor made sense
The rewrite of Dropbox's sync engine, codenamed “Nucleus,” was an opportunity to revisit assumptions baked into the original design. Compression wasn't new to the sync protocol, but the field had moved on since zlib was chosen years earlier. Newer algorithms offered measurable gains on both bandwidth and latency, but those gains had to be weighed against operational constraints. Earlier work like Lepton, a novel image recompression approach, proved valuable for specific cases but didn't suit general-purpose compression at network speeds on client machines.
Choosing Brotli, and making it Broccoli
Dropbox evaluated several lossless compressors on its incoming data stream, including 7zip, zstd, zlib, and Brotli. Brotli emerged as the winner, and five characteristics drove that decision:
- File size: Brotli selects Huffman tables dynamically at runtime using context bytes, which yields a multi-percent improvement over statically assigned tables.
- Pre-coding: Magic Pocket, the persistent storage layer, already held blocks compressed with Broccoli. Those pre-coded blocks could be served directly to clients on the download path, avoiding recompression entirely.
- Security: Nucleus is written in Rust. Only Brotli and zlib among the candidates have safe-Rust implementations, meaning the decompressor resists bugs and crashes even on intentionally garbled input.
- Familiarity: Dropbox already used Brotli for static web content, so the format was proven internally.
- HTTP support: Brotli is a standard for HTTP stream compression, so the same format serves both browser clients and the Nucleus sync engine.
The winning implementation, called Broccoli, is Dropbox's own Rust compressor. It offers two advantages over vanilla Google Brotli. First, it compresses files roughly three times faster by using multiple cores and concatenating per-chunk results. Second, it operates as a function call from Python and a Reader/Writer interface in Go, rather than requiring a low-privilege jail for raw C code. Avoiding that jail removes both maintenance overhead and the performance penalty it imposes on small files.
Making multithreaded compression work required a subset of the original Brotli protocol that allowed independently compressed chunks to be stitched into a valid output file. Those protocol changes are detailed in the appendix of the original engineering write-up.
The block sync protocol in brief
The desktop client sync protocol has two halves. The metadata sub-protocol handles file attributes—name, size, and similar—and tells the block sync engine which blocks are needed to reach a sync-complete state. The block sub-protocol moves actual data as aligned chunks of up to 4 MiB.
The block protocol itself exposes PutBlock and GetBlock end-points. For an upload, the client supplies both the block and its hash so the server can verify integrity on arrival. For downloads, the client asks for a block by hash. The storage layer underneath services those requests through Magic Pocket. Stripped of authentication and optimization layers, that interface looks like:
rpc PutBlock (PutBlockRequest) returns PutBlockResponse;
rpc GetBlock (GetBlockRequest) returns GetBlockResponse;
message PutBlockRequest {
bytes block_hash = 1;
bytes block = 2;
}
message PutBlockResponse {}
message GetBlockRequest {
bytes block_hash = 1;
}
message GetBlockResponse {
bytes block = 1;
}
Compressing the upload path
Compression on the storage layer was already supported, so adding it to uploads required extending the request with the compressed block format plus the hash of the uncompressed block. That second hash is not redundant. Since client machines rarely have ECC memory, there is an inherent risk of corruption during the compression step itself. Dropbox observes memory corruption in the wild at a constant rate, and end-to-end integrity verification is the accepted cost of durability.
message PutBlockRequest {
bytes block_hash = 1;
bytes block = 2;
// An enum describing what compression type is needed.
BlockFormat block_format = 3;
}
message PutBlockResponse {}
Verifying that the compressed file truly encodes the original requires an extra decompression call on the request path. That check adds server load, but the cost is tolerable. Benchmarks across file types showed Broccoli decompressing at upward of 300 MiB per second per core. Balancing that against durable storage is not a hard tradeoff: integrity always wins, and the performance impact stayed acceptable.
What the numbers showed
The upload path delivered daily average bandwidth savings of roughly 33%. Aggregated and normalized across users, half of all users saved at least 13%, a quarter saved around 40%, and the top decile saved roughly 70%. The median request size dropped from 3.5 MiB to about 1.6 MiB, while the p75 request size was essentially unchanged—evidence that a quarter of hosted data is largely incompressible, which is expected for formats like video and images.
Latency followed suit. The median saw roughly a 35% improvement. Request size and latency both exhibited periodic fluctuation: users work with highly compressible files like email, Word documents, and PDFs during the week, and switch to movies and pictures on weekends. File-extension analysis confirmed that savings came from non-image media, archives, and documents, not from images or video.
A deployment hiccup: compression as bottleneck
The rollout was smooth until the network team noticed compression itself became the limiting factor on high-bandwidth links, those running at 100 Mbps or more. The initial settings—quality level 5 with a 4 MiB window—were chosen for long-term storage durability. Benchmarking revealed those settings could not keep up with fast connections, so Dropbox trade slightly larger compressed outputs for lower quality settings that removed the bottleneck. The reasoning was user-first: better to avoid upload latency than to shave a few percentage points off data on the wire.
That change sacrificed some overall savings, dropping from roughly 33% to 30%, but peak large-file upload throughput rose from about 35 Mbps to 50 Mbps. The lesson was a reminder to challenge assumptions: the possibility that compression itself would become the bottleneck was not obvious at the outset.
Compressed Downloads: Client-Server Negotiation
The download path presented more design choices than uploads. The team considered either client-driven or server-driven compression-format selection, and ultimately settled on a hybrid: the client drives the interaction, while the server retains the ability to guide the client toward simpler formats when appropriate.
message GetBlockRequest {
bytes block_hash = 1;
BlockFormat block_format = 2;
}
message GetBlockResponse {
bytes block = 1;
BlockFormat block_format = 2;
}
This design avoids version-skew problems between client and server, and it allows an overloaded server to skip compression entirely and return raw bytes. Because the server knows the block size when it fetches from Magic Pocket, it can also determine whether compression is actually worthwhile. Brotli, notably, can add overhead to incompressible data, making the compressed block larger than the original—a scenario that occurs more frequently with small blocks. In those cases, the server simply returns uncompressed data. As usage data accumulates, the team targets these edge cases for modest performance gains.
Download Compression Results
The impact of download compression was measured across daily request loads. Average daily savings were around 15%, though the distribution skewed considerably by user. When normalized by host, 50% of users saved 8%, 25% saved about 20%, and the top 10% saw savings near 50%.
Request size at the median dropped from 3.4 MiB to 1.6 MiB. Unlike upload compression—which had negligible latency effects—the download path showed significant gains. Latency improved by 12% at p90, 27% at p75, and fully 50% at p50.
Bandwidth for most clients was largely unchanged, but the p99 average daily bandwidth improved from 80 Mbps to 100 Mbps at peak. This suggests that high-bandwidth connections extracted the most benefit from the compressed download link.
Deployment Hiccup and Fix
The rollout hit a snag during internal alpha testing (Dropbox employees only) when a client crashed. Given Dropbox's zero-crash policy and the assumption that a single alpha crash can presage thousands in stable releases, the team investigated immediately. Two problems emerged on the decompression path: a bug in the decompression library itself, and an architectural assumption that decompression would never fail.
The response was threefold: the server stopped sending compressed downloads, a patch was committed upstream to rust-brotli-decompressor, and the client was modified to fall back to vanilla downloads on decompression failures rather than crash. This incident validated both the internal-alpha process and the choice of a hybrid client-server protocol. The lesson was clear: the optimization path must fail open, falling back to the vanilla path and alerting on compression errors.
Future Directions
There is headroom for reducing CPU time where the underlying data is provably incompressible. Several techniques are under consideration:
- Maintaining a static list of common incompressible file types within Dropbox, enabling constant-time checks to decide whether compressing a block is worthwhile
- Detecting, before upload compression, whether the upload link is saturated or CPU-bound on compression, then choosing quality level and window size dynamically
- Applying heuristics that compute the Gaussian distribution and Shannon entropy of the byte stream to filter out likely incompressible blocks (similar to the approach in Btrfs)
The Rust implementation has been open sourced for community contributions.
Making Brotli Concatenatable
Brotli's data format presents several features that complicate constant-time concatenation of independently compressed blocks. The Broccoli protocol addresses each in turn.
Context. Brotli decodes byte-by-byte, selecting Huffman tables as it goes based on the preceding one or two bytes. The format supports raw-byte meta-blocks, which Broccoli exploits by always storing the first two bytes of a file in their own raw meta-block. Those bytes establish the correct Huffman table context for the rest of the stream. Without this seeding, a blind concatenation would give the wrong context for the second block's opening meta-blocks.
Bit alignment. Brotli is bit-aligned, not byte-aligned, and knowing how many bits are used in the final byte requires decoding the entire file. The required leading raw-byte meta-blocks come with a fortuitous property: they must be byte-aligned, so the stream always lands on a byte boundary, making concatenation safe.
Dictionary. Brotli ships a built-in dictionary of common phrases, accessed as if prepended to the file. If two chunks are blindly concatenated, a dictionary reference in the second chunk would fetch bytes from the end of the first chunk. The fix is to deactivate the dictionary during compression. Measurements show this costs only ~0.1% additional file size—well worth the correctness guarantee.
Final meta-block. The bit marking the last meta-block sits early in the file and requires sequential scanning. Broccoli sidesteps this by ensuring the last meta-block contains no output, using the last-meta-block bit code after the final raw-byte meta-block. This lets the trailing nonzero bits be dropped cleanly to make room for a subsequent file.
Assembled Protocol
These small compressor tweaks yield a concatenate-able Brotli stream:
- The format starts with an uncompressed raw-byte meta-block, two bytes long, carrying the file's first bytes and establishing the Huffman context and byte alignment
- The compressor ignores dictionary matches, preventing false back-references
- The final meta-block is empty, so identifying and dropping it—the last two nonzero bits—is constant-time
Files can now be concatenated in O(1) by removing the final pair of nonzero bits. A custom Broccoli header, stored in a Brotli metadata meta-block, encodes the software version that created the file, making blocks self-describing. Every Broccoli file carries the three-byte magic number e19781 in its first eight bytes; the header parser documents the byte-level structure.
