램포트 타임스탬프(Lamport timestamp)와 벡터 시계(Vector clock)는 분산 시스템에서 "어떤 사건이 먼저 일어났는가"를 물리 시계 없이 판단하기 위한 논리 시계입니다. 여러 서버의 벽시계(wall clock)는 서로 미세하게 어긋나기 때문에, 시각으로는 사건의 순서를 신뢰할 수 없습니다. 그래서 순서 그 자체를 세는 별도의 카운터를 씁니다.
이게 왜 문제가 되는지 한 번 크게 데어봐야 실감이 납니다. 저는 두 데이터센터에서 같은 문서를 편집하는 기능을 만들다가, "나중에 저장한 게 이겨야 한다"를 서버 타임스탬프로 판단했다가 낭패를 봤습니다. NTP로 맞췄어도 서버 시계는 수십 밀리초씩 튑니다. 그 틈에 더 늦게 도착한 편집이 더 이른 시각을 달고 와서, 멀쩡한 수정이 덮여 사라졌죠.
"먼저 일어남" 관계부터
램포트가 정의한 핵심 개념은 happened-before(→) 관계입니다. 세 가지 규칙으로 정리됩니다. 같은 노드 안에서 앞선 사건은 뒤 사건보다 먼저다. 메시지를 보낸 사건은 그 메시지를 받은 사건보다 먼저다. 그리고 이 관계는 이행적(transitive)이다. 여기서 중요한 건, 서로 인과관계가 없는 두 사건은 순서를 매길 수 없다는 점입니다. 이걸 "동시적(concurrent)"이라고 부릅니다.
램포트 타임스탬프 — 카운터 하나
램포트 시계는 노드마다 정수 카운터 하나입니다. 규칙은 단순합니다.
- 내부 사건이 생기면 카운터를 1 올린다.
- 메시지를 보낼 때 현재 카운터 값을 함께 실어 보낸다.
- 메시지를 받으면
내 카운터 = max(내 카운터, 받은 값) + 1로 갱신한다.
class LamportClock:
def __init__(self):
self.t = 0
def tick(self): # 내부 사건
self.t += 1
return self.t
def send(self):
self.t += 1
return self.t # 메시지에 붙여 보냄
def recv(self, msg_t):
self.t = max(self.t, msg_t) + 1
return self.t이렇게 하면 "A → B이면 반드시 timestamp(A) < timestamp(B)"가 보장됩니다. 다만 역은 성립하지 않습니다. timestamp가 작다고 실제로 먼저 일어난 건 아닙니다. 즉 램포트 시계로는 인과관계를 만들 수는 있어도, 두 사건이 인과적인지 동시적인지 구별할 수는 없습니다.
벡터 시계 — 노드마다 칸을 둔다
벡터 시계는 이 한계를 넘습니다. 각 노드가 카운터 하나가 아니라 노드 수만큼의 배열을 들고 다닙니다. 노드 i는 자기 사건이 생기면 자기 칸 V[i]만 올리고, 메시지를 받으면 각 칸을 원소별 최댓값으로 병합한 뒤 자기 칸을 올립니다.
# 노드 3개, 벡터 = [n0, n1, n2]
def event(V, i):
V[i] += 1
def merge(V, incoming, i):
for k in range(len(V)):
V[k] = max(V[k], incoming[k])
V[i] += 1
# 비교: A가 B보다 먼저인가?
def happened_before(A, B):
return all(a <= b for a, b in zip(A, B)) and A != B이제 두 벡터를 비교하면 세 가지 결과가 나옵니다. 모든 칸이 A ≤ B이고 하나라도 작으면 A가 먼저, 반대면 B가 먼저, 어느 쪽도 아니면 두 사건은 동시적입니다. 드디어 "동시성"을 탐지할 수 있게 된 겁니다. 이게 협업 편집이나 리더리스 복제에서 충돌을 감지하는 토대가 됩니다.
둘을 언제 고르나
| 기준 | 램포트 | 벡터 시계 |
|---|---|---|
| 크기 | 정수 1개 | 노드 수만큼 |
| 전체 순서 | 동점을 노드ID로 깨면 가능 | 부분 순서만 |
| 동시성 탐지 | 불가 | 가능 |
정리하면, 전체 순서(total order)만 필요하고 동시성 판별이 필요 없으면 램포트가 가볍습니다. 충돌 감지가 필요하면 벡터 시계입니다. 실제로 Amazon Dynamo, Riak, 그리고 여러 CRDT 구현이 벡터 시계나 그 사촌 격인 버전 벡터를 씁니다.
현실의 함정
- 노드가 많아지면 벡터가 비대해집니다. 수천 노드면 벡터 하나가 수 KB가 되죠. 그래서 도트 버전 벡터(dotted version vector)처럼 압축하는 변형이 나왔습니다.
- 노드가 동적으로 추가·삭제되면 벡터의 칸 관리가 까다롭습니다. 사라진 노드의 칸을 언제 정리할지 정책이 필요합니다.
- 동시성 탐지는 충돌을 알려줄 뿐, 그걸 어떻게 병합할지(마지막 쓰기 우선? 사용자에게 물어보기? 자동 병합?)는 별개의 비즈니스 결정입니다.
자주 묻는 질문
그냥 NTP로 시계를 맞추면 안 되나요?
NTP는 오차를 줄일 뿐 없애지 못합니다. 수 밀리초의 오차만으로도 인접한 사건의 순서가 뒤집힐 수 있어, 인과관계 판단에는 물리 시계를 신뢰할 수 없습니다. 논리 시계는 오차와 무관하게 인과 순서를 보장합니다.
구글 TrueTime은 뭐가 다른가요?
TrueTime(Spanner)은 GPS·원자시계로 시계 오차의 상한을 알고, 그 불확실 구간이 지나갈 때까지 잠깐 기다려 전역 순서를 보장합니다. 하드웨어로 물리 시계 문제를 정면 돌파한 셈인데, 일반 환경에선 쓰기 어렵습니다.
램포트 시계로 전체 순서를 만들 수 있나요?
타임스탬프가 같을 때 노드 ID로 동점을 깨면 임의의 전체 순서를 만들 수 있습니다. 다만 그 순서가 "실제 인과관계"와 일치하는 건 아니고, 그저 모두가 동의하는 하나의 순서일 뿐입니다.
벡터 시계와 버전 벡터는 같은 건가요?
원리는 같지만 쓰임이 조금 다릅니다. 벡터 시계는 개별 사건을, 버전 벡터는 데이터 복제본의 버전 상태를 추적합니다. 리더리스 저장소의 충돌 감지에는 보통 버전 벡터 계열을 씁니다.
댓글 0