It is very important to improve the read and write performance of RAID. The write performance of RAID is related to disk scheduling algorithms and destage algorithms. The read performance of RAID is associated with prefetching and caching technologies. This thesis presents a destage algorithm for fragmented writes in RAID, prefetching algorithms that resolves the fundamental problems of sequential prefetching when it confronts with striped disk arrays, and a sophisticated prefetching and buffer management algorithm that resolves five problems that are newly addressed in this thesis.
Contiguous reads and writes outperform fragmented reads and writes even though the starting positions and the end positions of the kinds of I/O are the same, fragmented reads and writes are forcefully transformed into contiguous reads and writes via a proposed matrix-stripe-cache-based contiguity transform (MSC-CT) method, which employs a rule of consistency for data integrity at the block level, and a rule of performance that ensures no performance degradation. MSC-CT performs at destage in a redundant rray of independent disks (RAID) array.
Traditional studies on disk arrays have focused on parallelism or load balance of disks. However, this thesis reveals that the independency of disks is more important than parallelism for concurrent reads of larger numbers of processes in striped disk arrays, whereas parallelism is only significant for concurrent reads of small numbers of processes. Hence, this thesis propose two types of sequential prefetching: strip-aligned sequential prefetching (SASEQP) for independency and massive stripe prefetching (MSP) for parallelism.
Conventional prefetching schemes regard prediction accuracy as important because useless data prefetched by a faulty prediction may pollute the cache. If prefetching requires considerably low read cost but the prediction is not accurate, it may or may not be beneficial depending on the situation. However, the problem of low prediction accuracy can be dramatically reduced if we efficiently manage prefetched data by considering the total hit rate for both prefetched data and cached data. To achieve this goal, we propose an adaptive strip prefetching (ASP) scheme, which provides low prefetch cost and evicts prefetched data at the proper time by using differential feedback that maximizes the hit rate of both prefetched data and cached data in a given cache management scheme. Additionally, ASP controls prefetching by using an online disk simulation that investigates whether prefetching is beneficial for the current workloads and stops prefetching if it is not. Finally, ASP provides methods that resolve both independency loss and parallelism loss that may arise in striped disk arrays.
We implemented a kernel module in Linux version 2.6.18 as a RAID-5 driver with our scheme. MSC-CT delivers a peak throughput that is 3.2 times higher than a case without MSC-CT on representative workloads. ASP outperforms a hardware-based RAID by 11 times in an experiment. The combinational approach of SASEQP and MSP outperforms the sequential prefetching of Linux by 3.2 times in an experiment. The proposed schemes can be combined altogether. The experimental results demonstrate that the proposed schemes are extremely simple to implement, have low overhead, and are ideally suited for RAID controllers, are beneficial to random writes, sequential writes, various types of sequential reads, and non-sequential reads in various realistic scenarios.
RAID의 읽기와 쓰기의 성능을 개선하는 것은 매우 중요하다. RAID의 쓰기 성능은 디스테이징(destaging)과 디스크 스케줄링이 읽기 성능은 프리페칭과 캐시가 관련 있다. 이 학위논문에서는, RAID에서 조각화된 쓰기를 위한 디스테이징 알고리즘과; 순차 프리페칭이 스트라이핑 디스크 어레이를 만났을 때 발생되는 근본적인 문제들을 해결하는 프리페칭 알고리즘들과; 이 논문에서 새롭게 제기되는 다섯 가지 문제를 해결하는 세련된 프리페칭과 버퍼 관리 알고리즘을 제시한다.
캐시와 디스크 사이의 연속적인 읽기와 쓰기가 시작과 끝이 같을 지라도 조각화된 읽기와 쓰기보다 빠를 때에, 제안된 행렬-스트라이프-기반 연속성 변형(MSC-CT)을 통하여 조각화된 읽기와 쓰기를 연속적인 읽기와 쓰기로 변환시킨다. MSC-CT는 블록 수준에서 데이터의 무결성을 위한 일관성 법칙과 성능저하가 없도록 해주는 성능 법칙이 제안된다. RAID-5에서의 쓰기 요청은 패리티 갱신을 위한 읽기와 디스크로의 쓰기를 포함한다. MSC-CT는 기존의 디스크 기술들과 호환된다.
디스크 어레이에 관한 기존 연구들은 디스크들의 병렬성과 부하 균형에 초점을 맞추었다. 그러나 이 학위논문은 스트라이핑 디스크 어레이와 프리페칭과의 새로운 현상을 밝힌다. 그 현상은 다음과 같다. 스트라이핑 디스크 어레이에 있어서, 다수의 프로세스가 발생하는 동시 읽기들에 대해서 디스크들의 독립성이 병렬성보다 더 중요하다. 반면에, 병렬성은 작은 수의 프로세스의 동시 읽기에 대해서 중요하다. 그래서 이러한 새로운 문제를 해결한 두 가지 종류의 순차 프리페칭을 제안한다. 그것은 독립성을 위한 스트립-정렬 순차 프리페칭(SASEQP)과 병렬성을 위한 대량 스트라이프 프리페칭(MSP)이다.
기존의 프리페칭 기술들은 예측의 정확성을 중요하게 다루었다, 왜냐하면 잘못된 프리페칭으로 프리페치된 불필요한 데이터는 캐시를 오염시키기 때문이다. 만약 프리페칭이 상당히 낮은 읽기 비용을 요구하지만 그 프리페치가 그리 정확하지 않다면, 그것은 상황에 따라서 이득일 수도 있고 아닐 수도 있다. 그러나 만약 프리페치된 데이터와 캐시될 데이터를 동시에 고려하여 프리페치된 데이터를 효과적으로 관리한다면 낮은 예측 정확성의 문제는 효과적으로 줄어들 수 있다. 이 목적을 달성하기 위해서, 적응적 스트립 프리페칭(ASP)을 제안한다. 이 기법은 낮은 프리페칭 비용을 제공하고, 주어진 캐시 관리 기법 하에서 프리페치된 데이터와 캐시된 데이터의 총 적중률을 최대화하는 미분 되먹임 방법을 이용하여 프리페치된 데이터를 적절한 시간에 퇴출한다. 더구나 프리페칭이 읽기 시간의 측면에서 현재 작업 부하에 이로운지 검사하는 온라인 디스크 시뮬레이션을 이용하여 프리페칭이 제어된다.
리눅스 커널 2.6.18에서 상기 제안된 알고리즘들을 포함하는 RAID-5 드라이버를 구현하였다. 주어진 실험에서 MSC-CT는 MSC-CT가 없는 경우에 비하여 최대 3.2의 성능을 제공하였다. 어떤 실험에서, ASP는 하드웨어 기반 RAID보다 11배 더 좋은 처리량을 보였다. SASEQP와 MSP를 결합하는 방법은 리눅스의 순차 프리페칭을 3.2배 앞섰다. 제안된 방법들은 모두 같이 결합될 수 있다. 실험 결과들은 제안된 기법들이 구현이 쉽고 부하가 낮고, RAID 제어기에 이상적이고 임의 쓰기와 순차 쓰기와 다양한 형태의 순차 읽기와 비 순차 읽기에 이롭다는 것을 보인다.
