CRDT

도입

CRDT는 분산 복제본이 서로 독립적으로 수정된 뒤에도 최종적으로 같은 상태로 수렴하도록, 자료형 자체에 병합 규칙과 동시성 의미를 내장한 모델이다.

분산 시스템에서 가장 까다로운 문제 중 하나는 여러 복제본이 동시에 같은 데이터를 수정할 때 무엇을 정답으로 볼 것인지입니다. 중앙 서버가 모든 변경을 순서대로 정해 주면 단순해 보이지만, 오프라인 작업이나 지연이 큰 네트워크, 피어 투 피어 구조에서는 이 방식이 금방 병목이 됩니다.

CRDT는 이 문제를 자료형 수준에서 다룹니다. 즉 충돌이 난 뒤에 애플리케이션 코드가 임시 merge 함수를 쓰는 것이 아니라, 카운터는 어떻게 합칠지, 집합은 add와 remove가 동시에 일어나면 무엇을 우선할지, 리스트나 트리는 동시 편집을 어떻게 해석할지를 자료형의 의미로 미리 정합니다.

그래서 CRDT를 이해한다는 것은 단순히 “충돌 없이 병합된다”는 슬로건을 아는 것이 아니라, 분산 복제와 동시성 의미를 데이터 모델 안으로 끌어들이는 관점을 이해하는 일에 가깝습니다.

필요성

네트워크 지연과 단절을 견디면서도 로컬에서 즉시 쓰기 가능한 시스템을 만들려면, 충돌 해결을 뒤늦게 붙이는 것보다 애초에 병합 가능한 자료형을 선택하는 편이 훨씬 안정적이다

CRDT가 자주 거론되는 이유는 단순히 이론적으로 예쁘기 때문이 아닙니다. 사용자는 문서를 편집할 때 네트워크 왕복을 기다리고 싶지 않고, 여러 디바이스에서 같은 데이터를 다룰 때도 오프라인 작업이 깨지지 않기를 기대합니다.

이때 CRDT는 로컬에서 먼저 변경을 수용하고, 나중에 다른 복제본과 비동기적으로 동기화하더라도 수렴하도록 설계할 수 있게 해 줍니다. 그래서 협업 편집기, 멀티 디바이스 동기화, local-first 소프트웨어, 일부 약한 일관성 저장소에서 CRDT가 자주 등장합니다.

핵심은 “충돌을 없앤다”보다 “동시 수정의 의미를 자료형 차원에서 통제한다”는 데 있습니다. 이 차이를 이해해야 CRDT가 왜 어떤 시스템에는 잘 맞고 어떤 시스템에는 과한 선택인지 판단할 수 있습니다.

CRDT가 특히 강한 지점

• 오프라인 상태에서도 로컬 업데이트를 먼저 수용해야 하는 경우
• 여러 복제본이 중앙 조정자 없이 비동기적으로 동기화되는 경우
• 협업 편집처럼 동시 수정이 자주 발생하는 경우
• local-first 소프트웨어처럼 사용자 디바이스의 로컬 사본을 1차 권위로 두고 싶은 경우

정의

CRDT는 Conflict-Free Replicated Data Type의 약자이며, 복제본이 같은 업데이트 집합을 받았을 때 순서가 달라도 결국 동일한 상태로 수렴하도록 설계된 복제 자료형이다

초기 CRDT 논문은 eventual consistency를 ad-hoc merge 로 처리하지 말고, 수렴을 보장하는 수학적 조건을 만족하는 자료형으로 설계하자고 제안했습니다. 이후 후속 서베이는 이 개념을 더 정리하면서, CRDT를 여러 프로세스에 복제되도록 설계된 추상 자료형으로 설명합니다.

여기서 중요한 점은 conflict-free가 “동시 수정이 아예 사라진다”는 뜻이 아니라는 것입니다. 실제로는 동시 수정이 일어났을 때 어떤 결과를 정답으로 볼지 자료형이 미리 의미를 갖습니다. 예를 들어 add-wins set과 remove-wins set은 같은 집합처럼 보여도 동시 add/remove를 다르게 해석합니다.

즉 CRDT는 충돌을 마술처럼 없애는 도구가 아니라, 충돌을 해석하는 정책을 자료형 안에 명시적으로 넣는 방식이라고 보는 편이 더 정확합니다.

핵심 메시지

"CRDT의 본질은 충돌을 숨기는 데 있지 않고

동시 수정의 의미를 자료형 차원에서 결정해 수렴을 보장하는 데 있습니다."

핵심 원리

핵심은 동시 수정 이후에 임시로 merge 코드를 짜는 것이 아니라, 같은 업데이트 집합을 받으면 같은 상태로 가도록 수렴 조건과 병합 연산을 자료형 안에 설계하는 데 있다

Strong Eventual Consistency 관점에서 보면, 두 복제본이 같은 업데이트 집합을 받았을 때 순서가 달라도 같은 상태가 되어야 합니다. CRDT는 이 수렴을 보장하기 위해 상태 기반이라면 세미라티스와 join merge를, 연산 기반이라면 동시 연산의 가환성을 이용합니다.

이 때문에 CRDT는 단순한 저장 형식이 아니라 동시성 의미를 포함한 자료형입니다. 카운터는 증가/감소가 어떻게 합쳐질지, 멀티밸류 레지스터는 동시 write를 어떻게 보여줄지, 리스트나 텍스트는 삽입 순서를 어떻게 유지할지까지 포함합니다.

또 중요한 점은 수렴과 직관적 UX가 항상 같은 말이 아니라는 것입니다. 어떤 CRDT는 수렴은 보장하지만, 그 상태가 사람이 기대하는 편집 결과와 다를 수 있습니다. 즉 convergence는 필요조건이지 항상 충분조건은 아닙니다.

결국 CRDT 설계의 진짜 난점은 “병합이 되느냐”보다 “그 병합 의미가 애플리케이션에 맞느냐”에 있습니다.

CRDT Thinking
1) 복제본은 로컬에서 먼저 업데이트를 수용한다
2) 업데이트 또는 상태를 나중에 다른 복제본에 전파한다
3) 자료형이 정의한 규칙으로 병합한다
4) 같은 업데이트 집합을 받으면 순서가 달라도 같은 상태로 수렴한다
5) 단, 수렴 자체와 사용자 의도 보존은 별개의 문제일 수 있다

분류

실무에서 CRDT를 볼 때는 state-based, operation-based, 그리고 둘의 절충인 delta-state 세 가지 축을 먼저 구분하는 편이 가장 이해하기 쉽다

분류	핵심 아이디어	전파 단위	채널 요구사항	실무 해석
State-based CRDT (CvRDT)	상태가 join-semilattice를 이루고 merge가 LUB를 계산	전체 상태 또는 상태 조각	메시지 손실/중복/순서 뒤바뀜에 비교적 강함	개념적으로 이해하기 쉽지만 상태가 커지면 전송 비용이 커질 수 있음
Operation-based CRDT (CmRDT)	동시 연산이 가환되도록 설계	연산(effectors)	신뢰 가능한 전달, 보통 causal delivery 가정	메시지가 더 작을 수 있지만 전파 계층 가정이 더 강함
Delta-state CRDT (δ-CRDT)	상태 기반 장점은 유지하면서 전체 상태 대신 delta만 전송	delta-state	상태 기반 스타일의 채널 위에서 동작 가능	큰 상태 전송 비용을 줄이기 위한 절충안으로 자주 언급됨

이 세 분류는 우열 관계가 아니라 설계 선택지입니다. 상태 기반은 merge 성질이 강하고 채널 가정이 약한 편이고, 연산 기반은 메시지를 더 작게 만들 수 있지만 전달 계층에 더 많은 보장을 기대합니다. delta-state는 이 둘 사이에서 상태 기반의 합성 가능성과 작은 메시지를 함께 노리는 방향입니다.

기본 구조

CRDT는 하나의 알고리즘 이름이 아니라, 카운터·레지스터·집합·맵·시퀀스·JSON 같은 여러 자료형 계열로 이루어진 설계 패밀리에 가깝다

자료형 계열	대표 예시	실무 해석
Register	LWW Register, Multi-Value Register	값 하나를 저장하지만 동시 write 의미를 어떻게 정의할지가 중요
Counter	G-Counter, PN-Counter, Bounded Counter	증가/감소·수량·quota 같은 문제에 자주 쓰임
Set	G-Set, 2P-Set, OR-Set, Add-Wins / Remove-Wins Set	동시 add/remove 의미를 명시적으로 선택해야 함
Map	Observed-Remove Map 등	필드별로 다른 CRDT를 중첩하는 기반이 됨
Sequence / List / Text	RGA, Treedoc, Logoot 계열	협업 편집에서 중요하지만 의미 보존이 특히 어려운 축
JSON / Tree	JSON CRDT, tree CRDT	맵과 리스트를 중첩해 더 현실적인 앱 상태를 표현

즉 CRDT를 도입한다는 말은 “하나의 만능 병합 엔진”을 가져온다는 뜻이 아니라, 데이터 항목별로 어떤 동시성 의미가 맞는지 선택하는 작업에 더 가깝습니다. 숫자는 counter로, 선택 상태는 set으로, 문서 구조는 sequence나 JSON CRDT로 나누어 보는 식입니다.

기본 구현

가장 이해하기 쉬운 시작점은 state-based G-Counter 로, 각 복제본의 로컬 증가분을 따로 기록하고 merge 시 항목별 최대값을 취하는 구조다

data class GCounter(
    val counts: MutableMap<String, Int> = mutableMapOf()
) {
    fun increment(replicaId: String) {
        counts[replicaId] = counts.getOrDefault(replicaId, 0) + 1
    }

    fun merge(other: GCounter): GCounter {
        val merged = mutableMapOf<String, Int>()
        val ids = counts.keys + other.counts.keys

        for (id in ids) {
            merged[id] = maxOf(
                counts.getOrDefault(id, 0),
                other.counts.getOrDefault(id, 0)
            )
        }
        return GCounter(merged)
    }

    fun value(): Int = counts.values.sum()
}

이 구조는 왜 state-based CRDT가 semilattice와 join merge를 말하는지 직관적으로 보여 줍니다. 각 복제본은 자기 슬롯만 증가시키고, 병합은 각 슬롯의 최대값을 취하기 때문에 중복 전파나 순서 뒤바뀜이 있어도 최종 값이 뒤틀리지 않습니다.

실전 포인트

카운터는 CRDT를 설명할 때 가장 단순한 예시지만, 실무에서는 집합·맵·리스트·트리처럼 더 복잡한 자료형이 문제의 핵심입니다. 특히 문서 편집으로 갈수록 수렴 자체보다 사용자 의도 보존과 메타데이터 비용이 훨씬 더 중요해집니다.

패턴 1. 협업 문서와 로컬 퍼스트

현대 CRDT가 가장 자주 쓰이는 곳은 협업 편집과 local-first 소프트웨어이며, Yjs 와 Automerge 는 이 방향의 대표적인 구현으로 자주 언급된다

Yjs는 공유 타입을 통해 문서 상태를 동시 조작하고 자동 병합하는 방향을 전면에 내세우고 있고, 네트워크 기술에 크게 구애받지 않는 데이터 모델로 소개됩니다. Automerge는 로컬 사본을 1차로 두고 오프라인 상태에서도 변경을 쌓아 두었다가 나중에 동기화하는 local-first 협업 소프트웨어에 초점을 둡니다.

즉 오늘날 CRDT는 단순한 분산 이론 예제가 아니라, Google Docs류 협업 문서, 멀티플레이어 앱 상태, 오프라인 우선 데이터 모델 같은 현실적인 UX 요구와 맞물려 사용됩니다.

대표 use case
- 협업 텍스트/리치 텍스트 편집
- 화이트보드, 캔버스, 드로잉
- 멀티 디바이스 노트/태스크 앱
- 로컬 퍼스트 앱 상태 동기화
- 중앙 서버가 없어도 동작해야 하는 공유 데이터

패턴 2. 멀티 디바이스 상태 동기화

사용자 한 명이 여러 디바이스에서 같은 상태를 오프라인과 온라인을 오가며 편집해야 할 때 CRDT는 중앙 조정 없이도 자연스러운 동기화 모델을 제공한다

CRDT를 꼭 다중 사용자 협업에만 써야 하는 것은 아닙니다. 노트 앱, 개인 지식 관리, 드로잉 앱처럼 한 사람이 노트북·태블릿·폰을 오가며 같은 상태를 편집하는 문제에도 잘 맞습니다.

이 경우에도 본질은 같습니다. 각 디바이스는 로컬에서 먼저 변경을 수용하고, 통신이 가능해지면 서로의 변경을 교환해 수렴합니다. 중앙 서버는 있을 수도 있지만, 병합 의미의 중심이 서버가 아니라 자료형에 있다는 점이 중요합니다.

패턴 3. 저장소와 백엔드 데이터 모델

CRDT는 라이브러리 안의 협업 상태 모델로만 쓰이지 않고, 약한 일관성 저장소와 런타임이 외부에 제공하는 데이터 모델로도 사용된다

2018년 서베이는 CRDT가 애플리케이션 내부 데이터 구조뿐 아니라 저장소 시스템의 데이터 모델로도 쓰였다고 정리합니다. 예시로 Riak, Redis, Akka 같은 시스템이 언급되고, 응용이 CRDT를 직접 저장하거나 내부 상태 유지에 활용하는 방식이 함께 소개됩니다.

즉 CRDT는 앱 단의 협업 편집 기술로만 한정되지 않습니다. 어떤 시스템은 CRDT를 라이브러리로 임베드하고, 어떤 시스템은 저장 계층 자체가 CRDT 연산을 노출하기도 합니다.

한계와 주의점

CRDT는 강력하지만 만능은 아니며, 전역 불변식·메타데이터 비용·텍스트 의미 보존처럼 별도의 난제를 함께 안고 간다

첫째, 모든 연산이 conflict-free로 표현되는 것은 아닙니다. 예를 들어 경매에서 입찰 수집은 약한 일관성 하에서도 가능할 수 있지만, 경매를 종료하고 단 하나의 우승자를 확정하는 일은 전역 합의가 필요할 수 있습니다. 즉 CRDT는 coordination을 줄여 주지만, 시스템 전체에서 coordination을 완전히 없애 주지는 않습니다.

둘째, 메타데이터와 가비지 컬렉션 비용이 현실적인 문제입니다. CRDT 구현은 인과성과 동시성을 추적하기 위해 추가 메타데이터를 저장하는 경우가 많고, 이 비용은 복제본 수나 문서 규모가 커질수록 부담이 됩니다. 일부 설계는 tombstone 제거 같은 GC 없이는 구조가 계속 커질 수 있습니다.

셋째, 수렴만으로는 충분하지 않습니다. 텍스트와 리치 텍스트 편집에서는 단순히 같은 상태로 모이는 것보다 사용자 의도 보존이 훨씬 더 어렵습니다. 실제로 동시 삽입 텍스트가 글자 단위로 뒤섞이는 interleaving anomaly나, 단순한 plaintext CRDT를 리치 텍스트로 확장했을 때 발생하는 편집 이상 사례가 문헌에 보고돼 있습니다.

주의해야 할 지점

• CRDT는 coordination 을 줄여 주지만 모든 전역 합의를 없애 주지는 않음
• 추가 메타데이터와 인과성 추적 비용이 커질 수 있음
• 일부 구조는 tombstone 제거나 compaction 없이는 계속 비대해질 수 있음
• 수렴이 보장돼도 사용자가 기대하는 의미 보존까지 자동으로 해결되는 것은 아님

자주 하는 실수

CRDT를 어렵게 만드는 가장 흔한 원인은 알고리즘 그 자체보다, 수렴 보장과 애플리케이션 의미를 같은 것으로 생각하는 데 있다

• CRDT = 충돌이 완전히 사라진다고 생각함
• CRDT = 서버가 필요 없다고 오해함
• CRDT = 어떤 자료형에도 그대로 적용 가능하다고 생각함
• 수렴만 보장되면 UX도 자연스럽다고 가정함
• 카운터 수준의 단순 예시만 보고 텍스트/트리 문제도 같은 난이도로 봄
• 메타데이터와 GC 비용을 나중 문제로 미룸

실무 루틴

CRDT를 도입할 때는 먼저 데이터 항목별 동시성 의미를 정하고, 그다음 복제 방식과 메타데이터 비용, 드물게 필요한 coordination 지점을 분리해서 설계하는 편이 안전하다

1. 먼저 어떤 데이터가 counter, set, register, list, tree 인지 구분한다.
2. 동시 수정이 일어났을 때 무엇을 정답으로 볼지 자료형 의미를 먼저 정한다.
3. 전송 계층 가정에 맞춰 state-based, op-based, delta-state 중 무엇이 맞는지 고른다.
4. 메타데이터, tombstone, compaction 비용을 초기에 함께 측정한다.
5. 드물지만 반드시 하나로 결정돼야 하는 작업은 별도 coordination 경로로 분리한다.
6. 수렴 테스트와 함께 사용자 의도 보존 테스트도 별도로 만든다.

디버깅

CRDT 문제를 디버깅할 때는 단순히 merge 결과만 보지 말고, 수렴 실패인지 의미 설계 실패인지 전달 가정 위반인지부터 먼저 분리해야 한다

1

먼저 각 복제본이 정말 같은 업데이트 집합을 받았는지 확인한다.

2

op-based 라면 전달 보장과 causal order 가정이 깨진 것은 아닌지 본다.

3

수렴은 되는데 이상하면 자료형의 동시성 의미가 애플리케이션에 맞는지 다시 본다.

4

문서/텍스트 문제라면 단순 convergence 가 아니라 interleaving 과 intent preservation 관점으로 본다.

5

메타데이터, tombstone, sync 로그가 비대해지는지 운영 지표를 함께 본다.

점검 체크리스트
- 같은 업데이트 집합을 정말 모두 받았는가
- state-based / op-based 가정이 맞는가
- causal delivery 또는 anti-entropy 경로가 깨지지 않았는가
- 문제의 본질이 convergence 인가, semantics 인가
- tombstone / metadata / sync 비용이 병목인가
- 드물게 필요한 global agreement 를 따로 분리했는가

요약

CRDT의 핵심은 충돌을 나중에 수습하는 것이 아니라, 자료형 자체에 병합 의미와 수렴 조건을 넣어 오프라인·비동기·다중 복제 환경에서도 같은 상태로 모이게 만드는 데 있다

• ✅ CRDT는 복제본이 독립적으로 갱신돼도 수렴하도록 설계된 복제 자료형이다.
• ✅ 핵심은 동시 수정의 의미를 자료형 안에 넣는 것이다.
• ✅ 크게 state-based, operation-based, delta-state 로 구분해 볼 수 있다.
• ✅ 카운터, 집합, 맵, 리스트, 텍스트, JSON, 트리 등 다양한 계열이 존재한다.
• ✅ 협업 편집, local-first, 멀티 디바이스 오프라인 동기화에서 특히 자주 쓰인다.
• ✅ CRDT는 coordination 을 줄여 주지만 모든 전역 합의를 없애지는 못한다.
• ✅ 메타데이터, tombstone, GC, replica 수 증가에 따른 비용을 반드시 고려해야 한다.
• ✅ convergence 와 사용자 의도 보존은 별개의 문제이므로 함께 설계해야 한다.

 

RELATED POST

OT 와 CRDT 는 무엇이 다를까
Eventual Consistency 와 Strong Eventual Consistency 차이
Local-First Software 는 왜 CRDT 와 함께 언급될까

 

REFERENCE

Conflict-free Replicated Data Types (Shapiro et al., 2011)
Conflict-free Replicated Data Types (Preguiça et al., 2018)
Delta State Replicated Data Types
A Conflict-Free Replicated JSON Datatype
Verifying Strong Eventual Consistency in Distributed Systems
Yjs Docs
Welcome to Automerge
Local-First Software
Interleaving anomalies in collaborative text editors
Peritext: A CRDT for Collaborative Rich Text Editing