Venti : a new approach to archival storage

Venti : a new approach to archival storage

 

Venti는 중복 데이터를 제거하여 저장하는 스토리지 시스템이며 파일을 고정된 크기의 블록으로 나누고 각 블록에 SHA1 해시를 적용하여 중복을 제거한다.

Venti특징

 

1. 다중 클라이언트와 응용프로그램에 의해 공유 되는 일 회 기록할 수 있는 아카이브 데이터 스토리지를 제공

2. 블록 단위의 네트워크 스토리지 시스템

3. 블록은 SHA1 해쉬 함수에 의해 해시 값으로 계산됨

4. Write once policy

Venti Archival Server

 

Venti Archival Server는 아카이브 데이터 처리를 위해 고안된 블록 수준의 네트워크 스토리지 시스템이며, 인터페이스는 클라이언트 애플리케이션이 가변성 규모의 데이터 블록을 읽고 쓸 수 있게 한 단순한 프로토콜이다. Venti는 해시를 통해 데이터 블록을 확인하며, 해시는 블록의 Fingerprint로 불리며, 판독을 위한 주소로서 이용된다. 즉 해시는 데이터 블록을 위한 이름 공간을 생성한 것이라고 할 수 있다. 다중 클라이언트는 이 이름 공간인 해시를 공유하고 Venti 서버를 공유할 수 있다. 또한 Venti는 데이터의 무결성 을 제공한다. 블록이 검색 될 때, 클라이언트와 서버 모두는 데이터의 Fingerprint를 계산하고 요청된 Fingerprint를 비교한다. 이러한 작업은 클라이언트가 발견되지 않은 데이터 파괴로부터 오류를 피하게 하고, 서버가 언제 오류 복구가 필요한지 확인 할 수 있게 해준다.

 

 

Venti 의 Hash 기능

 

클라이언트가 저장하는 모든 데이터블록을 위한 Fingerprint를 생성할 수 있는 Hash 함수가 필요하다. Venti는 SHA1해시함수를 이용한다. 이 해쉬 함수를 통해 클라이언트가 블록의 Fingerprint를 서버에 요청하고 반송된 Fingerprint가 일치하면 클라이언트는 서버가 이 데이터를 가지고 있다는 것을 알고 중복으로 간주하여 블록의 저장을 피할 수 있게 된다.

 

Application Using Venti

어플리케이션은 복잡한 데이터 구조를 저장하기 위해 밴티에서 제공된 블록 레벨 서비스를 사용한다. 데이터는 블록으로 나뉘어지고 서버에 기록 된다. 이 데이터가 검색 될 수 있게 하기 위해 어플리케이션은 이러한 블록의 Fingerprint를 등록하여야 한다. 본 논문의 접근 방법은 포인터 블록으로 Fingerprint를 묶는 것이다. 그림1와 같이 Recursive 트리 형태로 구성 된다. 데이터 블록은 Root Fingerprint 에 의해 다뤄지는 포인터 블록을 통해 위치 하게 된다. Venti의 1회 기록 성질은 트리가 수정될 순 없지만 그림2와 같이 새롭거나 수정된 데이터 블록을 저장하고 트리의 변하지 않는 부분을 재사용함으로써 효율적으로 생성 될 수 있다. Fingerprint가 똑 같은 거라면 블록은 새롭게 Venti에 쓸 필요가 없다. 대신에 적절한 포인터 블록으로 주소를 복사하여 사용할 수 있다. 이러한 최적화는 양쪽 네트워크의 대역폭을 세이브 시키는 효과를 불러온다. 다른 방식의 구조는 얼마든지 가능하며, Venti의 블록 레벨 인터페이스에서는 포맷의 형태를 클라이언트 애플리케이션에 맡기고, 이러한 다양한 데이터 구조는 단일 서버에서 공존할 수 있다.

Implement

Venti의 프로토타입의 구현은 데이터 블록로그와 이 로그에서 지문을 매핑하는 인덱스를 이용한다.

- Block Cash : 블록 캐시의 히트는 Index 검색과 데이터 로그에 대한 접근을 우회하면서 Fingerprint에 대한 데이터를 반환한다.

- Index Cash : 인덱스 캐시의 히트는 인덱스 검색에서 Hit된 인덱스를 제거한다.

클라이언트는 서버로 블록의 해시를 전송하고 서버는 블록이 저장유무에 따라 중복이 아닌지 확인한다.

본 논문의 접근은 블록을 위치시키는데 사용된 인덱스로부터 데이터 블록의 스토리지를 분리하는 것에 있다. 블록은 디스크 드라이브의 Raid계층의 추가 전용 로그에 저장된다.

데이터 로그는 Arena로 나뉘어 진다. Arena는 많은 수의 데이터 블록을 포함한다. 각각의 데이터 블록은 블록의 내용을 기술한 헤더에 의해 앞에 붙는다. 헤더의 주요 목적은 작동되는 동안 무결성 확인을 제공하고 데이터 복구를 지원하는 것이다. 헤더는 Magic Number, 블록의 Fingerprint와 Size, 블록이 첫번째로 쓰여진 시간과 그것을 사용한 사용자의 Indentity를 포함한다. 헤더의 Encoding은 데이터 압축에 쓰여진 알고리즘을 나타낸다. Eszie는 Arena의 다음 블록의 위치가 결정될 수 있게 하는 압축 뒤의 데이터의 사이즈를 나타낸다.

Arena는 데이터 블록 뿐만 아니라 헤더와 디렉토리, 트레일러를 포함한다. 헤더는 Arena의 식별 필드로 사용된다. 디렉토리는 블록 헤더를 복사한 것과 Arena내의 모든 오프셋을 포함한다. Arena내의 모든 블록의 헤더를 복사함으로서 서버는 시스템을 빨리 체크하거나 재축조할 수 있게 된다. 디렉토리는 Arena내의 한 부분이 파괴 당하거나 오류가 발생하면 오류 복구를 용이하게 해주는 역할을 담당한다. 트레일러는 블록의 수와 로그의 사이즈를 포함하여, Arena의 현재 상태를 요약한다. Arena가 다 채워지면 그것은 밀봉된 것처럼 표시되고 Arena는 Fingerprint로 계산되어 진다.

밴티의 기본 조작은 Fingerprint를 기반으로 블록을 저장하고 검색하는 것이다 Fingerprint는 160비트이고 가능한 Fingerprint의 수는 서버에 저장된 블록의 수를 훨씬 더 초과한다. Fingerprint의 수와 블록의 수의 불일치는 직접적으로 Fingerprint를 기억장치에서 위치를 매핑하는 것은 비 실용적이라는 것을 의미한다. 그러므로 로그 내에 블록을 위치시키기 위해 인덱스를 이용한다.

 

인덱스는 각각 단일 디스크 블록으로서 저장된 고정 크기의 버킷으로 나누어 진다. 각각 버킷은 Fingerprint 공간을 위한 인덱스 맵을 포함한다. 해시함수는 버킷을 Index에 넣기 위해 Fingerprint를 매핑하는데 사용되고 버킷은 이진 탐색을 사용하여 검사된다. 충분한 버킷으로 공급되면 인덱스 해시 테이블은 상대적으로 비어 있을 것이고 버킷 오버플로우는 매우 드물 것이다. 만약 버킷이 오버플로우를 하면 여분 엔트리는 인접 버킷에 위치하게 된다.

 

결론

 

Venti는 파일을 고정된 크기의 블록(8Kbyte)의 블록으로 나누고 각 블록마다 SHA1해시를 만들고 전송한다. 만약 블록의 해시가 저장 서버에 있을 경우 중복으로 간주하여 블록의 저장을 피한다. Venti는 이전 저장 정보가 없어도 델타(Delta) 백업의 효과를 낼 수 있다. Venti의 단점으로는 중복 데이터를 놓치는 경우가 발생하는 것을 들 수 있는데 왜냐하면 파일을 수정하거나 데이터가 변경되는 경우 중복 블록들의 오프셋 위치가 달라지고 이로 인해 수정이 가해진 뒷 부분의 블록을은 다른 해시 값으로 계산하기 때문이다.