Squeezing better Brotli output from mid-tier presets

Brotli has become the default choice for lossless text compression on the web, and Cloudflare has used the Google brotli library for dynamic compression since the format gained browser support. Brotli’s static dictionary is one of its most distinctive features: alongside LZ77-style back-references, the encoder can replace byte sequences with references to a built-in dictionary of 13,504 words across six languages, each word typically 4–24 characters long. Those words can also be transformed in 120 ways, including suffixes, prefixes, capitalization and trimming, to increase match coverage.

The dictionary’s full power, however, is generally reserved for the slowest encoder settings. The open-source library defines 11 quality levels; the static dictionary is only partially used from level 5 onwards, and is used to its full extent only at levels 10 and 11. The reason is search cost: the transforms expand the dictionary into roughly 1.6 million possible word forms, far too many to search exhaustively at lower levels. Google’s implementation therefore restricts lower-level dictionary use to a subset of ~5,500 words, and only searches for matches when LZ77 fails to produce one. Only the “cut” transform is applied at these levels.

For web content, that leaves meaningful compression on the table at the levels Cloudflare actually uses for dynamic responses. Their work set out to use a larger, more specialized dictionary subset at levels 5–9, adding heuristics that keep the extra CPU cost small enough for production traffic.

A trie, a hash table and a bloom filter

The core problem is lookup speed. To search more of the dictionary without a large CPU hit, they built a pipeline of three data structures that decide, at each position, whether a dictionary match is worth chasing:

  • A radix trie maps the current text position to the longest possible dictionary word. Compressed nodes (edges labelled with more than one character) keep traversal shallow.
  • A hash table indexes the first four bytes of every word, so the trie is only entered when the prefix actually exists in the dictionary. Mismatches are rejected before any trie descent.
  • A k=1 bloom filter sits in front of the hash table. Since the filter is a single bit per hash slot and the hash table needs 16 bytes per entry, filter lookups avoid cache misses and can discard more than half of all non-matching positions with one memory access.

The first four bytes matter more than the rest: most strings that don’t match the dictionary diverge within that span, and the trie’s early nodes tend to have many children. Feeding those four bytes into a hash table bypasses that expensive early traversal entirely; the bloom filter then prevents many unnecessary hash probes in the first place.

Three heuristics keep the broader dictionary search fast enough for live use.

Search only at promising positions. Unlike the stock implementation, which only tries the dictionary where LZ77 found nothing, the new approach also explores positions where LZ77 produced a poor match by its own cost model — for example, short matches or matches with a long distance back to the reference.

Only transform the longest match. Rather than enumerating every dictionary word and transform at a position, they take the longest word the trie can find and apply a transform to it. This is far cheaper and, in the common case, picks the best available match.

Restrict the transforms. Suffix transforms (e.g., “work” → “working”) are applied after the trie returns a plain match, and uppercase variants are inserted into the trie itself as separate entries. Prefix and cut transforms are not supported because they don’t fit the trie structure well; cuts of more than one byte are also omitted.

Building a shorter dictionary

Storing every dictionary word plus its uppercase variants would require about 31,700 trie entries and ~11,000 four-byte hash prefixes — slow to build and search. Instead the team generated reduced dictionaries tuned per content type. Using a large sample of representative web traffic collected from several world regions, they ranked dictionary words by how often they match and how much they reduce output under Brotli’s cost model. They also dropped words whose hash values slow down lookups for more useful neighbours.

The resulting word lists contain roughly 15–35% of the full dictionary (including uppercase forms), and separate dictionaries are generated for HTML, CSS and JavaScript, selected by the response’s Content-Type header. The same tooling can be pointed at other text formats, such as non-English or XML data, to produce a similarly reduced dictionary.

Results at level 5

Testing used a data set of HTML, CSS and JavaScript files up to 256KB, reflective of typical web sizes; smaller files benefit most from dictionary matching because LZ77 has little history to reference. Compression was measured at quality level 5 on an Intel Core i7-7820HQ, defining improvement as the relative size reduction versus the same level without the dictionary.

For files in the 5–50KB range, dictionary-matched compression typically delivered around five to eight percentage points of size reduction on HTML and JavaScript, with CSS improvements running higher. Gains tapered off as files approached 200KB. These average figures mark the difference between weighted (by file size) and unweighted averages over the test pool, which skewed toward small files in line with real traffic.

The significant result is the cost: using the reduced dictionary at level 5 raised CPU usage by only 1–3%. By comparison, moving from level 5 to level 6 costs up to 12% more CPU — and the dictionary approach produces output that is comparable to, or better than, level 6 and sometimes higher, at a fraction of the performance penalty. That makes mid-level Brotli settings a more attractive operating point for dynamic compression on busy servers.