Abstract Next-generation non-volatile memory modules have emerged recently in storage market. However, due to the limited life time and poor performan

Transcription

1 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 A Recent Trend of Buffer Management based on Database using Next-generation Memory Module 이미경 (Mi-kyung Lee) 1, 김재형 (Jae-hyung Kim) 2, 박상현 (Sang-hyun Park) 3 요약 최근전원이공급되지않는상태에서도데이터를보존하기위한비휘발성차세대메모리소자가각광받고있다. 그러나제한된수명과 DRAM 대비부족한지연대기로인해단기간내에 DRAM 을완전히대체하기란어려울것으로예상되고있다. 따라서차세대메모리저장장치를하드디스크를대체하거나하드디스크의버퍼로활용하여현재의환경에서데이터베이스시스템의성능을향상시키기위한연구들이계속해서진행되고있다. 본논문에서는차세대메모리저장장치를활용한버퍼관리기법을연구하는것이중요한연구주제라고판단하여버퍼관리기법을위해고려해야할메모리소자의특성과내부구조에대해설명하고이러한특성을적극적으로활용한각각의최신버퍼관리기법들의동향을소개하고자한다. 주제어 : DRAM, 비휘발성저장장치, 플래시메모리, SSD, NVRAM, 버퍼관리알고리즘 1 연세대학교컴퓨터과학과, 석사과정. 2 연세대학교컴퓨터과학과, 박사과정. 3 연세대학교컴퓨터과학과, 교수, 교신저자. + 본연구는 2015년도정부 ( 미래창조과학부 ) 의재원으로한국연구재단의지원을받아수행하였음. (NRF-2015R1A2A1A ) + 논문접수 : 2016년 3월 3일, 심사완료 : 2016년 3월 15일, 게재승인 : 2016년 3월 24일.

2 Abstract Next-generation non-volatile memory modules have emerged recently in storage market. However, due to the limited life time and poor performance, these storages are predicted not to completely replace DRAM in the foreseeable future. Accordingly, there is a growing body of studies that these memories are used for an alternative to HDD or write buffer between DRAM and storage devices. In this paper, we consider the buffer management schemes using next-generation non-volatile memory module as an important research topic and also explain the characteristics of these memory modules. Finally, we describe a recent trend of the buffer management schemes using next-generation non-volatile memory modules. Keywords: DRAM, non-volatile storage, flash memory, SSD, NVRAM, buffer management algorithm

3 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 서론 컴퓨터의주기억장치로서주로사용되는 DRAM(Dynamic random access memory) 은하나의기억소자에 1개의트랜지스터 (Trangister) 와 1 개의커패시터 (Capacitor) 로구성된다. 이와같은간단한구성덕분에 DRAM 은높은직접도로제작될수있고데이터접근속도가매우빠르며저비용으로도대용량화할수있다. 그러나 DRAM 은전원이공급되고있는동안데이터를일정한주기로다시기록해주지않으면데이터가사라지는문제점을가지고있다. 이러한문제점을극복하기위하여하드디스크 (Hard disk) 와같이전원이공급되지않는상태에서도데이터를유지하기위한차세대메모리저장장치들이새롭게각광받고있다. 표 1 [1-2] 과같이현재까지가장광범위하게사용되고지속적으로연구되고있는대표적인메모리소자들중하나인플래시메모리 (Flash memory) 는비휘발성특성을갖고있으나, DRAM 대비읽기및쓰기지연시간이길고제자리덮어쓰기 (In-place update) 가불가능하며, 비트정보가저장된플래시메모리의셀들의지우고쓰는횟수가제한되어있어아직까진 DRAM 을완전히대체하지못하고있다. 그럼에도불구하고플래시메모리는하드디스크와다르게데이터접근시, 기계적인구동없이전기적인신호를사용하여데이터에접근하기때문에요청이들어온즉시데이터를접근하므로하드디스크보 다전력소모가적다. 이와같은장점들덕분에여러개의플래시메모리들을묶음으로써하드디스크를대체하기위한플래시 SSD(Solid state drive) 가등장했다. SSD는플래시메모리의제작공정의발달에따라용량대비가격이낮아지고있어서버시장에까지사용영역을넓히고있다. 이외에도보다적극적으로 DRAM 을대체하기위한대표적인비휘발성메모리소자를통칭하는 NVRAM(Non-volatile random access memory) 이있다. NVRAM 은 DIMM(Dual in-line memory module) 인터페이스를통해바이트단위의연산을제공하며제자리덮어쓰기가가능해가비지컬렉션 (Garbage collection) 으로인한오버헤드문제를우려할필요가없다. 또한, 플래시메모리대비빠른읽기및쓰기지연대기시간을보이고있어 DRAM 을대체할소자로주목받고있다. 그러나 DRAM 대비느린쓰기지연대기와제한적인수명, 그리고높은용량대비가격문제로인해단기간내에 DRAM 을완전히대체하기란어려울것으로예상되고있다. 따라서 NVRAM 을 DRAM 을대체하는구조가아닌, 하드디스크혹은플래시 SSD와혼합된시스템상에서캐시로활용하려는시도가지속적으로연구되고있고, 이에부응하여각저장장치의특성에적합한버퍼관리기법의연구는앞으로도유망할것으로판단된다. 본논문에서는차세대메모리소자를활용한버퍼 [ 표 1] 메모리소자의특성 Name Read latency Write latency Non-volatility Endurance DRAM Fast Fast NO SRAM Fast Fast NO NAND flash Slow Slow YES 10 5 ~ 10 6 PRAM Fast Slow YES 10 8 STT-MRAM Fast Slow YES > 10 15

4 34 데이터베이스연구제 32 권제 1 호 ( ) 관리기법을연구하는것이중요한연구주제라고판단하여이와관련된버퍼관리기법들에대해살펴보고자한다. 논문의구성은다음과같다. 2장에서는버퍼관리기법을위해고려해야할메모리소자의특성에대해설명하고, 3장에서는 2장에서설명했던메모리들을활용한최신버퍼관리기법들을소개한다. 4장에서는차세대메모리를활용한버퍼관리기법들을토대로향후발전될버퍼관리기법들의동향제시와결론을기술하도록한다. 2. 차세대메모리저장장치 2.1 플래시메모리전원이차단되어도데이터가그대로보존되는플래시메모리는데이터를전기적으로기록하고삭제하기때문에하드디스크에비해전력소모가적고데이터접근속도가빠르다. 이와같은특성들로인해플래시메모리는차세대메모리저장장치로크게주목받아왔다. 플래시메모리소자는메모리셀의배열에따라크게 NOR 플래시메모리와 NAND 플래시메모리로나눌수있다. 병렬로연결된셀의구조로인해임의적접근은가능하지만쓰기연산의수행속도가느리고대용량화하기가어려운 NOR 플래시메모리와는달리, 직렬로연결된셀의구조를가진 NAND 플래시메모리는 NOR 플래시메모리에비해읽기연산의수행속도는느리지만, 쓰기연산의수행속도가빠르고비트당제작비가낮아대용량화하기가쉽기때문에데이터를저장하기위한용도로적합하다. 이러한특성을바탕으로하드디스크보다더빠른입출력처리를필요로하는요구에부응하여새로운비휘발성저장장치인 SSD(Solid state disk) 가등장하였으며, 이를기반으로한연 구역시활발히진행되고있다. 그러나플래시메모리는쓰기연산의비용이읽기연산에비해확연히크고덮어쓰기가불가능하며셀당쓰기및삭제연산의횟수가제한되어있다 [3]. 이러한한계점은모바일또는서버환경에서의데이터베이스시스템이나운영체제와같은시스템소프트웨어에서기존의하드디스크기반의방법론에 SSD 혹은 NAND 플래시메모리가적용될때기대할만한성능향상을이끌어내지못할수있다. 따라서운영체제혹은데이터베이스시스템의성능을향상시키기위해하드디스크에최적화된기존의방법론들을 NAND 플래시메모리의특성에맞게개선하려는연구가지속적으로진행되고있다. 2.2 플래시 SSD NAND 플래시메모리를기반으로하는 SSD는 NAND 플래시메모리제작기술의발전에따라용량대비가격면에서하드디스크에근접하게되면서사용범위가확대되는추세다. 이와더불어클라우드 (Cloud) 및데이터센터가성장하면서대규모서버시스템을위한대용량데이터저장장치로도각광받고있다. SSD는그림 1에서보는바와같이 SSD 컨트롤러 (Controller), DRAM, 그리고다수의플래시메모리들로구성된다. 호스트 (Host) 로부터읽기또는쓰기명령어를입력받으면 DRAM 에저장된주소변환테이블을통해호스트로부터받은요청에대한논리적주소 (Logical block address) 를물리적주소 (Physical block address) 로변환한후, 플래시메모리로저장한다. 이때, 다수의플래시메모리들은독립적인채널 (Channel) 들로묶여있는다중채널구조를가지며각채널은입력받은명령어가다수의플래시메모리에최대한병렬적으로데이터를읽고쓸수있도록함으로써보다효율적인

5 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 35 [ 그림 1] SSD 의구조 입출력연산을수행할수있도록한다. 즉 SSD는다중채널을통한내부병렬성 (Internal parallelism) 을최대한활용하여입출력성능을높인다 [4]. 한편, DRAM 은주소변환테이블을임시버퍼공간으로사용하기도하는데이러한경우, 하드디스크에최적화된방법론들을그대로적용시키면하드디스크와는전혀다른성질을지닌 SSD에맞지않아기대했던성능을이끌어내지못할가능성이있다. 이러한문제를해결하고자하드디스크기반의기존방법론들을 SSD에최적화시켜성능개선을시도하려는연구가많이진행되어왔다. 최근에는 SSD의 NAND 플래시메모리소자의특성뿐만아니라위에서언급한 SSD 내부의채널구성등보다깊은수준의하드웨어특성을다각도로고려하여성능향상을꾀하는방법론들이연구되고있다. 2.3 NVRAM 현재까지주로통용되는컴퓨터구조는휘발성메모리인 DRAM 과하드디스크와같은비휘발성저장장치로이루어진구조를토대로하고있으며, 운영체제에서수행하는모든작업들은메모리에 1차적으로반영이되고난다음, 데이터의영속성을위해하 드디스크에다양한방식으로메모리에반영된데이터를저장하게된다. 이와같은컴퓨터구조에서비휘발성메모리소자인 NVRAM 은보조기억저장장치에한정적인 NAND 플래시메모리를넘어, 주기억장치인 DRAM 을대체하고있다. NVRAM 은휘발성메모리인 DRAM 과다르게비휘발성인특성을갖는메모리소자로서, NAND 플래시메모리가지닌부족한특성들로인하여기존 DRAM 을대체하지못한것과는달리, DIMM 인터페이스를통해바이트단위연산을제공하며 NAND 플래시대비수십배에서수백배이상빠른지연대기시간을보장하는 DRAM 을대체할메모리소자들의통칭이라고할수있다. 또한 NVRAM 은플래시메모리와달리제자리덮어쓰기가가능하여지속적인쓰기연산의수행으로인한가비지컬렉션에대한높은비용문제가존재하지않는다. 현재까지 NVRAM 으로분류될수있는메모리소자들에는 PRAM(Phase-change RAM), STT-MRAM(Spin-transfer torque magnetic RAM), ReRAM(Resistive RAM) 등이있으며이들은유력한차세대메모리로부상하고있다. 그럼에도불구하고 PRAM 을기준으로 DRAM 대비느린쓰기연산에서의지연대기시간 [5] 과제

6 36 데이터베이스연구제 32 권제 1 호 ( ) 한적인수명문제 [6], 그리고용량대비가격으로인하여현재까지발표된 NVRAM 이상용환경에서단시일내에 DRAM 을대체하기란불가능할것으로예측되고있다. 따라서 NVRAM 을메모리의대체품으로적용하기보다는그자체로 SSD를대체하는차세대저장장치의일환으로사용하거나, DRAM 과하드디스크또는 SSD 사이의캐시장치로사용하려는시도가연구되고있다. 특히캐시장치로사용되는 NVRAM 환경을고려할때운영체제혹은데이터베이스의성능을좌우하는버퍼교체기법에서기존하드디스크와 SSD에특화된방법만을적용할경우, 그특성을살리지못해원하는성능을충분히확보하지못하는문제가있으며, 이러한문제를다루기위한다양한연구들은 DRAM 을대체할새로운메모리소자가나오기전까지다양한저장장치아키텍처혹은인터페이스의등장과더불어앞으로도유망할것으로보인다. 3. 차세대메모리저장장치를활용한버퍼관리기법 3.1 플래시메모리의특성을활용한버퍼관리기법플래시메모리가등장하기이전에는하드디스크를기반으로한버퍼관리기법들이주로연구되었다. 그러나하드디스크를기반으로한기존의버퍼관리기법들은그림 2와같은플래시저장장치를보조기억장치로사용한데이터베이스시스템에적용시켰을때시스템성능이기대에미치지못할우려가있다. 이러한문제를해결하기위하여하드디스크기반의버퍼관리기법들을앞서살펴보았던플 [ 그림 2] 플래시메모리기반데이터베이스시스템의구조래시메모리만의특성에맞게개선하려는시도가이루어지고있다. 플래시메모리의부진한쓰기성능을보완하기위해 LRU(Least Recently Used) 기법 [7-9] 을개선하는연구들이진행되고있다. Heeseung Jo [10] 은 PMP(Portable media player) 의성능을높이기위해 FAB(Flash-Aware Buffer management policy for portable media players) 기법을제안하였으며, 희생자페이지를선정할때시간적지역성 (Temporal locality) 보다플래시메모리의우수한순차쓰기성능을고려한다. 따라서희생자페이지를결정하려고한다. 따라서버퍼교체시, 페이지개수가가장많은블록을희생자로선택한다. Seon-yeong Park [11] 은플래시메모리의쓰기연산의비용을줄이기위한 CFLRU(Clean-First Least Recently Used) 기법을제안하였다. 이를위하여버퍼를최근에참조된페이지들이모여있는워킹영역 (Working region) 과오랫동안참조되지않은페이지들이이영역에모여있는클린- 퍼스트영역 (Clean-first region) 으로분류한다. 버퍼교체시, 클린- 퍼스트영역에있는페이지들중영역의

7 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 37 끝에위치한클린페이지 (Clean page) 를우선적으로버퍼에서내보내어쓰기연산의비용을절감할수있도록한다. 한편, Hoyoung Jung [12] 은콜드탐지 (Cold-detection) 기법을사용하여참조빈도수가낮은콜드페이지 (Cold page) 를감별하는 LRU-WSR(Integration of LRU and Write Sequence Reordering) 기법을제안하였다. 이기법은버퍼교체시리스트의꼬리에있는희생자후보페이지가클린페이지라면버퍼에서내보내고, 더티페이지이면그림 3과같이해당페이지가콜드페이지인지구별하여콜드페이지인경우희생자페이지로간주한다. 이와같은과정은클린페이지또는콜드한더티페이지를버퍼에서내보내고콜드하지않은더티페이지를버퍼에서유지할수있도록하므로캐시적중률의저하를해결하면서도플러시되는더티페이지개수를낮출수있다. [ 그림 3] LRU-WSR 의희생자페이지선정과정 Yi Ou [13] 은 CFDC(Clean First Dirty Clustered) 기법을제안하였으며버퍼를워킹영역 (Working region) 과중요도영역 (Priority region) 으로분류한다. 워킹영역은다시참조될가능성이높은핫페이지 (Hot page) 들이모여있는영역으로, 다양한버퍼관리기법들을적용시킬수있다. 반면, 중요도영역은중요도를가진페이지클러스터 (Cluster) 들로이루어져있고클러스터는공간적으로근접하게위치한페이지들로구성된다. 중요도영역에있는클린페이지들은 LRU 리스트로, 더티페이지들은클러스터들이들어있는중요도큐 (Priority queue) 로관리되며클러스터탐색을위해해시테이블 (Hash table) 이존재한다. 버퍼교체시중요도영역의 LRU 리스트에있는클린페이지가우선적으로희생자페이지로선정되고, 중요도영역에클린페이지가없으면중요도큐에서중요도가가장낮은클러스터를찾아해당클러스터내에서가장오래된페이지를희생자페이지로선택한다. 클러스터의중요도는페이지개수로결정되며페이지개수가많은클러스터일수록클러스터의중요도는낮아진다. 희생자페이지가플러시되는동안공간적지역성 (Spatial locality) 을발생시켜플래시메모리의쓰기연산의성능을보완한다. Zhi Li[14] 는 CCF-LRU(Cold-Clean-First LRU) 기법을제안하였으며참조빈도수가낮은콜드- 클린페이지 (Cold-clean page) 들을모아둔콜드- 클린 LRU 리스트와그외의핫-클린 (Hot-clean), 콜드- 더티 (Cold-dirty), 핫-더티 (Hot-dirty) 상태를갖는페이지들을모아놓은혼합 LRU 리스트로페이지들을관리한다. CCF-LRU 기법은실험에의거하여핫- 더티페이지, 핫-클린페이지, 콜드- 더티페이지, 콜드- 클린페이지순으로교체비용이크다는것을확인하였으며이에따라버퍼교체시콜드- 클린 LRU 리스트에있는콜드- 클린페이지를우선적으로내보낸다. 따라서쓰기연산의횟수와 I/O 수행시간을감소시킬수있다. 콜드- 클린 LRU 리스트에콜드- 클린페이지가없으면 LRU-WSR 기법의콜드- 탐지기법을사용하여혼합 LRU 리스트의꼬리에있는페이지가클린페이지인지검사한다. 해

8 38 데이터베이스연구제 32 권제 1 호 ( ) 당페이지가콜드- 더티페이지인경우에는희생자페이지로간주하지만, 핫-더티페이지인경우에는콜드플래그를사용하여콜드페이지로변경한후, 혼합 LRU 리스트의헤드로옮긴다. 해당페이지가핫-클린페이지이면콜드페이지로변경한다음, 헤드로이동시킴으로써읽기연산의비용을절감할수있도록한다. 한편, Bokyeong Kim[15] 은 PMP에서멀티미디어데이터뿐만아니라메타데이터도고려하는 LSF(Long Sequential accessed pages First) 기법을제안하였다. 멀티미디어데이터와메타데이터는데이터를이루는페이지들이순차적이며번갈아나타난다. 특히멀티미디어데이터는순차적패턴의길이가길고데이터를이루는페이지들이한번씩만참조되지만, 메타데이터는패턴의길이는짧고자주참조되는경향을가지고있다. LSF 기법은페이지가새롭게참조되면저장되는콜드리스트 (Cold list) 와핫리스트 (Hot list) 로분리하여관리한다. 버퍼교체시콜드리스트에빈프레임이없을때콜드리스트에있는페이지들의순차적인패턴을검사하여긴순차참조집합 (Long sequential reference set) 과짧은순차참조집합 (Short sequential reference set) 으로분류하고, 긴순차참조집합을버퍼에서우선적으로내보낸다. 따라서캐시적중률이높고쓰기연산의개수도줄일수있다. 이와같은연구들은플래시메모리가순차쓰기성능이우수하다는점을활용하여 LRU 기법을개선한연구들로플래시메모리의부진한쓰기성능을보완하고자하는데의의를두고있다. 또한, 플래시메모리의쓰기성능을개선하기위하여하드디스크기반의 CLOCK 기법 [16] 을개선하려는연구들도존재한다. Debnath B.[17] 은 SSD 를위한 LB-CLOCK(Large Block CLOCK) 기법을제안하였으며, 페이지들을 SSD의소거블록 (Erase block) 과동일한크기의논리적블록단위로유지하고모든논리적블록은 CLOCK 기법처럼참조비트를가지고있다. 페이지교체시참조비트가 0인블록들을희생자후보집합 (Victim candidate set) 에포함시키고, 집합에서페이지개수에가장많은블록을희생자블록으로선정하여블록에속한모든페이지들을버퍼에서내보내므로쓰기연산의횟수를감소시킬수있다. Hyojun Kim[18] 은스마트폰을위한 Spatial Clock 기법을제안하였으며버퍼에페이지를추가할때마다페이지들을논리적인섹터번호순서로정렬하기때문에다른기법보다순차쓰기연산들을많이생성한다. Donghyun Kang[19] 은 TS-CLOCK(Temporal and Spatial locality aware CLOCK) 기법을제안하였는데, 이기법은페이지들을블록단위로묶고블록내페이지들을논리적섹터번호를기준으로정렬한다. 이기법은버퍼교체시, t-hand 포인터가가리키는페이지의참조횟수가 0일때해당페이지가클린페이지이면버퍼에서내보내고, 더티페이지이면 s-hand 포인터를이용하여해당페이지가속한블록에들어있는페이지들의참조횟수를순차적으로검사하여희생자페이지를결정한다. 클린페이지를희생자페이지로우선적으로고려하였기때문에쓰기연산의횟수를줄일수있고다른기법에비해순차적쓰기패턴을많이생성한다는장점을가지고있다. 이와같이 NAND 플래시메모리를활용한버퍼관리기법들은페이지를교체하는과정에서더티페이지를디스크에쓰는비용을줄이는데중점을두고있다. 이를위하여플래시메모리를활용한버퍼관리기법들을크게세가지형태의기법들로분류할수있다. 쓰기연산의횟수를줄이기위하여클린페이지를우선적으로버퍼에서내보내는데중점을둔기법, 플래시메모리의순차쓰기성능을이용함

9 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 39 으로써부진한쓰기성능을보완하는기법, 시간적지역성을고려하여캐시적중률을높이고이로인해페이지교체횟수자체를감소시키려는기법이이에해당된다. 그러나메모리직접도등플래시메모리의물리적인구조를변화시키는연구가계속해서다루어지고있기때문에제시한기법들외에도다양한방법들을활용한버퍼관리기법들이제시될수있다. 3.2 플래시 SSD 의다중채널구조를이용한버퍼관리기법 NTFS, FAT 과같은파일시스템이나운영체제, 그리고이를기반으로하는프로그램들은기본적으로섹터단위로작업을수행한다. 그러나플래시 SSD는블록과페이지기반으로작업을수행한다. 이러한구조적차이때문에파일시스템과운영체제는직접적으로플래시메모리를사용할수없게되어있다. 그러나플래시 SSD는자체컨트롤러 (Controller) 단계에서 FTL(Flash Translation Layer) 을통해파일시스템과운영체제기반의논리적인주소를플래시메모리에맞는물리적인주소로변환함으로써기존의파일시스템과운영체제, 그리고이를기반으로하는프로그램들은이에대해특별히고려할필요없이 SSD를사용할수있도록한다. 그외에도 FTL은 SSD의다중채널구조를이용하여논리적인페이지들을여러개의채널에서병렬적으로처리할수있도록하고, 가비지컬렉션 (Garbage collection) 을수행하여플래시메모리가덮어쓰기가불가능하다는점을해결한다. 그러나가비지컬렉션은유효페이지의복사작업과블록의소거작업과같은추가연산을필요로하기때문에이로인해입출력처리에대한지연시간이길어지거나대역폭이변동하는현상 (Bandwidth fluctuation) 이발생하기도한다. 이와같은문제를해결하기위하여 SSD의내부버퍼를쓰기버퍼로활용하여플래시메모리의부진한쓰기연산성능을보완하고이를통해가비지컬렉션의오버헤드를감소시키려는연구가수행되고있다. 특히 Sung Kyu Park [20] 은쓰기버퍼에대하여버퍼교체가발생한경우, I/O 병렬성을활용하기위해버퍼교체시각블록을하나의채널에할당하여하나의블록에속한페이지들이동일한플래시메모리블록에저장되는기법을제안하였다. 이로인해가비지컬렉션발생빈도가감소된다. 한편, 희생자페이지의개수가아니라희생자페이지가선택되는순서를고려하는연구들역시수행되어왔다. Jinho Seol [21] 은플래시메모리의연산단위가호스트인터페이스의연산단위보다커짐에따라 SSD는때때로부분적으로채워진페이지 (Partially-filled page) 에대한쓰기작업이수행될수있음을주장하였다. 이와같은쓰기작업은요청된섹터에해당되는페이지를읽어오고해당페이지에서요청된섹터로수정한다음, 수정된페이지를다시쓰는읽기- 수정- 쓰기 (Read-modify-read) 연산을수행하게끔한다. 그리고이러한연산은칩- 웨이팅 (Chip-waiting) 문제로이어지면서시스템의성능저하로이어질수있다. 이를해결하기위하여부분적으로채워진페이지를쓰게되는경우, 이웃한페이지를희생자페이지로선정하여 SSD의멀티칩을병렬로처리하며쓰기성능을개선하고있다. Xufeng Guo[22] 은 SSD 내부버퍼의병렬성을좀더극대화하는 PAB 기법을제안하였다. 이기법은버퍼를워크존 (Work zone) 과파라존 (Para zone) 으로분류하며워크존은일반적인버퍼관리기법을사용하여반복된쓰기연산을줄이고워크존이가득차면워크존에서페이지들을파라존으

10 40 데이터베이스연구제 32 권제 1 호 ( ) 로내보낸다. 파라존에서는페이지들을다중채널에맞게병렬단위 (Parallel unit) 를설정하여페이지들을재배치하여관리한다. 한편, Ronghui Wang [23] 은버퍼교체시, 희생자페이지의개수와순서를모두고려한 CAWR(Channel-Aware Write Reording mechanism for SSDs) 기법을제안하였다. 공간적지역성을고려하기위해페이지들을클러스터링 (Clustering) 하고각클러스터는 SSD의각채널과대응된다. 따라서버퍼교체가발생한경우, 각클러스터의페이지를각채널로동시에내보내어병렬성을높이고있다. 이와같은연구들은 SSD 내부버퍼를쓰기버퍼로활용하여 SSD의쓰기성능을보완하고자한연구들에해당되며 SSD의다중채널구조를활용하여가비지컬렉션에대한오버헤드를줄이는데의의를두고있다. 또한희생자페이지를선정할때희생될페이지의개수나순서를고려하고있다. 앞의연구와는다르게 SSD 내부버퍼를읽기버퍼로활용한연구도시도되고있다. 특히 Zhiguang Chen [24] 은 SSD 내부채널들사이에서수행되는워크로드의불균형을고려하였다. 여러개의채널들중특정채널들은읽기연산이집중된핫데이터 (Hot data) 를가지고있을수있는데여기에서제안한 SAC 기법은채널들을제외한나머지채널들에서희생자페이지를결정함으로써읽기연산을수행하는데평균적으로소요되는지연시간을감소시키고자한다. 이와같이 SSD를기반으로한버퍼관리기법들은주로플래시메모리의쓰기및지우기성능과이로인해발생되는가비지컬렉션에대한오버헤드를줄이는데목적으로두고있으며 SSD의다중채널구조를이용한버퍼관리기법들은플래시메모리의직접도기술과다중채널기술이끊임없이발전되므로이를고려한다양한버퍼관리기법들이 제시될수있음을알수있다. 3.3 NVRAM 의특성을이용한버퍼관리기법사실 NVRAM 의개념은매우오래된것으로, NVRAM 을쓰기버퍼로활용해느린하드디스크의 I/O 성능을높이려는시도는새로운것이아니다. 1988년발표된 Menon [25] 의논문에서이미유닉스환경에서파일시스템의쓰기연산성능을향상시키기위해 NVRAM 을사용, DRAM 과하드디스크사이의캐시로구성하고, NVRAM 에대한쓰기연산이완료되면하드디스크에대한쓰기가완료되지않더라도사용자어플리케이션혹은데이터베이스에완료프로토콜을전송하게된다. 이를네트워크파일시스템에적용한 Lyon [26] 의논문은비교적작은크기의블록을쓸때도동기화된쓰기연산을수행해야만하는네트워크파일시스템의프로토콜적특성으로인한성능저하를, 파일시스템을구동하고있는원격서버에 NVRAM 을위치시킴으로써해결하고있다. Baker [27] 가발표한논문에서는로그기반파일시스템 (Log-structured file system, LFS) 에서발생하는세그먼트의단편화현상으로인해증가하는하드디스크로의접근을줄이기위해 NVRAM 을통해일정크기의세그먼트를채운후에디스크로전송하여충분한대역폭을활용할수있게하였다. 지금까지의연구는하드디스크를기반으로 NVRAM 을활용한쓰기버퍼기법의연구에해당하는것으로, 2000년대들어등장한 SSD에는하드웨어적특성으로인해곧바로적용하기는비효율적인면이있었다. 하드디스크기반의쓰기버퍼기법에서고려하는요소는 NVRAM 에서하드디스크로전달되는쓰기연산의수를줄이기위한시간적지역성의활용과평균적인접근비용의감소를위한공간적지역성의

11 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 41 극대화로나타낼수있다. 시간적지역성은 SSD에대한쓰기버퍼기법에서도여전히유효한요소가될수있으나, 공간적지역성의경우디스크상에데이터가저장된위치가접근시간에영향을미치지않는 SSD의특성상고려되어야할요소라고볼수없게되었다. 대신 SSD의특성중하나인 FTL에서제자리덮어쓰기의불가능으로인해발생되는삭제연산과그로인해파생되는유효페이지들의병합연산을효율적으로다루기위해, 버퍼교체는해당삭제연산의단위인블록단위와동일하게구성되어야하며, 순차쓰기성능이무작위접근에비해매우빠른경향을고려하여순차쓰기가가능한버퍼영역을먼저내리도록고안할필요가있음을전제로한다. Park[28] 는이러한특성을고려하여 NVRAM 에위치한페이지들을하나의클러스터단위로묶어 SSD로전달할수있도록하며, 이를통해 FTL에서병합연산발생을최소화하고, 혹병합연산이발생하더라도부분병합 (Partial merge) 혹은교환병합 (Switch merge) 연산이발생할수있도록가능한한순차적쓰기연산의형태가되는희생자클러스터를구성하도록하는 CLC(Cold and Largest Cluster) 정책을제안했다. Kang [29] 은한발더나아가페이지를클러스터로구성하는정책과더불어다양한종류의버퍼교체정책을구현하고이를웹서핑, 전자메일등에서발생하는워크로드를통해평가하여페이지클러스터기반정책의유효성을입증하였다. 더나은성능이보장됨에도불구하고최근개발된 NVRAM 들이상용적으로발전하지못한이유는가격과수명문제인데, Kim [30] 은이러한문제점들을해결하는것이예측가능한미래에는불가능할것으로보고, 갑작스런전원공급중단사태에도일정시간전력을공급하여데이터의지속성 (Durability) 을보장하는전통적인접근법을통해 DRAM 을논리적으로비휘발성인영역과휘발성인영역으로구분하여비휘발성영역을 NVRAM 과같이간주하는방법론을제시했다. 이와동일한접근법을사용한 Yoo [31] 는플래시메모리를저장장치로사용하는가장활성화된사용자단말인스마트폰환경에서의플래시메모리에대한쓰기버퍼전략을평가하고, 추가적으로차세대 NVRAM 중의하나인 PRAM 을직접적으로사용했을때의성능평가를통해 NVRAM 의미래를점치고있다. 또한 SQLite 의 WAL(Write-Ahead Logging) 동작으로인해발생되는작은크기의 I/O로인한부하를더빠른지연대기성능을보이는 PRAM 을통해완화하고, 플래시메모리에대한쓰기횟수를줄여수명문제를해결하려한다. 이와같이 NVRAM 을활용한버퍼관리전략은메모리소자의발전에따라다양한특성을고려하여특화된형태로발전하고있음을확인할수있다. 이제까지의연구에서제시한기법들이플래시메모리의특성에입각해연구되었음에반해, 현재의차세대 NVRAM 들또한수명문제를본질적으로갖고있으므로, 쓰기버퍼로활용시특정비트에대한덮어쓰기연산발생시해당비트의수명이먼저다하는문제가발생할수있다. 이러한메모리소자의특성을다각도로고려한버퍼관리연구는수명문제와쓰기속도문제가극적으로개선되지않는한지속적으로유망할것으로판단된다. 4. 결론및향후과제 현대컴퓨터구조의확립이래로메인메모리와하드디스크의성능차이를메우기위한노력의일환으로 NAND 플래시메모리, 그리고 PRAM,

12 42 데이터베이스연구제 32 권제 1 호 ( ) STT-MRAM, ReRAM 과같은 NVRAM 계열의메모리소자등다양한종류의비휘발성메모리소자들이등장하고있다. 그럼에도불구하고제한된수명과부족한성능등으로인하여아직까지 DRAM 을대체할수있는비휘발성메모리소자는개발되지않고있으며, 예측가능한미래에도 DRAM 을완전히대체하기란불가능할것으로예상되고있다. 그러나플래시메모리또는 NVRAM 계열의차세대저장장치가발전함에따라하드디스크대비빠른성능을끌어내기위하여제한된수명문제를다양한방식으로억제하면서시스템에적용하려는시도가최근에도계속되고있다. 또한, 운영체제나데이터베이스시스템상에서앞서언급한차세대저장장치가하드디스크를대체하여사용되거나쓰기버퍼로활용하려는등의시도를통해성능향상을꾀하고있다. 현재까지개발된메모리소자들의경우, 각각이갖는물리적혹은논리적특성으로인해하드디스크에최적화된방식을그대로적용할경우, 원하는수준의성능향상을보이기어려울뿐만아니라수명이단축되는문제가있었다. 플래시메모리는쓰기연산의수행속도가읽기연산에비해확연히느리고셀마다쓰기및삭제연산의횟수가제한되어있다는단점을가지고있다. 이러한문제를해결하기위하여메인메모리를버퍼로할당하여플래시메모리의장점을이용하고단점을개선하려는연구가계속해서진행되어왔다. 최근에는플래시메모리기반 SSD의물리적, 논리적특성을더다양한측면에서고려한버퍼교체기법들이연구되고있다. 이러한예로는 SSD의내부병렬성과 FTL의동작방식을고려하여성능을향상시키려는시도가대표적이다. NVRAM 의경우에는바이트단위의연산을제공하고 NAND 플래시메모리보다지연대기시간 이빠르다는점에서주목받았으나, DRAM 에비해쓰기연산이느리고수명이제한적이기때문에근시일내에 DRAM 을대체하기는힘들것으로예측된다. 이로인해 DRAM 을대체하기보다는 SSD와 DRAM 사이의쓰기버퍼로활용하여 DRAM 에근접한수준의쓰기속도를보이기위한기법들이발표되고있는추세이다. 이외에도각 CPU 별로특정메모리가속한채널을통해 SSD로접근하는메모리채널플래시저장장치 (Memory channel flash storage) 와 DIMM 모듈에 NAND 플래시메모리나 PRAM 과같은비휘발성메모리를결합한 NVDIMM(Non-volatile dual in-line memory module) 이새로운저장장치로주목받고있다. NVDIMM 은전원공급을차단하면데이터가사라지는 DRAM 과달리, 데이터를영구저장할수있는비휘발성메모리가결합되었으므로예기치못한전원손실이발생했을경우에도데이터가안전하게저장되고복구할수있다. 또한, CPU와직접통신하는 DIMM 규격을가지며 DRAM 이일종의캐시메모리역할을수행하기때문에많은비용을들이지않고서도데이터처리속도를높이는것이가능하다. 그러나이러한연구흐름은수명문제및쓰기지연속도를극복하고 DRAM 을완전히대체하기전까지는지속적으로연구될것으로판단된다. 참고문헌 [1] Mu-Tien Chang, Rosenfeld. P, Shih-Lien Lu, Jacob. B, Technology comparison for large last-level caches (L 3 Cs): Low-leakage SRAM, low write-energy STT-RAM, and refresh-optimized edram, In

13 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 43 Proceedings of the 19th International Symposium on High Performance Computer Architecture, pp , 2013 [2] Y.Xie, Emerging NVM Memory Technologies, Presentation, Department of Computer Science and Engineering, Pennsylvania State University, USA, [3] Roberto Bez, Emilio Camerlenghi, Alberto Modelli, Angelo Visconti, "Introduction to Flash memory", IEEE, Vol.91, no.4, pp , 2003 [4] Yang Hu et al., "Exploring and exploiting the multilevel parallelism inside SSDs for improved performance and endurance", IEEE Transactions on Computers, Vol.62, no.6, pp , 2013 [5] Hyojun Kim et al., "Evaluating phase change memory for enterprise storage systems: A study of caching and tiering approaches", In Proceedings of the 12th USENIX Conference on File and Storage Technologies. pp.33-45, 2014 [6] Dmytro Apalkov et al., "Spin-transfer torque magnetic random access memory (STT-MRAM)", ACM Journal on Emerging Technologies in Computing Systems (JETC), Vol.9, no.2, 2013 [7] James L. Peterson, Abraham Silberschatz, "Operating system concepts (2nd ed.)", Addison-Wesley Longman Publishing Company, pp , 1985 [8] BELADY, L.A, "A study of replacement algorithms for virtual storage computers", IBM Systems, Vol.5, no.2, pp , 2010 [9] Mr.C.C.Kavar, Mr. S.S.Parmar, "Performance Analysis of LRU Page Replacement Algorithm with Reference to different Data Structure", Engineering Research and Applications, Vol.3, no.1, pp , 2013 [10] Heeseung Jo et al., "FAB: Flash-aware Buffer management policy for portable media players", IEEE Transactions on Consumer Electronics, Vol.52, no.2, pp , 2006 [11] Seon-yeong Park et al,. "CFLRU: A Replacement Algorithm for Flash memory", In Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems(cases), pp , 2006 [12] Hoyoung Jung et al., "LRU-WSR: integration of LRU and writes sequence reordering for flash memory", IEEE Transactions on Consumer Electronics, Vol.54, no.3, pp , 2008 [13] Yi Ou, Theo Harder, Peiquan Jin, "CFDC: a flash-aware replacement policy for database buffer management", In Proceedings of the 5th International Workshop on Data Management on New Hardware, pp.15-20, 2009 [14] Zhi Li et al., "CCF-LRU: a new buffer replacement algorithm for flash memory", IEEE Transactions on Consumer Electronics, Vol.55, no.3, pp , 2009 [15] Bo-Kyeong Kim, Dong-Ho Lee, "LSF: a new buffer replacement scheme for flash memory-based portable media players", IEEE Transactions on Consumer Electronics, Vol.59, no.1, pp [16] Victor F. Nicola, Asit Dan, Daniel M. Dias, "Analysis of the generalized clock buffer replacement scheme for database transaction processing", In Proceedings of the 1992 ACM

14 44 데이터베이스연구제 32 권제 1 호 ( ) SIGMETRICS joint international conference on Measurement and modeling of computer systems, pp.35-46, 1992 [17] Biplob Debnath, Sunil Subramanya, David Du, David J. Lilja, "Large Block CLOCK (LB-CLOCK): A write caching algorithm for solid state disks", In Proceedings of Modeling, Analysis&Simulation of Computer and Telecommunication Systems, pp.1-9, 2009 [18] Hyojun Kim, Moonkyung Ryu, Umakishore Ramachandran, "What is a good buffer cache replacement scheme for mobile flash storage?", In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pp , 2012 [19] Dong Hyun Kang, Changwoo Min, Young Ik Eom, "TS-CLOCK: temporal and spatial locality aware buffer replacement algorithm for NAND flash storages", In Proceedings of the ACM international conference on Measurement and modeling of computer systems, pp , 2014 [20] Sungkyu Park, Youngwoo Park, Gyudong Shim et al., CAVE: channel-aware buffer management scheme for solid state disk, In Proceedings of the 2011 ACM Symposium on Applied Computing, pp , 2011 [21] Jinho Seol et al., A buffer replacement algorithm exploiting multi-chip parallelism in solid state disks, In Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems, pp , 2009 [22] Xufeng Guo, Jianfeng Tan et al., PAB: parallelism-aware buffer management scheme for NAND-based SSDs, In Proceedings of the 21st International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems(MASCOTS), pp , 2013 [23] R Wang et al., "CAWR: Buffer Replacement with Channel-Aware Write Reordering Mechanism for SSDs.", ETRI, Vol.37, no.1, pp , 2015 [24] Z Chen, N Xiao, F Liu, Sac: rethinking the cache replacement policy for ssd-based storage systems, In Proceedings of the 5th Annual International Systems and Storage Conference, 2012 [25] Menon J., Hartung M., The IBM 3990 Disk Cache, In Proceedings of COMPCON, pp , 1988 [26] Lyon B., R. Sandberg, "Breaking Through the NFS Performance Barrier.", SunTech, pp.21-27, 1989 [27] Baker Mary et al. "Non-volatile memory for fast, reliable file systems.", ACM SIGPLAN Notices. Vol.27. no [28] Park, S et al., Using non-volatile ram as a write buffer for nand flash memory-based storage devices, In Proceedings of Modeling, Analysis and Simulation of Computers and Telecommunication Systems (MASCOTS), 2008 [29] Kang S. et al., "Performance trade-offs in using NVRAM write buffer for flash memory-based storage devices.", IEEE Transactions on Computers, pp , 2009 [30] Kim D., S. Kang, Dual region write buffering: making large-scale nonvolatile buffer using small capacitor in SSD, In Proceedings of the 30th Annual ACM Symposium on Applied Computing, pp , 2015

15 차세대메모리를활용한데이터베이스기반버퍼관리기법의최신동향 45 [31] Ungjoo Yoo et al., "Reducing Mobile Storage Writes: Non-Volatile Write Buffer and PRAM-based Journaling." 정보과학회지, Vol.33, no.2, pp.52-59, 2015 이미경 2014 년동덕여자대학교컴퓨터학과학사 2014 년 ~ 현재연세대학교컴퓨터과학과석사관심분야 : 데이터베이스, 버퍼관리기법, 플래시메모리김재형 2007 년한양대학교컴퓨터공학과학사 2009 년한양대학교컴퓨터공학과석사 2013 년 ~ 현재연세대학교컴퓨터과학과박사관심분야 : 데이터베이스, 스토리지, 빅데이터박상현 1989 년서울대학교컴퓨터공학과학사 1991 년서울대학교대학원컴퓨터공학과공학석사 1991 년 UCLA 대학원컴퓨터과학과공학박사 1991 년 ~1996 년대우통신연구원 2001 년 ~2002 년 IBM T. J. Watson Research Center Post-Doctoral Fellow 2002 년 ~2003 년포항공과대학교컴퓨터공학과조교수 2003 년 ~2006 년연세대학교컴퓨터과학과조교수 2006 년 ~2011 년연세대학교컴퓨터과학과부교수 2011 년 ~ 현재연세대학교컴퓨터과학과교수관심분야 : 데이터베이스, 데이터마이닝, 바이오인포매틱스, 적응적저장장치시스템, 플래시메모리인덱스, SSD