버전 벡터 (Version Vector)

1. 배경: 리더가 없는 복제

리더 기반 복제는 순서가 하나이므로 충돌이라는 개념 자체가 없다. 대신 대가가 있다. 리더가
죽으면 선출까지 쓰기가 멈추고, 지리적으로 분산된 환경에서는 모든 쓰기가 리더까지 왕복해야
한다.

그래서 반대편 설계가 있다. 아무 레플리카나 쓰기를 받는다(leaderless / multi-master).
Amazon Dynamo 논문이 대표이고 Riak, Cassandra, DynamoDB가 이 계열이다. 가용성은
극대화되지만 새로운 문제가 생긴다. 같은 데이터가 서로 다른 노드에서 동시에 갱신되면,
누가 최신인지 어떻게 아는가?

타임스탬프(LWW)로는 왜 안 되는가

"타임스탬프 붙여서 늦은 쪽이 이긴다"(Last-Write-Wins)는 두 가지 문제가 있다. 첫째, 서버들의
물리 시계는 완벽히 동기화되지 않는다(clock skew). 시계가 빠른 노드의 쓰기가 항상 이기는
왜곡이 생긴다. 둘째, 더 근본적으로 — LWW는 충돌을 감지하는 게 아니라 은폐한다. 두
클라이언트가 동시에 다른 값을 썼다면 병합이 필요한 사건인데, LWW는 한쪽을 조용히 버린다.
데이터 유실이 정책으로 내장된 셈이다.

필요한 것은 "더 최신이다"와 "동시였다(concurrent)"를 구분하는 능력이다. 단일 버전
번호로는 안 된다. 노드 A에서 v2가 되고 노드 B에서도 v2가 되면, 같은 v2라도 전혀 다른
값인데 구분할 방법이 없다.

2. 버전 벡터: 노드별로 카운터를 분리한다

해법은 버전을 숫자 하나가 아니라 노드별 카운터의 맵으로 관리하는 것이다.

{A: 2, B: 1}   ← "노드 A가 2번, 노드 B가 1번 갱신에 관여한 버전"

규칙은 단순하다. 노드가 쓰기를 처리할 때 자기 카운터만 1 올린다. 값이 레플리카 간에
전파될 때 버전 벡터도 함께 다닌다.

비교 규칙

두 버전 벡터 V1, V2에 대해:

• 모든 성분에서 V1 ≤ V2이면 → V2가 V1의 후손이다. V2는 V1을 "본 뒤에" 만들어진
  갱신이므로 V1을 V2로 덮어써도 안전하다.
• 서로 어느 쪽도 전부 크지 않으면 — 예컨대 {A:2, B:1}과 {A:1, B:2} —
  동시(concurrent)다. 서로가 서로를 모른 채 만들어진 갱신이며, 이것이 감지된 충돌이다.

data class VersionVector(val versions: Map<String, Long>) {
    fun increment(nodeId: String) =
        VersionVector(versions + (nodeId to (versions[nodeId] ?: 0) + 1))

    fun descendsFrom(other: VersionVector): Boolean =
        other.versions.all { (node, v) -> (versions[node] ?: 0) >= v }

    fun isConcurrentWith(other: VersionVector): Boolean =
        !descendsFrom(other) && !other.descendsFrom(this)
}

시나리오

장바구니 데이터가 {A:1} 버전으로 두 레플리카에 있는 상태에서 네트워크가 분단된다.

초기: cart = [빵], VV = {A:1}          (A, B 양쪽에 복제된 상태)

분단 중:
  클라이언트1 → 노드 A: 우유 추가 → cart = [빵, 우유], VV = {A:2}
  클라이언트2 → 노드 B: 계란 추가 → cart = [빵, 계란], VV = {A:1, B:1}

분단 복구, 동기화:
  {A:2} vs {A:1, B:1} → 어느 쪽도 후손이 아님 → 동시! 충돌 감지

분단이 없었고 클라이언트2가 {A:2}를 읽은 뒤 썼다면 결과는 {A:2, B:1}이 되고, 이것은
{A:2}의 후손이므로 조용히 덮어쓴다. 인과 관계가 있으면 자동 병합, 없으면 충돌 보고 —
이것이 버전 벡터가 하는 일의 전부다.

연습: 세 벡터의 관계

V1 = {A:2, B:1}, V2 = {A:2, B:2}, V3 = {A:3, B:0}일 때:

• V1 vs V2: 모든 성분에서 V1 ≤ V2 → V2가 V1의 후손
• V2 vs V3: A는 V3가 크고 B는 V2가 크다 → 동시(충돌)
• V1 vs V3: 마찬가지로 동시(충돌)

V3는 A 성분이 가장 크지만 B의 갱신을 본 적이 없다. "총합이 크다"거나 "한 성분이 앞선다"로는
아무것도 결정되지 않는다. 비교는 언제나 성분 전체로 한다.

3. "자기 카운터만 올린다"는 규칙이 왜 중요한가

이 규칙을 어기면 무엇이 깨지는지 시나리오로 보자.

초기: VV = {A:1}, 양쪽에 복제됨

분단 중:
  노드 A가 쓰기 처리 → 자기 카운터 올림 → {A:2}, 값 = X
  노드 B가 쓰기 처리 → 규칙 위반, A의 카운터를 올림 → {A:2}, 값 = Y

분단이 복구되면 {A:2} vs {A:2} — 서로 다른 두 값이 동일한 버전 벡터를 갖는다. 비교
결과는 "같음"이므로 충돌이 감지되지 않고, 동기화 과정에서 한쪽이 조용히 덮어써진다.
충돌이어야 할 것이 인과 관계로 위장되는 것(false merge / lost update)이다.

규칙의 본질은 이것이다. 각 슬롯의 주인이 유일한 증가자여야, 벡터가 "이 버전이 각 출처의
갱신을 몇 개까지 반영했는가"의 정직한 기록이 된다. 버전 벡터의 부분 순서(partial order)가
실제 사건의 happened-before 관계와 일치한다는 보장은 이 "단독 소유권" 전제 위에서만
성립한다.

4. 충돌을 감지한 다음 — 해소의 실제 흐름

버전 벡터는 충돌을 감지할 뿐 해결하지는 않는다. 해소는 별도의 사이클이 담당한다.
Dynamo/Riak 스타일의 흐름을 처음부터 끝까지 따라가 보자.

장바구니 cart = [빵], 버전 {C0:1}이 저장돼 있고, 클라이언트 C1과 C2가 둘 다 이 상태를
읽은 뒤 동시에 갱신한다(행위자를 클라이언트 ID로 두는 방식).

C1: [빵] 읽음(VV {C0:1}) → 우유 추가해서 쓰기 → {C0:1, C1:1}, 값 [빵, 우유]
C2: [빵] 읽음(VV {C0:1}) → 계란 추가해서 쓰기 → {C0:1, C2:1}, 값 [빵, 계란]

어느 쪽도 후손이 아니므로 동시다. 서버는 이 시점에 어느 쪽도 버리지 않고 둘 다
형제(siblings)로 보관한다. 해소는 다음 읽기 때 일어난다.

어떤 클라이언트가 읽기 요청
  ← 서버 응답: 값 [빵,우유] 그리고 [빵,계란] (형제 둘 다)
              + 인과 컨텍스트: {C0:1, C1:1, C2:1}   ← 두 벡터의 상한(supremum)

클라이언트: 애플리케이션 로직으로 병합 → [빵, 우유, 계란]
클라이언트: 병합 결과를 받은 컨텍스트와 함께 다시 쓰기
  → 새 버전: {C0:1, C1:1, C2:1, C3:1}

마지막 쓰기의 벡터는 두 형제 모두의 후손이므로, 서버는 형제 둘을 지우고 하나로
수렴시킨다. 충돌은 "읽기 → 클라이언트 병합 → 컨텍스트를 실은 재쓰기" 사이클로 해소된다.

여기서 중요한 프로토콜 규칙이 보인다. 쓰기는 반드시 "내가 읽었던 버전의 인과 컨텍스트"를
실어 보내야 한다. 서버는 이 컨텍스트로 "이 쓰기가 무엇을 본 상태에서 만들어졌는가"를
판별한다. 낙관적 락의 버전 토큰과 정확히 같은 역할 — JPA의 @Version을 분산 환경으로
일반화한 것이라 봐도 좋다.

병합 정책의 세 층

병합 자체는 시스템이 못 해준다. [빵, 우유]와 [빵, 계란]을 어떻게 합칠지는 도메인
지식이기 때문이다.

애플리케이션 병합 — 클라이언트 코드가 도메인 규칙으로 합친다. 유연하지만 모든
클라이언트가 병합 코드를 가져야 하고, 단순 합집합 병합은 "삭제한 상품이 부활하는"
문제(합집합은 삭제를 표현할 수 없다)를 조심해야 한다. Amazon 장바구니의 유명한 일화가 바로
이 사례다.

CRDT — 병합이 수학적으로 항상 안전하도록 자료구조 쪽을 설계한다(아래 6장).

LWW 폴백 — 형제 관리가 복잡하니 타임스탬프 큰 쪽을 채택한다. 간단하지만 애써 감지한
충돌을 도로 버리는 것이므로 유실이 허용되는 데이터에만 쓴다. Cassandra가 기본값으로 이
방식을 택했다 — 단순함을 얻고 조용한 유실을 대가로 치른 것이다.

5. 행위자(actor)를 누구로 할 것인가 — 서버 ID vs 클라이언트 ID

카운터의 주인을 누구로 하느냐가 감지 정밀도를 좌우한다.

서버 노드 ID를 행위자로 하면 벡터가 노드 수만큼만 자라서 컴팩트하다. 하지만 같은 노드가
서로 다른 두 클라이언트의 쓰기를 연달아 처리하면 {A:1} → {A:2} → {A:3}처럼 일렬로 쌓여서,
실제로는 동시였던 갱신이 인과 관계처럼 보일 수 있다(충돌 미감지).

클라이언트 ID를 행위자로 하면 행위자가 다르면 벡터가 반드시 갈라지므로 감지가
정확해진다. 대신 키 하나의 벡터가 그 키를 건드린 모든 클라이언트 수만큼 자란다. 모바일
사용자 수백만이 행위자라면 벡터가 값보다 커진다. 오래된 항목을 잘라내면(pruning) 인과
정보가 유실되어 거짓 충돌이 늘어난다.

Riak은 결국 "서버 ID를 쓰되, 같은 노드가 처리한 서로 다른 쓰기를 점(dot)으로 구분한다"는
dotted version vector로 정착했다. 서버 ID의 컴팩트함과 클라이언트 ID의 정밀함을 동시에
잡는 절충이다.

용어 정리: 벡터 시계와의 구분

벡터 시계(vector clock) 와 자주 혼용되지만 엄밀히는 다르다. 벡터 시계는 프로세스 간
이벤트의 인과 관계를 추적하는 범용 도구이고, 버전 벡터는 데이터 객체의 버전 계보를
추적하는 특수화된 응용이다. 구조는 같지만 목적과 갱신 규칙이 다르다.

6. CRDT (Conflict-free Replicated Data Type)

이름 그대로 "충돌이 아예 발생하지 않도록 설계된 복제 자료구조" 다. 버전 벡터 세계에서
병합은 애플리케이션이 짜야 하는 골칫거리였다. CRDT는 발상을 뒤집는다. 병합 함수가
수학적으로 항상 안전하도록 자료구조 쪽을 설계하면, 충돌 해소라는 문제 자체가 소멸한다.

병합 함수 merge(a, b)가 세 가지 성질을 만족하면 된다.

• 교환법칙: merge(a, b) = merge(b, a) — 합치는 순서 무관
• 결합법칙: 셋 이상을 어떤 짝으로 묶어 합쳐도 동일
• 멱등성: merge(a, a) = a — 같은 것을 두 번 합쳐도 무해

이 셋이 성립하면 레플리카들이 어떤 순서로, 몇 번씩 중복해서 상태를 교환해도 결국 전부
같은 값으로 수렴한다. 네트워크가 지연시키든 중복 전달하든 상관없어진다. 프로토콜을 정교하게
만드는 대신, 데이터에 좋은 성질을 부여해서 프로토콜이 대충해도 되게 만드는 접근이다.

가장 간단한 예: G-Counter

전역 카운터 하나를 두면 동시 증가가 충돌하지만, 노드별 카운터의 맵으로 바꾸고 각 노드는
자기 슬롯만 올리게 한다. 값 = 전체 슬롯의 합, 병합 = 슬롯별 max.

data class GCounter(val counts: Map<String, Long>) {
    fun increment(nodeId: String) =
        GCounter(counts + (nodeId to (counts[nodeId] ?: 0) + 1))

    fun value() = counts.values.sum()

    fun merge(other: GCounter) = GCounter(
        (counts.keys + other.counts.keys).associateWith {
            maxOf(counts[it] ?: 0, other.counts[it] ?: 0)  // 슬롯별 max
        }
    )
}

어디서 본 구조인가 — 버전 벡터와 완전히 같은 뼈대다. "노드별 슬롯 + 자기 슬롯만 증가 +
성분별 비교/병합". 사실 버전 벡터 자체가 CRDT의 성질을 갖는 구조이고, 두 주제는 같은 수학
위에 서 있다.

표준 레퍼토리

여기서 층층이 쌓아 올린다. 감소도 필요하면 증가용/감소용 G-Counter 두 개를 붙인
PN-Counter, 추가만 되는 집합 G-Set, 삭제까지 필요하면 각 원소에 고유 태그를 붙여
"내가 본 태그만 삭제"하게 한 OR-Set(장바구니의 "삭제 부활" 문제를 이것으로 푼다), 단일
값이면 타임스탬프 큰 쪽을 취하는 LWW-Register 등이 표준이다.

실전 사례로는 Riak 내장 데이터 타입, Redis Enterprise의 액티브-액티브 복제, 그리고 협업
편집기(Yjs, Automerge — Figma/Notion류 도구들의 기반)가 있다. 협업 편집은 "오프라인에서
편집하고 나중에 동기화"가 본질이라 CRDT의 주 무대가 됐다.

한계

모든 도메인이 교환·결합·멱등 병합으로 표현되는 것은 아니다. "재고가 0 미만이 되면 안 된다"
같은 전역 불변식은 CRDT로 지킬 수 없다. 두 레플리카가 각자 마지막 재고를 팔면 병합
결과는 -1이다. 그런 요구사항은 결국 합의(복제 로그) 세계로 돌아가야 한다. 도구 선택의
기준이 여기서 갈린다.

7. 정리 — 두 세계의 지도

복제 로그와 버전 벡터는 같은 문제("여러 노드의 갱신을 정합성 있게")에 대한 두 극단의 답이다.

복제 로그는 순서를 하나로 강제해서 충돌을 원천 봉쇄한다(일관성 우선, CP 성향). 버전
벡터는 충돌을 허용하되 정확히 감지해서 나중에 병합한다(가용성 우선, AP 성향). 그리고
CRDT는 병합 자체를 수학으로 자동화해서, 충돌 허용 세계의 병합 비용을 없앤다.

어느 쪽이 옳은 것이 아니라 트레이드오프의 양 끝이고, 실제 시스템은 요구사항 — 유실을 얼마나
허용하는가, 전역 불변식이 있는가, 가용성이 얼마나 중요한가 — 에 따라 이 사이 어딘가에 선다.

참고 자료

• 『30가지 패턴으로 배우는 분산 시스템 설계와 구현 기법』 — 버전 벡터
• Martin Kleppmann, 『데이터 중심 애플리케이션 설계』 5장 (리더리스 복제, 동시 쓰기 감지)