CRDT: 충돌 없는 복제 데이터 타입

여러 복제본이 서로 묻지 않고 따로 고쳐도, 같은 변경 집합을 받은 노드는 같은 상태로 수렴합니다. 충돌을 사후에 푸는 대신 충돌이 생길 수 없게 데이터 타입을 설계하는 방식입니다.

충돌을 푸는 대신 없애는 발상

분산 시스템에서 복제(replication)는 가용성과 응답 속도를 위해 거의 필수입니다. 그런데 여러 노드가 동시에 같은 데이터를 고치면 충돌(conflict)이 생깁니다. 어느 변경을 살리고 어느 변경을 버릴지 정해야 하는 문제입니다.

전통적 해법은 두 갈래였습니다. 하나는 쓰기마다 다수결 합의를 거치는 강한 일관성이고, 다른 하나는 타임스탬프로 최신 값만 남기는 마지막 쓰기 우선(Last-Write-Wins, LWW)입니다. 둘 다 대가가 분명합니다.

충돌 없는 복제 데이터 타입(Conflict-free Replicated Data Type, CRDT)은 세 번째 길을 택합니다. 충돌을 사후에 해결하는 대신, 충돌이 발생할 수 없도록 데이터 타입 자체를 설계합니다. 합의도 잠금도 없이 복제본이 각자 변경한 뒤 나중에 병합해도 결과가 한 점으로 모입니다.

수렴을 보장하는 대수 구조

CRDT의 핵심은 병합(merge) 함수에 세 가지 대수 성질을 강제하는 것입니다. 교환법칙(commutativity), 결합법칙(associativity), 멱등성(idempotency)입니다. 이 셋이 성립하면 병합 순서가 달라도, 같은 메시지가 중복 도착해도 최종 상태가 같아집니다.

세 성질이 왜 필요한지는 네트워크의 결함과 짝을 이룹니다. 메시지는 순서가 뒤바뀌어 도착할 수 있으니 교환·결합법칙이 순서 의존을 없애 줍니다. 메시지는 재전송으로 중복될 수 있으니 멱등성이 같은 변경을 두 번 반영해도 안전하게 만듭니다.

이 성질을 만족하는 상태 공간을 수학에서는 조인 반격자(join-semilattice)라고 부릅니다. 두 상태를 병합한 결과가 둘의 최소 상계(least upper bound, LUB), 즉 두 상태를 모두 포함하는 가장 작은 상태가 되는 구조입니다. 병합이 항상 LUB로 정의되면 복제본들은 단조롭게 위로만 올라가다 한 점에서 만납니다.

이렇게 얻는 보장을 강한 최종 일관성(Strong Eventual Consistency, SEC)이라고 합니다. 같은 업데이트 집합을 받은 두 복제본은 추가 조정 없이 즉시 같은 상태가 됩니다. Shapiro 등의 2011년 INRIA 보고서(RR-7506)가 이 수렴 조건과 증명을 정리했습니다.

위 그림은 두 복제본이 따로 카운터를 올린 뒤 서로의 상태를 교환하는 과정입니다. 병합이 칸별 최댓값(LUB)이라, 어느 쪽이 먼저 보내든 두 복제본은 같은 상태로 수렴합니다.

상태 기반과 연산 기반

CRDT를 복제본 사이에서 동기화하는 방식은 크게 둘로 나뉩니다. 무엇을 네트워크로 보내느냐가 갈림길입니다. 전체 상태를 보내는 상태 기반과 변경 연산만 보내는 연산 기반입니다.

상태 기반은 수렴 복제 데이터 타입(Convergent Replicated Data Type, CvRDT)이라고 부릅니다. 복제본이 주기적으로 자기 상태 전체를 교환하고 받은 상태를 병합합니다. 병합이 LUB라서 메시지가 중복되거나 순서가 뒤집혀도 안전하지만, 매번 전체 상태를 보내니 대역폭이 비쌉니다.

연산 기반은 교환 복제 데이터 타입(Commutative Replicated Data Type, CmRDT)입니다. 복제본은 상태를 바꾸는 연산만 브로드캐스트합니다. 전송량은 작지만, 네트워크가 인과 순서 전달(causal delivery)을 보장해야 하고 동시 연산들이 서로 교환 가능해야 합니다.

상태 기반의 대표 예가 증가만 되는 카운터인 G-Counter(Grow-only Counter)입니다. 노드별 칸을 둔 벡터로 상태를 잡고, 자기 칸만 1씩 올립니다. 병합은 각 칸의 최댓값을 취하는 연산입니다.

def increment(state, node):
    state[node] = state.get(node, 0) + 1
 
def value(state):
    return sum(state.values())
 
def merge(a, b):
    keys = set(a) | set(b)
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in keys}

이 코드를 실제로 돌려 보면 수렴이 눈에 보입니다. 복제본 A가 자기 칸을 3까지 올리고 B가 자기 칸을 1로 올린 뒤, 순서를 바꿔 병합하거나 같은 상태를 중복 병합해도 결과는 {A: 3, B: 1}, 값 4로 같습니다. 각 칸의 max가 LUB이기 때문에 교환·결합·멱등이 한꺼번에 성립합니다.

증가와 감소를 모두 지원하려면 PN-Counter(Positive-Negative Counter)를 씁니다. 더하기용 카운터와 빼기용 카운터를 각각 G-Counter로 두고, 값은 두 합의 차로 읽습니다. 감소를 따로 모아 두기 때문에 빼기도 순서와 무관하게 수렴합니다.

델타 상태 CRDT

상태 기반의 약점은 매번 전체 상태를 보낸다는 점입니다. 카운터 한 칸만 바뀌어도 벡터 전체를 전송하면 낭비가 큽니다. 델타 상태 CRDT(delta-state CRDT, δ-CRDT)는 변경된 최소 조각인 델타만 보내 이 비용을 줄입니다.

동작 원리는 세 단계로 나뉩니다. 상태를 바꾸는 연산은 바뀐 부분만 담은 델타를 함께 반환합니다. 이 델타를 버퍼에 모아 상대 노드에 보내고, 받는 쪽은 기존 병합과 같은 join으로 합칩니다.

def delta_increment(state, node):
    state[node] = state.get(node, 0) + 1
    return {node: state[node]}   # 바뀐 칸만 델타로 반환
 
def join(state, delta):
    keys = set(state) | set(delta)
    return {k: max(state.get(k, 0), delta.get(k, 0)) for k in keys}

델타도 결국 같은 LUB 병합으로 합쳐지므로, 델타가 중복 도착하거나 순서가 바뀌어도 안전합니다. 그래서 수신 확인이 안 되면 델타만 다시 보내면 되고, 별도의 신뢰성 보장 계층이 없어도 됩니다. Akka Distributed Data와 IPFS가 δ-CRDT 방식을 채택한 사례입니다.

주요 CRDT 타입

카운터 말고도 집합·레지스터·시퀀스 등 여러 타입이 있습니다. 각각 어떤 연산을 지원하고 어떻게 수렴하는지로 구분합니다. 자주 쓰이는 타입을 정리하면 다음과 같습니다.

집합 타입에서 까다로운 부분은 삭제입니다. 단순히 집합 빼기로 지우면, 한 노드가 원소를 지우는 동안 다른 노드가 같은 원소를 다시 추가할 때 결과가 어긋납니다. 관찰 삭제 집합(Observed-Remove Set, OR-Set)은 이 문제를 dot으로 풉니다.

dot은 노드 식별자와 단조 증가 시퀀스로 만든 고유 태그입니다. add는 새 dot을 부여하고, remove는 자신이 본 dot만 지웁니다. 그래서 삭제와 동시에 새로 추가된 원소는 새 dot을 달고 있어 살아남습니다. 동시 add/remove에서 추가가 이기는 이 규칙을 add-wins라고 합니다.

동기화 비용과 한계

CRDT의 대가는 메모리와 메타데이터입니다. OR-Set은 원소마다 dot을 들고 다니고, 삭제된 원소의 흔적(tombstone)도 가비지 컬렉션 전까지 남습니다. 삭제가 잦은 워크로드에서는 메타데이터가 데이터보다 커질 수 있습니다.

전송량도 부담입니다. 상태 기반은 전체 상태를 주고받아 대역폭을 많이 쓰는데, δ-CRDT가 줄여 줘도 한계가 있습니다. 최근 연구인 ConflictSync(arXiv:2505.01144, 2025-05)는 상태를 다이제스트로 분해해 집합 재조정 문제로 바꿉니다. 이 방식으로 전체 상태 동기화 대비 데이터 전송량을 최대 18배 줄였다고 보고합니다.

다만 이 절감은 조건부입니다. 같은 논문은 두 복제본 상태의 유사도가 93%를 넘으면 블룸 필터 전처리가 오히려 손해여서, 전처리를 생략하는 편이 낫다고 밝힙니다. 유사도 구간에 따라 전처리 여부를 골라야 하는 문제입니다.

가장 본질적인 한계는 의미론입니다. CRDT는 '어떻게 병합하는가'를 정의할 뿐 '그 병합이 사용자 의도에 맞는가'는 보장하지 않습니다. LWW-Register는 두 사람이 동시에 같은 이름을 고치면 한쪽을 조용히 버리는데, 수렴은 했지만 사용자가 원한 결과는 아닐 수 있습니다.

어디에 쓰고 어디에 피하나

실제 서비스는 의미론이 단순한 곳에 CRDT를 씁니다. Riak은 OR-Set과 PN-Counter를 데이터베이스 내장 데이터 타입으로 제공합니다. Redis Enterprise의 액티브-액티브 구성은 CRDT로 멀티 마스터 복제를 처리합니다. 실시간 협업 편집에 쓰이는 CRDT 라이브러리 Automerge는 시퀀스 타입인 RGA 계열로 텍스트를 동기화합니다.

반대로 CRDT를 피해야 하는 자리도 분명합니다. 은행 잔고나 재고 차감처럼 '이 값 아래로 내려가면 안 된다'는 불변식이 있는 경우입니다. 두 사용자가 동시에 마지막 한 개를 사면 PN-Counter는 음수까지 허용하므로, 이런 곳은 분산 잠금이나 Raft 같은 강한 일관성이 맞습니다.

협업 편집에서도 선택지가 갈립니다. 사용자 의도 보존이 핵심이면 연산을 변환하는 연산 변환(Operational Transformation, OT)이 강점을 갖습니다. Google Docs는 중앙 서버 기반 실시간 편집에 OT를 씁니다. CRDT는 데이터 구조 자체가 수렴을 보장해 P2P나 서버리스 환경에 유리한 대신, 삽입 순서 표현이 까다롭고 메모리 비용이 큽니다.

판단 기준은 결국 불변식의 유무입니다. 비즈니스 로직에 '더하면 안 되는 조건'이 있으면 강한 일관성을, 순수한 집계나 집합이면 CRDT를 택합니다.

정리

CRDT는 충돌을 사후에 푸는 대신, 병합 함수에 교환·결합·멱등을 강제해 충돌이 생길 수 없게 만드는 데이터 타입입니다. 이 구조 덕에 복제본은 조정 없이 각자 변경하고도 같은 상태로 수렴하는 강한 최종 일관성을 얻습니다. 동기화는 전체 상태를 보내는 상태 기반, 연산만 보내는 연산 기반, 변경분만 보내는 델타 기반으로 나뉘며 대역폭과 네트워크 요구가 서로 다릅니다. 대가는 tombstone과 인과 컨텍스트 같은 메타데이터 오버헤드, 그리고 수렴이 사용자 의도와 다를 수 있는 의미론적 한계입니다. 따라서 카운터·집합·협업 편집처럼 의미론이 단순한 자리에 쓰고, 불변식이 걸린 거래에는 강한 일관성을 남겨 두는 것이 안전한 기준입니다.