Vector Clocks and Conflicting Data

On This Page

What is clock skew?

What is a vector clock?

Conflict-free replicated data types (CRDTs)

Last-write-wins (LWW)

The previous lesson showed why a sloppy quorum lets multiple conflicting values exist for the same key. Let's look at how that happens, and how Dynamo deals with it.

What is clock skew?

On a single machine, one clock is enough. Suppose a write to key k lands at wall-clock time t1. A second write to the same key lands at t2. Since t2 is greater than t1, the second write is newer, and the database can safely overwrite the first value with it.

A distributed system breaks that assumption. Different clocks tend to run at different rates, a problem called clock skew. So time t on node a does not necessarily come before time t + 1 on node b, even though the numbers say so. Tools like

NTP

synchronize clocks about as well as anything practical can. Even they cannot guarantee that every clock agrees at every instant. Short of specialized hardware, like GPS units or atomic clocks, wall-clock timestamps alone are not enough to order writes.

What is a vector clock?

Instead of relying on tight clock synchronization, Dynamo tracks causality between versions with a vector clock. A vector clock is a list of (node, counter) pairs. Every version of every object stored in Dynamo carries one.

Comparing two vector clocks tells you how their versions relate. Say every counter in the first clock is less than or equal to the matching counter in the second. Then the first version is an ancestor of the second, and it can be forgotten. Otherwise, neither version can claim to be the ancestor of the other. The two changes are in conflict, and need reconciliation. Vector clocks detect that conflict at read time. They do not resolve it. Dynamo discards a version only when it is a strict ancestor of another. A genuine conflict goes back to the client, which reconciles it. Here is an example that shows how this plays out:

Server A writes key k1 with the value foo, and assigns it version [A:1]. This write replicates to server B.
Server A writes key k1 again, this time with value bar, and assigns it version [A:2]. This write also replicates to B.
A network partition occurs. A and B can no longer talk to each other.
Server A writes key k1 with value baz, and assigns it version [A:3]. It cannot replicate this to B, so the write sits in a hinted handoff buffer on another server instead.
Server B writes key k1 with value bax, and assigns it version [B:1]. It cannot replicate this to A, so it too sits in a hinted handoff buffer on another server.
The network heals, and A and B can talk to each other again.
A read request for k1 arrives at either server. It finds two versions, [A:3] and [A:2][B:1], and neither can claim to be newer. It returns both to the caller. It leaves the client to figure out the right version, and write it back into the system.

Conflict resolution using vector clocks

In the example above, most conflicts resolve themselves. A newer version subsumes the older one, since the system can see that [A:2] came after [A:1]. But failures and concurrent updates can overlap. When they do, versions branch, and the system is left holding genuinely conflicting versions of the same object. At that point the system cannot reconcile them on its own. So the client does the work: it collapses the branches back into one. That process is called semantic reconciliation.

Merging different versions of a customer's shopping cart is the standard example of a collapse like this. With this kind of reconciliation, an add, putting an item in the cart, is never lost. A deleted item, though, can resurface.

<p align="center">Resolving conflicts here works much like Git. When Git can merge two versions on its own, it does. When it can't, the developer reconciles them by hand.</p>

Vector clocks cannot grow forever, so Dynamo truncates them, dropping the oldest entries first once a clock grows too large. That has a cost. Say Dynamo drops an old vector clock that was still needed to reconcile an object's state. Then it can no longer achieve eventual consistency for that object. Dynamo's authors call this out as a real risk, without offering a fix for it. They do note that, as of their writing, it had not shown up in any of their production systems.

Conflict-free replicated data types (CRDTs)

There is a more straightforward way to sidestep conflicts: CRDTs, conflict-free replicated data types. Using one means modeling your data so that concurrent changes commute. That means they produce the same end result, no matter what order they run in. Once that holds, the system never has to worry about ordering at all.

Amazon's shopping cart is the classic example. A user adds two items, A and B, to the cart. Those two additions can run on any node, in any order, and the cart still ends up holding both items. (Removing an item is modeled as a negative add.) This property has a name: strong eventual consistency. It means any two nodes that have received the same set of updates end up seeing the same result. Riak ships a few built-in CRDTs.

Last-write-wins (LWW)

Modeling data as CRDTs is not always practical. In many cases it takes more effort than it is worth. That is why vector clocks with client-side resolution are usually considered good enough on their own.

Dynamo also gives you a way to resolve conflicts automatically, on the server, instead of using vector clocks. Dynamo, and Apache Cassandra, commonly use a simple policy for this: last-write-wins (LWW). LWW keeps the version with the later wall-clock timestamp. LWW can lose data easily. Say two conflicting writes happen at close to the same instant. Then keeping one over the other is no better than a random choice about which write gets thrown away.

Mark as Completed

Amey Naik

· 5 years ago

Show 3 replies

Reading Progress

Vote for new content

On This Page

What is clock skew?

What is a vector clock?

Conflict-free replicated data types (CRDTs)

Last-write-wins (LWW)