algorithm - 2 つの順序付きリストを同期する

Question

通常は相互に通信できない 2 つのオフライン システムがあります。両方のシステムは、アイテムの同じ順序付きリストを維持します。リストを同期するために相互に通信できることはめったにありません。

編集を検出するために、アイテムには変更のタイムスタンプが付けられます。(自動インクリメント整数を使用するのではなく) 新しいアイテムを挿入するときの競合を避けるために、アイテムは UUID によって識別されます。同期すると、新しい UUID が検出され、他のシステムにコピーされます。削除についても同様です。

上記のデータ構造は、順序付けされていないリストには問題ありませんが、順序付けをどのように処理できますか? 整数の「ランク」を追加した場合、新しいアイテムを挿入するときに番号を付け直す必要があります (したがって、1 つの挿入だけのために後続のすべてのアイテムを同期する必要があります)。別の方法として、分数ランク (先行アイテムと後続アイテムのランクの平均を使用) を使用することもできますが、多くの新しいアイテムが挿入されるとすぐに精度の問題が発生するため、これは堅牢なソリューションとは思えません。

また、これを、各アイテムがその先行アイテムと後続アイテムの UUID を保持する二重リンク リストとして実装することも検討しました。ただし、1 つの新しいアイテムが挿入されたときに 3 つのアイテムを同期する必要があります (または、1 つのアイテムが削除されたときに残りの 2 つのアイテムを同期する)。

できれば、新しく挿入されたアイテムのみを同期する必要があるデータ構造またはアルゴリズムを使用したいと考えています。そのようなデータ構造は存在しますか？

編集: 既存のアイテムを別の位置に移動することも処理できる必要があります!

Answer 1

各アイテムに 2 つのフィールドを追加できます - 「作成タイムスタンプ」と「挿入後」(新しいアイテムが挿入された後のアイテムの ID を含む)。リストを同期したら、すべての新しいアイテムを送信します。その情報は、反対側でリストを作成するのに十分です。

新しく追加されたアイテムのリストを受け取ったら、これを行います (受信側で): 作成タイムスタンプで並べ替え、1 つずつ移動し、「後に挿入」フィールドを使用して新しいアイテムを適切な場所に追加します。

アイテム A が追加され、B が A の後に追加され、その後 A が削除されると、問題が発生する可能性があります。これが発生する可能性がある場合は、A も同期する必要があります (基本的には、現在のリストの内容だけでなく、最後の同期以降にリストで行われた操作を同期します)。これは基本的にログ配布の形式です。

Answer 2

ここで適切なデータ構造はorder statistic treeだと思います。統計ツリーを作成するには、他のデータとともにサブツリーのサイズも維持する必要があります。サイズ フィールドを使用すると、必要に応じてランクごとに要素を簡単に見つけることができます。ランク付け、削除、位置変更、挿入などのすべての操作はO(logn).

Answer 3

ここで一種のトランザクションアプローチを試すことができると思います。たとえば、項目を物理的に削除するのではなく、削除のマークを付け、同期中にのみ変更をコミットします。どのデータ型を選択すればよいか、はっきりとはわかりません。より生産的にしたい操作 (挿入、削除、検索、反復) によって異なります。

両方のシステムで次の初期状態があるとします。

|1|   |2|
---   ---
|A|   |A|
|B|   |B|
|C|   |C|
|D|   |D|

その後、最初のシステムは要素Aに削除のマークを付け、2 番目のシステムは と のBC間Bに要素を挿入しCます。

|1         |   |2           |
------------   --------------
|A         |   |A           |
|B[deleted]|   |B           |
|C         |   |BC[inserted]|
|D         |   |C           |
               |D           |

どちらのシステムも、ローカルの変更を考慮して処理を続行します。システム 1 は要素を無視しB、システム 2 は要素BCを通常の要素として扱います。

同期が発生すると:

私が理解しているように、各システムは他のシステムからリストのスナップショットを受け取り、同期が完了するまで両方のシステムが処理をフリーズします。

そのため、各システムは、受信したスナップショットとローカル リストを順次反復し、「トランザクションがコミットされた」後、ローカル リストに変更を書き込み (変更されたタイムスタンプに従って競合の可能性を解決します)、すべてのローカル変更が最終的に適用され、それらに関する情報が消去されます。たとえば、システム 1 の場合:

|1 pre-sync|             |2-SNAPSHOT  |   |1 result|
------------             --------------   ----------
|A         | <the same>  |A           |   |A       |
|B[deleted]| <delete B>  |B           |
             <insert BC> |BC[inserted]|   |BC      |
|C         | <same>      |C           |   |C       |
|D         | <same>      |D           |   |D       |

システムが起動し、処理を続行します。

アイテムは挿入順でソートされ、移動は同時削除と挿入として実装できます。また、リスト全体のスナップショットではなく、実際に変更されたアイテムのリストのみを転送することも可能だと思います。

Answer 4

PrecedingItemID各アイテムに a (アイテムが順序付きリストのトップ/ルートである場合は null になる可能性があります) を含め、すべてのアイテムのリストを並べ替えた順序で保持する一種のローカル キャッシュを用意することで、同様の問題を暫定的に解決しました。(これは純粋に効率のためです。そのため、再帰的にクエリを実行したり、リストに基づいてリストを作成したりする必要はありません。PrecedingItemIDs ローカル クライアントで再注文があるたびに)。次に、同期するときが来たら、2 つのアイテムが同じ PrecedingItemID を要求しているケースを探すという、少しコストのかかる操作を行います。そのような場合、私は単に作成時間で並べ替え (または、どちらが優先されて最初に来るかを調整したい場合)、2 番目 (またはその他) をその後ろに置き、リストの順序付けに進みます。次に、この新しい順序付けをローカルの順序付けキャッシュに保存し、次の同期までそれを使用し続けます (常にPrecedingItemID最新の状態を維持するようにします)。

このアプローチの単体テストはまだ行っていないため、問題のある競合シナリオを見逃していないことを 100% 確信しているわけではありませんが、少なくとも概念的には、OP のニーズに似た私のニーズを処理しているように見えます。

Answer 5

双方向プログラミングの概念である「レンズ」を見ることができます。たとえば、あなたの問題は、この論文で説明されている「マッチングレンズ」で解決されたようです。

Answer 6

大まかに言えば、運用の変革は、ここで説明している問題に関連している可能性があると思います。たとえば、リアルタイムの共同テキスト編集の問題を考えてみましょう。

基本的に、同期を維持する必要があり、リスト内でランダムに追加/変更/削除できるアイテム（単語）のソート済みリストがあります。私が見る唯一の大きな違いは、リストへの変更の周期性にあります.(頻繁には起こらないとあなたは言います)

運用の変革はたまたまよく研究されている分野です。このブログ記事で、ポインターと紹介を見つけることができました。さらに、Google Wave にはさまざまな問題がありましたが、実際には運用上の変革の分野で大きな進歩を遂げました。これをチェックしてください。. このテーマについてはかなりの数の文献が利用可能です。このstackoverflowスレッドを見て、差分同期について

私を驚かせたもう 1 つの類似点は、Text Editors - Ropesで使用されるデータ構造です。したがって、「インデックス 5 を削除した」、「インデックス 6 を ABC に変更した」、「インデックス 8 を挿入した」などの操作のログがある場合、システム A から変更のログを送信する必要があります。システム B に送信し、反対側で操作を順番に再構築します。

もう 1 つの「実用的なエンジニア」の選択は、システム A が変更されたときにシステム B のリスト全体を単純に再構築することです。変更の実際の頻度とサイズによっては、これは思ったほど悪くはないかもしれません。