Free Online Storage

  • Subscribe to our RSS feed.
  • Twitter
  • StumbleUpon
  • Reddit
  • Facebook
  • Digg

Thursday, 23 September 2010

What’s different about the new Google Docs: Making collaboration fast

Posted on 09:42 by Unknown
This is the final post in a three part series about the collaboration technology in Google Docs. On Tuesday, we explained some of the technical challenges behind real time collaboration. Yesterday, we showed how operational transformation can be used merge editors’ changes.

Imagine that you’re doing a jigsaw puzzle with a bunch of friends and that everyone is working in the same corner of the puzzle. It’s possible to solve a puzzle like this, but it’s hard to keep out of each other’s way and to make sure that when multiple pieces are added at once, that they all fit together perfectly. Making a document collaborative is a little like that: one challenge is coming up with a method to let multiple people edit in the same area without conflicting edits. A second problem is to ensure that when many changes happen at the same time, each change is merged properly with each other changes. In Google Docs, the first problem is handled by operational transformation and the second problem is handled by the collaboration protocol, which is the subject of this post.

To open a Google document, you need code running in two places: your browser and our servers. We call the code that’s running in your browser a client. In the document editor, the client processes all your edits, sends them to the server, and processes other editors’ changes when it receives them from the server.

To collaborate in Google Docs, each client keeps track of four pieces of information:
  1. The number of the most recent revision sent from the server to the client.
  2. Any changes that have been made locally and not yet sent to the server.
  3. Any changes that have been made locally, sent to the server, but not yet acknowledged by the server.
  4. The current state of the document as seen by that particular editor.
The server remembers three things:
  1. The list of all changes that it has received but not yet processed.
  2. The complete history of all processed changes (called the revision log)./li>
  3. The current state of the document as of the last processed change./li>
By carefully making use of this information, it’s possible to design the client-server communication such that all editors are capable of rapidly processing each other’s changes in real time. Let’s walk through a straightforward example of how client-server communication is handled in a document.

In the diagrams below, the two outer columns represent the editors: Luiz and John. The middle column is the server. The oval shapes represent changes inputted by the editors and sent between the clients and the server. The diamonds represent transformations.

Let’s say Luiz starts by typing the word Hello at the beginning of the document.


Luiz’s client added the edit to his list of pending changes. He then sent the change to the server and moved the change into his list of sent changes.

Luiz continues to type, adding the word world to his document. At the same time, John types an ! in his empty version of the document (remember he has not yet received Luiz’s first change).


Luiz’s {InsertText ' world' @6} change was placed in the pending list and wasn’t sent to the server because we never send more than one pending change at a time. Until Luiz recieves an acknowledgement of his first change, his client will keep all new changes in the pending list. Also notice that the server stored Luiz’s first change in its revision log. Next, the server will send John a message containing Luiz’s first change and it will send Luiz a message acknowledging that it has processed that first change.


John received Luiz’s edit from the server and used operational transformation (OT) to transform it against his pending {InsertText '!' @1} change. The result of the transformation was to shift the location of John’s pending change by 5 to make room at the beginning of the document for Luiz’s Hello. Notice that both Luiz and John updated their last synced revision numbers to 1 when they received the messages from the server. Lastly, when Luiz received the acknowledgement of his first change, he removed that first change from the list of sent changes.

Next, both Luiz and John are going to send their unsent changes to the server.


The server got Luiz’s change before John’s so it processed that change first. An acknowledgement of the change was sent to Luiz. The change itself was sent to John, where his client transformed it against his still pending {InsertText '!' @1} change.

What comes next is important. The server received John’s pending change, a change that John believes should be Revision 2. But the server has already committed a Revision 2 to the revision log. The server will use OT to transform John’s change so that it can be stored as Revision 3.


The first thing the server did, was to transform John’s sent change against all the changes that have been committed since the last time John synced with the server. In this case, it transformed John’s change against Luiz’s {InsertText ' world' @6}. The result shifted the index of John’s change over by 6. This shift is identical to the transformation John’s client made when it first received Luiz’s {InsertText 'Hello' @1}.

The example above ends with Luiz and John receiving John’s change and the acknowledgement of that change respectively. At this point the server and both editors are looking at the same document — Hello world!.

The main advantages of this collaboration protocol are:
  1. Collaboration is fast. At all times, every editor can optimistically apply their own changes locally without waiting for the server to acknowledge those changes. This means that the speed or reliability of your network connection doesn’t influence how fast you can type.

  2. Collaboration is accurate. There is always enough information for each client to merge collaborators’ changes in the same deterministic way.

  3. Collaboration is efficient. The information that is sent over the network is always the bare minimum needed to describe what changed.

  4. Collaboration complexity is constant. The server does not need to know anything about the state of each client. Therefore, the complexity of processing changes does not increase as you add more editors.

  5. Collaboration is distributed. Only the server needs to be aware of the document’s history and only the clients need to be aware of uncommitted changes. This division spreads the workload required to support real time collaboration between all the parties involved.
When we switched to the new document editor, we moved from a very simple collaboration algorithm based on comparing versions to a much more sophisticated algorithm powered by operational transformation and the protocol described above. The results are dramatic: there are no more collaboration conflicts and editors can see each other’s changes as they happen, character-by-character.

Well that’s all folks: we hope by reading this series you learned a bit more about what’s under the hood in Google Docs, and the kinds of things you need to think about to make a fast collaboration experience. You can try collaboration yourself, without signing in, by visiting the Google Docs demo.

Posted by: John Day-Richter, Software Engineer
Email ThisBlogThis!Share to XShare to Facebook
Posted in documents, Google Apps Blog | No comments
Newer Post Older Post Home

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Popular Posts

  • More Google Experiments That Hide Results URLs
    There are at least two other versions of the Google experiment that removes search results URLs . The first alternate version places site na...
  • Add a Keyboard Shortcut for Chrome's App Launcher
    I'm not sure why Chrome's app launcher doesn't have a keyboard shortcut, but it's pretty easy to add one. For Windows XP, r...
  • Merge cells vertically in Google spreadsheets
    There are many times when you want to format your spreadsheets in a certain way to make your data easier to read and understand. Starting to...
  • Docs on the iPhone with Chris Pirillo
    Posted by: Meredith Whittaker, Program Manager Chris Pirillo , Gnomedex Conference founder, CNN.com Live technology contributor, and one of ...
  • Writing a campaign speech with Google Docs
    A few months ago, my colleague Julia and I were at a technology conference for educators. Teachers were very enthusiastic when we demonstrat...
  • Google Now for Google's Homepage in Testing
    It looks like Google Now won't be limited to Android, iOS and Chrome , it will also be added to Google's homepage. Some code from a...
  • Google spreadsheets, now with discussions
    Getting things done with others would be much easier if everyone was sitting right next to you. But since that’s rarely the case, we’re alwa...
  • Collect audience input with Google Sites & Moderator
    Google Moderator helps anyone find the best input from their audiences, whether it’s suggestions on how to stop the oil spill , debate que...
  • Get Docs in 38 languages
    Posted by: Ken Norton, Product Manager, Google Docs Earlier today we launched Google Docs in 13 more languages, bringing our total number of...
  • View .doc attachments right in your browser
    Cross posted on the Gmail blog If you receive Microsoft® Word files as attachments in Gmail, you can now view them with a single click -- no...

Categories

  • Acquisitions
  • Ads
  • Android
  • Annoyances
  • April Fools Day
  • attachments
  • back to school
  • Blogger
  • charts
  • chat
  • Chrome
  • Chrome extensions
  • chrome web apps
  • Cloud Connect
  • collaboration
  • comments
  • community
  • discussions
  • DMCA
  • docs
  • document list
  • documents
  • documents list
  • drawings
  • drivebacktoschool
  • Easter Egg
  • education
  • Faces of Docs
  • forms
  • gmail
  • gone google
  • Google Alerts
  • Google Analytics
  • Google Apps Blog
  • Google Apps Script
  • Google Calendar
  • Google Cast
  • Google Checkout
  • Google Chrome
  • Google Chrome OS
  • Google Cloud Connect
  • Google Contacts
  • Google Dictionary
  • Google Docs
  • Google Docs Viewer
  • google documents
  • google drive
  • Google Earth
  • Google Goggles
  • Google Hangouts
  • Google Instant
  • Google Keep
  • Google Latitude
  • Google Local
  • Google Maps
  • Google Music
  • Google News
  • Google Notebook
  • Google Now
  • Google Pack
  • Google Photos
  • Google Play
  • Google Plus
  • Google Reader
  • Google Sites
  • Google Suggest
  • Google Takeout
  • Google Talk
  • Google Toolbar
  • Google Translate
  • Google Trends
  • Google Voice
  • Google Wallet
  • Google+
  • googlenew
  • Greasemonkey
  • Guest Post
  • holiday
  • iGoogle
  • Image Search
  • images
  • InOut
  • iOS
  • Keep
  • Knowledge
  • mobile
  • OCR
  • offline
  • OneBox
  • paperless
  • pdfs
  • photo
  • photos
  • Picasa Web Albums
  • presentations
  • product ideas
  • profiles
  • quickoffice
  • Reddit
  • research
  • save to drive
  • scripts
  • Security
  • sharing
  • sheets
  • shortcut
  • slides
  • spell check
  • spreadsheets
  • stock photos
  • storage
  • students
  • tables
  • teachers
  • templates
  • Tips
  • User interface
  • videos
  • Viewer
  • Visualization
  • Voice Search
  • Web Search
  • Yahoo
  • YouTube

Blog Archive

  • ►  2013 (519)
    • ►  December (33)
    • ►  November (44)
    • ►  October (64)
    • ►  September (50)
    • ►  August (63)
    • ►  July (60)
    • ►  June (57)
    • ►  May (62)
    • ►  April (49)
    • ►  March (33)
    • ►  February (1)
    • ►  January (3)
  • ►  2012 (34)
    • ►  December (4)
    • ►  November (4)
    • ►  October (5)
    • ►  September (4)
    • ►  August (2)
    • ►  July (1)
    • ►  June (3)
    • ►  May (2)
    • ►  April (2)
    • ►  March (2)
    • ►  February (5)
  • ►  2011 (80)
    • ►  December (4)
    • ►  November (1)
    • ►  October (7)
    • ►  September (10)
    • ►  August (11)
    • ►  July (8)
    • ►  June (9)
    • ►  May (1)
    • ►  April (8)
    • ►  March (8)
    • ►  February (8)
    • ►  January (5)
  • ▼  2010 (118)
    • ►  December (11)
    • ►  November (16)
    • ►  October (6)
    • ▼  September (13)
      • Keyboard shortcuts in Google Sites
      • More tools for viewing document revisions
      • Import your files many different ways
      • What’s different about the new Google Docs: Making...
      • What’s different about the new Google Docs: Confli...
      • A more fontastic Google Docs
      • What’s different about the new Google Docs: Workin...
      • Print your spreadsheets (and save ink) with more p...
      • Back to School with Google forms
      • Learn about Google Docs
      • Easier site organization with drag and drop
      • Trimming our privacy policies
      • Drawing out ideas in documents
    • ►  August (13)
    • ►  July (7)
    • ►  June (15)
    • ►  May (11)
    • ►  April (7)
    • ►  March (7)
    • ►  February (6)
    • ►  January (6)
  • ►  2009 (82)
    • ►  December (14)
    • ►  November (4)
    • ►  October (10)
    • ►  September (10)
    • ►  August (4)
    • ►  July (6)
    • ►  June (6)
    • ►  May (5)
    • ►  April (4)
    • ►  March (8)
    • ►  February (7)
    • ►  January (4)
  • ►  2008 (97)
    • ►  December (6)
    • ►  November (4)
    • ►  October (6)
    • ►  September (8)
    • ►  August (5)
    • ►  July (7)
    • ►  June (11)
    • ►  May (20)
    • ►  April (13)
    • ►  March (6)
    • ►  February (6)
    • ►  January (5)
  • ►  2007 (25)
    • ►  December (1)
    • ►  November (1)
    • ►  October (2)
    • ►  September (3)
    • ►  August (3)
    • ►  July (4)
    • ►  June (3)
    • ►  May (2)
    • ►  April (2)
    • ►  March (1)
    • ►  February (2)
    • ►  January (1)
  • ►  2006 (10)
    • ►  December (2)
    • ►  November (4)
    • ►  October (4)
Powered by Blogger.

About Me

Unknown
View my complete profile