同步兩個有序列表

Question

我們有兩個通常不能相互通信的離線系統。兩個系統都保持相同的有序物品清單。他們很少能夠互相溝通來同步列表。

項目標有修改時間戳以檢測編輯。項目由UUID標識以避免在插入新項目時發生衝突（與使用自動遞增整數相反）。同步檢測到新的UUID並將其複製到其他系統時。同樣對於刪除。

上面的數據結構適用於無序列表，但我們如何處理排序？如果我們添加了一個整數「等級」，那麼在插入一個新項目時需要重新編號（因爲只需要一次插入就需要同步所有後繼項目）。或者，我們可以使用小數排名（使用前任和後繼項目的平均排名），但這看起來不像一個強大的解決方案，因爲插入許多新項目時，它會很快出現準確性問題。

我們還考慮將其作爲一個雙重鏈接列表，每個項目都包含其前任和後繼項目的UUID。但是，當插入1個新項目時（或者在刪除1個項目時同步其餘2個項目），仍然需要同步3個項目。

優選地，我們希望使用只有新插入的項目需要同步的數據結構或算法。這樣的數據結構是否存在？

編輯：我們需要能夠處理將現有項目移動到不同的位置！

Answer 1

您可以爲每個項目添加兩個字段 - '創建時間戳'和'插在'之後（包含插入新項目之後的項目的ID）。一旦同步列表，發送所有新項目。這些信息足以讓您能夠在另一側構建列表。

使用收到的新增項目列表，執行以下操作（在接收端）：按創建時間戳排序，然後逐個添加，然後使用「插入後」字段將新項目添加到適當的位置。

如果添加了一個項目A，然後在A之後添加B，則A可能會被刪除，您可能會遇到麻煩。如果發生這種情況，您還需要同步A（基本上同步自上次同步以來發生在列表上的操作，而不僅僅是當前列表的內容）。這基本上是一種日誌傳送的形式。

Answer 2

你可以看看「鏡頭」，這是雙向編程的概念。 例如，您的問題似乎解決了我的「匹配鏡頭」，如this paper中所述。

Answer 3

我認爲這裏適合的數據結構是order statistic tree。爲了統計樹，您還需要維護子樹的大小以及其他數據，大小字段可幫助您輕鬆找到排名，因爲您需要它。所有的操作，如排名，刪除，更改位置，插入是O(logn)。

Answer 4

我想你可以在這裏嘗試一種交易方法。例如，您不要物理刪除項目，而是將它們標記爲刪除並僅在同步期間提交更改。我不是很確定你應該選擇哪種數據類型，這取決於你想要更高效的操作（插入，刪除，搜索或迭代）。

讓我們有兩個系統上的以下初始狀態：

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

此後第一系統標記元件A爲刪除和第二系統插入B和C之間元件BC：

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

這兩個系統繼續處理accou nt本地更改，系統1忽略元素B，系統2將元素BC視爲正常元素。

當同步發生時：

據我所知，每個系統從其它系統接收的列表中的快照和兩個系統凍結處理，直到同步將完成。

所以依次每個系統遍歷接收到的快照和本地列表和寫入切換到本地列表（解決根據修改的時戳可能衝突），經過「交易將提交」，所有的本地變化最終應用和關於它們的信息擦除。 例如對於系統之一：

|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  | 

系統喚醒並繼續處理。

項目按插入順序排序，移動可以實現爲同時刪除和插入。此外，我認爲可以不傳輸整個列表shapshot，而只是列出實際修改的項目。

Answer 5

我認爲，廣義上說，Operational Transformation可能與您在此處描述的問題有關。例如，考慮實時協作文本編輯的問題。

我們基本上有一個項目（單詞）的排序列表，需要保持同步，並且可以在列表中隨機添加/修改/刪除。我看到的唯一的主要區別在於列表的修改週期（​​你說它不經常發生）

操作轉換的確發生了很好的研究領域。我可以找到this blog article指點和介紹。此外，對於Google Wave所遇到的所有問題，他們實際上在運營轉型領域取得了重大進展。檢查this out.。關於這個問題有相當多的文獻可以提供。看看這stackoverflow thread，和約Differential Synchronisation

另一個並行打擊我是文本編輯器中使用的數據結構 - Ropes。 所以，如果你有一個操作日誌，可以說，「索引5刪除」，「索引6修改爲ABC」，「索引8插入」，你現在可能要做的就是從系統A到系統B，然後在另一側順序重建操作。

另一個「實用工程師」的選擇將是當系統A改變時簡單地重建系統B上的整個列表。根據變化的實際頻率和大小，這可能不像聽起來那麼糟糕。

Answer 6

我試圖通過在每個項目中包含一個PrecedingItemID（如果項目是有序列表的頂部/根，可以爲空），然後有一種本地緩存保存列表所有項目按排序順序排列（這純粹是爲了提高效率 - 所以您無需每次在本地客戶端進行重新排序時都基於PrecedingItemID遞歸查詢或構建列表）。然後，當需要同步時，我會執行稍微更昂貴的操作來查找兩個項目請求相同的PrecedingItemID的情況。在這些情況下，我只需按創建時間排序（或者您想調和哪一個贏得和先來），將第二個（或其他）放在它後面，然後繼續排列列表。然後，我將這個新的順序存儲在本地順序緩存中，並繼續使用它，直到下一次同步（只要確保隨時更新PrecedingItemID即可）。

我還沒有單元測試過這種方法，所以我不是100％肯定我不會錯過一些有問題的衝突場景 - 但它似乎至少在概念上處理了我的需求，這聽起來類似於那些OP。

Answer 7

插值秩方法確實沒有問題。只需定義您自己的編號系統，該編碼系統基於可變長度的位向量，表示0到1之間的二進制分數，不含尾隨零。二進制點位於第一位數字的左側。

該系統的唯一不便之處在於空位向量給出的最小可能密鑰爲0。因此，只有在您肯定的情況下，您纔會使用它，相關的項目將永遠是第一個列表元素。通常情況下，只給第一項爲鍵1.這相當於1/2，因此在範圍（0..1）中的隨機插入將傾向於最小化比特的使用。之前和之後插一個項目，

01 < newly interpolated = 1/4 
1 
11 < newly interpolated = 3/4 

要再次插：

001 < newly interpolated = 1/8 
01 
011 < newly interpolated = 3/8 
1 
101 < newly interpolated = 5/8 
11 
111 < newly interpolated = 7/8 

請注意，如果你願意，你可以省略存儲最後1！所有密鑰（除非你通常使用的0除外）都以1結尾，因此存儲它是非常有用的。

比較二進制分數很像詞法比較：0 < 1，並且從左到右掃描的第一個位差告訴你哪個更小。如果沒有差異發生，即一個矢量是另一個矢量的嚴格前綴，則較短的那個更小。

有了這些規則，想出一個算法來接受兩個位向量並計算一個大致（或在某些情況下）在它們之間的結果是非常簡單的。只需添加位串，然後右移1，丟棄不必要的尾位，即取兩者的平均值來分割它們之間的範圍。

在上面的例子中，如果缺失已經給我們留下了：

01 
111 

，我們需要插這些，加上01(0)和和111獲得1.001，然後轉移到獲得1001。這可以很好地作爲插值。但是請注意，最後的1不必要地使其長於任一操作數。一個簡單的優化是放棄最後的1位以及尾隨零來獲得簡單的1。果然，1大概是我們希望的一半。

當然，如果您在同一位置執行多次插入操作（例如，想像列表開始處的連續插入操作），位向量將變長。這與在二叉樹中的相同點處插入完全相同。它長得很長，很纖細。爲了解決這個問題，你必須在同步期間通過用最短可能的位向量重新編號來「重新平衡」，例如，對於14你會使用上面的序列。

加成

雖然我還沒有嘗試過，Postgres的bit string type似乎足以爲我所描述的鑰匙。我需要驗證的是整理順序是正確的。

此外，對於任何k>=2，同樣的推理可以很好地處理base-k數字。第一項獲得鑰匙k/2。還有一個簡單的優化，可以防止常見的在末端和前端添加和預先添加元素的情況，導致長度爲O（n）的鍵。它爲這些情況維護O（log n）（儘管在內部插入相同的地方仍然可以在p插入後生成O（p）鍵）。我會讓你解決這個問題。 k = 256時，可以使用無限長度的字節字符串。在SQL中，我相信你會想要varbinary(max)。 SQL提供正確的詞典排序順序。如果你有一個類似於Java的BigInteger包，插值操作的實現很容易。如果您喜歡可讀的數據，則可以將字節字符串轉換爲十六進制字符串（0-9a-f）並存儲它們。然後正常的UTF8字符串排序順序是正確的。