Optimizing block I/O subsystem for fast storage devices

다국어 초록 (Multilingual Abstract)

Recent development of storage devices has been driven by advanced memory technology, which shifts the paradigm of data access mechanism from magnetics and mechanics to electronics. As a result, the latency of
Solid State Drives (SSD) is cut down to order of microseconds. In spite of the emergence of fast storage devices, however, the existing storage stack cannot keep pace with the speed of the new device since the software has been too optimized to a slow disk for decades; storage vendors like Fusion-IO and OCZ started to implement their own fast storage stack that would
maximize the benefit of their products. Storage systems are now facing an important challenge exploiting the low-latency characteristics of these devices.
In this paper, we propose six types of block I/O subsystem that exploit the performance feature of an SSD with ultra low latency. Our optimization principles are 1) minimizing per-request overhead by redesigning I/O path, and 2) mitigating per-request overhead by using a request batching scheme. The techniques of device polling and synchronous I/O path belong to the first principle, while dispatching discontiguous block requests in a single I/O operation belongs to the second one. Unlike the previous works that mostly focus on the elimination of some software layers, we actively
optimize the existing OS components and implement new functionalities to achieve both low latency and high throughput. We demonstrate the effectiveness of our designs with actual prototypes that operate in recent Linux kernel 2.6.32. Evaluation results show that synchronous I/O path (SyncPath) attains 3.3x reduction in software-latency under single-threaded workload
and a new merge scheme with double buffering (2Q) leads to 4.4x improvement in throughput under multi-threaded workload, compared to the Linux block I/O subsystem. In addition, the hybrid I/O path design (HTM) delivers
87%∼100% of the performance of low-latency devices to an application regardless of request access patterns or request types. We believe that our block I/O subsystem designs are general enough to be implemented for next-generation SSDs pursuing near-DRAM latency and throughput.

국문 초록 (Abstract)

메모리 기술의 발달은 저장 장치 하드웨어의 발전을 가져오게 되었고, 이는 데이터 접근의 패러다임을 기계적 방식에서 전기적 방식으로 이동하게 만들었다. 그 결과, 솔리드 스테이트 드라이브 (SSD)의 응답시간은 마이크로초 수준으로 줄어들게 되었다. 하지만 이러한 빠른 저장 장치의 등장에도 불구하고, 기존의 스토리지 스택은 그러한 새로운 장치의 속도를 따라올 수 없는 문제를 가지고 있는데, 그 이유는 스토리지 스택이 수십년간 매우 느린 디스크에 기반하여 최적화 되어왔기 때문이다. Fusion-IO 나 OCZ 와 같은 저장 장치 제조 회사들
은 자사의 고성능 저장 장치의 이점을 극대화하기 위해 최적화된 별도 의 스토리지 스택을 구현하기 시작했다. 이제 스토리지 시스템은 빠른 저장 장치의 낮은 응답 시간 특성을 최대한 이용할 수 있어야 한다는 도전에직면해있다.
본 논문에서는, 매우 낮은 응답 속도를 가지는 SSD의 성능을 최대한 이용할 수 있는 블럭 입출력 서브시스템의 6가지 타입에 대해 제안한다. 우리의 최적화 기법은 다음의 두가지로 요약할 수 있다; 1) 입출력 경로를 재디자인함으로써 개별 요청의 오버헤드를 줄이는 것, 2) 다수의 요청을 모아서 처리함으로써 개별 요청의 오버헤드를 가리는
것이다. 디바이스 폴링과 동기적 입출력 경로가 첫번째 기법에 해당하고, 비연속 요청을 하나의 I/O로 처리하는 것이 두번째 기법에 해당한
다. 기존의 일들이 불필요한 소프트웨어 계층을 제거하는데 초점을 두었던 것과는 달리, 우리는 적극적으로 기존의 소프트웨어 컴포넌트들
을 최적화하고 새로운 기능을 추가하여 낮은 응답속도와 높은 처리량
(throughput)을 달성할 수 있도록 하였다. 우리의 블럭 입출력 서브시스템은 리눅스 커널 2.6.32 기반으로 구현되었다. 실험 결과에 따르면, 동기적인 입출력 경로 (SyncPath)의 경우, 단일 쓰레드 기반 워크로드에서 약 3.3배 정도 소프트웨어 오버헤드를 줄일 수 있었고, 이중 버퍼링 (2Q)의 경우 다중 쓰레드 기반의 워크로드에서 4.4배 정도의 처리량 향상을 볼 수 있었다. 또한 혼합 입출력 경로 디자인 (HTM)의 경우 입출력 요청의 접근 패턴이나 타입과 상관없이 저장 장치의 성능을 87%∼100% 까지 이끌어 낼 수 있었다. 제안된 블럭 입출력 서브시스템 디자인은 매우 일반적이기 때문에 차세대 SSD가 등장할 시점에도 효과적으로 적용될 수 있을 것으로 기대한다.

목차 (Table of Contents)

• I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
• 1.1 Motivation: Slow Software on Fast Hardware . . . . . . . . 3
• 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 6
• 1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
• II. Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
• 2.1 Trends in Storage Technology . . . . . . . . . . . . . . . . 9
• 2.2 Analysis of I/O Path . . . . . . . . . . . . . . . . . . . . . . 11
• 2.3 Optimization Techniques by I/O Subsystem . . . . . . . . . 13
• III. Analyzing the Legacy of Disk-based I/O Subsystem . . . . . 15
• 3.1 Problem 1: High Software Latency . . . . . . . . . . . . . . 16
• 3.1.1 Interrupt Latency . . . . . . . . . . . . . . . . . . . 16
• 3.1.2 Delayed Execution . . . . . . . . . . . . . . . . . . 17
• 3.2 Problem 2: Low Random Throughput . . . . . . . . . . . . 20
• 3.2.1 Narrow Block I/O Interface . . . . . . . . . . . . . 20
• 3.2.2 Disk-oriented Configuration of I/O Subsystem . . . 22
• IV. Design Exploration of I/O Subsystem . . . . . . . . . . . . . 25
• 4.1 Baseline Design: Asynchronous I/O Path and Interrupt . . . 26
• 4.2 Design 1: Making Entire I/O Path Synchronous . . . . . . . 26
• 4.3 New I/O Interface: Dispatching Discontiguous Block Requests
• in a Single I/O Request . . . . . . . . . . . . . . . .
• 4.4 Design 2: Merging Discontiguous Block Requests Synchronously 30
• 4.5 Design 3: Merging Discontiguous Block Requests Asynchronously
• . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
• 4.6 Design 4: Choosing I/O Path Dynamically Based on a Request
• Property . . . . . . . . . . . . . . . . . . . . . . . . . 37
• 4.7 Design 5: Including Upper Layer to Bridge Semantic Gap
• between VFS and Block I/O Subsystem . . . . . . . . . . . 38
• 4.8 Design 6: Using Double Buffering to Avoid Lock Contention 40
• 4.9 Design Summary . . . . . . . . . . . . . . . . . . . . . . . 42
• V. Implementation Details . . . . . . . . . . . . . . . . . . . . . 44
• 5.1 Block I/O Subsystem in Linux . . . . . . . . . . . . . . . . 44
• 5.2 New Storage Device Interface . . . . . . . . . . . . . . . . 47
• VI. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
• 6.1 Latency Reduction . . . . . . . . . . . . . . . . . . . . . . 48
• 6.2 Microbenchmark 1: Iozone . . . . . . . . . . . . . . . . . . 50
• 6.3 Microbenchmark 2: Fio . . . . . . . . . . . . . . . . . . . . 53
• 6.4 Macrobenchmark 1: Postmark . . . . . . . . . . . . . . . . 53
• 6.5 Macrobenchmark 2: TPC-C . . . . . . . . . . . . . . . . . . 56
• 6.6 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . 58
• 6.7 CPU Utilization . . . . . . . . . . . . . . . . . . . . . . . . 60
• 6.8 Temporal Merge Count . . . . . . . . . . . . . . . . . . . . 62
• VII. RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
• 7.1 Software Stack Optimization . . . . . . . . . . . . . . . . . 65
• 7.1.1 Network I/O Subsystem . . . . . . . . . . . . . . . 65
• 7.1.2 Block I/O Subsystem . . . . . . . . . . . . . . . . . 67
• 7.2 Exploiting Device Functionality . . . . . . . . . . . . . . . 68
• 7.3 Extending Device Interface . . . . . . . . . . . . . . . . . . 69
• VIII. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
• References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
• Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
• Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . 86