CRDT
gpt-4.icon
Conflict-free Replicated Data Type（CRDT、コンフリクトフリー複製データ型）は、分散システムにおいてデータの自動マージを可能にするデータ構造です。ネットワーク分断や非同期通信があるような環境でも、競合（conflict）なしで一貫した状態に収束できるように設計されています。
💡 背景と動機
分散システムでは、複数ノードがローカルでデータを変更し、その後同期を試みます。このときに「どちらの変更を採用するか」「どうマージするか」といった競合処理が問題になります。
通常の解決策：
中央集権的なロックやトランザクション
ユーザーによるマージの介入
これらはスケーラビリティや耐障害性に課題があります。
そこで、CRDTは「競合をそもそも起こさない」ようにする設計で注目されています。
📚 基本原理
CRDTには以下の2種類があります：
1. 状態ベース（State-based）CRDT = CvRDT 各ノードが状態（state）を持ち、他ノードと「マージ」することで一貫性を得る。
要件：状態のマージが可換（commutative）・結合的（associative）・冪等（idempotent）
マージ関数が存在し、部分順序集合の上で「最小上界」をとるイメージ。
2. 操作ベース（Operation-based）CRDT = CmRDT 各操作（オペレーション）が他ノードに伝播され、適用される。
要件：操作が可換であること（適用順が違っても結果が同じ）
🧱 代表的なCRDTの例
table:_
データ型 CRDT名 説明
セット G-Set（Grow-only Set） 追加のみ可能
セット 2P-Set（Two-Phase Set） 追加・削除可（削除した要素は二度と追加不可）
セット OR-Set（Observed-Remove Set） 複数ノードで同時に追加/削除しても整合性が取れる
カウンタ G-Counter（Grow-only Counter） インクリメントのみ可能なカウンタ
カウンタ PN-Counter 加算・減算の両方が可能
Map LWW-Map（Last-Write-Wins Map） タイムスタンプによって競合を解決
リスト RGA（Replicated Growable Array） 並行編集されたリストを整合的にマージ可能
🌍 実用例
CRDTは主にリアルタイム協調アプリケーションや分散データベースで使われています：
共同編集ツール（例：Google Docs, Figma） オフライン編集後の自動マージ（例：Notion, Automerge）
分散キーバリューストア（例：Redis CRDT, Riak）
🔍 参考リンク
JSのライブラリ