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
ehappened beforef, thenl.e < l.f; - like a physical clock, it stays close to real time:
l.eis close to the wall-clock time ofe; - 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).
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 asOperationIdincrdt_lf; - a full counter moves
lforward 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.