Skip to main content

Time: the hybrid logical clock

Peers that edit offline need to agree on an order of events, and they cannot trust the wall clock for it: phones drift, users change the time, two edits land in the same millisecond. Every change in crdt_lf is stamped with a hybrid logical clock (HLC) from hlc_dart, which combines the two kinds of clock:

  • like a logical clock, it captures causality: if event e happened before f, then l.e < l.f;
  • like a physical clock, it stays close to real time: l.e is close to the wall-clock time of e;
  • it fits in 64 bits: 48 bits of milliseconds since the Unix epoch, 16 bits of counter;
  • it works peer to peer, with no central server.

It follows the paper Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases.

How the engine uses it​

  • Each change gets an OperationId: the peer id plus the HLC. It is unique, and it gives a total order that respects causality.
  • When a handler replays its history, it walks the changes sorted by (HLC, author). Two peers that hold the same changes replay them in the same order, and reach the same state. That order is also what "last writer wins" means in a last-writer-wins handler.
  • When a document imports a change or a snapshot, it moves its own clock past it. That is why a restored document never mints an operation id twice (see Peer identity).
The order cannot detect concurrency

If e happened before f, then e < f. The reverse does not hold: e < f also when e and f are concurrent. So the HLC order alone cannot tell whether two events are concurrent. The document keeps a causal graph for that (see Documents and changes).

Using hlc_dart on its own​

The clock is a package of its own, with zero dependencies, so you can use it outside CRDTs too.

dart pub add hlc_dart
import 'dart:io';

import 'package:hlc_dart/hlc_dart.dart';

final clock = HybridLogicalClock.now();

// Another peer has its own clock: here it lives in the same program.
final received = HybridLogicalClock.now();

// A local event: an edit, a write, anything this peer does.
clock.localEvent(DateTime.now().millisecondsSinceEpoch);
stdout.writeln(clock); // <milliseconds>.<counter>

// A message from the other peer carries its clock.
clock.receiveEvent(DateTime.now().millisecondsSinceEpoch, received);

// After the receive, the message comes before this clock.
final ordered = received.happenedBefore(clock);
stdout.writeln(ordered); // true

// 64 bits, or 8 big-endian bytes.
final fromInt = HybridLogicalClock.fromInt64(clock.toInt64());
final fromBytes = HybridLogicalClock.fromUint8List(clock.toUint8List());
stdout.writeln(fromInt == clock && fromBytes == clock); // true

isConcurrentWith only checks that two timestamps are equal: the clock alone cannot tell that two events are concurrent (see the note above).

What it offers:

  • local events, and messages exchanged between peers;
  • a total order that respects causality (compareTo, <, >, max, min);
  • serialization to and from 64-bit integers (toInt64 / fromInt64);
  • a compact 8-byte big-endian form (toUint8List / fromUint8List), used as a building block of larger binary frames, such as OperationId in crdt_lf;
  • a full counter moves l forward by 1 ms, so the 8-byte form never wraps;
  • drift detection;
  • mutable and immutable methods for every operation.

A complete example is in the repository, and so are the benchmarks.