Vector Clock / Lamport Timestamp (벡터 시계 / 램포트 타임스탬프)

Vector Clock / Lamport Timestamp (벡터 시계 / 램포트 타임스탬프)

분산 시스템에서 이벤트의 인과 관계(Causality)와 순서를 추적하기 위한 논리적 시계로, 물리적 시계 동기화 없이 이벤트 순서를 결정

목적: 이벤트 순서 결정, 인과 관계 추적, 동시성 탐지, 충돌 해결

Lamport Timestamp

• •단일 정수 카운터, 이벤트 발생/메시지 수신 시 증가
• •규칙: 로컬 이벤트 시 C = C + 1, 메시지 수신 시 C = max(C, 수신값) + 1
• •한계: 동시 이벤트 구분 불가, 인과 관계 부분적 추적
• •A < B이면 A가 먼저지만, 같은 값이면 순서 불명확

Vector Clock

• •노드 수만큼의 카운터 배열 [N1, N2, N3, ...]
• •각 노드는 자신의 카운터만 증가, 메시지에 전체 벡터 포함
• •수신 시: 각 요소를 max(로컬, 수신)로 업데이트 후 자신 카운터 증가
• •장점: 동시 이벤트 탐지 가능 (V1 || V2: 어느 쪽도 크지 않음)

순서 비교

• •V1 < V2: V1의 모든 요소가 V2 이하이고, 최소 하나는 작음
• •V1 || V2 (동시): 서로 비교 불가, 충돌 가능

장점: 물리적 시계 불필요, 인과 관계 추적, 동시성 탐지

단점: 벡터 크기가 노드 수에 비례, 오버헤드 증가, 가비지 컬렉션 필요

적용사례: Amazon DynamoDB(충돌 탐지), Riak, 분산 버전 관리, 이벤트 소싱

기술요소: 논리적 시계, 인과 관계, 동시성, 충돌 해결

비교: Lamport(단일 정수/부분 순서) vs Vector Clock(벡터/완전 인과 추적) vs Hybrid Logical Clock(물리+논리)

연관: 분산 시스템, 인과 일관성, CRDT, 이벤트 순서, 충돌 해결