Hybrid Logical Clock

hlc_dart_badge pub points pub likes codecov ci_badge License: MIT pub publisher

A hybrid logical clock (HLC) for Dart: a causal order of events across peers, close to physical time, in 64 bits, with no central server. Based on Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases.

Read the full documentation

πŸ“– The full documentation, and how the CRDT engine uses this clock, is on mattiapispisa.it/crdt.

Features

  • πŸ”— Causality: if e happened before f, then e < f
  • πŸ•°οΈ Close to physical time: 48 bits of milliseconds, 16 bits of counter
  • πŸ“‘ Peer to peer: local events and messages between peers, no central server
  • πŸ”’ Total order: compareTo, <, >, max, min
  • πŸ’Ύ Compact: a 64-bit integer, or 8 big-endian bytes; a full counter never wraps
  • 🧭 Drift detection
  • πŸͺΆ Zero dependencies
  • βž• …and more: everything else is in the documentation

Quick start

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

The program is a recipe, tested in CI, and the benchmarks are on the documentation site.

Used by

crdt_lf stamps every change with this clock: how it uses it.

Roadmap

Roadmap: done, in progress, to do

πŸ—ΊοΈ The project board shows what is done, what is in progress and what comes next, for this package and the rest of the workspace. Missing something? Open an issue: requests go on the board too.

Apps

Packages

Other bricks of the crdt "system" are:

Libraries

hlc_dart