5 ms·

Operational Transformation (algorithm behind Wave, Google Docs)

125 points by samstokes 16y ago

deleted 16y ago
[deleted]
billjings 16y ago
"...in light of the fact that Google’s documentation on the subject is sparing at best, I thought I would take some time to clarify this critical piece of the puzzle." Is Google's documentation crap?
- hammerdr 16y ago
  Just very broad: a series of white papers and a sample Java implementation which doesn't have any persistent storage. There is certainly space for someone to document the specifics of the Wave Protocol (and, along with that, operational transforms) and this blog post goes a long way toward that. Edit: I should also note that the OT white paper, like most white papers, builds on prior knowledge and expects some background in the area of research. You have to read a few white papers in order to really grok it.
  - Jd 16y ago
    There was a long blog series on OT not long after the Google Wave that is linked from the Wave docs: http://blog.wavenz.com/2009/07/introduction-to-operational.html http://blog.wavenz.com/2009/07/introduction-to-operational.h... http://blog.wavenz.com/2009/07/operational-transformation-algorithm.html http://blog.wavenz.com/2009/07/operational-transformation-al... http://blog.wavenz.com/2009/07/operational-transformation-and.html http://blog.wavenz.com/2009/07/operational-transformation-an... (full disclosure: I helped edit these)
adrenalin 16y ago
Hey thanks, have a school-project in progress (a google wave like project) that need OT, this article will help.
jerf 16y ago
I worked out the logic for a system like this for one of those "Someday I'd like to release this" projects. The way I looked at it is that basically it's just patch theory. It's the same problem you get with a source-control system, it's just happening faster. You can use the exact same patch theory. In fact I think patch theory may even be stronger than the algorithms described here. This link says "we need to impose a restriction on the client: we can never send more than one operation at a time to the server.", but patch theory can handle that case just fine and still "recover" later. The only thing you need is some sort of merge policy, and my plan was just to arbitrarily (but consistently) pick a side, because unlike a code merge where you could literally have kilobytes of conflict and discarding either side could be bad, in the collaborative case you're looking at a few small commands. (Even a large copy/paste is just one operation, from the human perspective. No matter how collaborative your editor, two people editing the same character is always going to be a problem; there's really no point trying to get too clever.) If you are interested in this topic, you might want to read http://en.wikibooks.org/wiki/Understanding_darcs/Patch_theory http://en.wikibooks.org/wiki/Understanding_darcs/Patch_theor... as well. I think patch theory may be stronger than what was described because it can use patch inverses to do a few things I'm not sure operational transformation" can, and coming up with inverses for the collaborative editing case is quite trivial. Note that darcs had a well-known exponential case, I think in the collaborative editor case it could never come up as everybody is always within a few seconds of "HEAD". (Incidentally, the patch approach would also potentially allow offline interaction as well, though then you can't ignore the merge issue quite so thoroughly and you could conceivably have exponential merges again, never got far enough to tell. Sounds like this approach would not allow that. Does Wave allow offline interaction which it then propagates up? If so then it may be using something more like patch theory.)
- mvaerle 16y ago
  I was also wondering about the difference between patch theory and this. I wonder if one of the reasons for operational transformation is that it is more feasible in semi-realtime environments, for example because transforming the operations is (computationally) easier than doing a merge on the data itself.
gritzko 16y ago
The present OT is very much an epicycle theory. They always have that one last issue to fix. In fact, several, if not the most of, classic OT papers were later found to be inconsistent, e.g. some combination of concurrent edits makes copies diverge (source: P. Molli). And that problems are extremely hard to find/understand. Apparently, the original authors of OT had a local network in mind: universal connectivity, instant message propagation, etc. But the internet is full of "relativistic" effects: different clients have different views of the state, messages propagate with finite/varying speed, etc etc. After reading the article, try to estimate what happens if e.g. one client syncs hourly/daily/monthly (like in the git), or suppose we don't have a central server (like in git), or if the stream of edits is too dense... like we really have a hundred of monkeys... Maybe Google engineers managed to get the probability of OT screw-ups lower than the probability of all other screw-ups... but that does not make the theory any better. (...and the way they dealt with XML is a very special song. OT is pretty much a complexity explosion itself, but they also multiplied it by the complexity of XML; got 15 kinds of mutation operations and all the stuff. The fact they invented "annotations" to skip XML nesting speaks for itself.) Conclusion. OT is a big messy mess.
saikat 16y ago
For people interested in the approaches to real-time collab, I made a summary writeup of what I researched a while back - http://techblog.gomockingbird.com/using-real-time-collaboration-to-help-solve-r http://techblog.gomockingbird.com/using-real-time-collaborat... . Still hoping to actually dive into all the algorithms later, but there is definitely a lot out there, just mostly in the form of academic papers.
mvaerle 16y ago
Make sure you watch this guy: http://www.youtube.com/watch?v=84zqbXUQIHc http://www.youtube.com/watch?v=84zqbXUQIHc (presentation at google). They developed a lot of systems using OT, even going so far as doing collaborative autocad. There are papers on that if you search for CoMaya and CoAutoCAD. The complexity, especially of the last one, is mind boggling though.

125 points by samstokes 16y ago

deleted 16y ago

[deleted]

"...in light of the fact that Google’s documentation on the subject is sparing at best, I thought I would take some time to clarify this critical piece of the puzzle." Is Google's documentation crap?

hammerdr 16y ago
Just very broad: a series of white papers and a sample Java implementation which doesn't have any persistent storage. There is certainly space for someone to document the specifics of the Wave Protocol (and, along with that, operational transforms) and this blog post goes a long way toward that. Edit: I should also note that the OT white paper, like most white papers, builds on prior knowledge and expects some background in the area of research. You have to read a few white papers in order to really grok it.
- Jd 16y ago
  There was a long blog series on OT not long after the Google Wave that is linked from the Wave docs: http://blog.wavenz.com/2009/07/introduction-to-operational.html http://blog.wavenz.com/2009/07/introduction-to-operational.h... http://blog.wavenz.com/2009/07/operational-transformation-algorithm.html http://blog.wavenz.com/2009/07/operational-transformation-al... http://blog.wavenz.com/2009/07/operational-transformation-and.html http://blog.wavenz.com/2009/07/operational-transformation-an... (full disclosure: I helped edit these)

adrenalin 16y ago

Hey thanks, have a school-project in progress (a google wave like project) that need OT, this article will help.

jerf 16y ago

I worked out the logic for a system like this for one of those "Someday I'd like to release this" projects. The way I looked at it is that basically it's just patch theory. It's the same problem you get with a source-control system, it's just happening faster. You can use the exact same patch theory. In fact I think patch theory may even be stronger than the algorithms described here. This link says "we need to impose a restriction on the client: we can never send more than one operation at a time to the server.", but patch theory can handle that case just fine and still "recover" later. The only thing you need is some sort of merge policy, and my plan was just to arbitrarily (but consistently) pick a side, because unlike a code merge where you could literally have kilobytes of conflict and discarding either side could be bad, in the collaborative case you're looking at a few small commands. (Even a large copy/paste is just one operation, from the human perspective. No matter how collaborative your editor, two people editing the same character is always going to be a problem; there's really no point trying to get too clever.) If you are interested in this topic, you might want to read http://en.wikibooks.org/wiki/Understanding_darcs/Patch_theory http://en.wikibooks.org/wiki/Understanding_darcs/Patch_theor... as well. I think patch theory may be stronger than what was described because it can use patch inverses to do a few things I'm not sure operational transformation" can, and coming up with inverses for the collaborative editing case is quite trivial. Note that darcs had a well-known exponential case, I think in the collaborative editor case it could never come up as everybody is always within a few seconds of "HEAD". (Incidentally, the patch approach would also potentially allow offline interaction as well, though then you can't ignore the merge issue quite so thoroughly and you could conceivably have exponential merges again, never got far enough to tell. Sounds like this approach would not allow that. Does Wave allow offline interaction which it then propagates up? If so then it may be using something more like patch theory.)

mvaerle 16y ago
I was also wondering about the difference between patch theory and this. I wonder if one of the reasons for operational transformation is that it is more feasible in semi-realtime environments, for example because transforming the operations is (computationally) easier than doing a merge on the data itself.

gritzko 16y ago

The present OT is very much an epicycle theory. They always have that one last issue to fix. In fact, several, if not the most of, classic OT papers were later found to be inconsistent, e.g. some combination of concurrent edits makes copies diverge (source: P. Molli). And that problems are extremely hard to find/understand. Apparently, the original authors of OT had a local network in mind: universal connectivity, instant message propagation, etc. But the internet is full of "relativistic" effects: different clients have different views of the state, messages propagate with finite/varying speed, etc etc. After reading the article, try to estimate what happens if e.g. one client syncs hourly/daily/monthly (like in the git), or suppose we don't have a central server (like in git), or if the stream of edits is too dense... like we really have a hundred of monkeys... Maybe Google engineers managed to get the probability of OT screw-ups lower than the probability of all other screw-ups... but that does not make the theory any better. (...and the way they dealt with XML is a very special song. OT is pretty much a complexity explosion itself, but they also multiplied it by the complexity of XML; got 15 kinds of mutation operations and all the stuff. The fact they invented "annotations" to skip XML nesting speaks for itself.) Conclusion. OT is a big messy mess.

saikat 16y ago

For people interested in the approaches to real-time collab, I made a summary writeup of what I researched a while back - http://techblog.gomockingbird.com/using-real-time-collaboration-to-help-solve-r http://techblog.gomockingbird.com/using-real-time-collaborat... . Still hoping to actually dive into all the algorithms later, but there is definitely a lot out there, just mostly in the form of academic papers.

mvaerle 16y ago

Make sure you watch this guy: http://www.youtube.com/watch?v=84zqbXUQIHc http://www.youtube.com/watch?v=84zqbXUQIHc (presentation at google). They developed a lot of systems using OT, even going so far as doing collaborative autocad. There are papers on that if you search for CoMaya and CoAutoCAD. The complexity, especially of the last one, is mind boggling though.