19장. 인과를 기록하다 — 벡터 클록
만화로 보는 요약 — 먼저 읽어보세요
카운터 하나의 정보 부족 → 노드별 벡터와 원소별 비교 → 동시 충돌을 감지하는 대신 노드 수만큼 커지는 메타데이터.
면접 실전 질문: ① 벡터 클록의 로컬·발신·수신 규칙은 무엇인가? ② V(a) ≤ V(b)는 Lamport의 비교와 무엇이 다른 결론을 주는가? ③ 벡터 클록이 노드 churn 환경에서 무거워지는 이유는?
카운터 하나를 노드 수만큼의 벡터로 바꾸면, 두 이벤트가 정말 인과관계인지 아니면 서로 무관하게 동시에 일어난 것인지를 처음으로 구별할 수 있다 — 대신 그 벡터는 노드가 늘어날 때마다 함께 자란다.
면접 실전 질문: ① 벡터 클록의 세 규칙(로컬 이벤트, 발신, 수신)은 각각 무엇을 하는가? ②
V(a) ≤ V(b)가 성립하는 것과 Lamport의C(a) < C(b)가 성립하는 것은 어떻게 다른 결론을 보장하는가? ③ 벡터 클록이 실무에서 부딪히는 크기 문제는 왜 생기고, Dynamo류 스토어는 이걸 어떻게 안고 가는가?
배경 — 정수 하나엔 담을 수 없던 정보
18장은 질문 하나를 남기고 끝났습니다. 램포트 카운터는 a → b이면 반드시 C(a) < C(b)라는 걸 보장하지만, 그 역은 보장하지 않습니다. C(a) < C(b)라는 사실만으로는 a가 b의 원인인지, 아니면 둘이 서로 전혀 모르는 사이에 각자 카운터만 올린 동시적(concurrent) 이벤트인지 구별할 수 없었습니다. 실측 시뮬레이션에서 C(a)=1 < C(b)=4였지만, a와 b는 실제로는 어느 쪽으로도 메시지가 오간 적 없는 동시적 이벤트였죠.
문제는 정수 하나가 담을 수 있는 정보의 한계입니다. 카운터는 “지금까지 몇 번의 이벤트·메시지 교환이 누적됐는가”만 셀 뿐, 그 누적이 누구로부터 왔는지는 기록하지 않습니다. P2와 P3가 서로 활발히 메시지를 주고받아 카운터를 4까지 올리는 동안, P1은 그 대화에 전혀 끼지 않고도 낮은 카운터로 남아 있을 수 있습니다. 숫자만 보면 순서가 있어 보이지만, 그 뒤에 인과관계가 있는지는 숫자가 말해주지 않습니다.
18장의 마지막 질문이 정확히 이 지점을 가리켰습니다. 정수 하나가 아니라, 각 프로세스가 자신이 아는 만큼을 통째로 들고 있다면 어떨까? 이 장은 그 질문에 대한 답입니다.
스토리 — 카운터 하나에서 벡터 하나로
콜린 피지와 프리데만 마턴, 같은 답에 각자 도달하다
1988년, 콜린 피지(Colin Fidge)는 논문 “Timestamps in Message-Passing Systems That Preserve the Partial Ordering”(11th Australian Computer Science Conference, 1988)에서 프로세스마다 정수 하나 대신 벡터를 들게 하는 방법을 제안했습니다. 비슷한 시기 프리데만 마턴(Friedemann Mattern)도 서로의 작업을 모른 채 독자적으로 같은 구조에 도달해 “Virtual Time and Global States of Distributed Systems”(1988년 워크숍 발표, 1989년 논문)에서 발표했습니다. 오늘날 벡터 클록을 인용할 때 두 사람을 나란히 언급하는 게 관례인 이유입니다.
규칙은 세 개, 달라진 건 변수 하나
알고리즘의 뼈대는 18장과 놀랄 만큼 닮았습니다. 딱 하나, “정수 하나”가 “정수 배열 하나”로 바뀌었을 뿐입니다. N개의 프로세스가 있다면, 각 프로세스는 길이 N짜리 벡터 V를 하나씩 갖습니다. 자기 자신에게 배정된 슬롯 하나와, 나머지 프로세스에 대해 “그 프로세스의 사건을 몇 개나 알고 있는가”를 담은 슬롯들입니다.
- 로컬 이벤트를 처리할 때: 자기 슬롯만
+1.V[self] = V[self] + 1. - 메시지를 보낼 때: 자기 슬롯을
+1하고, 벡터 전체를 메시지에 실어 보낸다. - 메시지를 받을 때: 받은 벡터와 자기 벡터를 원소별로 max 취한 뒤, 자기 슬롯을
+1.
18장과 다른 점은 딱 하나, 수신 규칙의 max가 정수 하나가 아니라 벡터 전체에 걸쳐 원소별로 일어난다는 것뿐입니다. 그런데 이 작은 차이가 비교 규칙을 완전히 바꿔놓습니다.
비교 규칙 — 이 장이 존재하는 이유
두 벡터 V(a), V(b)를 비교할 때는 이렇게 합니다.
V(a) ≤ V(b)(모든 슬롯에서 a의 값이 b의 값 이하)이고V(a) ≠ V(b)이면,a → b.
18장의 보장은 한쪽으로만 성립했습니다 — a → b이면 C(a) < C(b)였지만, 역은 성립하지 않았죠. 벡터 클록의 비교 규칙은 양쪽으로 성립합니다. a → b이면 V(a) ≤ V(b)이고, 거꾸로 V(a) ≤ V(b)이면(V(a) ≠ V(b)인 한) 정말로 a → b입니다. 그리고 어느 쪽 벡터도 다른 쪽을 원소별로 완전히 지배하지 못하면 — 즉 V(a)의 어떤 슬롯은 더 크고 V(b)의 다른 슬롯은 더 크면 — 두 이벤트는 동시적입니다. 램포트 카운터로는 절대 알 수 없었던 것을, 벡터는 계산만으로 알려줍니다.
실측 — 18장과 똑같은 스크립트, 두 렌즈로 본다
18장의 세 프로세스 P1·P2·P3, 그리고 똑같은 메시지 스크립트를 그대로 재사용합니다. 이번엔 각 프로세스가 램포트 카운터와 벡터를 동시에 들고 다니게 해서, 같은 실행을 두 렌즈로 봅니다. 난수도 벽시계 호출도 없는 고정 스크립트라 몇 번을 돌려도 같은 결과가 나옵니다.
import java.util.Arrays;
public class VectorClockDemo {
static final int N = 3; // P1, P2, P3
static class Process {
final String name;
final int id; // 벡터에서 이 프로세스가 차지하는 인덱스
int lamport = 0;
int[] vector = new int[N];
Process(String name, int id) {
this.name = name;
this.id = id;
}
void local(String label) {
lamport += 1;
vector[id] += 1;
print("local", label);
}
int[] send(String label) {
lamport += 1;
vector[id] += 1;
print("send", label);
return vector.clone(); // 벡터 전체를 메시지에 실어 보낸다
}
void receive(String label, int receivedLamport, int[] receivedVector) {
lamport = Math.max(lamport, receivedLamport) + 1;
for (int i = 0; i < N; i++) {
vector[i] = Math.max(vector[i], receivedVector[i]);
}
vector[id] += 1;
print("receive", label);
}
void print(String type, String label) {
System.out.printf("%-2s | %-9s | %-20s | C=%-2d | V=%s%n",
name, type, label, lamport, Arrays.toString(vector));
}
}
// -1: a -> b (b의 벡터가 a의 벡터를 지배, a가 원인)
// 1: b -> a
// 0: 동일 벡터
// 2: 동시적(concurrent) -- 어느 쪽도 다른 쪽을 지배하지 않음
static int compare(int[] a, int[] b) {
boolean aLeqB = true, bLeqA = true;
for (int i = 0; i < a.length; i++) {
if (a[i] > b[i]) aLeqB = false;
if (b[i] > a[i]) bLeqA = false;
}
if (Arrays.equals(a, b)) return 0;
if (aLeqB) return -1;
if (bLeqA) return 1;
return 2;
}
static String describe(int[] a, int[] b) {
switch (compare(a, b)) {
case -1: return "a -> b (a가 b의 원인)";
case 1: return "b -> a (b가 a의 원인)";
case 0: return "a = b (동일 벡터)";
default: return "a || b (동시적 concurrent -- 어느 쪽도 다른 쪽을 지배하지 않음)";
}
}
public static void main(String[] args) {
Process p1 = new Process("P1", 0);
Process p2 = new Process("P2", 1);
Process p3 = new Process("P3", 2);
System.out.println("=== 1. 18장과 동일한 스크립트를 두 렌즈로 본다 (고정 순서, 랜덤 없음) ===");
p1.local("a (기준 이벤트)");
int[] aVec = p1.vector.clone();
int aLamport = p1.lamport;
p2.local("e1");
p3.local("e1");
int[] m1Vec = p2.send("m1 -> P3");
int m1Lamport = p2.lamport;
p3.receive("m1 from P2", m1Lamport, m1Vec);
p3.local("b (비교 대상)");
int[] bVec = p3.vector.clone();
int bLamport = p3.lamport;
int[] m2Vec = p1.send("m2 -> P2");
int m2Lamport = p1.lamport;
p2.receive("m2 from P1", m2Lamport, m2Vec);
int[] m3Vec = p2.send("m3 -> P3");
int m3Lamport = p2.lamport;
p3.receive("m3 from P2", m3Lamport, m3Vec);
int[] p3rm3Vec = p3.vector.clone();
System.out.println();
System.out.println("=== 2. 센터피스 -- 18장에서 C(a) < C(b)였던 그 쌍을 벡터로 다시 비교 ===");
System.out.println("V(a) = " + Arrays.toString(aVec) + " (Lamport C(a)=" + aLamport + ")");
System.out.println("V(b) = " + Arrays.toString(bVec) + " (Lamport C(b)=" + bLamport + ")");
System.out.println("비교 결과: " + describe(aVec, bVec));
System.out.println();
System.out.println("=== 3. 대조군 -- 실제로 인과관계가 있는 쌍은 벡터가 지배 관계를 보인다 ===");
System.out.println("V(a) = " + Arrays.toString(aVec));
System.out.println("V(P3.recv(m3)) = " + Arrays.toString(p3rm3Vec));
System.out.println("비교 결과: " + describe(aVec, p3rm3Vec));
System.out.println();
System.out.println("=== 4. (참고) 벡터 크기는 노드 수에 정비례한다 ===");
int[] nodeCounts = {3, 5, 10, 50, 200};
for (int n : nodeCounts) {
System.out.printf("노드 수=%-4d -> 이벤트 하나당 벡터 원소 수=%d개%n", n, n);
}
}
}=== 1. 18장과 동일한 스크립트를 두 렌즈로 본다 (고정 순서, 랜덤 없음) ===
P1 | local | a (기준 이벤트) | C=1 | V=[1, 0, 0]
P2 | local | e1 | C=1 | V=[0, 1, 0]
P3 | local | e1 | C=1 | V=[0, 0, 1]
P2 | send | m1 -> P3 | C=2 | V=[0, 2, 0]
P3 | receive | m1 from P2 | C=3 | V=[0, 2, 2]
P3 | local | b (비교 대상) | C=4 | V=[0, 2, 3]
P1 | send | m2 -> P2 | C=2 | V=[2, 0, 0]
P2 | receive | m2 from P1 | C=3 | V=[2, 3, 0]
P2 | send | m3 -> P3 | C=4 | V=[2, 4, 0]
P3 | receive | m3 from P2 | C=5 | V=[2, 4, 4]
=== 2. 센터피스 -- 18장에서 C(a) < C(b)였던 그 쌍을 벡터로 다시 비교 ===
V(a) = [1, 0, 0] (Lamport C(a)=1)
V(b) = [0, 2, 3] (Lamport C(b)=4)
비교 결과: a || b (동시적 concurrent -- 어느 쪽도 다른 쪽을 지배하지 않음)
=== 3. 대조군 -- 실제로 인과관계가 있는 쌍은 벡터가 지배 관계를 보인다 ===
V(a) = [1, 0, 0]
V(P3.recv(m3)) = [2, 4, 4]
비교 결과: a -> b (a가 b의 원인)
=== 4. (참고) 벡터 크기는 노드 수에 정비례한다 ===
노드 수=3 -> 이벤트 하나당 벡터 원소 수=3개
노드 수=5 -> 이벤트 하나당 벡터 원소 수=5개
노드 수=10 -> 이벤트 하나당 벡터 원소 수=10개
노드 수=50 -> 이벤트 하나당 벡터 원소 수=50개
노드 수=200 -> 이벤트 하나당 벡터 원소 수=200개(✅ 실측 — 2026년 7월, Temurin JDK 21 컨테이너, 고정 스크립트·난수 없음. Lamport 카운터 값은 18장의 출력과 한 줄 한 줄 동일합니다 — 같은 실행을 두 시계로 재는 것뿐이니까요.)
여기가 이 장의 센터피스입니다. 18장은 C(a)=1 < C(b)=4라는 사실만 보고 “a가 b보다 먼저다”라고 오해할 위험을 지적했습니다. 벡터로 다시 보면 V(a)=[1,0,0], V(b)=[0,2,3]입니다. 첫 번째 슬롯(P1)만 보면 a가 크고, 두 번째·세 번째 슬롯(P2, P3)만 보면 b가 큽니다. 어느 쪽도 다른 쪽을 원소별로 완전히 덮지 못해요. 알고리즘은 이걸 그대로 “동시적”이라 보고합니다 — 램포트 카운터의 대소 비교가 넌지시 암시했던 순서는 애초에 존재하지 않았다는 걸, 이번엔 증명한 겁니다.
3번 블록은 반대 경우입니다. V(a)=[1,0,0]과 V(P3.recv(m3))=[2,4,4]를 비교하면 모든 슬롯에서 a가 작거나 같고, 벡터 전체가 같지도 않습니다. V(a) ≤ V(P3.recv(m3))가 원소별로 성립하니 a → P3.recv(m3)입니다. 실제로 a는 m2를 거쳐 P2에 전달되고, P2가 다시 m3으로 P3에 전달하면서 P3의 벡터 첫 슬롯에 a의 흔적(1)이 그대로 남아 있는 겁니다. happened-before의 전이성이 벡터 위에 눈에 보이는 흔적으로 남은 셈이죠.
핵심 — 두 방향으로 성립하는 대가, 몸집
왜 두 방향으로 성립하는가
램포트 카운터가 한쪽으로만 성립했던 이유는 정수 하나에는 “누구의 사건을 얼마나 알고 있는가”를 프로세스별로 구분할 자리가 없었기 때문입니다. 벡터는 그 자리를 프로세스 수만큼 마련해둔 겁니다. V(a)[i]는 “a가 일어난 시점까지, a를 만든 프로세스가 프로세스 i의 이벤트를 몇 개나 인과적으로 알고 있었는가”를 정확히 기록합니다. 그러니 V(a) ≤ V(b)가 원소별로 성립한다는 건 “b가 아는 모든 프로세스의 사건 이력을, a도 최소한 그만큼은 알고 있었다”는 뜻이고, 이건 곧 a가 b보다 인과적으로 앞서거나 같은 지점에서 일어났다는 것과 정확히 같은 말입니다. 정보를 뭉개지 않고 프로세스별로 나눠 들고 다니니, 비교가 양방향 참·거짓을 모두 말해줄 수 있는 겁니다.
대가 — 벡터는 노드 수만큼 자란다
이 정확함에는 값이 붙습니다. 벡터의 길이는 시스템에 참여하는 노드 수와 같습니다. 노드가 3개면 이벤트 하나마다 정수 3개, 200개면 정수 200개를 들고 다녀야 합니다. 위 시뮬레이션의 4번 블록이 그 비례 관계를 그대로 보여줍니다 — 이건 추정이 아니라 벡터 클록의 정의 자체에서 나오는 구조적 비용입니다.
노드 수가 고정돼 있으면 이 비용은 그냥 “메시지마다 몇 바이트 더 붙는다” 정도로 끝납니다. 문제는 churn, 즉 노드가 계속 들어오고 나가는 시스템입니다. 새 노드가 들어올 때마다 벡터에 슬롯을 하나씩 늘려야 하고, 나간 노드의 슬롯을 지우고 싶어도 함부로 지울 수 없습니다 — 그 슬롯이 다른 이벤트의 인과 이력에 이미 섞여 들어가 있을 수 있기 때문입니다. 죽은 지 오래된 노드의 슬롯을 안전하게 걷어내는 문제(가지치기, pruning)는 벡터 클록 자체의 규칙만으로는 풀리지 않는, 여전히 연구·엔지니어링 대상인 어려운 문제입니다. 그래서 벡터 클록은 “람포트 카운터보다 무조건 나은 상위 호환”이 아니라, 정확함과 몸집을 맞바꾼 트레이드오프입니다.
현장으로 — 승자를 고르지 않고, 갈라진 채로 남긴다
17장에서 본 last-write-wins(LWW)는 두 쓰기 중 하나를 골라 나머지를 조용히 지웠습니다. Amazon의 Dynamo 논문은 정확히 반대 선택을 합니다. 각 데이터 버전에 벡터 클록을 붙여, 새 쓰기가 이전 버전을 인과적으로 덮어썼는지(V(이전) ≤ V(새 버전)) 아니면 동시에 갈라져 나온 것인지를 구분합니다. 후자로 판정되면 Dynamo는 임의로 승자를 고르지 않고 두 버전을 형제 버전(sibling version) 으로 나란히 저장한 뒤, 충돌 해소를 애플리케이션에 맡깁니다 — LWW가 “유실을 감수하고 하나를 고른다”였다면, 이쪽은 “고르지 않고 둘 다 보여준다”입니다.
📄 문서 기반(미검증) — Dynamo 논문은 프로덕션 쇼핑카트 트래픽 24시간을 관찰한 결과 99.94%는 버전이 하나(충돌 없음), 나머지가 2~4개의 형제 버전으로 갈라졌다고 보고합니다. 벡터 클록이 있어야 이 갈라짐 자체를 “감지”할 수 있다는 뜻입니다.
비슷하게 생겼지만 다른 개념 하나만 짚고 넘어갑니다. 일부 복제 시스템은 버전 벡터(version vector) 를 씁니다 — 이벤트마다가 아니라 복제본(replica)마다 슬롯 하나를 두고, 그 복제본이 데이터를 갱신할 때만 슬롯을 올리는 방식입니다. 벡터 클록이 “이벤트 사이의 인과관계”를 추적한다면, 버전 벡터는 “데이터 버전 사이의 인과관계”만 좁혀서 추적하는 사촌뻘 구조입니다. 이름이 비슷해 자주 혼동되지만, 무엇을 세는지가 다릅니다.
정리
- 18장은
C(a) < C(b)가 인과관계를 증명하지 못한다는 한계를 남기고 끝났다. 이 장은 카운터를 노드 수만큼의 벡터로 바꿔 그 한계를 해결한다. - 알고리즘은 세 규칙이다 — 로컬 이벤트에서 자기 슬롯
+1, 발신 시 자기 슬롯+1후 벡터 전체를 첨부, 수신 시 원소별max를 취한 뒤 자기 슬롯+1. - 비교는 양방향으로 성립한다.
V(a) ≤ V(b)(원소별)이고V(a) ≠ V(b)이면a → b— 그리고 그 역도 성립한다. 18장의 보장이 한쪽으로만 성립했던 것과 정확히 대비된다. 어느 쪽 벡터도 다른 쪽을 지배하지 못하면 동시적이며, 실측 시뮬레이션에서 18장의 그 쌍(C(a)=1 < C(b)=4)이 벡터로는[1,0,0]과[0,2,3]으로, 정말 동시적임을 직접 확인했다. - 대가는 몸집이다. 벡터 길이는 노드 수에 비례해 자라고, 노드가 계속 들고 나는 churn 환경에서는 자연스러운 상한이 없다. 오래된 노드의 슬롯을 안전하게 가지치기하는 문제는 여전히 어렵다.
- Dynamo는 벡터 클록으로 동시 쓰기를 감지해 승자를 고르는 대신 형제 버전으로 남기고 해소를 애플리케이션에 맡긴다 — 17장의 LWW와 정반대 선택이다. 📄 문서 기반(미검증) — 프로덕션 관찰에서 99.94%는 충돌 없이 단일 버전이었다.
- 버전 벡터는 이벤트가 아니라 복제본 단위로 슬롯을 두는, 벡터 클록과 이름은 닮았지만 세는 대상이 다른 별개의 구조다.
생각해볼 질문: 벡터 클록은 두 이벤트가 인과관계인지 동시적인지는 정확히 말해줍니다. 하지만 여전히 대답하지 못하는 게 있습니다. V(a)와 V(b)를 아무리 들여다봐도, a가 실제로 몇 시 몇 분에 일어났는지는 알 수 없습니다. 그리고 두 이벤트가 진짜 동시적이라고 판명 났을 때 — 시스템이 정말 하나의 전역 순서를 정해야만 하는 상황이라면, 벡터 클록은 그 둘 중 어느 걸 앞에 둘지 결정해줄 근거를 아무것도 갖고 있지 않습니다. 순서도 아니고 시각도 아닌, 그 사이 어딘가에 답이 있다면 어떤 모습일까요?