同步两个有序列表

Question

同步两个有序列表

algorithmdata-structuressynchronizationlinked-listhtml-lists

8

我们有两个离线系统，它们通常无法相互通信。这两个系统都维护着同一个有序项目列表。它们只有在极少数情况下才能相互通信以同步该列表。

为了检测编辑，项目标记有修改时间戳。为避免在插入新项目时发生冲突（而不是使用自增整数），项目由UUID进行标识。在同步时，会检测到新的UUID并将其复制到另一个系统中。删除也是如此。

上述数据结构对于无序列表来说是可以的，但是如何处理排序呢？如果我们添加一个整数“rank”，那么在插入新项目时就需要重新编号（因此需要由于仅插入1个项目而同步所有后续项目）。或者，我们可以使用分数排名（使用前任和后继项目的排名平均值），但这似乎不是一个稳健的解决方案，因为当许多新项目被插入时，它很快就会遇到精度问题。

我们还考虑将其实现为双向链表，每个项目都持有其前任和后继项目的UUID。然而，当插入1个新项目时，仍需要同步3个项目（或在删除1个项目时同步2个剩余项目）。

最好的情况是，我们想使用一种数据结构或算法，只需要同步新插入的项目。是否存在这样的数据结构？

编辑：我们还需要能够处理将现有项目移动到不同的位置！

- Jason Smith

如果在两个系统中都有 {a, b, c}，并且系统 A 插入 p 以获得 {a, b, p, c}，系统 B 插入 p 以获得 {a, p, b, c}，当您同步时，您希望最终得到什么顺序？ - Geoff

@Geoff，由于我们使用随机UUID，出现两个“p”的几率几乎为零。 - Jason Smith

抱歉，你是对的。我真正想问的是如何处理排序中的冲突。在我更改之前，我写道：如果两个系统都有 {a, b, c}，并且系统 A 插入 p 以获得 {a, b, p, c}，系统 B 插入 q 以获得 {a, b, q, c}，当你同步时，你希望 p 和 q 的顺序是什么？ - Geoff

在这种情况下，只要两个系统同意相同的顺序，p和q的任何顺序都是可以接受的，显然。 - Jason Smith

7个回答

3

您可以为每个项目添加两个字段：“创建时间戳”和“插入后”（包含新项目插入的项目ID）。同步列表后，发送所有新项目。这些信息足以让您能够在另一端上构建列表。

收到新添加项目的列表后，请按创建时间戳排序，然后逐一进行，并使用“插入后”字段将新项目添加到适当的位置。

如果添加了项目A，然后在A之后添加了B，然后删除了A，则可能会遇到麻烦。如果发生这种情况，您还需要同步A（基本上是同步自上次同步以来对列表执行的操作，而不仅仅是当前列表的内容）。这基本上是一种日志传送形式。

- zmbq

1

你会如何处理将现有项目移动到列表中的不同位置？你会（滥）使用创建时间戳还是对修改时间戳进行某些操作来完成？ - Jason Smith

我很好奇你最终选择了什么解决方案，Jason。（在SO上，你可以回答自己的问题。） - Ryan Norbauer

1

我认为，广义上来说操作转换可能与您在此描述的问题有关。例如，考虑实时协作文本编辑的问题。

我们基本上有一个需要保持同步的已排序项目（单词）列表，这个列表中的项目可以随机添加/修改/删除。我唯一看到的主要区别在于对列表的修改的周期性。（您说它不经常发生）

操作转换是一个被广泛研究的领域。我找到了一篇博客文章，介绍了一些指南和概述。此外，尽管Google Wave存在很多问题，但他们在操作转换领域确实取得了重大进展。请看这里。关于这个主题有很多文献可供参考。可以查看stackoverflow线程和差分同步。

另一个引起我注意的相似之处是文本编辑器中使用的数据结构 - Ropes。因此，如果您有一系列操作记录，比如“删除索引5”，“将索引6修改为ABC”，“插入索引8”，现在您可能需要将更改日志从系统A传输到系统B，然后在另一侧按顺序重建操作。

另一位“务实工程师”的选择可能是在系统A更改时简单地在系统B上重新构建整个列表。根据实际更改的频率和大小，这可能并不像听起来那么糟糕。

- Arvind

1

我曾经通过在每个条目上包含一个PrecedingItemID（如果该项是有序列表的顶部/根，则可以为空）来解决类似问题，并且具有一种本地缓存的排序方式，以保持所有按排序顺序排列的项目列表（这纯粹是为了效率——因此您不必每次在本地客户端重新查询或基于PrecedingItemID构建列表时进行递归）。然后，当同步时间到来时，我会执行稍微昂贵的操作，查找两个项目请求相同的PrecedingItemID的情况。在这些情况下，我只需按创建时间（或者您想要协调哪个获胜并首先出现）排序，将第二个（或其他）放在其后面，然后继续对列表进行排序。然后，我将这个新的排序存储在本地排序缓存中，并继续使用它直到下一次同步（只需确保在进行操作时保持PrecedingItemID更新即可）。

我还没有单元测试这种方法-所以我不能确定是否存在某些问题冲突的情况-但至少在概念上处理我的需求，这听起来与OP的需求类似。

- Ryan Norbauer

1

我认为这里适合使用的数据结构是顺序统计树。在顺序统计树中，您还需要维护子树大小以及其他数据，大小字段可以帮助您轻松找到所需的排名元素。所有操作（如排名、删除、更改位置、插入）的时间复杂度均为O(logn)。

- Vikram Bhat

1

你可以了解一下“镜头”（lenses）这个双向编程的概念。例如，你的问题似乎可以通过“匹配镜头”来解决，该镜头在this paper中有所描述。

- esope

1

我非常乐意接受这个，但所有的集合符号对我来说都是无意义的。你知道有没有更易于理解的工程、实践或行业视角下的透镜讨论？不幸的是，他们选择了一个非常常见且模糊的术语作为他们的编程概念，所以很难在谷歌上搜索到相关信息。 - Ryan Norbauer

1

我认为你可以在这里尝试一种事务性方法。例如，您不会物理删除项目，而是将它们标记为删除，并仅在同步期间提交更改。我不确定您应该选择哪种数据类型，这取决于您想要更加高效的操作（插入、删除、搜索或迭代）。

让我们看看两个系统的初始状态：

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

在此之后，第一个系统标记删除元素A，而第二个系统将元素BC插入到B和C之间。

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

两个系统都会继续处理，考虑到本地的更改。系统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       |

系统唤醒并继续处理。

项按插入顺序排序，移动可以实现同时删除和插入。我认为可能不需要传输整个列表快照，而只需要传输实际修改的项目列表。

- Ilya Tsyplenkov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gene · Accepted Answer

插值排名方法没有任何问题。只需基于变长位向量定义自己的编号系统，表示介于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的位字符串类型似乎足够描述我所描述的键。我需要验证的事情是排序顺序是否正确。

同样的推理对于任何k>=2的基数k的数字也适用。第一项的键为k/2。还有一个简单的优化，可以防止在末尾和前面添加和预置元素的常见情况导致O(n)长度的键。对于这些情况，它保持O(log n)（尽管在内部插入到相同位置仍可能产生O(p)键，其中p是插入次数）。我会让您自己解决。使用k=256，您可以使用无限长度的字节字符串。在SQL中，我认为您需要varbinary(max)。SQL提供正确的词典顺序。如果您有类似于Java的BigInteger包，那么实现插值运算很容易。如果您喜欢人类可读的数据，则可以将字节字符串转换为例如十六进制字符串（0-9a-f）并存储这些字符串。然后正常的UTF8字符串排序顺序就是正确的。