3

我想要一个单一类型的项目的主要集合，随着时间的推移对其进行修改。周期性地，几个从属集合将与主集合同步。主集合应该将项目的增量发送到从集合。

Primary Collection: A, C, D
Slave Collection 1: A, C    (add D)
Slave Collection 2: A, B    (add C, D; remove B)

从属集合不能自己添加或删除项目，它们可能存在于不同的进程中，所以我可能会使用管道来推送数据。

我不想推送比必要更多的数据，因为集合可能会变得非常大。

什么样的数据结构和策略最适合这个？

4

2 回答 2

1
  • 如果不推送所有数据，则需要某种日志，而不是使用管道带宽，而是使用主内存。在 CPU 和内存使用之间找到良好平衡的参数将是“推送”频率。
  • 根据您的问题，我假设您有多个从属进程。在这种情况下，一些在主进程中具有双缓冲的共享内存或CMA (Linux) 方法应该远远优于多个管道，因为它甚至不需要多线程推送，这将用于优化同步期间的整体管道吞吐量。
    从属进程可以使用全局同步屏障来通知从 masterCollectionA 读取而不复制，而 master 修改 masterCollectionB（使用来自 masterCollectionA 的副本初始化），反之亦然。对集合的访问应该在从属和主控之间互锁。从属服务器可以复制该集合（快照），如果他们阻止它超过来自主服务器的下一次更新尝试，从而允许它继续。从属进程中的修改可以通过单个元素的写入时复制策略来实现。这种协作方式实现起来相当简单，并且如果从属进程不每次都复制整个快照，则整体内存消耗很低。
于 2013-11-16T15:26:51.910 回答
1

为此，我使用差异执行。

（顺便说一句，“奴隶”这个词对某些人来说是有道理的。）

对于每个远程站点，主站点都有一个顺序文件，表示远程站点上存在的内容。

主站点有一个遍历主集合的过程，当它遍历时，它会读取相应的文件，检测远程站点上当前存在的内容与应该存在的内容之间的差异。这些差异会产生增量，并将其传输到远程站点。同时，该过程写入一个新文件，表示处理增量后远程站点将存在的内容。

这样做的好处是它不依赖于检测主集合中的更改事件，因为这些更改事件通常是不可靠的，或者可以自行取消或与其他更改无关，因此您可以减少到远程站点的不必要传输.

在集合是简单的事物列表的情况下，这归结为拥有远程集合的本地副本并运行diff算法来获取增量。这里有几个这样的算法：

如果可以对集合进行排序（例如您的 A、B、C 示例），只需运行合并循环：

while(ix<nx && iy<ny){
  if (X[ix] < Y[iy]){
    // X[ix] was inserted in X
    ix++;
  } else if (Y[iy] < X[ix]){
    // Y[iy] was deleted from X
    iy++;
  } else {
    // the two elements are equal. skip them both;
    ix++; iy++;
  }
}
while(ix<nx){
  // X[ix] was inserted in X
  ix++;
}
while(iy<ny>){
  // Y[iy] was deleted from X
  iy++;
}

如果无法对集合进行排序（注意与Levenshtein distance的关系），

Until we have read through both collections X and Y,
  See if the current items are equal

  else see if a single item was inserted in X
  else see if a single item was deleted from X

  else see if 2 items were inserted in X
  else see if a single item was replaced in X
  else see if 2 items were deleted from X

  else see if 3 items were inserted in X
  else see if 2 items in X replaced 1 items in Y
  else see if 1 items in X replaced 2 items in Y
  else see if 3 items were deleted from X

  etc. etc. up to some limit

性能通常不是问题，因为该过程不必以高频率运行。

有一个演示此概念的粗略视频，以及用于动态更改用户界面的源代码。

于 2013-11-16T15:27:11.007 回答