Replication insight

Tonight I had the most beautiful insight into distributed revision management. Originally the CouchDb revision conflict management consisted of maintaining a linear list of revisions ids, such that every time a document is edited it generates a revision id that is added to the revision list. To detect conflicts in edits, it is simple enough to check if one document's revision list is a subset of another. If not, there's a conflict.

The problem is when a conflict is detected, what to do? If you want to just deterministically declare one a winner and jettison the loser then the problem is simple. However if you wish to preserve the losing conflict information so that it might be resolved later it becomes a much more difficult problem, the edge cases in a peer distributed model make it difficult. One approach is to deterministically generate a new conflict document, preserving the losing conflict information but now as a new and separate document. This is the approach Notes/Domino replication takes and it works ok in some applications, but it can cause problems.

What I realized tonight is that by converting the revision lists to a tree, then conflicts are simple tree merges (conflicts in the revisions lists becomes branches in the revision tree) and then by using a simple algorithm for deterministically selecting the winning leaf node, it makes distributed and deterministic conflict resolution and merging possible while still providing single document semantics. No separate document is necessary to preserve losing conflict data and all the edge cases work. I'm glossing over lots of details, but thankfully little existing CouchDb code needs to change to make this happen.

I know I'm still not explaining CouchDb in people terms (more like barely intelligible dorkinese), but this is stuff that has very real impact on how well it "just works" in the real world. I had to tell someone.

Posted November 8, 2006 12:33 AM