Dropbox Nucleus: sync engine rewritten in Rust

01 · CONTEXT

What a sync engine does and why it is hard

A sync engine runs on the user's computer and coordinates the upload and download of files to a remote file system. Nucleus is the codename of the new engine, rebuilt from scratch for the desktop client over four years.

The scale is large: Dropbox has hundreds of billions of files, trillions of revisions, and exabytes of customer data. In addition, clients can stay offline for long periods and reconcile their changes on return, which makes network partitions a normal operation rather than an exception.

An example shows how durability goes beyond not corrupting the server. The legacy engine represented a move as a pair of a delete at the old location and an add at the new one. If the delete went through and the add did not, the user would see the file gone from the server and from other devices, even though they had only moved it locally.

02 · WHY REWRITE

From data model debt to Nucleus

Rewriting from scratch has a bad reputation: Joel Spolsky called it the single worst strategic mistake a software company can make. Dropbox itself says the rewrite was very hard and was only a great idea because of the care with which the process was carried out.

The most important cause of the legacy engine's problems was the data model, which was born for a world without sharing, with files lacking a stable identifier across moves. Refactoring alone does not change the data model fundamentals, and performance improvements in memory use, such as increasing the number of files managed, remained elusive.

03 · DATA MODEL

Three trees instead of pending work

The legacy engine persisted the pending work for each file or folder. Nucleus persists observations: it keeps three trees, each internally consistent, from which correct sync behavior can be derived.

1. Two trees describe the real world: the remote one, with the latest state in the cloud, and the local one, with the last state observed on disk.

2. The synced tree holds the last state known to be fully synchronized between the two and can be seen as a merge base, as in version control.

3. The planner takes the three trees as input and produces operations to converge them incrementally.

4. If the local tree matches the merge base, a file present only in the remote was added in the cloud. Without the synced tree, it would be impossible to tell this apart from a local deletion.

5. The system's goal is to converge the three trees to the same state, and this becomes a testable rule: whatever the initial trees, they must converge.

Identifying nodes by a unique id also changes the move. In the legacy engine, nodes were indexed by full path; in Nucleus, a move is just an update to the moved node's attributes, and a tested invariant is that any moved folder is visible in exactly one place. Another invariant, of consistency: in the database, no file or folder exists, even transiently, without a parent directory. This is the principle of designing to eliminate invalid states.

In the case of two folders moved offline that would form a cycle, the legacy engine duplicated each directory. Nucleus keeps the original folders, and the final order depends on which engine sends its move first.

04 · CONCURRENCY AND PROTOCOL

One control thread and a strict protocol

In the legacy engine, scheduling was left to the OS, and that made integration tests non-reproducible. Components could create threads freely and coordination used a series of global locks.

1. Almost all of Nucleus's code runs on a single control thread, which reduces what the developer has to consider when adding a feature.

2. The control thread is designed to be fully deterministic when inputs and scheduling decisions are fixed.

3. Whatever does not stay on the control thread is delegated: network IO to an event loop, hashing to a thread pool, and filesystem IO to a dedicated thread.

4. The client talks to the server over a protocol that guarantees the same view of the remote file system before a mutation is considered.

5. On the server, the backend includes a metadata database and the file content storage, among other services.

The client-server protocol was redesigned with strong consistency: files and folders support atomic moves regardless of subtree size, and any discrepancy between the client's view and the server's is a bug.

Nucleus was written in Rust, which lets you encode invariants in the type system and have the compiler check them.

05 · DETERMINISTIC TESTING

Randomized tests that always reproduce

The rule is that all randomized testing frameworks be fully deterministic and easy to reproduce. Each run generates a seed, uses a pseudorandom generator with that seed for all random decisions, and, if the test fails, prints the seed.

Tens of millions of random runs execute every night. When a regression appears, CI automatically creates a follow-up task for each failing seed. To keep the guarantee, even Rust's default HashMap was replaced with a deterministic hasher. Dropbox also runs millions of scenarios a day on its testing infrastructure.

CanopyCheck shuffles the set of operations to verify that order does not matter, and enforces additional invariants beyond convergence. One of them: a file present only in the remote tree must exist in all three trees at the end of the test. It was CanopyCheck that exposed the Archives/Drafts/January directory cycle bug.

1. Trinity is essentially a custom executor for the future that represents Nucleus, and so it schedules itself and the engine on the same thread.

2. The native filesystem is swapped for an in-memory mock, which allows about ten times more test runs.

3. The server backend is swapped for a mock in Rust, which allows reordering, delaying, and failing any RPC.

4. The clock is also simulated: Trinity can intercept a timeout, advance time, and fire the timeout whenever it wants.

5. With everything under control, Trinity modifies the local and remote file systems, reorders responses, injects filesystem and network failures, and simulates crashes.

6. If a run fails, the seed is printed and CI opens a follow-up task for it.

An example of a race Trinity hunts for: the engine deletes a file and overwrites the user's recent change. Trinity helps discover races of this kind before deploy.

06 · LIMITS AND LESSONS

What the tests do not cover

Simulating this much has a price. Running Trinity against the native filesystem costs about ten times in performance, and Trinity cannot restart the machine in the middle of a test, so it does not validate the use of fsync for crash durability.

There is also a high risk that the server mock's behavior drifts from reality. To test the protocol there is a separate suite, Heirloom, which talks to a real Dropbox server and runs about a hundred times slower than Trinity. In addition, Trinity cannot minimize failing test cases as easily as CanopyCheck.

The target of the rewrite had more than a decade to stabilize, and it was necessary to avoid regressing more than ten years of fixes. It was the deterministic frameworks that made it possible to do this safely.