Skip to main content

Merge Rules

info

It isn't important to understand this section to use automerge. You can just let automerge handle merging for you. But it may be interesting to understand.

How does automerge merge concurent changes? Well, let's think about what kinds of concurrent changes are possible. Automerge documents always carry their history with them, so the way to think about two concurrent versions of a document is as the set of changes since some common ancestor.

Here the common ancestor is C and the concurrent changes are (D,E) and (F,G).

Automerge documents are composed of nested maps and lists or simple values or text sequences. We can describe the merge rules by describing the rules for maps, lists, text, and counters independently. In each case we describe how to merge two sets of concurrent changes we refer to as A and B.

Map merge rules

  • If A sets key xx to a value and B sets key yy to a value and xyx \neq y then add both xx and yy to the merged map
  • If A deletes key xx and B makes no change to xx then remove xx from the merged map
  • If A deletes key xx and B sets xx to a new value then set the value of xx to the new value B set in the merged map
  • If both A and B delete key xx then delete xx from the merged map
  • If both A and B set the key xx to some value then randomly choose one value

Note that "randomly choose" means "choose one arbitrarily, but in such a way that all nodes agree on the chosen value".

List merge rules

To understand the way lists merge you need to know a little about how the operations on lists are expressed. Every element in a list has an ID and operations on the list reference these IDs. When you update an index in a list (using list[<index>] = <value> in a change function in the JS library) the operation which is created references the ID of the element currently at index. Likewise when you delete an element from a list the delete operation which is created references the deleted element at the given index. When you insert elements into a list the insert operation references the ID of the element you are inserting after

In the following then when we say "index xx" that really means "the ID of the element at index xx at the time the operation was created".

  • If A inserts an element after index ii and B inserts an element after index ii then arbitrarily choose one to insert first and then insert the other immediately afterwards
  • If A deletes element at index ii and B updates the element at ii then set the value of ii to the updated value from B
  • If A and B both delete element ii then remove it from the merged list

Note that inserting a run of elements will maintain the insertion order of the replica which generated it. Imagine we have some list [a, b] and say A inserts the sequence [d, e] after a whilst B inserts [f, g] after a. Initially the set of operations are:

Operation IDReference elementValue
ANonea
BAb

The operations after inserting on A are

Operation IDReference elementValue
ANonea
BAb
DBd
EDe

And on B

Operation IDReference elementValue
ANonea
BAb
FBf
GFg

Here you can see that while both F and D insert after the same reference element (B) the following operations reference the element that was just inserted on the local replica. That is, automerge must arbitrarily choose one of either F or D to be inserted after B, but after that the operations stay in the same order as they were inserted on each node. Let's say that A is chosen, then the final order of operations will be

Operation IDReference elementValue
ANonea
BAb
DBd
EDe
FBf
GFg

There are cases where this algorithm does not preserve insertion order - primarily when inserting elements in reverse - but most of the time it does a good job.

Text merge rules

The characters of a text object are merged using the same logic as lists. For a description of the merge rules for marks see Peritext

Counter merge rules

Counters are very simple, we just sum all the individual operations from each node.