Upgrade to Pro — share decks privately, control downloads, hide ads and more …

CRDTで始めるコンフリクトしないデータ同期

 CRDTで始めるコンフリクトしないデータ同期

Yuto Takamune

May 14, 2023
Tweet

More Decks by Yuto Takamune

Other Decks in Technology

Transcript

  1. Strong Eventual Consistency(SEC) • Eventual delivery ◦ ある正しいレプリカに配信されたアップデートは、最終的にすべての正しいレ ◦ プリカに配信される

    • Strong Convergence ◦ 配信した正しいレプリカは同等の状態を持つ • Termination ◦ すべてのメソッドの実行が終了する
  2. CvRDTとCmRDT • State-based なConvergent Replicated Data Type(CvRDT) ◦ レプリカ自体を共有して merge

    していくタイプのCRDT • Operation-basedなCommutative Replicated Data Type(CmRDT) ◦ レプリカ間で操作を共有していくタイプの CRDT
  3. CvRDT • レプリカ自体を共有してmerge していくタイプのCRDT • レプリカのマージは可換かつ冪等 • 可換: どの順番でmergeしても同じ結果になる •

    冪等: 何回mergeの操作を適用しても同じ結果になる • つまり: メッセージが失われたり、順番が違ったり、複数回受信されたりしても、最終 的に同じ結果に収束する • レプリカ全体を同期させるのでデータが大きくなると結構びみょい
  4. TreeDocとは • テキスト共同編集のためのCRDT(CmRDT) • binary treeにテキストを保存していく構造 • atomと呼ばれる要素がNodeになる • 各atomはPosIDという一意の位置識別子を持つ

    ◦ PosIDにはRootからNodeへのPathが使われる ◦ 右図の場合、たとえば dのPosIDは10 • 同じ位置に異なるatomを同時に挿入する可能性を考え、binary treeのNodeに binary treeを持たせるような構造になっている • Deleteは、削除したNodeにtombstoneを持たせる仕組み 引用: Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, Mihai Leția “A commutative replicated data type for cooperative editing”
  5. 参考文献 • Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek

    Zawirski. Conflict-free replicated data types. In 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS 2011, pages 386--400. Springer LNCS volume 6976, October 2011. • Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. A comprehensive study of convergent and commutative replicated data types. Research Report 7506, INRIA, January 2011. • Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, Mihai Leția. A commutative replicated data type for cooperative editing. 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), Jun 2009, Montreal, Québec, Canada. pp.395-403, ff10.1109/ICDCS.2009.20ff. ffinria00445975f