Collaborative editor (Google Docs)

01 · CONTEXT

Several people, one document

The classic exercise asks for a browser-based document editor in which several people edit the same document at the same time, see each other's changes in real time, and see the others' cursors and presence. Hello Interview assumes a plain text editor and leaves out sophisticated document structure.

The central challenge, according to the Google Docs team, is making sure all editing sessions end up convergindo on the same correct version of the document. Because the network is not instantaneous, whoever is editing temporarily creates a local version different from the one collaborators see.

Hello Interview lists as deep dives the scaling of connections WebSocket and storage control. This case focuses on the convergence of edits.

02 · COMPARING VERSIONS

Why comparing versions is not enough

The old Google Docs, like many collaborative word processors, compared versions: the server finds the differences between its version and the one received and decides how to merge them as best it can. Anyone with unsent changes has to compare the server's version with their own and merge locally.

1. Both start from the same text. John bolds the last two words, while Luiz replaces the last one with another.

2. John's change reaches the server first, which sends it to Luiz.

3. Luiz, who has only two versions to compare, does not have enough information to know which merge is correct; several combinations are valid ways of merging the two versions.

4. The correct result combines John's styling with Luiz's replacement, but just comparing versions cannot guarantee that the merge comes out as the editors expect.

An alternative would be to lock paragraphs so that only one editor types in each at a time, but Google's blog considers that not a good solution: it sidesteps the technical challenge instead of solving it and hurts the collaborative editing experience.

03 · LOG AND OT

A change log and operational transformation

The new editor stopped computing changes by comparing versions. The document is stored as a chronological series of changes, and the version is obtained by replaying that history. Every edit reduces to three kinds of change: insert text, delete text, and apply styles to a range. Editing is appending a change to the end of the revision log; to display the document, the log is replayed from the beginning.

Because each change's revision is known, you can check what the editor was seeing when they made it and merge it correctly with what has changed since. That is why, according to the blog, the editor's intent is never ambiguous.

Sending changes to the other editors is not enough, because people fall out of sync. In the blog's example, Luiz had two characters at the start of the text that John did not know about; if he applied John's first change unadjusted, he would delete the wrong characters. Luiz needs to transform John's changes so they become relative to his local document. The algorithm that handles these shifts is operational transformation, OT.

If OT is implemented correctly, it guarantees that, when all editors receive all changes, everyone sees the same version of the document. Not every pair of changes conflicts: a style transformed against a style of a different kind does not conflict, and style ranges expand when transformed against text insertions.

04 · PROTOCOL

Client, server, and the order of changes

Merging well is one problem; making sure each change is merged with the others when many happen at the same time is another, handled by the collaboration protocol. Each client separates local changes not yet sent from changes sent but not yet acknowledged, and the server keeps the full history of processed changes, the revision log.

1. Luiz types a word at the start of the document. The client puts it in the pending list, sends it to the server, and moves it to the sent list.

2. Luiz keeps typing, and John types an exclamation point in his empty version. Luiz's new change is not sent: the client never sends more than one pending change at a time and keeps new ones in the pending list until it receives the acknowledgment for the first.

3. The server stores Luiz's first change in the revision log, sends that change to John, and acknowledges to Luiz that it processed it.

4. John's client uses OT to transform Luiz's change against the change he still has pending. The result shifts the position of John's pending change to make room, at the start of the document, for Luiz's word.

5. When John's change reaches the server, it has already recorded a revision at that position in the log. The server transforms it against the changes acknowledged since John's last sync before storing it as the next revision.

6. In the end, the server and both editors see the same document.

According to the blog, the protocol makes collaboration fast, because each editor applies their own changes optimistically, without waiting for server acknowledgment, and the speed or reliability of the connection does not affect typing speed. The server does not need to know anything about each client's state, and only it knows the history, while only the clients know the unacknowledged changes.

05 · OT, CRDT, AND FIGMA

Alternatives: CRDT and Figma's path

A CRDT, a conflict-free replicated data type, is a structure replicated across several machines in which the application can update any replica independently, concurrently, and without coordination, and the replicas are guaranteed to converge. The development of CRDTs was initially motivated by collaborative text editing and mobile computing.

Figma chose not to use OT, the standard algorithm popularized by apps like Google Docs, and considered it too complex for its problem. For the team, OT is great for editing long texts with little memory and performance overhead, but it is very complicated and hard to implement correctly, and it leads to a combinatorial explosion of states that is hard to reason about.

Figma also does not use pure CRDTs: they are designed for decentralized systems, with no central authority deciding the final state, and since Figma's server is that authority, the team simplified the system and removed the extra overhead.

1. The clients are web pages that talk to the server over WebSocket. When opening a document, the client downloads a copy, and from then on updates in both directions flow over the connection.

2. Each multiplayer document has its own process on the server, which everyone editing it connects to.

3. A conflict only exists when two clients change the same property of the same object; in that case the document keeps the last value sent to the server.

4. Comments, users, teams, and projects live in Postgres, outside the multiplayer system, and are synchronized with clients by a completely separate system.

The cost shows up in text: if one person changes the value B to AB while another changes it to BC, the result is AB or BC, never ABC. For Figma this is acceptable, because it is a design tool, not a text editor.

Figma allows staying offline for an arbitrary amount of time: on returning, the client downloads a fresh copy of the document and reapplies the offline edits on top of the latest state. On the client, property changes are applied immediately, without waiting for server acknowledgment.

06 · IN THE INTERVIEW

How to organize the answer

Points to cover: the requirements (concurrent editing, real-time changes, cursor and presence); how to represent the edit, whether as a change log or as a property map; who defines the final order; how the client stays responsive and what happens when someone comes back from a disconnection; and connection scale and storage.