Handling write conflicts under multi-master replication (3) - Convergence to a consistent state and custom conflict resolution logic

3.2.3 Convergence to a consistent state

In the master-slave replication model, data updates conform to the sequential principle, that is, if there are multiple updates to the same field, the last write operation will determine the final value of the field.

In the multi-master replication model, since there is no such write order, the final value is also uncertain.In Figure-7:

• The title in master node 1 is first updated to B and then to C
• In master node 2, first update to C, then update to B

The two cannot identify which is "more correct".

If each replica executes in the order in which it sees the writes, the DB will end up in an inconsistent state, such as master 1 seeing the final value C and master 2 seeing B.This is not acceptable, all replication models must at least ensure that the final state of the data is consistent across all replicas.Therefore, the DB must resolve conflicts in a convergent way, which means that all replicas must end up with the same value when all changes are replicated.

3.2.3.1 Convergence conflict resolution

• Give each write a unique ID (such as a timestamp, a long nonce, a UUID, or a hash), pick the write with the highest ID as the winner, and discard the others.If based on timestamps, this technique is called last write wins (LWW, last write wins).Although this method is popular, it is prone to data loss.Discussed in detail later.
• Assign a unique ID to each replica and make rules such that writes to replicas with higher ID numbers always have higher priority.However, data loss may also occur
• Merge the values ​​in some way, such as alphabetically, and then concatenate (Figure-7, the combined title may be something like "B/C")
• Record and retain all conflict-related information in a predefined format, and then rely on application-layer logic to resolve the conflict afterwards (possibly prompting the user)

3.2.4 Custom conflict resolution logic

The most appropriate way to resolve conflicts is to rely on the application layer, so many multi-master replication models have tools that allow application code to resolve conflicts, which can execute these code logic when writing or reading:

p>

Execute on write

The conflict handler is called whenever the DB system detects a conflict in replicating the changelog.Such as Bucardo allows to write a piece of Perl code.This handler usually cannot prompt the user online, it can only run as a background process

Execute while reading

When a conflict is detected, all conflicting writes are staged.On the next read, multiple versions of the data are returned to the application layer.The application may prompt the user or resolve the conflict automatically and write the final result back to the DB.Such as CouchDB.

Conflict resolution usually applies to a single line or document, not the entire transaction.Therefore, if an atomic transaction contains multiple different write requests, each write request still needs to be considered separately to resolve conflicts.

What is a conflict?

Some conflicts are obvious, as shown in Figure-7. Two write operations concurrently modify the same field in the same record and set them to two different values.

Other types of conflicts may be subtler.Such as a conference room reservation system, which records who has booked which room at which time period.The app needs to ensure that each room is booked by only one group of people at the same time (no double bookings for the same room).At this point, if two different reservations are created for the same room at the same time, there is a conflict.Although the application checks for room availability when booking, there may be a conflict if the two bookings are made by two different primary nodes.

Automatic conflict resolution

Conflict resolution rules can become increasingly complex, and custom code is prone to errors.Amazon is a classic counter-example: For a while, the conflict resolution logic on the shopping cart relied on the user's cart page (where all the items were saved), but customers sometimes found items that had been removed before reappearing in their cart.

Some interesting research attempts to automatically resolve conflicts due to concurrent modification of data:

• Conflict-free replicated datatypes (CRDT) A series of data structures such as collections, maps, ordered lists, counters, etc. that can be edited by multiple users simultaneously, theyAutomatically resolve conflicts in a reasonable manner.Some CRDTs have been implemented in Riak 2.0
• **Mergeable persistent data structures** explicitly track history, similar to the Git version control system, and use a three-way merge feature (whereas CRDT uses a two-way merge)
• **operational transformation** The conflict resolution algorithm behind collaborative editing applications like Etherpad and Google Docs.Designed for simultaneous editing of ordered lists of items, such as lists of characters that make up a text document

The implementation of these algorithms in databases is still young, but it is likely that they will be integrated into more replicated data systems in the future.Automatic conflict resolution can make it easier for applications to handle multi-leader data synchronization.

Unfortunately, there is no ready-made answer, which will be explained in more depth later.