Brain258. 벡터 시계 (Vector Clock) / 타임스탬프
핵심 인사이트 (3줄 요약)
- 본질: 벡터 시계는 분산 시스템에서事件的因果関係(causal ordering)를 추적하기 위한 자료구조로, 각 노드가 자신의 논리적 시계를 유지하고, 두 버전의 데이터 중 어느 것이 더 최근인지 판단할 수 있게 해준다.
- 가치: 결과적 일관성 환경에서 복제 충돌을 감지하고 해결하는 데 핵심적인 역할을 하며, 단순 타임스탬프보다 정확한因果관계 추적이 가능하다.
- 융합: CAP 정리, Eventually Consistency, 복제 전략, 맵리듀스, 분산 로그와 밀접하게 연관되며, DynamoDB, Riak, Cassandra 등의 분산 데이터베이스에서 활용된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
개념 정의
벡터 시계(Vector Clock)는 분산 시스템에서事件的因果관계(causal ordering)를 추적하기 위한 논리적 시계 기법이다. 각 노드가 자신만의 논리적 카운터를 유지하는 벡터를 가지고 있으며, 이를 통해 두 이벤트가 동시에 발생했는지, 혹은 어떤 이벤트가 원인인지를 판단할 수 있다. 이는 단순 물리적 타임스탬프만으로는不可能한因果관계 추적을 가능하게 한다.
필요성
분산 시스템에서 여러 노드가 동시에 쓰기 작업을 수행하면, 어느 쓰기가 더 최근에 발생했는지 물리적 시간만으로는 판단할 수 없다. 또한 네트워크 지연으로 인해 순서가 바뀔 수 있다. 벡터 시계는 이러한 문제을 해결하여, 노드 간 복제 충돌을 감지하고 해결하는 데 필수적인 역할을 한다.
배경
벡터 시계는 1988년 Colin Fidge, Jong-Hoon Ohlsson, Adam Wigley 등 연구자들이 제안했으며, 분산 시스템의 因果関係 추적에 중요한 도구로 자리잡았다. Amazon Dynamo 논문(2007)에서 벡터 시계를 활용한 충돌 감지 및 해결 방안을 제시한 이후, 대규모 분산 시스템에서 널리 활용되고 있다.
물리적 타임스탬프의 한계
┌─────────────────────────────────────────────────────────────────────────────┐
│ 물리적 타임스탬프의 한계 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 물리적 시계의 문제: │
│ ────────────────── │
│ 1. Clock Skew: 서로 다른 서버의 시계가 항상 일치하지 않음 │
│ • 서버 A: 10:00:00.100 │
│ • 서버 B: 10:00:00.050 (네트워크 지연으로 늦게 수신) │
│ • 서버 C: 10:00:00.200 (시계가 빨리 감) │
│ │
│ 2. 순서 역전: 네트워크 지연으로 인해 后来의 쓰기가 먼저 기록될 수 있음 │
│ T1: Client → Server A (10:00:00.100) │
│ T2: Client → Server B (10:00:00.095) ← 네트워크 지연으로 늦게 수신 │
│ ※ 물리적 시간만으로는 T1이 T2보다 나중임에도 B가 먼저 기록된 것처럼 보임 │
│ │
│ 3. 동시 쓰기 판단 불가: 같은 시간에 두 쓰기가 발생하면 어떤 것이 진짜 나중인지 │
│ 판단할 수 없음 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 물리적 시계 vs 벡터 시계 비교 │ │
│ │ │ │
│ │ 물리적 시계: │ │
│ │ • 절대 시간 제공 │ │
│ │ •Clock Skew 문제로 분산 환경에서 신뢰성 낮음 │ │
│ │ • "언제"는 알 수 있지만 "因果관계"는 알 수 없음 │ │
│ │ │ │
│ │ 벡터 시계: │ │
│ │ • 논리적 시간 제공 │ │
│ │ • 각 노드의 因果関係 추적 │ │
│ │ • "언제"보다 "어떤 собы트가 어떤事件를 발생시켰는지" 추적 가능 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
비유
벡터 시계는 SNS의 "읽지 않은 메시지" 표시와 같다. 누군가 메시지를 보내면 받는 사람마다 "내가 언제 읽었는지"가 기록되어, 전체 메시지 흐름에서 정확한 순서를 알 수 있다. 단순히 "보낸 시간"만으로는 알 수 없는 因果関係를 파악할 수 있다.
📢 섹션 요약: 벡터 시계는 물리적 시계의Clock Skew와 순서 역전 문제를 해결하여, 분산 환경에서 정확한 因果관계 추적을 가능하게 하는 논리적 시계 기법이다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
벡터 시계 동작 원리
┌─────────────────────────────────────────────────────────────────────────────┐
│ 벡터 시계 동작 원리 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [벡터 시계 구조] │
│ │
│ 각 노드가 유지하는 논리적 시계 벡터: │
│ VC = [Node_A: 3, Node_B: 2, Node_C: 1] │
│ │
│ • Node_A의 논리적 시계: 3 │
│ • Node_B의 논리적 시계: 2 │
│ • Node_C의 논리적 시계: 1 │
│ │
│ [작동 규칙] │
│ │
│ 규칙 1: 로컬 이벤트 발생 시 → 해당 노드의 카운터 1 증가 │
│ ───────────────────────────────────────────────── │
│ Node_A에서 이벤트 발생: │
│ VC_A = [Node_A: 2, Node_B: 1, Node_C: 1] │
│ → VC_A = [Node_A: 3, Node_B: 1, Node_C: 1] (A만 증가) │
│ │
│ 규칙 2: 메시지 수신 시 → max(로컬, 수신) 후 로컬 카운터 1 증가 │
│ ───────────────────────────────────────────────── │
│ Node_A가 Node_B로부터 VC_B 수신: │
│ VC_A = [Node_A: 3, Node_B: 1, Node_C: 1] │
│ VC_B = [Node_A: 2, Node_B: 2, Node_C: 1] │
│ │
│ VC_A_new = [Node_A: max(3,2)+1=4, Node_B: max(1,2)=2, Node_C: max(1,1)=1] │
│ = [Node_A: 4, Node_B: 2, Node_C: 1] │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 벡터 시계의 핵심은 각 노드가 자신만의 카운터만 증가시키고, 메시지 교환 시 상대방의 카운터와 비교하여最大值을 취하는 것이다. 이를 통해 어떤 노드가 다른 노드보다 앞서가고 있는지를 알 수 있다. 예를 들어 VC_A = [3, 1, 1]이고 VC_B = [2, 2, 1]이라면, A는 B보다 먼저 시작했지만 B가追赶하여現在는 B의 Node_B 카운터가 A보다 높다.
동시성 판단 알고리즘
┌─────────────────────────────────────────────────────────────────────────────┐
│ 벡터 시계 기반 동시성 판단 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 두 벡터 VC1과 VC2가 있을 때: │
│ │
│ 비교 결과: │
│ ───────── │
│ 1. VC1 < VC2 (VC1이 먼저): VC1的所有分量 ≤ VC2이고, 적어도 하나는 < │
│ 예: VC1 = [1, 2], VC2 = [2, 2] │
│ → VC1의 모든 요소가 VC2 이하이고, 1 < 2이므로 VC1 < VC2 │
│ │
│ 2. VC1 > VC2 (VC2가 먼저): VC1의 모든分量 ≥ VC2이고, 적어도 하나는 > │
│ 예: VC1 = [3, 2], VC2 = [2, 2] │
│ → VC1 > VC2 │
│ │
│ 3. VC1 || VC2 (동시 발생): VC1의 일부 > VC2이고, 일부 < VC2 │
│ 예: VC1 = [2, 2], VC2 = [1, 3] │
│ → Node_A: 2 > 1, Node_B: 2 < 3 → 동시 발생 (충돌) │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 충돌 해결 시나리오 │ │
│ │ │ │
│ │ Version 1: VC=[A:1, B:0, C:0] → "value": "Kim" │ │
│ │ Version 2: VC=[A:1, B:1, C:0] → "value": "Lee" (Node B에서 수정) │ │
│ │ Version 3: VC=[A:1, B:0, C:1] → "value": "Park" (Node C에서 수정) │ │
│ │ │ │
│ │ Version 2와 Version 3을 비교: │ │
│ │ • Node_A: 1 == 1 │ │
│ │ • Node_B: 1 > 0, 1 > 1 (아니고) → 1 > 0 → Version 2가 앞섬 │ │
│ │ • Node_C: 0 < 1, 0 < 1 (아니고) → 0 < 1 → Version 3이 앞섬 │ │
│ │ • 결과: 동시 수정 (충돌) 발생 │ │
│ │ │ │
│ │ 해결: Last Writer Wins, Application-level merge 등 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 벡터 시계의 핵심은 "동시 발생(Concurrent)"를 감지할 수 있다는 점이다. 단순 타임스탬프로는 동시에 발생한 쓰기 중 어느 것이 진짜 나중인지 알 수 없지만, 벡터 시계는 이를 감지하여 충돌로 처리할 수 있게 해준다. 이는 Eventually consistent 시스템에서 데이터 충돌을 정확히 파악하고 적절히 해결하는 데 필수적이다.
Version Vectors
┌─────────────────────────────────────────────────────────────────────────────┐
│ Version Vectors (VV) vs 벡터 시계 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Version Vectors는 벡터 시계의 应用特화 버전으로, 분산 파일 시스템나 │
│ 키-값 저장소에서 복제본 버전 추적에 사용된다. │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Version Vectors 동작 예시 │ │
│ │ │ │
│ │ Object Version 1: VV = {NodeA: 1} → "Kim" │ │
│ │ │ │
│ │ Node A에서 수정: │ │
│ │ Object Version 2: VV = {NodeA: 2} → "Lee" │ │
│ │ │ │
│ │ Node B에서 수정 (Version 1基础上): │ │
│ │ Object Version 3: VV = {NodeA: 1, NodeB: 1} → "Park" │ │
│ │ │ │
│ │ 비교: │ │
│ │ • Version 2 ({NodeA: 2}) vs Version 3 ({NodeA: 1, NodeB: 1}) │ │
│ │ • NodeA: 2 > 1, NodeB: undefined < 1 → 동시 발생! │ │
│ │ • 충돌! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ DynamoDB, Riak, Cassandra에서 활용: │
│ • DynamoDB: Version ID (업데이트 마다 고유 ID 생성) │
│ • Riak: 벡터 시계 직접 사용 │
│ • Cassandra: Timestamp 기반 (Last Writer Wins) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: 벡터 시계는 분산 환경에서事件的 因果관계를 추적하며, 두 버전의 데이터가 동시 수정인지 판단할 수 있게 해준다.
Ⅲ. 구현 및 실무 응용 (Implementation & Practice)
Riak에서의 벡터 시계 활용
# Riak에서 벡터 시계를 사용한 충돌 감지 예시
import riak
client = riak.RiakClient()
bucket = client.bucket('users')
# 쓰기: 벡터 시계 자동 증가
user = bucket.new('user:123', data={'name': 'Kim', 'age': 30})
user.store()
# 읽기: 벡터 시계 포함 반환
fetched = bucket.get('user:123')
print(f"Value: {fetched.data}") # {'name': 'Kim', 'age': 30}
print(f"Vector Clock: {fetched.vclock}") # 벡터 시계 정보
# 두 노드에서 동시 수정 시뮬레이션
# Node A에서 수정
obj_a = bucket.get('user:123')
obj_a.data['name'] = 'Lee'
obj_a.store()
# Node B에서 동시 수정 (Vector ClockConflict)
obj_b = bucket.get('user:123')
obj_b.data['name'] = 'Park'
obj_b.store()
# 충돌 감지: Riak는 두 버전을 모두 저장
resolved = bucket.get('user:123')
print(f"Data after conflict: {resolved.data}")
# → Riak는 siblings(형제)를 생성하여 충돌 버전을 모두 유지
# → 애플리케이션에서 해결策略 선택 필요
충돌 해결 전략
┌─────────────────────────────────────────────────────────────────────────────┐
│ 벡터 시계 기반 충돌 해결 전략 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 전략 1: Last Writer Wins (LWW) │
│ ───────────────────────────────────────────────────────────────────── │
│ • 가장 최신 타임스탬프(또는Version)를 가진 쓰기만 유지 │
│ • 단순하고高效적 │
│ • 그러나 일부 데이터 손실 발생 가능 │
│ • 예: Cassandra │
│ │
│ 전략 2: Application-level Merge │
│ ───────────────────────────────────────────────────────────────────── │
│ • 애플리케이션에서 비즈니스 로직에 따라 병합 │
│ • 예: 카운터라면 합산, 리스트라면 합집합 │
│ • 가장 유연하지만 구현 복잡 │
│ • 예: Riak │
│ │
│ 전략 3: Structural Sharing │
│ ───────────────────────────────────────────────────────────────────── │
│ • 변경되지 않은 부분은 공유하여 메모리 절약 │
│ • 예: MongoDB document │
│ │
│ 전략 4: 자동 병합 (CRDT 활용) │
│ ───────────────────────────────────────────────────────────────────── │
│ • Conflict-free Replicated Data Types 사용 │
│ • G-Counter, PN-Counter, LWW-Register, OR-Set 등 │
│ • 자동으로 충돌 해소 │
│ • 예: Redis CRDT 모듈 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ CRDT 예시: G-Counter (Grow-only Counter) │ │
│ │ │ │
│ │ Node A에서 +1: Counter = {A: 1} │ │
│ │ Node B에서 +1: Counter = {A: 1, B: 1} │ │
│ │ Node A에서 +1: Counter = {A: 2, B: 1} │ │
│ │ │ │
│ │ 병합 (합산): Counter = {A: 2, B: 1} → 합계 = 3 │ │
│ │ ※ 어떤 순서로 병합해도 결과 동일! │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: 벡터 시계 기반 충돌 해결에는 Last Writer Wins, 애플리케이션 수준 병합, CRDT 활용 등이 있으며, 시스템 요구에 맞는 전략을 선택해야 한다.
Ⅳ. 품질 관리 및 테스트 (Quality & Testing)
벡터 시계 테스트
┌─────────────────────────────────────────────────────────────────────────────┐
│ 벡터 시계 관련 품질 테스트 항목 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [동시성 감지 테스트] │
│ ─────────────────── │
│ □ 두 노드에서 동시 쓰기 시 벡터 시계가 동시 발생으로 판단하는지 확인 │
│ □ 순차적 쓰기 시 벡터 시계가 정확한 因果관계 반영하는지 확인 │
│ │
│ [충돌 해결 테스트] │
│ ───────────────── │
│ □ 충돌 발생 시 선택한 전략(LWW, 병합 등)이 올바르게 동작하는지 확인 │
│ □ 충돌 해결 후 데이터 무결성 확인 │
│ □ 충돌 해소 과정의 로깅/감사 추적 │
│ │
│ [확장성 테스트] │
│ ───────────── │
│ □ 노드 수 증가 시 벡터 시계 크기 증가 (N-1 문제) │
│ □ 벡터 시계 크기 관리 (버킷팅, 정리 정책) 테스트 │
│ │
│ [일관성 테스트] │
│ ──────────── │
│ □ Eventually consistent 상태 도달 시간 측정 │
│ □ 네트워크 분단/복구 시 벡터 시계 동작 확인 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: 벡터 시계 테스트는 동시성 감지, 충돌 해결, 확장성, 일관성을 모두 검증해야 하며, 대규모 노드 환경에서의 동작을 사전에 확인해야 한다.
Ⅴ. 최신 트렌드 및 결론 (Trends & Conclusion)
Dotted Version Vectors
传统的 Version Vectors는 모든 노드의 카운터를 유지하므로 노드 수에 따라 크기가 증가한다. Dotted Version Vectors는 版本信息과 版本号을 분리하여 불필요한 정보를 제거함으로써 크기를 줄인다.
Hybrid Logical Clocks
Hybrid Logical Clocks (HLC)는 물리적 시계와 논리적 시계의 장점을 결합한 것이다. 물리적 시계로 因果관계无关인 이벤트 ordering을 제공하고, 논리적 시계로 因果관계가 있는 이벤트 사이의 순서를 보장한다. CockroachDB, TiDB 등에서 활용된다.
결론
벡터 시계는 분산 시스템에서 因果관계 추적의 핵심 도구로서, Eventually consistent 환경에서 충돌 감지 및 해결에 필수적이다. 그러나 노드 수에 따라 크기가 증가하는 한계가 있으므로, practical实现에서는 크기 관리 정책이 필요하다. 최근에는 HLC나 CRDT 등 더욱 효율적인 대안이 연구되고 있다.
📢 섹션 요약: 벡터 시계는 분산 시스템의 因果관계 추적에 필수적이지만, 확장성 한계가 있으며 HLC나 CRDT 등 대안과 함께 고려해야 한다.
핵심 인사이트 ASCII 다이어그램 (Concept Map)
┌─────────────────────────────────────────────────────────────────────────────┐
│ Vector Clock Concept Map │
│ │
│ ┌───────────────────────────┐ │
│ │ Vector Clock │ │
│ │ (벡터 시계) │ │
│ └─────────────┬─────────────┘ │
│ │ │
│ ┌─────────────────┼─────────────────┐ │
│ ▼ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │
│ │ Causality │ │ 동시성 │ │ 충돌 감지 │ │
│ │ Tracking │ │ Detection │ │ & Resolution│ │
│ │ (因像관계추적)│ │ (동시발견) │ │ (충돌해결) │ │
│ └─────────────┘ └─────────────┘ └─────────────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ 관련 기술 │ │
│ │ Version Vectors | HLC | CRDT | DynamoDB | Riak │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 한계: N-1 문제 (노드 수 증가 시 벡터 크기 증가) │
│ 대안: Dotted Version Vectors, Hybrid Logical Clocks │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
참고
- 벡터 시계는 분산 시스템에서 因果관계 추적을 위한 논리적 시계 기법이다.
- 물리적 시계의Clock Skew 문제를 해결한다.
- Eventually consistent 환경에서 복제 충돌 감지에 활용된다.
- 노드 수에 따라 크기가 증가하는 N-1 한계가 있다.
- CRDT, HLC 등 대안과 함께 고려되어야 한다.