Version Vectors and Hybrid Logical Clocks for Mobile Sync Ordering

Two devices edit the same record while both are offline. When they reconnect, the sync layer must decide whether one edit happened after the other or whether they happened independently and must be reconciled. A timestamp seems like the obvious answer, and it is wrong for a reason that no amount of clock discipline fixes: the ordering that matters is causal, and a clock measures elapsed time, not causality.

Version vectors answer the causal question exactly, at a storage cost proportional to the number of replicas. Hybrid logical clocks answer a weaker question at constant cost, and they answer it in a way that stays close to wall-clock time so that the numbers remain useful for other purposes. Choosing between them is a choice about what the sync layer is allowed to conclude when it sees two edits.

The failure of timestamps

A device’s clock is set by the user, corrected by the network, and perturbed by suspend and resume. Two devices can differ by minutes without either being broken, and a single device’s clock can move backward across a daylight-saving transition or a manual correction. Ordering by timestamp therefore orders by an estimate of when the write happened, and the estimate is not monotonic.

Even with perfect clocks, timestamps answer the wrong question. If device A edits a record at 10:00:00 and device B edits the same record at 10:00:01 without having seen A’s edit, the second edit is not a successor of the first; it is concurrent with it. Ordering by time would silently discard A’s edit as older, which loses data. Causality distinguishes the two cases: B’s edit is a successor only if B had seen A’s edit.

Lamport’s happens-before relation captures this with two rules. Events on the same process are ordered. A send happens before its matching receive. The transitive closure of those two rules is the causal order, and any two events that are not related by it are concurrent. A timestamp scheme that respects the relation is a logical clock; a timestamp scheme that measures real time is not one.

What a version vector records

A version vector is one counter per replica. Each replica increments its own entry on every local write, and a write that is sent to another replica carries the sender’s whole vector. On receipt, the receiver merges by taking the element-wise maximum and then increments its own entry.

Comparing two vectors gives exactly three outcomes. If every element of A is less than or equal to the corresponding element of B and at least one is strictly less, then A happened before B. If every element of B is less than or equal to A with one strict, then B happened before A. If neither holds, the two are concurrent: there exists a replica whose counter is higher in A and another whose counter is higher in B, which is precisely the evidence that each side saw writes the other did not.

That third case is the useful one, and it is why the structure cannot be replaced by a single number. A single counter merged by maximum loses the information about which replica contributed what, so two concurrent edits collapse to one and the conflict disappears rather than being reported.

def compare(a, b):
    """Return 'before', 'after', 'equal', or 'concurrent' for two version vectors."""
    keys = set(a) | set(b)
    a_le = all(a.get(k, 0) <= b.get(k, 0) for k in keys)
    b_le = all(b.get(k, 0) <= a.get(k, 0) for k in keys)
    if a_le and b_le:
        return 'equal'
    if a_le:
        return 'before'
    if b_le:
        return 'after'
    return 'concurrent'   # each side has a counter the other lacks

def merge(a, b):
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in set(a) | set(b)}

The cost is the number of replicas. A user with three devices carries three counters per record; a shared document with fifty collaborators carries fifty. Storing the vector per row is the naive approach and it scales badly: a 50-entry vector of four-byte counters is 200 bytes per row, which on a page-oriented store is a meaningful fraction of a 4096-byte page and pushes rows toward overflow chains.

Two techniques reduce this. The vector can be stored once per document rather than per row, with rows inheriting the document’s version, which works when edits are at document granularity. Or the vector can be replaced by a dotted version vector (a compact summary plus a set of exceptional dots for writes not yet summarised), which bounds the per-record size at the cost of a garbage-collection step that decides when a dot can be folded into the summary.

What a hybrid logical clock adds

A hybrid logical clock, as described by Kulkarni and colleagues, carries a physical component and a logical counter. On a local event it reads the wall clock; if the reading is greater than the stored physical component, it takes the reading and resets the counter to zero, otherwise it keeps the physical component and increments the counter. On receiving a message with components (m, c_m) it takes l = max(own physical component, m, local clock reading). If l equals both the own component and m, the new counter is one more than the larger of the two counters; if l equals only one of them, the counter is one more than that one’s; if the local clock reading is what supplied l, the counter resets to zero.

The result is a timestamp whose physical part is never far from real time and whose ordering respects causality: if event A happens before event B, A’s timestamp is strictly less than B’s. The counter breaks ties within a physical millisecond and absorbs clock skew: a device whose clock is behind will, on receiving a message with a higher physical component, adopt that component and continue from there.

The constant-size property is the attraction. A hybrid timestamp is a fixed-width value, 64 bits in the common encoding, split between a physical component in milliseconds and a counter, regardless of how many replicas exist. On a phone, where storage per row is charged against a page budget and where the number of devices a user owns is not knowable in advance, that is a decisive advantage over a vector.

What it does not provide is conflict detection. Two concurrent edits receive two timestamps, and one is smaller. The ordering is arbitrary with respect to causality (both could have been generated in either order), so a total order is imposed on events that are actually concurrent. The sync layer can order them and pick a winner, but it cannot know that a conflict occurred unless it also tracks something else.

Detecting conflict without a vector

There is a middle path that keeps the constant size and recovers detection: attach the hybrid timestamp of the last write the client had seen when it made its own. This is a one-element causal dependency rather than a full vector. If the incoming edit’s “seen” timestamp is at least the current record’s timestamp, the edit was made with knowledge of the current state and is a legitimate successor. If it is less, the edit was made against an older state and is concurrent.

The scheme is not exact. A client that saw a state through a path the server does not know about can present a “seen” value that appears older than it is, and the server will report a false conflict. In practice the false conflicts are resolved by the same merge policy that would have applied anyway, so the cost is a wasted merge rather than a lost edit. The false negatives, a genuinely concurrent edit classified as a successor, are the dangerous direction, and they occur when the client’s “seen” value happens to be current despite the client not having seen the latest edit. That requires the latest edit to have the same timestamp, which the counter makes unlikely but not impossible.

Storage and transport consequences

Both mechanisms impose a per-record write on every mutation, which interacts with the durability costs described in fsync and journal modes. A version vector update is a read-modify-write of a blob; a hybrid timestamp update is a single integer plus a counter. The latter is cheaper in dirty pages, and on a device where each transaction costs a barrier, that difference is real.

Transport has the opposite profile. A version vector sent to the server is O(replicas) per record, and a pull of ten thousand records carries ten thousand vectors. A hybrid timestamp is O(1) per record. The vector’s cost is paid in bandwidth per sync; the clock’s cost is paid in conflicts that must be resolved by policy rather than detected exactly.

A workable combination is to use hybrid timestamps for ordering and last-seen tracking during normal operation, and to store a full version vector only at coarse granularity (per document or per collection) where conflicts are expensive enough to be worth detecting precisely. The record level gets the cheap ordering; the document level gets the exact causality. That combination is a compromise rather than a theorem: it accepts that a per-record conflict may be resolved by policy, and reserves exact detection for the level at which the merge is a user-visible decision.

Clocks that go backward

Every scheme built on a physical component must handle a clock that moves backward. A hybrid clock that reads a wall time lower than its stored physical component keeps the stored component and increments the counter, so its own timestamps remain monotonic. That handles the local case.

The distributed case is harder: a device whose clock was set two days forward will produce timestamps two days in the future, and every other device that receives one will advance its own physical component to match. The whole system’s clock effectively jumps forward, and it does not come back until real time catches up. This is why implementations bound how far a received timestamp may advance the local physical component, and why a timestamp beyond that bound is treated as suspect rather than adopted.

The alternative is to distrust the physical component entirely and to treat it as a hint, which reduces the scheme to a Lamport clock with a wider counter. That is a legitimate choice: the ordering remains correct, the constant size remains, and the only loss is the correlation with real time that made the timestamps useful for display and for retention policies.

Either way, the change log must record the ordering value it used, because a sync decision made with one scheme cannot be re-derived later with another. Migrating from timestamps to hybrid clocks means either keeping the old values and translating at the boundary, or accepting a one-time reconciliation in which every record’s order is recomputed from the log.