# Versions, conflicts, convergence

When the same data lives on a laptop, a phone and a server, and each of
them accepts writes while offline, two of them will sooner or later edit
the same document before they sync. Keeping only the last write would
silently drop the other edit. Barrel keeps both, shows the same
answer on every copy, and lets you decide what the document should say.

Every write to a Barrel document creates a version, named by a token
built from a hybrid logical clock (HLC) and the id of the database that
wrote it. Copies of a database exchange versions through
[replication](/docs/concepts/glossary#replication), keep concurrent
edits side by side as siblings, and all show the same winner. Read this
before you replicate, or when a document comes back with `_conflicts`.

## The version token

The token is the `_rev` you see on every read, the document's
[revision](/docs/concepts/glossary#revision). It is a string you can
read: the time of the write, then who made it.

```text
000001a1ba45b14e00000000@wddc4e1c028733ad0
|--------------||------| |---------------|
 wall clock ms   counter   writer id
```

- The first 24 hex digits are the HLC of the write: 16 for the wall clock
  in milliseconds, 8 for a logical counter that orders writes in the same
  millisecond. The hex is fixed width, so comparing tokens as strings
  compares them by clock.
- After `@` comes the writer id of the database that made the write. A
  database gets a new writer id every time it opens.
- `_rev` on a read is the token of the winning version.

## The clock

Ordering writes by wall clock alone breaks when one machine's clock is
behind another's. A hybrid logical clock fixes that: it follows the wall
clock and never goes back. Every replication exchange carries the peer's
clock (`x-barrel-hlc` over HTTP) and each side folds it into its own, so
a write made after a version was received always gets a greater token.

- If the node clock goes back below the highest HLC a database has
  written, writes fail with `{error, clock_skew}` until the clock catches
  up. The data is kept.
- A peer whose clock is ahead by more than `hlc_max_offset` ms is
  refused with `clock_skew` (409 over HTTP). The default, 0, turns that
  check off.

## Causal order and siblings

To know whether two versions are in conflict, Barrel has to know whether
one was written with knowledge of the other. Each version carries a
version vector: for every writer, the latest HLC it had seen. Barrel
compares vectors to tell two cases apart:

- **One version saw the other.** The newer one replaces the older one.
  This is the normal case: you read `_rev`, change the body, write.
- **Neither saw the other.** Two copies edited the same document before
  they synced. Both versions are kept as siblings. Nothing is dropped.

The second case is a [conflict](/docs/concepts/glossary#conflict). It is
not an error: it is a record that two people, or two agents, changed the
same thing at once.

## The winner

A document with siblings still has to answer reads, so Barrel picks one
to show. Among siblings, the winner is the greatest version: highest HLC
first, writer id to break a tie. The rule only depends on the set of
versions, so every copy that holds the same siblings shows the same
winner, in any order of sync. Showing a winner deletes nothing; the
others stay as `_conflicts` until you resolve them.

Here is a concrete case. Two copies, `laptop` and `phone`, both start
from the same `task:1`. The laptop marks it `done`, the phone marks it
`blocked`, and then they sync both ways:

Erlang shell:

```erlang
{ok, L} = barrel_docdb:get_doc(<<"laptop">>, <<"task:1">>),
{ok, P} = barrel_docdb:get_doc(<<"phone">>, <<"task:1">>),
barrel_docdb:put_doc(<<"laptop">>,
                     L#{<<"state">> => <<"done">>}),
barrel_docdb:put_doc(<<"phone">>,
                     P#{<<"state">> => <<"blocked">>}),
barrel_rep:replicate(<<"laptop">>, <<"phone">>),
barrel_rep:replicate(<<"phone">>, <<"laptop">>),
barrel_docdb:get_doc(<<"laptop">>, <<"task:1">>,
                     #{conflicts => true}).
```

Output from a run on barrel_docdb 2.1.0:

```
{ok,#{<<"_conflicts">> =>
          [<<"000001a1ba40490400000000@w0db1f003b3487bf5">>],
      <<"_observed">> =>
          [<<"000001a1ba40490400000001@w6e689af2f29a3bb0">>,
           <<"000001a1ba40490400000000@w0db1f003b3487bf5">>],
      <<"_rev">> =>
          <<"000001a1ba40490400000001@w6e689af2f29a3bb0">>,
      <<"id">> => <<"task:1">>,<<"state">> => <<"blocked">>}}
```

> **Note:** The read shows the winner, `blocked`, and its token in `_rev`. The
> laptop's `done` edit is not lost: its token is in `_conflicts`.
> `_observed` lists both tokens, the winner and the sibling, because this
> read showed both.

Reading `phone` returns the same `_rev`, `_conflicts` and body. Both
writes fell in the same millisecond, so the logical counter decided.

## Resolve with `_observed`

Resolving means writing the version that should replace the siblings.
The risk is that a third edit arrives while you decide, and your
resolution wipes it out. `_observed` prevents that.

`_observed` lists every version your read showed. Pass it back and the
resolution replaces exactly those versions. A version that arrived after
your read is not one of them, so it stays as a conflict: you never
overwrite an edit you did not see.

Erlang shell:

```erlang
{ok, #{<<"_observed">> := Seen}} =
    barrel_docdb:get_doc(<<"laptop">>, <<"task:1">>,
                         #{conflicts => true}),
barrel_docdb:resolve_conflict(<<"laptop">>, <<"task:1">>, Seen,
    {merge, #{<<"id">> => <<"task:1">>,
              <<"state">> => <<"blocked">>,
              <<"note">> => <<"done once unblocked">>}}).
```

Output from a run on barrel_docdb 2.1.0:

```
{ok,#{id => <<"task:1">>,
      rev => <<"000001a1ba40490700000000@w0db1f003b3487bf5">>,
      conflicts_resolved => 1}}
```

> **Note:** The merge wrote a new version with its own token in `rev`.
> `conflicts_resolved => 1` says it replaced the one sibling, so `task:1`
> is back to a single version on the laptop.

After the next replication, `phone` has the resolution and no conflicts:

Output from a run on barrel_docdb 2.1.0:

```
> barrel_docdb:get_conflicts(<<"phone">>, <<"task:1">>).
{ok,[]}
```

> **Note:** An empty list means `phone` holds no siblings for `task:1` any more. The
> resolution travelled like any other write.

The resolution can be:

| Resolution | Effect |
|------------|--------|
| `{choose, Token}` | Keep that version's body and its deleted flag |
| `{merge, Body}` | Write a new body |
| `delete` | Resolve to a delete |

You can also write the document with `_observed` in the body (over REST,
read with `?conflicts=true` and send `_observed` back). A write with only
`_rev` replaces the winner and leaves the conflicts in place. A `_rev`
that is not the winner returns `{error, conflict}`.

## Resolve automatically

When your application knows a rule for picking or merging versions, you
do not have to resolve by hand. Give the database a `conflict_resolver`.
It runs whenever a write or a sync leaves more than one version, and
returns `{choose, Token}`, `{merge, Body}`, `delete` or `keep`.

```erlang
Resolver = fun(Versions) ->
    %% Versions: [#{token, deleted, body}], sorted by token
    Live = [B || #{deleted := false, body := B} <- Versions],
    case Live of
        [] -> delete;
        _ -> {merge, lists:max(Live)}
    end
end,
{ok, _} = barrel_docdb:create_db(<<"db">>,
    #{conflict_resolver => Resolver}).
```

Make it pure and independent of the order it sees versions in. Then
every copy writes the same resolution and the conflict ends in one
version everywhere. A crash counts as `keep`. Pass it again on every
open: it is not stored.

> **Limit:** Two copies resolving the same conflict at the same time leave their two
> resolutions in conflict; resolve once more. Above
> `max_conflict_versions` (default 8) the oldest siblings are evicted; the
> winner always stays.

## Why it converges

[Convergence](/docs/concepts/glossary#convergence) is the promise that
copies which have exchanged all their versions end up identical, without
a central server deciding. Each copy ends with the same set of versions,
the same winner, the same body and the same deleted flag, whatever the
order of writes and syncs. Delivery is idempotent, so sending a version
twice is safe. The model and its checked properties are in [Replication
proofs](/docs/architecture/replication-proofs).

<NextSteps steps={[
  { href: '/docs/guides/synchronization', label: 'Synchronization', why: 'Set up the replication that moves these versions between copies.' },
  { href: '/docs/replicate/conflicts', label: 'Conflicts', why: 'Find, inspect and resolve conflicts in a running application.' },
  { href: '/docs/architecture/replication-proofs', label: 'Replication proofs', why: 'The model behind convergence and the properties that are checked.' },
]} />
