是否有一种校验和算法也支持“减法”运算。数据呢？ [英] Is there a checksum algorithm that also supports "subtracting" data from it?

问题描述

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

I have a system with roughly a 100 million documents, and I'd like to keep track of their modifications between mirrors. In order to exchange information about modifications effectively, I want to send information about modified documents by days, not by each separate document. Something like this:

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

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

where each cs is the checksum of timestamps of all documents created on a particular day.

现在，我遇到的问题是，我不知道删除文档时会从校验和中减去数据的算法。出于显而易见的原因，没有一种密码散列符合需要，而且我找不到能做到这一点的CRC算法。

Now, the problem I'm running into is that I don't know of an algorithm that could "subtract" data from the checksum when a document is being deleted. None of the cryptographic hashes fit the need, for obvious reasons, and I couldn't find any algorithms for CRC that would do this.

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

One option I considered was to have deletes add extra information to the hash, but this would lead to even more problems, as nodes can receive delete requests in different order, and when a node would restart it would re-read all the timestamps from the documents, and thus the information about the deletes would be lost.

我也不希望在所有文档散列都使用内存的情况下使用散列树，因为这将使用大约8个内存，并且我认为，仅凭这种需求有点矫kill过正。

I also wouldn't like using a hash tree with all document hashes in-memory, as that would use roughly 8 gigs of memory, and I think it's a bit of overkill for just this need.

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

For now the best option seems to regenerate these hashes completely from time to time in background, but that is also a lot of needless overhead, and wouldn't provide immediate information on changes.

所以，你们知道一种校验和算法，该算法可以让我从中删除一些数据校验和？我需要算法更快并且校验和应能强烈指示最小的变化（这就是为什么我不能真正使用纯异或的原因。）

So, do you guys know of a checksum algorithm that would let me "remove" some data from the checksum? I need the algorithm to be somewhat fast and the checksum that would strongly indicate the smallest of changes (that's why I can't really use plain XOR).

推荐答案

怎么样

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

其中X是一个总异或（紧随其后的是javascript-y伪代码）：

where X is an aggregate XOR (javascript-y pseudocode follows):

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

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

and f() is a hash of individual document information? (whether timestamp or filename or ID or whatever)

使用XOR可以使您减去文档，但是对每个文档使用哈希可以您可以保持类似哈希的检测小变化的质量。

The use of XOR would allow you to "subtract" out documents, but using a hash on a per-document basis allows you to preserve a hash-like quality of detecting small changes.

这篇关于是否有一种校验和算法也支持“减法”运算。数据呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！