Logical clocks

Backend Fundamentals · Distributed Systems · 7 min read

1. What problem does this solve?

In a distributed system, events happen on many machines that have no shared clock.
When you need to order events, detect causality, or merge data from different nodes, you cannot rely on wall‑clock timestamps because:

• Clock skew: Even synchronized NTP clocks can drift by milliseconds or more.
• Clock rollback: A node’s clock can be manually adjusted or reset.
• Network latency: Messages can arrive out of order.

If you ignore these issues, you may:

• Apply updates in the wrong order (lost updates, stale reads).
• Inconsistently resolve conflicts in CRDTs or eventual‑consistency stores.
• Misinterpret causality in debugging or audit logs.

Logical clocks provide a causal ordering that is guaranteed to be consistent across nodes, independent of physical time. They are used in:

• Event sourcing (ordering domain events).
• CRDTs (conflict resolution).
• Distributed databases (e.g., DynamoDB’s version vectors).
• Message brokers (Kafka’s offset ordering).
• Distributed tracing (to correlate spans).

2. Mental model

Analogy: “Book‑page numbers”

Imagine each node is a book that writes its own page numbers.
When you read a page, you can tell if it was written before or after another page by comparing numbers, even if the books were written on different days.
The page number is a logical clock: it only needs to increase monotonically, not match real time.

Engineering model

A logical clock is a counter that each node increments when it performs an event.
When nodes communicate, they exchange their counters.
The receiving node updates its own counter to be max(received, local) + 1.
Thus, every event can be assigned a unique, monotonically increasing number that reflects causal order.

3. Deep explanation

Internals

Important terminology

• Event: Any state change (e.g., write, message send).
• Causality (→): Event a happened before b if a could have influenced b.
• Concurrent: Events that are not causally related.
• Clock skew: Difference between logical clocks of two nodes.

Trade‑offs

Failure modes

• Clock rollback: If a node’s clock jumps back, vector clocks may lose ordering guarantees.
• Node churn: Adding/removing nodes changes vector size; requires re‑initialization.
• Network partitions: Events may be lost or duplicated; vector clocks help detect divergence.

Limitations

• Scalability: Vector clocks become unwieldy for thousands of nodes.
• Storage: Persisting full vector per record can be expensive.
• Complexity: Implementing conflict resolution with vectors can be error‑prone.

Where it fits

• Data stores: Store a vector clock per record to resolve concurrent updates.
• Messaging: Attach Lamport timestamps to messages for ordering.
• Tracing: Use HLC to correlate spans across services.

Interaction with related concepts

• Consensus (Paxos/Raft): Logical clocks are orthogonal; consensus ensures agreement, clocks ensure ordering.
• CRDTs: Vector clocks are often embedded in CRDT metadata.
• Event sourcing: Event IDs can be logical timestamps.

4. How it works

1. Node starts → local counter = 0 (Lamport) or vector = all zeros.
2. Event occurs → increment local counter; record timestamp.
3. Send message → include current timestamp/vector.
4. Receive message →
   • For Lamport: local = max(local, received) + 1.
   • For vector: local[i] = max(local[i], received[i]) for all i; then local[self] += 1.
5. Persist → store updated timestamp with event or record.

sequenceDiagram
    participant A as Node A
    participant B as Node B
    A->>A: Event e1 (Lamport 5)
    A->>B: Send e1 (timestamp 5)
    B->>B: Event e2 (Lamport 3)
    B->>A: Send e2 (timestamp 3)
    A->>A: Receive e2
    A: local = max(5,3)+1 = 6

5. Practical implementation

TypeScript / Node.js – Lamport clock

// lamport.ts
export class LamportClock {
  private counter: number = 0;

  // Call when local event occurs
  tick(): number {
    this.counter += 1;
    return this.counter;
  }

  // Call when receiving a message
  receive(received: number): number {
    this.counter = Math.max(this.counter, received) + 1;
    return this.counter;
  }

  get value() {
    return this.counter;
  }
}

Usage in an HTTP API

// server.ts
import express from 'express';
import { LamportClock } from './lamport';

const app = express();
app.use(express.json());

const clock = new LamportClock();

app.post('/write', (req, res) => {
  const ts = clock.tick(); // local write
  // Persist to DB with ts
  res.json({ ts });
});

app.post('/receive', (req, res) => {
  const { ts: remoteTs } = req.body;
  const ts = clock.receive(remoteTs);
  // Persist or merge
  res.json({ ts });
});

app.listen(3000, () => console.log('Listening on 3000'));

Vector clock example

// vector.ts
export class VectorClock {
  private readonly id: string; // node id
  private vector: Record<string, number>;

  constructor(id: string, peers: string[]) {
    this.id = id;
    this.vector = { [id]: 0 };
    peers.forEach(p => { this.vector[p] = 0; });
  }

  tick(): Record<string, number> {
    this.vector[this.id] += 1;
    return { ...this.vector };
  }

  receive(remote: Record<string, number>): Record<string, number> {
    for (const node of Object.keys(remote)) {
      this.vector[node] = Math.max(this.vector[node] ?? 0, remote[node]);
    }
    this.vector[this.id] += 1;
    return { ...this.vector };
  }

  get value() {
    return { ...this.vector };
  }
}

Persist the vector as JSON in PostgreSQL or MongoDB.
When merging two records, compare vectors to detect concurrency.

6. Production considerations

7. Common mistakes

8. Senior engineer perspective

What changes at scale?

• Architecture:
  • Use partitioned vector clocks (e.g., per shard).
  • Combine with conflict‑free replicated data types (CRDTs) for eventual consistency.
• Trade‑offs:
  • Vector size vs. precision.
  • Latency of vector propagation vs. consistency guarantees.
• Bottlenecks:
  • Central clock service becomes a hotspot.
  • Network overhead of sending full vectors.
• Failure scenarios:
  • Partitioned nodes may diverge; need reconciliation logic.
  • Clock rollback can cause duplicate events; guard with idempotency.
• Monitoring:
  • Track max vector difference between replicas.
  • Alert on sudden jumps in Lamport timestamps.
• Cost/performance:
  • Vector storage adds overhead; compress or prune old entries.
  • Use HLC to reduce vector size while keeping near‑real‑time ordering.
• When NOT to use:
  • For strictly linearizable services where consensus (Raft) is already used.
  • When latency is critical and a small ordering window is acceptable; use simple sequence numbers.

9. Interview questions

10. Hands‑on task

Implement a vector‑clock‑aware merge for a simple JSON document store:

1. Create a Node.js project with an in‑memory store (Map<string, {data: any, vc: Record<string, number>}>).
2. Add endpoints:
   • POST /doc/:id – create/update a document; increment local vector.
   • GET /doc/:id – retrieve document and its vector.
   • POST /merge/:id – accept a remote vector and merge if concurrent.
3. Write tests that simulate two nodes updating the same document concurrently and verify that the merge preserves both updates.

11. Quick revision

• Logical clocks provide causal ordering independent of physical time.
• Lamport: single counter, guarantees a → b ⇒ T(a) < T(b), cannot detect concurrency.
• Vector: array of counters, one per node, captures full causality; size = node count.
• Hybrid Logical Clock (HLC): combines physical time + logical counter for near‑real‑time ordering.
• Use logical clocks in event sourcing, CRDTs, distributed DBs, and tracing.
• Increment on local events and on message receive (max(received, local) + 1).
• Persist clocks with events to survive restarts.
• Vector clocks become unwieldy at scale; consider hierarchical or partitioned vectors.
• Common pitfalls: ignoring receive increment, using wall‑clock timestamps, not handling node churn.
• At scale: monitor vector divergence, guard against clock rollback, balance precision vs. overhead.

12. References

• Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System
• Vector Clocks – Wikipedia
• Hybrid Logical Clocks – Google Cloud Blog
• DynamoDB Version Vectors
• CRDTs – Wikipedia
• Distributed Tracing – OpenTelemetry