How Multiplayer Data Structures Work
The Future of Work is a distributed system.
I was in graduate school at the beginning of COVID, so I spent a lot of time on Zoom and with new multiplayer collaboration software (at Stanford, it's hard not to be an early adopter). Some borrowed inspiration from the physical world with features like presence (knowing who else is viewing a document, who is online, or even extending to audio or avatars).
But other tools created something new that wasn't possible before. An entire class writing on a canvas at the same time. Interactive polls. Queues of raised hands, so you knew when you were about to be called (unless you were getting cold-called).
How are these tools created? How do products show you where every else's cursor is? How do conflicts get resolved when multiple edits come in at the same time?Powering the real-time collaboration features in products like Google Docs and Figma are two data structures: operational transforms and conflict-free replicated data types. Here's a high-level overview of how they work.
Operational Transforms (OT) are simple on the surface. They store a chronological list of every change for the document. A document is just an operation log of the changes. When two people simultaneously edit, the algorithm looks back at the operation log to guess what the intended edit should be.
Operational transforms were first described in 1995 in a paper called "High-Latency, Low-Bandwidth Windowing in the Jupiter Collaboration System." OT systems can be fast, but they have a single point of weakness, they rely on a centralized server to process the transforms (have you ever visited a popular document on Google Docs that's "too busy" to edit?).
Conflict-free replicated data types (CRDTs) showed up around 2006 and were formalized in 2011. CRDTs work without a single source of truth. "Conflict-free" means that updates can always be merged together on different replicas of the same data without any conflicts.
A trivial example is a one-way boolean. Imagine there is a variable that is 'true' if an event has happened, and 'false' if it hasn't. When different replicas report back different values, the merge strategy is always that "true" wins (since if one player observes the event, it has happened).
At a basic level, CRDTs need an update, query, compare, and merge algorithm.
Grow-only counter: Used for things like counting the number of page views. To merge, take the max of each replica's counter.
Positive-negative counter: Count the number of users logged in or the number of likes. Combine two grow only counters and use for for "positive values" and the other for "negative" values.
Last-Write-Wins-Set. Use the merge strategy of last-write-wins by attaching a timestamp to each request. Read about how Figma uses last-write-wins on their blog.
For further reading, Wikipedia and crdt.tech have more in-depth descriptions of the algorithms for each.
Some interesting CRDT implementations
Some interesting companies offering CRDTs-as-a-Service
Some interesting companies using CRDTs to create new experiences in old products