SHA-1 ベースのディレクトリ構造と NTFS の制限は?

StackOverflow https://stackoverflow.com/questions/1902061

  •  19-09-2019
  •  | 
  •  

質問

データの SHA-1 ハッシュをキーオフする NTFS ディレクトリ パスにファイルベースのデータを保存しているアプリがあります。これにはいくつかの非常に優れた属性 (重複排除、他のメタデータ変更の影響を受けないなど) がありますが、ハッシュ ベースのディレクトリ ストレージ構造を作成するために人々が経験したベスト プラクティスに興味があります。私の主な関心事は、特定のフォルダーの深さに実際に保存できるファイル/フォルダーの数です。

どのような制限が発生するか知っている人はいますか?これらをすべてストレージ パスのルートにあるフォルダーにダンプすると、ストレージの拡張能力が大幅に制限されるような気がします。すぐには問題にはなりませんが、後で大規模なストレージを再構築するよりも、これを回避する構造を採用したいと思います。

より深いツリーを作成するために署名を分割するアプローチを採用した場合、どれくらい分割する必要があるかについてのガイダンスはありますか?このようなもので十分でしょうか?

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 経由でプログラムからアクセスする場合はどうすればよいでしょうか?

役に立ちましたか？

解決 3

他の回答者様の洞察力に感謝します。

ウェブ上の他の質問からのようです NTFS がそのサイズを処理できること, ただし、Windows エクスプローラーとネットワーク操作は、はるかに低いしきい値で停止する可能性があります。SHA-1 が 1,000,000 個の「ファイル」のランダムなセットに対して生成するものと同様の、非常に均一なランダム分布のシミュレーションを実行しました。

Windows エクスプローラーは、ディレクトリ幅 4 がそのレベルの最大値 (65536) にすぐに近づいてしまうため、明らかに好みませんでした。上位 2 つのディレクトリの長さをそれぞれ 3 (最大 4096) になるように微調整し、残りの 34 桁を 3 番目のレベルに配置して、深さとレベルあたりのディレクトリが多すぎる可能性のバランスをとろうとしました。これにより、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);
}

約 50,000 回を超えると、シミュレーションが少し遅くなるように見えますが (5,000 回あたり 15 ～ 20 秒)、その速度は維持されます。私のマシンでは最後の削除に 30 分以上かかりました。

100 万個のハッシュの分布は次のようになります。

  • 第 1 レベルには 4096 個のフォルダーがあります
  • 2 番目のレベルには平均 250 個のフォルダーがあります
  • 3 番目のレベルには平均 1 つのフォルダーがあります

これは Windows エクスプローラー内で非常に管理しやすく、深くなりすぎたり広くなりすぎたりすることはないようです。もちろん、分布がこれほど均一でない場合は、問題が発生する可能性がありますが、 のみ 3番目のレベルで。最初の 2 つのレベルは 4096 で制限されます。目標設定がもっと大きければ、さらにレベルを追加して、大きな成長の可能性を得ることができると思います。私のアプリケーションにとって、100 万は非常に妥当な上限です。

ディレクトリ構造のヒューリスティックを決定するためのこのようなテストの有効性について何か考えている人はいますか?

他のヒント

いくつかの観察:

  • さらに 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) 項目は 1 つのディレクトリに移動されます。

衝突検出器とレゾルバを追加します。あなたがより良い誰かがSHA-1の衝突ベクトルをチェックインしようとする場合には準備ができています。

私はまだSHA-1の衝突を見ていないが、私は、誰かが、彼らがユニークだと思っていた偶然のMD5の衝突の悪いケースを見ました。

あなたが本当に1つのフォルダにすべてを置くことができるように

とにかく、NTFSは、Bツリーのディレクトリ構造を使用しています。 Windowsエクスプローラは、しかしそれを好きではありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top