Why Firefly’s Query Latency Climbed
Dropbox’s full-text search engine, Firefly, is designed to keep query latency under 250 ms at the 95th percentile. As the user base grew, that number drifted to 1000 ms. The team’s first step was to measure where the time was going.
Firefly does not keep its search index in RAM. Instead, it serves queries from solid-state drives (SSDs), which keeps the machine footprint small while supporting hundreds of billions of documents. The investigation pointed to a clear culprit: index servers had become I/O bound. The growth in users had driven up IOPS, and that increase was the source of the latency spike.
Reducing I/O at the Encoding Level
Every document update in Firefly mutates its inverted index. To cut I/O, the team needed to shrink the amount of data read and written during those updates. That meant revisiting the encoding scheme used for the index entries.
Conceptually, a search index holds a mapping from a token to a list of document IDs plus a set of attributes for that token:
token => List(Tuple(DocumentID, attributes))Attributes capture things like whether the token was in the document body, part of the filename, or an extension. The two lists are encoded separately and laid out adjacently in storage:
token => Header, Encoded(List(DocumentID)), Encoded(List(attributes))
A header precedes each entry and records the byte length of each encoded part plus the version of the encoding scheme. That version field turned out to be important: it allowed the team to introduce new encodings without breaking compatibility with older index entries.
For example, take the token “JPG” where it is an extension for documents 10001, 10002, and 10005, and appears as text in document 10007:
JPG => [10001, 10002, 10005, 10007], [Extension, Extension, Extension, FullText]
Two encoding changes were made. First, document IDs switched to delta encoding — each ID stores the difference from the previous one. The posting list above, with documents 10001, 10002, 10005, becomes much smaller when only the deltas are stored:
JPG => [10001, 1, 3, 2], [Extension, Extension, Extension, FullText]
Document IDs are also Varint-encoded, so smaller values directly translate into fewer bytes on disk.
Second, attributes switched to run-length encoding. Instead of repeating the same attribute for every consecutive document, the encoding stores the attribute once along with a run count:
JPG => [10001, 1, 3, 2], [Extension x 3, FullText]
Measured Gains
Together, the two changes cut the total size of the encoded search index by 33%. The size reduction came in two distinct steps, matching the two deployments:
The smaller index meant less I/O on the index servers, and the effect was immediate:
What surprised the team was that run-length encoding delivered a bigger win than delta encoding. They expected it to help mainly with filename tokens such as “jpeg,” where the same attribute (extension) recurs across many documents. It did help there, but it also produced a large reduction for full-text tokens. The likely explanation: many users have documents that contain a particular word only once, so across a large corpus, all those hits share the same attributes and compress cleanly.
The combined effect brought the 95th percentile latency back under the 250 ms target:
Takeaways
The project reinforced two habits. Tracking system vitals as the service scales is essential — had the team not followed up on the latency regression, the root cause might have stayed hidden. And extensible data structures pay off: without the versioned header on index entries, introducing alternate encodings would have been far more invasive.
After the encoding changes, Firefly’s index servers were no longer I/O bound, and search latency returned to the range users had come to expect.
