Time, Clocks & Ordering in Distributed Systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// NAIVE ANTI-PATTERN: Last-Write-Wins using physical server timestamps
interface DocumentRecord {
  id: string;
  data: string;
  updatedAtMs: number; // Wall-clock timestamp from local server!
}

// SCENARIO: Node 1 clock is 250ms SLOW. Node 2 clock is ACCURATE.
// Real Physical Time: 12:00:00.000
// User A updates document on Node 2:
const updateA: DocumentRecord = {
  id: 'doc_1',
  data: 'Initial Title',
  updatedAtMs: 1700000000250 // Real physical time 12:00:00.250
};

// Real Physical Time: 12:00:00.300 (50ms later)
// User B updates document on Node 1 (whose clock is 250ms behind!):
const updateB: DocumentRecord = {
  id: 'doc_1',
  data: 'Revised Title by User B',
  updatedAtMs: 1700000000050 // Timestamp generated: 12:00:00.050!
};

// Distributed Merge Engine executes LWW:
function mergeLWW(a: DocumentRecord, b: DocumentRecord): DocumentRecord {
  return a.updatedAtMs > b.updatedAtMs ? a : b;
}

// CATASTROPHE: updateB happened AFTER updateA in physical reality.
// But mergeLWW picks updateA because updateA's timestamp is higher!
// User B's update is permanently, silently discarded!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

// PRODUCTION VECTOR CLOCK CAUSALITY ENGINE
export type CausalRelation = 'BEFORE' | 'AFTER' | 'CONCURRENT' | 'IDENTICAL';

export class VectorClock {
  public clock: Map<string, number>;

  constructor(initial?: Map<string, number>) {
    this.clock = new Map(initial);
  }

  // Increment local clock on internal event or write
  public tick(nodeId: string): void {
    const current = this.clock.get(nodeId) || 0;
    this.clock.set(nodeId, current + 1);
  }

  // Merge with incoming remote clock
  public merge(remote: VectorClock): void {
    for (const [nodeId, remoteVal] of remote.clock.entries()) {
      const localVal = this.clock.get(nodeId) || 0;
      this.clock.set(nodeId, Math.max(localVal, remoteVal));
    }
  }

  // Determine causal relationship between two vector clocks:
  // V1 <= V2 iff for all k: V1[k] <= V2[k]
  public static compare(v1: VectorClock, v2: VectorClock): CausalRelation {
    let v1HasGreater = false;
    let v2HasGreater = false;

    const allKeys = new Set([...v1.clock.keys(), ...v2.clock.keys()]);

    for (const key of allKeys) {
      const val1 = v1.clock.get(key) || 0;
      const val2 = v2.clock.get(key) || 0;

      if (val1 > val2) v1HasGreater = true;
      if (val2 > val1) v2HasGreater = true;
    }

    if (!v1HasGreater && !v2HasGreater) return 'IDENTICAL';
    if (v1HasGreater && !v2HasGreater) return 'AFTER';
    if (!v1HasGreater && v2HasGreater) return 'BEFORE';
    return 'CONCURRENT'; // Fork detected! Conflict requires application merge.
  }
}

// SPANNER TRUETIME COMMIT WAIT ENGINE
export interface TrueTimeInterval {
  earliest: number; // Earliest possible physical time (ms)
  latest: number;   // Latest possible physical time (ms)
}

export class TrueTimeService {
  private static readonly EPSILON_MS = 5; // Bounded uncertainty (1-7ms in Spanner)

  public static now(): TrueTimeInterval {
    const physicalTime = Date.now();
    return {
      earliest: physicalTime - this.EPSILON_MS,
      latest: physicalTime + this.EPSILON_MS,
    };
  }

  // Spanner Commit Wait Rule:
  // To guarantee strict serializability (external consistency),
  // a transaction MUST wait until physical time is guaranteed past its commit timestamp.
  public static async commitWait(commitTimestampMs: number): Promise<void> {
    while (true) {
      const now = this.now();
      if (now.earliest > commitTimestampMs) {
        return; // Safe to release locks and return to client!
      }
      await new Promise((resolve) => setTimeout(resolve, 1));
    }
  }
}