Deduplication기법

Deduplication기법

 

Deduplication기법의 핵심 기술은 스토리지를 저장하는 과정에서 기존 데이터와 비교하여 같은 데이터의 백업을 필러팅 하는 것입니다. 그런 다음 포인터를 통해 기존 데이터에 연결하는 것입니다. 업계에서는 중복제거(Deduplication)의 처리 시간을 감소하는데 집중합니다.

파일 수준의 중복 제거

파일 수준의 중복 제거는 말 그대로 파일 전체가 중복되는 경우에만 중복 제거를 수행하는 방식으로 SIS(Single Instance Storage)라고도 불린다. 중복되는 파일이 많은 경우 손쉽게 구현될 수 있다는 장점이 있으나 효율성 면에서는 바람직하지 못하다. 예를 들어, 두 파일이 딱 1비트만 달라도 서로 다른 파일로 인식되기 때문이다.

데이터 블록수준의 중복 제거

반면 한 파일을 블록(혹은 청크, 세그먼트) 단위로 나누거나 비트 단위의 중복 제거를 수행하는 방식이 있다. 중복되는 블록은 오직 한번 저장되고, 그 블록을 가리키는 포인터를 저장함으로써 추후에 파일을 재조합할 수 있다. 당연히 효율성 면에서는 파일 수준의 중복 제거보다 훨씬 뛰어나다. 블록 수준의 중복 제거는 다시 두가지로 나뉠 수 있다. 블록의 크기가 고정되어있는 고정 길이 방식과 블록의 크기가 가변적인 가변 길이 방식이 그것이다. 일반적으로 블록의 길이를 최적화 할 수 있고, 중복된 블록의 파일 내 오프셋 변경이 가능한 가변 길이 방식이 더 효율적이다.

Muthitacharoen A, Chen B, Maziéres D,"A low-bandwidth network file system" In: Proc. of the 18th ACM Symp. on Operating System Principles (SOSP 2001). New York: ACM Press, 2001. 174−187.

LBFS는 MIT에서 개발 한 네트워크 파일 시스템입니다. 목표는 전송 대역폭을 줄이는 것입니다. 데이터 청크가 전송하기 전 대상 컴퓨터에 있는지 판단하고 있으면 데이터 청크를 보내지 않습니다. LBFS는 SHA-1값의 앞64자리로 청크인덱스로 합니다. 비동기 업데이트를 쓰고 서버측에서 먼저 클라이언트측에게 응답을 하고 자체의 데이터베이스를 업데이트합니다. 따라서 LBFS는 데이터베이스에 있는 청크의 hash 값을 이용하는데 데이터베이스 시스템에 의존하지 않습니다. 노드B와 노드A는 동일한 데이터베이스 인덱스 번호를 사용합니다. LBFS의 주요 공작원리는 아래와 같습니다.

 

 

 

 

 

X'파일중청크hash값을

서버A에게 준다

 

 

hash값이 같지않는 데

이터청크만 전송

 

LBFS의 가장 큰 장점의 하나는 두 개의 파일만 고려한다는 것입니다. 단점은 파일중의 중복 데이터가 여러 파일에 배포 되여 있을수 있다는 것입니다. 이러한 방법으로 검증할수 있는 반복 데이트가 제한되여 있습니다. LBFS는 청크의 익스트림현상을 방지하기 위하여 취소치와 취대치값을 설정하였습니다. LBFS테스트 데이터중 moving window크기는 48bytes, 평균 청크 크기는 8kb, 최소 청크 크기는2kb, 최대 청크 크기는64kb로 되였습니다.