2009-02-21 57 views
1

这是客户端/服务器应用程序系统。同步条目顺序的算法

客户端应用程序可以进入脱机模式,有时会与服务器同步。 (比如GMail离线)

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

添加,编辑和删除条目的算法是微不足道的。服务器可以为每个新条目创建一个唯一的ID,客户端使用这些ID进行更新和删除。

新的要求是条目的排序。

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

  • x:DCBA: A(4),B(3),C(2),d(1)
  • Y:DCBA:A(4),B(3),C(2),d(1)

客户ÿ创建d和C

  • x与新条目E:DCBA: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:DECBA:A(5),B(4),C(3),d(1),E(2)
  • Y:DECBA:A(5),B(4) ,C(3),D(1),E(2)

如何同步这些订单信息?


*附加测试*

Cient X除去d和C,但客户端ÿ创建d和C之间新项E

  • X:BA:A(2) ,B(1)
  • Y:DECBA:A(5),B(4),C(3),d(1),E(2)

同步后。

  • X:CBA:A(5),B(4),C(3),d(1),E(2)
  • Y:CBA:A(5),B(4) ,C(3),d(1),E(2)

回答

0

你可能想看看如何FeedSync处理同步中涉及的这个问题(和其他几个人)。

0

唯一困难的部分是当一个条目被删除,对吧?你如何保持删除的条目在服务器上,但标记为已删除。一旦所有的客户端都与服务器同步,所以他们都不知道这个条目了,你可以从服务器永久删除它。

1

我相信你应该坚持SVN协议。您不应允许在没有同步(更新)的情况下提交,以查看是否发生了一些更改。

如果不这样做,那么存储数据的一致性(一致性)会有很大的问题。例如,您存储了D-C-B-A,并且客户端x和y已同步。

  • 客户端X除去C和A - > d - B
  • 客户Ž同步,他获得d - B和他d和B之间添加的F - > d - F - 乙
  • 同时客户ÿ增加了C和B E之间 - > d - C - é - B - 一个

现在,如果所有客户端都将同步你不能告诉其中F将被放置在数据序列:d - F - é - B或d - E - F - B。