| @@ -0,0 +1,36 @@ | |||
| 1 | + | # System Design Interview: Designing Real-Time Collaborative Editing (Google Docs-style) | |
| 2 | + | ||
| 3 | + | The key question is how several people can type into the same document at once and all end up with the same text. | |
| 4 | + | ||
| 5 | + | ## Requirements | |
| 6 | + | ||
| 7 | + | - Multiple users edit one document simultaneously and see each other's changes in under a second. | |
| 8 | + | - Offline edits merge when the user reconnects. | |
| 9 | + | - Full version history. | |
| 10 | + | ||
| 11 | + | ## Two approaches to convergence | |
| 12 | + | ||
| 13 | + | **Operational Transformation (OT).** Each edit is an operation like `insert("x", pos 5)`. When two operations were made concurrently, the server *transforms* one against the other (if Alice inserted 3 characters before position 5, Bob's insert at 5 becomes an insert at 8). A central server orders operations, which keeps the transform logic manageable. Google Docs uses this family. | |
| 14 | + | ||
| 15 | + | **CRDTs.** Every character gets a unique, ordered ID (for example a position between two fractional keys plus a site ID), so concurrent inserts can be merged in any order and still converge without a central server. Yjs and Automerge are popular libraries. Cost: extra metadata per character and tombstones for deletes. | |
| 16 | + | ||
| 17 | + | In an interview, pick one, explain why, and mention the other. | |
| 18 | + | ||
| 19 | + | ## Architecture (OT version) | |
| 20 | + | ||
| 21 | + | 1. Clients hold a WebSocket to a **collaboration server**; all users of one document are routed to the same server (consistent hashing on document ID). | |
| 22 | + | 2. The server keeps the document in memory, assigns each incoming operation a revision number, transforms it against operations the client hadn't seen, applies it, and broadcasts it. | |
| 23 | + | 3. Operations are appended to a log in durable storage; periodic **snapshots** let you load a document without replaying its whole history. | |
| 24 | + | ||
| 25 | + | ## Presence and cursors | |
| 26 | + | ||
| 27 | + | Cursor positions and "who's here" are ephemeral, so send them over the same socket but don't persist them. | |
| 28 | + | ||
| 29 | + | ## Trade-offs to mention | |
| 30 | + | ||
| 31 | + | - Single owner server per document is simple but is a hotspot for documents with hundreds of editors; you can cap editors and make the rest viewers. | |
| 32 | + | - Snapshots every N operations trade storage for load time. | |
| 33 | + | - Permissions must be checked on every operation, not just on open. | |
| 34 | + | ||
| 35 | + | --- | |
| 36 | + | *Disclosure: I work on [Linkjob AI](https://www.linkjob.ai/), a real-time interview copilot.* | |
linkjobai / System Design Interview: Designing Real-Time Collaborative Editing (Google Docs-style)
Last active 5 days ago
Interview prep notes
linkjobai revised this gist 5 days ago · d8f1e22
1 file changed, 36 insertions