---
id: cs-vector-clocks-lamport
title: Lamport / Vector Clocks — distributed ordering
category: Coding
status: draft
source_trust_level: B
verification_status: conceptual
created_at: 2026-05-09
updated_at: 2026-05-09
tags: [cs, distributed, vibe-coding]
tech_stack: { language: "TS", applicable_to: ["Backend", "CS"] }
applied_in: []
aliases: [Lamport timestamp, vector clock, hybrid logical clock, HLC, causality, happens-before]
---

# Lamport / Vector Clocks

> Distributed system 의 시계 = 안 동기화. **Lamport timestamp (logical) / Vector clock (causal) / HLC (hybrid)**. Causality 추적 + conflict resolution.

## 📖 핵심 개념
- Wall clock = node 별 다름 (NTP 도 ms 차이).
- Logical clock = 사건 순서 만.
- Causality: A 가 B 에 영향?
- Concurrent: A 와 B 가 독립.

## 💻 코드 패턴

### Lamport timestamp
```ts
class LamportClock {
  private counter = 0;
  
  // Local event
  tick(): number {
    return ++this.counter;
  }
  
  // 받은 message 의 ts
  update(receivedTs: number): number {
    this.counter = Math.max(this.counter, receivedTs) + 1;
    return this.counter;
  }
}

// Node A
const clockA = new LamportClock();
const tsA1 = clockA.tick();  // 1
sendMessage({ ts: tsA1, content: 'hello' });

// Node B 가 받음
const clockB = new LamportClock();
const tsB1 = clockB.update(tsA1);  // max(0, 1) + 1 = 2
```

→ A → B 가 invariant: tsA < tsB.

### Lamport 의 한계
```
Total order O.
Causality 안 줌:
- ts 비교 만 → A 가 B 에 영향 인지 모름.
- 같은 ts = 다른 node 가 가능 (tiebreak: node id).

→ "A happened-before B" 강 보장 X.
```

### Vector clock
```ts
class VectorClock {
  // node id → counter
  vec: Record<string, number> = {};
  
  constructor(public myId: string, nodes: string[]) {
    for (const n of nodes) this.vec[n] = 0;
  }
  
  tick(): VectorClock {
    this.vec[this.myId]++;
    return this.copy();
  }
  
  update(received: Record<string, number>): VectorClock {
    for (const n in received) {
      this.vec[n] = Math.max(this.vec[n], received[n]);
    }
    this.vec[this.myId]++;
    return this.copy();
  }
  
  copy() { return { ...this.vec }; }
}
```

### Causality 비교
```ts
function compare(a: Vec, b: Vec): 'before' | 'after' | 'concurrent' | 'equal' {
  let lt = false, gt = false;
  for (const n in a) {
    if (a[n] < b[n]) lt = true;
    if (a[n] > b[n]) gt = true;
  }
  if (!lt && !gt) return 'equal';
  if (lt && !gt) return 'before';
  if (!lt && gt) return 'after';
  return 'concurrent';
}
```

→ A < B (모든 entry) = A happened-before B.
→ 둘 다 = concurrent (conflict).

### Use case (Dynamo, Riak)
```
1. User 가 cart 에 item 추가 (Node A).
2. User 가 다른 device 에서 추가 (Node B).
3. 두 node 가 vector clock 가짐.
4. Read 시: 둘 다 본다 → "concurrent" 면 둘 다 반환.
5. Client 가 merge.
```

→ Eventually consistent + causal.

### Vector clock 의 한계
```
Vec size = node 수 N.
1000 node = 1000 entry / message.

→ 큰 system 에 부적합.
Pruning, dotted version vector 가 변형.
```

### Hybrid Logical Clock (HLC)
```ts
class HLC {
  private logicalTime = 0;
  private logicalCounter = 0;
  
  now(): { time: number; counter: number } {
    const now = Date.now();
    if (now > this.logicalTime) {
      this.logicalTime = now;
      this.logicalCounter = 0;
    } else {
      this.logicalCounter++;
    }
    return { time: this.logicalTime, counter: this.logicalCounter };
  }
  
  update(receivedTime: number, receivedCounter: number) {
    const now = Date.now();
    const newTime = Math.max(this.logicalTime, receivedTime, now);
    
    if (newTime === this.logicalTime && newTime === receivedTime) {
      this.logicalCounter = Math.max(this.logicalCounter, receivedCounter) + 1;
    } else if (newTime === this.logicalTime) {
      this.logicalCounter++;
    } else if (newTime === receivedTime) {
      this.logicalCounter = receivedCounter + 1;
    } else {
      this.logicalCounter = 0;
    }
    this.logicalTime = newTime;
  }
}
```

→ Wall clock 가 가까움 + Lamport 의 logical 보장.

### CockroachDB / Spanner (HLC 사용)
```sql
SELECT now();
-- HLC timestamp: physical time + logical counter.

SELECT cluster_logical_timestamp();
```

→ MVCC + HLC = causal consistency.

### Causal consistency
```
Strong: 모든 사용자 가 같은 순서.
Causal: 인과 관계 보존 (X 후 Y 가 모든 사용자 X→Y).
Eventual: 결국 같음.

Causal = strong 보다 cheap, eventual 보다 강.
```

### Conflict resolution
```ts
// Vector clock 비교
const c = compare(a.vec, b.vec);

if (c === 'before') return b;    // b 가 새
if (c === 'after')  return a;
if (c === 'equal')  return a;
if (c === 'concurrent') {
  // Custom merge (CRDT, app logic)
  return merge(a, b);
}
```

### Dotted version vector (모던)
```
Riak 가 사용.
Vector + "dot" (마지막 update 의 정확 entry).

→ Sibling 잘 추적.
Vector 보다 작은 size.
```

### 분산 lock 의 fencing token
```ts
// Lock 가 lease.
// 같은 client 가 lease 잃음 + 작업 계속 = 위험.

// Fencing token (Lamport 식)
const token = await lockService.acquire('resource');
// token = 1, 2, 3, ...

await storage.write('data', value, { fencingToken: token });

// Storage 가 token < lastSeenToken = reject.
```

→ "이 작업 가 옛 lock 가" 검출.

### Causal order 의 broadcast
```ts
class CausalBroadcast {
  vec: Record<string, number> = {};
  pending: Message[] = [];
  
  send(content: string) {
    this.vec[myId]++;
    network.broadcast({ from: myId, vec: { ...this.vec }, content });
  }
  
  receive(msg: Message) {
    // 인과 순서 가 도착 까지 대기
    if (this.canDeliver(msg)) {
      this.deliver(msg);
      this.checkPending();
    } else {
      this.pending.push(msg);
    }
  }
  
  canDeliver(msg: Message): boolean {
    // msg.vec[msg.from] === this.vec[msg.from] + 1
    // 다른 node 의 vec[k] >= msg.vec[k]
    return ...;
  }
}
```

→ Delivery 가 causal order.

### 함정
```
- 매 message 가 vector → bandwidth.
- Node add / remove → vector 변경.
- Wall clock 도 도움 (HLC).
- Lamport 가 causality 안 줌 (just total order).
```

### When NOT 분산 시계?
```
- Single node: wall clock OK.
- Strong consistency (synchronous, leader): leader 가 order.
- Eventually consistent + 단순 LWW: timestamp + node id.

→ Causal consistency 가 진짜 필요할 때 만.
```

### Spanner 의 TrueTime
```
Google 의 atomic clock + GPS = 정확 시계 (5-7ms 오차).
External consistency 가능.

→ HLC 의 hardware version.
일반 cloud 가 안 됨.
```

### CockroachDB / YugabyteDB
```
HLC 가 MVCC 에 사용.
Linearizability 가 limit (no atomic clock).
Causal consistency 강함.
```

### Riak / Dynamo
```
Vector clock + sibling.
Read 시 conflict 발견 → client 가 resolve.

→ Sibling 가 client 에 push.
"마지막 client 가 winner" (LWW) X.
```

### Cassandra
```
Wall clock + LWW (Last Write Wins).
- 단순.
- Wall clock skew = 잃음.

→ Casual consistency 안 줌.
```

### CRDT 가 다른 답
```
Vector clock = order 보존.
CRDT = order 무관 (commutative).

→ [[CS_CRDT_Patterns]].
```

### Snapshot Read (HLC)
```sql
-- CockroachDB
SELECT * FROM users AS OF SYSTEM TIME '-10s';
```

→ HLC 가 시점 query.

## 🤔 의사결정 기준
| 상황 | 추천 |
|---|---|
| Total order 만 | Lamport |
| Causality | Vector clock |
| 큰 system | HLC |
| 매우 정확 | Spanner TrueTime |
| Conflict resolution | CRDT |
| 단순 (LWW OK) | Wall clock + node id |
| Distributed lock | Fencing token |

## ❌ 안티패턴
- **Wall clock 만**: skew = bug.
- **Vector clock 의 큰 size**: bandwidth.
- **Lamport 가 causality 줄 거 가정**: 안 줌.
- **Causal broadcast 없이 causal data**: order 깨짐.
- **CRDT + LWW + 시계 무시**: data 잃음.
- **Fencing token 없이 lock**: stale lock 위험.

## 🤖 LLM 활용 힌트
- Lamport = total order. Vector = causal. HLC = hybrid.
- Spanner / CockroachDB / Riak 가 영감.
- Causal broadcast 가 distributed system 의 기초.
- Wall clock 신뢰 = 실패.

## 🔗 관련 문서
- [[CS_Eventual_Consistency]]
- [[CS_Distributed_Consensus]]
- [[CS_CRDT_Patterns]]
