crc - 使用 CRC 作为摘要来检测文件之间的重复项

Question

CRC 和类似计算（例如 Fletcher 和 Adler）的主要用途似乎是用于检测传输错误。因此，我看到的大多数研究似乎都解决了检测两个数据集之间小规模差异的概率问题。我的需求略有不同。

以下是对该问题的非常近似的描述。细节比这复杂得多，但下面的描述说明了我正在寻找的功能。这个小小的免责声明旨在避免诸如“当您可以更轻松地以我建议的其他方式解决问题时，您为什么要以这种方式解决问题？”之类的答案？- 由于无数与此问题或帖子无关的原因，我需要以这种方式解决我的问题，因此请不要发布此类答案。

我正在处理分布式网络上的数据集集合（大小~1MB）。对这些数据集执行计算，速度/性能至关重要。我想要一种机制来避免重新传输数据集。也就是说，我需要某种方法来为给定大小的每个数据集生成唯一标识符 (UID)。（然后，我将数据集大小和 UID 从一台机器传输到另一台机器，接收机器只需要根据 UID 在本地没有数据时请求传输数据。）

这类似于使用 CRC 检查文件更改和使用 CRC 作为摘要来检测文件之间的重复之间的区别。我没有看到任何关于后者使用的讨论。

我不关心篡改问题，即我不需要加密强度散列。

我目前正在使用序列化数据的简单 32 位 CRC，到目前为止，这对我很有帮助。但是，我想知道是否有人可以推荐哪种 32 位 CRC 算法（即哪个多项式？）最适合在这种情况下最小化冲突概率？

我的另一个问题有点微妙。在我当前的实现中，我忽略了我的数据集的结构，实际上只是对表示我的数据的序列化字符串进行 CRC。但是，由于各种原因，我想按如下方式更改我的 CRC 方法。假设我的顶级数据集是一些原始数据和一些从属数据集的集合。我目前的方案本质上是连接原始数据和所有从属数据集，然后是 CRC 的结果。但是，大多数时候我已经有了从属数据集的 CRC，我宁愿通过将原始数据与从属数据集的CRC连接起来，然后 CRC来构造我的顶级数据集的 UID这种结构。问题是，

用一种可以让我讨论我的想法的语言来表达，我将定义一些符号。调用我的顶级数据集T，假设它由原始数据集R和从属数据集组成Si, i=1..n。我可以这样写T = (R, S1, S2, ..., Sn)。如果&表示数据集的拼接，我原来的方案可以认为是：

UID_1(T) = CRC(R & S1 & S2 & ... & Sn)

我的新方案可以被认为是

UID_2(T) = CRC(R & CRC(S1) & CRC(S2) & ... & CRC(Sn))

那么我的问题是：（1）如果T和T'非常不同，什么CRC算法最小化prob( UID_1(T)=UID_1(T') )，什么CRC算法最小化prob( UID_2(T)=UID_2(T') )，这两个概率如何比较？

我对此事的（天真和不知情的）想法是这样的。T假设和之间的差异T'仅在一个从属数据集中，WLOG 说S1!=S1'。如果发生这种情况CRC(S1)=CRC(S1')，那么显然我们将拥有UID_2(T)=UID_2(T')。另一方面，如果CRC(S1)!=CRC(S1')，则 和 之间R & CRC(S1) & CRC(S2) & ... & CRC(Sn)的R & CRC(S1') & CRC(S2) & ... & CRC(Sn)差异仅在 4 个字节上存在微小差异，因此 UID_2 检测差异的能力实际上与 CRC 检测传输错误的能力相同，即它仅检测错误的能力一些没有广泛分离的位。由于这是 CRC 的设计目的，我认为 UID_2 非常安全，只要我使用的 CRC 擅长检测传输错误。用我们的符号表示，

prob( UID_2(T)=UID_2(T') ) = prob(CRC(S1)=CRC(S1')) + (1-prob(CRC(S1)=CRC(S1'))) * probability of CRC not detecting error a few bits.

让我们称 CRC 未检测到几位错误的P概率，以及它未检测到大型数据集上的大差异的概率Q。上式可以大致写成

prob( UID_2(T)=UID_2(T') ) ~ Q + (1-Q)*P

现在我将更改我的 UID，如下所示。对于“基本”数据，即T=(R)R 只是双精度、整数、字符、布尔值等的数据集，请定义UID_3(T)=(R). 然后对于T由下级数据集向量组成的数据集T = (S1, S2, ..., Sn)，定义

UID_3(T) = CRC(ID_3(S1) & ID_3(S2) & ... & ID_3(Sn))

假设一个特定的数据集T具有嵌套层次深的从属数据集m，那么，在某种模糊的意义上，我会认为

prob( UID_3(T)=UID_3(T') ) ~ 1 - (1-Q)(1-P)^m

鉴于这些概率在任何情况下都很小，这可以近似为

 1 - (1-Q)(1-P)^m = Q + (1-Q)*P*m + (1-Q)*P*P*m*(m-1)/2 + ... ~ Q + m*P

因此，如果我知道我的最大嵌套级别m，并且我知道P并且Q对于各种 CRC，我想要的是选择为我提供最小值的 CRC Q + m*P。如果我怀疑可能是这种情况，P~Q那么上面的内容就简化了。我对 UID_1 的错误概率是P. 我对 UID_3 的错误概率是(m+1)P，m我的最大嵌套（递归）级别在哪里。

这一切看起来合理吗？

Answer 1

我想要一种机制来避免重新传输数据集。

rsync已经解决了这个问题，通常使用您概述的方法。

但是，我想知道是否有人可以推荐哪种 32 位 CRC 算法（即哪个多项式？）最适合在这种情况下最小化冲突概率？

精心挑选的 CRC 多项式之间不会有太大差异。速度对您来说可能更重要，在这种情况下，您可能想要使用硬件 CRC，例如crc32现代 Intel 处理器上的指令。那一个使用CRC-32C (Castagnoli) polynomial。您可以通过在同一个循环中计算三个缓冲区上的 CRC，然后将它们组合起来，在单个内核上并行使用所有三个算术单元，从而实现非常快的速度。请参阅下面如何组合 CRC。

但是，大多数时候我已经有了从属数据集的CRC，我宁愿通过将原始数据与从属数据集的CRC连接来构造我的顶级数据集的UID，然后CRC这个构造.

或者您可以快速计算整个集合的 CRC，就好像您对整个事物进行了 CRC，但是使用已经计算的片段的 CRC。crc32_combine()在zlib中查看。这比拿一堆 CRC 的 CRC 更好。通过组合，您可以保留 CRC 算法的所有数学优点。

Answer 2

马克·阿德勒的回答很成功。如果我脱掉程序员的帽子，戴上数学家的帽子，其中一些应该是显而易见的。他没有时间解释数学，所以我会在这里为有兴趣的人提供。

计算 CRC 的过程本质上是进行多项式除法的过程。多项式的系数为 mod 2，即每一项的系数为 0 或 1，因此 N 次多项式可以用 N 位数表示，每一位是一项的系数（以及执行多项式除法相当于进行一大堆 XOR 和移位操作）。当对数据块进行CRC校验时，我们将“数据”视为一个大多项式，即一长串位，每个位代表多项式中一项的系数。好吧，调用我们的数据块多项式 A。对于每个 CRC“版本”，都选择了CRC 的多项式，我们称之为 P。对于 32 位 CRC，P 是一个 32 次多项式，因此它有 33 个项和 33 个系数。因为顶部系数始终为 1，所以它是隐式的，我们可以用 32 位整数表示 32 次多项式。（计算上，这实际上是很方便的。）数据块A的CRC计算过程就是A除以P求余数的过程。也就是说，A总是可以写成

A = Q * P + R

其中R是一个次数小于P次数的多项式，即R的次数小于等于31，所以可以用32位整数表示。R本质上是CRC。（小提示：通常在 A 前面加上 0xFFFFFFFF，但这在这里并不重要。）现在，如果我们连接两个数据块 A 和 B，则与两个数据块连接对应的“多项式”就是 A 的多项式，“移位向左”乘以 B 中的位数加上 B。换句话说，A&B 的多项式是 A*S+B，其中 S 是对应于 1 后跟 N 个零的多项式，其中 N 是B 中的位（即 S = x**N ）。那么，对于 A&B 的 CRC，我们能说些什么呢？假设我们知道 A=Q*P+R 和 B=Q'*P+R'，即 R 是 A 的 CRC，R' 是 B 的 CRC。假设我们也知道 S=q*P+r。然后

A * S + B = (Q*P+R)*(q*P+r) + (Q'*P+R')
          = Q*(q*P+r)*P + R*q*P + R*r + Q'*P + R'
          = (Q*S + R*q + Q') * P    + R*r + R'

所以要求A*S+B除以P的余数，只需求R*r+R'除以P的余数即可。因此，计算两个数据流A和B的级联的CRC ，我们只需要知道数据流的单独CRC，即R和R'，以及尾随数据流B​​的长度N（因此我们可以计算r）。这也是 Marks 其他评论之一的内容：如果尾随数据流 B 的长度被限制为几个值，我们可以为这些长度中的每一个预先计算 r，从而使两个 CRC 的组合变得非常简单。（对于任意长度 N，计算 r 并不简单，但它比对整个 B 重新进行除法要快得多（log_2 N）。）

注意：以上不是CRC的精确阐述。正在发生一些变化。准确的说，如果L是0xFFFFFFFF表示的多项式，即L=x* 31+x *30+...+x+1，而S_n是“左移n位”多项式，即S_n = x* *n，则N位多项式A的数据块的CRC，是(L * S_N + A)*S_32除以P时的余数，即(L&A)*S_32除以P时的余数，其中&为“连接”运算符。

另外，我认为我不同意 Marks 的其中一个评论，但如果我错了，他可以纠正我。如果我们已经知道 R 和 R'，则使用上述方法比较计算 A&B 的 CRC 的时间，与直接计算它相比，不取决于 len(A) 与 len(B) 的比率 - 到以“直截了当”的方式计算它，实际上不必在整个连接数据集上重新计算 CRC。使用我们上面的符号，只需要计算 R*S+B 的 CRC。也就是说，我们不是将 0xFFFFFFFF 预先添加到 B 并计算其 CRC，而是将 R 预先添加到 B 并计算其 CRC。因此，它比较了重新计算 B 的 CRC 的时间与计算 r 的时间（然后将 R*r+R' 除以 P，这在时间上可能是微不足道且无关紧要的）。

Answer 3

Mark Adler 的回答解决了技术问题，所以这不是我在这里要做的。在这里，我将指出 OP 问题中提出的同步算法中的一个主要潜在缺陷，并提出一个小的改进。

校验和和散列为某些数据提供了单一的签名值。但是，由于长度有限，如果数据较长，校验和/哈希的可能唯一值的数量总是小于原始数据的可能组合。例如，一个 4 字节的 CRC 只能采用 4 294 967 296 个唯一值，而即使是可能是数据的 5 字节值也可以采用 8 倍的值。这意味着对于任何比校验和本身更长的数据，总是存在一个或多个具有完全相同签名的字节组合。

当用于检查完整性时，假设是稍微不同的数据流导致相同签名的可能性很小，因此如果签名相同，我们可以假设数据相同。重要的是要注意，我们从一些数据开始d并验证给定一个校验和，c，使用校验和函数计算f，f(d) == c。

然而，在 OP 的算法中，不同的使用会引入一种微妙的、有害的置信度下降。在 OP 的算法中，服务器 A 将从原始数据开始[d1A,d2A,d3A,d4A]并生成一组校验和[c1,c2,c3,c4]（其中dnA是服务器 A 上的第 n 个数据项）。然后，服务器 B 将接收此校验和列表并检查它自己的校验和列表以确定是否缺少任何校验和。假设服务器 B 有列表[c1,c2,c3,c5]。然后应该发生的是它d4从服务器 A 请求并且同步在理想情况下正常工作。

如果我们回想一下冲突的可能性，并且它并不总是需要那么多数据来产生一个（例如CRC("plumless") == CRC("buckeroo")），那么我们很快就会意识到我们的方案提供的最好保证是服务器 B 肯定没有，d4A但它不能保证它有[d1A,d2A,d3A]。这是因为它是可能的，f(d1A) = c1即使f(d1B) = c1和d1A是d1B不同的，我们希望两台服务器都拥有两者。在这个方案中，任何一个服务器都无法知道两者的d1A存在d1B. 我们可以使用越来越多的抗冲突校验和和散列，但这种方案永远不能保证完全同步。这变得更重要，网络必须跟踪的文件数量越多。我建议使用像 SHA1 这样没有发现冲突的加密哈希。

一种可能的缓解这种风险的方法是引入冗余哈希。一种方法是使用完全不同的算法，因为虽然有可能crc32(d1) == crc32(d2)，但不太可能adler32(d1) == adler32(d2)同时发生。不过，本文建议您不会通过这种方式获得太多收益。要使用 OP 表示法，它也不太可能crc32('a' & d1) == crc32('a' & d2)同时 crc32('b' & d1) == crc32('b' & d2)为真，因此您可以“加盐”到不太容易发生碰撞的组合。但是，我认为您也可以只使用像 SHA512 这样的抗冲突哈希函数，它实际上可能不会对您的性能产​​生那么大的影响。