188 정보과학회논문지 : 시스템및이론제 41 권제 4 호 (2014.8) SSD 의특성을활용한 NCQ 스케줄링알고리즘 (An NCQ Scheduling Algorithm Exploiting the SSDs Characteristics) 조용운 김태석 (Yongwoon Cho) (Taeseok Kim) 요약본논문에서는하드디스크의데이터접근오버헤드를줄이기위한기존의 NCQ(Native Command Queueing) 기술을 SSD(Solid State Drives) 의특성에적합하도록개선한기법을제안한다. SSD 는하드디스크와달리디스크헤드가없어데이터접근오버헤드가낮고, 읽기와쓰기속도가다르다는특징을가지는데, 여기에 SSD 내쓰기버퍼상태를함께고려하여처리시간이짧은입출력요청부터먼저처리함으로써평균응답시간을줄이고자하였다. 실험결과 FCFS (First-Come-First-Served) 알고리즘대비평균읽기응답시간이최대 78% 까지향상되었다. 키워드 : NAND 플래시메모리, SSD, NCQ, 스케줄링 Abstract In this paper, we propose an efficient scheduling scheme for NCQ (Native Command Queueing) in SSDs (Solid State Drives). Since NCQ was originally designed to improve the I/O performance in hard disk drives, it should be redesigned for SSDs due to different physical characteristics. Unlike hard disk drives, SSDs have low data access overhead and asymmetric read and write speed. Our scheme evaluates the execution time of each I/O command by considering the states of write buffer as well as the SSDs physical characteristics, and then minimizes the average response time by first servicing the I/O command with the shortest execution time. Through the trace-driven simulations, our scheme minimize the average read response time up to 78% compared to FCFS (First-Come-Frist-Served). Keywords: NAND flash memory, SSD, NCQ, scheduling 1. 서론 저장기술의급격한발전으로인해오랜세월동안컴퓨터의보조기억장치로줄곧사용해오던하드디스크의자리를 SSD가점차대신하고있다. SSD는하드디 학생회원 : 광운대학교컴퓨터공학과 ssangkong@kw.ac.kr 비회원 : 광운대학교컴퓨터공학과교수 tskim@kw.ac.kr (Corresponding author임 ) 논문접수 : 2013년 9월 12일 (Received 12 September 2013) 논문수정 : 2014년 4월 25일 (Revised 25 April 2014) 심사완료 : 2014년 5월 13일 (Accepted 13 May 2014) CopyrightC2014 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 시스템및이론제41권제4호 (2014.8) 스크와는달리디스크헤드가없어입출력오버헤드가낮고, 읽기와쓰기속도가다르며, 수명이짧다는특징을가지고있다. 따라서운영체제를포함하여그동안하드디스크를위해설계되었던많은시스템소프트웨어어기술들이 SSD를위해재설계되어야할필요가분명해졌다. 본논문에서는과거하드디스크를위해고안되었던 NCQ 기술을 SSD의특성에따라재설계하고자한다. NCQ 기술은원래 SATA(Serial Advance Technology Attachment) 인터페이스의하드디스크에서성능을향상시키기위해도입된기술로, 입출력요청들을하드디스크의컨트롤러내큐에보관한다음, 전체헤드의움직임을최소화할수있도록입출력요청들을재배열한다. 하지만, 이러한 NCQ 기술을 SSD에그대로사용한다면하드디스크와는다른 SSD의물리적인특성상하드디스크에서의성능을그대로기대하기가어렵다. 이에본논문에서는 SSD의물리적인특성, 구체적으로입출력헤드의부재로인한낮은입출력오버헤드, 읽기와
SSD 의특성을활용한 NCQ 스케줄링알고리즘 189 쓰기속도의비대칭성등을활용하는 NCQ 스케줄링알고리즘을제안한다. 또한, SSD의쓰기성능과수명을향상시키기위해 SSD 컨트롤러내에존재하는쓰기버퍼의상태정보를활용함으로써 NCQ 스케줄링알고리즘의성능을극대화하고자하였다. SSD는스케줄링오버헤드가거의없어서 IOPS(Input/ Output Operations Per Second) 나입출력대역폭을개선하기는어려우나, 적절한입출력요청의재배열을통해서응답시간은크게개선이가능하다. 따라서제안하는알고리즘에서는입출력요청의크기와종류 ( 쓰기또는읽기 ), 그리고요청하는데이터가버퍼에존재하는지의유무를통해큐에존재하는각입출력요청들의처리시간을예측하고, 처리시간이짧은입출력요청부터처리함으로써평균응답시간을개선한다. 다양한워크로드를통한실험결과, 제안한알고리즘은 IOPS나입출력대역폭에대한손실없이평균응답시간을최대 78% 까지개선됨을보인다. 2. 배경지식및관련연구 2.1 SSD의구조 SSD 장치의 NCQ 내입출력명령어들을효과적으로스케줄링하려면, 먼저 SSD 장치의구조와특성을파악해야한다. 그림 1과같이 SSD는호스트인터페이스, NCQ, 버퍼, FTL(Flash Translation Layer), 그리고여러개의낸드플래시로구성된다 [1]. 운영체제에서요청한입출력명령어들은호스트인터페이스를통해 NCQ 에들어와순차적으로쌓이게된다. 이렇게쌓인요청들은처리될때먼저버퍼에해당데이터가있는지확인한후, 버퍼에해당데이터가있으면바로처리가가능하다. 만일버퍼에해당데이터가없을경우 FTL을거쳐낸드플래시에서처리된다. NCQ는원래 SATA 인터페이스를사용하는하드디 스크에서입출력성능을향상시키기위한한방법이었는데, SSD에서도여전히사용하고있다 [2]. 운영체제에서보낸입출력요청들을큐에쌓아두고, 입출력성능을향상시키기위해운영체제의입출력스케줄러와는별도로 NCQ에서다시한번스케줄한다. 운영체제의입출력스케줄러와는다르게저장장치내에서스케줄링하는것이므로각입출력요청의물리적인위치를정확히알고있기때문에, 하드디스크에서는탐색시간뿐만아니라회전지연시간을개선할수있다는특징이있다 [3]. 하지만, SSD에서는하드디스크와달리디스크헤드가없어탐색시간이나회전지연시간등의데이터접근오버헤드가존재하지않고, NAND 플래시메모리특성상읽기와쓰기속도가다르기때문에하드디스크를위한기존의 NCQ 스케줄링기법을재설계할필요가있다. 2.2 관련연구운영체제수준에서의디스크스케줄링알고리즘은 FCFS, SSTF(Shortest Seek Time First), SCAN 등수십년간폭넓게연구되어왔다 [4]. 이들대부분은입출력요청의논리적주소를바탕으로디스크헤드의탐색시간을최소화하는데그목적이있었다. 최근 SSD가다양한컴퓨팅환경에서저장장치로사용되면서 SSD를위한입출력스케줄링알고리즘도점차소개되고있는데, IRBW-FIFO-RP[5], STB[6], SITF[7] 등이대표적이다. IRBW-FIFO-RP에서는쓰기요청은묶어서처리하는데반해읽기요청은개별적으로처리하고, 또한읽기요청에더높은우선순위를두어응답시간을개선한알고리즘이다 [5]. STB는 IRBW-FIFO-RP에기반한알고리즘으로, 시간제한과선택적묶음처리기법을통하여성능을더욱개선하였다 [6]. 한편, SITF는 SSD의물리적특성을비교적잘반영하는입출력스케줄링기법으로처리시간이가장짧은요청을먼저처리하여응답시간을개선하고자하였다 [7]. 그림 1 SATA SSD 에서입출력요청의처리과정 Fig. 1 IO process in SATA SSD
190 정보과학회논문지 : 시스템및이론제 41 권제 4 호 (2014.8) 이처럼운영체제수준에서의입출력스케줄링알고리즘연구는비교적활발히이루어지고있으나, 저장장치내에서 NCQ 스케줄링연구는그렇지않은형편이다. 하드디스크에서의 NCQ 스케줄링관련연구로 [3] 과 [8] 이있는데, [3] 에서는고착화된디스크인터페이스로인해운영체제에서의입출력스케줄링알고리즘과 NCQ에서의스케줄링알고리즘을따로설계할수밖에없고그로인해발생하는성능저하문제를제기하고있다. 또한, [8] 에서는하드디스크컨트롤러내에있는입출력요청들의물리적위치정보를바탕으로디스크헤드의이동거리를최소화하는기법을제시하고있다. 그러나 SATA 기반의 SSD에서여전히 NCQ 기술을사용하고있음에도불구하고 [2], SSD의물리적특성을활용한효과적인스케줄링알고리즘이현재까지전혀연구되지않은상황이다. 3. SSD 의특성을활용한 NCQ 스케줄링알고리즘제안하는알고리즘은 NCQ에존재하는각요청의입출력처리시간을평가하고, 가장짧은처리시간을가진입출력요청부터처리한다. 이는 CPU 스케줄링에서가장짧은처리시간을가진프로세스부터먼저처리하는 SJF(Shortest Job First) 알고리즘에서착안한것으로, 이를통해평균응답시간을개선하고자한것이다. 하드디스크에서의입출력처리시간은탐색시간, 회전지연시간, 데이터전송시간의합으로구성되는데, SSD 에서는디스크헤드가없으므로탐색시간과회전지연시간이존재하지않는다. 따라서 SSD에서의입출력처리시간은데이터전송시간에만의존하는데, 데이터전송시간은입출력요청의크기에비례한다. 또한 SSD에서는읽기속도에비해쓰기속도가훨씬느리기때문에입출력요청의종류에따라처리시간이달라질수밖에없다. 여기에입출력요청에해당하는데이터가버퍼에존재하는지유무를살펴입출력처리시간을평가한다. 이는입출력요청에해당하는데이터가만일버퍼에있다면플래시메모리의접근없이바로처리가가능하고, 그렇지않다면플래시메모리에서처리되어야하므로입출력처리시간에크게영향을받기때문이다. 즉, 제안하는알고리즘을요약하면각입출력요청의크기, 종류, 그리고버퍼에존재하는지의유무에따라처리시간을평가하고, 가장짧은처리시간을가진입출력요청부터처리함으로써평균응답시간을개선하고자한것이다. 각입출력요청의크기, 종류, 버퍼에존재유무를모두고려하여처리시간을평가하기위해다음과같은순서로처리시간을모델링하고자한다. 먼저, 입출력요청의처리시간은입출력요청의크기에비례하므로, 입출력요청의크기만을고려할경우 번째입출력요청의 처리시간 은식 (1) 과같다. (1) 여기에서 는 번째입출력요청의크기를페이지단위로나타낸것이고, 는한페이지를읽거나쓰는데걸리는시간이다. SSD에서는한페이지를읽는시간과쓰는시간이다르기때문에입출력연산의종류에따라 가달라지므로, 입출력요청의크기에연산의종류를함께고려하면식 (1) 을식 (2) 로수정가능하다. 여기에서 는플래시메모리로부터한페이지를읽는데걸리는시간이고, 는한페이지를플래시메모리에쓰는데걸리는시간이다. for (2) for SSD 장치내부에는버퍼가존재하므로, 각입출력요청에해당하는데이터가버퍼에존재한다면플래시메모리에읽거나쓰는대신버퍼에서처리가가능하다. 플래시메모리에서데이터를읽고쓰는데걸리는시간에비해 DRAM으로구성되어있는버퍼에서데이터를읽고쓰는데걸리는시간이훨씬짧기때문에이시간을무시하면, 결국각입출력요청의처리시간은버퍼에서미스나는페이지들을처리하는데걸리는시간이된다. 식 (3) 은식 (2) 를수정한것으로, 각입출력요청의데이터가버퍼에얼마나존재하는지에따른입출력요청의처리시간을모델링한것이다. 여기에서 는 번째입출력요청에해당하는데이터중버퍼에서미스난페이지들의개수이다. for (3) for 제안한알고리즘은각입출력요청들의처리시간을평가하고짧은처리시간을가진요청들부터처리하기때문에평균응답시간은개선할수있지만, 처리시간이긴입출력요청들에기아현상이발생할수있다. 이를해결하기위해여기에서는전통적인에이징 (aging) 기법을이용하는데, NCQ에존재하는입출력요청들이새로들어오는요청에의해순서가뒤로밀릴때마다처리시간을보정한다. 보정한식은식 (4) 와같다. for (4) for 여기에서 는에이징을위한가중치로써 0과 1사이의값이고, 는 번째요청이큐에대기하는동안들어오는입출력요청들중 번째입출력요청보다더짧은처리시간을가진입출력요청들의개수이다. 즉, 가 1 보다작기때문에처리시간이더작은입출력요청이들어와먼저서비스되는걸허용할때마다처리시간을
SSD 의특성을활용한 NCQ 스케줄링알고리즘 191 그림 2 제안하는알고리즘의동작과정 Fig. 2 Process of the proposal 짧게보정하여기아현상을방지하게된다. 결과적으로 가 0에가까울수록 FCFS에가까워지고, 1에가까울수록식 (3) 에가까워진다. 그림 # 은시간에따른큐의상태를나타낸다. 이큐의내용은차례로타입, 버퍼에서미스난페이지수, 예상시간을의미한다. 는 0.02라가정하였고, 는 0.2라가정하였다. 따라서요청이하나씩쌓일때마다큐의상태를위의그림과같이표현한것이다. 여기서 read 7 pages 연산이들어오면, write 1 page 연산은우선순위가밀려에이징되어 0.2보다작은값을나타내게된다. 이런방식으로크기와종류를고려하고, 에이징기법을활용하여기아현상까지방지한알고리즘을제안한다. 4. 실험결과및분석 4.1 실험환경앞서제시한알고리즘모델에따라 Flashsim [9] 에기반하여 SSD 시뮬레이터를개발하고이를바탕으로다양한실험을진행하였다. 기본적인시뮬레이터의설정은표 1과같다. 주소매핑방식은페이지레벨매핑을사용하였고, NCQ의길이는 128이라가정하였다. 버퍼는가장덜최근에참조된버퍼를교체하는 LRU(Least Recently Used) 기법에의해관리된다고가정하였고, 워크로드는 Iometer를사용하여 noop 스케줄러환경에 표 1 SSD의물리적특성 Table 1 Specification of the SSD Specification Capacity 64 GB Buffer Size 32 MB Packages/SSD 8 Packages Dies/Package 8 Dies Planes/Die 2 Planes Blocks/Palne 2048 Blocks Pages/Block 64Pages Page SIze 4KB Page Read Latency 0.02 ms Page Write Latency 0.2 ms Block Erase Latency 1.5 ms Queue Depth 128 서읽기와쓰기비율, 파일접근패턴등을달리하여다양한특성을가진 4개를추출하였다 [10]. 표 2는실험에사용된워크로드의특성을요약한것이다. 제안하는알고리즘은읽기연산과쓰기연산의순서에따라빈번하게스케줄링을하기때문에, 읽기와쓰기비율에변화를주었고, 버퍼의상태에따라스케줄링을다르게하기때문에, 버퍼의상태를변화시키기위하여파일접근패턴을무작위와순차적두가지로다르게하여실험을진행하였다. 4.2 실험결과제안한기법은스케줄링시각입출력요청의크기, 종류, 버퍼상태의세가지고려사항을처리시간관점에서종합적으로모델링한것인데, 각고려사항의개별적인영향을분석하기위해다음과같이몇가지중간단계의알고리즘을함께구현하여비교실험하였다. 첫번째는가장기본적인 FCFS 알고리즘이고, 두번째는각입출력요청의크기만고려한알고리즘 (S), 세번째는각입출력요청의크기와버퍼상태를고려한알고리즘 (SB), 네번째는각입출력요청의크기와종류를고려한알고리즘 (TS), 마지막으로다섯번째는본논문에서최종적으로제안하는즉, 크기와종류, 그리고버퍼상태를모두고려하는알고리즘 (TSB) 이다. 표 2 사용한워크로드의특성 Table 2 Characteristics of the workloads used A B C D Number of Threads 12 12 12 12 File Size 512 KB~1 GB 512 KB~1 GB 512 KB~1 GB 512 KB~1 GB Record Size 4 KB~512 KB 4 KB~512 KB 4 KB~512 KB 4 KB~512 KB Average Inter-arrival Time 1.78 1.76 1.08 1.58 Read / Write Ratio 2:1 1:1 2:1 1:1 Access Pattern Random Random Sequential Sequential
192 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) 4.2.1 에이징 가중치에 따른 실험 결과 본격적인 실험을 진행하기에 앞서, 기아현상을 방지하 기 위한 에이징 가중치에 대한 실험을 먼저 진행하였다. 그림 3은 A 워크로드에 대해서 제안하는 TSB 알고리 즘을 에이징 가중치에 따라 실험한 결과이다. 에이징 가중치는 1에 가까울수록 기아현상을 덜 고려 하면서 제안된 알고리즘에 따라 적극적으로 스케줄링을 하기 때문에 평균 응답시간은 좋아지지만, 기아현상이 발생할 수 있다. 실제로 에이징 가중치를 1로 설정하였 을 때, 최대 쓰기시간이 확연하게 늘어나 일부 쓰기 요 청에서 기아현상이 발생하는 것을 확인할 수 있었다. 그 래서 나머지 실험에서는 기아현상이 발생하지 않으면서 평균 응답시간 측면에서 가장 좋은 성능을 보여주는 0.9 를 에이징 가중치로 설정하였다. 그림 4 버퍼 크기에 따른 읽기 요청들의 평균 응답시간 Fig. 4 average read response time according to buffer size 그림 3 에이징 가중치에 따른 응답시간 그림 5 버퍼 크기에 따른 쓰기 요청들의 평균 응답시간 Fig. 3 response time according to aging factor Fig. 5 average write response time according to buffer size 4.2.2 버퍼 크기에 따른 실험 결과 그림 4는 A 워크로드에서 버퍼의 크기를 변경하면서 평균 읽기 응답시간을 측정한 것이다. 예상할 수 있듯이 버퍼가 커짐에 따라 모든 알고리즘들의 평균 응답시간 은 개선된다. 가장 큰 성능향상을 보인 64MB 크기의 버퍼를 사용하였을 때, FCFS대비 요청의 크기를 고려 한 S의 경우 평균 읽기 응답시간은 59% 개선되었고, S 에 요청의 종류까지 고려한 TS는 73%, TS에 버퍼의 상태까지 고려한 TSB의 경우 78%으로 크게 개선된 것 을 확인할 수 있었다. 버퍼가 작을 때에는 큐에 쌓이는 요청들도 많고 버퍼에 의한 효과도 거의 없었지만, 버퍼 크기가 64MB일 때 모든 요소를 고려한 TSB의 평균 읽기 응답시간은 78%까지 성능이 향상된 것을 확인할 수 있었고, 버퍼가 굉장히 클 때에는 큐에 쌓이는 요청 그림 6 버퍼 크기별 IOPS 들이 별로 없음에도 효과가 꽤 있었다. 하지만 절대적인 Fig. 6 IOPS according to buffer size
SSD 의특성을활용한 NCQ 스케줄링알고리즘 193 4.2.3 워크로드에따른알고리즘별효과모든워크로드에서평균읽기응답시간은감소하여사용자의응답시간이개선될수있었고, 워크로드 B에서는 FCFS대비 TSB가 35% 수준으로줄어들어사용자의응답시간이크게개선됨을확인할수있었고, 평균쓰기응답시간도대부분의워크로드에서줄어들었지만, D 워크로드의경우 6% 증가한현상을확인할수있었다. D 워크로드에서버퍼를고려하였음에도불구하고, 평균읽기응답시간이증가한것을확인할수있는데, 이는버퍼를고려함으로써읽기요청보다쓰기요청이먼저처리되었기때문에나타난현상으로보인다. 그림 7 워크로드별평균읽기응답시간 Fig. 7 average read response time according to workloads 5. 결론본논문에서는 SSD의물리적특성과구조를활용한 NCQ 스케줄링알고리즘을제안하였다. SSD가데이터접근오버헤드가없다는사실을이용하여크기가작은입출력요청부터처리하고자하였고, 읽기가쓰기보다빨리처리된다는점을이용하여읽기요청부터처리하고자하였다. 또한, 버퍼에데이터를가지고있는입출력요청은처리시간이짧다는사실을이용하여버퍼의상태정보까지 NCQ 스케줄링에반영하였다. 실험결과, 평균읽기응답시간이최대 78% 까지향상된것을확인할수있었다. References 그림 8 워크로드별평균쓰기응답시간 Fig. 8 average write response time according to workloads 수치로봤을때 32MB일때효과가가장큰것으로나타났고, 버퍼크기를변경하더라도모든경우의평균응답시간이개선되었다. 그림 5는 A 워크로드에서버퍼의크기를변경하면서평균쓰기응답시간을측정한것이다. 이결과를통하여버퍼의크기가작아큐에요청들이많이쌓여있을경우, 읽기요청을쓰기요청보다먼저처리하기때문에앞의결과와반대로쓰기응답시간은떨어지는것을볼수있다. 하지만큐에요청들이많지않은경우, 빨리끝나는작업을먼저처리하여평균쓰기응답시간도줄어드는것을확인할수있다. 버퍼크기에따른 IOPS(Input/Output Operations Per Second) 도조금은나아졌지만, 큰변화는없었다. 이는전체적인성능에는영향이없이사용자의반응성만향상된것을의미한다. [1] OpenSSD project, http://www.openssd-project.org/ wiki/the_ OpenSSD_Project [2] G. Gasior, "Intel's X25-E Extreme solid-state drive," The technical report, 2008. [3] Y. J. Yu, D. I. Shin, H. Eom and H. Y. Yeom, "NCQ vs. I/O scheduler: Preventing unexpected misbehaviors," Trans.Storage, vol.6, pp.2:1-2:37, apr, 2010. [4] P. J. Denning, "Effects of scheduling on file memory operations," spring joint computer conference, pp. 9-21, 18-20 Apr. 1967. [5] J. Kim, Y. Oh, E. Kim, J. Choi, D. Lee and S. H. Noh, "Disk schedulers for solid state drivers," in Proceedings of the Seventh ACM International Conference on Embedded Software, Grenoble, France, pp.295-304, 2009. [6] S. Kang, H. Park and C. Yoo, "Performance enhancement of I/O scheduler for Solid State Devices," Consumer Electronics (ICCE), 2011 IEEE International Conference on, pp.31-32, 2011. [7] Y. Kim, S. Kang and T. Kim, "Design of I/O scheduler considering the characteristics of SSDs," pp.505-506, 2010. [ 8 ] http://www.techwarelabs.com/reviews/storage/hitachiseagate400gb/index_2.shtml
194 정보과학회논문지 : 시스템및이론제 41 권제 4 호 (2014.8) [9] Y. Kim, B. Tauras, A. Gupta and B. Urgaonkar, "FlashSim: A Simulator for NAND Flash-based Solid-State Drives," First International Conference on Advances in System Simulation, pp.125-131, 2009. [10] Iomerter project, http://www.iometer.org/ 조용운 2012 년광운대학교컴퓨터공학과졸업 ( 학사 ). 2014 년광운대학교컴퓨터공학과졸업 ( 석사 ). 2014 년 ~ 현재광운대학교컴퓨터공학과재학 ( 박사 ). 관심분야는운영체제, 플래시메모리, 차세대비휘발성메모리등 김태석 2000년서울대학교전산과학과졸업 ( 학사 ). 2002년서울대학교컴퓨터공학부졸업 ( 석사 ). 2007년서울대학교컴퓨터공학부졸업 ( 박사 ). 2007년~2008년삼성전자책임연구원. 2008년~현재광운대학교컴퓨터공학과조교수. 관심분야는운영체제, 스토리지시스템, 임베디드시스템등