Pages

Try the processWave.org Diagram Editor now!

Use the processWave.org Editor in Google Wave (discontinued).

Watch the screencasts showing the editor in Google Wave or Google+ Hangouts.

Check out our MIT-licensed source code on GitHub.

February 4, 2010

syncro: Real collaboration in Google Wave gadgets

When Google Wave was first announced, excitement was high among developers. For the first time there would be a platform to enable real-time collaboration not only when editing text but also in all kinds of embedded applications. Google called them gadgets.

Disappointment ensued when it became obvious that the great collaborative text editing features were not available inside of gadgets. Instead Google provided a shared gadget state, a simple key-value storage that is kept in sync across all clients. While this model of a shared state is very easy to pick up, it does not lend itself to creating complex applications. Let's have a look at a simple example: Imagine we want to create a simple application that allows us to create shapes on a canvas and move them around.


The gadget state for this application could look like this:
"next_object_index" : "3"
"0": "{'type': 'rectangle', 'x': 128, 'y': 256}"
"1": "{'type': 'rectangle', 'x': 512, 'y': 0}"
"2": "{'type': 'circle', 'x': 256, 'y': 0}"
Each time a user wants to create a new shape, they insert a new key-value pair to the gadget state using the value of next_object_index as the key. Afterwards, the value of next_object_index has to be incremented. If the position of a shape changes, the user updates the according attributes in the key-value pair representing the object.

There is a problem to this approach widely known as "lost update": When two users create a shape at the same time, they are likely to do so using the same key. If this happens, the update from the user with higher latency will overwrite the other update. Similarly if a user with high latency changes the position of a shape, this update might reach the server with a high delay, causing another position update which actually happened afterwards to be overwritten.

To address this issue we could encapsulate each change to the model (e.g. shape creation, position change) in a single command object which is stored under a unique key in a unambiguous chronological order in the gadget state. This allows the commands to be applied after another so every client has the same view on the model state. This is a fairly common design pattern known as the command pattern. However, this raises two new problems:
1) How do we generate unique keys within the gadget?
2) How do we maintain a chronologically ascending order of commands which is the same on all participating clients without a central coordinator, i.e. in a distributed way?

Introducing syncro

We have written syncro, JavaScript library for Google Wave gadgets to solve these problems. Syncro provides an interface to a
command stack stored in the gadget state. The library ensures unambiguous chronological order of all commands pushed to this stack.

The interface to syncro is dead easy. The library has to be initialized with two callbacks:
syncro.initialize(initializeCallback, newCommandCallback);
The initializeCallback is executed when the gadget is loaded. It receives all commands on the command stack as a parameter in the order they must be applied in.
function initializeCallback(commands) { 
 for (var i = 0; i < commands.length; i++) {
  apply(commands[i]); 
 }
}
ThenewCommandCallback is executed every time a new command is pushed to the command stack. It receives three arguments: the new command, an array of commands that need to be reverted because of delayed updates as described in the example above and an array of the commands that have to be applied after reverting.
function newCommandCallback(newCommand, revertCommands, applyCommands) { 
 for (var i = 0; i < revertCommands.length; i++) {
  revert(revertCommands[i]); 
 } 
 for (var i = 0; i < applyCommands.length; i++) { 
  apply(applyCommands[i]); 
 } 
}
newCommand is always identical toapplyCommands[0] and just passed for convenience. Finally, you are able to push new commands to the command stack with the following function:
syncro.pushCommand(command);

Example

There is a little collaborative drag and drop gadget demonstrating the capabilities of syncro. You can use it as an entry point to start writing your own gadget with syncro. Try it out in our public syncro wave in the Wave Sandbox.
Gadget url: http://static.processwave.org/syncro/example/example.xml
Gadget installer url: http://static.processwave.org/syncro/example/syncro_example_installer.xml

Get the code

The library itself and the example are licensed under the terms of the MIT license. You can get it from our bitbucket repository: http://bitbucket.org/processwave/syncro

Known issues

Google currently limits the gadget state size to 100 kilobytes. If your Wave
crashes while using the provided example, the command stack may have exceeded the granted memory.

3 comments:

  1. I made something somewhat similar (but nowhere near as polished) in my Ajax Animator gadget. To circumvent the 100kb limit, you could remove the spaces in the JSON, take the quotes off the key names (when possible) and have a library of key names to shorten the content from, for example {'type':'rectangle'} to {t:'r'}, which is what I do in my system.

    ReplyDelete
  2. Why aren't you simply use vector clocks or matrix clocks?

    ReplyDelete
  3. @Anonymous: The idea described here is based on Lamport clocks, which are somewhat related to vector clocks.

    ReplyDelete

 
Web Statistics
Embed Wave to Blogger