0

"Designing Google Docs" is a popular system design interview question, and there are plenty of articles on it on the web. However, those mostly touch on merging changes, but don't explain how to swiftly notify a user of a change made by another user in the same document. Supposedly, for collaborative editing getting notified of changes as fast as possible is one of the main requirements. So my question is, what design would allow to quickly notify all connected users of a document that another user just made a change? This design should meet the following requirements:

  • Deliver change notifications within seconds
  • Be scalable (up to 100 users can edit the document at the same time; no limit on the number of documents being concurrently edited in the system)
  • Be fault-tolerant

Change merging strategies are out of the scope of this question.


That was the question, now here are some of my thoughts and what I came up with:

The user client needs to have an open Websocket/longpolling connection to quickly get new changes. If this connection is handled by any random node, we have several ways of checking for new changes in the document:

  • Polling the database/some cache for new changes — puts unnecessary load on the system, is not going to be fast, doesn't scale
  • Running the changes through a single message queue and processing it on each node to notify users connected to node — doesn't scale, as the time between enqueuing a message and processing it would grow with the number of documents being edited at the same time

Neither of these two ideas seem to work, so what if user connections for a particular document are handled by a node designated to that document? Say, users working with documents D1, D2, D3 are routed to node N1, and users working with documents D4, D5 are routed to node N2. In this case a change made in a document by one of the collaborators can be sent to all the other collaborators as soon as this change is validated, merged and persisted to the database, because all collaborators are connected to the same node. Now, this design requires a separate registry service, which would:

  • Be aware which documents are being handled by which node
  • Designate a node to handle a document if this document isn’t currently being handled by any node
  • Do healthchecks against nodes to quickly reassign documents from a failing node to a healthy one

So, when a user wants to interact with a document, the user client makes a request to establish a connection, the node for the requested document is looked up in the registry, and the connection is established to this node.

Fault tolerance:

  • The client that makes a change gets notified once the change is persisted and acknowledged. If the client connection is broken, all unacknowledged changes get resent on reconnect.
  • If the client connection is broken, the client gets all the latest changes on reconnect.

Thus if the node unexpectedly shuts down, the routing service assigns the document to a new node, all users switch connections to that new node, get all the latest persisted changes, and unacknowledged changes are resent to the new node.

I think this design can work and is scalable, since it’s possible to introduce as many nodes as needed, spreading documents as thinly as needed between these nodes. However, I’m skeptical of the fact that instead of nodes that can handle incoming connections for any document I now have special-purpose nodes that can’t be killed without some hassle of switching all connected users to new nodes.

How do you find this design? What design would you advise?

8
  • 4
    the reason people like to ask this question is that it breaks the web paradigm of request and response. But really websockets has been a thing for a while now and anyone who has played a multiplayer game in the last 20 years is unsurprised that you can see what others are doing to a document
    – Ewan
    Sep 13 at 17:26
  • @DanWilson Could you please elaborate? How would those messages be partitioned, and how would the hub be scaled between multiple nodes?
    – sdds
    Sep 13 at 20:41
  • @Ewan My question is not whether it's technically possible, how to do it quickly and efficiently at scale, because for only thousands of concurrent users and hundreds of documents this is a no-problem. Could you elaborate on your comment?
    – sdds
    Sep 14 at 6:27
  • "Running the changes through a single message queue and processing it on each node to notify users connected to node" Why a single queue and not a topic per document?
    – JimmyJames
    Sep 14 at 15:54
  • @sdds when modern games easily handle 64 players all jumping around and shooting each other in real time with millisecond response times, why is have doc edits for 100 people and sub second response times considered a problem? Your naive approach with a queue and web-sockets is pretty much going to work
    – Ewan
    Sep 14 at 17:12
3

To solve the question of how Google Docs works:

Here is a Blog post by the guy who designed the syncing system of gdocs: https://neil.fraser.name/writing/sync/

The link point to a detailed writeup of a syncing system that can work in lossy enviroment like Internet.

the entire sync architeture algorithm shown, looks complex but it just has many parts to it

The whole process is just a giant diff-match-Patch cycle between clients and the Server farm(as one Server is unable to handle all load), controlled and timed by the client.

More Details can be found in the linked document.

Answer

The adaptive Timing(7) part of the linked document explains that the system works in a Timerange, (as example given, at most every 1 s, minimal every 10 s) to get changes pulled to the client.

The main request volume driver is the adaptive Timing, where even at a very long timescales with an sufficent amount of documents in circulation, every connected client needs to check if any changes happen in the meantime on their documents. Every thing else is just bootstrapping this process(on the client) or handling the resulting packets( server side).

As always in system design, find the main request count driver and design your system for its handling and ignore the rest in the design calculations.

The rest is just the interface design and server side request handling and storage.

2
  • Link-only answers are discouraged on Stack Exchange websites. Can you provide an explanation of the link's content in your answer instead? Sep 14 at 14:43
  • More Details provided.
    – Max N
    Sep 14 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.