Brotli: Not Just for TV

When HBO’s Silicon Valley debuted Pied Piper, its fictional lossless compression algorithm, it inspired real-world engineering. We built our own take on that idea during Hack Week, and have since extended it into a bit-exact, lossless media compression algorithm that performs strongly across a broad range of images—more on that in future posts.

But beyond experimental codecs, our users need practical, industry-standard compression that works with tools they already have. That’s why we've been contributing open source improvements to Brotli, a codec already built into most major browsers. Shipping bits to business customers through Brotli costs 4.4% less bandwidth than gzip.

What Brotli Brings to the Table

Brotli is an open source project from Google, providing a versatile encoder with a range of time-space tradeoff settings. It’s already a supported encoding format in Mozilla Firefox, Google Chrome, Android Browser, and Opera. The diagram above shows how it applies to typical business use-case files—excluding photos and video—along with the Weissman score, the fictional metric created for Silicon Valley that famously favors compression speed over ratio.

Our integration into the storage pipeline rests on two pillars:

  1. Rapid ingestion of Brotli-compressed bytes—compression must run significantly faster than line speed.
  2. Safe, repeatable decompression of any valid Brotli stream.

The Speed-Space Tightrope

The central problem with pushing compression onto external traffic is balancing compression speed against ratio. Dropbox files are, on average, written once but read only a handful of times over their lifetime. If the desktop or mobile client can compress faster than line speed, we save user bandwidth and cut sync time without noticeable lag.

Default Brotli settings rely on Zopfli, which maximizes ratio but is slow. On a fast connection that uploads megabytes per second, Brotli can take 20 seconds to compress as little as 4MB. At the other extreme, a greedy algorithm like gzip -9 handles any line speed but can waste up to 10% of the achievable space.

Inside a Brotli File

To navigate that tradeoff, it helps to understand the format. Brotli files begin with a metablock header that defines a set of named Huffman tables. Each table assigns short bit codes to frequently occurring bytes and longer codes (or no code at all) to rare ones—just as in English text, a, e, i, o, and u are cheaper than z, x, or ø.

In the example above, for a file heavy with humuhumunukunukuapua'a, the most common letter u gets a single-bit code of 0, while the next common, h, gets the two-bit code 10. Common letters are always cheaper.

After the header, the file is a sequence of command blocks, each consisting of:

  1. The index of the Huffman table to use,
  2. Where and how much data to copy from earlier in the file,
  3. New bytes encoded with the selected table.

Making Compression Smarter

Deciding when to switch Huffman tables—starting a new command block versus continuing the current one—is a costly optimization. In greedy mode, Brotli tries a few candidate block splits and keeps any that reduce file size. Zopfli mode undertakes an exhaustive search to find the optimal split boundaries and encodes with those.

Our key insight was simple: optimal is often the enemy of good. In practice, many different split strategies yield nearly identical sizes. We cut the search space to just 5% of all possible splits, which preserved enough flexibility to occasionally find a “creative” split without paying for the full exhaustive sweep.

The tradeoff is minor: file size grows by only 0.45% on the suboptimal splits we miss, but compression speed more than doubles, bringing it in line with upload speeds. When you factor in that photos and video dominate Dropbox storage, the net bandwidth savings using our modified compressor is 4.4%. One more metric worth celebrating: the Brotli Weissman score climbs 6.5%—Richard Hendricks would approve.

Decompression, Made Safe and Deterministic

Once upload completes, files are durably stored, and on demand they must decode back to the original bytes exactly, securely, and repeatably. Our decompressor therefore must meet three criteria:

  1. Safety: It must handle hostile or corrupted input without failing unsafely.
  2. Determinism: Identical bytes must always produce identical output.
  3. Speed: It must keep up with decodes at scale.

The Brotli reference decompressor, written in C, only satisfies the speed requirement. It’s a sizable body of C code that could be neither deterministic nor bulletproof against crafted hostile bytes—there's too much of it to prove otherwise by inspection alone.

We chose Rust to write a new decompressor: a language that promises memory safety without garbage collection, concurrency without data races, and abstractions without overhead. Rust’s performance and memory profile match C, which matters because many of our services are memory-bound rather than CPU-bound.

We built rust-brotli as a direct port of the C decompressor into safe Rust, and also authored rust-alloc-no-stdlib, a custom memory allocator supporting standard boxes, fixed-size heap allocation, or stack-based pools. That lets us impose a memory ceiling for handling a single 4MB block. After allocating virtual memory, we arm an alarm timer using the alarm syscall to bound decode duration, then pivot into secure computing mode (SECCOMP), blocking all system calls except read, write, sigreturn, and exit.

Even if a hypothetical gap existed in Rust’s runtime safety net, a hostile process cannot escape this sandbox: the kernel’s SECCOMP filter rejects system calls before execution.

Porting From C: What It Took

Rewriting the decoder in Rust meant more than translating syntax:

  1. We created a malloc-like memory manager layer to decouple from the standard library, enabling SECCOMP later and no_std operation—released as rust-alloc-no-stdlib.
  2. We directly ported the bit_reader and Huffman modules, capturing unit test traces from the reference C decompressor for every input and output crossing those module boundaries.
  3. We ported the BrotliState continuation structure, mapping each C pointer to either a statically sized value, owned data, or an alias.
  4. The main decode loop required refactoring: helpers that previously pulled fields from a state struct were reworked so they could independently borrow the data they needed, sometimes splitting the state into related modular structs.
  5. Control flow needed cleanup—gotos and case fallthroughs were extracted into structured loops.
  6. Integration tests surfaced the usual C-to-Rust bugs: negative indices into sliced arrays, -- parsing as no-op double negation before Rust added fixity rules, and C's promotion of shifts to integer type where Rust operates on bytes.

Performance Trade-Offs in the Rust Decompressor

With safety, determinism, and correctness established, the last piece of the puzzle is raw speed. The Rust-based decompressor currently runs at roughly 72% of the speed of the vanilla -O3 optimized Brotli decompressor compiled with gcc-4.9 when decompressing 4 megabyte blocks. In absolute terms, that means it safely decompresses Brotli data at 217 MB/s on an Intel Core i7-4790 CPU at 3.60GHz. The remaining 28% gap comes from several specific sources.

Zeroing Memory

A surprising amount of time goes into zeroing memory during allocation. By instructing the Rust allocator to skip zeroing when allocating for Brotli, throughput improves to 224 MB/s.

Bounds Checks

Huffman-coded data with backwards references relies heavily on table lookups, which is where bounds checks become a bottleneck. Some of these checks are not obvious from the source code:

fn sum_array_len_2(buffer : [i32], offset : usize) -> i32{
  let sum : i32 = buffer[offset + 1];
  return sum + buffer[offset + 0];
}

This code unexpectedly requires two separate bounds checks rather than one. The issue is that offset + 1 might wrap in release mode (it would panic in debug mode), allowing the first overflow check to pass while the second one fails. The fix is to restrict the range of the index variable so no wrapping can occur:

fn sum_array_len_2(buffer : [i32], offset : u32) -> i32{
  let sum : i32 = buffer[offset as usize + 1];
  return sum + buffer[offset as usize+ 0];
}

On 64-bit systems, the usize type leaves ample computational headroom for the addition, and the Rust compiler can elide one of the two bounds checks since adding two 32-bit integers cannot overflow a 64-bit addition. Many other checks, however, cannot be eliminated the same way. To quantify their impact, the team added a fast!((array)[index]) macro that toggles between the safe slice operator [] and the unsafe get_unchecked() method, controlled by a --features=unsafe build flag. Enabling unsafe mode buys another speed increase, lifting the total to 249 MB/s and closing the gap with the C implementation to within 82%.

Offsets and Aliasing

The original C code caches direct pointers to buffers, passes them to helper functions, and even applies negative offsets at times. Rust's ownership model prohibits this style: it enforces a single mutable reference to a buffer at any time and does not permit negative slice indices. The Rust decompressor must instead track a base slice plus an explicit offset to avoid negative accesses and to keep multiple mutable borrows out of play.

Control Flow Translation

The C codebase also leans on goto statements and switch cases with intentional fall-through. Neither feature exists in Rust. The decompressor emulates this behavior with a while loop wrapped around a match statement, where fall-through becomes a continue and a C-style break keeps its original semantics.

These small performance costs are softened by an important characteristic of Brotli decompression: it is fully streamable. Since each chunk of bytes can be decompressed as it arrives, the decompression cost overlaps with network transfer time. Only the first and last packets add to overall latency, and because data travels compressed over the wire, fewer bytes need to be fetched in the first place. That means Dropbox syncs can finish faster despite the safe-language overhead.

The combination of Rust's security guarantees, deterministic behavior, and the ability to run without a garbage collector inside a SECCOMP sandbox makes the modest computational premium worthwhile. Bounds-checked arrays and strict safety models cost a little throughput, but they deliver a decompressor that is far easier to reason about in a security-sensitive environment.