Hybrid Logical Clocks for Deduplication Ordering

When a deduplication log is replicated across regions, two questions arise that a single-store design never faces: which of two conflicting records came first, and when can either be expired? Wall clocks answer the second and get the first wrong; Lamport clocks answer the first and cannot help with the second. A hybrid logical clock answers both with one 64-bit value. This runbook implements the mechanism introduced in clock skew & time ordering in distributed systems.

Prerequisites. A multi-region or multi-store deduplication design where records are exchanged between nodes, and a transport you can add a header or field to.

Step 1 — What an HLC guarantees

An HLC timestamp is a pair: a physical component in milliseconds, and a logical counter that breaks ties within a millisecond and absorbs skew. Two rules define it.

Causality preserved across a message, whatever the clocks say Node A, whose wall clock reads ahead, stamps an event and sends it. Node B, whose wall clock lags by a minute, merges the received stamp. B's resulting stamp exceeds A's because the physical component is pulled forward and the logical counter increments, so the happens-before relation holds despite the skew. node A (clock ahead) (1000, 0) node B (clock 60 s behind) (1000, 1) (1000, 2) B's stamps exceed A's — happens-before holds B's own wall clock never enters the comparison
  • Causality. If event a happened before event b — same node, or b received a message sent after a — then hlc(a) < hlc(b). This holds no matter how badly the clocks disagree.
  • Bounded drift. The physical component never falls behind the node’s own wall clock, and never runs ahead of the maximum wall clock in the system. So an HLC value is always within the fleet’s skew bound of real time.
Three clock models against two requirements A two-column comparison across three rows. The wall clock row is marked as failing causal ordering under skew but succeeding at closeness to real time. The Lamport clock row succeeds at causal ordering but fails at closeness to real time, so it cannot drive a time to live. The hybrid logical clock row succeeds at both, at a cost of eight bytes carried on every message. orders events causally usable for TTL / audit wall clock time.Now() NO — skew reorders events YES Lamport clock counter only YES NO — 4,271 means nothing in seconds hybrid logical 48-bit ms + 16-bit counter YES — unconditionally YES — within the fleet skew bound Cost: 8 bytes on every message and every stored record.

Step 2 — Implement Now and Update

Two operations. Now() stamps a locally generated event; Update() merges a stamp received from a peer.

type HLC struct {
    mu       sync.Mutex
    physical int64  // milliseconds
    logical  uint16
}

// Now stamps a local event.
func (c *HLC) Now() (int64, uint16) {
    c.mu.Lock()
    defer c.mu.Unlock()
    wall := time.Now().UnixMilli()
    if wall > c.physical {
        c.physical, c.logical = wall, 0
    } else {
        c.logical++                 // same or regressed wall clock: advance logically
    }
    return c.physical, c.logical
}

// Update merges a peer's stamp, preserving happens-before across the message.
func (c *HLC) Update(pPhys int64, pLog uint16) (int64, uint16) {
    c.mu.Lock()
    defer c.mu.Unlock()
    wall := time.Now().UnixMilli()
    switch {
    case wall > c.physical && wall > pPhys:
        c.physical, c.logical = wall, 0            // wall clock leads both
    case pPhys > c.physical:
        c.physical, c.logical = pPhys, pLog+1      // peer leads
    case c.physical == pPhys:
        if pLog > c.logical { c.logical = pLog }   // same millisecond: take the max
        c.logical++
    default:
        c.logical++                                // we lead: just advance
    }
    return c.physical, c.logical
}
import threading, time

class HLC:
    def __init__(self) -> None:
        self._lock, self._physical, self._logical = threading.Lock(), 0, 0

    def now(self) -> tuple[int, int]:
        with self._lock:
            wall = time.time_ns() // 1_000_000
            if wall > self._physical:
                self._physical, self._logical = wall, 0
            else:
                self._logical += 1
            return self._physical, self._logical

    def update(self, p_phys: int, p_log: int) -> tuple[int, int]:
        with self._lock:
            wall = time.time_ns() // 1_000_000
            if wall > self._physical and wall > p_phys:
                self._physical, self._logical = wall, 0
            elif p_phys > self._physical:
                self._physical, self._logical = p_phys, p_log + 1
            elif self._physical == p_phys:
                self._logical = max(self._logical, p_log) + 1
            else:
                self._logical += 1
            return self._physical, self._logical

The logical counter is what absorbs skew. When a node’s wall clock lags behind the messages it receives, physical is pulled forward by the peer and logical increments — ordering stays correct and the drift becomes visible.

Step 3 — Pack into 64 bits

// 48 bits physical (ms, good to year 10889) | 16 bits logical (65,536/ms/node).
func Pack(phys int64, log uint16) int64 { return phys<<16 | int64(log) }
func Unpack(v int64) (int64, uint16)    { return v >> 16, uint16(v & 0xFFFF) }
-- One bigint column, sortable as an integer, indexable as a primary key component.
ALTER TABLE dedup_log ADD COLUMN hlc bigint NOT NULL;
CREATE INDEX dedup_log_hlc ON dedup_log (hlc);

-- Recover a human-readable time without unpacking in the application.
SELECT to_timestamp((hlc >> 16) / 1000.0) AS approx_time, hlc & 65535 AS counter
  FROM dedup_log ORDER BY hlc DESC LIMIT 10;

Because the physical part occupies the high bits, ordinary integer comparison gives the correct causal order — no custom collation, no composite index, no application-side sort.

Step 4 — Propagate on every message

// Outbound: stamp and attach.
phys, logi := clock.Now()
msg.Headers = append(msg.Headers,
    kafka.Header{Key: "hlc", Value: []byte(strconv.FormatInt(Pack(phys, logi), 10))})

// Inbound: merge BEFORE processing, so any stamp generated during processing
// is causally after the message that triggered it.
if h := headerValue(msg, "hlc"); h != "" {
    if v, err := strconv.ParseInt(h, 10, 64); err == nil {
        p, l := Unpack(v)
        clock.Update(p, l)
    }
}

Merge on receipt, before doing the work. Merging afterwards breaks the happens-before relation for anything the handler stamps, which is precisely the guarantee you added the HLC to get.

Conflict resolution then becomes a comparison rather than a judgement call:

-- Last-writer-wins on the deduplication record, ordered causally rather than
-- by whichever region's clock happened to be ahead.
INSERT INTO dedup_log (scoped_key, hlc, region, outcome)
VALUES ($1, $2, $3, $4)
ON CONFLICT (scoped_key) DO UPDATE
   SET hlc = EXCLUDED.hlc, region = EXCLUDED.region, outcome = EXCLUDED.outcome
 WHERE dedup_log.hlc < EXCLUDED.hlc;      -- older causal stamp never overwrites

Step 5 — Alert on a growing counter

A healthy HLC spends almost all its time with logical at 0 or 1. A counter that climbs means physical time is advancing more slowly than causality — the direct signature of clock skew or of a node whose NTP has stopped working.

# The skew alarm nobody else gives you: causality outrunning wall time.
max_over_time(hlc_logical_counter[5m]) > 100
// Export it on every stamp.
phys, logi := clock.Now()
hlcLogicalGauge.Set(float64(logi))
hlcPhysicalSkew.Set(float64(time.Now().UnixMilli() - phys))   // negative = we are behind

Verification and testing

Confirm causality holds under injected skew.

def test_causality_survives_skew():
    a, b = HLC(), HLC()
    with freeze_clock(b, offset_ms=-60_000):        # node B is 60 s behind
        pa = a.now()
        pb = b.update(*pa)                          # B receives A's message
        assert pack(*pb) > pack(*pa)                # happens-before preserved
        pb2 = b.now()
        assert pack(*pb2) > pack(*pb)               # B's own order preserved

Confirm monotonicity under a clock step.

# Step the container clock backwards and assert stamps never regress.
docker exec -u root app date -s '-30 seconds'
python3 -c "
from hlc import clock, pack
prev = 0
for _ in range(10000):
    v = pack(*clock.now())
    assert v > prev, 'HLC regressed'
    prev = v
print('monotonic across a backward step')"

Confirm the packed value sorts correctly in SQL.

SELECT hlc, to_timestamp((hlc >> 16)/1000.0) AS t, hlc & 65535 AS c
  FROM dedup_log ORDER BY hlc LIMIT 20;
-- expect: timestamps non-decreasing, counter resetting each new millisecond

Failure scenarios and debugging

Failure Scenario Remediation Steps Observability Hooks
Peer stamp merged after processing, so events generated by a handler are not causally after the message that caused them Call Update at the top of the handler, before any work. Assert the ordering in the test above. hlc_causality_violation_total from a consistency checker comparing stored stamps against message order
One node’s clock is hours ahead, and its stamp drags the whole fleet’s physical component forward permanently Bound the accepted peer physical component: reject a stamp more than the fleet’s maximum skew ahead of local wall time, and alert. HLC has no natural defence against a wildly wrong peer. hlc_peer_rejected_total; hlc_physical_skew_ms per node, alert above 60,000
Logical counter overflows 16 bits because one node emits more than 65,536 events in a millisecond Widen the counter to 32 bits and use a 96-bit stamp, or shard the clock per partition so no single instance exceeds the rate. hlc_logical_counter p99; alert above 10,000, long before the ceiling
HLC adopted but conflict resolution still compares created_at, so ordering is unchanged Grep for wall-clock comparisons on replicated tables and replace with hlc. Adding the column without changing the comparison achieves nothing. A schema-and-query audit listing every ordering predicate on replicated tables
8 bytes per event added to a 5,000-per-second log without capacity planning, and storage grows 30 GB per week Model the cost before enabling globally; apply the HLC only on the cross-region path that needs it, not to every local record. dedup_log table size growth rate versus the pre-HLC baseline
Packed into one sortable bigint A sixty-four bit word split into a forty-eight bit millisecond physical component in the high bits and a sixteen bit logical counter in the low bits. Because the physical part occupies the high bits, ordinary integer comparison yields the correct causal order, so no custom collation or composite index is required. 48 bits — physical milliseconds 16 bits — counter high bits low bits Physical time in the high bits means plain integer ordering is causal ordering. One bigint column, one B-tree, no custom collation.

SRE / observability checklist

  1. hlc_logical_counter — Gauge of the logical component at each stamp. A p99 above 100 means physical time is lagging causality; it is the best skew alarm you will have.
  2. hlc_physical_skew_ms — Gauge of wall_clock - hlc_physical. Persistently negative means this node’s clock trails the fleet.
  3. hlc_peer_rejected_total — Counter of peer stamps rejected as implausibly far ahead. Any value identifies a node with a broken clock.
  4. hlc_causality_violation_total — Counter from a periodic checker comparing stored stamps against known message order. Must be zero.
  5. hlc column on every replicated record — And in the structured log, so a conflict can be explained without guessing which region wrote last.
  6. node_clock_offset_seconds — The underlying NTP metric. An HLC makes skew survivable, not invisible; keep watching the source.