3

我有一个应用程序将基于文件的数据存储在 NTFS 目录路径下，该路径关闭数据的 SHA-1 哈希。它有几个非常好的属性（重复数据删除、不受其他元数据更改的影响等），但我很好奇人们在创建基于哈希的目录存储结构方面所经历的最佳实践。我主要关心的是可以实际存储在给定文件夹深度的文件/文件夹的数量。

有谁知道我会遇到什么样的限制？如果我将它们全部转储到存储路径根目录的文件夹中，我觉得我会严重限制存储增长的能力。虽然这不会很快成为问题，但我宁愿有一个可以避免这种情况的结构，也不愿稍后尝试重组大量存储。

如果我采取一种方法来分块签名以创建更深的树，是否有任何关于我需要分块多少的指导？这样的事情就足够了吗？

StringBuilder foo = new StringBuilder(60);
// ...root, etc.
// SHA-1 always has a length of 40, chunk it up to distribute into smaller groups
// "\0000\0000000000000000\00000000000000000000"
foo.Append(Path.DirectorySeparatorChar);
foo.Append(sha1, 0, 4);
foo.Append(Path.DirectorySeparatorChar);
foo.Append(sha1, 4, 16);
foo.Append(Path.DirectorySeparatorChar);
foo.Append(sha1, 20, 20);

知道 SHA-1 的分布相当不错，我不得不假设最终会有大型集群，但平均而言它会均匀分布。我担心的是那些集群。

访问过宽的目录结构时是否存在性能损失？我知道 Windows 资源管理器会窒息，但是通过 C#/System.IO 以编程方式访问呢？

4

3 回答 3

3

一些观察：

  • 您在 4 个和 10 个字符后拆分。4 个字符本身可以导致目录中的 65536 个条目，10 个字符将导致 16^10 个条目，这肯定太多了（还有更多字符剩余......）
  • 所以下一个问题是：你是如何选择这个数字的？在我看来，它们就像神奇的数字。您似乎希望您的拆分在所有情况下都能发挥作用...

您关于可以处理的目录深度的问题很好 - 我无法回答。但是您应该看看，如果 20 个嵌套目录太多而无法处理，因为 20 个级别允许您最多保留每个级别 256 个条目：

xx/xx/xx/xx/xx/...

另一方面，您可以坚持使用 4 个字符，这将导致最多 10 个和 65536 个条目的深度：

xxxx/xxxx/xxxx/xxxx/xxxx/...

但是 - 在这两种情况下，我可能会编写一个动态算法，它检查每个级别的项目数并根据需要引入新的子文件夹。因此，前 256 个（或 65536 个）项目只会进入一个目录。

于 2009-12-14T17:44:54.087 回答
1

添加碰撞检测器和解析器。你最好做好准备，以防有人试图检查 SHA-1 碰撞向量。

我还没有看到任何 SHA-1 碰撞，但我确实看到了一个意外 MD5 碰撞的坏情况，有人认为它们是独一无二的。

无论如何，NTFS 使用 BTree 目录结构，因此您真的可以将所有内容放在一个文件夹中。Windows 资源管理器不会喜欢它。

于 2009-12-14T18:00:50.680 回答
1

感谢其他回答者的洞察力。

从网络上的其他问题听起来，NTFS 可以处理大小，但 Windows 资源管理器和网络操作可能会在低得多的阈值下窒息。我运行了一个非常均匀的随机分布的模拟，类似于 SHA-1 为一组随机的 1,000,000 个“文件”生成的分布。

Windows Explorer 绝对不喜欢 4 的目录宽度，因为它很快就接近了该级别的最大值 (65536)。我将前两个目录长度调整为每个 3（最大 4096），并将剩余的 34 位放在第三级，以尝试平衡深度与每级目录过多的概率。这似乎允许 Windows 资源管理器处理浏览结构。

这是我的模拟：

const string Root = @"C:\_Sha1Buckets";
using (TextWriter writer = File.CreateText(@"C:\_Sha1Buckets.txt"))
{
    // simulate a very even distribution like SHA-1 would produce
    RandomNumberGenerator rand = RandomNumberGenerator.Create();
    byte[] sha1 = new byte[20];
    Stopwatch watch = Stopwatch.StartNew();

    for (int i=0; i<1000000; i++)
    {
        // populate bytes with a fake SHA-1
        rand.GetBytes(sha1);

        // format bytes into hex string
        string hash = FormatBytes(sha1);

        // C:\_Sha1Buckets
        StringBuilder builder = new StringBuilder(Root, 60);

        // \012\345\6789abcdef0123456789abcdef01234567\
        builder.Append(Path.DirectorySeparatorChar);
        builder.Append(hash, 0, 3);
        builder.Append(Path.DirectorySeparatorChar);
        builder.Append(hash, 3, 3);
        builder.Append(Path.DirectorySeparatorChar);
        builder.Append(hash, 6, 34);
        builder.Append(Path.DirectorySeparatorChar);

        Directory.CreateDirectory(builder.ToString());
        if (i % 5000 == 0)
        {
            // write out timings every five thousand files to see if changes
            writer.WriteLine("{0}: {1}", i, watch.Elapsed);
            Console.WriteLine("{0}: {1}", i, watch.Elapsed);
            watch.Reset();
            watch.Start();
        }
    }

    watch.Reset();
    Console.WriteLine("Press any key to delete the directory structure...");
    Console.ReadLine();
    watch.Start();
    Directory.Delete(Root, true);
    writer.WriteLine("Delete took {0}", watch.Elapsed);
    Console.WriteLine("Delete took {0}", watch.Elapsed);
}

大约 5 万之后，模拟速度似乎有所放缓（每 5000 秒 15-20 秒），但仍保持在该速度。最后的删除在我的机器上花费了 30 多分钟！

对于 100 万个哈希，分布是这样计算的：

  • 第一级有 4096 个文件夹
  • 第二级平均有 250 个文件夹
  • 第 3 级平均有 1 个文件夹

That is very manageable within Windows Explorer and doesn't seem to get too deep or wide. Obviously if the distribution weren't this even, then we could run into problems, but only at the third level. The first two levels are bounded at 4096. I suppose if the target set were larger, we could add an additional level and gain a lot of growth potential. For my application 1 million is a very reasonable upper bound.

Anyone have any thoughts on the validity of such a test for determining directory structure heuristics?

于 2009-12-15T17:21:33.323 回答