85

Operational Transform と CRDT の主な違いを簡単に説明してもらえますか?

私が理解している限り、どちらも分散システムの異なるノードで競合することなくデータを収束させるアルゴリズムです。

どのユースケースでどのアルゴリズムを使用しますか? 私の知る限り、OTは主にテキストに使用され、CRDTはより一般的で、より高度な構造を正しく処理できますか?

CRDT は OT よりも強力ですか?

私がこの質問をするのは、HTML 文書用の共同エディターを実装する方法を調べようとしていて、最初にどの方向を見ればよいかわからないからです。私は、ShareJS プロジェクトと、ブラウザ上でcontenteditables要素のリッチ テキスト コラボレーションをサポートしようとする試みを見ました。ShareJSのどこにも、そのためにCRDTを使用しようとする試みは見られません。

また、Google Docs が OT を使用していることもわかっており、リッチ ドキュメントのリアルタイム編集に非常にうまく機能しています。Google が OT を選択したのは、当時 CRDT があまり知られていなかったからですか? それとも今日も良い選択でしょうか？

データベースでこれらのアルゴリズムを使用するなど、他のユースケースについても知りたいです。Riak は CRDT を使用しているようです。OT を使用してデータベースのノードを同期し、Paxos/Zab/Raft の代わりにすることはできますか?

4

1 に答える 1

56

どちらのアプローチも、結果整合性を提供するという点で似ています。違いは、その方法にあります。それを見る1つの方法は次のとおりです。

  • OT は操作を変更することでそれを行います。操作はネットワーク経由で送信され、同時操作は受信後に変換されます。
  • CRDT は、状態を変更することによってそれを行います。操作はローカル CRDT で行われます。その状態はネットワーク経由で送信され、コピーの状態とマージされます。マージが行われる回数や順序は関係ありません。すべてのコピーが収束します。

そうです、OT は主にテキストに使用され、CRDT よりも前から使用されていますが、調査によると次のことがわかっています。

文献の多くの OT アルゴリズムは、著者が述べたものとは異なり、収束特性を満たしていません。

言い換えれば、CRDT マージは交換可能ですが、OT 変換関数はそうでない場合があります。

CRDTに関するウィキペディアの記事から：

OT は一般的に複雑で、拡張性に欠ける

さまざまな種類の問題に適したさまざまな種類の CRDT (セット、カウンターなど) があります。テキスト編集用に設計されたものもあります。たとえば、Treedoc -共同編集用の可換複製データ型です。

于 2014-12-15T22:33:22.150 に答える