Figure 4-1: Conflict Management by Example
Suppose you are sitting in a coffee shop working on your book. Chris comes over and tells you about his new phone. The new phone came with a new number and you have Chris dictate it while you change it using your laptop’s address book application.
Luckily, your address book is built on CouchDB; so when you come home, all you need to do to get your home computer up to date with Chris’s number is replicate your address book from your laptop. Neat, eh? What’s more, CouchDB has a mechanism to maintain continuous replication, so you can keep a whole set of computers in sync with the same data, whenever a network connection is available.
Let’s change the scenario a little bit. Chris didn’t anticipate meeting you at the coffee shop and sent you a mail with the new number. You weren’t using the WiFi so you could concentrate on your work. You didn’t read his email until getting back home and meanwhile, it was a long day, you have long forgotten that you changed the number in the address book on your laptop. You read the email, however, when getting back home and you simply copy & paste the number into your address book on your home computer. Now, and here is the twist, you copied the number wrong on your laptop’s address book.
You now have a document in each of the databases that has different information. This situation is called a conflict. Conflicts occur in distributed systems. They are a natural state of your data. How does CouchDB’s replication system deal with conflicts? [fix story-to-textbook-lingo-switch]
When you replicate two databases in CouchDB and you have conflicting changes, CouchDB will detect that and flag the affected document with the special attribute "\_conflicts":true. Next, CouchDB determines which of the changes will be stored as the latest revision (remember, documents in CouchDB are versioned). The version that gets picked to be the latest revision is the winning revision. The losing revision gets stored as the previous revision.
CouchDB does not attempt to merge the conflicting revision. Your application dictates how the merging should be done. The choice of picking the winning revision is arbitrary. In the case of the phone number, there is no way for a computer to decide on the right revision. This is not specific to CouchDB, no other software can this (ever had your contacts sync tool for your phone ask you which contact from which source to take?).
Replication guarantees that conflicts are detected and that each instance of CouchDB makes the same choice regarding winners and losers, independent of all the other instances. There is no group-decision made, instead, a deterministic algorithm determines the order of the conflicting revision. After replication, all instances taking part have the same data. The data set is said to be in a consistent state. If you ask any instance for a document, you will get the same answer regardless of which one you ask.
Whether or not, CouchDB picked the version that your application needs, you need to go and resolve the conflict, just as you need to resolve a conflict in a version control system like Subversion. Simply create a version that you want to be the latest by either picking the lastest, or the previous, or both (by merging them) and save it as the now latest revision. Done. Replicate again and your resolution will populate over to all other instances of CouchDB. Your conflict resolving on one node could lead to further conflicts all of which will need to be addressed, but eventually, you will end up with a conflict free database on all nodes.
This is an interesting conflicts scenario in that we helped a British broadcasting company build a solution for that is now in production. The basic set up is this: to guarantee that the company’s website are online 24/7 even in the event of the loss of a data center they have multiple data centers backing the website. The "loss" of a data center is a rare occasion, but it can be as simple as network outages where the data center is still alive and well, but can’t be reached by anyone.
The split brain scenario is one where the two (for simplicity’s sake we’ll stick to two) data centers are up and well connected to end-users, but the connection between the data centers, which is most likely not the same connection that end-users use to talk to the computers in the data center, fails.
The inter-data-center connection is used to keep both centers in sync so either can take over for the other in case of a failure. When that link goes down we end up with two halves of a system that act independently; the split brain.
As long as all end users can get to their data, the split brain is not scary. Resolving the split brain situation and bringing up the connection that links the data centers and staring synchronization again is where it gets hairy. Arbitrary conflict resolution, like CouchDB does by default can lead to unwanted effects on the user’s side. Data could revert to an earlier stage and leave the impression that changes weren’t reliably saved while in fact they were.
Let’s go through an illustrated example of how conflicts emerge an how to solve them in super slow-motion. Figure 4-1 illustrates the basic setup: we have two CouchDB databases and we are replicating from database A to database B. To keep this simple we assume triggered replication and not continuous replication and we don’t replicate back from database B to A. All other replication scenarios can be reduced to this setup, so this explains everything we need to know.
We start out by creating a document in database A. Note the clever use of imagery to identify a specific revision of a document. Since we are not using continuous replication database B won’t know about the new document for now.
We now trigger replication and tell it to use database A as the source and database B as the target. Our document gets copied over to database B. To be precise, the latest revision of our document gets copied over.
Now we go to database B and update the document. We change some values and upon change, CouchDB generates a new revision for us. Note that this revision got a new image. Node A is ignorant of any activity.
Now we make a change to our document in database A and we change some other values. See how it makes a different image for us to see the difference. It is important to not that this is still the same document. It’s just that there are two different revisions of that same document in each database.
Now we trigger replication again from database A to database B as before. By the way, it doesn’t make a difference if the two databases live in the same CouchDB server or on different servers connected over a network.
When replicating CouchDB detects that there are two different revisions for the the same document and it creates a conflict. A document conflict means that there are now two latest revisions for this document.
Finally, we tell CouchDB which version we like to be latest revision by resolving the conflict. Now both databases have the same data.
Other possible outcomes include choosing the other revision and replicating that decision back to database A or creating yet another revision in database B that includes parts of both conflicting revisions (a merge) and replicate that back to database A.
Now that we walked through replication with pretty pictures, let’s get our hands dirty and see what the API calls and responses for this and other scenarios look like. We’ll be continuing The Core API chapter by using curl on the command line to make raw API requests.
First, we create two databases that we can use for replication. These live on the same CouchDB instance, but they might as well live on a remote instance, CouchDB doesn’t care.
To save us some typing we create a shell variable for our CouchDB base URL that we want to talk to. We then proceed and create two databases db and db-replica:
HOST="http://127.0.0.1:5984"
> curl -X PUT $HOST/db
{"ok":true}
> curl -X PUT $HOST/db-replica
{"ok":true}
In the next step we create a simple document {"count":1} in db. And trigger replication to db-replica:
curl -X PUT $HOST/db/foo -d '{"count":1}'
{"ok":true,"id":"foo","rev":"1-74620ecf527d29daaab9c2b465fbce66"}
curl -X POST $HOST/_replicate -d '{"source":"db","target":"http://127.0.0.1:5984/db-replica"}'
{"ok":true,...,"docs_written":1,"doc_write_failures":0}]}
We skip a bit of the output of the replication session, see the Replication chapter for details. If you see "docs_written":1 and "doc_write_failures":0 our document made it over to db-replica.
We now update the document to {"count":2} in db-replica. Note that we now need to include the correct _rev property.
> curl -X PUT $HOST/db-replica/foo -d '{"count":2,"_rev":"1-74620ecf527d29daaab9c2b465fbce66"}'
{"ok":true,"id":"foo","rev":"2-de0ea16f8621cbac506d23a0fbbde08a"}
Next, we create the conflict! We change our document on db to {"count":3}. Our document is now logically in conflict, but CouchDB doesn’t know about it until we replicate again:
> curl -X PUT $HOST/db/foo -d '{"count":3,"_rev":"1-74620ecf527d29daaab9c2b465fbce66"}'
{"ok":true,"id":"foo","rev":"2-7c971bb974251ae8541b8fe045964219"}
> curl -X POST $HOST/_replicate -d '{"source":"db","target":"http://127.0.0.1:5984/db-replica"}'
{"ok":true,..."docs_written":1,"doc_write_failures":0}]}
To see that we have a conflict, we create a simple view in db-replica. The map function looks like this:
function(doc) {
if(doc._conflicts) {
emit(doc._conflicts, null);
}
}When we query this view, we get this result:
{"total_rows":1,"offset":0,"rows":[
{"id":"foo","key":["2-7c971bb974251ae8541b8fe045964219"],"value":null}
]}The key here corresponds to the doc._conflicts property of our document in db-replica. It is an array listing all conflicting revisions. We see that the revision we wrote on db ({"count":3}) is in conflict. CouchDB’s automatic promotion of one revision to be the winning revision chose our first change ({"count":2}). To verify that, we just request that document from db-replica:
> curl -X GET $HOST/db-replica/foo
{"_id":"foo","_rev":"2-de0ea16f8621cbac506d23a0fbbde08a","count":2}
|
How does CouchDB Decide Which Revision to Use?
CouchDB guarantees that each instance that sees the same conflict comes up with the same winning and losing revisions. It does so by running a deterministic algorithm to pick the winner. Application should not rely on the details of this algorithm and must always resolve conflicts. We’ll tell you how it works anyway. Each revision includes a list of previous revisions. The revision with the longest revision history list becomes the winning revision. If they are the same, the _rev values are compared in ASCII sort order, the highest wins. In our example 2-de0ea16f8621cbac506d23a0fbbde08a is higher than 2-7c971bb974251ae8541b8fe045964219. One advantage of this algorithm is that CouchDB nodes do not have to talk to each other to agree on winning revisions. We already learned that the network is prone to errors and avoiding it for conflict resolution makes CouchDB very robust. |
To resolve the conflict we need to determine which one we want to keep. Let’s say we want to keep the highest value. This means we don’t agree with CouchDB’s automatic choice. To do this, we first overwrite the target document with our value and then simply delete the revision we don’t like:
curl -X DELETE $HOST/db-replica/foo?rev=2-de0ea16f8621cbac506d23a0fbbde08a
{"ok":true,"id":"foo","rev":"3-bfe83a296b0445c4d526ef35ef62ac14"}
curl -X PUT $HOST/db-replica/foo -d "{\"count\":3,\"_rev\":\"2-7c971bb974251ae8541b8fe045964219\"}"
{"ok":true,"id":"foo","rev":"3-5d0319b075a21b095719bc561def7122"}
CouchDB creates yet another revision that reflects our decision. Note that the 3- didn’t get incremented this time. We didn’t create a new version of the document body, we just deleted a conflicting revision. To see all is well, we check if our revision ended up in the document.
curl GET $HOST/db-replica/foo
{"_id":"foo","_rev":"3-5d0319b075a21b095719bc561def7122","count":3}
We also verify that our document is no longer in conflict by querying our conflicts view again and we see that there are no more conflicts:
{"total_rows":0,"offset":0,"rows":[]}
Finally, we replicate from db-replica back to db by simply swapping source and target in our request to _replicate:
curl -X POST $HOST/_replicate -d '{"target":"db","source":"http://127.0.0.1:5984/db-replica"}'
And see that that our revision ends up in db, too:
curl GET $HOST/db/foo
{"_id":"foo","_rev":"3-5d0319b075a21b095719bc561def7122","count":3}
And we’re done.
Let’s have a look at this revision id: 3-5d0319b075a21b095719bc561def7122. Parts of the format might look familiar. The first part is an integer followed by a dash (3-). The integer increments for each new revision the document receives. Updates to the same document on multiple instances create their own, independent increments. When replicating, CouchDB knows that there are two different revisions 2- (like in our example above) by looking at the second part.
The second part is an md5-hash over a set of document properties: The JSON body, the attachments and the _deleted flag. This allows CouchDB to save on replication time in case you make the same change to the same document on two instances. Earlier versions (0.9 and back) used random integers to specify revisions and making the same change on two instances would result in two different revision ids, creating a conflict, where it was not really necessary. CouchDB 0.10 and above uses deterministic revision ids using the md5 hash.
For example, let’s create two documents a and b with the same contents to illustrate the deterministic revision ids.
curl -X PUT $HOST/db/a -d '{"a":1}'
{"ok":true,"id":"a","rev":"1-23202479633c2b380f79507a776743d5"}
> curl -X PUT $HOST/db/b -d '{"a":1}'
{"ok":true,"id":"b","rev":"1-23202479633c2b380f79507a776743d5"}
This concludes our tour of the conflict management system. You should now be able to create distributed setups that deal with conflicts in a proper way.