5

对于一个开源项目，我正在文件系统之上编写一个抽象层。

该层允许我将元数据和关系附加到每个文件。

如果文件被重命名/移动或复制，我希望该层能够优雅地处理文件重命名并维护元数据。

为此，我需要一种计算文件身份的机制。显而易见的解决方案是为每个文件计算一个 SHA1 哈希，然后针对该哈希分配元数据。但是……那真的很贵，尤其是电影。

所以，我一直在考虑一种算法，虽然不是 100% 正确，但在绝大多数情况下都是正确的，而且很便宜。

一种这样的算法可能是使用文件大小和该文件的字节样本来计算散列。

我应该为样本选择哪些字节？如何保持计算便宜且相当准确？我知道这里需要权衡，但性能至关重要。并且用户将能够处理系统出错的情况。

我需要这个算法来处理非常大的文件（1GB+ 和 5K 的小文件）

编辑

我需要这个算法在 NTFS 和所有 SMB 共享（基于 Linux 或 Windows）上工作，我希望它支持文件从一个位置复制到另一个位置的情况（存在 2 个物理副本被视为一个身份）。我什至可能会考虑希望它在 MP3 被重新标记的情况下工作（物理文件已更改，因此我可能对每种文件类型都有一个身份提供者）。

编辑 2

相关问题：确定文件身份的算法（优化）

4

8 回答 8

5

Bucketing，多层比较应该在您正在讨论的文件范围内最快且可扩展。

第一级索引只是文件的长度。

第二级是哈希。低于一定大小，它是整个文件的散列。除此之外，是的，我同意您对采样算法的想法。我认为可能会影响采样速度的问题：

  1. 为避免碰到可能高度相似或相同的规则间隔的标题，您需要插入一个不一致的数字，例如：素数或连续素数的倍数。
  2. 避免可能最终遇到常规记录标头的步骤，因此，如果尽管位置不同，您仍从样本字节中获得相同的值，请尝试将步骤调整为另一个素数。
  3. 处理具有大量相同值的异常文件，因为它们是未编码的图像，或者只是填充了空值。
于 2009-01-19T16:36:58.467 回答
4

做第一个 128k，在 1mb 标记处再做 128k，在 10mb 标记处再做 128k，在 100mb 标记处再做 128k，在 1000mb 标记处再做 128k，等等。随着文件大小变大，你更有可能将能够仅根据它们的大小来区分两个文件，你散列的数据越来越小。128k以下的一切都得到了彻底的照顾。

于 2009-01-19T01:11:07.680 回答
2

信不信由你，我使用刻度作为文件的最后写入时间。它尽可能便宜，我仍然看到不同文件之间的冲突。

于 2009-01-19T00:09:19.913 回答
2

如果您可以放弃 Linux 共享要求并将自己限制在 NTFS，那么 NTFS 备用数据流将是一个完美的解决方案，它：

  • 不需要任何类型的散列；
  • 在重命名后幸存下来；和
  • 在移动中幸存下来（即使在不同的 NTFS 卷之间）。

你可以在这里阅读更多关于它的信息。基本上，您只需为您的流添加一个冒号和一个名称（例如“:meta”），然后在其中写入您喜欢的任何内容。因此，如果您有一个目录“D:\Movies\Terminator”，请使用普通文件 I/O 将元数据写入“D:\Movies\Terminator:meta”。如果要保存特定文件（而不是整个文件夹）的元数据，也可以这样做。

如果您希望将元数据存储在其他地方并且只能够检测同一 NTFS 卷上的移动/重命名，则可以使用 GetFileInformationByHandle API 调用（请参阅 MSDN /en-us/library/aa364952(VS.85)。 aspx) 来获取文件夹的唯一 ID（结合 VolumeSerialNumber 和 FileIndex 成员）。如果文件/文件夹在同一卷上移动/重命名，此 ID 不会更改。

于 2009-08-14T22:42:31.053 回答
1

如何存储一些随机整数 r i并查找字节（r i mod n），其中 n 是文件的大小？对于带有标题的文件，您可以先忽略它们，然后对剩余的字节执行此过程。

如果您的文件实际上非常不同（不仅仅是某处单个字节的差异，而是说至少有 1% 的差异），那么随机选择的字节会注意到这一点。例如，在字节数相差 1% 的情况下，100 个随机字节将无法注意到的概率为 1/e ~ 37%；增加您查看的字节数会使此概率呈指数下降。

使用随机字节背后的想法是，它们基本上可以保证（好吧，从概率上讲）与任何其他字节序列一样好，除非它们不易受到其他序列的一些问题的影响（例如碰巧查看每个文件格式的第 256 个字节，其中该字节必须为 0 或其他值）。

更多建议：

  • 与其抓取字节，不如抓取更大的块来证明寻找的成本是合理的。
  • 我建议始终查看文件的第一个块左右。由此，您可以确定文件类型等。（例如，您可以使用该file程序。）
  • 至少权衡整个文件的CRC之类的成本/收益。它不像真正的加密哈希函数那样昂贵，但仍然需要读取整个文件。好处是它会注意到单字节的差异。
于 2009-01-19T00:57:50.127 回答
0

嗯，首先你需要更深入地研究文件系统是如何工作的。您将使用哪些文件系统？大多数文件系统都支持硬链接和软链接，因此“文件名”信息不一定存储在文件本身的元数据中。

实际上，这是可堆叠分层文件系统的全部要点，您可以通过各种方式对其进行扩展，例如支持压缩或加密。这就是“vnodes”的全部意义所在。您实际上可以通过多种方式做到这一点。其中一些非常依赖于您正在查看的平台。这在使用 VFS 概念的 UNIX/Linux 系统上要简单得多。例如，您可以在 ext3 之上实现您自己的层，或者您拥有什么。

** 阅读您的编辑后，还有更多内容。如前所述，文件系统已经使用 inode 之类的东西来做到这一点。散列可能不是一个好主意，不仅因为它很昂贵，而且因为两个或多个原像可以共享同一个图像；也就是说，两个完全不同的文件可以具有相同的哈希值。我认为您真正想做的是利用文件系统已经公开的元数据。当然，这在开源系统上会更简单。:)

于 2009-01-19T00:09:50.037 回答
0

我应该为样本选择哪些字节？

我想我会尝试使用一些算术级数，比如斐波那契数。这些很容易计算，并且它们的密度越来越小。小文件比大文件具有更高的采样率，并且样本仍然会超过整个文件中的点。

于 2009-01-19T00:57:01.393 回答
0

这项工作听起来可以在文件系统级别更有效地实现，或者使用版​​本控制系统的一些松散近似（两者？）。

为了解决最初的问题，您可以为每个文件保留一个（文件大小、散列的字节数、散列）数据库，并尝试最小化每个文件大小的散列字节数。每当您检测到冲突时，您要么拥有相同的文件，要么增加哈希长度以超过第一个差异。

毫无疑问，需要进行优化以及 CPU 与 I/O 的权衡，但对于不会出现误报的事情来说，这是一个好的开始。

于 2009-01-19T03:49:50.637 回答