yjsのCRDT論

リポジトリ
https://github.com/yjs/yjs

アルゴリズムを紹介している論文
https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types

INTRODUCTION

• NRT（Near real-time）コラボレーションという分野におけるOTとの比較や優位性
  • client-serverであるOTとP2PであるCRDT
  • NRTコラボアプリにおけるモデリングやらアルゴリズムやらに費やす時間を減らすべく作られたOSSがyjs
• アルゴリズムはYATAと名付けられている
  • Yet Another Transformation Approach
  • yjsはこれの実装
  • CRDTは削除データの肥大化という問題を抱えているが、YATAではGCの導入によってこれを解決している

RELATED WORK

• OTとCRDTの紹介
• OTは比較用なので略
• CRDT
  • 互いに競合しないよう定義された操作による optimistic concurrency control（楽観的な並行制御？） を要請する

  • CRDT systems are designed for peer-to-peer environments and to perform and achieve consis-tency for a big number of users.

  • state-based と operation-based の２種類がある
  • YATAに似たP2PアルゴリズムでWooT（Without OT）というものもある
    • unique idやtombstoneを使うらしいので結構似ていそう
    • この系列でさらに改良されたものも出てきている

Requirements

Unique identifiers

• userはuniqueなIDを持つ
  • ここでは書かれていないがこのIDは一意に並べられることが求められる
  • 単にintegerでインクリメントされていくIDと考えるでもOK

• each user gets an operation counter which gets incremented every time a user creates an operation.

  • 各userの操作にはインクリメントされていく番号が付与される
  • userが異なるorデータが異なれば番号は被る（はず）
    • 同一userの複数環境オフラインだとインクリメントが重複するから無理そう
• 各operationは上記のuser idとoperation counterから構成されたunique identiferを持つことになる
  • 後の文章で単にidと表現されているのは大体これのこと
  • これだけだとアプリケーション全体ではuniqueにならなそう

Operations

• YATA represents linear data (e.g. text) as a doubly linked list.

• We define only two types of changes on this representation: insert and delete.

  • 各要素は全てinsert operationによって表現される
  • deleteはフラグ立てで表現されて要素自体は残る
    • => delete operationはinsert operationに影響を与えなくなる
    • 増え続けるdelete operationによる残骸の処理方法は後述のGCにて
• o_k(id_k, origin_k, left_k, right_k, isDeleted_k, content_k) という表記でoperationを表現する
  • origin_kはこのoperationが作成された時点でのleft_k
  • left_kとright_kは後から追加されるoperationによって変化しうる
  • listの先頭と末尾に対するinsertはspecail caseとしてleft_kとright_kに入れるためのspecial delimitersを用意する
    • beginningとかendとか

YATA

left_k, right_kの間にinsertしたいが、NRTコラボによって間に要素が増えていたようなケースはconflictなので解消する必要がある。

Definition: Intention Preservation.

• 意思の保存？（良い訳が不明）
• insertionはつまるところleft_k, right_kの間のどこかにinsertできればそれでよい

The concurrent insertion problem.

• Figure1のような状態
  • userは"YA"というテキストを見ながらその間に"T"をinsertするoperationを作成したが、実行する段階ではその間に"AT"というテキストが増えていた

Definition: Conflicting insertions.

• Figure1のような状態を一般化して定義している
• 適切なinsert位置を見つけるために3つのルールを満たす<_cを用意する

Rule 1

• We forbid crossing of origin connections (red lines in the graphical epresentation) between conflicting insertions.

• conflictしたinsertion同士のoriginがcrossしてはいけない
• Figure2左のように跨ぐのはOK（origin_2 \leq origin_1）
• 同じoriginを持つことはありうる

Rule 2

• <_cは推移律（transitive law）を満たす

Rule 3

• When two conflicting insertions have the same origin, the insertion with the smaller creator id is to the left.

• originが同じ場合はuser idの大小で位置を決める

Correctness

• <_cはorigin_*にのみ依存し、origin_*は変化しない

  • We can conclude that whenever two sites compare conflicting insertions, they will find the same order for insertions.

  • Furthermore, this implies that all sites will eventually converge.

• この<_cがstrict total order functionであることの証明が続く（本文参照）
  • 全順序

Insert Algorithm

• 上述の<_cを用いたsort実装例
• 同時に競合する要素はせいぜい数個だろうから計算量はそこまで問題でもなさそう

Garbage Collection

• 全員が削除operationを完了したらそのoperationは消すことができる
  • とはいえ全員について完了されたかを知ることは難しい
• 全userが固定のt時間経過までに削除operationを受け取ると仮定して簡単化する
• YATAではGC用の2種類のbufferを用意している
  • GC対象になった時点で第一bufferに移動
    • GC対象になる条件は後述
  • 何事もなくt時間が経過したら第二bufferにコピーする
    • これ以降は対象operationを元のlistからも第二bufferからも安全に削除可能
• ケース次第では削除operationのremovalは不可能になる
  • leftとrightの間にremoveされた削除operationが実は存在していたようなケース

  • In order to ensure consistency, YATA demands that a new insertion is always inserted between the most left non-deleted character and its direct successor.

    • insertは常にdeleteの左側に配置していていく
    • => 左端のdelete以外はremove可能になる
    • => これがGC対象になる条件っぽい
• このGCの仕組みによってYATAはlate join mechanismsをbreakする可能性はある
  • t時間以上offlineになったuserがremovedなoperationを持ったままだった場合
  • => offlineでのGCはサポートしていないらしい
    • これはoffline時はGCが停止する？
    • 停止するけどt時間過ぎたらどのみち動作は保証できないということ？
    • offlineからの復帰時は次節の同期共有処理によって先に状態を最新化していそう

Ofline Editing Support

• offlineからonlineになったタイミングで共有状態からの乖離チェックを行う
  • state vectorによりチェックする

  • A user that receives a state vector compares it with the local state vec-
    tor and sends all remaining operations to the synchronizing client.

YATA独自の方法というよりはstate vector一般の利用方法っぽい

Complexity Analysis

時間計算量の話題

List Manager Operation

• 文字列と同じくここまで見てきたYATAと同じ
• 明記されていないがYATAデータ自体を要素に持つことができそう
  • => 後続のXMLでchildrenとして使っている

Replace Manager Operation

• YATAはinsertとdeleteのみ可能だが、replaceを表現することも可能
• List Managerの機能を使ってReplace Managerを表現する
  • 基本機能はそのままで、先頭要素をcurrent contentと見なせば良い

Map Manager Operation

• keyごとにReplace Managerを割り当てて表現する
• valueとしてprimitive以外にYATAデータそのものも利用可能
  • => ネストしていけるらしい

Representation of Specific Data Formats

• 上記のOperationを組み合わせればJSONやXMLのデータ構造を表現可能
• XMLの場合にYATAでは空attributesや空childrenを制限したりの制約を入れていたりする