Validating Nautilus: How Dropbox Measures Search Performance and Reliability

Dropbox's new search engine, Nautilus, was built to handle the company's unique workload characteristics. While search systems are often optimized for read-heavy traffic, Dropbox observes write volumes that are roughly 10 times higher than reads — files are created, edited, and deleted far more often than they are searched. This asymmetry shaped key design decisions in the retrieval engine's data structures and informed how the team validates both performance and reliability.

Index Format: Trading Compression for Write Efficiency

At the core of any retrieval engine are posting lists, which map each token to the documents containing it. A conventional posting list format stores the token alongside a grouped list of document IDs with metadata such as term frequency. That layout is well-suited for read-dominated workloads: searching for a token is an O(1) hash lookup followed by iterating through the associated document IDs.

For Nautilus, Dropbox chose a different approach. Instead of grouping document IDs per token, the reverse index uses an "exploded" format backed by RocksDB, where each (namespace ID, token, document ID) tuple is stored as its own row. The row key is formatted as <namespace ID>|<token>|<doc ID>, enabling efficient prefix searches against a given namespace and token.

This design embeds the namespace directly into the key structure, yielding two benefits. First, it provides a security guarantee: a query cannot accidentally return documents outside the user's accessible namespace. Second, it narrows every search to the relevant namespace rather than scanning the entire partition, improving performance on its own.

The trade-off is storage efficiency. Grouped posting lists can use compact encodings like delta encoding, while the exploded format requires one row per token-document pair. However, the exploded representation excels at handling index mutations. Adding a document is simply an insert operation per token, which key/value stores like RocksDB handle very efficiently. The storage penalty is mitigated by RocksDB's prefix compression of keys — the index ends up only about 15% larger than it would with a conventional posting list layout.

Serving Performance: What the Metrics Show

For serving performance, Dropbox tracks query latency at the 95th and 99th percentiles. Currently, the slowest 5% of queries must complete within 500ms, and the slowest 1% within 1 second. Median latency is expected to be significantly faster. As Nautilus was developed, the team instrumented every component to understand its contribution to overall latency, which surfaced several lessons.

  • Don't prematurely optimize: Initial analysis revealed that a surprising share of latency came not from retrieval itself but from fetching metadata from external relational databases — used for ACL checks and decorating results with folder paths, creators, and modification times. Optimizing the retrieval engine first would have addressed the wrong bottleneck.
  • Watch for "queries of death": A few pathological queries — often generated by software bugs rather than human users — can disproportionately harm overall latency. Dropbox built circuit breakers to filter these out and added a time budget mechanism. When the budget is exceeded, the retrieval engine stops fetching candidates; this protects system load but may omit results for very broad queries, such as prefix searches on a single token during auto-completion.
  • Replicas improve tail latency: Leaves are already replicated 2X for redundancy, but the replicas also serve queries. By sending each query to all replicas and using the fastest response, Dropbox reduces tail latency without extra hardware.
  • Build dedicated benchmarks: To iterate quickly on component-level bottlenecks, the team wrote a benchmark tool for the core retrieval engine. Running on leaves, it measures indexing and retrieval performance against synthetic data generated to mirror production characteristics — including namespace counts, document counts, and token distributions.

Reliability: Designing for Inevitable Failures

In a distributed system of this scale, failures are a certainty. Nautilus's design assumes hardware faults and software crashes will occur and focuses on automatic recovery for components in the serving path.

Stateless components — such as Octopus, which handles result merging and ranking, and the retrieval engine root that fans out queries to leaves — can be deployed across multiple instances and automatically reprovisioned when they fail. The harder problem is the leaf instances, which must maintain the actual index data.

Partition Assignment and Replica Groups

Nautilus divides the index into partitions, with each leaf instance responsible for a subset of the index. A dedicated coordinator maintains a registry of all leaves and assigns partitions to them. A newly started leaf remains idle until the coordinator instructs it to serve a partition, at which point it loads the index and begins accepting requests.

To handle the gap between a leaf starting up and becoming ready — or any leaf failure — each partition is replicated across leaf replica groups. A replica group is an independent cluster of leaves that provides full coverage of the index. With 2X replication, Dropbox runs two groups, each with its own coordinator.

This architecture also simplifies maintenance. New code can be rolled out incrementally without availability impact by deploying to one group at a time. Entire groups can be added or removed — useful for hardware or OS upgrades, where a group on new hardware can be brought online and fully operational before the older group is decommissioned. Throughout these operations, Nautilus continues to answer every search request.

Failover and Recovery

To recover quickly from leaf failures, every leaf group is over-provisioned by roughly 15% hardware capacity. This spare pool of idle instances sits ready to take over a partition the moment the coordinator notices that an active leaf has stopped serving requests.

When such a drop in partition coverage is detected, the coordinator selects an idle leaf and directs it to serve the lost partition. The replacement leaf then proceeds through a recovery sequence:

  1. Download the index — It fetches the partition's index data from the index repository. Because this snapshot was produced by the offline build process at an earlier time, the leaf starts with a stale index.
  2. Replay old mutations — The leaf reads the Kafka queue, starting at the offset that corresponds to when the downloaded index partition was built, and applies all subsequent mutations.
  3. Go live — Once the replayed mutations are applied on top of the downloaded index, the leaf is fully caught up. It then switches into serving mode and begins processing queries.

Nautilus represents the kind of large-scale engineering challenge—combining data retrieval and machine learning—that Dropbox's teams tackle regularly. The company credits Adam Faulkner, Adhiraj Somani, Alan Shieh, Annie Zhou, Braeden Kepner, Elliott Jin, Franck Chastagnol, Han Lee, Harald Schiöberg, Ivan Traus, Kelly Liu, Michael Mi, Peng Wang, Rajesh Venkataraman, Ross Semenov, and Sammy Steele for their contributions to this work.