Module 19 / Algorithms behind big systems

Module 19 · lesson 2 of 22 · Read 8 min

Vector clocks

Telling "happened before" from "happened at the same time".

Lamport clocks gave every event a number that respects cause and effect. But they could not answer the question you most often need answered: did these two writes see each other, or not? If they did, the later one should simply win. If they didn't, you have a conflict, and throwing one away loses data.

That question comes up the moment you accept writes in more than one place. In Module 13 you met leaderless replication, where any replica can take a write. This lesson is about the bookkeeping that lets such a system tell an overwrite from a conflict.

The problem: a cart edited from two devices

Tiffin keeps each customer's cart in a Dynamo-style store with three replicas, X, Y and Z. Any replica can accept a write. Priya has the app open on her phone and on her laptop.

  • On her phone she adds naan.
  • On her laptop, which loaded the cart a minute ago, she adds a lassi.

Both writes land on different replicas. Later, a read finds two versions of the cart. Which one is right? With wall clocks you would pick the newer one and lose an item. With Lamport timestamps you would also pick one and lose an item. What you actually want is to notice "these two were made without seeing each other" and keep both.