CRDT

• Conflict-free Replicated Data Typeとも

• コンフリクトせず、複製可能なデータ

• 分散環境においてCAP定理のAvailabilityとPartition-toleranceの両立を実現する

  • Cは[Strong Eventual Consistency]しかない

• ネットワーク上に異なるバージョンのデータ(レプリカ)を存在させる

• データへの操作を可換なものだけに限定する

  • 足し算など
  • 操作列がすべて到達すれば、すべてのノードのレプリカは収束する→Strong Eventual Consistency!

• Local firstなソフトウェアを実現する

• CmRDT (Operation-Based CRDT)

  • 操作を送り合う
    • atSource (prepare): ローカルレプリカのみで実行される。操作と現在の状態を調べ、操作を表現するためのメッセージを生成する
    • downstream (effect): リモートで適用される
  • 操作が可換である必要がある
  • 操作列がすべて到達しないと収束しないので、操作が確実に&一度だけ伝わるような信頼性の高いメッセージング機構が必要

• CvRDT (State-Based CRDT)

• 全体は$(S,M,Q)$のトリプルから構成される - $S$: Join Semilatticeなステート - $M$: Mutatorの集合。Mutator $m\in M$は、状態$X\in S$を受け取り、新しい状態$X^{\prime }=m(X)$を返す - Mutatorはインフレーションするように定義される。(monotonic semilattice構造) $X⊑m(X)$が成立する - Mutator: 例えばカウンタならinc(), dec()など - $Q$: クエリ関数の集合。

  • Join Semilatticeなレプリカ自体を送りあい、マージ
  • マージするときに、コンフリクトしているかどうか判定するために論理時計が使われている?(kekeho)
    • LWW Registerとか、一部のCvRDTはそうっぽいな(kekeho)

• アプリケーション

  • https://inria.hal.science/inria-00555588/document
  • カウンタ
  • 足し算(G-Set: Grow-only Set)
  • 集合
  • Map
  • Register
  • Graph

• CRDTはNon-adversarial(非敵対的)なシナリオで有効

  • Byzantine Fault TolerantにしたMaking CRDTs Byzantine fault tolerantという論文もある

• 発展形としてδ-CRDTというのもあるらしい

解説

• https://link.springer.com/chapter/10.1007/978-3-642-24550-3_29
• https://redis.com/blog/diving-into-crdts/
• https://qiita.com/everpeace/items/bb73ec64d3e682279d26
• https://inria.hal.science/inria-00555588/document
• https://archive.org/details/Microsoft_Research_Video_153540
• https://github.com/pfrazee/crdt_notes
• https://www.figma.com/ja/blog/how-figmas-multiplayer-technology-works/
• https://josephg.com/blog/crdts-are-the-future/
• https://github.com/ipfs/notes/tree/master/CRDT
• https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html
• https://www.bartoszsypytkowski.com/the-state-of-a-state-based-crdts/
  • Replicated Growable Arraysの解説
    • https://www.bartoszsypytkowski.com/operation-based-crdts-arrays-1/
    • https://www.bartoszsypytkowski.com/operation-based-crdts-arrays-2/

実装

• Automerge CRDT | Automerge CRDT
  • JSON
• Yjs Shared Editing
• Roshi: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

アプリケーションで使われているCRDT

• Groupware, 共同編集でけっこう使われる
• TreeDoc

注意

• CRDTsは書き込みをConflict-freeにしているだけで、読み込みは”annoying”であることが指摘されている
  • Early Read(Potato Ferrari Problem): 2P-Setのショッピングカートに、ポテトとフェラーリを入れる。その後フェラーリを外し、チェックアウトする。フェラーリを外すより先にチェックアウトが走ると、どっちも買うことになる。全てのDeleteが到着したかどうか、カートは知る由もない。
  • Keep CALM and CRDT on: 読み取りクエリもmonotonicにするには…という話が整理されている

その他

• CRDTsは2 way merge

A comprehensive study of CRDTsのまとめ

• https://inria.hal.science/inria-00555588/document Introduction
• Replicationにフォーカス
  • 多くの研究では、Faultがあっても、Global total orderを維持することに重点を置いている
  • しかしながら、Serializationにかかるボトルネックは性能とスケーラビリティに影響を与えている
  • CAP定理は[Consistency]と[Partition-tolerance]のトレードオフを課している
• Eventual ConsistencyやOptimistic Replicationという別のアプローチがある
  • レプリカは、非同期で操作を適用し、他のレプリカに送信する
  • バックグラウンドにあるコンセンサスアルゴリズムがコンフリクトを解消する
  • ネットワークの分断(P)にもかかわらず、データのAvailabilityを高めることができる
  • ハイパフォーマンス
  • 弱い一貫性(Eventual Consistency)が許容できるアプリケーションもある
  • [Reconciliation]は一般的に困難で、大変です
• Eventual Consistencyに対するシンプルなアプローチとして、CRDTの概念を提案
• CRDTはコンセンサスいらず
• Linearizabilityほしいが、これには一般的にコンセンサスが必要なので、CRDTでは弱いQuiescent Consistencyを考える
• 続きを書こうと思ったけど、めんどくさくなってしまって諦めた(kekeho)
  • Delightの輪読でやったときにまとめたスライド: https://blog.kekeho.net/2023/10/23/論文輪読-crdt/