타임스탬프로 최신 쓰기를 고르면 왜 데이터가 조용히 사라지는가 — 벡터 시계와 버전 벡터

1. 벽시계로 "최신"을 고르면 어떤 일이 벌어지는가

멀티리더나 리더리스(Dynamo 계열) 복제에서 같은 키에 두 클라이언트가 거의 동시에 쓰면, 서버는 "둘 중 무엇을 남길까"를 정해야 한다. 가장 직관적인 답은 타임스탬프가 큰 쪽을 남기는 것(Last-Write-Wins, LWW)이다. 나도 처음엔 그거면 충분한 줄 알았다.

문제는 두 가지다. 첫째, 노드마다 벽시계가 어긋난다(clock skew). 둘째 — 이게 본질인데 — 벽시계는 인과관계를 표현하지 못한다. 서로 무관하게 발생한 두 쓰기 중 우연히 시각이 큰 쪽을 남기면, 다른 쪽 쓰기는 아무 에러도 없이 소실된다(lost update). 장바구니에 A가 담은 항목과 B가 담은 항목이 있는데, 하나가 통째로 사라지는 식이다.

그래서 Dynamo나 Riak 같은 실제 시스템은 벽시계 대신 벡터 시계(vector clock)와 버전 벡터(version vector)로 "이 두 쓰기는 애초에 순서가 없다(동시다)"를 먼저 판별한다. 이 글은 그 자료구조가 어떻게 벽시계 없이 인과관계를 판정하는지, 그리고 자주 같은 말로 쓰이는 두 개념이 무엇이 다른지를 정리한 것이다.

2. 왜 스칼라 논리 시계로는 부족한가 — Lamport 시계의 한계

Lamport 논리 시계는 카운터 하나(스칼라)다. 규칙은 단순하다.

• 로컬 이벤트마다 C += 1
• 메시지 송신 시 C를 실어 보냄
• 수신 시 C = max(C, C_msg) + 1

이렇게 하면 "a가 b의 원인이면 항상 C(a) < C(b)"라는 happens-before 보존은 된다. 하지만 역은 성립하지 않는다. C(a) < C(b)라고 해서 a가 b의 원인이라는 보장은 없다 — 서로 무관한 이벤트도 카운터 대소는 생기기 때문이다.

Lamport 시계는 전순서(total order)를 억지로 만들지만, 그 대가로 "동시성"이라는 정보를 지워버린다.

충돌을 감지하려면 "이 둘은 인과적으로 순서가 없다"를 알아야 하는데, 스칼라 하나로는 이걸 구분할 수 없다. 여기서 성분을 여러 개로 늘린 것이 벡터 시계다.

3. 벡터 시계 — 성분별 카운터로 동시성을 복원한다

노드가 N개면 각 노드는 길이 N의 벡터 V를 든다. V[i]는 "노드 i에서 일어난 것으로 내가 아는 이벤트 수"다.

규칙 (노드 i 기준):
- 로컬 이벤트/쓰기:      V[i] += 1
- 메시지 송신:          현재 V를 통째로 첨부
- 메시지 수신(V_msg):    for k: V[k] = max(V[k], V_msg[k]); 그다음 V[i] += 1

비교는 성분별로 한다. 그리고 이 비교가 전순서가 아니라 부분순서(lattice)라는 점이 핵심이다.

V_a ≤ V_b   ⟺  ∀k. V_a[k] ≤ V_b[k]
V_a < V_b   ⟺  V_a ≤ V_b 이고 V_a ≠ V_b     → a가 b의 조상 (happens-before)
V_a ∥ V_b   ⟺  둘 중 어느 쪽도 ≤ 가 아님       → 동시(concurrent) = 충돌

두 벡터가 서로를 지배하지 못하는 ∥ 경우가 바로 "동시 쓰기"다. 두 노드 예시로 손으로 따라가 보면 명확하다.

노드 A, B. 초기 (A:0, B:0)

A: 로컬 쓰기 → (A:1, B:0)  --- x1
B: 로컬 쓰기 → (A:0, B:1)  --- x2      # A 소식 아직 못 들음
  (A:1,B:0) 와 (A:0,B:1): 서로 ≤ 아님 → x1 ∥ x2  (동시, 충돌!)

A가 B의 x2 수신·병합 → (A:1,B:1), 로컬 쓰기 → (A:2, B:1)  --- x3
  (A:1,B:0) ≤ (A:2,B:1) 이고 다름 → x1 < x3  (x1은 x3의 조상, 안전하게 덮어씀)

병합 연산 join = 성분별 max는 격자의 최소상계(LUB)라서, 두 이력을 합치면 정확히 "둘 다 반영된" 벡터가 나온다. 이 성질은 뒤에서 CRDT와 연결된다.

4. 벡터 시계와 버전 벡터는 무엇이 다른가

구조는 둘 다 Map<노드ID, counter>로 같다. 그런데 증가 주체가 다르다 — 이걸 같은 말로 알고 있다가 확인하고 나서야 정리됐다.

구분	벡터 시계	버전 벡터
세는 대상	프로세스에서 일어난 이벤트	데이터 객체(키)의 복제본 버전
증가 주체	모든 로컬 이벤트에서 자기 성분++	그 쓰기를 조율한 복제본만 자기 성분++
단순 복제/전달	(해당 없음)	증가 아님, max 병합만
성분 수 유계성	프로세스 수	복제본 수(클라이언트로 잡으면 폭발)

Dynamo(§4.4)는 객체마다 버전 벡터를 context로 붙여 다닌다. 흐름은 이렇다.

1. get(key)  → 서버가 값 + context(버전 벡터) 반환
2. put(key, value, context) → 코디네이터 복제본이 context를 복사한 뒤
                              자기 성분 +1 하여 새 버전에 부착
3. 복제본이 값을 받으면 버전 벡터로 비교:
     - 들어온 것이 내 것의 자손(≥) → 덮어씀
     - 내 것이 들어온 것의 자손    → 무시
     - 서로 ∥(동시)               → 둘 다 보관 (sibling)
4. 다음 get 때 sibling 여러 개를 반환 → 애플리케이션(또는 CRDT)이
   reconcile 후 put하면 두 벡터의 join으로 수렴

여기서 벽시계는 어디에도 쓰이지 않는다. "최신"이 시각이 아니라 인과 지배 관계로 정의된다는 것이 이 설계의 핵심이다.

5. 코드로 확인하기

성분별 비교 규칙을 그대로 옮기면 이렇게 된다. DDIA Ch.5의 shopping cart 예제를 이 코드로 따라가 대소 판정이 일치하는지 확인했다.

// 성분별 비교로 인과관계 판정 (벽시계 없음)
enum Ord { BEFORE, AFTER, EQUAL, CONCURRENT }

static Ord compare(Map<String,Long> a, Map<String,Long> b) {
    boolean aLess = false, aGreater = false;
    Set<String> keys = new HashSet<>(a.keySet()); keys.addAll(b.keySet());
    for (String k : keys) {
        long va = a.getOrDefault(k, 0L), vb = b.getOrDefault(k, 0L);
        if (va < vb) aLess = true;
        if (va > vb) aGreater = true;
    }
    if (aLess && aGreater) return Ord.CONCURRENT; // ∥ → 충돌, sibling 보관
    if (aLess)  return Ord.BEFORE;
    if (aGreater) return Ord.AFTER;
    return Ord.EQUAL;
}

// join: 두 이력 병합 = 성분별 max (격자의 LUB)
static Map<String,Long> join(Map<String,Long> a, Map<String,Long> b) {
    Map<String,Long> r = new HashMap<>(a);
    b.forEach((k, v) -> r.merge(k, v, Math::max));
    return r;
}

compare((A:1,B:0), (A:0,B:1))은 한 성분은 작고 다른 성분은 크므로 CONCURRENT, compare((A:1,B:0), (A:2,B:1))은 모두 ≤이고 같지 않으므로 BEFORE가 나온다.

6. 벡터가 무한정 자라지 않는 이유 — truncation과 성분 설계

버전 벡터의 실무 부담은 메모리다. 쓰기에 관여하는 주체가 많아질수록 성분 수가 늘어 객체 하나에 붙는 메타데이터가 커진다. Dynamo는 각 (노드, 카운터)에 타임스탬프를 함께 저장하고, 벡터가 임계 크기(논문에서는 10개)를 넘으면 가장 오래된 성분부터 잘라낸다(truncation). 이건 이론적으로 "실제로는 조상인데 잘려서 concurrent로 보이는" 거짓 동시 오판을 만들 수 있지만, 실무에서는 거의 걸리지 않는다고 알려져 있다.

Riak은 노드ID를 클라이언트가 아니라 서버 vnode로 잡고, actor 수·시간·크기 기준으로 프루닝한다. 어느 쪽이든 규칙은 같다 — 성분을 클라이언트로 잡으면 폭발하고, 서버 복제본으로 잡으면 유계가 된다. 이 설계 선택이 성능을 좌우한다.

7. 정리

벡터 비교는 부분순서다. ≤도 ≥도 아닌 ∥(동시)가 존재하고, 그 지점이 곧 충돌이다. "더 큰 벡터"를 고르려고 전순서를 기대하면 바로 거기서 로직이 깨진다.

핵심을 한 줄로 남기면, LWW는 충돌 감지가 아니라 충돌 해소 정책일 뿐이다. 감지(이 둘은 동시다)를 버전 벡터가 먼저 해주고, 버릴지 병합할지는 그다음 애플리케이션의 몫이다. 감지 단계를 건너뛴 채 벽시계로 곧장 하나를 고르면 쓰기가 조용히 사라진다.

더 파고들 만한 것:

• CRDT (특히 state-based CvRDT): join이 격자의 LUB라는 성질이 버전 벡터와 같다. 병합이 교환·결합·멱등이면 자동 수렴하므로 sibling 수동 병합을 없앨 수 있다.
• Dotted Version Vector: Riak이 버전 벡터의 false concurrency(같은 복제본의 연속 쓰기가 sibling으로 갈라지는 문제)를 dot으로 고친 개선판.

참고 자료

• DDIA (Kleppmann) Ch.5 — "Detecting Concurrent Writes", version vectors
• Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (CACM 1978)
• Dynamo 논문 (DeCandia et al., SOSP 2007) §4.4 — vector clock as context, truncation
• Riak Docs — Vector Clocks / Dotted Version Vectors