💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

원문 렌더가 준비되기 전까지 텍스트 가이드로 표시합니다.

TL;DR

- **CRDT의 마법**: 여러 사용자가 동시에 다른 복제본을 수정해도 **자동으로 같은 상태로 수렴**. 락 없이, 중앙 서버 없이

- **두 가지 접근**: State-based(전체 상태 전송) vs Operation-based(연산 전송). 각각 장단점

- **로컬 우선 운동**: Ink & Switch 연구소가 시작. Figma, Linear, Notion이 채택

- **Yjs vs Automerge**: Yjs는 성능과 텍스트 협업, Automerge는 JSON 데이터 모델에 강함

- **언제 사용**: 협업 에디터, 오프라인 우선 앱, P2P 동기화, 분산 메모

1. CRDT란 무엇인가?

1.1 문제 — 분산 환경에서의 충돌

**시나리오**: 두 사용자가 동시에 같은 문서를 편집합니다.

초기: "Hello"

User A 추가: "Hello World"

User B 동시 추가: "Hello Friend"

병합 시 어떻게? 어떤 게 이기나?

전통적 해결책:

- **마지막 쓰기 승리(Last Write Wins)** — 한 사람의 변경이 사라짐

- **수동 병합** — 사용자가 직접 해결

- **락(Locking)** — 한 명만 편집 가능, 협업 불가능

**CRDT의 답**: 두 변경을 **자동으로 의미 있게 병합**. 둘 다 보존.

1.2 CRDT의 수학적 정의

CRDT는 **두 가지 속성**을 가진 데이터 타입입니다:

1. **결합법칙(Associativity)**: `(a + b) + c = a + (b + c)`

2. **교환법칙(Commutativity)**: `a + b = b + a`

3. **멱등성(Idempotence)**: `a + a = a`

이 세 가지를 만족하면, **어떤 순서로 병합해도 결과가 동일**합니다. 이를 ACI 속성 또는 **semilattice**라고 합니다.

1.3 두 가지 접근

State-based CRDT (CvRDT)

- 전체 상태를 전송

- 병합 함수: `merge(a, b) → c`

- 장점: 단순, 메시지 순서 무관

- 단점: 큰 상태 = 큰 네트워크 비용

Operation-based CRDT (CmRDT)

- 연산만 전송

- 모든 노드가 같은 연산을 같은 횟수 적용해야 함

- 장점: 작은 메시지

- 단점: 안정적인 메시지 전달 필요 (at-least-once)

**실용적 선택**: 대부분의 라이브러리(Yjs, Automerge)는 **하이브리드** 접근을 사용합니다.

2. 기본 CRDT 타입

2.1 G-Counter (Grow-only Counter)

증가만 가능한 카운터.

class GCounter:

def __init__(self, node_id):

self.node_id = node_id

self.counts = {} # {node_id: count}

def increment(self):

self.counts[self.node_id] = self.counts.get(self.node_id, 0) + 1

def value(self):

return sum(self.counts.values())

def merge(self, other):

각 노드의 카운트는 max로 병합

for node, count in other.counts.items():

self.counts[node] = max(self.counts.get(node, 0), count)

**왜 max?**: 같은 노드의 카운트는 단조 증가(monotonic). max를 취하면 어떤 노드가 더 최신인지 자동 결정.

**사용 예**: 페이지 뷰 카운트, 좋아요 수.

2.2 PN-Counter (Positive-Negative Counter)

증가/감소 모두 가능.

class PNCounter:

def __init__(self, node_id):

self.positive = GCounter(node_id) # 증가용

self.negative = GCounter(node_id) # 감소용

def increment(self):

self.positive.increment()

def decrement(self):

self.negative.increment()

def value(self):

return self.positive.value() - self.negative.value()

def merge(self, other):

self.positive.merge(other.positive)

self.negative.merge(other.negative)

**핵심 트릭**: 두 개의 G-Counter로 분리. 감소는 "음수의 증가"로 표현.

2.3 G-Set (Grow-only Set)

요소 추가만 가능한 Set.

class GSet:

def __init__(self):

self.elements = set()

def add(self, e):

self.elements.add(e)

def merge(self, other):

self.elements |= other.elements # 합집합

**한계**: 삭제 불가능. 영원히 자라는 Set.

2.4 2P-Set (Two-Phase Set)

추가와 삭제 모두 가능. 단, **한 번 삭제된 요소는 다시 추가 불가**.

class TwoPhaseSet:

def __init__(self):

self.added = set()

self.removed = set()

def add(self, e):

if e not in self.removed:

self.added.add(e)

def remove(self, e):

self.removed.add(e)

def contains(self, e):

return e in self.added and e not in self.removed

def merge(self, other):

self.added |= other.added

self.removed |= other.removed

**한계**: tombstone(삭제 표시)이 영원히 누적.

2.5 LWW-Register (Last-Write-Wins Register)

타임스탬프 기반의 단일 값.

class LWWRegister:

def __init__(self):

self.value = None

self.timestamp = 0

def write(self, value, timestamp):

if timestamp > self.timestamp:

self.value = value

self.timestamp = timestamp

def merge(self, other):

if other.timestamp > self.timestamp:

self.value = other.value

self.timestamp = other.timestamp

**문제**: 시계 동기화. **Hybrid Logical Clock(HLC)**로 해결.

2.6 OR-Set (Observed-Remove Set)

가장 실용적인 Set CRDT. 추가/삭제 자유.

class ORSet:

def __init__(self):

{element: set of unique tags}

self.elements = defaultdict(set)

self.tombstones = defaultdict(set)

def add(self, e):

tag = uuid.uuid4()

self.elements[e].add(tag)

def remove(self, e):

현재 보이는 모든 태그를 tombstone에

self.tombstones[e] |= self.elements[e]

def contains(self, e):

return bool(self.elements[e] - self.tombstones[e])

def merge(self, other):

for e, tags in other.elements.items():

self.elements[e] |= tags

for e, tags in other.tombstones.items():

self.tombstones[e] |= tags

**핵심 아이디어**: 각 추가에 고유 태그. 삭제는 "현재 본 태그들"을 tombstone에 추가. 새 추가는 새 태그 → 살아남음.

3. 텍스트 협업 — 가장 어려운 CRDT

3.1 왜 텍스트가 어려운가?

**시나리오**: 두 사용자가 같은 위치에 동시에 삽입.

초기: "ABCDE"

User A: 위치 2에 "X" 삽입 → "ABXCDE"

User B: 위치 2에 "Y" 삽입 → "ABYCDE"

병합: "ABXYCDE" 또는 "ABYXCDE"?

**문제**: 위치는 상대적입니다. 한 사용자의 삽입이 다른 사용자의 위치를 무효화.

3.2 RGA (Replicated Growable Array)

각 문자에 **고유 ID**를 부여. 위치 대신 ID를 참조.

초기 문서:

[start] - A(id1) - B(id2) - C(id3) - [end]

User A: B 다음에 X 삽입 (id4)

[start] - A(id1) - B(id2) - X(id4) - C(id3) - [end]

User B: B 다음에 Y 삽입 (id5)

[start] - A(id1) - B(id2) - Y(id5) - C(id3) - [end]

병합 (id로 비교, 작은 id가 먼저):

[start] - A(id1) - B(id2) - X(id4) - Y(id5) - C(id3) - [end]

**핵심**: 고유 ID + 정렬 규칙으로 결정적 병합.

3.3 Yjs의 YATA 알고리즘

Yjs는 **YATA(Yet Another Transformation Approach)**라는 변형 알고리즘 사용. RGA보다 효율적입니다.

각 문자가 다음을 가집니다:

- 고유 ID `(client_id, clock)`

- `origin_left`: 삽입 시 왼쪽 이웃의 ID

- `origin_right`: 삽입 시 오른쪽 이웃의 ID

병합 규칙:

1. 같은 origin을 가진 삽입들은 client_id 순으로 정렬

2. origin이 다르면 위치 정보로 정렬

**효율성**: Yjs는 같은 문자열의 연속 입력을 단일 객체로 압축 → 메모리 100배+ 효율.

4. Yjs — JavaScript CRDT의 표준

4.1 기본 사용법

// 공유 문서 생성

const doc = new Y.Doc()

// 공유 텍스트

const ytext = doc.getText('shared-text')

ytext.insert(0, 'Hello, ')

ytext.insert(7, 'World!')

console.log(ytext.toString()) // "Hello, World!"

// P2P 동기화 (WebRTC)

const provider = new WebrtcProvider('my-room', doc)

4.2 다양한 데이터 타입

// 텍스트

const ytext = doc.getText('text')

ytext.insert(0, 'Hello')

// 배열

const yarray = doc.getArray('list')

yarray.push(['item1', 'item2'])

// 맵 (객체)

const ymap = doc.getMap('config')

ymap.set('theme', 'dark')

// XML/JSON

const yxml = doc.getXmlFragment('content')

4.3 변경 감지

ytext.observe((event) => {

console.log('Changes:', event.changes.delta)

// [{ retain: 7 }, { insert: 'World!' }]

})

4.4 영속화 — IndexedDB

const persistence = new IndexeddbPersistence('my-doc', doc)

persistence.on('synced', () => {

console.log('Loaded from IndexedDB')

})

브라우저 새로고침 후에도 상태 유지 — 진정한 로컬 우선.

4.5 다중 프로바이더

Yjs는 transport-agnostic — 여러 동기화 방식 지원:

- `y-websocket` — 중앙 서버 동기화

- `y-webrtc` — P2P 동기화

- `y-indexeddb` — 로컬 영속화

- `y-leveldb` — Node.js 서버

- 커스텀 프로바이더 작성 가능

5. Automerge — JSON 데이터 모델

5.1 JSON 친화적 인터페이스

let doc = Automerge.init()

doc = Automerge.change(doc, 'Initial', d => {

d.todos = []

d.todos.push({ text: 'Buy milk', done: false })

})

// 다른 디바이스

let doc2 = Automerge.merge(Automerge.init(), doc)

doc2 = Automerge.change(doc2, 'Add task', d => {

d.todos.push({ text: 'Walk dog', done: false })

})

// 병합

const merged = Automerge.merge(doc, doc2)

console.log(merged.todos) // [Buy milk, Walk dog]

5.2 Yjs vs Automerge

| | Yjs | Automerge |

|---|---|---|

| 작성 언어 | JavaScript | TypeScript + WASM |

| 데이터 모델 | CRDT 타입 (Y.Text, Y.Map) | JSON-like |

| 텍스트 성능 | **매우 빠름** | 좋음 |

| 메모리 효율 | 우수 | 보통 |

| 학습 곡선 | 중간 | 낮음 |

| 사용 사례 | 협업 에디터 | 일반 데이터 동기화 |

| 문서 크기 | 작음 | 보통 |

| 사용처 | Notion, Linear, Affine | Local-first 앱 |

**선택 가이드**:

- **텍스트 협업** (에디터, 노트): Yjs

- **JSON 데이터** (앱 상태, 폼): Automerge

- **둘 다 고려**: 프로토타입은 Automerge가 빠름

6. Local-First Software 운동

6.1 7가지 이상

Ink & Switch 연구소의 [Local-First Software](https://www.inkandswitch.com/local-first/) 매니페스토:

1. **빠르다** — 네트워크 왕복 없음

2. **다중 디바이스 작동** — 동기화는 백그라운드

3. **네트워크 선택적** — 오프라인에서 완전 작동

4. **다른 사람과 협업** — CRDT로 충돌 해결

5. **장기적 보존** — 클라우드가 사라져도 데이터 보존

6. **기본적 보안과 프라이버시** — 데이터는 사용자 디바이스에

7. **궁극적 사용자 통제** — 데이터 소유권

6.2 클라우드 우선 vs 로컬 우선

| | 클라우드 우선 | 로컬 우선 |

|---|---|---|

| 데이터 위치 | 서버 | 디바이스 |

| 오프라인 | 작동 X | 완전 작동 |

| 응답 시간 | 네트워크 의존 | 즉시 |

| 협업 | 서버 중계 | P2P 또는 서버 |

| 회사 폐업 | 데이터 손실 | 데이터 유지 |

| 예시 | Google Docs | Obsidian, Logseq, Linear |

6.3 로컬 우선 채택 사례

**Linear** — 프로젝트 관리:

- 전체 데이터를 로컬 IndexedDB에

- 즉시 응답 (latency 0)

- WebSocket으로 백그라운드 동기화

- 오프라인 변경은 큐에 저장 후 재연결 시 전송

**Figma** — 디자인 협업:

- 자체 CRDT 구현 (RGA 기반)

- 실시간 멀티 커서

- 오프라인 편집 후 동기화

**Affine** — 노트:

- Yjs 사용

- 완전 로컬 우선

- 클라우드는 선택적 동기화

**Notion** — 노트/위키:

- 부분적 CRDT (블록 단위)

- 텍스트 편집은 OT에서 CRDT로 마이그레이션 중

7. CRDT vs OT (Operational Transformation)

7.1 OT란?

Google Docs가 사용한 전통적 협업 방식. **연산 변환** — 동시 연산을 변환하여 일관성 유지.

초기: "ABC"

User A: insert(1, "X") → "AXBC"

User B: delete(2) → "AB"

User B의 연산을 User A의 변경 후로 변환:

delete(2) → delete(3) (위치 조정)

결과: "AXB"

7.2 비교

| | OT | CRDT |

|---|---|---|

| 중앙 서버 | 필수 | 선택 |

| 오프라인 지원 | 어려움 | 자연스러움 |

| 알고리즘 복잡도 | 매우 복잡 | 복잡 (하지만 검증 가능) |

| P2P | 어려움 | 자연스러움 |

| Google Docs | ✅ (현재) | ❌ |

| Figma, Linear | ❌ | ✅ |

| 학계 연구 | 1990년대~ | 2000년대~ |

**트렌드**: OT → CRDT 마이그레이션 (Notion, Confluent 등). CRDT가 분산 환경에 더 적합.

8. CRDT의 한계와 함정

8.1 메타데이터 폭증

**문제**: tombstone, 태그, 클럭 등이 누적되어 문서 크기가 실제 콘텐츠보다 큼.

**해결**:

- **압축(Compaction)**: 더 이상 필요 없는 메타데이터 정리

- **델타 압축**: Yjs가 사용. 연속 작업을 단일 객체로

- **체크포인트**: 주기적으로 베이스라인 생성

8.2 의미적 충돌

CRDT는 **구문적 충돌**(같은 위치 동시 편집)을 해결합니다. **의미적 충돌**은 해결 못 합니다.

**예시**: 캘린더 앱. 두 사용자가 같은 회의실을 다른 회의로 동시 예약. CRDT는 둘 다 예약 성공으로 처리 — **비즈니스 규칙 위반**.

**해결**: CRDT 위에 비즈니스 로직 레이어 추가. 또는 강한 일관성이 필요한 부분은 다른 메커니즘.

8.3 부분적 CRDT가 더 실용적

**Notion**의 접근: 블록 수준에서 CRDT, 블록 내부는 일반 텍스트. 모든 것을 CRDT로 만들 필요 없음.

**Linear**의 접근: 일부 필드만 CRDT, 나머지는 LWW. 단순함과 성능의 균형.

9. 실전 — 협업 텍스트 에디터 만들기

9.1 기본 구조

// 1. Yjs 문서 생성

const ydoc = new Y.Doc()

const ytext = ydoc.getText('codemirror')

// 2. 동기화 프로바이더

const provider = new WebsocketProvider(

'wss://my-server.com',

'document-id-123',

ydoc

)

// 3. CodeMirror 에디터 + Yjs 통합

const view = new EditorView({

doc: ytext.toString(),

extensions: [

basicSetup,

yCollab(ytext, provider.awareness) // 협업 확장

parent: document.body

})

코드 100줄 미만으로 **Google Docs 같은 협업 에디터** 구현 가능.

9.2 사용자 인식 (Awareness)

provider.awareness.setLocalStateField('user', {

name: 'Alice',

color: '#ff0000'

})

provider.awareness.on('change', () => {

const users = Array.from(provider.awareness.getStates().values())

console.log('Online users:', users)

})

다른 사용자의 커서, 선택 영역이 자동으로 표시됩니다.

퀴즈

**답**: (1) **결합법칙 (Associativity)**: `(a + b) + c = a + (b + c)`, (2) **교환법칙 (Commutativity)**: `a + b = b + a`, (3) **멱등성 (Idempotence)**: `a + a = a`. 이 세 가지를 만족하면 어떤 순서로 병합해도 결과가 동일합니다. 이를 ACI 속성 또는 **semilattice**라고 합니다. 이것이 CRDT의 자동 충돌 해결의 수학적 기반입니다.

**답**: **State-based (CvRDT)**는 전체 상태를 전송, 병합 함수로 결합. 메시지 순서 무관, 단순. 단점은 큰 상태 = 큰 네트워크 비용. **Operation-based (CmRDT)**는 연산만 전송. 작은 메시지지만 안정적인 메시지 전달 필요 (at-least-once delivery + 멱등성). 실용적 라이브러리(Yjs, Automerge)는 **하이브리드** 접근을 사용합니다.

**답**: **텍스트 협업** (에디터, 노트, IDE) → Yjs (성능과 메모리 효율 우수, 사용처: Notion, Linear, Affine). **JSON 데이터 동기화** (앱 상태, 폼, 설정) → Automerge (JSON-like API, 학습 곡선 낮음). 둘 다 고려된다면 프로토타입은 Automerge로 빠르게, 프로덕션은 Yjs로 최적화하는 패턴이 일반적입니다.

**답**: Ink & Switch의 7가지 이상: (1) 빠르다(네트워크 의존 X), (2) 다중 디바이스, (3) 네트워크 선택적(오프라인 완전 작동), (4) 협업, (5) 장기적 보존(클라우드 사라져도 데이터 유지), (6) 보안/프라이버시(데이터는 디바이스에), (7) 사용자 데이터 통제. **클라우드 우선**은 회사가 망하면 데이터도 사라지지만, **로컬 우선**은 데이터가 사용자 손에 있습니다. Linear, Figma, Notion이 채택했습니다.

**답**: **의미적 충돌(semantic conflict)**입니다. CRDT는 같은 데이터 구조의 동시 변경을 자동 병합하지만, 비즈니스 규칙 위반은 못 막습니다. 예시: 두 사용자가 같은 회의실을 다른 회의로 동시 예약 → CRDT는 둘 다 성공으로 처리. 해결: CRDT 위에 비즈니스 로직 레이어 추가, 또는 강한 일관성이 필요한 부분은 별도 메커니즘(중앙 검증, 분산 락 등) 사용.

참고 자료

- [CRDT.tech](https://crdt.tech/) — CRDT 종합 자료

- [Local-First Software](https://www.inkandswitch.com/local-first/) — Ink & Switch 매니페스토

- [Yjs](https://yjs.dev/) — 공식 문서

- [Automerge](https://automerge.org/) — 공식 문서

- [Conflict-Free Replicated Data Types](https://hal.inria.fr/inria-00609399v1/document) — 원논문 (Shapiro 2011)

- [A Conflict-Free Replicated JSON Datatype](https://arxiv.org/abs/1608.03960) — Automerge 논문

- [YATA: Yet Another Transformation Approach](https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types) — Yjs 알고리즘

- [Designing Data-Intensive Applications](https://dataintensive.net/) — Martin Kleppmann (CRDT 챕터)

- [Linear's offline mode](https://linear.app/blog/scaling-the-linear-sync-engine) — Linear 동기화 엔진

- [Figma's multiplayer technology](https://www.figma.com/blog/how-figmas-multiplayer-technology-works/) — Figma 협업

- [Diamond Types](https://github.com/josephg/diamond-types) — Rust로 작성된 고성능 CRDT