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 탐색기는 해당 수준의 최대값(65536)에 매우 빠르게 접근했기 때문에 디렉터리 너비 4를 좋아하지 않았습니다.상위 2개의 디렉터리 길이를 각각 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분 이상이 걸렸습니다!

백만 개의 해시에 대해 분포는 다음과 같이 작동합니다.

  • 첫 번째 수준에는 4096개의 폴더가 있습니다.
  • 2단계에는 평균 250개의 폴더가 있습니다.
  • 3레벨에는 평균 1개의 폴더가 있습니다.

이는 Windows 탐색기 내에서 매우 관리하기 쉽고 너무 깊거나 넓어지지 않는 것 같습니다.분명히 분포가 이렇지 않다면 문제가 발생할 수 있지만 오직 세 번째 수준에서.처음 두 수준은 4096으로 제한됩니다.목표 세트가 더 크다면 추가 레벨을 추가하고 많은 성장 잠재력을 얻을 수 있다고 생각합니다.내 신청서의 경우 100만 달러가 매우 합리적인 상한선입니다.

디렉토리 구조 경험적 방법을 결정하기 위한 테스트의 타당성에 대해 생각하는 사람이 있습니까?

다른 팁

일부 관찰 :

  • 당신은 4와 10 더 숯이 나서 나누었습니다. 4 개의 숯이 스스로 디렉토리에 65536 개의 항목으로 이어질 수 있으며, 10 숯은 16^10 개의 항목으로 이어질 것입니다.
  • 다음 질문은 다음과 같습니다.이 숫자를 어떻게 선택 했습니까? 그들은 나를 좋아해요 마법 번호. 당신은 희망 당신의 분할은 모든 경우에 일을 할 것입니다 ...

처리 할 수있는 디렉토리 Deepth에 대한 귀하의 질문은 좋습니다. 대답 할 수 없습니다. 그러나 20 개의 레벨이 레벨 당 최대 256 개의 항목을 유지할 수 있기 때문에 20 개의 중첩 디렉토리가 다루기가 너무 많으면 살펴 봐야합니다.

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

반면에 4자를 고수 할 수 있습니다. 이는 최대 10 및 65536의 깊이로 이어질 수 있습니다.

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

그러나 두 경우 모두 동적 알고리즘을 작성하여 레벨 당 항목 수를 확인하고 필요한대로 새로운 하위 폴더를 소개합니다. 따라서 처음 256 (또는 65536) 항목은 하나의 디렉토리로 이동합니다.

충돌 감지기와 리졸버를 추가하십시오. 누군가 SHA-1 충돌 벡터를 확인하려고 할 경우를 대비하여 준비가 더 좋았습니다.

나는 아직 SHA-1 충돌을 보지 못했지만 누군가가 독특하다고 생각한 우발적 인 MD5 충돌의 나쁜 사례를 보았습니다.

어쨌든 NTFS는 Btree 디렉토리 구조를 사용하므로 실제로 한 폴더에 모두 배치 할 수 있습니다. Windows 탐색기는 마음에 들지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top