많은 데이터 블록에 대해 해시를 저장하고 해시로 목록을 검색하는 방법은 무엇입니까?

Question

저는 중복 제거를 구현하는 opensource 프로젝트를 진행하고 있습니다. 프로젝트에 대한 링크는 아래 두 개의 하이퍼 링크를 참조하십시오. 프로젝트의 성능은 현재 매우 양호하지만 더 많은 블록이 디스크에 기록되면 성능이 저하됩니다. 이것은 HashManager 때문입니다. 작성된 각 블록에 대해 hashmanager는 해시 - 블록 아이디 쌍을 저장합니다. 중복 제거 프로세스의 경우 지정된 해시가있는 블록 식별자 목록이 필요합니다. (사용 된 해시는 Crc32 임) HashManager의 인터페이스에 대해서는 the source을 참조하십시오.

인터페이스의 현재 implementation은 목록을 256 개의 파일 (crc & 0xFF)에 저장하고 전체 목록을 메모리에로드합니다. 다른 목록이 필요할 때 이전 목록이 저장되고 다음 목록이로드됩니다. 이것이 메모리 소모를 야기 할 수 있다는 사실 외에도 이것은 성능 저하를 의미합니다.

문제를 극복하기 위해 어떤 좋은 옵션이 있습니까?

(그냥 clearify합니다 : 블록들이 중복 제거하기 전에 일치하는지 완전히 점검) 내가 온 디스크 구조에서 전문가가 아니다

Answer 1

,하지만 난 B-트리 자주 구현에 사용되는 들었습니다 키 - 값지도는 디스크에 저장됩니다. 그래서 당신은 CRC의 B-Tree 인덱스를 가질 수 있다고 생각합니다. 그런 다음 블록 ID 목록에 저장된 일종의 링크가 있습니다. 또한 CRC와 그 다음 블록 ID의 연결 인 키를 효과적으로 사용하여 목록을 B-Tree 구조로 결합하고 B-Tree에 대한 접두사/범위 쿼리를 효과적으로 수행 할 수 있습니다 .

Wikipedia Page on B-Trees : "컴퓨터 과학에서 B- 트리는 데이터를 정렬하고 로그 시간에 검색, 순차 액세스, 삽입 및 삭제를 허용하는 트리 데이터 구조입니다 .B 트리는 이진 검색의 일반화입니다 (Comer 1979, p. 123) 셀프 - 밸런싱 (self-balancing) 이진 탐색 트리와 달리, B- 트리는 큰 데이터 블록을 읽고 쓰는 시스템에 최적화되어 있습니다. 데이터베이스 및 파일 시스템. "

Answer 2

crcs를 저장하기 위해 256 개의 목록 파일을 사용하는 경우 첫 번째 명백한 단계는 목록 0에 0 바이트로 시작하는 모든 crcs를 넣고 목록 파일 1에 1 바이트를 가진 모든 crcs를 넣는 것입니다. . 다음 각 파일에있는 crc의 마지막 3 바이트 만 저장하십시오. 이렇게하면 키 저장소의 25 %가 절약되고 처리 속도가 빨라집니다.

두 번째해야 할 일은 4GB crc가 목록에 등록되었는지 보여주기 위해 4 기가 비트 인 메모리 플래그 배열을 만드는 것입니다. 비트가 0이면 crc가 아직 사용되지 않았기 때문에 기존 항목을 먼저 찾아야하는지 알 수 있으므로 배열에 새 항목을 추가하는 속도가 크게 빨라집니다.

데이터 도메인 개발자가 작성한 논문에 따르면이 불필요한 검색은 가져 오기 프로세스가 가장 느려지는 것입니다 (다른 방법은 피할 수 있습니다).

수정하려는 목록을 저장한다고 가정합니다. 필자는 전체 목록을 다시 작성하는 대신 파일의 끝에 모든 변경 사항을 넣으므로 전체 목록을 다시 작성하는 대신 파일의 끝에 추가 할 수 있습니다. 파일의 끝에있는 포인터로 시작하는 링크 된 목록 구조를 사용하여 추가 할 때마다 파일 끝에 목록에 새 헤더를 씁니다. 삭제 플래그가 설정된 목록 위로 새 항목을 작성하여 삭제할 항목을 표시 할 수 있습니다. 그런 다음 주기적으로 목록 크기를 줄이기 위해 각 목록을 가비지 수집 할 수 있습니다 (예 : 일주일에 한 번 또는 일주일에 한 번 일괄 처리). 목록 수정을 통해 동일한 작업을 수행 할 수 있습니다. 새 항목을 작성하여 이전 항목을 플래그로 대체하십시오. 그런 다음 가비지를 주기적으로 수집하여 이전 항목을 제거하십시오.

매번 메모리에 전체 내용을로드 할 필요가 없도록 목록을 구조화 할 수있는 모든 작업을 수행하게됩니다. 할 수있는 한 거의 데이터를 이동하지 마십시오.

이것은 스택 오버플로에서 작성한 첫 번째 항목이므로 내 게시가 기본 규범을 따르지 않으면 변명하십시오.

위의 지시 사항에 따라 답변을 편집 구역으로 지정해야합니다. 명확한 설명이 필요하지는 않습니다. 따라서 정확하게 문제가 무엇인지 추측하는 것이 더 재미있을 것 같습니다. 나는 나의 추측이 가깝고 나의 대답이 유용한 요소들을 포함하기를 바랍니다.