The correct way to merge John’s style change and Luiz’s text substitution is as
The quick brown dog. But Luiz doesn’t have enough information to know what the correct merge is. From his perspective,
The quick brown fox dog, The quick brown dog, The quick brown dog fox are all perfectly valid ways of merging the two versions. And that’s the problem: if you just compare versions, you can’t make sure that changes are merged in the way that an editor would expect.
You can avoid the merging problem by introducing more restrictions on the editors. For example, you could lock paragraphs so that only one editor was ever allowed to type in a single paragraph at a given time. But locking paragraphs isn’t a great solution: you’re sidestepping the technical challenges by hampering the collaborative editing experience. Plus, it’s always possible for two editors to begin editing a paragraph at the same time. In that case, one of the editors will find out that he didn’t actually acquire the paragraph lock and any changes that he made while he thought he had the lock will need to be merged (which has all of the above problems) or discarded.
The new version of Google documents does things differently. In the new editor, a document is stored as a series of chronological changes. A change might be something like
{InsertText 'T' @10}. That particular change was to insert the letter
T at the 10th position in the document. A fundamental difference between the new editor and the old one is that instead of computing the changes by comparing document versions, we now compute the
versions by playing forward the history of changes.
This approach creates a better collaboration experience, because the editors’ intentions are never ambiguous. Since we know the revision of each change, we can check what the editor saw when he made that change and we can figure out how to correctly merge that change with any changes that were made since then.
That’s it for today. Tomorrow’s post will give an overview of the algorithm for merging changes —
operational transformation. Even if we know
how to properly merge changes, we still need to make sure that each editor knows
when there are changes that need to be merged. This challenge is handled by the
collaboration protocol which will be the subject of Thursday’s post. Together, these technologies create the character-by-character collaboration in Google Docs.
Posted by: John Day-Richter, Software Engineer
