ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 42, No. 12, pp. 1480-1485, 2015. 12 http://dx.doi.org/10.5626/jok.2015.42.12.1480 SSD 입출력요청스트림들의 QoS 지원을위한플래시연산그룹스케줄링 (Flash Operation Group Scheduling for Supporting QoS of SSD I/O Request Streams) 이은규 원선 이준우 김강희 남이현 (Eungyu Lee) (Sun Won) (Joonwoo Lee) (Kanghee Kim) (Eyeehyun Nam) 요약최근에서버시스템에서 SSD(Solid-State Drive) 가고성능저장장치및캐시로서많이사용됨에따라다양한서버응용들의입출력요청스트림들을위해 SSD 수준에서서비스품질 (Quality-of- Service) 를제공할수있는지에대한관심이높아지고있다. 현재까지대부분의 SSD 는 SATA 버스상에서 AHCI 컨트롤러를사용해왔기때문에각입출력스트림을 SSD 내부에서구별하여서비스할수가없었다. 그러나, 최근에새로운 SSD 인터페이스로서 PCI Express 버스상에서 NVME 컨트롤러가제안됨에따라각입출력스트림을 SSD 내부에서구별할수있게되었고, 이에따라입출력요청들을스케줄링할수있게되었다. 본논문은 NVME 기반플래시저장장치를위한플래시연산그룹스케줄링 (Flash Operation Group Scheduling) 을제안하고, 가중치에따라입출력스트림별로비례지분대역폭을제공할수있음을 QEMU 기반시뮬레이션을통해보인다. 키워드 : 플래시저장장치, solid-state drive, 서비스품질, NVME, 플래시연산스케줄링 Abstract As SSDs are increasingly being used as high-performance storage or caches, attention is increasingly paid to the provision of SSDs with Quality-of-Service for I/O request streams of various applications in server systems. Since most SSDs are using the AHCI controller interface on a SATA bus, it is not possible to provide a differentiated service by distinguishing each I/O stream from others within the SSD. However, since a new SSD interface, the NVME controller interface on a PCI Express bus, has been proposed, it is now possible to recognize each I/O stream and schedule I/O requests within the SSD for differentiated services. This paper proposes Flash Operation Group Scheduling within NVME-based flash storage devices, and demonstrates through QEMU-based simulation that we can achieve a proportional bandwidth share for each I/O stream. Keywords: flash storage device, solid-state drive, quality of service, non-volatile memory express, flash operation scheduling 본연구는미래창조과학부및정보통신기술진흥센터의 ICT융합고급인력과정지원사업 (IITP-2015-H8601-15-1001) 과한국연구재단의지원 (No. 2014055278, 비회원 : SK 텔레콤스토리지기술연구소 eyeehyunnam@gmail.com No.2012015266) 을받아수행된연구결과입니다. 논문접수 : 2015년 7월 23일 이논문은 2015 한국컴퓨터종합학술대회에서 플래시저장장치의 QoS 지원을 (Received 23 July 2015) 위한플래시연산그룹 (Flash Operation Groups) 스케줄링 의제목으로발표 논문수정 : 2015년 9월 9일 된논문을확장한것임 (Revised 9 September 2015) 학생회원 : 숭실대학교정보통신공학과 eglee@ssu.ac.kr answpwl@nate.com 비회원 : 숭실대학교정보통신공학과 joonwoolee@ssu.ac.kr 정회원 : 숭실대학교정보통신전자공학부교수 (Soongsil Univ.) khkim@ssu.ac.kr (Corresponding author 임 ) 심사완료 : 2015년 9월 21일 (Accepted 21 September 2015) CopyrightC2015 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지제42권제12호 (2015. 12)
SSD 입출력요청스트림들의 QoS 지원을위한플래시연산그룹스케줄링 1481 1. 서론 최근에서버시스템에서 SSD(Solid-State Drive) 가고성능저장장치및캐시로서많이사용됨에따라다양한서버응용들을위해 SSD 수준에서서비스품질 (Quality-of-Service) 를제공할수있는지에대한관심이높아지고있다. 서비스품질은각입출력스트림에게일정한대역폭을제공함으로써단위시간당처리량과입출력요청의응답시간을보장하는것을의미한다. 예를들어, 다수의가상머신들을실행하는서버시스템에서하나의가상머신이생성하는모든입출력요청들을하나의입출력스트림으로취급하고일정한대역폭을제공한다면, 각가상머신은호스트운영체제를통해서하나의 SSD를공유함에도불구하고, 독립적인가상디스크를갖는효과를보일것이다. 현재까지대부분의 SSD는 HDD와동일하게 SATA 버스상에서 AHCI(Advanced Host Controller Interface) 컨트롤러를사용해왔기때문에입출력스트림들을 SSD 내부에서구별하여서비스할수가없었다. 그러나, 최근에새로운 SSD 인터페이스로서 PCI Express 버스상에서 NVME(Non-Volatile Memory Express) 컨트롤러 [1] 가제안됨에따라각입출력스트림을 SSD 내부에서구별할수있게되었고, 이에따라입출력요청들을스케줄링할수있게되었다. NVME는하나의입출력요청이처리되기전에는다른입출력요청을처리할수없는 AHCI 컨트롤러의한계를극복하기위해서 SSD 내부에멀티큐구조를제공하며, 여러개의큐들에쌓이는입출력요청들을병렬적으로서비스하는것을허용한다. 그림 1은 NVME 기반 SSD의내부구조를보여준다. 그림 1에서보듯이하나의응용이생성하는입출력요청들을하나의입출력스트림으로취급하고, 각응용은 NVME 내부에스트림당요청큐 (per-stream request queue) 를갖는다. 그림에는나타나지않지만운영체제의 NVME 드라이버는입출력스트림마다지정된요청큐에입출력요청을삽입한다. 그러면 FTL(Flash Translation Layer) 은스트림당요청큐들에서입출력요청을꺼내어여러개의플래시연산들로변환하여지정된스트림당연산큐 (per-stream operation queue) 에넣는다. 예를들어, 16KB 크기의읽기요청은 4KB 크기의페이지읽기연산들 4개로변환될수있다. 그리고이러한플래시연산들은본논문이제안하는플래시연산그룹스케줄링 (Flash Operation Group Scheduling) 에의해서칩당큐 (per-chip queue) 에분배된다. 페이지쓰기 (page-program) 연산은 FTL의페이지재사상 (page remapping) 기능에의해서임의의플래시칩에할당할수있으며, 페이지읽기 (page-read) 연산은과거에 FTL이 그림 1 NVME 기반 SSD의구조와 FOG 스케줄러 Fig. 1 NVME-based SSD organization with FOG scheduler 해당페이지를저장하기위해지정한칩에만할당할수있다. 이과정에서플래시연산그룹 (FOG) 스케줄러는각입출력스트림에게정해진가중치 (w) 에따라서각스트림이전체 SSD의대역폭을가중치의비율대로분할받도록플래시연산들을스케줄링한다. 최종적으로플래시제어기 (Flash Controller) 는칩당큐에할당된연산들을큐내부에서의연산들의상대적순서를유지하면서병렬성을최대화하는방식으로인터리빙하여플래시하드웨어를통해서비스한다. 본논문은위와같은 NVME 기반 SSD 구조상에서플래시연산그룹스케줄링을제안하며가중치에따라각입출력스트림에게비례지분대역폭을제공할수있음을 QEMU 기반시뮬레이션을통해보인다. 2. 제안하는 FOG 스케줄링제안하는 FOG 스케줄링은각입출력스트림을플래시연산의그룹으로취급한다. SSD 내부에서한스트림에속한입출력요청은여러개의플래시연산들로변환되며각연산들은지정된플래시칩들에서병렬적으로실행된다. 이와같이동일한자원이두개이상존재하며, 하나의서비스주체를그자원들이병렬적으로서비스하는모델은멀티코어프로세서스케줄링에서도발견된다. 즉, 프로세서코어라는자원이두개이상존재하는환경에서하나의응용프로그램을위해서그것에속하는여러개의쓰레드들을코어들이병렬적으로
1482 정보과학회논문지제 42 권제 12 호 (2015. 12) (a) Task group scheduling (b) Flash operation group scheduling 그림 2 태스크그룹스케줄링과 FOG 스케줄링 Fig. 2 Task group scheduling vs. FOG scheduling 서비스하는상황은 FOG 스케줄링상황과매우유사하다. 멀티코어상에서서로다른응용프로그램들이가중치에따라서프로세서시간을균일하게수신하는공정지분스케줄링모델은 CFS(Completely Fair Scheduler) 를확장하여 CFS 그룹스케줄링 [2] 이라는이름으로개발되었다. CFS의태스크그룹스케줄링을도시하면그림 2(a) 와같다. 각응용은태스크들의그룹으로취급하며, 태스크는그응용에속하는쓰레드의실행인스턴스를의미한다. 동일한쓰레드라도서로다른시간에실행한인스턴스들은그림에서별개의태스크들로취급하기로한다. CFS의태스크그룹스케줄링에의하면, 각태스크그룹은그룹수준에서가상시간 (virtual time) 을유지하며가상시간은각태스크들이개별적으로수신한프로세서시간들에 1/w를곱하여계속누적한다 (w는태스크그룹에부여된가중치임 ). 이때공정지분스케줄링을달성하기위해서 CFS의태스크그룹스케줄링은서로다른그룹들의가상시간 VT가균일하게진행하도록태스크들을멀티코어상에서서비스한다. 그림 2(a) 는태스크할당결과가그림과같다고가정할때에물리시간 t0에서그룹 A와 B의가상시간이서로달랐지만 t1에서는같아지면서공정지분이달성되는예를보여준다. 그림 2(b) 는플래시연산그룹스케줄링을도시한것이다. 하나의스트림은플래시연산그룹으로취급하며, 각연산들은지정된플래시칩들에서병렬적으로서비스된다. 그러나플래시연산그룹스케줄링에 CFS의태스크그룹스케줄링모델을그대로적용하고자하면, 플래시저장장치의특수성으로인해다음문제들이발생한다. 첫째, CFS의태스크그룹스케줄링이요구하는부하균등화알고리즘은플래시연산들을고속처리해야하는 SSD 내부에서구현하기에는복잡도가너무높다. 이부하균등화알고리즘을그대로적용한다면공정지분을달성하기위하여각스트림에부여되는전역적인가중치를기준으로각플래시칩에서서비스되는소속연산들의지역적인가중치의재계산이수시로필요할것이다. 따라서본논문에서는 FTL의연산부하균등화알고리즘으로라운드- 로빈 (round-robin) 과같이단순한알고리즘을가정하고이것과분리된형태로플래시연산그룹스케줄링을구현하고자한다. 이를위해본논문은여러개의플래시칩을하나의가상칩으로추상화함으로써다중칩스케줄링문제를단일칩스케줄링문제로단순화 (approximation) 하는방법을제안한다. 그결과, 본논문에서는다음간단한공식들로각스트림의가상시간을관리하고부하분배에따른칩별지역적가중치의재계산필요성을없앤다. 각기호의의미는표 1 에설명되어있다. (1) (2) 둘째, Ozone[3] 과같은플래시제어기하드웨어는플래시칩들의병렬성을최대로활용하기위해서칩당큐에다수의플래시연산들이미리적재될것을요구한다. 이것은플래시연산그룹스케줄링관점에서각연산의정확한서비스시간을알지못한상태에서각연산들의 VFT를결정하고, 칩당큐에분배해야함을의미한다. 따라서 FOG 스케줄러는각연산마다일단명목서비스시간 (Nominal Service Time) 을가정하여각스트림의가상시간을누적하고, 추후에실제서비스시간 (Actual Service Time) 값이플래시제어기를통해서알려지면이에따라누적된가상시간을다시보정하는방법을취한다. 본논문은다음수식을통해이보정과정을수행한다. (3)
SSD 입출력요청스트림들의 QoS 지원을위한플래시연산그룹스케줄링 1483 Notation OP i,k VST i,k VFT i,k 표 1 기호설명 Table 1 Notations Description Flash operation k of stream i Virtual start time of OP i,k Virtual finish time of OP i,k AT(OP i,k) SVT(t) ST(OP i,k) w i Physical arrival time of OPi,k (at per-stream operation queue) System virtual time observed at physical time t (defined as the minimum of the virtual times of all the streams at time t) Service time OPi,k at flash hardware (chip+bus) (nominal ST: NST, actual ST: AST) Weight of stream i 결과적으로 FOG 스케줄러는상기고려사항들을반영하여 FTL 내부모듈로구현되며모든스트림당연산큐들에존재하는연산들을 VST가작은것부터우선적으로칩당큐에할당하게된다. 3. 실험결과 본논문은제안한 FOG 스케줄링의성능평가를위해 [4] 에서제안한 NVME 기반 SSD 시뮬레이터인 nvmesim 을사용하였다. nvmesim은 QEMU[5] 의내부모듈로서동작하며 QEMU 위에서실행하는 Linux 운영체제의 NVME 드라이버를통해서응용프로그램들의입출력요청을전달받는다. 본논문에서는앞서설명한그림 1 과같이 FOG 스케줄링을적용하기위해 nvmesim을확장하였다. nvmesim은내부 FTL에서페이지수준사상테이블을사용하며페이지쓰기연산들은스트림별로각칩에라운드- 로빈 (round-robin) 방식으로분배한다. 그결과, 이후에발생한해당페이지들의읽기연산들역시라운드-로빈방식으로칩들에균등분배되는효과를기대할수있다. nvmesim은플래시제어기로 Ozone 제어기를가정한다. nvmesim의설정값들은표 2와같다. 표 2 nvmesim 설정값들 Table 2 nvmesim parameters item value Number of flash chips 4 Number of blocks per chip 4096 Number of pages per block 256 Page size 4096 bytes Number of channels One per chip Register access time 100 us Page-read service time 50 us Page-program service time 900 us Block-erase service time 2000 us 그림 3 동일한가중치를갖는두스트림의처리량비교 Fig. 3 Throughput comparison between two streams of equal weights 그림 3은동일한가중치를갖는두스트림의처리량을보여준다. FOG 스케줄링의대역폭분할효과를살펴보기위하여 Stream1은시점 t0에서부터비동기입출력방식으로읽기요청들을쉼없이생성하고, Stream2 는 t0보다늦은 t1부터시작하여마찬가지로읽기요청들을생성하다가 t2 시점부터는쓰기요청들을생성한다. 이때각스트림이읽거나쓴데이터바이트들을누적해보면 [t0, t1] 구간에서는 Stream1이전체 SSD의대역폭을독점하여사용하다가, [t1, t2] 구간에서는 Stream2와 50% 씩분할하여사용하는것을볼수있다. [t2, t3] 구간에서도이러한대역폭분할이유지되는데, 다만읽기요청들만생성하는 Stream1은단위시간당읽기량이 [t1, t2] 구간과동일한데비해, Stream2는그쓰기량이 [t1, t2] 구간에비해줄어듦을확인할수있다. 이것은 Stream2의페이지쓰기연산들이플래시하드웨어상에서 Stream1의페이지읽기연산들보다더많은물리서비스시간을요구하기때문이다. 그림 4는동일한가중치를갖는 8개스트림의대역폭분할효과를보여준다. 모든스트림들은비동기입출력방식으로동일한크기와개수의입출력요청들을생성하는데, 스트림 S1, S2, S3는읽기요청들만을, S4와 S5은읽기요청들과쓰기요청들을섞어서, S6, S7, S8 은쓰기요청들만을생성한다. 그결과 S6, S7, S8이제일먼저종료하고, 다음에 S4와 S5가종료하고, 마지그림 4 동일한가중치를갖는스트림들의대역폭지분비교 Fig. 4 Bandwidth share comparison between streams of equal weights
1484 정보과학회논문지제 42 권제 12 호 (2015. 12) 다. 이경우에 GC 스트림은일정한크기의대역폭 (S8 에게분배되는대역폭과같은크기 ) 만을수신할수있기때문에단위시간당생성된모든연산들을같은시간안에서소진할수있음이보장되지는않는다. 따라서단위시간당자유페이지의생산률을높여야하는경우에는 GC 스트림의가중치값을높여야하는경우도있을것이다. 그림 5 다른가중치를갖는스트림들의대역폭지분비교 Fig. 5 Bandwidth share comparison between streams of different weights 그림 6 다른가중치를갖는스트림들의대역폭지분비교 (GC 스트림포함 ) Fig. 6 Bandwidth share comparison between streams of different weights (including GC stream) 막으로 S1, S2, S3가종료하는것을확인할수있다. 이와같이매순간 SSD가서비스하는스트림의개수가변화하는상황에서 FOG 스케줄링에따라전체 SSD의대역폭은경쟁하는스트림들의가중치가동일할때균등하게분배됨을확인할수있다. 그림 5는서로다른가중치를갖는 8개스트림의대역폭분할효과를보여준다. 8개스트림들은그림 4의실험에서사용한스트림들과동일하며, 가중치 w i = w i+1 1.25 가되도록설정하였다. 따라서 S1의대역폭지분이가장크고 S8의대역폭지분이가장작다. 그결과 S1, S2,, S8의순서대로종료하게된다. 이경우에도 FOG 스케줄링에따라전체 SSD의대역폭은경쟁하는각스트림들의가중치에비례하여비교적정확하게분배됨을확인할수있다. 그림 6은그림 5의실험에 FTL 내부에서동작하는가비지컬렉션 (garbage collection) 스트림을추가한것이다. 이를위해 FTL 내부에는 GC 스트림을위한스트림당연산큐를추가하였고, 일정주기마다하나의블록지우기연산과다수의페이지읽기 / 쓰기연산들이이큐에도착하도록설정하였다. GC 스트림은그림 6에서 S9로표기하며, 스트림 S8과동일한가중치를갖는 4. 결론 본논문은 NVME 기반 SSD에서각입출력스트림에게부여된가중치에비례하여 SSD의대역폭을분할하여제공하는플래시연산그룹스케줄링을제안하였다. NVME 인터페이스는입출력스트림마다 SSD 내부에별도큐를생성할수있으므로입출력스트림을식별할수있으며 CFS의태스크그룹스케줄링과유사하게플래시연산그룹들의서비스시간을하나의가상시간으로누적하여스트림간에균일한진행을달성할수있다. FOG 스케줄링이각스트림의대역폭을일정하게보장하기위해서는전체 SSD 대역폭이출렁이지않도록다음사항들을고려해야한다. 첫째, 어떠한상황에서도읽기연산들이특정플래시칩들에집중되지않도록 FTL에서부하균등화를잘달성해야한다. 둘째, 사용자스트림들과는별개로 SSD의대역폭을소비하는 FTL의백그라운드작업들, 말하자면가비지컬렉션 (garbage collection), 마모도균등화 (wear-leveling), 불량블록관리 (bad block management) 작업들을별도의내부스트림으로관리하고, 이스트림에게요구되는대역폭의크기를일정하게관리할수있는구조가필요하다. SSD 대역폭이일정하게유지될수있다면궁극적으로플래시연산들의응답시간의상한이존재할것이므로개별입출력요청의응답시간을보장하는것또한가능해질것이다. References [1] NVMHCI Work Group. (2011, Jun. 1). New Promoter Group Formed to Advance NVM Express [Online]. Available: http://www.nvmexpress.org/wp-content/ uploads/2013/04/nvme_press_release_new-promot er-group_20110601.pdf (downloaded 2015, Sep. 25) [2] P. Turner. (2011, Sep.). Improving Global Scheduler Decisions [Online]. Available: http://linuxplumbersconf.net/2011/ocw/system/presentations/309/original /LPC_2011_Global_Lag.pdf (downloaded 2015, Sep. 25) [3] E.H. Nam, B.S.J. Kim, H. Eom, S.L. Min, "Ozone (O3): An Out-of-Order Flash Memory Controller Architecture," IEEE Trans. Computers, Vol. 60, No. 5, pp. 653-666, 2011. [4] E. Lee, S. Won, K. Kim, and E. Nam, "NVMe-based
SSD 입출력요청스트림들의 QoS 지원을위한플래시연산그룹스케줄링 1485 Flash Storage Simulator," Proc. of the 41th KIISE Winter Conference, Dec., 2014. [5] F. Bellard, "QEMU: a Fast and Portable Dynamic Translator," Proc. of the 2005 USENIX Annual Technical Conference, pp. 41-46, 2005. 이은규 2011 년숭실대학교정보통신전자공학부 ( 학사 ). 2013 년숭실대학교정보통신공학과 ( 석사 ). 2013 년 ~ 현재숭실대학교정보통신공학과박사과정. 관심분야는실시간시스템, 임베디드시스템, 스토리지시스템등 원선 2014년숭실대학교정보통신전자공학부 ( 학사 ). 2014년~현재숭실대학교정보통신공학과석사과정. 관심분야는실시간시스템, 임베디드시스템, 스토리지시스템등 이준우 2011년숭실대학교정보통신전자공학부 ( 학사 ). 2013년숭실대학교정보통신공학과 ( 석사 ). 2015년숭실대학교정보통신공학과 ( 박사수료 ). 관심분야는 CPU 스케줄러, 플래시저장장치, 실시간임베디드시스템등 김강희 1996년서울대학교컴퓨터공학과 ( 학사 ) 1998년서울대학교전기컴퓨터공학부 ( 석사 ). 2004년서울대학교전기컴퓨터공학부 (Ph.D., 박사 ). 2004년~2010년삼성전자무선사업부책임연구원. 2010년~현재숭실대학교스마트시스템소프트웨어학과교수. 관심분야는실시간시스템, 임베디드시스템, 운영체제, 모바일플랫폼, 플래시저장장치, 모션제어시스템등 SW 아키텍처등 남이현 1998 년서울대학교전기공학부 ( 학사 ). 2011 년서울대학교전기컴퓨터공학부 (Ph.d., 박사 ). 2011 년 ~2012 년서울대학교 BK21 정보기술사업단박사후연구원. 2013 년 ~ 2015 년 SK 텔레콤 ( 주 ) 종합기술원 Expert PL. 관심분야는플래시저장시스템 HW/