거대한 파일의 효율적인 확산을위한 알고리즘
https://stackoverflow.com/questions/2030238
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
100GB와 같이 매우 큰 두 파일 A와 B를 저장해야합니다. 그러나 B는 큰 부분에서 A와 비슷할 수 있으므로 a와 diff (a, b)를 저장할 수 있습니다. 이 문제에는 두 가지 흥미로운 측면이 있습니다.
- 파일은 너무 커서 내가 알고있는 DIFF 라이브러리가 메모리 내이기 때문에 분석 할 수 없습니다.
- 나는 실제로 Diff가 필요하지 않습니다. Diff에는 일반적으로 인간이 읽을 수 있기 때문에 삽입, 편집 및 삭제가 있습니다. 정보가 적은 정보를 얻을 수 있습니다. "새로운 바이트"와 "임의의 오프셋에서 오래된 파일의 복사 바이트"만 필요합니다.
나는 현재 이러한 조건에서 델타를 A에서 B로 계산하는 방법을 잃어 버렸습니다. 누구든지 이것에 대한 알고리즘을 아는 사람이 있습니까?
다시 한 번 문제는 간단합니다. 둘 다 상당히 유사하다는 사실을 감안할 때 파일 A와 B를 가능한 한 바이트로 저장할 수있는 알고리즘을 작성하십시오.
추가 정보 : 큰 부품이 동일 할 수 있지만 다른 오프셋이 있고 순서가 좋지 않을 수 있습니다. 마지막 사실은 기존의 차이가 많이 절약되지 않는 이유입니다.
해결책
rsyncs 알고리즘을 살펴보십시오. 정확하게 수행하도록 설계되어 델타가 효율적으로 복사 할 수 있습니다. 그리고 내가 기억하는 것처럼 알고리즘은 잘 문서화되어 있습니다.
다른 팁
당신이 사용할 수있는 rdiff, 큰 파일에서 매우 잘 작동합니다. 여기서 나는 두 개의 큰 파일의 차이를 만듭니다 A 그리고 B:
예를 들어 하나의 파일의 서명을 만듭니다
rdiff signature A sig.txt생성 된 서명 파일을 사용합니다
sig.txt그리고 다른 큰 파일은 델타를 만듭니다.rdiff delta sig.txt B delta지금
delta파일을 재현하는 데 필요한 모든 정보가 포함되어 있습니다B둘 다가있을 때A그리고delta. B를 재현하려면 달리기rdiff patch A delta B
우분투에서 그냥 달리십시오 sudo apt-get install rdiff 설치하려면. 매우 빠릅니다. PC에서 초당 약 40MB를 얻습니다. 방금 8GB 파일로 시도했으며 RSYNC에서 사용하는 메모리는 약 1MB였습니다.
그것이 바로 다음으로 알려진 문제입니다 "데이터 중복 제거". 가장 일반적으로 사용되는 접근법은 다음과 같습니다.
- 블록으로 파일을 읽으십시오.
- 소위 "청크"의 데이터를 분할하십시오. 가장 자주 사용되는 접근법은 "Rabins 지문을 사용한 내용 정의 청킹"이라고합니다.암호). 이 청크 접근 방식을 사용하면 대부분의 데이터 세트에서 더 나은 중복 제거로 이어지면 정적 크기의 덩어리를 사용합니다 (예 : 표시 여기).
- 암호화 지문을 사용하여 덩어리를 지문 인쇄 (예 : SHA-256).
- 지문이 이미 알려진 경우 지문을 색인에 저장하고 각 청크에 대해 조회하십시오. 지문이 알려진 경우 덩어리를 두 번째로 저장할 필요가 없습니다. 지문을 알 수없는 경우에만 데이터를 저장해야합니다.
이러한 데이터 중복 제거 알고리즘은 예를 들어 정확히 정확하지 않습니다. xdelta, 그러나 대형 데이터 세트의 경우 더 빠르고 확장 가능합니다. 청킹 및 지문은 코어 (Java) 당 약 50MB/s로 수행됩니다. 인덱스 크기는 중복, 청크 크기 및 데이터 크기에 따라 다릅니다. 200GB의 경우 EG 16KB의 청크 크기에 대한 메모리에 맞아야합니다.
벤틀리와 맥 일로이 압축 접근법은 매우 유사하지만 (예 : Googles Bigtable에 의해 사용됨) 압축 기술을 사용하는 상자 명령 줄 도구는 알지 못합니다.
그만큼 "FS-C" 오픈 소스 프로젝트에는 필요한 대부분의 코드가 포함되어 있습니다. 그러나 FS-C 자체는 중복성과 algzye 파일을 메모리 또는 사용하는 것만 측정하려고합니다. Hadoop 무리.
한 가지 질문은 파일의 레코드 크기입니다. 즉, 오프셋이 바이트로 바이트를 변경하거나 파일이 1024b 블록으로 구성 될 수 있습니다. 데이터가 바이트 지향적이라고 가정하면 다음을 수행 할 수 있습니다.
파일 A에 대한 접미사 배열을 만듭니다.이 배열은 모든 인덱스 값의 파일 A에 대한 순열입니다. A a 2^37 바이트가있는 경우 인덱스 배열은 64 비트 정수로 가장 쉽게 표시되므로 모든 바이트 (오프셋으로 오프셋됩니다. 파일)은 인덱스 배열의 8 바이트에 해당하므로 인덱스 배열은 길이가 2^40 바이트가됩니다. 예를 들어 800GB. 인덱스 배열의 크기를 줄이기 위해 1024 번째 위치마다 색인화 할 수도 있습니다. 그런 다음 복사 가능한 조각의 평균 실행 시간에 따라 포장 품질을 발견합니다.
이제 오프셋 O = 0에서 시작부터 시작한 파일 B를 탐욕스럽게 포장 한 다음 인덱스 배열을 사용하여 'O'에서 시작하는 데이터와 일치하는 A에서 가장 긴 일치를 찾으십시오. 포장 된 파일에서 쌍을 출력합니다. 이것은 16 바이트를 인코딩하지 않고 케이스를 사용하므로 실행이 <16 바이트 인 경우 실제로 공간을 잃습니다. 비트 레벨 인코딩을 사용하고 비트 마커를 사용하여 분리 된 바이트 (마커 + 8 비트 = 9 비트) 또는 오프셋/길이 쌍 (마커 + 40 비트 + 40 비트 = 81 비트), o에서 가장 긴 조각을 포장 한 후 조각 후 다음 바이트로 O를 증가시키고 파일 끝까지 반복하십시오.
접미사 어레이의 구성 및 사용은 쉽고 참조를 쉽게 찾을 수 있습니다. 고속 응용 분야에서 사람들은 접미사 트리 또는 접미사 트리를 대신 사용하여 조작하기가 더 복잡하지만 더 빠른 조회를 제공합니다. 귀하의 경우에는 보조 스토리지에 배열이 있고 포장 단계의 실행 속도가 문제가되지 않으면 접미사 배열이 충분해야합니다.
