In previous post, we learnt about multi-leader replication and the use cases where we need that multi-leader replication. In this post we will look into a common problem with multi leader replication – write conflicts. 

Consider google doc which is shared between multiple people, if two people edit the same line at the same time from two different machines, in multi leader replication, both of them will look like they are written on the replicas, but there is a conflict which needs to be solved before committing them. At this time though, it will be too late to resolve the conflict by asking the users. 

We could make conflict detection synchronous, wait for the write to be replicated to all replicas before telling the user that the write was successful.

However, by doing so, you would lose the main advantage of multi-leader replication: allowing each replica to accept writes independently. If you want synchronous conflict detection, you might as well just use single-leader replication.

Conflict avoidance

The simplest strategy for dealing with conflicts is to avoid them: if the application can ensure that all writes for a particular record go through the same leader, then conflicts cannot occur. 

Say we have two people A and B. A’s writes will always go to the leader A (one data center) and B’s writes would always go to the leader B (second datacenter). Same for reads, A will read from leader A and B will read from leader B. Different users may have different “home” data centers (perhaps picked based on geographic proximity to the user), but from any one user’s point of view the configuration is essentially single-leader.

However conflict avoidance breaks when either data center fails/user moves to another data center’s region and now we need to change the leader to another data center, that leader might not have the whole data from previous leaders and there is possibility of concurrent writes as both users now have same leader.

Converging toward a consistent state

A single-leader database applies writes in a sequential order: if there are several updates to the same field, the last write determines the final value of the field.

In a multi-leader configuration, there is no defined ordering of writes, so it’s not clear what the final value should be. The database must resolve the conflict in a convergent way, which means that all replicas must arrive at the same final value when all changes have been replicated.

There are various ways of achieving convergent conflict resolution:

• Give each write a unique ID, pick the write with the highest ID as the winner, and throw away the other writes. If a timestamp is used, this technique is known as last write wins (LWW). Although this approach is popular, it is dangerously prone to data loss. We will discuss LWW in more detail at the end of this chapter.

• Give each replica a unique ID, and let writes that originated at a higher-numbered replica always take precedence over writes that originated at a lower-numbered replica. This approach also implies data loss.

• Somehow merge the values together—e.g., order them alphabetically and then concatenate them.

• Record the conflict in an explicit data structure that preserves all information, and write application code that resolves the conflict at some later time (perhaps by prompting the user).

Custom conflict resolution logic

Letting application handle conflict resolution either at write or at read.

On write

As soon as the database system detects a conflict in the log of replicated changes, it calls the conflict handler. 

On read

When a conflict is detected, all the conflicting writes are stored. The next time the data is read, these multiple versions of the data are returned to the application. The application may prompt the user or automatically resolve the conflict, and write the result back to the database. CouchDB works this way, for example.

Automatic conflict resolution

Different ways in which we can achieve automatic conflict resolution in multi leader database –

• Conflict-free replicated datatypes (CRDTs) are a family of data structures for sets, maps (dictionaries), ordered lists, counters, etc. that can be concurrently edited by multiple users, and which automatically resolve conflicts in sensible ways. Some CRDTs have been implemented in Riak 2.0.

• Mergeable persistent data structures track history explicitly, similarly to the Git version control system, and use a three-way merge function (whereas CRDTs use two-way merges).

• Operational transformation is the conflict resolution algorithm behind collaborative editing applications such as Etherpad and Google Docs. It was designed particularly for concurrent editing of an ordered list of items, such as the list of characters that constitute a text document.

Thanks for stopping by! Hope this gives you a brief overview in to handling conflicts for multi-leader replication. Eager to hear your thoughts and chat, please leave comments below and we can discuss.