Improving disk I/O efficiency using cross-layer information sharing

국문 초록 (Abstract)

빠른 저장과 정보 검색 현대 컴퓨팅 시스템이 풀어야 할 핵심 과제 중 하나이다.
지난 수십 년 동안 대표적인 보조 저장 장치였던 마그네틱 하드 디스크 드라이브는
마이크로 프로세서 및 메모리와의 성능 격차 증가로 인해 전체 시스템의 주요한 성능 병목 대상이 되었다.
이러한 성능 격차를 완화하기 위해서 기존 스토리지 스택은 길고 복잡하게 진화하였다.
현대 스토리지 시스템의 계층적인 디자인은 그러나 정보 은폐라는 근본적인 문제점을 안고 있다.
현대 스토리지 시스템의 좁고 단순한 인터페이스는 필연적으로 각 계층이 가지고 있는 많은 정보들을 숨긴다.
그 결과, 정보 은폐는 디스크 드라이브의 보다 효율적인 사용을 저해할 가능성이 높게 된다.
우리는 계층별 정보의 공유를 기반으로 스토리지 시스템에서의 협업이 디스크 입출력 효율성을
개선하는데 도움이 될 것으로 믿는다.

본 학위 논문에서는 디스크 입출력 시스템에서의 정보 공유의 필요성과 장점을 연구한다.
우리는 우선적으로 어떠한 정보가 계층간에 공유되어야 할지에 대해 초점을 맞춘다. 우리는
현대 디스크 드라이브의 세부적인 메커니즘을 분석하여 운영체제와 저장 장치 사이의 의미론적인
차이 (semantic gap)이 존재함을 밝힌다. 이를 위해서 우리는 현대 디스크 드라이브의 저수준 정보를
추출할 수 있는 소프트웨어 도구를 설계 및 구현한다. 동시 갱신 캐싱 (write-through caching) 기법이
적용된 디스크에서의 의미론적인 차이의 문제를 해결하기 위해서, 우리는 요청 인터리빙 (request
interleaving) 이라는 블록 계층의 기법을 제안한다. 본 기법은 운영체제의 입출력
스케줄링 결정에 디스크의 저수준 정보를 반영하여 동시 갱신 캐싱 기법이 적용된 디스크에서
관찰되는 긴 지연 시간을 피하도록 근접 거리의 쓰기 요청들을 재배치 하는 것이다.

우리는 또한 계층간 정보 공유를 활용하여 기존 저장소 시스템에 적용된 입출력 최적화 기술을
강화하는 방법을 연구한다. 파일 시스템이 유지하는 블록 생존 (block liveness) 정보를
통해서 비연속적인 요청을 병합할 수 있도록 기존의 요청 병합 (request merging) 기법의
적용 범위를 확장한다. 우리는 이러한 기법을 요청 브리징 (request bridging)이라 일컫는다.
이 기법을 통해서 우리는 불연속적인 여러 쓰기 요청들을 더 큰 요청들로 병합할 수 있으며,
하나의 입출력 요청이 담고 있는 데이터의 크기를 늘림으로서 디스크의 입출력 지연시간을 분할
시킬 수 있다. 우리의 성능 평가는 병렬 입출력 응용 프로그램에서 우리의 기법이 상당한 성능의
향상을 가져온다는 것을 보여주고, 동시에 처리되는 읽기 요청의 성능 역시 향상된다는 것을 보여준다.

다국어 초록 (Multilingual Abstract)

Fast storage and retrieval of information is one of the key challenges for modern computing systems. Magnetic hard disk drives as secondary storages over the past
decades became a major performance bottleneck due to the increasing gap with microprocessor andmemory. In order tomitigate the gap, the existing storage stack
evolved to be long and complex. Hierarchical design in modern storage systems has a fundamental drawback of an information gap: Narrow and simple interfaces
over the storage stack hide much information into the inside of each layer. As a result, the information concealment is likely to hinder more efficent usage of disk drives.We believe collaborating in disk I/O subsystem based on informatin sharing
would help improving disk I/O efficiency.

In this dissertation, we study benefits of information sharing in disk I/O subsystems.
We first focus on what information is useful to be shared. We study the
semantic gap between hostOS and storage devices by examining the delicatemechanisms
of modern disk drives. For this, we design and implement a software tool
which can extract the low-level information from modern disk drives. To address
the semantic gap observed in write-through caching disk, we propose Request interleaving,
a block-level technique applying the low-level disk information into the
scheduling decision. This technique reorders write requests in close proximity to
avoid their long latency observed inwrite-through caching disk.We also study how
to strengthen the existing disk I/O optimization techniques using the shared information.
Using the block liveness information of filesystems, we extend the range
of request merging technique into the non-successive requests. We call it Request
bridging. We can coalesce separate write requests into larger ones, thus amortize
the disk latency across more bytes of data. In our evaluation, the performance benefit
for these parallel I/O applications is shown to be significant as we expected.
Our evaluation also convinces us that the performance benefit in write requests
can also increase the competitive reads in real-world workloads.

목차 (Table of Contents)

• 1.INTRODUCTION 10
• 1.1 Information Sharing in Disk I/O Paths 11
• 1.2 Case study: Request Bridging and Interleaving 13
• 1.3 Evaluation 14
• 1.4 Contributions 16
• 1.5 Organization 17
• 2. BACKGROUND AND RELATED WORK 18
• 2.1 Background 18
• 2.1.1 Disk terminology 18
• 2.1.2 Disk buffer 19
• 2.1.3 Disk controller mechanism 20
• 2.2 Related Work 21
• 2.2.1 Low-level Disk Feature Extraction 21
• 2.2.2 Block-level I/O optimization in disk I/O layers 23
• 2.2.3 Cross-layer information sharing 24
• 2.2.4 Utilizing disk layout information and operational characteristics 24
• 3. CROSS-LAYER INFORMATION SHARING IN DISK I/O PATHS 26
• 3.1 Diskclose: Uncovering the Internal Layout of Storage Devices 26
• 3.1.1 Overview 26
• 3.1.2 Multidimensional disk layout model 28
• 3.1.3 Extraction methodology of layout model parameters 30
• 3.1.4 Inferring two-dimensional arrangement in a track group 37
• 3.1.5 Experimental result 42
• 3.1.6 Model verification and discussion 48
• 3.2 Analyzing Disk I/O Activity 49
• 3.2.1 Disk I/O trace environments 52
• 3.2.2 Disk access pattern from multiple I/O stream workloads 54
• 3.2.3 Disk I/O activity analysis of write requests in close proximity 58
• 3.3 Sharing Semantic Information Stored in Disk Blocks 60
• 3.3.1 Design 60
• 3.3.2 Explicit notification interfaces 64
• 3.3.3 Guaranteeing system consistency 65
• 3.3.4 Implementation 67
• 4. CASE STUDY 70
• 4.1 Request Interleaving 70
• 4.1.1 Main idea 71
• 4.1.2 Determining a decision point for Request Interleaving 74
• 4.1.3 Guaranteeing data and system consistency 77
• 4.1.4 Implementation issues 77
• 4.2 Request Bridging 79
• 4.2.1 Overview 79
• 4.2.2 Block liveness checking 81
• 4.2.3 Page cache lookup in block I/O layer 81
• 4.2.4 Implementation 84
• 5. PERFORMANCE EVALUATION 86
• 5.1 Write throughput 90
• 5.2 Request distribution 95
• 5.3 Maximum queue depth in disk drive 97
• 5.4 File system and scheduling algorithm effects 100
• 5.5 Write-back cache vs. Write-through cache 103
• 5.6 Limitations and Discussion 106
• 6. CONCLUSIONS 108
• 6.1 Future Work 108
• 6.1.1 Extraction Time in Diskclose 108
• 6.1.2 Utilizing semantic information of blocks stored in disk drive 108
• 6.1.3 Information sharing in RAID disks 109
• 6.2 Summary 110