Why does last-writer-wins by device clock lose edits, and how do hybrid logical clocks fix the ordering?

26.6.3 · L8 · Interview

Predict first

Device A’s clock is an hour fast. B sees A’s edit and then edits again. Who wins?

struct HLC: Comparable { var l: Int; var c: Int
    static func < (a: HLC, b: HLC) -> Bool { (a.l, a.c) < (b.l, b.c) } }
final class Device {
    let skew: Int; var hlc = HLC(l: 0, c: 0)
    init(skew: Int) { self.skew = skew }
    func wall(_ real: Int) -> Int { real + skew }
    func tick(_ real: Int) -> HLC { let w = wall(real); if w > hlc.l { hlc = HLC(l: w, c: 0) } else { hlc.c += 1 }; return hlc }
    func receive(_ m: HLC, _ real: Int) { let w = wall(real); let l = max(hlc.l, m.l, w)
        hlc = HLC(l: l, c: l == hlc.l && l == m.l ? max(hlc.c, m.c) + 1 : l == hlc.l ? hlc.c + 1 : l == m.l ? m.c + 1 : 0) }
}
let a = Device(skew: 3600), b = Device(skew: 0)          // A's clock runs one hour fast
// t=100: A renames the note ("from A"); t=150: B receives it; t=200: B renames it again ("from B"), which is causally later
let aEdit = a.tick(100); let aWall = a.wall(100)
b.receive(aEdit, 150)
let bEdit = b.tick(200); let bWall = b.wall(200)
print("wall clock LWW keeps:", aWall > bWall ? "from A (the OLDER edit)" : "from B")
print("HLC LWW keeps:", aEdit > bEdit ? "from A" : "from B (the causally later edit)", "| B stamp", bEdit.l, bEdit.c)
// a truly concurrent pair is still ordered by HLC, deterministically on both devices
let x = Device(skew: 0), y = Device(skew: 0)
let hx = x.tick(500), hy = y.tick(500)
print("two devices stamping the same instant get identical HLCs:", hx == hy, "-> add the device id as the final tie-break")

Wall-clock LWW keeps A’s older edit; HLC keeps B’s causally later edit (stamp 3700, 2)
Both keep B
Both keep A

Mental model. A rumour that carries the highest date it has heard. Anyone who repeats it has to date their version at least that late, however their own watch reads.

Last-writer-wins (LWW) needs a total order of writes, and the obvious order is the device’s wall-clock time. Device clocks are wrong: users change them, networks adjust them, and they drift. In the check device A runs an hour fast. It edits a note at real time 100, device B receives that edit at 150 and edits it again at 200, a change that happened after and with knowledge of A’s edit. Wall-clock LWW compares A’s stamp (3700) with B’s (200) and keeps A’s older edit, so the user’s later change is silently lost. The ordering you want is causal: if B saw A’s write, B’s write must sort after it, whatever the clocks say.

A hybrid logical clock (HLC) keeps a pair (l, c): l follows the largest physical time seen so far and c is a counter for events within the same l. On a local event it uses max(l, wall) and bumps c if the time did not advance; on receiving a message it takes the max of its own l, the sender’s l and its wall clock, and increments c. In the check B’s second edit is stamped (3700, 2), greater than A’s, so the later edit wins. Two devices that stamp the same instant produce identical pairs, so add the device id as a final tie-break to get a total order. HLCs stay close to real time (useful for display and expiry) but never go backwards, at the price that one device with a wildly fast clock drags everyone’s l forward; servers should reject stamps too far in the future. Alternatives: version vectors detect true concurrency but cannot pick a winner, and a server-assigned sequence is simplest when you have a server and are online (Q340).

Receiving a message advances the logical clock past the sender’s, so later edits sort later.

Common traps

Trusting Date() for conflict resolution. One wrong clock decides who wins for everyone.
Accepting any timestamp from a client. Cap how far ahead of the server a stamp may be.

They might follow up with

HLC or version vector? A version vector tells you whether two writes were concurrent; an HLC gives you a single deterministic order to pick a winner.
Does an HLC fix merge semantics? No; for fields like counters or text use a CRDT or a merge rule, not LWW (Q340).

Why does last-writer-wins by device clock lose edits, and how do hybrid logical clocks fix the ordering?

Predict first

Common traps

They might follow up with

Related questions