Detect Conflicts with Vector Clock Comparison

Causal Ordering with Vector Clocks

The power of vector clocks is that they allow precise causal reasoning. Given two versions of a value — say from two replicas — you can determine exactly one of four relationships.

The Comparison Algorithm

def compare(a, b):
    a_le_b = all(a[n] <= b[n] for n in nodes)
    b_le_a = all(b[n] <= a[n] for n in nodes)

    if a_le_b and b_le_a:
        return "EQUAL"
    elif a_le_b:
        return "BEFORE"
    elif b_le_a:
        return "AFTER"
    else:
        return "CONCURRENT"

Interpreting Results in Dynamo

Result	Meaning	Action
BEFORE	A is an older version of B	Discard A, keep B
AFTER	A is a newer version of B	Discard B, keep A
CONCURRENT	Genuine conflict	Store both; surface to client
EQUAL	Duplicate write	Keep either

Concurrent Writes in Dynamo

Concurrent writes happen when two clients write to the same key at roughly the same time via different coordinators. Neither write was aware of the other. Dynamo stores both versions and returns them both to the next reader. The application (or a merge function) then resolves the conflict.

Amazon's shopping cart, for example, merges conflicting carts by taking the union of items — you might see duplicate items, but you will never lose an item due to a conflict.