Handling asynchronous edits of documents on the web

Question

I am writing a Web application that has a user interface for editing data. The idea is something similar to a wiki where there are edits to chunks of text. What is the best way to handle asynchronous edits from multiple users? The situation I am considering is this:

There is a document that is version 0. User A is editing it when it is version 0. A few minutes later but before user A saves his changes, user B opens up the same document and starts editing. How should the server treat the two different edits to version 0 of the document? Also what is this problem called and where can I get more information about similar problems?

Answer 1

One typical pattern is to send each user a chunk of text and also a version number indicating which version they received. The rule is that the host will only accept the first revision to the currently activer version.

That way only one person can revise each version; everyone else would be told that their version was obsolete and you can do what you want for them at that point - usually send them the current version to retry.

This only works if it's unlikely to have multiple people working on the same version. If that's likely, then you probably need to research how subversion for instance handles multiple revisions to source code.

There are also schemes for multiple people working simultaneously on the same text and being feed each others' updates - see Google Wave for one example.

Answer 2

Wikipedia addresses this problem in the following way:

Assume that person A and person B are both editing the same document. Also assume person A submits their edits slightly before person B.

• First the media wiki software runs a traditional diffing algorithm over both edits.
• Next, the results of the diffing algorithm are used to merge the text.
• If the diffing algorithm finds that there are merge conflicts (i.e. person A and B edited the same piece of text), then person B is asked to resolve the conflicts since they submitted their edits last.

Wikipedia handles merge conflicts much like conflicts in a code repository.

If you want to allow multiple people to edit a document simultaneously and in real-time (like with google wave or etherpad), then I'd recommend looking into operational transforms (aka OT). Though the OT algorithm is no harder or simpler than a traditional diffing algorithm, there is less information on it and fewer ready-made implementations.