同步条目顺序的算法

Question

这是客户端/服务器应用系统。

客户端应用程序可以进入离线模式，有时会与服务器同步。 (就像 GMail 离线)

多个客户端可以连接到服务器，因此每个客户端都可以添加、编辑和删除其条目并像 SVN 一样同步这些更改(可能会发生冲突，但不是问题。)

添加、编辑和删除条目的算法很简单。服务器可以为每个新条目创建一个唯一的 ID，客户端使用这些 ID 进行更新和删除。

新要求是条目的排序。

有两个客户端应用程序 - x,y。它们存储条目 - A、B、C 和 D。这些条目排列为 D-C-B-A，因此 A 的顺序属性为 4，B 为 3，C 为 2，D 为 1。

• x : D-C-B-A : A(4), B(3), C(2), D(1)
• y : D-C-B-A : A(4), B(3), C(2), D(1)

客户端y在D和C之间创建新条目E

• x : D-C-B-A : A(4), B(3), C(2), D(1)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

客户端与服务器同步后。

• x : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

如何同步这些订单信息？

---

* 附加测试 *

客户端 x 删除了 D 和 C，但客户端 y 在 D 和 C 之间创建了新条目 E。

• x : B-A : A(2), B(1)
• y : D-E-C-B-A : A(5), B(4), C(3), D(1), E(2)

同步后。

• x : C-B-A : A(5), B(4), C(3), D(1), E(2)
• y : C-B-A : A(5), B(4), C(3), D(1), E(2)

---

Answer 1

我认为您应该坚持使用 SVN 协议(protocol)。您不应允许在未同步(更新)以查看是否发生某些更改的情况下提交。

如果不这样做，存储数据的连贯性(一致性)就会出现大问题。例如，您存储了 D - C - B - A 并且客户端 x 和 y 是同步的。

• 客户 x 删除 C 和 A -> D - B
• 客户端 z 同步，他获得 D - B 并在 D 和 B 之间添加 F -> D - F - B
• 同时客户 y 在 C 和 B 之间添加 E -> D - C - E - B - A

现在，如果所有客户端都将同步，您将无法确定 F 将放在数据序列中的何处:D - F - E - B 或 D - E - F - B。