algorithm - 如何检测大文件(TB)中的少量变化

Question

我刚发现一个有趣的博客，谈论一些面试问题。其中一个问题是:

Given a very large file (multiple TB), detect what 4MB ranges has changed in the file between consecutive runs of your program.

我对此一无所知。任何人都可以对此提出一些想法吗？

Answer 1

如果您对数据的创建有任何控制，您可以使用 Merkle trees

将数据分成小片段(假设每个片段 10MB，但这不是问题所在)，并为每个片段创建一个 h=hash(fragment)。

现在，所有这些哈希将成为树的叶子。现在，从叶子向上创建一个完整的二叉树:h(father) = hash(father.left XOR father.right)。
现在，你已经得到了一棵树——如果你比较两棵树，h(root1) = h(root2) 当且仅当 tree1=tree2——很有可能(如果你使用 128 位散列，出错的概率是1/2^128，真的可以忽略不计)。

同样的说法当然对任何子树都是正确的，这让你可以快速找到不同的叶子，这个叶子代表被改变的片段。

这个想法被Amazon's Dynamo使用了比较两个数据库是否发生变化，并快速找到变化。