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, 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. It is a string you can
read: the time of the write, then who made it.
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. _revon 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_offsetms is refused withclock_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. 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:
{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}). {ok,#{<<"_conflicts">> =>
[<<"000001a1ba40490400000000@w0db1f003b3487bf5">>],
<<"_observed">> =>
[<<"000001a1ba40490400000001@w6e689af2f29a3bb0">>,
<<"000001a1ba40490400000000@w0db1f003b3487bf5">>],
<<"_rev">> =>
<<"000001a1ba40490400000001@w6e689af2f29a3bb0">>,
<<"id">> => <<"task:1">>,<<"state">> => <<"blocked">>}} 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.
{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">>}}). {ok,#{id => <<"task:1">>,
rev => <<"000001a1ba40490700000000@w0db1f003b3487bf5">>,
conflicts_resolved => 1}} 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:
> barrel_docdb:get_conflicts(<<"phone">>, <<"task:1">>).
{ok,[]} 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.
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.
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 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.