Data Deduplication Using Dynamic Chunking

Data Deduplication Using Dynamic Chunking

- 고정된 길이의 Chunking 과 파일 유사성 기술을 이용하는 동적 Chunking 방법

 

파일 유사성 정보를 통하여 중복된 데이터를 찾는다는 아이디어를 가진 이 논문은 파일 유사성 정보 내에 해시 키 값과 파일 오프셋을 비교함으로써 중복된 점을 찾는다. 2개의 파일 사이에 해시를 비교함으로써 중복된 영역을 파일에서 찾을 수 있다. 똑같은 해시키가 있다면, 고정 Chunking을 적용한 파일 오프셋을 이용하고, 그 외에는 데이터 중복 제거를 건너 뛴다.

 

System Design

 

이 논문의 핵심 개념은 2개 파일 사이에 중복된 점을 알기 위해 파일 유사성 정보를 적용하는 것이다. 2개의 파일 사이의 유사성의 정도를 알기 위해 대표 해시 리스트를 이용한다. 모든 파일에 대하여Rabin 해시 함수를 통해 각 바이트 마다 해시 값을 계산하고, 이중에 최대값을 가지는 해시 값을 대표 해시 값으로 선정한다.

 

 

 

위 알고리즘은 파일로부터 연속적으로 파일 유사성 정보를 받는 내용을 담고 있다.

Seek() 함수를 통해 현재 파일의 위치를 찾는다. 현재 위치의 바이트로 Rabin 해시 함수를 통해 해시 값을 얻는다. 해시 값이 hasharray의 해시값보다 더 크면 hasharray의 작은 해시 값 대신에 넣는다.

위 그림은 대표 해시 값을 이용하여 파일 간에 중복된 점을 찾는데 이용하는 것을 보여주고 있다. target 파일은 서버에 위치하고 source파일은 클라이언트에 위치한다. 클라이언트는 target파일을 수정함으로써 소스 파일을 만든다. 위 그림의 예를 보면 a앞에 새로운 블록을 삽입하고 b블록 앞을 삭제하고 뒤에 246개의 바이트 데이터를 삽입한다. 대표 해시값을 통해 중복된 점 a와 b를 얻을 수 있다. 그리고 오프셋 정보를 통하여 파일 어디에 위치하는지 정보를 알 수 있다. *Diff(해시값의 오프셋 – 블록의 시작 오프셋)

 

첫째로, 클라이언트는 중복된 파일을 검색하기 위해 대표하는 해시 값을 검색한다.

클라이언트가 대표 해시 값을 발견하지 못하면, Rabin 해시 함수를 이용하여 계산한다.

둘째로, 클라이언트는 대표 해시 값을 서버로 보낸다. 서버는 서버와 파일 간의 해시 값을 비교함으로써 가장 비슷한 대표 해시 값을 찾는다. 비슷한 값을 찾는다면, 그것에 대해 diff(차이값)을 계산하여 중복된 점을 계산한다. diff는 블록의 시작 오프셋과 대표 해시값의 시작 오프셋 간의 차이로 구할 수 있다. 클라이언트는 동적 Chunking에서 발생된 Lookup정보를 보낸다. 서버는 lookup목록을 체크하고 중복되지 않은 청크 정보를 클라이언트로 보낸다. 마지막으로 클라이언트는 중복되지 않은 청크를 서버로 보낸다.