Algorithm behind Google Docs
Earlier this year, Google has launched new editors for documents and spreadsheets on Google Docs, built on a code base designed to improve collaboration and take advantage of the latest advances in the technology. These improvements to Google Docs are designed to help businesses to move to the cloud faster and be more productive than ever before. If you’ve never tried web-based documents, spreadsheets and presentations, you can instantly take a test drive at docs.google.com/demo.
In this post, we will describes how Google Docs uses an algorithm called operational transformation to merge edits in real time.
In documents, basically, there are three types of changes: inserting text, deleting text, and applying styles to a range of text. When someone edits a document, they’re not modifying the underlying characters that represents the document. Instead they are appending their change to the end of the revision log. To display a document, Google replay the revision log from the beginning.
To see what these changes look like, suppose that a document edited by John and Luiz initially reads; EASY AS 123 and if John changes the document to EASY AS ABC, then he is making four changes:

Collaboration is not quite as simple as sending these changes to the other editors because people get out of sync. Suppose as John is typing, Luiz (represented by yellow) begins to change his document to IT’S EASY AS 123. He first inserts the I and the T at the beginning of the document:

Suppose Luiz naively applies John’s first change {DeleteText @9-11}:

He deleted the wrong characters! Luiz had two characters at the beginning of the doc that John was never aware of. So the location of John’s change was wrong relative to Luiz’s version of the document. To avoid this problem, Luiz must transform John’s changes and make them relative to his local document. In this case, when Luiz receives changes from John he needs to know to shift the changes over by two characters to adjust for the IT that Luiz added. Once he does this transformation and applies John’s first change, he gets:

The algorithm that Google use to handle these shifts is called operational transformation (OT). If OT is implemented correctly, it guarantees that once all editors have received all changes, everyone will be looking at the same version of the document.
The OT logic in documents must handle all of the different ways that InsertText, DeleteText, and ApplyStyle changes can be paired and transformed against each other. The example above showed DeleteText being transformed against InsertText.
Collaboration in Google Docs consists of sending changes from one editor to the server, and then to the other editors. Each editor transforms incoming changes so that they make sense relative to the local version of the document. Google Docs can support up to 50 simultaneous editors, and documents let you see other people’s changes character-by-character as they type.
Source: Google Docs
Reads:1719
Comments (0)
Sep 29 2010
Posted: under Google Docs.
Tags: Algorithm behind Google Docs, Google Docs
