有支持从校验算法中“减去”数据的校验和算法吗？

Question

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

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

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

现在，我遇到的问题是我不知道是否有一种算法可以在删除文档时“减去”校验和中的数据。由于明显的原因，没有一个加密哈希函数适合这个需求，并且我找不到任何适用于CRC的算法可以做到这一点。

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

我也不想使用具有全部文档哈希值的哈希树存储在内存中，因为这将使用大约8 GB的内存，而我认为这对于仅此需求来说有些过度。

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

那么，你们知道是否有一种校验和算法可以让我“删除”校验和中的一些数据吗？我需要该算法快速一些，并且校验和能够强烈指示最小的更改（这就是为什么我不能使用简单的XOR）。

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

- Andrejs Krasilnikovs

---

我不明白。为什么你不能对所有校验和进行异或运算。如果有一个文档被删除，你可以对该文档的校验和进行异或运算，然后你就应该得到其余文件的校验和。 - aioobe

你每天有多少次修改？难道你不能对这些修改做一个校验和吗？ - biziclop

@aioobe 我并没有为特定文档保留单独的校验和，所以这个想法并没有出现在我的脑海中，但是，是的，这是一个好主意，本质上Jason S建议了同样的事情。 - Andrejs Krasilnikovs

不清楚你想要用这些校验和做什么。假设一个节点收到 [2012/03/26, cs26]……现在怎么办？ - n. m.

@n.m. 然后它将比较校验和，如果校验和不匹配，则请求该日期上文档及其时间戳的列表，然后获取时间戳不匹配的文档内容。 - Andrejs Krasilnikovs

Answer 1

如何？

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

X是一个聚合异或（以下是javascript-y伪代码）：

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

而f()则是单个文档信息的哈希值（无论是时间戳、文件名还是ID等）？

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

- Jason S

---

太棒了，而且做起来非常简单！ - Andrejs Krasilnikovs