Tuesday, March 17, 2020

Rewriting Dropbox’s Sync Engine in Rust

Sujay Jayakar:

Rewriting the sync engine was really hard, and we don’t want to blindly celebrate it, because in many environments it would have been a terrible idea. It turned out that this was an excellent idea for Dropbox but only because we were very thoughtful about how we went about this process. In particular, we’re going to share reflections on how to think about a major software rewrite and highlight the key initiatives that made this project a success, like having a very clean data model.

[…]

There were few consistency guarantees, and we’d spend hours debugging issues where something theoretically possible but “extremely unlikely” would show up in production. Changing the foundational nouns of a system is often impossible to do in small pieces, and we quickly ran out of effective incremental improvements.

[…]

Rust has been a force multiplier for our team, and betting on Rust was one of the best decisions we made. More than performance, its ergonomics and focus on correctness has helped us tame sync’s complexity. We can encode complex invariants about our system in the type system and have the compiler check them for us.

[…]

The Control thread is designed to be entirely deterministic when its inputs and scheduling decisions are fixed. We use this property to fuzz it with pseudorandom simulation testing.

[…]

We redesigned the client-server protocol to have strong consistency. The protocol guarantees the server and client have the same view of the remote filesystem before considering a mutation. Shared folders and files have globally unique identifiers, and clients never observe them in transiently duplicated or missing states. Finally, folders and files support O(1) atomic moves independent of their subtree size.

Previously:

Update (2020-03-27): Sujay Jayakar:

  1. we write almost all of our logic on a single thread, using futures to multiplex concurrent operations on a single thread. then, we make sure all of the code on that thread is deterministic with fixed inputs. there’s lots of ways code can sneak in a dependency on a global random number generator or time.

  2. have traits for the interfaces between the control thread and other threads. we also mock out external time behind a trait too.

  3. then, wrap each real component in a mock component that pauses all requests and puts them into a wait queue.

now, instead of just calling .wait on the control thread future, poll it until it blocks (i.e. returns Async::NotReady). this means that the control thread can’t make any progress until some future it’s depending on completes. then, we can look at the wait queues and psuedorandomly unpause some subset of them and then poll the control thread again. we repeat this process until the test completes.

all of these scheduling decisions are made psuedorandomly from a fixed RNG seed that’s determined at the beginning of the test run. we can also use this seed for injecting errors, generating initial conditions, and “agitating” the system by simulating other concurrent events. the best part is that once we find a failure, we’re guaranteed that we can reproduce it given its original seed.

in fact, we actually don’t even log in CI at all. we run millions of seeds every day and then if CI finds a failure, it just prints the seed and we then run it locally to debug.

1 Comment RSS · Twitter

I wonder if this rewrite is the reason why symlinks aren’t supported any more? Seems like that happed at the same time this was rolling out.

Leave a Comment