[Computer Terms] 벡터 시계 (Vector Clocks)

이 장을 읽기 전에

CAP 정리와 합의 알고리즘에서 다룬 “여러 노드가 하나의 값에 합의하기 어렵다"는 문제와, 샤딩과 복제에서 다룬 복제 지연 개념을 안다고 가정한다. 이 챕터는 합의를 통해 값을 하나로 맞추는 대신, 애초에 “어떤 이벤트가 먼저 일어났는가"를 각 노드가 어떻게 판단할 수 있는지를 다룬다.

물리적 시계로는 순서를 알 수 없다

분산 시스템의 각 서버는 자신만의 하드웨어 시계를 갖고 있고, 이 시계들은 완벽히 동기화되지 않는다. NTP(Network Time Protocol) 같은 동기화 프로토콜을 쓰더라도 네트워크 지연과 클럭 드리프트(clock drift, 발진기 오차로 시계가 조금씩 어긋나는 현상) 때문에 밀리초 단위의 오차가 항상 남는다. 이 오차가 왜 문제가 되는지 구체적으로 보면, 서버 A가 타임스탬프 100을 찍어 이벤트를 기록하고, 서버 B가 99를 찍어 다른 이벤트를 기록했다고 해도, A의 시계가 B보다 5만큼 빠르게 맞춰져 있었다면 실제로는 B의 이벤트가 먼저 일어났을 수 있다. 즉 타임스탬프 값의 크고 작음이 실제 발생 순서를 보장하지 않는다 — 이것이 물리적 시계를 분산 시스템의 이벤트 순서 판단 기준으로 쓸 수 없는 근본 이유다.

이 문제는 단일 서버 안에서는 발생하지 않는다. 한 프로세스 안의 이벤트는 코드가 실행되는 순서 그대로 일어나므로, 순서를 알기 위해 시계가 필요 없다. 문제는 서로 다른 노드에서 일어난 두 이벤트의 순서를 어떻게 비교할 것인가로 좁혀진다.

인과 순서: happens-before 관계

Leslie Lamport는 1978년 논문에서 절대적인 시간 대신 **인과관계(causality)**로 이벤트 순서를 정의하는 방법을 제시했다. 이벤트 A가 이벤트 B보다 논리적으로 먼저(happens-before, A → B) 라고 말할 수 있는 경우는 셋으로 나뉜다. 같은 프로세스 안에서 A가 B보다 코드상 먼저 실행됐거나, A가 메시지를 보내는 이벤트이고 B가 그 메시지를 받는 이벤트이거나, A → C이고 C → B인 중간 이벤트 C가 존재해 전이적으로 연결되는 경우다. 이 세 조건 중 어디에도 해당하지 않는 두 이벤트는 **동시(concurrent)**라고 부른다 — 이는 “같은 시각에 일어났다"는 뜻이 아니라 “어느 쪽이 먼저인지 인과적으로 판단할 수 없다"는 뜻이다.

Lamport가 제안한 **논리적 시계(Lamport Timestamp)**는 각 노드가 정수 카운터 하나만 유지하며, 이벤트가 일어날 때마다 증가시키고 메시지를 주고받을 때 더 큰 값으로 맞춘다. 이 방식은 A → B이면 반드시 타임스탬프(A) < 타임스탬프(B)가 성립하도록 보장하지만, 역은 성립하지 않는다 — 타임스탬프만 보고는 두 이벤트가 실제로 인과관계인지 아니면 그냥 동시(concurrent)인데 우연히 순서가 매겨진 것인지 구분할 수 없다. 벡터 시계는 이 한계를 정확히 메우기 위해 고안됐다.

벡터 시계의 구조와 갱신 규칙

**벡터 시계(Vector Clock)**는 정수 하나 대신, 클러스터의 노드 수만큼의 원소를 가진 정수 벡터를 각 노드가 유지한다. N개의 노드가 있다면 각 노드는 길이 N짜리 벡터 [c1, c2, ..., cN]을 갖고, ci는 “노드 i가 관측한 노드 i 자신의 이벤트 개수"를 뜻한다. 갱신 규칙은 세 가지다. 노드가 로컬 이벤트를 처리할 때마다 자기 자신에 해당하는 원소를 1 증가시킨다. 메시지를 보낼 때는 현재 벡터 전체를 함께 첨부한다. 메시지를 받으면, 받은 벡터와 자신의 벡터를 원소별로 최댓값을 취해 병합한 뒤 자기 자신의 원소를 1 증가시킨다.

1
2
3
4
5
6
7
노드 A, B, C 3대, 벡터는 [A, B, C] 순서

1. A에서 이벤트 발생: A의 벡터 [1, 0, 0]
2. A가 B에게 메시지 전송 (벡터 [1, 0, 0] 첨부)
3. B가 메시지 수신: B의 벡터를 [0,0,0]과 받은 [1,0,0]의 원소별 최댓값으로 병합 → [1,0,0]
   그 후 B 자신의 원소 증가 → [1, 1, 0]
4. 같은 시각 C에서 독립적인 이벤트 발생: C의 벡터 [0, 0, 1]

이 예에서 B의 벡터 [1, 1, 0]과 C의 벡터 [0, 0, 1]을 비교하면, 어느 쪽도 다른 쪽의 모든 원소보다 크거나 같지 않다. 이럴 때 두 이벤트는 **동시(concurrent)**로 판정된다 — 즉 인과적으로 어느 쪽이 먼저인지 알 수 없고, 실제로 서로 독립적으로 일어났다.

벡터 시계로 인과관계 판정하기

두 벡터 시계 V1, V2를 비교하는 규칙은 다음과 같다. V1의 모든 원소가 V2의 대응 원소보다 작거나 같고 적어도 하나는 진짜로 작다면 V1 → V2(V1이 V2보다 인과적으로 먼저), 반대 방향이 성립하면 V2 → V1, 어느 쪽도 성립하지 않으면 두 이벤트는 동시(concurrent)다. 앞의 예에서 B의 [1,1,0]과 C의 [0,0,1]은 서로 비교 불가능하므로 동시로 판정된다.

이 판정이 실무에서 왜 중요한지는 분산 데이터베이스의 쓰기 충돌 감지에서 드러난다. Amazon Dynamo(2007년 논문에서 공개)는 벡터 시계를 사용해, 같은 키에 대한 두 쓰기가 인과관계인지 동시 쓰기(충돌)인지 구분한다. 인과관계라면 나중 값이 이전 값을 덮어써도 안전하지만, 동시 쓰기로 판정되면 시스템이 임의로 하나를 고르는 대신 두 값을 모두 보존하고 애플리케이션(또는 사용자)에게 병합을 맡긴다 — 쇼핑 카트에 서로 다른 기기에서 동시에 상품을 추가한 경우, 어느 한쪽만 남기면 데이터 손실이 발생하므로 두 변경을 합쳐야 하는 것이 그 예다.

벡터 시계의 한계: 확장성 문제

벡터 시계의 근본적인 단점은 벡터 크기가 노드 수에 비례한다는 점이다. 노드가 수천 대인 클러스터에서는 메시지마다 수천 개의 정수로 이루어진 벡터를 함께 보내야 하므로 오버헤드가 무시할 수 없는 수준이 된다. 실무에서는 이를 완화하기 위해 벡터의 원소를 클라이언트(요청을 보낸 주체) 단위로 제한하거나, 오래되어 더는 유용하지 않은 원소를 주기적으로 잘라내는 가지치기(pruning) 기법을 함께 쓴다. 이 트레이드오프 때문에 모든 시스템이 벡터 시계를 쓰는 것은 아니며, 정확한 인과 추적보다 단순한 최종 일관성으로 충분한 시스템은 CAP 정리와 합의 알고리즘에서 다룬 더 단순한 타임스탬프 기반 충돌 해결(예: 최종 쓰기 우선, Last-Write-Wins)을 택하기도 한다.

비교: 물리적 시계 vs 논리적 시계 vs 벡터 시계

특성	물리적 시계	Lamport 논리적 시계	벡터 시계
표현	실제 시각(ms)	정수 하나	노드 수만큼의 정수 벡터
순서 보장	동기화 오차로 부정확	happens-before면 순서 보장	happens-before와 동시성 모두 판정 가능
동시 이벤트 구분	불가능	불가능(타임스탬프만으로는 판단 불가)	가능
오버헤드	낮음	낮음(정수 하나)	노드 수에 비례해 증가

흔한 오개념

“벡터 시계는 실제 시간을 측정한다” — 벡터 시계의 각 원소는 “몇 시에 일어났는가"가 아니라 “그 노드에서 몇 번째 이벤트인가"를 센 값이다. 두 노드의 벡터를 비교해도 실제 경과 시간(초·밀리초)은 전혀 알 수 없다. 벡터 시계가 알려주는 것은 오직 인과관계(먼저/나중/동시) 뿐이다.

“동시(concurrent)로 판정되면 시스템 버그다” — 동시 판정은 오류가 아니라 정상적인 결과다. 서로 다른 두 사용자가 각자의 기기에서 동시에 같은 데이터를 수정했다면 그 두 이벤트는 실제로 인과관계가 없으므로 동시로 판정되는 것이 옳다. 문제는 이 상황을 감지하지 못하고 조용히 한쪽 데이터를 버리는 것이지, 동시성 자체가 아니다.

다른 개념과의 연결

벡터 시계가 감지하는 “동시 쓰기 충돌"은 CAP 정리와 합의 알고리즘에서 다룬 AP(가용성 우선) 시스템에서 특히 자주 발생한다 — CP 시스템은 합의를 통해 애초에 동시 쓰기 자체를 막지만, AP 시스템은 쓰기를 먼저 받아들이고 나중에 충돌을 감지해 처리하기 때문이다. 다음 챕터에서는 이런 재시도·중복 쓰기 상황에서 “같은 요청을 여러 번 보내도 결과가 같아야 한다"는 멱등성 개념을 다룬다.

평가 기준

이 챕터를 읽은 후에는 다음을 할 수 있어야 한다. 물리적 시계의 타임스탬프만으로 분산 시스템의 이벤트 순서를 판단할 수 없는 이유를 설명할 수 있다. happens-before 관계의 세 조건과, 이에 해당하지 않는 이벤트가 “동시"로 분류되는 이유를 설명할 수 있다. 두 벡터 시계를 비교해 인과관계(먼저/나중/동시)를 직접 판정할 수 있다. 벡터 시계가 노드 수에 비례해 커지는 확장성 문제와, 실무에서 이를 완화하는 방법을 설명할 수 있다.