是否有校验和算法也支持从中“减去”数据？

Question

我有一个大约有1亿个文档的系统，我想跟踪它们在镜像之间的修改。为了有效地交换有关修改的信息，我希望按天而不是每个单独的文档发送有关修改文档的信息。像这样的东西：

[ 2012/03/26, cs26],
[ 2012/03/25, cs25],
[ 2012/03/24, cs24],
...

其中每个cs是特定日期创建的所有文档的时间戳的校验和。

现在，我遇到的问题是我不知道在删除文档时可以从校验和中“减去”数据的算法。由于显而易见的原因，没有一个加密哈希符合需要，我找不到任何能够做到这一点的CRC算法。

我考虑的一个选项是删除向哈希添加额外信息，但这会导致更多问题，因为节点可以以不同顺序接收删除请求，并且当节点重新启动时，它将重新读取所有时间戳。文档，因此有关删除的信息将丢失。

我也不喜欢在内存中使用带有所有文档哈希的哈希树，因为这将使用大约8演出的内存，我认为这对于这种需求来说有点过分。

目前最好的选择似乎是在后台完全不时地重新生成这些哈希值，但这也是很多不必要的开销，并且不会提供有关更改的即时信息。

那么，你们知道校验和算法会让我从校验和中“删除”一些数据吗？我需要算法有点快，校验和强烈表明最小的变化（这就是我不能真正使用普通XOR的原因）。

或许你对整个设计有更好的想法？

Answer 1

怎么样

hash = X(documents, 0, function(document) { ... })

其中X是聚合XOR（跟随javascript-y伪代码）：

function X(documents, x, f)
{
   for each (var document in documents)
   {
      x ^= f(document);
   }
   return x;
}

和f（）是单个文档信息的哈希？ （无论是时间戳，文件名或ID还是其他）

使用XOR将允许您“减去”文档，但是在每个文档的基础上使用哈希允许您保持检测小变化的类似哈希的质量。