Have you implemented OpenMRS? Please participate in the Implementation Site Survey. If you already have, thank you!
Child pages
  • Conflict detection and resolution
Skip to end of metadata
Go to start of metadata


This article is a proposal of conflict detection and resolution, which is a result of research.

Index:

  1. Introduction
  2. Research
  3. Research summary
  4. Proposal
  5. Resources


1. Introduction

Conflict scenarios:

  • Insert-insert
    All objects in each table participating in peer-to-peer replication are uniquely identified by using primary key values. An insert-insert conflict occurs when an object with the same key value was inserted at more than one node.
  • Update-update
    Occurs when the same object was updated at more than one node.
  • Insert-update
    Occurs if an object was updated at one node, but the same object was deleted and then reinserted at another node.
  • Insert-delete
    Occurs if a row was deleted at one node, but the same row was deleted and then reinserted at another node.
  • Update-delete
    Occurs if a row was updated at one node, but the same row was deleted at another node.
  • Delete-delete
    Occurs when a row was deleted from more than one node.

Greyed-out scenarios do not apply to our system, because:

  • we use UUID, so there are no PK conflicts
  • we do not delete object, we void them if needed, right?



2. Research

2.1. Oracle

Conflict detection

Main conception:

To detect and resolve an update conflict for a row, the propagating site must send a certain amount of data about the new and old versions of the row to the receiving site.

More info here!

How it is done:

The receiving site detects an update conflict if there is any difference between the old values of the replicated row (the values before the modification) and the current values of the same row at the receiving site.


Let's take an example:

sync2-example-diagram2


  1. New Patient with name "A" is created on Parent instance
  2. Both Child 1 and Child 2 pull new Patient with name "A"
  3. Child 1 updates name of Patient to "B" and pushes to Parent
    1. Conflict detection checks if name saved on Parent is equal to old (before updating) name saved on Child 1
      1. if YES, then it means that Child 1 is updating original and up-to-date name on Parent = no conflict, update
      2. in NO, then it means that either Parent itself or Child 2 updated name = conflict, resolve somehow
    2. Name saved on Parent is "A", old name saved on Child 1 is "A", updated name on Child 1 is "B"
    3. "A" == "A", conflict detection answered YES, name value was updated
  4. Child 2 updates name of Patient to "C" and pushes to Parent
    1. Conflict detection checks if name saved on Parent is equal to old (before updating) name saved on Child 2
      1. if YES, then it means that Child 2 is updating original and up-to-date name on Parent no conflict, update
      2. in NO, then it means that either Parent itself or Child 1 updated name = conflict, resolve somehow
    2. Name saved on Parent is now "B", old name saved on Child 2 is "A", updated name on Child 2 is "C"
    3. "B" !== "A", conflict detection answers NO, there is a conflict 



Conflict resolution


If it is possible to apply, we should check out Oracle Database Advanced Replication Management API Reference.


Common Update Conflict Resolution Methods

  • Latest Timestamp
  • Overwrite

But out of those, only Latest Timestamp is useful with multiple master sites.

Latest Timestamp = most recent update wins


Additional Update Conflicts Resolution Methods

(those than offer convergence with multiple master sites)

  • additive - for single numeric values
  • maximum - takes the biggest value
  • minimum - takes the smallest value
  • priority group - enable you to assign a priority level to each possible value of a particular column





2.2. GitHub

Conflict detection


We can easily apply Oracle example to GitHub.

Example 1:

Let's imagine a master branch (Parent) and two branches (Child 1 and Child 2) with Parent as upstream.

  1. Both branches pull master
  2. Child 1 pushes its changes to master
    1. Parent code is equal to Child 1 code before making any modifications (update) = no conflict
  3. Child 2 pushes its changes to master
    1. Parent code was modified by Child 1's push, so it is NOT equal to Child 2 code before making modifications = conflict


Conflict resolution



Resolving Example 1 conflict:

Git will not let Child 2 push to master, but will notify:

Updates were rejected because the remote contains work that you do not have locally.

You will be asked to pull updated master and resolve conflicts manually.

Create UI interface for choosing which changes to accept?



2.3. Microsoft

Conflict detection

Microsoft's note:

To avoid potential data inconsistency, make sure that you avoid conflicts in a peer-to-peer topology, even with conflict detection enabled. To ensure that write operations for a particular row are performed at only one node, applications that access and change data must partition insert, update, and delete operations. This partitioning ensures that modifications to a given row that is originating at one node are synchronized with all other nodes in the topology before the row is modified by a different node. 

So we just sync change in one node with ALL the rest?


How SQL Server 2017 handles it:

In systems such as peer-to-peer replication, conflicts are not detected when changes are committed at individual peers. Instead, they are detected when those changes are replicated and applied at other peers. In peer-to-peer replication, conflicts are detected by the stored procedures that apply changes to each node, based on a hidden column in each published table. This hidden column stores an ID that combines an originator ID that you specify for each node and the version of the row.









empty


2.4. Brent Ozar's website












empty

Conflict resolution

Strategies

  • Manual intervention
  • Logging conflicts
  • Master write server
  • Last write wins
  • Write partitioning

a. Manual intervention

Letting users/admin choose which change to accept.


b. Logging conflicts

As conflicts are logged, they can be written to a queue where conflict resolution software and kick into action and attempt to resolve the conflicts automatically.

c. Master write server

One instance writes to all child instances - rather impossible solution


d. Last write wins

Oracle's Last Timestamp


e. Write partitioning

Ensure that all writes for a single row will always happen on the same server.

- useless in our system



3. Research summary


Conflict detection

The most reasonable solution for conflict detection could be:

  1. On every manual push of Child to Parent - first download Parent's version of object.
  2. Compare values of Parent's object to object stored on Child (before modifications).
  3. If Parent's object is equal to Child's object than it means that Child is operating on up-to-date object and there is no conflict.
  4. However, if they differ, it means that Child is operating on outdated object and conflict is detected.

Note: Some OpenMRS classes offer voiding, that saves outdated values as voided and keep date of change - but not all classes! 


However with this solution we will have problems detecting conflicts when object are synced automatically, we should figure out if there is a solution for this case.


Different approach is better because it does not need to detect conflicts, because they can be prevented. However it requires all nodes to be updated after a single change of object in one node - that for sure is hard to accomplish due to: amount of operations that would have to be executed, constant internet connection (node-node connection).


Conflict resolution

The most reasonable solution for conflict resolution could be:

After a conflict was detected:

  1. Show "conflict resolution" page to the user to let him choose between conflicted values.
    or
  2. Use Latest Timestamp approach.
    or
  3. Action taken by Parent instance.

4. Proposal


4.1. Conflict detection

We need a new table in a database of each instance to store hashcodes of objects pulled from this instance's Parent.

PULL:

  1. At first, when we pull an object from Parent to Child instance (where it does not exist yet):
    1. calculate hashcode of an object pulled from Parent,
    2. look for an object on Child instance with UUID of pulled object,
    3. such object on Child instance does not exist, so object is created on Child instance,
    4. object's hashcode is saved in Child's database as the latest version of this object on Parent instance,
    5. there is NO conflict.
  2. Object is NOT modified on Parent instance.
  3. When we pull the same object from Parent the second time (this object already exist on Child instance):
    1. calculate hashcode of an object pulled from Parent,
    2. look for an object on Child instance with UUID of pulled object,
    3. such object on Child instance exists, so compare calculated hashcode with a hashcode that is saved in Child's database,
    4. they are equal, which means that object on Child instance is up to date with corresponding object on Parent instance,
    5. there is NO conflict.
  4. Object is modified both on Parent and/or Child instance.
  5. When we pull the same object from Parent the third time (this object already exist on Child instance):
    1. calculate hashcode of an object pulled from Parent,
    2. look for an object on Child instance with UUID of pulled object,
    3. such object on Child instance exists, so compare calculated hashcode with a hashcode that is saved in Child's database,
    4. they are NOT equal, which means that object on Child instance is NOT up to date with corresponding object on Parent instance
    5. there is a conflict, which is resolved using rule RULE 1


4.2. Conflict resolution



PULL:

  • RULE 1

    If hashcode of an object on Parent instance is NOT equal to hashcode of an object on Child instance* it means that there is a new version of this object on Parent → 

    • if object on Child instance was NOT modified (calculated hashcode of modified object is equal to hashcode saved on Child's instance*) →
      • void current object's fields on Child instance,
      • save fields of object from Parent instance to Child.

    • if object on Child instance was modified (calculated hashcode of modified object is NOT equal to hashcode saved on Child's instance*) → 
      • these two objects have to be merged**, then
      • saved on Child and Parent instance;
      • hashcodes on both Child and Parent instance have to be updated.


* REMEMBER: This is a hashcode of an object that was calculated and saved on the last pull of this object from Parent. This hashcode is stored in a seperate table than pulled object.

** See 4.3. Merging


PUSH:

  1. At first, when we push an object from Child to Parent instance (where it does not exist yet):
    1. In SyncPushServiceImpl class during execution of readAndPushObjectToParent method we call shouldPushObject method, where we pull corresponding object from Parent instance,
    2. this object does not exist on Parent instance yet, shouldPushObject returns true,
    3. object is pushed to Parent,
    4. object's hashcode is saved in Child's database as the latest version of this object on Parent instance.
  2. Object is modified on Child instance.
  3. When we push this object from Child to Parent instance (where it already exists):
    1. In SyncPushServiceImpl class during execution of readAndPushObjectToParent method we call shouldPushObject method, where we pull corresponding object from Parent instance,
    2. this object already exists on Parent instance,
    3. calculate hashcode of an object pulled from Parent,
    4. compare calculated hashcode with a hashcode that is saved in Child's database,
    5. they are equal, which means that Child modified the latest version of object on Parent instance,
    6. object is pushed to Parent,
    7. object's hashcode is updated in Child's database as the last version of this object.
  4. Object is modified both on Parent and/or Child instance.
  5. When we push this object from Child to Parent instance (where it already exists):
    1. In SyncPushServiceImpl class during execution of readAndPushObjectToParent method we call shouldPushObject method, where we pull corresponding object from Parent instance,
    2. this object already exists on Parent instance,
    3. calculate hashcode of an object pulled from Parent,
    4. compare calculated hashcode with a hashcode that is saved in Child's database,
    5. they are NOT equal, which means that object on Child instance is NOT up to date with corresponding object on Parent instance (someone modified this object on Parent instance),
    6. there is a conflict, which is resolved using rule RULE 2.


PUSH:

  • RULE 2

    If hashcode of an object on Parent instance is NOT equal to hashcode of an object on Child instance* it means that the object was updated on Parent instance after the last pull to Child (we are pushing modifications of outdated version of object) → 

    • if object on Child instance was NOT modified (calculated hashcode of modified object is equal to hashcode saved on Child's instance*) → PUSH operation of this object will not take place

    • if object on Child instance was modified (calculated hashcode of modified object is NOT equal to hashcode saved on Child's instance*) → 
      • these two objects have to be merged**, then
      • saved on Child and Parent instance;
      • hashcodes on both Child and Parent instance have to be updated.


* REMEMBER: This is a hashcode of an object that was calculated and saved on the last pull of this object from Parent. This hashcode is stored in a seperate table than pulled object.

** See 4.3. Merging



4.3. Merging

Once a conflict was detected two objects will have to be merged. To do this, a new database table "Conflicts" will have to be created.
This table will have columns: openmrs_class, first_object, second_object and more if needed.

It will be possible to insert any type of object into child_object and parent_object due to its type: it will be either JSON, (TINY)BLOB, TEXT or else.


All conflicted objects will be put into this table and queued just like AuditLog does this.
However, there should be only the most recent merge conflict for any object. The old ones should be voided.

Then either chosen strategy or UI will be used to:

  • determine if child_object, parent_object or mixed object will be preserved,
  • determine what operation should be taken after merging (pushpull / ...)

When the conflict is resolved we should save parent's object as voided in child's database.


UI for merging will use openmrs_class field to determine what class are child_object and parent_object.
Fields of determined class will be displayed as textboxes or buttons for each of two objects.
User will be able to choose which value he wants to keep.


  • No labels