- CRDT(Conflict-free Replicated Data Type, 競合のない複製データ型) は、ネットワーク分断や同時更新の状況でも 調停なしに一貫したデータマージ を可能にする分散データ構造である
- データマージが 交換法則・結合法則・冪等性 を満たせば、すべてのレプリカは最終的に同一の状態へ収束する
- 代表的なものとして G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot などがあり、それぞれ異なる 追加・削除・再追加・順序維持 の要件を扱う
- Delta CRDT は全体状態の代わりに変更分だけを送ることで効率を高め、Garbage Collection はメタデータ蓄積の問題を解決するための重要課題である
- CRDTは万能な解決策ではないが、可用性が即時一貫性より重要なシステム において強力な選択肢と評価されている
CRDTの基本概念
- CRDTは 分散環境で同時更新が発生しても、調停なしにマージ可能なデータ構造
- マージ演算が 可換(commutative)、結合的(associative)、冪等(idempotent) であれば、すべてのレプリカが同一状態へ収束する
- Lattice(束) の概念に基づき、状態が常に「上方向」にのみ進むよう設計される
- 例: G-Counterは各レプリカのカウントを
max でマージし、損失のない合算を保証する
- CRDTには State-based(CvRDT) と Operation-based(CmRDT) の2つのアプローチがある
- CvRDTは全体状態をマージし、CmRDTは操作を伝播する
主なCRDTの種類
- G-Counter: 増加のみ可能なカウンタ、各レプリカの値を合算
- PN-Counter: 増加用・減少用のG-Counterを組み合わせ、双方向カウントをサポート
- G-Set: 追加のみ可能な集合
- 2P-Set: 追加・削除は可能だが再追加は不可
- LWW-Element-Set: タイムスタンプに基づき、最新の操作が勝つ
- OR-Set: 一意タグを用いて 同時追加時もデータ損失なくマージ し、add-winsで動作
- LWW-Register / MV-Register: 単一値保存用で、LWWは単一の勝者、MVは同時値をすべて保持
- OR-Map: キーごとにOR-Setを組み合わせたマップ構造
- RGA / WOOT / Logoot / LSEQ: 順序付きシーケンスデータ向けのCRDT
- RGAはツリーベース、WOOTは双方向参照ベース、Logoot/LSEQは位置識別子ベース
高度なCRDTの概念
- Causal CRDTs: バージョンベクタを使って因果関係を追跡し、より正確な競合検出が可能
- Delta CRDTs: 全体状態の代わりに変更分(デルタ)だけを送信し、ネットワーク効率を向上
- Tree CRDTs: 階層構造データ(ファイルシステムなど)の複製をサポートし、親子関係の維持が必要
- Observed-Remove Shopping Cart: OR-SetとPN-Counterを組み合わせたEC向けショッピングカートの例
Garbage Collectionの問題
- CRDTは収束のためにメタデータを継続的に蓄積するため、無限成長の問題 が発生する
- 例: OR-Setのタグ、RGAのtombstone
- 時間ベースの期限切れ, 合意ベースの削除, バージョンベクタベースの因果追跡, メタデータ上限の設定, チェックポイント/リベース など多様な戦略がある
- 各方式は 安全性(ゾンビ復元防止) と 空間効率性 の間でトレードオフが必要
性能と選定ガイド
- CRDTの種類ごとの空間・時間計算量は、レプリカ数、要素数、タグ数などに応じて変わる
- G/PN-Counterはレプリカ数に比例し、OR-Setはタグ数に比例、RGAはtombstoneが蓄積する
- Delta CRDT はマージ性能を大きく改善する
- 選定基準:
- 追加のみ必要 → G-Counter, G-Set
- 削除が必要、再追加は不要 → 2P-Set
- LWWを許容 → LWW-Set/Register
- 同時更新の保持 → OR-Set, MV-Register
- 順序維持が必要 → RGA, Logoot
- ネスト構造 → OR-Map
結論
- CRDTは 調停なしの収束 を保証するが、メタデータ増加と複雑性 が欠点である
- 可用性優先のシステム で有用であり、各CRDTは特定の問題タイプに最適化されている
- 実務では従来型データベースと併用され、ガベージコレクション戦略 が必須
- 「完璧なCRDT」は存在せず、アプリケーション要件に合った選択 が重要である
1件のコメント
Hacker Newsの意見
CRDTの興味深い点の1つは、単に複数の低レベルCRDTを組み合わせたライブラリではないということ たとえばAutomergeはそれ自体で完全なCRDTであり、数学的証明によって並行実行下でも一貫性を保証する AutomergeチームはIsabelleのような定理証明ツールで設計を検証し、データベース分野の最新の性能手法を適用して、高速かつ正確な実装を目指している リアルタイム協業が必要なSaaS（例: Notion、Figma）を作るなら、複雑な理論を知らなくても協調型データ構造をすぐに適用できる バックエンドはシンプルなkey-valueストレージで十分で、フロントエンドはライブラリ1つで済む
CRDTの基本から高度な概念までよく整理された記事だった ちなみにRiakは今でもOpenRiakとして維持されている
この2年間、直接CRDTを開発してきたが、あまりに多くのトレードオフがあると気づき、最終的にIDベースのOTフレームワークへ移行した 今週火曜日にDocnode.devをローンチする予定だ。フィードバックを聞きたい 今後はP2Pが必要な状況に備えて、CRDTモードも追加する計画だ
CRDTやOTは人々が同じ段落を同時に編集するときの問題を解決しようとする仕組みだが、実際にはそういう状況はほとんど発生しない
この記事でいうOR-Setは、昔Monotoneが2005年から使っていたマージ方式と似ている 関連資料はMarkMerge文書で見られる
CRDTは依然として自分で実装しなければならない領域だ 私も2か月前、diamond typesに着想を得てシーケンスベースのCRDTエンジンを作った AIに助けを求めたが、こうした論理中心の問題にはまったく役に立たなかった LLMが新しいロジックを理解できるか検証するブラックボックステストが必要だと感じる
記事は素晴らしかったが、用語集には**索引(index)**がぜひ必要だと思う
CRDTは結局、マージ競合をDBからアプリケーションロジックへ押し出しているだけなのではないかという気がする