This document explains how Ledger handles conflicts.
Ledger is an offline-first database - devices can naturally diverge when making concurrent changes and thus, the change history forms a directed acyclic graph (DAG) of commits. Whenever the local history DAG has more than one head commit, i.e. more than one leaf in the DAG, we call this state a conflict.
Whenever a conflict arises, Ledger by default merges the local heads automatically, using an entry-by-entry last-one-wins policy based on non-reliable timestamps of the two commits being merged. See the Merge Strategies section for more details.
Client apps that want to override this behavior can opt for either one of the predefined merging policies or use a custom policy and handle the merges themselves, see Conflict Resolution in the API Guide.
As the same conflict can be resolved concurrently on two devices, the resulting state can once more be different between devices. This can potentially create a situation where two or more devices keep creating merge commits that are then synced and merged again. This situation is called a merge storm.
Ledger employs a number of strategies in order to prevent merge storms:
For each page, client apps can define a merge strategy. These strategies determine the behavior of Ledger when a conflict is detected, and are appropriate for different situations.
To avoid merge storms (as described above), we ensure that any automatic merge strategy is deterministic, so that two devices seeing the same conflict reach the same resolution.
The last-one-wins merge strategy is the default one, i.e. the one applied if the client app didn‘t configure any other strategy. When using this strategy, the client app delegates all merging to Ledger and doesn’t have to handle merges.
The last-one-wins strategy operates by taking, for each conflicting key/value pair, the one present in the latest commit, ordered by creation timestamp. However, if a key/value pair is modified by one commit only (added, removed, or changed value), the modification is taken, regardless of the timestamp.
This strategy is very convenient for applications that use Ledger to store independent key/value pairs, as it removes the burden of merging from the client application entirely. Storing independent key/value user preferences would be a good case for this strategy.
The creation timestamps are generated on each device. Thus, unsynchronized clocks or clock drift between devices may result in older values taking precedence over new ones.
We think this is fine because:
The automatic with fallback merge strategy attempts to automatically merge commits when no key/value pair conflicts, and defer to a custom conflict resolver when at least one key/value pair conflicts.
When using this strategy, client applications need to write a custom conflict resolver, but its usage is limited: if the client application modified disjointed (different) parts of a page on two devices, the modifications of each device will be applied automatically and the custom conflict resolver will not be called. However, if an entry was modified on both sides to contain different values, then the custom conflict resolver will be called.
This strategy is convenient if a client application stores independent key/value pairs, but wants to control how the values are merged when modified on both places. For example, when storing a list as value, a client app may want to merge the list as to keep the modifications of both sides instead of picking only one. This strategy can also be used to prompt the user to choose the resolution they want.
The Custom merge strategy defers to the client app each time there is a conflict. Remember, however, that Ledger does not consider a change from another device to be conflicting if there were no local changes during the same period, and will simply fast-forward the Ledger state.
This strategy is useful when the client app is storing key/value pairs that have dependencies that need to be enforced by business-logic.
In order to facilitate convergence, any custom conflict resolution implemented by the client app should be deterministic - that is, the resulting merge commit should depend only on the two commits being merged. This ensures that the same conflict resolved concurrently on two devices yields the very same result.
The pair of commits passed to the conflict resolver is ordered deterministically by Ledger, so the conflict resolver doesn’t need to be commutative.
This section discusses conflict resolution behavior in a number of scenarios.
When a device that has been making modifications offline goes back online, the device downloads remote modifications first, then resolves any conflicts, and only after that uploads its own changes to the cloud. This way the other devices that are online and in sync with each other only need to fast-forward to catch up with remote changes. We sacrifice sync latency (it takes longer for changes from the offline device to be visible to others) for faster convergence and less bandwidth spend.
When two online devices make a concurrent change (that is, both make their changes before seeing changes from the other device), the convergence is ensured as long as the conflict resolver is deterministic (see Custom conflict resolvers). When two devices concurrently resolve the same conflict, they produce the same resulting merge commit. This commit can be then uploaded to the cloud twice, once by each device, but any extra occurrences will be ignored by each participant and will not trigger further merges.
