CRDT 완전 가이드 2025: 충돌 없는 복제 데이터 타입, 로컬 우선 협업, Yjs/Automerge

초기: "Hello"

User A 추가:        "Hello World"
User B 동시 추가:   "Hello Friend"

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

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)

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)

class GSet:
    def __init__(self):
        self.elements = set()

    def add(self, e):
        self.elements.add(e)

    def merge(self, other):
        self.elements |= other.elements  # 합집합

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

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

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

초기: "ABCDE"

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

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

초기 문서:
  [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]

import * as Y from 'yjs'
import { WebrtcProvider } from 'y-webrtc'

// 공유 문서 생성
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)

// 텍스트
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')

ytext.observe((event) => {
  console.log('Changes:', event.changes.delta)
  // [{ retain: 7 }, { insert: 'World!' }]
})

import { IndexeddbPersistence } from 'y-indexeddb'

const persistence = new IndexeddbPersistence('my-doc', doc)
persistence.on('synced', () => {
  console.log('Loaded from IndexedDB')
})

import * as Automerge from '@automerge/automerge'

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]

초기: "ABC"

User A: insert(1, "X") → "AXBC"
User B: delete(2) → "AB"

User B의 연산을 User A의 변경 후로 변환:
  delete(2) → delete(3) (위치 조정)

결과: "AXB"

import * as Y from 'yjs'
import { WebsocketProvider } from 'y-websocket'
import { EditorView, basicSetup } from 'codemirror'
import { yCollab } from 'y-codemirror.next'

// 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
})

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)
})