A Low-bandwidth Network File System – MIT LAB for Computing science

Deduplication – LBFS

A Low-bandwidth Network File System – MIT LAB for Computing science

 

중복 제거 시스템은 해싱, 비교 연산, 입출력 작업, 데이터검색 그리고 네트워크 전송과 같은 세부작업들로 이루어진다. 중복 제거 시스템은 중복 제거의 핵심적인 기능이 어디에 위치하느냐에 따라 소스 기반 접근방식(SBA)과 타겟 기반 접근 방식(Target-based approach)로 분류 된다. 즉, 클라이언트에서 중복 제거 기능이 수행되어 동작이 되는 경우에는 소스 기반으로 분류하고, 중복 제거 서버에서 중복 제거 기능을 수행하는 경우에는 타겟 기반 접근 방식으로 분류된다. 타겟 기반 방식은 클라이언트로부터 데이터를 전송 받는 즉시 중복 제거를 수행하는 인라인 접근 방식(ILA)와 데이터를 임시 저장한 이후에 중복 제거를 수행하는 포스트 프로세스 방식으로 분류된다.

 

1. Deduplication

- 중복되는 데이터를 제거하고 하나의 데이터를 공유하는 것

- 데이터 동일 여부 판단을 위해 데이터를 비교해야 한다.

- 데이터 비교는 처리비용이 크다.

2. Deduplicaton Strategy

1) Chunking

- Data를 Chunk 단위로 나누는 거

- 각 Chunk 별로Fingureprint를 구한다.

 

 

- Static chunking : 고정된 크기로 Chunk를 나눔

- Varlable-sized chunking : 다양한 크기로 Chunk를 나눔

 

2) Deduplicaton

1) Fingureprinting – 동일한 Chunk를 공유한다.

2) Delta-Encoding – 비슷한 Chunk가 있으면 차이점만 저장한다.

 

 

 

3. Chunk

- Fingerprint를 구해서 비교하는 데이터 단위

- Static Chunking

- Chunk 크기가 고정되어 있어 처리가 빠름

- 그러나 동일한 데이터가 align 되지 않으면 인식 불가능하다.

 

 

 

 

- Content-defined Chunking

- Chunk의 크기가 가변하며, 데이터의 이동에 덜 영향 받는다.

- Chunking에 많은 연산이 필요하다.

 

 

 

 

 

 

4. Fingerprinting

- 데이터를 대표할 수 있는 값을 우선 비교

- 해쉬함수(SHA-1, MD5)등이 주로 사용됨

- 데이터를 비교하기전에 해시끼리 비교

- 해시의 collision 발생 가능성이 높으면 데이터를 비교하는 과정이 필요함

- 상대적으로 처리가 빠르지만 fingureprint들을 보관하는 index가 큼

 

5. Delta-encoding

- 유사한 데이터간의 차이점만을 저장

- Index가 작지만, 연산량이 많음

- Delta 데이터 저장시 alignment 문제 발생

- Unique data의 보존이 필요함

 

 

네트워크 대역폭과 저장 효율을 향상시키려는 방법은 현재 Rsync , Venti, LBFS, TTTD, DRED, ZHE등 여러 방면에서 진행되고 있다. 본 Paper에서는 LBFS방식에 대해 연구하였으며, 향후 다른 방식에 대해 연구할 예정이다.

 

LBFS

 

LBFS는 품질이 좋지 않은 네트워크 환경을 위해 설계된 네트워크 파일 시스템이다. 네트워크의 연결이 중단되고 다시 연결되어도 데이터 전송이 가능하도록 프로토콜을 설계하였고, 네트워크 대역폭을 절약하기 위해 동일한 데이터의 재전송을 막는 기법을 고안하였다. LBFS에서는 CDC(Condent-define Chunks) 방식을 사용하며 Rabin Fingureprint로 해시 작업을 수행한다. 특별한 값을 반환하는 앵커(Anchor) 블록을 파일에 삽입하고 데이터 전송 전에 앵커사이의 블록을 SHA-1, MD5같은 해시 함수를 사용해 해시를 생성한다. 그리고 클라이언트에서 해시를 전송하여 서버에 캐싱된 해시 룩업 테이블과 비교하여 중복을 검색함으로서 중복 제거 시스템이 동작된다.

 

 

 

 

1. LBFS Solution

1) 유사도 비교

LBFS는 파일 내에서 중복을 식별한다. 또한, 파일이 계속해서 수정 될것이라 가정하고, 여러 버전에 걸쳐 중복을 식별하고 그 공통점을 찾는다. LBFS는 가변길이 중복제거 방식으로서 일정 크기의 블록을 라빈(Rabin) 해시하고, 라빈 해시값을 블록크기로 나누어 나머지가 0일 경우 경계로 하여 블록을 나누고 경계 사이의 블록들의 SHA-1해시를 계산한다. 이후 해시 비교를 통해 중복을 찾는다. 이때 최소 블록 값, 최대 블록 값을 설정하여 블록의 크기가 작거나 큰 것을 방지한다. 유사도 비교의 경우 라빈 해시 를 통하여 전체 데이터에 대한 라빈 해시 값을 구한다. 결과 값은 모든 라빈 해시 값들을 내림차순 또는 오름차순으로 정렬하여 일부의 상위 해시 값들을 대표값으로 한다.

 

 

< 파일 유사도 해시 추출 기법 >

 

위 그림은 바이트들로 구성된 파일 스트림이 있고 일정한 크기의 블록에 대해서 해시 값을 구하고 있다. 파일 유사도 해시는 두 파일 간에 공통된 데이터 블록이 얼마만큼 존재하는지 예측하기 위한 방법으로 사용된다. 라빈해시를 통해 파일에 포함된 일정한 크기의 블록에 대해 해시 값을 계산하고 그중 상위 값을 갖는 9912, 9183, 8155의 해시를 선택한다. 모든 블록에 대해 해시를 구하고 그중에서 상위 해시를 선택하므로 파일간에 유사도 해시 개수의 비율을 정확하게 예측한다.

 

2) LBFS

 

< 그림1. LBFS가 파일을 나누기 전과 일련의 편집 후 청크 경계가 일어난 모습 >

a. 각각 48 바이트 영역이 해시에 의해 결정된 브레이크포인트(Marker)를 가진 가변길이의 청크로 나뉘어지는 원본 파일을 나타낸다

b. 약간의 텍스트를 파일에 삽입했을 경우 텍스트는 새로운 더 큰 청크 C8을 만들면서, 청크 C4에 삽입한다. 그러나 다른 모든 청크는 똑같이 그대로 유지된다. 그러므로 이미 Old-Version을 가지고 있는 데이터 파일에 새로운 파일을 보내기 위해서는 단지 C8만을 보내면 된다.

C. 브레이크 포인트를 포함하여 삽입되는 데이터를 보여준다. 바이트는 새로운 C9와 C10으로 분활하면서 C5에 삽입 된다. 다시 파일은 2개의 새로운 청크를 보냄으로서 이동될 수 있다.

d. 브레이크 포인트의 한 부분이 제거되는 것을 보여준다. 이전 버전의 파일의 청크 C2와 C3는 새로운 파일을 구성하기 위해 새로운 청크 C11으로 결합된다.

 

3. LBFS 구조

시스템은 클라이언트와 서버로 구성되며 클라이언트는 XFS를 이용하는 파일 시스템을 실행하며, 서버는 NFS를 통해 파일에 접근한다. 클라이언트와 서버는 Sun RFC를 이용하여 TCP를 통해 서로 통신한다. 서버와 클라이언트는 동일한 Chunk Index(데이터베이스)를 유지하며 클라이언트에서 서버로 라빈해시들의 정보를 보내며, 서버는 이를 바탕으로 룩업테이블을 통해 비교하여 중복을 감지한다. 하지만 LBFS는 동시성 데이터베이스 업데이트를 회피하며, 서버는 항상 새로운 청크를 삽입하기전에 클라이언트에게 먼저 알린다.