CRDT完全ガイド 2025: Conflict-Free Replicated Data Types、ローカルファースト協業、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)
})