同步两个有序列表

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字符串排序顺序是正确的。