Collaboration: Theory and Practice

My first attempt at creating a wave gadget is a reorderable task list. Here is an embedded version of the gadget running in the emulator.

As I started the implementation, I realized that there are certain difficulties with gadget state management with regard to Wave’s real-time concurrency. Here is an attempt to recreate the learning process I went through, with the difficulties I encountered and solutions I put in place to make this gadget work.

• This is just a preliminary version of the gadget – I am still tweaking the user interaction so that concurrency is completely flawless.
• I do not have access to the real Wave sandbox. All my development is done using the gadget emulator. As far as I know, this does not work on the real Wave server (but it’s probably a small fix if I could debug it)
• This is long and technical. Think of it as a guided discussion.

Background

Gadget states consist of a set of key-value pairs (like a hash table, associative array or Javascript object). It is important to note that as opposed to Javascript objects, gadget state values are always strings (and not arrays or other objects). If you want to see what some gadget states look like, try the gadget emulator – it shows the gadget state besides the gadget itself. If you take a look around, you will see a whole assortment of hacks to manage gadget state even though it only allows strings as values. When I asked in the google group about this, I was suggested to JSON encode any objects or arrays I want to store and use that string as the value in the state.

JSON encoding objects and arrays into strings is a hack, but that’s not the real problem. The issue is how that works with the way gadgets modify their state. In the gadget API reference you will find that gadgets modify their state by submitting a delta. A delta is just another set of key-value pairs that state which keys to modify, and which new value to give them. If a null value is submitted then that key is removed from the gadget state.

Approach #1

Let’s start by trying to implement a simple task list without reorderability. We have to think of our gadget state scheme. How about using the idea to store the array of tasks by JSON encoding it? Then the state will look something like this:

tasks: “['Go to store', 'Clean home', 'Finish blog post']“

Seems simple enough. Let’s imagine two people working on the same gadget instance and trying to add a new task at the same time. Participant #1 submits the following delta:

tasks: “['Go to store', 'Clean home', 'Finish blog post', 'Go to sleep']“

while participant #2 submits:

tasks: “['Go to store', 'Clean home', 'Finish blog post', 'Check xkcd']“

In effect, the Wave server will receive one of the deltas followed by the other, which means the end result will be whichever delta was applied by the server last. One of the new tasks will necessarily not appear (although it will be visible in the gadget history right before it got erased). And actually, no concurrent modifications will ever work with this scheme.  Can we find a different approach that will not have this problem?

Approach #2

We can try to put the different tasks in separate keys of the state, for example:

task_1: ‘Go to store’
task_2: ‘Clean home’
task_3: ‘Finish blog post’

This approach will allow modification of specific tasks to work in a concurrent fashion, but adding a new task will have the same problem as approach #1.

Approach #3

The problem with approach #2 is that two participants will try to modify the same key when they each add a new task. If we want to solve this, we need to make sure that the key sent by both participants is different. Each participant has a unique participant id which is accessible from the gadget API. Let’s augment the keys with the participant id who added them. So, the initial state will look something like this (assuming the two participant id’s are 722931 and 199882):

task_1_722931: ‘Go to store’
task_2_199882: ‘Clean home’
task_3_722931: ‘Finish blog post’

Now, the two deltas being submitted for the addition of the fourth task would be:

task_4_722931: ‘Go to sleep’

and

task_4_199882: ‘Check xkcd’

Which means the gadget state after both deltas were submitted would be:

task_1_722931: ‘Go to store’
task_2_199882: ‘Clean home’
task_3_722931: ‘Finish blog post’
task_4_722931: ‘Go to sleep’
task_4_199882: ‘Check xkcd’

That has the slight weirdness of having two task_4_* keys but there’s no need for the UI to expose that in any way, so concurrent modifications worked as far as the user is concerned (which is the only thing that really matters).

But, actually, there is a problem with this approach – it would fail if the same user is trying to modify the gadget from two different computers. But that can be easily amended, by using a randomly generated code instead of the participant id. If we use, let’s say, 96 possible characters with a code length of 6 characters, we can reach over 700 million options for each code. That basically means you’ll never have any concurrency problems. And if you did, it will probably never happen again to you (remember, this could only even perhaps cause an issue if two people are adding a new task at the same time anyways.)

Approach #4

Let’s take on reorderability now. If we take the gadget state after the two new tasks were added, now we want to move ‘Finish blog post’ to come right before ‘Clean home’. What delta would have to be submitted? The following delta seems like it may work:

task_2_199882: ‘Finish blog post’
task_3_722931: ‘Clean home’

Let’s see what happens if we would use this scheme and another user tries to move ‘Clean home’ to come before ‘Go to store’ with the following delta:

task_1_722931: ‘Clean home’
task_2_199882: ‘Go to store’

If the two deltas are submitted at once and the first gets applied before the second, we get the following gadget state:

task_1_722931: ‘Clean home’
task_2_199882: ‘Finish blog post’
task_3_722931: ‘Clean home’
task_4_722931: ‘Go to sleep’
task_4_199882: ‘Check xkcd’

Oh no! Clean home appears twice and Go to store disappeared!

If you are following this discussion and you find it interesting, now is probably a good time to stop reading, grab a piece of paper and a pen (or a chalkboard if you have one around) and  try to find a solution for these concurrent reordering issues. Take into account that the scheme should also allow for modification or removal of a task at the same time as it is being moved around. Also, how would we be able to move ‘Finish blog post’ to go between ‘Go to sleep’ and ‘Check xkcd’? They are both “task_4″!

Solution

Let me start by saying that this is the solution I came up with and the paradigm used in my implementation. If you think of other possible solutions, I’d love to hear about them. They may be better than mine.

The main observation is that since any two deltas may interfere with each other if they touch the same attributes, we must ensure that the attributes modified properly represent the action taken by the user. For example, the last example of a possible delta to represent moving ‘Clean home’ to come before ‘Go to store’ contains two attributes, even though the user only acted on ‘Clean home’. It’s good to try to put it in words. The delta submitted means “Put ‘Clean home’ at position 1 and ‘Go to store’ at position 2″ when our scheme should allow for a delta that means “Put ‘Clean home’ before ‘Go to store’”. Also, if possible we should be able to allow for one user to modify the text on a task at the same time as it is being moved. That means that we must ensure that attributes in a delta modifying the position of a task do not conflict with the attributes in a delta modifying the text of a task. And in general, it is a good idea to be able to represent user actions as modifying one attribute only. This gives the best chance that concurrent modifications won’t conflict.

The solution has two attributes for each task – one for the text and one for the position. Each task would have to get a random id generated. Here is a sample gadget state in our scheme (remember that only strings are allowed as values):

task_826721_text: ‘Go to store’
task_826721_position: ‘1′
task_612229_text: ‘Clean home’
task_612229_position: ‘2′
task_172034_text: ‘Finish blog post’
task_172034_position: ‘3′

Modifying the text of a task would submit a delta only modifying the _text attribute. In order to move ‘Clean home’ to come before ‘Go to store’ we submit the following delta:

task_612229_position: ‘0′

In order to move ‘Go to store’ to come after ‘Clean home’ (which may seem like the same operation but is not – think what would happen if someone else moves ‘Finish blog post’ at the same time) we submit the following delta:

task_826721_position: ‘2.5′

This means that positions must now be floating point numbers. Try to apply those two deltas and see what gadget state we reach. Think what would happen if someone else moves ‘Finish blog post’ at the same time.

There are just two minor issues. First of all, two people might move two different items to position 2.5. This on its own is not necessarily an issue but then one wouldn’t be able to put something between those two positions (it would also need to be position 2.5 but then there is no way to ensure that it is between the two). In order to solve this, instead of using the average of the two positions you are placing between we use a random number in that range (with a certain predefined precision.) Secondly, Floating point numbers have bounded precision, which means that at some point if a list is reordered a lot, the scheme will stop working. In order to solve this, we used a library for arbitrary precision floating point numbers, which are encoded in base-64.

Epilogue

Thank you for joining us for this lengthy exploration. Please let me know what you think of this form of presentation, as it is my first attempt of this kind. As for the gadget state paradigm, I realize that this is way too difficult to be implemented for each gadget separately, and I would like for gadgets to work with perfect concurrency. Therefore, once I have some more free time, I’ll start working on a framework that hides all these technicalities from the gadget developer.