こんにちは 最近、一連の共同編集記事を開始しました。 最初の記事では、ノンブロッキング編集の問題とその実装への可能なアプローチについて話しました。 最後に、アルゴリズムとして操作変換（OT）を選択したことを思い出させてください。 彼のクライアントサーバーバージョンについての話も発表されました。今日は彼の仕事の詳細を取り上げます。 さらに、OTでのキャンセルの動作が異なる理由と、それがいかに厳しい現実に直面するかを学びます。



さらに、多くのアルゴリズムと図があります。 興味があると思います。

クライアントサーバーモデル

前回の記事の終わりに、OTアプローチの実装の難しさを中央サーバーで回避できることに注目しました。 ピアツーピアアルゴリズムとは異なり、サーバーを使用すると、すべての操作の共通の順序（サーバーでの操作の順序）を入力できます。 したがって、いつでも、サーバー上のドキュメントの状態は1つの番号（リビジョン）によって特徴付けられます。







同時に、任意のクライアントのドキュメントのステータスは、サーバー上の特定のリビジョンと、サーバーとまだ一貫していない特定の数のローカル操作として表すことができます。

サーバーからクライアントへ

まず、クライアントがサーバーから新しい操作を受け取ったときに何が起こるかを調べてみましょう。 この状況では、すべてが明確です。 すべての操作は、サーバーに適用された順序で処理されると想定されています。 このため、操作のリビジョン（クライアントのリビジョン+ 1）がわかります。







リビジョン1は、サーバーとこのクライアントの最新の全体的なドキュメントの状態です。 前の記事で調べた変換を思い出してください。 彼らの助けを借りて、ドキュメントの変更のさまざまな方法を「減らす」ことができます。







わかりやすくするために、この図と後続の図では、Operation3がOp3、Local operation 1がLOp1などの略語を使用します。 右肩は、サーバーで実行されるアクションです。 そして、左側はクライアント上にあります。 変換のプロパティを使用します。これは、前の記事の図で説明されています。







このアクションをもう一度繰り返します。







さらに、次の2つの方向に行動できます。

1. クライアントにOp3 ''操作を適用し、リビジョンをインクリメントし、ローカル操作（LOp1、LOp2）を（LOp1 '、LOp2' '）に置き換えます。
2. ローカル操作をロールバックし、Op3、LOp1 '、LOp2' 'を順番に適用します。

どちらのオプションを選択しても、結果として、クライアントのこの状態を取得します。







現時点で与えられたすべての考慮事項に基づいて、すべてが、両方の場合の結果が類似するように見えます。 そして、パフォーマンス上の理由から、最初のものが望ましいです。 ただし、2番目の方法を使用します。 次のいずれかの記事で、これがどのように原因であるかを説明します。 それまでの間、そのまま使用して続行してください。

クライアントからサーバーへ

サーバーからクライアント側へのデータ送信を検討した後、反対方向の操作を検討します。 上記の例と同じ状態に戻りましょう。







ご覧のように、操作自体とともに、クライアントはリビジョンを送信します。これは、現時点ではクライアントとサーバーに共通です。 これにより、サーバーが履歴を使用して、送信された操作の基になったリビジョンを復元する必要がなくなります。 再び変換を適用します。







ここでは、サーバー上でLOp1 ''操作を適用し、それに応じてリビジョンを増やす必要があることがわかります。 さらに、ドキュメントを操作する他のクライアントに変換された操作を送信する必要があります。







クライアントのステータスは変更されていないことに注意してください。 彼が監査を強化できるようにするために、サーバーは確認を送信する必要があります。 通信チャネルはメッセージ配信順序を保持することが理解されます。これは、以前はLOp1 'の監査よりも小さい監査を持つすべての操作がクライアントに送信されることを意味します。



さらに、クライアントがサーバーから操作を受け取るときの手順により、すべての変換後、ローカル操作の最初の値がサーバー上の対応する操作と同じ値LOp1 'を持つようになります。







確認メッセージを受信すると、クライアントは改訂値を増やします。 このリビジョンの値は、送信された操作に対応するサーバー上のリビジョンと等しくなります。 また、LOp1 'はクライアントのローカル操作のリストから削除されます。これは、サーバー上にもあるためです。

Local Operation 2で次に何が起こりますか？

「ローカル操作2で次に何が起こるのですか？」とあなたは尋ねます。 上記のすべては、最初のローカル操作で機能します。 秒に何が起こるか見てみましょう。 クライアントがローカル操作2を追加するとすぐに、サーバーにすぐに送信すると想像してください。 同時に、これらの操作の間のサーバーでは、他のクライアントからの操作が「ウェッジ」する可能性があります。







サーバーでどの操作を使用するかを理解するには、次の問題を解決する必要があります。







理論の観点から、これを行うことを妨げるものは何もありません。 目的の操作を行うには、すでに述べた変換を何度も適用するだけで十分です。







すべての変換を指定しませんでした。そうしないと、回路が非常に大きくなります。 ただし、赤い矢印に対応する操作は空（同一）であることに注意してください。 これは、操作LOp2 'がサーバーに適用する必要がある変更であることを意味します。



これらの計算を実際的な観点から見てみましょう。 これらの変換を実行するには、サーバーで以下を行う必要があります。

1. チャートが始まるリビジョンを知る。 操作と一緒に基本的なリビジョンを送信できるため、これは難しくありません。
2. このクライアントの以前のローカル操作に関する情報を持っています。 上の図では、これはLOp1ですが、一般的な場合、それらの数はいくつでもかまいません。 さらに、LOp2の送信時にこれらの操作の状態を保持することが重要です。これは、操作がサーバーから行われるとローカル操作が変換され、変更につながる可能性があることが上で示されたためです。

「クライアントの以前のローカル操作に関する情報がある」という条件は、以前のすべてのローカル操作をLOp2と共に送信するか、サーバー上の変換を使用してそれらを復元する必要があることを意味します。 サーバー上の履歴でこのクライアントからの操作を使用することはできません。既に変換が行われているためです。 前者の場合、ネットワークトラフィックが大幅に増加し、後者の場合、サーバーの負荷が増加します。



Google Docs and Waveで使用されるアルゴリズムは、2つの悪から選択できるシンプルで効果的なソリューションを使用しています。 これは、前の操作がサーバーに正常に適用されたことの確認が受信されるまで、次のローカル操作を送信しないという考え方です。 私たちの場合、これは、LOp1に関する確認メッセージをサーバーから受信した後にのみLOp2が送信されることを意味します。







同じアプローチが使用されています。

まとめ

これらのルールが「ライブ」でどのように機能するかは、スライドで確認できます。

編集をキャンセル（元に戻す）

共同編集の可能性により、ユーザーのアクションを取り消すなど、このようなありふれた機能が非常に具体的になります。 これがユーザー側でどのように見えるかを見てください。



ドキュメントのさまざまな部分を編集する2人の人がいるとします。 そのうちの1人が最後の変更を好まなかったため、キャンセルボタンを押しました。 システムがローカルテキストエディターと同じように機能する場合、つまり、すべての編集の履歴から最後の変更をロールバックすると、別のユーザーの操作がキャンセルされる可能性があります。 この場合、両方が混同されます。

• キャンセルを開始したユーザーには、期待される結果が表示されません。
• 彼の同僚は突然彼のテキストを削除します。 さて、またはリモートが表示されます。

これは、時間内の最後の操作ではなく、キャンセルを開始したユーザーの最後の操作をキャンセルすることが適切であることを意味します。 この場合、効果はより期待され、通常の効果に近くなります。これは、ローカルドキュメントを編集するときに確認できます。 したがって、各ユーザーは独自の元に戻す/やり直しスタックを持っています。



ただし、クライアント操作の履歴では、後者はサーバーから受け取った別のユーザーからの操作である場合があります。 このため、ローカルドキュメントを編集するときに使用される、やり直しを元に戻す方法を適用できなくなります。キャンセルすると、一番上のドキュメントがスタックから取得され、ロールバックされます。 この場合、何らかの方法で操作を履歴の「中間」から抽出し、次のすべてを変換する必要があります。







使用するアルゴリズムの重要な特性は、サーバーと既に調整されている操作が変更されないことです。 また、このプロパティに違反すると、アルゴリズムは機能しなくなります。 したがって、このようなキャンセルの原則は私たちには適していません。



すでに歴史の奥底に突入している操作（ドキュメント操作のスタック）をロールバックする必要があります。 このために、1つの方法があります。新しい操作を作成し、元の効果をキャンセルします。 各操作について、反対の結果を生成できると想定しています。 逆の操作は、最初の操作の直後に発生するドキュメントの状態にのみ正しく適用できることが重要です。







変換の助けを借りて、以前の編集で行ったように、クライアント上のドキュメントの現在の状態に逆の操作を「転送」できます。







ダイアグラム（Op ^-1 ） 'では、これは必要な操作です。 既存のアルゴリズムを変更する必要はありません。操作はローカルに適用され、他のサーバーと同様にサーバーに送信されます。 サーバーも他のクライアントも、元に戻す操作と通常の操作を区別できません。 これはキャンセル操作であるという情報は、それを作成したユーザーによってのみ保存されます。これは、REDOが正しく機能するために必要なためです。

練習する

理論的には、理論と実践の間に違いはありません。

しかし、実際にはあります。

ヨハネス・ランベルトゥス・アドリアーナ・ファン・デ・スネプシュート



現時点では、操作をキャンセルする機能を備えたノンブロッキング同時編集を可能にするアルゴリズムがすでにあります。 この段階では、ほとんどの理論的な記事で、アルゴリズムを構築するタスクは解決されていると想定されています。 1行の編集の例は、「テストサイト」として使用されます。ここでは、編集操作は2つだけです。つまり、文字の挿入と削除です。 シンボルに何らかのプロパティがあり、それに応じて3番目の操作がその値を変更するように見える例を示します。 オペレーションの総数を言及するだけではありません。なぜなら、オペレーションを他のオペレーションと比較して変換できる必要があるからです。つまり、Nオペレーションの場合、N ²変換を実装する必要があります。 操作が2つまたは3つである場合、これは問題ではありません。



これまで、当社製品のカーネルインターフェイスには、ドキュメントを編集するための50以上の機能が含まれています。 それぞれを個別の操作として提示する場合、2500を超える変換を実装およびテストする必要がありますが、これは単に物理的に不可能です。 さらに、新しい機能を常に追加しているため、この数は増え続けています。



この場合の自然な解決策は、ユーザーのアクションと操作の間の1対1の対応を放棄することです。 一連の操作は最小限にする必要がありますが、一連の操作の助けを借りて、任意のユーザーアクションを記述できるようになります。 さらに、可能な限り操作の数を制限したい場合、操作自体はユニバーサルでなければなりません。 事実、変換の観点からは、フォントの色やサイズを設定する操作に違いはありません。 文字の挿入と段落の挿入に違いがないように、これはすべて1次元のコレクションに貼り付けられます。 その結果、要素の挿入、オブジェクトのプロパティの削除および設定という3つの根本的に異なる操作が残っていることがわかりました。



CoWordなどの製品は、文書全体をさまざまな種類の要素（文字、キャリッジ翻訳、写真など）の連続したリストとして表します。 そして、そのようなドキュメントモデルの場合、提案された3つの操作で十分です。 しかし問題は、このモデルでは、スタイル、ヘッダー、フッター、およびテーブルを含むオフィスドキュメントを完全に表示できないことです。

木のような文書

リストの代わりに、ドキュメントをその階層構造を反映したツリーと考えるのが自然です。 簡単に言えば、このモデルのドキュメントは次のようになります。







スキームを簡素化するために、意図的に要素タイプの数を減らしましたが、意味は残りました。 ドキュメントは、2つのタイプのノードを持つツリーの形式で表示されます。

1. 固定構造ノードは緑色でマークされています。 例として、ルート要素を取り上げます。 このモデル内のドキュメントには、常に2つの子ノードがあります。ブロックのリストとプロパティのセットです。
2. 可変数の子ノードを含む可能性のあるコレクションノードは、紫色でマークされています。 たとえば、ドキュメント内のブロック（段落または表）には異なる番号が付いている場合があります。 同様に、段落の文字と表の行と列について。

このようなドキュメントモデルを使用すると、同じ3つの基本的な操作を使用できます：プロパティの挿入、削除、および設定。 同時に、それが実行されるドキュメントツリーのノードアドレスが各操作に追加されます。 挿入または削除操作の場合、これはコレクションのアドレスである必要があります;プロパティを設定する場合、これはこのプロパティを変更するノードのアドレスです。

ツリー操作の変換

オペレーションのアドレスは、変革に役立ちます。 （Operation1、address1）と（Operation2、address2）の2つの操作があるとします。 ノードが保持されているノードの相対位置がInc（（Operation1、address1）、（Operation2、address2））の値にどのように影響するかを判断しましょう。 4つの異なるケースがあります。



1.ノードが一致、address1 = address2。





。

この場合、変換はドキュメントがフラットであるかのように行われます。 アドレスは同じままです：



Inc（（Operation1、address1）、（Operation2、address2））=（Inc（Operation1、Operation2）、address1）



2. Operation2はノードOperation1の祖先に作用し、address2はプレフィックスaddress1です。







Operation2がノードOperation1の祖先を削除すると、結果として空の操作が取得されます。 削除しない場合、Operation1自体は変更されませんが、Operation2がコレクションを変更するとアドレスが変更される場合があります。 たとえば、Operation1が2番目の段落への文字の挿入であり、Operation2が最初の段落の削除である場合、結果として、同じインデックスを持つ文字が最初の段落に挿入されます。



Inc（（Operation1、address1）、（Operation2、address2））=（Operation1、Inc（address1、Operation2））



3. Operation1はノードOperation2の祖先に作用し、address1はプレフィックスaddress2です。







この場合、Operation2はOperation1に影響しません。



Inc（（Operation1、address1）、（Operation2、address2））=（Operation1、address1）



4. Operation1とOperation2はさまざまなノードで動作しますが、いずれも他のノードの祖先ではありません。







ここでも、変換は同じです：



Inc（（Operation1、address1）、（Operation2、address2））=（Operation1、address1）



これらのルールにより、任意のペアの操作の変換を取得できます。 さらに、ドキュメントのさまざまな部分に対する操作は変換されないため、生産性にプラスの影響があります。

二次元コレクション

それとは別に、テーブルに言及する価値があります。 著者が階層的なドキュメントでOTをレビューするいくつかの出版物に出会いました。 ただし、リストは常にコレクションノードとして使用されています。 テーブルに関しては、それらは常にセルのリストである行または列のリストとして指定できると言われていました。 このアプローチは、行の操作と列の操作を正しく相互に変換できないため、根本的に間違っています。 そして今、その理由をお話しします。



行のリストの形式で2行2列のテーブルを格納するとします。







1人のユーザーがテーブルの最後に行を挿入し、2人目のユーザーが右側の列を並行して削除するとします。 最初のユーザーの場合、彼のアクションは、挿入（Table、3、{Cell31、Cell32}）という1つの操作で記述されます。 2番目の操作には、削除（Row1、2）、削除（Row2、2）の2つの操作が必要です。 上記のすべての変換ルールを適用すると、結果としてこのテーブルの状態が取得されます。







あまり長方形ではないテーブルを認めるか、別のアプローチを見つけます。 2番目のオプションを選択しました。 より正確には、テーブルを別個の2次元タイプのコレクションとして提示しました。 リストとは対照的に、それらに対する操作は2つではなく4つです。つまり、列の挿入と削除、および行の同様の操作です。 そして、子要素のアドレス-セル-は、単一の数値インデックスではなく、ペアによって設定されます。 このアプローチにより、行と列の操作を正しく表現および変換し、誤ったテーブル構造の状況を防ぐことができます。

おわりに

これについて私は呼んで、これがすべてであると書きたいです。 OTの場合、「詳細の悪魔」というフレーズは非常に正確です。なぜなら、基本的な問題を解決し、アルゴリズムを複雑にする必要性が実際にあるからです。 したがって、リスト操作の実際のアルゴリズムでは、2つではなく4つがあります。 そして、そのうちの1つは実行されません。 また、変換中だけでなく、実行時にも操作を変更できます。



この記事のすべてのニュアンスをカバーすることはもはや不可能であり、それらを継続するために残し、この2番目の記事を終了します。



じゃあね！