# CRDT ## 定義 Conflict-free Replicated Data Type(CRDT)は、競合を存在させない特殊なデータ構造であり、これらのデータ型に対する操作を、結果を変えない任意の順序で適用できる。強力な結果整合性(Strong Eventual Consistency, SEC)を実現する代表的な手法であり、更新が遅れて伝播したり順不同で伝播したりすることを許容しつつ、すべての更新が最終的にターゲットノードへ伝播したときに、それらの間の競合を解決・マージして同じ有効な状態を生成できる。強力な結果整合性は、線形化可能性・直列化可能性のような強力な一貫性モデルと、弱い一貫性である結果整合性の中間に位置し、両方の長所を併せ持つ。CRDT はネットワーク分断でノード間の通信ができない間もレプリカが独立に操作を実行でき、分断中に適用された操作が失われることなく、通信回復後に全ノードの結果を調整できる点で分散システムにおいて特に有用である。Redis に実装例がある。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.10) ## オペレーションベース CRDT(CmRDT)の3条件 CRDT のもっとも単純な例が、オペレーションベースの Commutative Replicated Data Type(CmRDT)である。CmRDT が成立するには、許容される操作が以下の3条件を満たす必要がある。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.10) - **副作用がない**: アプリケーションはシステムの状態を変更しない。 - **交換可能である**: 引数の順序はどちらでも問題にならない(x・y = y・x)。x が y とマージされるか y が x とマージされるかは問題にならない。 - **因果関係で順序付けられる**: 伝達が成功するかどうかは、操作を適用できる状態にシステムが達することを保証する前提条件次第である。 ## 代表的なデータ型 - **増加のみカウンタ**: 各サーバーは他の全参加者から最後に通知されたカウンタの更新で構成される状態ベクトルを保持し、各サーバーは自分の値のみ変更できる。更新伝播時は `merge(state1, state2)` によって各スロットの最大値を取り出し状態を結合する。マージ関数は交換可能で、サーバーが更新できるのは自分の値だけなので追加の調整は不要である。 - **ポジティブネガティブカウンタ(PN カウンタ)**: インクリメント用の P ベクトルとデクリメント用の N ベクトルの2つで構成し、増減両方をサポートする。比較的大きなシステムでは、巨大なベクトルの伝播を避けるためスーパーピアを使用できる。 - **LWW レジスタ(last-write-wins レジスタ)**: それぞれの値にグローバルに順序付けられた一意のタイムスタンプを関連付けて格納し、書き込み競合時にはタイムスタンプが大きいほうのみを保持する。マージ操作(最大タイムスタンプの値を選択)もタイムスタンプに依存するため交換可能である。値の廃棄を許容できない場合は、書き込まれたすべての値を格納するマルチバリューのレジスタとアプリケーション固有のマージ手法を使う。 - **G セット(順序付けられない増加のみセット)**: 各ノードはローカルな状態を維持し要素を追加できる。2つのセットのマージは交換可能な操作である。追加と削除の両方をサポートするには2つのセットを使い、追加セットに含まれる値のみを削除セットに追加できるという特性を維持する。 - **競合のないレプリケート JSON データ型**: リスト型とマップ型を持ち、深くネストされた JSON ドキュメントに対して挿入・削除・代入などの変更を可能にする。クライアント側でマージ操作を実行し、操作が特定の順序で伝播されることを必要としない。 (Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.10) ## 横断的知見 - 未収載(2ソース目以降で充実させる)。 ## 未解決の問い - CmRDT(オペレーションベース)と、状態全体を伝播して merge するステートベース CRDT(CvRDT)は、ネットワーク帯域・実装複雑性の観点でどのようなトレードオフを持つか。本章はオペレーションベースの例のみを扱っており、ステートベースとの比較は今後の課題。 - [[マルチリーダーレプリケーション]] concept が扱う自動衝突解決(強い結果整合性)のうち、CRDT 系と Operational Transformation(OT)系はどのような性能・機能トレードオフを持つか。両者を同一ワークロードで比較したデータの収集が必要。 - Redis の CRDT 実装は、本章が示す増加のみカウンタ・PN カウンタ・LWW レジスタ・G セットのうちどれをどの程度カバーしているか。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] - 概念: [[結果整合性]] / [[線形化可能性]] / [[マルチリーダーレプリケーション]] / [[リーダーレスレプリケーション]] - 実体: [[Redis]] ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.10 強力な結果整合性と CRDTs