Selective Data Deduplication and Buffer Cache Management for Primary Storage System

Abstract

This thesis studies one of most important factor for a primary storage system: an effective management of storage space and an effective management of buffer cache replacement. To achieve effective storage space management, we introduce data deduplication techique that targets primary storage systems and to achieve effective I/O performance management, we introduce a buffer cache management. This thesis consists of two parts. In Part I, selective data deduplication for primary storage system is described. Data deduplication is a technology that eliminates redundant data to save storage space. Most previous studies on data deduplication target backup storage, where the deduplication ratio and throughput are important. However, data deduplication on primary storage has recently been receiving attention; in this case, I/O latency should be considered equally with the deduplication ratio. Unfortunately, data deduplication causes high sequential-read-latency problems. When a file is created, the file system allocates physically contiguous blocks to support low sequential-read latency. However, the data deduplication process rearranges the block mapping information to eliminate duplicate blocks. Because of this rearrangement, the physical sequentiality of blocks in a file is broken. This makes a sequential-read request slower because it operates like a random-read operation. In this part, we propose a selective data deduplication scheme for primary storage system. A selective scheme can achieve a high deduplication ratio and a low I/O latency by applying different data-chunking methods to the files, according to their file access characteristics. In the proposed system, file accesses are characterized by recent access time and the access frequency of each file. No chunking is applied to update-intensive files since they are meaningless in terms of data deduplication. For sequential-read-intensive files, we apply big chunking to preserve their sequentiality on the media. For random-read-intensive files, small chunking is used to increase the deduplication ratio. Experimental evaluation showed that the proposed method achieves a maximum of 94% of an ideal deduplication ratio and 93% of the sequential-read performance of a native file system. In Part II, an effective buffer cache management technique is described. All the existing sophisticated cache algorithms are proposed to maintain meaningful entries that are likely to be re-accessed based on their observations or empirical heuristics. In this part, we concentrate on what entries should be excluded for a buffer cache. Careful analysis on real- world workloads leads us to observe that about 50% - 95% blocks are accessed less than three times. These infrequently accessed blocks are likely to cause high cache pollution by evicting out meaningful blocks from the cache. In addition, we observe those infrequently accessed blocks have certain access characteristics in terms of reuse distance: extremely long or short reuse distance. Based upon our observations, we propose an algorithm named FRD (Filtered buffer cache algorithm based on Reuse Distance). In this algorithm, we can effectively and simply exclude such infrequently accessed blocks from being cached. In addition, it can be simply implemented with O(1) time complexity by two LRU stacks. The experimental results show that FRD algorithm outperforms state-of-the-art cache algorithms such as LIRS and ARC.

본 연구는 주 저장장치에서 가장 중요한 부분인 저장공간의 효율적인 관리 방법과,입 출력 성능의 효율적인 관리 방법을 기술한다. 저장 공간의 효율적인 관리는 데이터 중복 제거 기술을 주 저장장치에 도입하여 해결할 수 있으며, 또한 입출력 성능 관리는 효과 적인 캐싱 기법을 통해 해결할 수 있다. 본문은 두 개의 파트로 나누져 있으며, 각 파트를 요약하면 다음과 같다. 파트 I은 선택적 중복 제거 기술에 대한 내용이 기술되어 있다. 데이터 중복 제거 기술은 저장 장치 내부의 중복된 자료를 검출 후 제거하여, 저장 장치의 공간을 더 효율적으로 사용할 수 있도록 해주는 기술이다. 기존에 제안되었던 중복 제거 기술은, 중복 제거율과 Throughput 이 중요한 백업 저장 장치를 기술 적용 대상으로 선정하여 연구되어 왔다. 그러나 점차 늘어나는 컨텐츠 크기들로 인해, 주 저장 장치에서의 중복 제거 기술의 중요 성이 점점 주목을 받고 있다. 주 저장 장치는 백업 장치와는 다르게, 빠른 입출력 레이턴 시가 중복 제거율 만큼 중요하게 고려되어야 한다. 그러나 데이터 중복 제거 기술은 순차 읽기 연산에 대해 높은 읽기 레이턴시를 발생하게 되는 심각한 문제가 있다. 일반적으로 파일 시스템은 새로운 파일이 생성될 때, 해당 파일의 순차적 읽기 성능을 확보하기 위해, 최대한 물리적으로 연속된 블록을 할당 시켜주어, 낮은 레이턴시의 순차 읽기가 가능해 진다. 그러나 데이터 중복 제거 기술은 중복된 데이터를 제거하고, 제거된 데이터에 대한 매핑을 동일한 내용을 가진 다른 위치의 블록으로 변경하기 때문에, 파일 시스템이 구 성해 둔, 물리적 연속성을 깨어지게 하는 문제를 가져온다. 이로 인해, 순차 읽기 요청은 마치 임의 읽기 요청처럼 처리되어, 순차 읽기 성능이 심각하게 저하 된다. 본 파트에서는 주 저장 장치를 위한 선택적 중복 제거 기술을 제안한다.선택적 중복 제거 기술은 개별파일의 접근 특성을 파악해서, 파일별 다른 데이터 청킹 기법을 적용하는 것으로 구성되어, 높은 중복 제거율을 보이면서, 또한 동시에 낮은 순차 읽기 지연시간을 지원하게 된다. 본 연구는 파일 접근 특성을 개별 파일의 최근 접근 시간과, 접근 빈도를 통해 구분한다. 본 연구에서 제안하는 방법에 따르면 업데이트가 자주 일어나는 파일들은 중복 제거의 효과가 없기 때문에 중복 제거 대상에서 제외되고, 순차 읽기가 주로 발생하는 파일들은 파일의 물리적 연속성을 최대한 보장하여 낮은 순차 읽기 지연을 얻기 위해, 큰 크기의 청크 단위로 중복 제거를 수행하고, 임의 읽기가 주로 발생되는 파일들은 최대한 높은 중복제거율을 학보하기 위해 작은 크기의 청크 단위로 중복 제거를 수행한다. 본 연구의 실험결과, 제안하는 방법은 이상적인 중복 제거율의 86%까지 중복 제거를 수행하면서, 동시에, 네이티브 환경 대비 97%의 순차 읽기 성능을 나타낸다. 파트 II는 효과적인 버퍼캐시 관리 기법에 대한 내용이 기술되어 있다. 기존의 버퍼캐 시 알고리즘은 캐시 적중률을 높이는데 있어, 어떤 블록들이 재 사용성이 높을 것인가? 라는 질문에 대한 해결책으로, 다양한 경험적 휴리스틱을 적용 하거나, 다양한 실험 결과 를 활용하여 새로운 캐시 알고리즘을 고안해 왔다. 본 파트는 기존의 연구와 다르게, 어떤 블록들이 캐시에 들어가서는 안되는가? 에 대한 질문으로 시작 한다. 본 연구의 다양한 실세계 워크로드 분석 결과, 약 50% - 95%의 블록들이 3번 이하의 접근 빈도를 나타내는 것을 확인 할 수 있었다. 이러한 사용빈도가 낮은 블록이 캐시로 진입하게 되면, 기존에 잘 유지되어 가까운 시간내에 캐시 적중이 날 가능성이 있는 블록이 제거되는 문제가 발생될 수 있다. 본 연구의 워크로드 분석에 의하면, 그러한 재 사용 빈도가 낮은 엔트 리들은 재사용 거리가 굉장히 길거나, 또는 굉장히 짧게 접근 되는 현상이 관찰 되었다. 본 관찰결과를 이용하여, 본 연구에서는, FRD(Filtered buffer cache algorithm based on Reuse Distance) 라는 알고리즘을 제안한다. 본 알고리즘은 접근 빈도수가 낮은 엔트리 들을 간단하면서도 효과적으로 캐싱이 되지 않도록 해준다. 또한, 이 알고리즘은 두 개의 LRU 스택을 이용해 O(1) 의 시간 복잡도를 가지도록 간단히 구현되며, 실험 결과, 현재 가장 좋은 성능을 보여주는 것으로 알려진 ARC, LIRS 와 같은 알고리즘보다 안정적으로 높은 캐시 적중율을 나타낸다.