System Design (High-Level Design) Module 10 – Consistency, time and coordination
Clocks and ordering: Lamport, vector and HLC
Why wall clocks cannot order events across servers, how Lamport, vector and hybrid logical clocks order them, and why timeouts need a monotonic clock.
What you will learn
- Explain why wall-clock timestamps from different machines cannot order events
- Compute Lamport and vector timestamps for a message diagram and identify concurrent events
- Explain how a hybrid logical clock stays causal while staying close to physical time
- Choose a monotonic clock for timeouts, leases and durations
Before you start
What you’ll learn · Before you start
What you will learn
- Explain why wall-clock timestamps from different machines cannot order events
- Compute Lamport and vector timestamps for a message diagram and identify concurrent events
- Explain how a hybrid logical clock stays causal while staying close to physical time
- Choose a monotonic clock for timeouts, leases and durations
Before you start
On this page
Merge the logs of a web server and a payments server by timestamp, and the payments server seems to receive a charge request 30 ms before the order that caused it arrived. Every server has a wall clock, but no two agree exactly, so the timestamps of two machines can put an effect before its cause.
Systems that must order events use clocks built for ordering. Lamport clock: A logical clock: a counter that every message carries, which gives every event a number that is always larger for an effect than for its cause. give every event a counter that is always larger for an effect than for its cause. vector clock: One counter per process, carried with every message, counting the events of each process that the sender knows of. Comparing two vector clocks shows whether one event could have caused the other or whether they are concurrent. keep one counter per process, which also shows when two events are concurrent. hybrid logical clock (HLC): A timestamp that adds a counter to physical time, so that it stays causal like a logical clock and close to the time of day. (HLC) add a counter to physical time, so their timestamps stay causal and close to real time. Google’s Spanner trusts physical time instead, waiting out the measured uncertainty of its TrueTime clocks before each commit. Timeouts and leases need yet another kind: a monotonic clock: A clock that only measures elapsed time, for timeouts, leases and durations, rather than telling the time of day., which only measures elapsed time.
Wall clocks cannot order events across machines
A wall clock is a quartz oscillator corrected over the network. NTP (Network Time Protocol): The protocol that synchronises a machine's clock with time servers over the network, correcting it by slewing it gradually or, past a threshold, by stepping it, which can move a clock backwards. keeps a client within a few hundred microseconds of its server on a fast local network, and within a few tens of milliseconds when it polls only every few hours. It corrects a clock by slewing it gradually or, past a threshold, by stepping it to the right time at once (RFC 5905). Close is not equal, and a step can move a clock backwards. Any clock skew: The difference between the readings of two machines' clocks at the same moment. Timestamps from two machines cannot order events that happen closer together than their skew. larger than the gap between a cause and its effect reorders them, and between two servers that gap can be well under a millisecond. Follow one order through two servers, top to bottom in the order things happened:
One order, two clocks: the effect carries the earlier timestamp
Text description of the diagram
The diagram is a sequence of messages between two servers, from top to bottom in the order the events really happened. The web server's clock is right; the payments server's clock is 50 ms slow.
- The web server receives order 41 and logs it with the timestamp 1000.
- The web server sends a charge request to the payments server, logged at 1005.
- The payments server receives the request and logs it at 970, because its clock is 50 ms behind: the effect carries a timestamp 35 ms earlier than its cause.
- The payments server approves the card and replies, logged at 1010.
- The web server confirms order 41, logged at 1081.
Sorting the two logs by timestamp would put "request received" first, before the order even arrived.
The program merges the two logs by wall-clock time. Beside each event it prints a Lamport time, a counter that every message carries: each server adds one for every event, and a receiver first sets its counter above the one in the message.
Python 3.14 · main.py
# One order logged on two servers, in the order things happened. The payments server's clock
# runs 50 ms slow.
EVENTS = [ # (wall-clock ms, server, event, the event whose message it receives)
(1000, "web", "order 41 received", None),
(1005, "web", "charge request sent", None),
(970, "payments", "charge request received", 1),
(1010, "payments", "card approved, reply sent", None),
(1080, "web", "reply received", 3),
(1081, "web", "order 41 confirmed", None),
]
clock = {"web": 0, "payments": 0}
log = []
for wall, server, event, source in EVENTS:
if source is not None: # a message carries its sender's Lamport time
clock[server] = max(clock[server], log[source][1])
clock[server] += 1
log.append((wall, clock[server], server, event))
print("merged by wall clock, with each event's Lamport time:")
for wall, lamport, server, event in sorted(log):
print(f" {wall:>4} ms Lamport {lamport} {server}: {event}")In Python: The log entries are tuples, so sorted(log) orders them by their first item, the wall-clock time.
Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
// [wall-clock ms, server, event, the event whose message it receives]
const EVENTS = [
[1000, "web", "order 41 received", null],
[1005, "web", "charge request sent", null],
[970, "payments", "charge request received", 1],
[1010, "payments", "card approved, reply sent", null],
[1080, "web", "reply received", 3],
[1081, "web", "order 41 confirmed", null],
];
const clock = { web: 0, payments: 0 };
const log = [];
for (const [wall, server, event, source] of EVENTS) {
// a message carries its sender's Lamport time
if (source !== null) clock[server] = Math.max(clock[server], log[source][1]);
clock[server] += 1;
log.push([wall, clock[server], server, event]);
}
console.log("merged by wall clock, with each event's Lamport time:");
for (const [wall, lamport, server, event] of [...log].sort((a, b) => a[0] - b[0])) {
console.log(` ${String(wall).padStart(4)} ms Lamport ${lamport} ${server}: ${event}`);
}In JavaScript: The clocks are kept in an object keyed by server name, and padStart lines up the times.
Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs
Java 25 LTS · Main.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;
public class Main {
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow. source: the event whose message it receives, or -1.
record Event(int wall, String server, String what, int source) {}
record Entry(int wall, int lamport, String server, String what) {}
static final List<Event> EVENTS =
List.of(
new Event(1000, "web", "order 41 received", -1),
new Event(1005, "web", "charge request sent", -1),
new Event(970, "payments", "charge request received", 1),
new Event(1010, "payments", "card approved, reply sent", -1),
new Event(1080, "web", "reply received", 3),
new Event(1081, "web", "order 41 confirmed", -1));
public static void main(String[] args) {
Locale.setDefault(Locale.ROOT);
Map<String, Integer> clock = new HashMap<>(Map.of("web", 0, "payments", 0));
List<Entry> log = new ArrayList<>();
for (Event e : EVENTS) {
if (e.source() >= 0) { // a message carries its sender's Lamport time
clock.merge(e.server(), log.get(e.source()).lamport(), Math::max);
}
int lamport = clock.merge(e.server(), 1, Integer::sum);
log.add(new Entry(e.wall(), lamport, e.server(), e.what()));
}
System.out.println("merged by wall clock, with each event's Lamport time:");
log.stream()
.sorted(Comparator.comparingInt(Entry::wall))
.forEach(
x ->
System.out.printf(
" %4d ms Lamport %d %s: %s%n", x.wall(), x.lamport(), x.server(), x.what()));
}
}In Java: clock.merge with Math::max and then with Integer::sum applies the two Lamport rules to the map, one call each.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
// One order logged on two servers, in the order things happened. The payments
// server's clock runs 50 ms slow.
#include <algorithm>
#include <map>
#include <optional>
#include <print>
#include <string>
#include <tuple>
#include <vector>
struct Event {
int wall;
std::string server, what;
std::optional<int> source; // the event whose message it receives
};
const std::vector<Event> events = {
{1000, "web", "order 41 received", {}},
{1005, "web", "charge request sent", {}},
{970, "payments", "charge request received", 1},
{1010, "payments", "card approved, reply sent", {}},
{1080, "web", "reply received", 3},
{1081, "web", "order 41 confirmed", {}}};
int main() {
std::map<std::string, int> clock = {{"web", 0}, {"payments", 0}};
std::vector<std::tuple<int, int, std::string, std::string>> log;
for (const Event &e : events) {
if (e.source) // a message carries its sender's Lamport time
clock[e.server] = std::max(clock[e.server], std::get<1>(log[*e.source]));
log.emplace_back(e.wall, ++clock[e.server], e.server, e.what);
}
std::println("merged by wall clock, with each event's Lamport time:");
std::ranges::sort(log);
for (const auto &[wall, lamport, server, what] : log)
std::println(" {:>4} ms Lamport {} {}: {}", wall, lamport, server, what);
}In C++: Each log entry is a std::tuple, which std::ranges::sort orders by its first element, the wall-clock time.
Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main
C# 14 · .NET 10 · app.cs
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
using System.Globalization;
CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
// (wall-clock ms, server, event, the event whose message it receives)
(int Wall, string Server, string What, int? Source)[] events =
[
(1000, "web", "order 41 received", null),
(1005, "web", "charge request sent", null),
(970, "payments", "charge request received", 1),
(1010, "payments", "card approved, reply sent", null),
(1080, "web", "reply received", 3),
(1081, "web", "order 41 confirmed", null),
];
var clock = new Dictionary<string, int> { ["web"] = 0, ["payments"] = 0 };
var log = new List<(int Wall, int Lamport, string Server, string What)>();
foreach (var (wall, server, what, source) in events)
{
if (source is int s) // a message carries its sender's Lamport time
{
clock[server] = Math.Max(clock[server], log[s].Lamport);
}
clock[server]++;
log.Add((wall, clock[server], server, what));
}
Console.WriteLine("merged by wall clock, with each event's Lamport time:");
foreach (var e in log.OrderBy(e => e.Wall))
{
Console.WriteLine($" {e.Wall,4} ms Lamport {e.Lamport} {e.Server}: {e.What}");
}In C#: The pattern source is int s unwraps the nullable index only when it has a value, and {e.Wall,4} right-aligns the time.
Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs
C23 · main.c
// One order logged on two servers, in the order things happened. The payments
// server's clock runs 50 ms slow.
#include <stdio.h>
#include <stdlib.h>
enum { WEB, PAYMENTS };
static const char *const servers[] = {"web", "payments"};
typedef struct {
int wall, server;
const char *what;
int source; // the event whose message it receives, or -1
} Event;
static const Event events[] = {
{1000, WEB, "order 41 received", -1},
{1005, WEB, "charge request sent", -1},
{970, PAYMENTS, "charge request received", 1},
{1010, PAYMENTS, "card approved, reply sent", -1},
{1080, WEB, "reply received", 3},
{1081, WEB, "order 41 confirmed", -1}};
static int lamport[6];
static int by_wall(const void *a, const void *b) {
return events[*(const int *)a].wall - events[*(const int *)b].wall;
}
int main(void) {
int clock[2] = {0, 0}, order[6];
for (int i = 0; i < 6; i++) {
const Event *e = &events[i];
if (e->source >= 0 && lamport[e->source] > clock[e->server])
clock[e->server] = lamport[e->source]; // the sender's Lamport time
lamport[i] = ++clock[e->server];
order[i] = i;
}
printf("merged by wall clock, with each event's Lamport time:\n");
qsort(order, 6, sizeof order[0], by_wall);
for (int i = 0; i < 6; i++) {
const Event *e = &events[order[i]];
printf(" %4d ms Lamport %d %s: %s\n", e->wall, lamport[order[i]],
servers[e->server], e->what);
}
}In C: qsort orders an array of event indexes with a comparator that reads their wall-clock times.
Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main
PHP 8.5 · main.php
<?php
declare(strict_types=1);
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
const EVENTS = [ // [wall-clock ms, server, event, the event whose message it receives]
[1000, 'web', 'order 41 received', null],
[1005, 'web', 'charge request sent', null],
[970, 'payments', 'charge request received', 1],
[1010, 'payments', 'card approved, reply sent', null],
[1080, 'web', 'reply received', 3],
[1081, 'web', 'order 41 confirmed', null],
];
$clock = ['web' => 0, 'payments' => 0];
$log = [];
foreach (EVENTS as [$wall, $server, $event, $source]) {
if ($source !== null) { // a message carries its sender's Lamport time
$clock[$server] = max($clock[$server], $log[$source][1]);
}
$clock[$server]++;
$log[] = [$wall, $clock[$server], $server, $event];
}
echo "merged by wall clock, with each event's Lamport time:\n";
sort($log);
foreach ($log as [$wall, $lamport, $server, $event]) {
printf(" %4d ms Lamport %d %s: %s\n", $wall, $lamport, $server, $event);
}In PHP: sort orders the log arrays item by item, so the wall-clock time decides, and printf aligns the times.
Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php
Rust 1.99 · main.rs
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
// (wall-clock ms, server, event, the event whose message it receives)
const EVENTS: [(u32, &str, &str, Option<usize>); 6] = [
(1000, "web", "order 41 received", None),
(1005, "web", "charge request sent", None),
(970, "payments", "charge request received", Some(1)),
(1010, "payments", "card approved, reply sent", None),
(1080, "web", "reply received", Some(3)),
(1081, "web", "order 41 confirmed", None),
];
fn main() {
let mut clock = [0, 0]; // web, payments
let mut log: Vec<(u32, u32, &str, &str)> = Vec::new();
for (wall, server, event, source) in EVENTS {
let own = &mut clock[usize::from(server == "payments")];
if let Some(i) = source {
*own = (*own).max(log[i].1); // a message carries its sender's Lamport time
}
*own += 1;
log.push((wall, *own, server, event));
}
println!("merged by wall clock, with each event's Lamport time:");
log.sort();
for (wall, lamport, server, event) in &log {
println!(" {wall:>4} ms Lamport {lamport} {server}: {event}");
}
}In Rust: clock holds the two servers' counters, and usize::from(server == "payments") picks the right one.
Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main
TypeScript 6.0 · main.ts
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
// [wall-clock ms, server, event, the event whose message it receives]
const EVENTS: [number, string, string, number | null][] = [
[1000, "web", "order 41 received", null],
[1005, "web", "charge request sent", null],
[970, "payments", "charge request received", 1],
[1010, "payments", "card approved, reply sent", null],
[1080, "web", "reply received", 3],
[1081, "web", "order 41 confirmed", null],
];
const clock: Record<string, number> = { web: 0, payments: 0 };
const log: [number, number, string, string][] = [];
for (const [wall, server, event, source] of EVENTS) {
// a message carries its sender's Lamport time
if (source !== null) clock[server] = Math.max(clock[server], log[source][1]);
clock[server] += 1;
log.push([wall, clock[server], server, event]);
}
console.log("merged by wall clock, with each event's Lamport time:");
for (const [wall, lamport, server, event] of [...log].sort((a, b) => a[0] - b[0])) {
console.log(` ${String(wall).padStart(4)} ms Lamport ${lamport} ${server}: ${event}`);
}In TypeScript: The event and log rows are tuple types, and a Record maps each server to its Lamport clock.
Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts
Go 1.27 · main.go
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
package main
import (
"cmp"
"fmt"
"slices"
)
// Source is the index of the event whose message it receives, or -1.
var events = []struct {
Wall int
Server, What string
Source int
}{
{1000, "web", "order 41 received", -1},
{1005, "web", "charge request sent", -1},
{970, "payments", "charge request received", 1},
{1010, "payments", "card approved, reply sent", -1},
{1080, "web", "reply received", 3},
{1081, "web", "order 41 confirmed", -1},
}
type entry struct {
wall, lamport int
server, what string
}
func main() {
clock := map[string]int{"web": 0, "payments": 0}
var log []entry
for _, e := range events {
if e.Source >= 0 { // a message carries its sender's Lamport time
clock[e.Server] = max(clock[e.Server], log[e.Source].lamport)
}
clock[e.Server]++
log = append(log, entry{e.Wall, clock[e.Server], e.Server, e.What})
}
fmt.Println("merged by wall clock, with each event's Lamport time:")
slices.SortFunc(log, func(a, b entry) int { return cmp.Compare(a.wall, b.wall) })
for _, x := range log {
fmt.Printf(" %4d ms Lamport %d %s: %s\n", x.wall, x.lamport, x.server, x.what)
}
}In Go: cmp.Compare orders the entries by wall-clock time, and the built-in max takes the larger counter.
Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
// (wall-clock ms, server, event, the event whose message it receives)
let events: [(wall: Int, server: String, what: String, source: Int?)] = [
(1000, "web", "order 41 received", nil),
(1005, "web", "charge request sent", nil),
(970, "payments", "charge request received", 1),
(1010, "payments", "card approved, reply sent", nil),
(1080, "web", "reply received", 3),
(1081, "web", "order 41 confirmed", nil),
]
func padded(_ n: Int) -> String {
String(repeating: " ", count: max(0, 4 - String(n).count)) + String(n)
}
var clock = ["web": 0, "payments": 0]
var log: [(wall: Int, lamport: Int, server: String, what: String)] = []
for e in events {
var lamport = clock[e.server, default: 0]
if let source = e.source { // a message carries its sender's Lamport time
lamport = max(lamport, log[source].lamport)
}
lamport += 1
clock[e.server] = lamport
log.append((e.wall, lamport, e.server, e.what))
}
print("merged by wall clock, with each event's Lamport time:")
for x in log.sorted(by: { $0.wall < $1.wall }) {
print(" \(padded(x.wall)) ms Lamport \(x.lamport) \(x.server): \(x.what)")
}In Swift: Without Foundation, Swift has no way to pad a number, so padded adds the spaces itself.
Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main
Ruby 4.0 · main.rb
# frozen_string_literal: true
# One order logged on two servers, in the order things happened. The payments server's clock
# runs 50 ms slow.
EVENTS = [ # [wall-clock ms, server, event, the event whose message it receives]
[1000, 'web', 'order 41 received', nil],
[1005, 'web', 'charge request sent', nil],
[970, 'payments', 'charge request received', 1],
[1010, 'payments', 'card approved, reply sent', nil],
[1080, 'web', 'reply received', 3],
[1081, 'web', 'order 41 confirmed', nil]
].freeze
clock = { 'web' => 0, 'payments' => 0 }
log = []
EVENTS.each do |wall, server, event, source|
clock[server] = [clock[server], log[source][1]].max if source # the sender's Lamport time
clock[server] += 1
log << [wall, clock[server], server, event]
end
puts "merged by wall clock, with each event's Lamport time:"
log.sort.each do |wall, lamport, server, event|
puts " #{wall.to_s.rjust(4)} ms Lamport #{lamport} #{server}: #{event}"
endIn Ruby: Arrays compare item by item, so log.sort orders the entries by their wall-clock time.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
data class Event(
val wall: Int,
val server: String,
val what: String,
val source: Int?, // the event whose message it receives
)
data class Entry(
val wall: Int,
val lamport: Int,
val server: String,
val what: String,
)
val events =
listOf(
Event(1000, "web", "order 41 received", null),
Event(1005, "web", "charge request sent", null),
Event(970, "payments", "charge request received", 1),
Event(1010, "payments", "card approved, reply sent", null),
Event(1080, "web", "reply received", 3),
Event(1081, "web", "order 41 confirmed", null),
)
fun main() {
val clock = mutableMapOf("web" to 0, "payments" to 0)
val log = mutableListOf<Entry>()
for (e in events) {
var lamport = clock.getValue(e.server)
if (e.source != null) lamport = maxOf(lamport, log[e.source].lamport) // the sender's time
clock[e.server] = ++lamport
log += Entry(e.wall, lamport, e.server, e.what)
}
println("merged by wall clock, with each event's Lamport time:")
for (x in log.sortedBy { it.wall }) {
val wall = x.wall.toString().padStart(4)
println(" $wall ms Lamport ${x.lamport} ${x.server}: ${x.what}")
}
}In Kotlin: getValue reads a counter that must exist, and ++lamport adds one before the value is stored.
Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
Dart 3.13 · main.dart
// One order logged on two servers, in the order things happened. The payments server's clock
// runs 50 ms slow.
// (wall-clock ms, server, event, the event whose message it receives)
const events = [
(1000, 'web', 'order 41 received', null),
(1005, 'web', 'charge request sent', null),
(970, 'payments', 'charge request received', 1),
(1010, 'payments', 'card approved, reply sent', null),
(1080, 'web', 'reply received', 3),
(1081, 'web', 'order 41 confirmed', null),
];
void main() {
final clock = {'web': 0, 'payments': 0};
final log = <(int, int, String, String)>[];
for (final (wall, server, event, source) in events) {
var lamport = clock[server]!;
if (source != null) {
lamport = lamport > log[source].$2
? lamport
: log[source].$2; // the sender's time
}
clock[server] = ++lamport;
log.add((wall, lamport, server, event));
}
print("merged by wall clock, with each event's Lamport time:");
for (final (wall, lamport, server, event)
in log..sort((a, b) => a.$1 - b.$1)) {
print(' ${'$wall'.padLeft(4)} ms Lamport $lamport $server: $event');
}
}In Dart: The events and log entries are records, read by their positions, $1 and $2.
Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart
What every language printed
merged by wall clock, with each event's Lamport time: 970 ms Lamport 3 payments: charge request received 1000 ms Lamport 1 web: order 41 received 1005 ms Lamport 2 web: charge request sent 1010 ms Lamport 4 payments: card approved, reply sent 1080 ms Lamport 5 web: reply received 1081 ms Lamport 6 web: order 41 confirmed
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 68 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 157 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 9 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads PHP (about 4.3 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 20 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 723 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 195 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 17 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
By wall clock, the payments server received the charge request at 970, before the order even arrived at 1000. The Lamport times number the six events 1 to 6 in the order they happened, so sorting by them puts every cause before its effect. The same skew does quieter damage elsewhere. A store that keeps the write with the latest timestamp lets a server whose clock runs fast win against writes that really came later, by up to the amount its clock is ahead. IDs that begin with a timestamp, such as version 7 UUIDs and ULIDs, sort by the clock of the machine that made them and inherit its skew (RFC 9562, ULID). Debugging, conflict resolution and replication all need an ordering that respects causality, so they cannot rely on raw wall-clock time across machines.
Vector clocks suit replicated stores that must notice two writes made without seeing each other. HLCs suit timestamps that must also be read as a time of day, such as a database snapshot as of 10:00.
Checkpoint
Check: Why wall clocks cannot order events
Lamport clocks give an order that never contradicts causality Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- Vector clocks tell concurrent events apart
- Hybrid logical clocks stay causal and close to real time
- TrueTime waits out its uncertainty before a commit
- Timeouts and leases need a monotonic clock
- Practise: vector timestamps by hand and in code
- Vector timestamps for a message diagram
- Interview questions
- Why can't you order events from different servers by their wall-clock timestamps?
- Logs collected from two services show a payment reply logged before the request that caused it. How could that happen, and how do you make the order in your logs and traces trustworthy?
- A profile store replicated across three regions resolves conflicting writes by keeping the one with the latest wall-clock timestamp. What goes wrong, how often, and what would you use instead?
- Why would a distributed database choose hybrid logical clocks over vector clocks for its timestamps, and what does it give up by doing so?
- Key takeaways
2 diagrams · 3 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 42 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- clock skew
- The difference between the readings of two machines' clocks at the same moment. Timestamps from two machines cannot order events that happen closer together than their skew.
- hybrid logical clock (HLC)
- A timestamp that adds a counter to physical time, so that it stays causal like a logical clock and close to the time of day.
- Lamport clock
- A logical clock: a counter that every message carries, which gives every event a number that is always larger for an effect than for its cause.
- monotonic clock
- A clock that only measures elapsed time, for timeouts, leases and durations, rather than telling the time of day.
- NTP (Network Time Protocol)
- The protocol that synchronises a machine's clock with time servers over the network, correcting it by slewing it gradually or, past a threshold, by stepping it, which can move a clock backwards.
- vector clock
- One counter per process, carried with every message, counting the events of each process that the sender knows of. Comparing two vector clocks shows whether one event could have caused the other or whether they are concurrent.
References
- Time, Clocks, and the Ordering of Events in a Distributed System (Communications of the ACM (Leslie Lamport))
- Virtual Time and Global States of Distributed Systems (Parallel and Distributed Algorithms (Friedemann Mattern))
- Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (University at Buffalo technical report (Kulkarni, Demirbas and others))
- Spanner: Google's Globally-Distributed Database (USENIX OSDI (Corbett and others))
- RFC 5905: Network Time Protocol Version 4 (IETF)
- Dynamo: Amazon's Highly Available Key-value Store (ACM SOSP (authors' copy))
- RFC 9562: Universally Unique IDentifiers (UUIDs), UUID version 7 (IETF)
- ULID specification (Universally Unique Lexicographically Sortable Identifier) (ULID project)
- time: time access and conversions (monotonic) (Python Software Foundation)
- Directions under sub-section (6) of section 70B of the Information Technology Act, 2000 (CERT-In, Ministry of Electronics and Information Technology)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress