42

私は、Google Docs に似た機能 (複数の人が同時に作業できるようにする) を備えた、独自の Javascript エディターを作成することをいじっています。私が理解していないことの1つ：

ユーザー A とユーザー B が 10 ミリ秒のネットワーク遅延で互いに直接接続されているとします。私は、編集が「インデックス 3 に「テキスト」を挿入」のように表される diff システム (Docs が行っていることを理解している) をエディターが使用していると仮定しています。

「xyz123」というテキストを含むドキュメントから始めましょう。

ユーザー A はタイムスタンプ 001ms でドキュメントの先頭に「abc」と入力し、ユーザー B はタイムスタンプ 005ms で「xyz」と「123」の間に「hello」と入力します。

どちらのユーザーも、結果が「abcxyzhello123」になることを期待しますが、ネットワークの遅延を考慮すると、次のようになります。

  • ユーザー B は、時間 011ms にユーザー A の「インデックス 0 に 'abc' を挿入」の編集を受け取ります。時系列の順序を維持するために、ユーザー B はユーザー B のインデックス 3 での挿入を元に戻し、ユーザー A の「abc」をインデックス 0 で挿入し、次にユーザー B のインデックス 3 での挿入を再挿入します。これは現在「abc」と「xyz」の間にあります。 、」したがって、「abchelloxyz123」が得られます
  • ユーザー A は、時間 015ms にユーザー B の「インデックス 3 に「hello」を挿入」の編集を受け取ります。ユーザー B の挿入がユーザー A の後に行われたことを認識し、インデックス 3 (現在は "abc" と "xyz" の間) に "hello" を挿入するだけで、"abchelloxyz123" となります。

もちろん、「abchello xyz123」は「 abc xyz hello 123」と同じではありません。

文字通りすべてのキャラクターに独自の一意の ID を割り当てる以外に、Google がこの問題を効果的に解決する方法を想像することはできません。

私が考えたいくつかの可能性：

  • ユーザー B が編集前に挿入ポイントを 1 ミリ秒移動した場合、まったく同じ問題が発生することを除いて、差分を含むインデックスを送信する代わりに挿入ポイントを追跡することは機能します。
  • ユーザー B に、「'xyz' の後に挿入」などの情報を diff で送信してもらい、ユーザー A がこれが発生したことをインテリジェントに認識できるようにすることもできますが、ユーザー A がテキスト「xyz」を挿入するとどうなるでしょうか。
  • ユーザー B は、これが発生したことを認識し (ユーザー A の diff を受信し、それが競合していることを確認すると)、ユーザー B の編集を元に戻す diff と、ユーザー B の "hello" "abc".length インデックスをさらに挿入する新しい diff を送信します。右。これに関する問題は、(1) ユーザー A がテキストに「ジャンプ」を表示すること、および (2) ユーザー A が編集を続ける場合、ユーザー B は継続的に差分を修正する必要があることです。修正する必要があり、複雑さが指数関数的に増加します。
  • ユーザー B は、最後に受信したタイムスタンプ付きの diff が -005ms か何かであるというプロパティを diff と共に送信できます。その後、A は B がその変更について知らなかったことを認識し (A の diff は 001ms であったため)、競合の解決を行うことができます。問題は、(1) ほとんどのコンピューターの時計がミリ秒単位で正確ではないことを考慮すると、すべてのユーザーのタイムスタンプがわずかにずれることと、(2) ユーザー A との遅延が 25 ミリ秒でユーザー B との遅延が 2 ミリ秒の 3 番目のユーザー C が存在する場合、ユーザー C が -003ms で「x」と「y」の間にテキストを追加すると、ユーザー B はユーザー C の編集を参照点として使用しますが、ユーザー A はユーザー C の編集については知りません (したがって、ユーザー B の参照点) 22msまで。共通のサーバーを使用してすべての編集にタイムスタンプを付ければ、これは解決できると思いますが、それはかなり複雑なようです。
  • 各キャラクターに一意の ID を与え、インデックスの代わりにそれらの ID を使用することもできますが、それはやり過ぎのように思えます...

http://www.waveprotocol.org/whitepapers/operational-transformを読んでいますが、この問題を解決するためのあらゆるアプローチを聞きたいです。

4

1 に答える 1

53

シナリオのトポロジとさまざまなトレードオフに応じて、レプリカの同時変更を実現するさまざまな可能性があります。

中央サーバーの使用

最も一般的なシナリオは、すべてのクライアントが通信する必要がある中央サーバーです。

サーバーは、各参加者のドキュメントがどのように見えるかを追跡できます。次に、A と B の両方が、変更を含む差分をサーバーに送信します。次に、サーバーは変更をそれぞれの追跡ドキュメントに適用します。次に、3 者間マージを実行し、マスター ドキュメントに変更を適用します。次に、マスター ドキュメントと追跡ドキュメントの差分をそれぞれのクライアントに送信します。これは、差分同期と呼ばれます。

従来のバージョン管理システムでのリベースに似た別のアプローチは、操作 (アル) 変換と呼ばれます。中央サーバーは必要ありませんが、1 つあると参加者が 2 人を超える場合に作業がはるかに簡単になります ( OT FAQを参照してください)。要点は、編集が別の編集の変更が既に行われたと想定するように、1 つの編集で変更を変換することです。たとえば、A は B の編集insert(3, hello)をその編集に対してinsert(0, abc)結果として変換しますinsert(6, hello)。

リベースと OT の違いは、異なる順序で編集を適用した場合、リベースでは一貫性が保証されないことです (たとえば、B が A の編集を A の編集に対して逆にリベースすると、ドキュメントの状態が分岐する可能性があります)。一方、OT の約束は、適切な変換を行った場合に任意の順序を許可することです。

中央サーバーなし

ピア ツー ピアのシナリオに対処できる OT アルゴリズムが存在します (制御レイヤーでの実装の複雑さとメモリ使用量の増加というトレードオフがあります)。単純なタイムスタンプの代わりに、Version ベクトルを使用して、編集の基になっている状態を追跡できます。次に (OT アルゴリズムの機能、具体的には transform プロパティ 2に応じて)、受信した編集を受信した順序に合わせて変換するか、バージョン ベクトルを使用して編集に半順序を課すことができます。ケース履歴は、編集を元に戻したり変換したりして「書き直す」必要があるため、バージョン ベクトルによって課された順序に準拠する必要があります。

最後に、WOOT、Treedoc、または Logoot と呼ばれるCRDTに基づくアルゴリズムのグループがあります。これらは、操作の交換を可能にする特別に設計されたデータ型で問題を解決しようとするため、それらが適用される順序は重要ではありません (これは各キャラクターの ID の考え方に似ています)。ここでのトレードオフは、メモリの消費と操作の構築におけるオーバーヘッドです。

于 2016-04-01T21:33:05.457 に答える