벡터 시계 (Vector Clock)는 이벤트의 인과관계를 추적해서 램포트 시계의 동시성 구별 한계를 해결한다.
·수정 2026.04.23·수정 1회
요약
- 분산 시스템에서 이벤트의 인과 관계를 추적하기 위한 논리적 시계
- 램포트 시계의 한계(동시성 구별 불가)를 해결
- 각 프로세스가 모든 프로세스에 대한 카운터 배열을 유지
램포트 시계 vs 벡터 시계
| 항목 | 램포트 시계 | 벡터 시계 |
|---|---|---|
| 구조 | 단일 정수 | 정수 배열 (n개 프로세스) |
| 동시성 구별 | ❌ | ✅ |
| 인과관계 역추적 | ❌ | ✅ |
| 공간 복잡도 | O(1) | O(n) |
| 메시지 오버헤드 | 낮음 | 높음 |
동작 원리
규칙
n개의 프로세스가 있을 때, 각 프로세스 i는 벡터 V[0..n-1] 유지
- 초기화: 모든
V[j] = 0 - 로컬 이벤트:
V[i]++(자기 자신 카운터 증가) - 메시지 전송: 현재 벡터를 메시지에 포함
- 메시지 수신:
- 각 요소별 max 취함:
V[j] = max(V[j], V_received[j]) - 자기 카운터 증가:
V[i]++
- 각 요소별 max 취함:
예시
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)