벡터 클락과 인과성: 이벤트 순서와 분산 추적

분산 시스템에는 시계가 없다

단일 프로세스에서 이벤트 순서를 판단하는 것은 쉽다. A가 B보다 먼저 실행되었다면, A의 타임스탬프가 더 작다. 문제는 분산 시스템에서 발생한다.

세 개의 노드 A, B, C가 각자의 시계를 갖고 있다고 하자. NTP로 동기화해도 몇 밀리초의 오차가 남는다. 이 정도면 마이크로초 단위 이벤트의 순서를 판단하기에는 충분히 위험하다. 더 심각한 문제는 시계가 멈추거나(VM 일시 정지), 앞으로 점프하거나(NTP 보정), 뒤로 이동(monotonicity 위반)할 수 있다는 것이다.

그렇다면 물리적 시간 없이도 "A가 B보다 먼저 일어났다"고 말할 수 있는가?

Leslie Lamport는 1978년 논문 Time, Clocks, and the Ordering of Events in a Distributed System에서 그 가능성을 보였다. 핵심 아이디어는 인과성(causality)을 시간의 대리자로 쓰는 것이다.

happens-before: 인과적 순서의 공리

happens-before 관계(→)는 두 이벤트 사이의 인과적 가능성을 정의한다. "A → B"는 A가 B에 인과적으로 영향을 줄 수 있다는 의미다.

세 조건 중 하나라도 성립하면 A → B이다:

1. 같은 프로세스: A와 B가 같은 프로세스에서 발생했고 A가 B보다 먼저 실행되었다.
2. 메시지 전달: A는 메시지 전송이고 B는 그 메시지의 수신이다.
3. 전이적 폐포: A → C이고 C → B이면 A → B이다.

어느 규칙으로도 순서를 결정할 수 없으면 두 이벤트는 동시적(concurrent)이다. 동시적 이벤트는 인과적 의존성 없이 독립적으로 발생했다. 둘 중 어느 것이 먼저라고 말할 수 없다.

이 정의의 핵심은 물리적 시간이 전혀 등장하지 않는다는 것이다.

Lamport 타임스탬프: 논리 시계의 기초

Lamport는 happens-before를 추적하는 간단한 메커니즘을 제안했다. 각 프로세스는 정수 카운터(논리 시계)를 유지한다.

규칙:

1. 이벤트가 발생하면 자신의 시계를 1 증가시킨다.
2. 메시지를 보낼 때 현재 시계 값을 함께 보낸다.
3. 메시지를 받으면 시계 = max(자신의 시계, 받은 값) + 1로 갱신한다.

Lamport 타임스탬프의 한계: T(A) < T(B)이면 A가 B보다 먼저일 수 있다는 것만 알 수 있다. A와 B가 동시적인지, 아니면 A → B인지 구분할 수 없다. 동시성을 감지하려면 더 풍부한 정보가 필요하다.

벡터 클락: 동시성을 감지하는 구조

벡터 클락(vector clock)은 각 프로세스가 모든 프로세스의 논리 시계를 배열로 유지하는 방법이다. N개의 프로세스가 있다면 각 노드는 길이 N의 정수 벡터를 갖는다.

규칙:

1. 처음에는 모든 값이 0: [0, 0, ..., 0]
2. 이벤트가 발생하면 자신의 인덱스만 1 증가
3. 메시지를 보낼 때 현재 벡터를 함께 전송
4. 메시지를 받으면 원소별 max를 취한 후 자신의 인덱스를 1 증가

벡터 클락 비교 규칙

두 벡터 V1, V2를 비교하는 규칙:

예시: [2,0,0]과 [0,0,1]을 비교하면—첫 번째 벡터는 P1에서 앞서고, 두 번째는 P3에서 앞선다. 어느 쪽도 다른 쪽의 모든 원소를 지배하지 않으므로 동시적이다.

Lamport와의 결정적 차이: 벡터 클락은 A → B인지, A ∥ B인지 정확히 구분한다. Lamport 타임스탬프로는 동시성을 감지할 수 없다.

실전: DynamoDB와 Riak의 버전 벡터

Amazon Dynamo의 활용

Amazon Dynamo(DynamoDB의 전신)는 높은 가용성을 위해 여러 복제본에 동시에 쓰기를 허용한다. 네트워크 분할이나 동시 쓰기로 인해 같은 키에 두 복제본이 서로 다른 값을 가질 수 있다—이것이 충돌(conflict)이다.

Dynamo는 객체마다 벡터 클락(버전 벡터)을 유지한다.

초기 상태:
  키 "cart:user42" = ["laptop"], VC = {서버A:1}

복제본 R1에 쓰기:
  키 "cart:user42" = ["laptop", "mouse"], VC = {서버A:2}

동시에 복제본 R2에 쓰기:
  키 "cart:user42" = ["laptop", "keyboard"], VC = {서버A:1, 서버B:1}

두 버전 모두 {서버A:1}로 시작하므로 동시 쓰기 → 충돌

Dynamo는 충돌하는 두 버전을 클라이언트에 모두 반환한다. 클라이언트가 합병(reconciliation)을 수행한다. 장바구니의 경우 두 목록의 합집합이 합리적인 기본값이다. 결과는 두 버전을 초과하는 벡터 클락과 함께 저장된다.

Riak의 발전: Dotted Version Vectors

Riak는 전통적인 벡터 클락의 "sibling 폭발" 문제를 해결하기 위해 DVV(Dotted Version Vectors)를 도입했다. 전통적 벡터 클락에서는 각 업데이트가 새 원소를 추가해 클락이 무한정 커질 수 있다. DVV는 이벤트의 점(dot)을 명시해 충돌을 더 정밀하게 추적하고 벡터 크기를 제한한다.

분산 추적에서의 인과성

현대 분산 추적(distributed tracing)은 벡터 클락의 아이디어를 실용적으로 적용한다.

OpenTelemetry Trace Context:

HTTP 헤더 traceparent에 담기는 trace-id와 span-id가 논리적 인과 체인을 만든다.

서비스 A가 요청 시작:
  traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
               ^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^
               버전  trace-id (128bit, 전체 요청 묶음)  parent-span-id  플래그

서비스 A → 서비스 B 호출:
  새 span-id 생성, parent-span-id = A의 span-id
  → 인과 관계가 헤더에 전파됨

서비스 B → 서비스 C 호출:
  다시 새 span-id, parent = B의 span-id

이 체인이 완성되면 Jaeger나 Zipkin에서 전체 요청 경로를 시각화할 수 있다.

벡터 클락과 분산 추적의 연결점: 분산 추적의 parent-span 관계는 단방향 인과 체인이다. 벡터 클락이 일반적인 "어느 이벤트가 어느 이벤트를 알고 있는가"를 추적한다면, 분산 추적은 "어느 요청이 어느 요청을 유발했는가"를 추적한다. 둘 다 물리적 시간 없이 인과 관계를 인코딩한다.

실무 운영에서의 인과성 문제

읽기-쓰기 인과성 위반

사용자가 프로필 사진을 업데이트한다 (Primary에 쓰기)
  → Primary → Replica 복제 지연 500ms

사용자가 바로 페이지를 새로고침한다 (Replica에서 읽기)
  → 이전 사진이 보인다 → 사용자 혼란

이 문제는 인과적 일관성(causal consistency) 위반이다. 자신이 방금 쓴 값을 읽지 못하는 것("read your own writes" 보장 실패)이다. 해결책은 쓰기를 수행한 사용자의 읽기를 일정 시간 동안 Primary로 라우팅하거나, 버전 벡터를 세션에 저장해 해당 버전 이상의 복제본에서만 읽도록 하는 것이다.

인과적 브로드캐스트

채팅 시스템에서 메시지 순서 문제가 생길 수 있다:

Alice: "저녁 먹었어?" (메시지 M1)
Bob: M1을 받고 "응 먹었어" (메시지 M2, M1에 인과 의존)
Carol: 네트워크 지연으로 M2를 M1보다 먼저 받는다
  → Carol 화면: "응 먹었어" → "저녁 먹었어?" (역전됨)

벡터 클락 기반 인과적 브로드캐스트(causal broadcast)는 각 메시지에 벡터 클락을 달아, 메시지가 의존하는 모든 메시지가 먼저 전달되었음을 확인한 후 전달한다. Apache Kafka의 파티션 순서 보장, Redis Streams의 메시지 ID, Kafka의 Lamport-style offset이 이 문제를 일부 해결하는 방식이다.

벡터 클락의 한계

크기 문제: 참여 프로세스 수만큼 벡터가 커진다. 수천 개의 마이크로서비스 인스턴스가 있다면 벡터 클락은 비실용적이다. 이 때문에 실제 시스템은 노드 집합을 그루핑하거나, DVV처럼 압축된 표현을 사용하거나, trace-id/span-id처럼 단방향 인과 체인으로 제한한다.

가비지 컬렉션: 오래된 벡터 항목을 정리하는 기준이 명확하지 않으면 메모리가 계속 증가한다.

완전한 순서가 아님: 벡터 클락은 동시적 이벤트들 사이에 순서를 부여하지 않는다. 동시적 이벤트들의 전체 순서(total order)가 필요하다면 Raft/Paxos 같은 합의 프로토콜이 필요하다.

기억할 문장

물리적 시간은 분산 시스템에서 믿을 수 없다. 인과성이 시계를 대체한다. 벡터 클락은 "A가 B를 알 때 A → B"라는 단순한 공리에서 출발해, 두 이벤트가 인과적으로 연결되어 있는지(순서가 있는지) 아니면 독립적으로 발생했는지(동시적인지) 정확히 구분한다.

이 구분이 중요한 이유는 동시적 쓰기는 충돌이고, 충돌은 해소 전략이 필요하기 때문이다. DynamoDB가 두 버전을 클라이언트에 돌려주는 것, 분산 추적이 span의 parent를 기록하는 것—모두 같은 아이디어의 다른 표현이다.

다음 장에서는 분산 스토리지의 핵심 과제인 샤딩, 파티셔닝, 데이터 지역성을 살펴본다.

References

• Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System — https://lamport.azurewebsites.net/pubs/time-clocks.pdf
• DeCandia, G. et al. (2007). Dynamo: Amazon's Highly Available Key-value Store — https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• Riak Documentation: Causal Context — https://docs.riak.com/riak/kv/2.2.3/learn/concepts/causal-context/index.html
• Riak: Vector Clocks Revisited — https://riak.com/posts/technical/vector-clocks-revisited/index.html?p=9545.html
• Preguiça, N. et al. (2010). Dotted Version Vectors: Logical Clocks for Optimistic Replication — https://arxiv.org/pdf/1011.5808
• Fidge, C. (1988). Timestamps in Message-Passing Systems That Preserve the Partial Ordering — https://www.semanticscholar.org/paper/Timestamps-in-Message-Passing-Systems-That-Preserve-Fidge/2f2f2ab0be7a7c5a3ec3c0fd08cc0f8c07ddaafe
• W3C Trace Context specification — https://www.w3.org/TR/trace-context/
• OpenTelemetry: Distributed Tracing Concepts — https://opentelemetry.io/docs/concepts/signals/traces/
• Kleppmann, M. (2017). Designing Data-Intensive Applications, Chapter 8: The Trouble with Distributed Systems — https://dataintensive.net/
• Baeldung: Lamport Clock — https://www.baeldung.com/cs/lamport-clock