是否有一个校验和算法也支持“减量”数据？

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的-γ的伪代码如下所示）：

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

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

XOR的使用将允许您“减掉”文档，但在每个文档的基础上使用散列可以保留类似散列的质量变化。