Real-Time Collaboration Explained - System Design

[00:02] these products lets dozens or even hundreds of people edit the same thing at the same time. And somehow it just works. You see everyone's cursors, changes appear instantly, nobody's edits get lost. This is collaborative editing,

[00:17] more often than you might expect in system design interviews. Design Google Docs, design a collaborative whiteboard, design a real-time code editor. It's one of the most common questions because it stressed has so many core concepts at

[00:32] once. Consistency in the face of concurrent rights, real-time communication, the tradeoff between latency and correctness. It goes on. Let's start with the problem. Every collaborative editing system has the

[00:45] same question. What happens when two people change the same thing at the same time? That's a conflict, and how you resolve it is the entire ballgame. If you've used Git, you already have an intuition for this. You write code for

[00:59] an hour, push, and if someone changed the same file, Git shows you both versions side by side and asks you to pick. It takes a minute, it's not a big deal. Git can do this because developers work in focused blocks. But for a

[01:11] real-time document, imagine typing a sentence in Google Docs and getting a merge conflict every 3 seconds. Hey, your coworker also edited paragraph two. Which version do you want? It would be unusable. So real-time collaboration

[01:25] needs automatic merging. Edits have to combine on their own immediately without human intervention, and the result has to make sense. Git's stop and ask the human approach works when you're merging once an hour. It's just not viable when

[01:38] you're merging hundreds of times per second. So what can we do instead? Let's start with the simplest approach. The most obvious thing we can do is to have every client write their version of the document to a blob store. The user types

[01:52] a character, sends the whole document to the server, and the server saves it. This is last writer wins. The document starts as the quick fox. User A adds brown and submits the quick brown fox. User B adds jumps and submits the quick

[02:09] fox jumps. Whoever's write arrives last completely overrides the other. You're silently losing edits every time two people type at the same time, and you're sending the entire document over the wire on every keystroke. It's both wrong

[02:24] and wasteful. Okay, so instead of sending the whole document, let's just send the edit. Instead of here's my entire document, the client says, I inserted these characters at this position, or I deleted the character at

[02:38] that position. This fixes the bandwidth problem, a tiny operation description instead of the whole document. But it introduces a new problem. So let's take introduces a new problem. So let's take the same document, the quick fox. User A

[02:52] inserts brown before fox. User B inserts jumps at the end. But these operations are encoded as positions, like character offsets into the string. User A says, insert at position 10. User B says, insert at position 13. If user A's edit

[03:09] arrives first, the document becomes the quick brown fox. Great. But now user B's insert at position 13 arrives, and position 13 isn't the end of the document anymore. User A just added six

[03:24] characters, so position 13 is now the middle of the word brown. The word jumps lands in completely the wrong place. Each edit references positions in a specific version of the document, but by the time that edit arrives at the

[03:37] server, the document has changed, and those positions point somewhere completely different. This is the core challenge for collaborative editing. Every edit references position in a specific version of the document, but by

[03:50] document may have changed, and those positions may point somewhere completely different. Every collaborative editing algorithm is a different answer to this question. How do you apply concurrent position-based edits when each edit

[04:03] might shift the position the other edit references? Okay, let's get into it. Our first stop is operational transformation, or OT, which was the first widely deployed solution dating back to the late 1980s. Google Docs is a

[04:17] great example that uses OT. The main idea is right there in the name. You transform operations. When two edits happen concurrently, you mathematically adjust one operation so it accounts for the effect of the other. Back in our the

[04:32] quick fox example, user A wants to insert brown, and user B wants to add jumps at the end. Both edits arrive at the server at roughly the same time. The server picks an order. It applies user A's edit first. The quick fox becomes

[04:48] the quick brown fox. Now it needs to apply user B's edit. But user B said insert at the end, and the end of the document just moved because user A added six characters. OT does the math, shifts user B's position forward by six, and

[05:04] applies it in the new spot. The result, the quick brown fox jumps. Both edits are preserved right where the user intended. The server acts as the single source of truth. Every client sends their operations to the server, and the

[05:18] server decides the canonical order. When a client receives an operation from the server that conflicts with something they've applied locally, the client transforms its pending operations against the incoming one. For simple

[05:31] text operations like insert and delete, the transformation rules aren't too bad. There are a handful of cases, insert versus insert, insert versus delete, delete versus delete. You can adjust positions based on whether the other

[05:44] operation was before or after yours. But this is where OT gets nasty. The number of transformation rules grow with the square of your operation types. Text editing has two operations and needs four transformation rules. If you add

[05:58] formatting like bold, italics, and underline, and now you need transforms for every pair. If you have tables, images, lists, you're looking at dozens of operation types and hundreds of transformation pairs. Joseph Gentle, an

[06:12] engineer in Google Wave, put it bluntly. The transformation functions are mathematically subtle, edge cases lurk everywhere, and a bug means that documents diverge, which means users end up looking at different versions of the

[06:25] same doc with no idea anything went wrong. The other major constraint of OT is that you fundamentally need a central server. You can do peer-to-peer operational transform in theory, but the transformation logic becomes

[06:38] dramatically harder. With a central server, there's one canonical ordering, and transformations only need to work against that sequence. So OT works, and it powers some of the most used collaborative software on the planet,

[06:50] but it's complex, scales poorly, and practically it requires a central server. That brings us to our next option, which are CRDTs, or conflict-free replicated data types. They take a fundamentally different

[07:05] approach. Instead of transforming operations after the fact, CRDTs design the data structure itself so that concurrent edits can never conflict. The merging logic is baked into the data structure, it's not bolted on top. The

[07:19] idea came out of distributed systems research in the late 2000s. The key thing is, if you design your merge function so that the order you combine things doesn't matter, and combining the same thing twice doesn't do anything

[07:33] extra, then replicas can sync with each other in any order, any sequence, timing, network topology, and they'll always eventually end up in the same state. Mathematically, there are a lot of functions that work like this. Think

[07:47] of a simple counter where each node tracks its own count, and the merge function just sums them all together. No matter what order we do the additions, we still get the same result. For text editing, CRDTs get more creative. The

[08:01] most common approach for collaborative text is to give every character a unique, globally ordered ID that never changes, no matter what gets inserted or deleted around it. So take a CRDT like Yjs, which is one of the most popular

[08:15] implementations. When user A types a character between positions two and three, Yjs assigns it an ID that's between the IDs of those two neighbors. When user B independently types a character in the same spot, they get a

[08:30] different ID, but it's in the same range. And since IDs are globally unique and totally ordered, there's a deterministic sort order. Both users end up with the same sequence, despite the fact that they saw the edits occur in a

[08:44] different order. Now this is mathematically elegant. There is no transformation needed, no central server. Each replica applies their edits independently, and the mathematical properties of the IDs guarantee that all

[08:58] users are seeing the same thing. So if two users are on a plane with no internet, they can both edit, and when they reconnect, their changes merge automatically. Cool, but there's a catch. When you delete a character in a

[09:11] CRDT, you can't actually remove it from the data. Other replicas might still reference it. So deleted characters have to become tombstones, invisible, but still taking up space. Over time, a heavily edited document accumulates a

[09:25] lot of dead weight. And while libraries like Yjs and Automerge have gotten clever, the overhead is fundamentally there. And a bigger issue is that convergence, being that all users see the same document, doesn't mean

[09:39] correctness. CRDTs guarantee every replica ends up with the same document, but they don't guarantee that document makes sense. If user A moves a paragraph while user B edits it, the CRDT will dutifully preserve both changes, but you

[09:55] might end up with the edited text in the wrong location or the moved text with stale content. The algorithms have no concept of what the users actually meant or their intent. So, what are CRDTs actually good for? CRDTs can work

[10:10] offline or in flaky networks. If you're building something like Apple Notes where devices sync without a central ordering server or a local-first app that works entirely offline, CRDTs are really the only game in town. That's a

[10:24] strong enough reason to reach for them. But if you have a server anyway, and you almost certainly do for all permissions, storage, you're paying the complexity tax for a capability you might not need. Our last option is differential

[10:38] synchronization and it's arguably the least well known of the three, but also the most intuitive. Neil Fraser at Google published it in 2009 and it was used in some Google products. It's pretty simple. Each client keeps two

[10:51] copies of the document, what they have now and what they had the last time they synced. Periodically, they diff those two copies to figure out what changed, send that patch to the server, and the server applies it. The server does the

[11:04] same thing in reverse. It diffs its current state against what it last sent to each client and sends patches back. That's it. Diff, patch, repeat. No transformation functions, no special data structures. You just need a good

[11:19] diff algorithm and a good patch algorithm. If you can diff and patch, you can do collaborative editing on it. This algorithm works in a loop. On the client, you make a diff between your current document and your shadow or the

[11:31] last known common state. You send that diff to the server. You update your shadow to match your current document. On the server, you apply the incoming diff to the server's copy, then make a diff between the server's copy and what

[11:43] it last sent to this client, send that diff back. Both sides continuously patches. The tradeoffs are what you'd expect from something this simple. It's lossy, meaning intermediate edits kind of disappear into the diff. It needs a

[11:59] server and it's less granular than OT or CRDTs. So, things like cursor sharing don't come naturally. But if you need collaborative editing on an unusual data format and approximate merging is good enough, differential synchronization or

[12:15] effort. So, which one should you actually use? Most comparisons come down to OT versus CRDTs, but differential sync and some of its hackier cousins are actually real contenders. If you're building a product, you should honestly

[12:30] consider your alternatives. In terms of implementation, OT is the hardest to it as one of their most painful engineering efforts. CRDTs are hard to design but easier to use correctly. Libraries like Yjs and Automerge mean

[12:46] that you don't need to implement the CRDT yourself. Differential sync is the simplest to build from scratch. It's easy. In terms of infra, OT needs a central server, full stop. Peer-to-peer OT exists in academia, but it doesn't

[12:59] work in practice. CRDTs work everywhere, server, peer-to-peer, offline. This is their killer feature, being able to work with arbitrary network topologies or basically how your clients connect to one another. Differential sync needs a

[13:14] server or direct connections between your clients. It's more flexible than OT, but less flexible than CRDTs. In terms of bandwidth and memory, OT is the goat. It's most efficient in terms of bandwidth and memory and the operations

[13:28] are small because you don't need a bunch of extra metadata. CRDTs, on the other hand, have higher memory overhead due to per-character metadata and tombstones, and while modern implementations have compressed this down significantly, it's

[13:42] still the worst of the three for very large documents. So, let's summarize. If you need true masterless peer-to-peer editing, devices syncing directly with another, no server in the loop, CRDTs

[13:55] are your only real option. Apple Notes syncing across your devices, a local-first app, these are legitimate CRDT use cases. For what it's worth, we use CRDTs for Hello Interview because Yjs is just a well-built library and we

[14:10] particularly complex use cases. If you're extending an existing OT system engineering muscle, OT is proven at massive scale. Don't switch away from something that works. And lastly, if you need collaborative editing on an unusual

[14:26] data format, tree-structured data, something interesting, and approximate merging is acceptable, differential sync gets you there with minimal effort. But I'll leave you with a hot take. If you have a server, and you probably do

[14:39] because your app needs a bunch of things for it, a simple server-authoritative approach might be your best default. Send your edits to the server along with the base that they came from and have the server reject the ones that occurred

[14:53] after an edit was already committed. Then all of the merging can take place on the client. You can decide what to do with those conflicts in a sensible way, and as long as your clients have internet access, you not only can get

[15:06] something incredibly performant, but you have much more control over the UX than have much more control over the UX than something like CRDTs or OT where When it comes to collaborative editing, the design space is wide open. Blend

[15:21] them all, mix your own like Figma. I hope that this video gave you some idea about how the pieces work so that you can go build some awesome collaborative can go build some awesome collaborative editing apps.