Low-overhead User-level Prefetching for Fast Application Response

Abstract

애플리케이션을 실행할 때 발생되는 긴 로딩 시간은 사용자가 체감하는 성능에 매우 중요한 요소이다. 애플리케이션의 응답성을 향삼시켜 사용자 경험을 개선하기 위한 하드웨어, 소프트웨어 분야의 연구는 오래전부터 최근까지 지속적으로 이루어지고 있다. 하드웨어 분야에서는 애플리케이션의 데이터가 주로 저장되는 보조 기억장치를 발전시키기 위한 연구가 큰 영향을 미친다. 최근 하드웨어 수준에서는 SSD (Solid State Drive)와 같은 플래시 기반 저장장치가 HDD (Hard Disk Drive)를 대체하여 애플리케이션 로딩 지연 시간이 대폭 감소되었으며 지속적인 발전을 이루고 있다. 그러나 디스크 I/O 시간은 여전히 응용 프로그램 실행 중 사용자 경험을 저하시키는 가장 큰 원인이 되고 있으며, 하드웨어 성능이 좋아지는 만큼 애플리케이션의 요구 사양도 계속해서 증가하고 있다. 하드웨어 수준에서의 성능 향상에 더하여 소프트웨어 수준에서의 성능 개선이 반드시 필요하다.

본 논문에서는 애플리케이션의 응답성을 개선하기 위한 새로운 프리페칭 프레임워크를 제안한다. 제안하는 프레임워크는 애플리케이션 최초 실행(구동) 뿐만 아니라 실행 중간에 발생되는 대량 읽기 요청에 대한 디스크 응답성을 모두 개선하며 모든 기능은 커널 영역이 아닌 사용자 영역에서 동작한다. iFetcher와 Spidermine이라는 이름의 두 가지 버전의 프리페칭 프레임워크를 구현하였으며, iFetcher는 파일 시스템 이벤트 모니터링을 기반으로 하고 Spidermine은 브레이크 포인트를 기반으로 구현되었다.

iFetcher는 inotify API (Application Programing Interface)를 이용하여 프리페칭을 수행한다. inotify는 파일 시스템의 이벤트 모니터링을 제공해주는 리눅스 서브시스템으로 특정 파일에 대한 접근, 읽기 등 원하는 이벤트를 모니터링하고 알림을 받을 수 있다. iFetcher는 애플리케이션의 파일 읽기 요청 정보들을 수집한 후 이 정보들을 분석하여 대량의 읽기 요청이 발생하는 시점들을 파악한다. 이 때 대량 읽기 요청이 발생하기 이전에 파일 I/O가 상대적으로 적은 구간에서 접근된 파일을 프리페칭의 트리거 (Trigger)로 설정한다. 이후 iFetcher와 함께 수집 및 분석이 완료된 애플리케이션을 실행하면 iFetcher는 inotify를 이용하여 트리거 파일에 대한 접근 이벤트를 모니터링하고, 해당 파일에 대한 접근이 발생될 때 잠시 후 대량의 읽기 요청이 예상되는 파일들에 대해 프리페칭을 수행한다. 애플리케이션이 실제 대량의 읽기 요청을 보낼 때에는 이미 대부분의 데이터가 디스크에 비해 성능이 월등한 메인 메모리에 저장되어 있도록 유도하여 로딩 속도를 줄임으로써 사용자 체감 성능을 향상시킨다. iFetcher의 모든 동작은 사용자 수준에서 이루어져 커널 수정이 필요하지 않으며, inotify를 이용하여 오버헤드가 낮다. 실험은 다섯 개의 벤치마크 애플리케이션을 대상으로 SSD가 장착된 PC 환경에서 수행하였다. 실험 결과 iFetcher는 애플리케이션의 구동 시간을 최소 0.3%에서 최대 40.7%, 실행 중간에 발생되는 로딩 시간을 최소 1.5%에서 최대 9% 줄일 수 있었다. 평균 성능은 구동 시간에 대해 3.9% 중간 로딩 시간에 대해 6.2% 개선된 결과를 보였다.

iFetcher는 커널 수준이 아닌 사용자 수준에서도 프리페칭을 수행하여 애플리케이션의 구동 뿐만아니라 중간 로딩에 대한 성능을 낮은 오버헤드로 개선할 수 있음을 보였다. 그러나 iFetcher는 수집 시 놓치는 데이터가 존재했고, 프리페칭 트리거로 사용될 파일은 고유한 파일이어야 하는데 애플리케이션 실행 시 단 한 번만 접근되는 파일이 많지 않아 트리거 설정에 어려움이 있었다. 이러한 문제를 개선하기 위해 후속 연구로 Spidermine을 제안하였다.

Spidermine은 iFetcher의 단점을 개선하여 수집, 분석, 프리페칭 과정을 모두 개선한 프리페칭 프레임워크이다. 수집 과정에서 놓치는 데이터가 거의 없도록 개선하였으며 프리페칭 트리거로는 파일이 아닌 애플리케이션의 명령 포인터 (Instruction Pointer)를 사용한다. 애플리케이션이 대량 읽기 요청을 하기 이전에 파일 I/O 요청이 적은 구간의 명령 포인터를 찾고 해당 명령 포인터의 오프셋 (Offset)을 기억하여 트리거로 활용한다. 이후 애플리케이션을 Spidermine과 함께 실행하면 저장된 오프셋을 이용하여 애플리케이션의 메모리 공간에서 미리 파악해둔 명령 포인터에 브레이크포인트 (0xCC) 코드를 삽입한다. 애플리케이션 실행 중 해당 구간의 코드가 실행되면 브레이크포인트가 발생되고 Spidermine이 프리페칭 쓰레드를 생성하여 프리페칭을 수행하도록 한 후 애플리케이션의 실행을 재개한다. 단순히 브레이크포인트만 삽입해두도록 하여 프리페칭 시점에 대한 모니터링은 전혀 필요가 없으며, 브레이크포인트 발생 후 애플리케이션 실행이 재개되는 과정은 사용자가 체감할 수 없을 정도로 매우 짧다. Spidermine 또한 모든 동작이 사용자 영역에서 이루어지도록 구현하였다. 실험은 총 29 개의 애플리케이션을 대상으로 수행하였으며 HDD와 SSD를 모두 활용하였다. Spidermine은 애플리케이션 구동에 대해 최소 12.1%에서 최대 55.3%, 중간 로딩에 대해 최소 4.5%에서 최대 70.1%의 성능 개선 결과를 보였다. HDD 환경에서는 구동 시간에 대해 평균 31.8%, 중간 로딩에 대해 평균 44.6%의 성능 개선을 이루었으며, SSD 환경에서는 구동에 대해 9.3%, 중간 로딩 시간에 대해 18.3%의 평균 성능 개선 결과를 나타냈다.|Applications face additional latency when they launch or access a disk to load data into the memory, and it significantly affects user-perceived performance. Recently, as flash-based storage devices such as solid state drives have become common, the delay caused by disk I/O has been greatly reduced. However, disk I/O time is still the most responsible cause of the deterioration of the user experience during application program execution.

In this dissertation, I propose a new prefetching framework to improve the responsiveness of application programs. The proposed framework handles not only application startup but also explosive disk read requests that appear during execution, and all functions are performed in user space. This framework has been implemented in two versions depending on the approach. One is called iFetcher, which uses file system event monitoring, and the other is Spidermine, which uses breakpoints. First, iFetcher employs an inode-notification inotify API (Application Programming Interface) that provides an efficient way to trace actions in the file system on Linux and reports those actions to applications in real-time. During an initial training run, iFetcher records when data is read by an application, and also records when the processor is waiting for input. Subsequently it searches the code just ahead of passages where a lot of data is requested, and finds events which can be used to trigger preloading. When the application is run again and a trigger event is reported (by the inotify API), the corresponding data is read into the page cache. iFetcher has a low overhead because disk reads only have to be monitored during training; and it requires no modification of Linux because it runs at the user level. Five benchmark applications were run on a PC with an solid-state drive: iFetcher reduced launch times by 0.3% to 40.7%, and post-launch data loading times by 1.5% to 9%. On Average, iFetcher reduces launch times by 3.9% and loading times by 6.2%.

Spidermine monitors the rate at which read requests are issued by an application, and thus detects bursts of disk reads. It then determines an address at which to insert a breakpoint into the application code or a library before each burst, and logs each breakpoint, together with the data required for the subsequent burst. When the application is subsequently run, Spidermine inserts breakpoints at each logged address by temporarily replacing the instruction. Spidermine is then invoked at each breakpoint, and prefetches the corresponding data blocks into the page cache. This use of breakpoints as triggers for prefetching eliminates the need for monitoring to determine when to prefetch data during program execution. Also, by operating at the user level, Spidermine avoids interference with other applications. Experiments on 29 benchmark applications demonstrated that Spidermine can reduce the time for launch by between 12.1% and 55.3%, and for run-time data-loading by between 4.5% and 70.1%. On Average, Spidermine reduces launch times by 31.8% and loading times by 44.6% on HDD, and launch times by 9.3% and loading times by 18.3% on SSD.