The web applications I’ve been involved with over the last year or two have tended towards being richer, with more real-time interactions, and more collaboration. The mechanics of building collaborative applications aren’t so tough, but eventually you run into the problem of what to do with text. But good news: there are some smart algorithms to help you out, which you can implement in a couple of hundred lines of code.
Let’s look at a real-world scenario. In November, The Huffington Post published a Sneak Peek: HuffPost Brings Real Time Collaboration to the Newsroom. Have a look at the article, or watch the short video, and you’ll notice that they solved the problem of safely collaborating on text with exclusive locking. By that I mean, one person edits, then they give up control for someone else to edit.
I have no connection or inside knowledge on their project, so I don’t know if that’s a compromise or a great fit to their workflow. It’s a totally fine solution, as you don’t risk ending up with corrupt copy, which in my mind is a primary concern.
But how would you like to support collaborative text editing in that kind of environment? Tools like Google Docs have, perhaps, led us to expect truly collaborative real time editing that just does the right thing with edits.
To understand what’s involved you need to recognise that “sharing a document” really means each collaborator is working on their own copy, stored in their browser. As edits happen, and are broadcast across the network, each copy is diverging. You need an algorithm to safely converge those documents after each change.
The answer is to use a CRDT—conflict-free replicated datatype.
Noel has explained that CRDTs are data structures designed to combine together when you have no control over the order of changes, timing of changes, or the number of participants. What that means is, if you delete a character or add a character, when that change is represented as a CRDT you know it will do two things: successfully combine everywhere; and consistently combine, so everyone ends up in the same state (with the same text, in our case).
To explore this we implemented the WOOT algorithm in Scala and JavaScript. WOOT is a CRDT applied to text editing, and was published from INRIA in 2005. You can see how it works in the video of the talk I gave at Scala eXchange 2013. Or flip through the slide deck.
Most people have no idea these kinds of algorithms are working hard behind the scenes. The benefit from all of this is, of course, for end users who can just get on to do whatever they need to do.