서버가 여러 대면 "어느 일이 먼저 일어났는가"를 벽시계로 정할 수 없다. 서버마다 시계가 조금씩 다르고, 맞추는 도중에 뒤로 가기도 하기 때문이다. 이 글은 시계 대신 인과 관계로 순서를 매기는 Lamport Clock과 Vector Clock의 규칙을 같은 예시 하나로 계산해 보고, 각각이 알려 주는 것과 알려 주지 못하는 것, 실무에서 쓰이는 곳과 Hybrid Logical Clock까지 정리한 것이다.
한눈에 보기
| 방식 | 값의 모양 | 알려 주는 것 | 알려 주지 못하는 것 |
|---|---|---|---|
| 물리 시계 | 밀리초 타임스탬프 | 사람이 읽는 시각 | 서버 간 순서(오차·역행) |
| Lamport Clock | 정수 1개 | a가 b보다 먼저면 L(a) < L(b) | L(a) < L(b)일 때 a가 먼저인지, 동시인지 |
| Vector Clock | 노드 수만큼의 정수 배열 | 먼저·나중·동시를 정확히 구분 | 실제 시각, 노드가 많을 때의 크기 |
| Hybrid Logical Clock | 물리 시각 + 카운터 | Lamport와 같은 보장 + 실제 시각에 가까운 값 | 동시 판정(Vector Clock이 필요) |
아래 그림이 이 글 전체에서 쓰는 예시다. 프로세스 A, B, C가 있고, A가 B에게 m1을, B가 C에게 m2를 보낸다. 점마다 Lamport 값(L)과 벡터 값을 적었다.
물리 시계로 순서를 정하면 생기는 일
각 서버의 시계는 NTP로 맞춘다. 그래도 서버마다 오차가 남고, NTP가 크게 틀어진 시계를 한 번에 보정하면 시각이 뒤로 갈 수 있다. 가상 머신이 일시 정지됐다 깨어나면 시계가 한 번에 튀기도 한다.
이 상태에서 "타임스탬프가 큰 쪽이 나중"이라고 정하면 두 가지 사고가 난다.
- 원인보다 결과가 먼저 찍힌다. 서버 1이 주문을 만들고 서버 2가 그 주문을 취소했는데, 서버 2 시계가 늦어서 취소 시각이 생성 시각보다 앞선다. 로그를 시각순으로 정렬하면 없는 주문을 취소한 것처럼 보인다.
- 나중에 쓴 값이 사라진다. 마지막 쓰기 승리(LWW) 저장소에서 시계가 앞선 서버의 오래된 쓰기가 시계가 늦은 서버의 새 쓰기를 이긴다.
한 서버 안에서 걸린 시간을 잴 때는 단조 시계(Java System.nanoTime(), Linux CLOCK_MONOTONIC)를 쓰면 역행은 피한다. 하지만 단조 시계는 서버끼리 비교할 수 없다. 서버 사이의 순서에는 다른 기준이 필요하다.
happened-before: 순서의 정의부터 바꾼다
Leslie Lamport는 1978년 논문 "Time, Clocks, and the Ordering of Events in a Distributed System"에서 순서를 시각이 아니라 인과로 정의했다. a가 b보다 먼저 일어났다(a → b)는 다음 셋 중 하나다.
- 같은 프로세스 안에서 a가 b보다 먼저 실행됐다. (a1 → a2)
- a가 메시지를 보낸 이벤트이고 b가 그 메시지를 받은 이벤트다. (a2 → b2)
- a → c이고 c → b다. (a2 → b2 → b3 → c2 이므로 a2 → c2)
어느 쪽으로도 화살표가 이어지지 않으면 두 이벤트는 **동시(concurrent)**다. 동시는 "같은 순간"이 아니라 "서로 영향을 줄 수 없었다"는 뜻이다. 그림의 a3와 c2는 줄을 맞춰 그렸지만, 둘이 같은 시각인지는 아무도 모르고 알 필요도 없다. a3가 c2에 영향을 줄 길이 없고, c2도 a3에 영향을 줄 길이 없다는 사실만 중요하다.
Lamport Clock 규칙
프로세스마다 정수 카운터 하나를 둔다. 규칙은 두 줄이다.
- 로컬 이벤트와 보내기: 카운터를 1 올리고, 보낼 때는 올린 값을 메시지에 싣는다.
- 받기: 카운터를
max(내 값, 메시지 값) + 1로 바꾼다.
그림으로 계산해 보면 이렇다.
| 이벤트 | 계산 | L |
|---|---|---|
| a1 | 0 + 1 | 1 |
| a2 (m1 보냄) | 1 + 1 | 2 |
| b1 | 0 + 1 | 1 |
| b2 (m1 받음) | max(1, 2) + 1 | 3 |
| b3 (m2 보냄) | 3 + 1 | 4 |
| c1 | 0 + 1 | 1 |
| c2 (m2 받음) | max(1, 4) + 1 | 5 |
| a3 | 2 + 1 | 3 |
받는 쪽이 메시지 값보다 큰 값으로 건너뛰기 때문에, 원인을 거쳐 온 결과는 늘 원인보다 큰 값을 가진다.
class LamportClock:
def __init__(self):
self.t = 0
def tick(self): # 로컬 이벤트, 보내기 직전
self.t += 1
return self.t
def recv(self, msg_t): # 메시지를 받는 순간
self.t = max(self.t, msg_t) + 1
return self.t
Lamport 값이 말해 주는 것과 말해 주지 않는 것
보장은 한 방향뿐이다. a → b이면 L(a) < L(b)다. 거꾸로 L(a) < L(b)라고 a → b인 것은 아니다.
그림의 a3는 L=3, c2는 L=5다. 숫자만 보면 a3가 먼저 같지만, a3에서 c2로 가는 화살표는 없다. c1(L=1)과 b2(L=3)도 마찬가지로 동시다. Lamport 값만으로는 "먼저인지 동시인지"를 가를 수 없다. 쓸 수 있는 건 대우뿐이다. L(a) ≥ L(b)이면 a는 b의 원인이 아니다.
값이 같을 수도 있다. a3와 b2가 둘 다 L=3이다. 모든 이벤트를 한 줄로 세워야 하면(전체 순서, total order) (L, 프로세스 ID) 쌍으로 비교해 동점을 가른다. (3, A) < (3, B)이므로 a3를 앞에 둔다. 이 순서는 인과를 어기지 않지만, 동시 이벤트 사이의 앞뒤는 임의로 정한 것이다. Lamport의 같은 논문은 이 전체 순서로 분산 상호 배제를 구현하는 방법을 보였다.
Vector Clock 규칙과 비교
"먼저인지 동시인지"를 알아야 하면 Vector Clock을 쓴다. 1988년 Colin Fidge와 Friedemann Mattern이 각각 발표했다. 프로세스가 N개면 길이 N의 배열을 들고 다닌다. i번째 칸은 "내가 알고 있는 프로세스 i의 이벤트 수"다.
- 로컬 이벤트와 보내기: 내 칸만 1 올리고, 보낼 때는 배열 전체를 싣는다.
- 받기: 칸마다
max(내 값, 메시지 값)을 취한 뒤 내 칸을 1 올린다.
c2를 계산하면 C의 이전 값 [0,0,1]과 m2의 [2,3,0]을 칸마다 최댓값으로 합쳐 [2,3,1], 내 칸을 올려 [2,3,2]다.
비교 규칙은 이렇다.
- 모든 칸에서 V(a) ≤ V(b)이고 한 칸 이상 작으면 a → b.
- 어느 쪽으로도 성립하지 않으면 동시.
a1 [1,0,0]과 c2 [2,3,2]는 모든 칸이 작거나 같으니 a1 → c2다. a3 [3,0,0]과 c2 [2,3,2]는 A칸은 a3가 크고 B칸은 c2가 크다. 어느 쪽도 앞서지 않으니 동시다. Lamport 값 3과 5가 숨긴 사실을 벡터가 드러낸다.
class VectorClock:
def __init__(self, me, n):
self.me, self.v = me, [0] * n
def tick(self):
self.v[self.me] += 1
return list(self.v)
def recv(self, msg_v):
self.v = [max(a, b) for a, b in zip(self.v, msg_v)]
self.v[self.me] += 1
return list(self.v)
def compare(x, y):
le = all(a <= b for a, b in zip(x, y))
ge = all(a >= b for a, b in zip(x, y))
if le and ge:
return 'same'
return 'before' if le else 'after' if ge else 'concurrent'
위 두 클래스로 그림의 시나리오를 그대로 돌리면 표와 그림의 값이 모두 나온다.
실무에서 쓰는 곳
버전 충돌 감지. Amazon의 2007년 Dynamo 논문은 키마다 벡터 시계를 붙였다. 두 복제본에 쓰기가 갈라져 들어오면 둘의 벡터가 동시로 판정된다. 이때 저장소는 어느 한쪽을 버리지 않고 두 버전을 모두 돌려주고, 애플리케이션이 합친다. 논문의 예가 장바구니다. 두 버전의 상품을 합집합으로 합치면 담은 상품은 사라지지 않는다. 대신 지운 상품이 되살아날 수 있다는 한계도 논문에 적혀 있다.
동시 쓰기를 병합하는 자료구조. CRDT는 동시 수정이 와도 같은 결과로 수렴하게 설계한 자료구조다. 동시 판정이 필요한 구현(동시에 추가와 삭제가 온 집합 등)은 벡터 시계나 그 변형으로 인과를 추적한다.
크기 문제. 벡터 길이는 쓰기에 참여하는 노드 수만큼 자란다. 클라이언트마다 칸을 주면 끝없이 길어진다. Dynamo는 서버(코디네이터) 단위로 칸을 두고 오래된 칸을 잘라 냈다. 자르면 잘못 동시로 판정될 수 있으니, 자르는 기준은 성능이 아니라 충돌 허용 범위로 정해야 한다. Riak 같은 저장소는 dotted version vector로 이 크기와 거짓 충돌을 줄였다.
전부에 필요하지는 않다. Cassandra처럼 셀마다 타임스탬프로 마지막 쓰기 승리를 택한 저장소도 많다. 동시 쓰기를 사람이 합칠 이유가 없는 데이터라면 그 편이 단순하다. 다만 이때는 앞에서 본 시계 오차로 새 값이 질 수 있다는 점을 받아들인 것이다.
Hybrid Logical Clock과 TrueTime
Lamport 값은 실제 시각과 상관이 없어서 "어제 오후 3시 기준 스냅숏"처럼 시각으로 묻는 질의에 쓸 수 없다. Sandeep Kulkarni 등이 2014년에 제안한 Hybrid Logical Clock(HLC)은 이 틈을 메운다. 값은 (l, c) 쌍이다. l은 지금까지 본 물리 시각 중 가장 큰 값, c는 l이 같을 때 올리는 카운터다. 받을 때는 Lamport처럼 메시지 값과 비교해 큰 쪽을 따른다.
그래서 HLC는 a → b이면 HLC(a) < HLC(b)라는 Lamport의 보장을 지키면서도, 값이 물리 시각에서 크게 멀어지지 않는다. CockroachDB가 트랜잭션 타임스탬프에 HLC를 쓴다. 동시 판정은 여전히 못 하므로, 필요하면 벡터 시계를 따로 둔다.
Google Spanner의 TrueTime은 방향이 다르다. GPS와 원자시계로 시계 오차의 범위를 직접 재고, 현재 시각을 [가장 이른 값, 가장 늦은 값] 구간으로 돌려준다. 커밋할 때 그 구간이 지날 때까지 기다려(commit wait) 물리 시각 순서가 곧 인과 순서가 되게 만든다. 논리 시계가 "시계를 믿지 않는" 방법이라면 TrueTime은 "오차를 재서 기다리는" 방법이고, 특수 하드웨어가 필요하다.
| 무엇을 | 언제 쓰나 | 없으면 생기는 일 |
|---|---|---|
| 단조 시계 | 한 서버 안의 경과 시간 | 시계 보정 때 음수 소요 시간 |
| Lamport Clock | 인과를 어기지 않는 전체 순서, 로그 정렬 | 결과가 원인보다 먼저 찍힘 |
| Vector Clock | 동시 쓰기 감지와 병합 | 한쪽 쓰기가 조용히 사라짐 |
| HLC | 인과 보장 + 시각 기준 스냅숏 | 시각으로 묻는 질의 불가 |
자주 하는 실수
Lamport 값이 작으면 먼저라고 해석한다. 보장은 "먼저면 작다"뿐이다. 작다고 먼저는 아니다. 동시 여부가 필요하면 벡터를 쓴다.
받을 때 +1을 빠뜨린다. max(내 값, 메시지 값)만 하면 받기 이벤트가 보내기 이벤트와 같은 값을 가져 인과가 동점으로 뭉개진다.
동점을 가르지 않고 정렬한다. 같은 L을 가진 이벤트의 순서가 노드마다 달라지면, 같은 로그를 재생해도 노드마다 결과가 다르다. (L, 노드 ID)처럼 모두가 같은 규칙으로 가른다.
벡터 칸을 클라이언트마다 준다. 클라이언트 수만큼 배열이 자라 메타데이터가 데이터보다 커진다. 칸은 쓰기를 조정하는 서버 단위로 둔다.
HLC를 동시 판정에 쓴다. HLC는 Lamport와 같은 한 방향 보장만 준다. HLC 값이 다르다고 인과가 있는 것은 아니다.
점검표
- 서버 간 순서를 벽시계 타임스탬프로만 정하는 곳을 목록으로 만들었다.
- 경과 시간 측정에는 단조 시계를 쓴다.
- Lamport 구현이 받을 때
max + 1을 한다. - 메시지에 보내기 직전에 올린 값을 싣는다.
- 전체 순서가 필요한 곳은
(L, 노드 ID)로 동점을 가른다. - 동시 쓰기를 감지해야 하는 데이터와 마지막 쓰기 승리로 충분한 데이터를 구분했다.
- 벡터 시계의 칸 단위(서버 또는 복제본)와 최대 길이를 정했다.
- 벡터 칸을 자를 때 생길 수 있는 거짓 충돌을 애플리케이션이 처리한다.
- 동시로 판정된 두 버전을 합치는 규칙을 문서로 남겼다.
- 시각 기준 질의가 필요하면 HLC 같은 물리 시각 결합 방식을 검토했다.
분산 시스템에서 순서는 시계가 아니라 메시지가 만든 인과로 정하고, 한 방향 보장으로 충분하면 Lamport Clock, 동시까지 가려야 하면 Vector Clock, 실제 시각도 함께 필요하면 HLC를 고른다.
댓글 0개
아직 댓글이 없습니다. 첫 댓글을 남겨보세요.