How one small team solved the big problem of version control

When Google launched Docs in 2012, the problem of emailing iterations of the same evolving document back and forth was solved. It was the Docs killer feature. You and your classmate could finally edit the same group assignment at the same time. Version control was a thing of the past. At least for the user. Version control was now Google’s problem. So how do you solve it?

From email iterations to real-time collaboration

In 2010, John was a software engineer working on infrastructure in Google’s Boulder office. "I wrote programs so Googlers could see how many resources their services were using." It was at an office-wide meeting where Googlers shared all the different things they were working on that John noticed in a footnote a mention that folks in the New York office were trying to make real-time collaboration work in document editing.

There were eight of us collaborating in different capacities, and at no point was anyone territorial.

So John contacted the team and spoke with his manager and started working on the effort as a 20% project—using a fifth of his time to work on a project outside his core role. "There were eight of us collaborating in different capacities, and at no point was anyone territorial." What started as a side project quickly became John’s full-time job.

Apply "mutations" to the doc based on specified coordinates
So, how do you let multiple people edit a doc without imposing unacceptable constraints? "We knew Stanford had published a paper on this theoretical model for reconciling changes to a single source of truth and Google Wave had built some cool functionality like this," John explains. And there were already a few ideas out there.

One simple way of doing it is to simply lock the document while one editor is making changes, freezing out all other collaborators. But this prohibits truly real-time collaboration and knowing when to lock and unlock the doc is really difficult.

Another way to do it is to try to approve every single keystroke as people are typing. This means having the server check, verify, and then publish every single letter as each contributor types. This starts to break down quickly as soon as you have more than one person typing at a normal rate.

Instead, the team—spread across New York, Boulder, Mountain View, and Sydney—developed a way to apply changes, or "mutations," to the document based on specified coordinates within the doc without having to rescan the doc for every single mutation.

There’s a problem in real-time collaboration where ordering matters. If we both insert something at the same point, who wins? How do you resolve it? We decided whoever got there last was the winner.

And the logic that goes about resolving that winner is an elegant transformer function that prioritizes incoming changes against already applied changes, then applies the transformed version. It looks like this, where T is the transformer function, and P & Q are edits.

The transformer function not only runs on the server, but also runs client-side, transforming incoming edits if the user is holding pending changes that haven't been transmitted to the server, like when you have a flaky network connection.

But even with an algorithmic solution to an intractable problem, how do you implement it in production? There was no way to run the same code everywhere—servers run Java while the web is JavaScript.

Java vs JavaScript

The team turned to a recently built developer tool called the Google Web Toolkit, or "GWT." GWT (pronounced "guh-wit") is an open source set of programs for building and optimizing complex JavaScript front-end applications in Java. At that time, no one at Google had tried using GWT to share business logic between server code and native JavaScript client code.

Once it compiled the binary was huge—twice the size of the rest of the project code. What was causing it to balloon? "We figured out that Google's own libraries were calling and referring to tons of other libraries, none of which we were actually using. Normally a compiler would take care of that kind of problem, but the GWT compiler wasn't able to do this kind of dead code removal at the time. So we had to rewrite huge chunks of the code and explicitly block those standard libraries in our build scripts."

There are no sacred cows at Google. If the best solution involves rewriting server code, or even building a server from scratch, we'll do it.

But to get the exact same code to run in the browser as on the server, which this implementation of real-time collaboration required, meant they needed to rewrite some of the core code running Google's actual servers. "There are no sacred cows at Google. If the best solution involves rewriting server code, or even building a server from scratch, we'll do it."

Time to put it to the test

And so with a working prototype, the team brought it to the group’s director for a live demo. "I remember the first time our director and manager were testing it out and editing the same doc at the same time. They started making fun of each other in the doc, deleting each other's edits, writing jokes and insults and I'm there sweating bullets worried that something would break!"

It didn't break, and the real-time collaboration engine the team built was generalized and now powers similar functionality not only in Docs, but in Google's entire Apps suite as well as countless apps from third-party developers using the Google Drive Realtime API.

Since launching, millions of users have collaborated in Docs on book reports, wedding vows, movie scripts, and more. The Google team has added the ability to work on documents offline and then have edits re-sync when you’re back online. And now people can collaborate on the same doc at the same time from desktops, tablets, and phones.

There are so many unsolved challenges. We've still got so much work to do.

But there are still lots of tough problems that require new solutions. Like, how do you allow for collaborative editing of directed acyclic graphs without leaving a lot of garbage in the model? How can you reorder file trees while users are accessing content? Or what about managing multi-user interactions on complex objects, like HTML tables? "There are so many unsolved challenges. We’ve still got so much work to do."

John is a Software Engineer on the Google Apps team, serving as the Apps Developer Platform team technical lead.