벡터 시계 (Vector Clock)는 이벤트의 인과관계를 추적해서 램포트 시계의 동시성 구별 한계를 해결한다.

요약

• 분산 시스템에서 이벤트의 인과 관계를 추적하기 위한 논리적 시계
• 램포트 시계의 한계(동시성 구별 불가)를 해결
• 각 프로세스가 모든 프로세스에 대한 카운터 배열을 유지

램포트 시계 vs 벡터 시계

항목	램포트 시계	벡터 시계
구조	단일 정수	정수 배열 (n개 프로세스)
동시성 구별	❌	✅
인과관계 역추적	❌	✅
공간 복잡도	O(1)	O(n)
메시지 오버헤드	낮음	높음

동작 원리

규칙

n개의 프로세스가 있을 때, 각 프로세스 i는 벡터 V[0..n-1] 유지

1. 초기화: 모든 V[j] = 0
2. 로컬 이벤트: V[i]++ (자기 자신 카운터 증가)
3. 메시지 전송: 현재 벡터를 메시지에 포함
4. 메시지 수신:
   • 각 요소별 max 취함: V[j] = max(V[j], V_received[j])
   • 자기 카운터 증가: V[i]++

예시

P0: [1,0,0] → [2,0,0] ────────────────→ [3,2,0]
                 ↘ send([2,0,0])              ↑ recv
P1: [0,1,0] → [2,2,0] → [2,3,0] ─────────────┘
                            ↘ send([2,3,0])
P2: [0,0,1] → [0,0,2] → [2,3,3]
                            ↑ recv([2,3,0])

인과관계 판단

두 벡터 V와 W에 대해:

조건	의미
V < W (모든 i에서 V[i] ≤ W[i], 하나 이상 <)	V가 W보다 먼저 발생 (V → W)
V = W	같은 이벤트
`V

예시

V = [2,3,1]
W = [3,2,1]

V[0]=2 < W[0]=3, V[1]=3 > W[1]=2 → 비교 불가 → 동시 발생!

장점

장점	설명
동시성 감지	동시 발생 이벤트 구별 가능
인과관계 추적	a → b 관계 완전 추적 가능
충돌 감지	분산 DB에서 write 충돌 감지

단점

단점	설명
공간 오버헤드	O(n) - 프로세스 수에 비례
메시지 크기 증가	벡터 전체를 전송해야 함
확장성 제한	수천 노드 이상에서 비효율적

사용 사례

• Amazon DynamoDB: 충돌 감지 및 버전 관리
• Riak: 분산 key-value 저장소
• 분산 디버깅: 이벤트 순서 추적

개선된 버전

• Version Vector: 벡터 시계와 유사, 데이터 버전 관리용
• Dotted Version Vector: 동시 업데이트 시 sibling 문제 해결
• Interval Tree Clock: 동적 프로세스 추가/제거 지원

참고

램포트 시계 (Lamport Clock)는 분산시스템에서 이벤트 순서를 결정하기 위한 논리적 시계다. 인과적 브로드캐스트 (Causal Broadcast)는 메시지의 인과관계를 유지하는 브로드 캐스트 프로토콜이다. 전체 순서 브로드캐스트 (Total Order Broadcast)