Cannes: ML saves $1.7M a year on document previews at Dropbox

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

Machine Learning Systems

Recommendations, ranking, feature stores and serving models at scale.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Real-World Systems · 12 minDesign collaborative editing (Google Docs)Several people edit one document at once and always end up seeing the same text: operational transformation, CRDTs, and the server that keeps order.Read hereClose

  The problem

  A shared document where several people type at once. Requirements:

  • Everyone sees changes within a fraction of a second.
  • All copies converge to the same text, whatever order edits arrive in.
  • Typing feels instant, even on a slow network.
  • History, undo, comments, cursors and permissions work.
  • A document can be edited offline and merged later.

  Why it is hard

  Two people start with AB. Alice inserts X at position 0. Bob, at the same moment, deletes B at position 1. If each applies the other's operation as received, Alice ends with XA (correct), while Bob who already deleted B and then inserts X at 0 gets XA too in this case, but with other edits the positions drift and copies diverge. The problem: a position means "where in the text as I saw it", and other people's edits change what that is.

  Two families of solutions

  Operational transformation (OT)

  A server puts all operations in one order. When your operation arrives and others were applied in between, the server transforms it (adjusts its position) so it still means what you intended. Used by classic Google Docs. Needs a central authority per document.

  CRDTs (conflict-free replicated data types)

  Give every character a unique identifier and a position between its neighbours' identifiers (not a numeric index). Operations then commute: applying them in any order yields the same result. No central referee is needed, which suits peer-to-peer and offline use. The cost is metadata per character and more complex data structures. Libraries such as Yjs and Automerge implement this.

  	OT	CRDT
  Central server	required to order operations	optional
  Offline editing	harder	natural
  Metadata	little	more (ids, tombstones)
  Maturity in products	very mature	fast-growing

  A simpler third option: differential synchronisation

  Instead of transforming individual operations, each side keeps a shadow copy of the last agreed text, computes the diff between its current text and the shadow, sends that diff, and the other side patches its own text with it. It is easy to build and tolerant of lost messages, but merges are fuzzier than OT or CRDTs, so it suits notes and forms better than a heavy, many-author document.

  Architecture

  100%

  Figure SDA-RWS-01-1 · Collaborative editing architecture · © forcsguy.com

  1. The editor applies your keystroke locally at once and sends the operation over a WebSocket.
  2. All editors of one document connect (through a gateway) to one collaboration server for that document, found by consistent hashing on the document id. One owner makes ordering simple.
  3. The server orders and transforms the operation, assigns a revision number, appends it to a durable operation log, and broadcasts it to the other editors.
  4. Editors that were behind apply the missed operations, using the revision numbers.
  5. Periodic snapshots of the document mean you do not replay the whole log to open it.

  Presence and cursors

  Cursor positions and "who is here" change constantly and need not be stored. Send them as ephemeral messages through the same server or a pub/sub channel, and expire them if heartbeats stop.

  Storage and scale

  • Operation log plus snapshots: the log gives history and undo; snapshots keep loading fast. Compact old logs.
  • Documents are independent, so partition by document id and scale out. The hot spot is one very popular document; limit the number of simultaneous editors or fall back to read-only viewers.
  • Permissions are checked on connect and on every operation.

  Failure handling

  • If the collaboration server dies, another loads the latest snapshot plus the log and clients reconnect and resend unacknowledged operations (they are tagged, so duplicates are ignored).
  • Clients keep a queue of unsent operations so a dropped connection loses nothing.
  • Autosave means there is no "save" button, because the log is the save.

  More on this site

  Related reading

  • Cannes: ML saves $1.7M a year on document previews at DropboxDropbox engineers · DropboxCase Studies
  • The Log-Structured Merge-Tree (paper)O'Neil et al. · UMass BostonPapers
  • Espresso: Distributed Document Store at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Vortex: Monitoring Server Applications at DropboxDropbox engineers · DropboxCase Studies

  Show 6 moreShow fewer

  • LISA '10 - Operations at Twitter: Scaling Beyond 100 Million UsersYouTubeYouTube
  • Determinism (4 parts) in League of Legends ServerRiotgames engineers · RiotgamesCase Studies
  • Automating Datacenter Operations at DropboxDropbox engineers · DropboxCase Studies
  • Netflix Guide to Microservices - Josh Evans, Director of Operations Engineering at NetflixNetflixYouTube
  • Cinchcast Architecture - Producing 1,500 Hours of Audio Every Day - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • GitLab BlogGitLab engineers · GitLabBlogs

  Open this lesson with its quiz and exercise