다중 - 채널및다중 - 웨이반도체디스크를위한플래시변환계층 685 다중 - 채널및다중 - 웨이반도체디스크를위한플래시변환계층 (Flash Translation Layer for the Multi-channel and Multi-way Solid State Disk) 박현철 신동군 (Hyunchul Park) (Dongkun Shin) 요약플래시메모리는전력소비가적고처리속도가빨라임베디드시스템의저장매체로서많은연구가이루어져왔다. 특히, 최근에는플래시메모리로구성된반도체디스크 (Solid state disk, SSD) 가하드디스크를점점대체하고있는추세이다. 현재 SSD 는성능을높이기위해서병렬성을이용한다중채널과다중웨이를사용하고있다. 이구조에서는연속된여러개의블록들로구성된슈퍼블록단위로플래시메모리에기록하게된다. 본논문은병렬처리를최적화하기위해 SSD 의버퍼를비울때희생슈퍼블록을선정하고재구성하는방법을제안하고있다. 실험을통해서희생슈퍼블록선정방법을바꾸는것으로슈퍼블록단위의쓰기횟수를 35% 줄일수있고, 슈퍼블록구성방법을달리하여 9% 를추가적으로더줄일수있었다. 키워드 : 플래시메모리, SSD, FTL, 다중채널 Abstract Flash memory has several features such as low-power consumption and fast access so that there has been various research on using flash memory as new storage. Especially the Solid State Disk which is composed of flash memory chips has recently replaced the 이논문은 2008년정부 ( 교육과학기술부 ) 의재원으로한국학술진흥재단의지원을받아수행된연구임 (KRF-2008-314-D00351) 이논문은제34회추계학술대회에서 다중채널반도체디스크를위한플래시변환계층 의제목으로발표된논문을확장한것임 학생회원 : 성균관대학교정보통신공학부 hcpark@skku.edu 정회원 : 성균관대학교정보통신공학부교수 dongkun@skku.edu (Corresponding author 임 ) 논문접수 : 2008년 12월 19일심사완료 : 2009년 7월 1일 CopyrightC2009 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제15권제9호 (2009.9) hard disk. At present, SSD adopts the multi-channel and multi-way architecture to exploit advantages of parallel access. In this architecture, data are written on SSD in a unit of a superblock which is composed of multiple blocks in which some blocks are put together. This paper proposes two schemes of selecting, segmenting and re-composing victim superblocks to optimize concurrent processing when a buffer flush occurs. The experimental results show that 35% of superblock- based write operations is reduced by selecting victims and additional 9% by composition of superblock. Key words :Flash Memory, SSD, FTL, Multi-channel 1. 서론 최근다방면에서플래시메모리가활용되는비중은급속도로커졌다. 이는빠른처리속도, 비휘발성, 무소음, 저전력, 내구성같은특징때문이다. 특히여러개의낸드 (NAND) 플래시칩과제어장치로구성된 SSD[1] 는차세대저장장치로써주목받고있다. 그러나플래시메모리는덮어쓰기가불가능하고, 읽기와쓰기는페이지단위인데지우기는연속한페이지들의집합인블록단위로수행되는단점이있다. 따라서기존의파일시스템에게플래시메모리가하드디스크인것처럼에뮬레이션 (Emulation) 해주는플래시변환계층 (Flash Translation Layer, FTL)[2,3] 이필요하다. 현재 SSD는다수의플래시메모리칩들을병렬로배치하는다중채널 (Multi-channel) 다중웨이 (Multi-way) 구조를활용하고있다 [4]. 이구조에서는다수의플래시메모리칩들에동시접근이가능하다. 이를뒷받침하기위해슈퍼블록이라는맵핑단위를도입하였고, 슈퍼블록단위에특화된 FTL의고안이필요하다. 본논문에서는 SSD 의병렬성을최대한활용하기위한 SSD의쓰기버퍼관리방법과슈퍼블록구성기법을제시하고있다. 본논문의내용은다음과같다. 2장에서는다중채널다중웨이 SSD 구조의특성과문제점을설명하고, 3장에서는 SSD의병렬성을활용하는방법을제시한다. 4 장에서는시뮬레이션을통한실험결과를보여주며, 5장에서는결론을맺고, 추가연구주제를소개한다. 2. 다중웨이다중채널 SSD 본논문에서다루고있는 SSD의구조는그림 1과같이 4 채널 & 2 웨이 SSD이다. 기존의 SATA, SCSI등의입출력인터페이스의대역폭은 150MB/s인데비해, 낸드플래시버스의대역폭은 40MB/s에불과하다. 그러나각버스의낸드제어기 (Controller) 들을통하여 4 개의버스에동시에데이터를전송한다면전체대역폭이 160MB/s가되어서기존의 I/O 인터페이스를충분히
686 정보과학회논문지 : 컴퓨팅의실제및레터제 15 권제 9 호 (2009.9) 그림 1 4-channel & 2-way SSD 구조지원할수있다. 또한버스내에서도 8개의칩들이 4쌍으로묶여서한쌍의칩들에대해서동시에접근이가능하다. 따라서총 8개의칩에서동시에명령을처리할수있기때문에플래시메모리칩의쓰기속도의최대 8배의속도로쓸수있으며, 4개의버스에서동시에데이터를전송받을수있으므로플래시메모리칩의원래읽기속도의최대 4배의속도로읽을수있다. 그리고 SSD 내부에는 DRAM 버퍼가있어서호스트로부터의쓰기요청을버퍼링 (Buffering) 한다. 2.1 슈퍼블록단위의명령수행본구조의장점을활용하기위해서는쓰기버퍼에서데이터를모아서각각의버스와칩들에동시에보내줄수있어야한다. 이를위해 8개의블록으로구성된슈퍼블록 (Superblock) 단위로전송하면효율적이다. 슈퍼블록의구성방법을알아보면, 우선각버스에서동일한위치에있는 4쌍의칩들을모아서슈퍼칩 (Superchip) 으로간주한다. 즉 4개의버스의 0번칩들과 1 번칩들을모아서 0번슈퍼칩으로간주한다. 그리고슈퍼칩의 8개의칩들에서같은번호의블록 8개를모은슈퍼블록을작업수행의기본단위로사용한다. 그림 2 는이구성을나타낸다. 읽을때에는한개의페이지만읽을수있고, 플래시메모리칩수준의명령은페이지와블록단위로수행된다. 그림 2 슈퍼블록의구성 2.2 슈퍼블록전송시문제점제시된구조의쓰기버퍼에서슈퍼블록단위로데이터를모을때, 일부칩들에쓸데이터가없는불완전한슈퍼블록이발생할수있다. 이경우, 맵핑 (Mapping) 단위를유지하기위해서갱신되지않는블록까지복사하는낭비가발생하게된다. 그림 3은쓰기버퍼의내용을플래시메모리에기록할때논리슈퍼블록 (Logical Superblock, LSB) 0번부 터순서대로비울경우의상황을나타낸다. 쓰기버퍼를비우기전 LSB들이같은번호의물리적슈퍼블록 (Physical Superblock, PSB) 에맵핑되어있다고가정하자. 쓰기버퍼의사용량이일정수준을넘어서비워야하는경우, LSB 0에갱신할내용이있기때문에빈 PSB 4를할당받아서기존의내용과새로운내용을합쳐서 PSB 4에쓴다. 그리고 PSB 0은무효화 (Invalidate) 되면서 LSB 0이 PSB 4에맵핑된다. 그러나블록 0, 1, 4 에해당하는데이터만갱신되어서 PSB 4로이동되고, 블록 2, 3, 5, 6, 7의데이터는 PSB 4로그냥이동되는것이다. 만약, 이후에갱신되지않았던곳이갱신되면새로운 PSB를할당받아서써야하므로비효율적이다. 그림 3 슈퍼블록단위의쓰기의문제점 3. 다중채널다중웨이 SSD 구조를위한 FTL 불완전한슈퍼블록의쓰기를막기위해이논문에서는두가지방법을제시하고있다. 첫째는버퍼를비울때내보낼희생슈퍼블록을결정해서일부만보내는것이다. 둘째는슈퍼블록에서갱신할데이터를다른슈퍼블록에서가지고와서모든칩에갱신할데이터를보낼수있는완전한슈퍼블록을구성하고, 다중수준주소맵핑 (Multi-level address mapping) 으로맵핑하는것이다. 3.1 희생슈퍼블록결정 DRAM 버퍼는덮어쓰기가가능하므로버퍼적중률 (Hit rate) 를높이고, 데이터를최대한모아서보내는것이쓰기횟수를줄일수있다. 따라서데이터가가장많이모인 LSB를희생슈퍼블록으로선정할수있다. 그러나상대적으로크기가작은데이터가계속남게되어, 버퍼의공간을차지하고버퍼적중률을떨어뜨릴수있다. 그러므로접근된지오래된것일수록희생대상으로선택하는 LRU(Least Recently Used) 기법을사용해야한다. 하지만 LRU만따르다보면접근된지오래되고데이터가조금모인불완전한 LSB가선정될수있다. 따라서희생슈퍼블록을선정할때 LSB에모인데이터의양과 LRU를동시에고려하여선택해야한다. 이를위해본논문에서는다음과같은희생슈퍼블록선정휴리스틱 (Heuristics) 을제안한다. (1)
다중 - 채널및다중 - 웨이반도체디스크를위한플래시변환계층 687 위의식 (1) 에서 R(i) 는 LSB i의우선순위를의미한다. n은쓰기버퍼에있는 LSB들의개수이며, X i 는 LSB i의 LRU 정도 (0: 가장최근에접근, n-1: 가장접근한지오래됨 ), Y i 는 LSB i에데이터가모여진양의순위 (0: 가장크기가작음, n-1: 가장크기가큼 ) 이다. 위의식을통하여우선순위가가장큰것을희생슈퍼블록으로선택한다. 3.2 다중수준블록맵핑 (Multi-level Block Mapping) 희생슈퍼블록들이불완전하다면이들을모아서완전한슈퍼블록으로만들어쓰는것이성능향상에유리하다. 이를위해서슈퍼블록보다작은단위의맵핑테이블이필요하다. 본논문에서는슈퍼블록들을조립하는두가지방법을제안하는데블록들의물리적위치를고려하지않고최대한조합하는 Best-fit Composition( 이하 Best-fit) 과블록들의물리적위치를고려한 Location-fit Composition( 이하 Location-fit) 이다. 그림 4는 Best-fit에서 LSB들을이용하여가상슈퍼블록 (Virtual Superblock, VSB) 을만들어서플래시메모리에쓰는과정을보여준다. 이때, 각블록들의 LSB 내에서의위치와상관없이 VSB를구성하게된다. 그림 4에서는 4개의 LSB를가지고 3개의 VSB를만드는예를보여주고있다. 예를들어 VSB 0은 LSB 0, 2, 3에서연속하는한쌍의블록들을모은것이고, 새로운내용이없는페이지나블록은플래시메모리에기록하게될때원래내용을복사해온다. 이렇게완성된 3개의 VSB만을플래시메모리에기록하면되므로기존의방법보다휠씬플래시메모리에대한 I/O 요청량을줄일수있게된다. 본논문에서는조립의최소단위는 LSB 내에서연속한 2개의블록으로했다. 따라서 VSB 0을구성할때새로운내용이없는 5번, 24번블록은플래시메모리칩에서복사해야한다. VSB의조립을위해서슈퍼블록보다작은단위의맵핑테이블이필요하기때문에그림 5처럼 L1 테이블과 L2 테이블을이용한다. L1 테이블은블록 4개단위의맵핑정보를기록하며, PSB의번호와 PSB 내에서의위치를가리키는 1bit를포함하고있다. L2 테이블은블록 2개단위의맵핑정보를기록하고있으며, PSB 번호와 PSB 내에서의위치를알려주는 2bits를포함하고있다. L0 테이블은기본적으로 PSB 번호를가리키지만조각나게되면조각난부분이 L1, L2 테이블의위치를가리키고, 현재해당 LSB가얼마나조각나있는지알리는 3bits를포함하고있다. 물론, SSD의 DRAM의가용공간이 L1테이블과 L2 테이블을위한추가공간으로인하여줄어들게된다. 그렇지만 32GB SSD에서다중수준블록맵핑을위한맵 그림 4 Best-fit Superblock Composition 핑테이블크기는 80.25KB로슈퍼블록맵핑시 60KB 가필요한것에비하면추가공간의크기는크다고할수없고, 슈퍼페이지맵핑시필요한 5.25MB의 2% 도안되는크기이다. 32GB SLC SSD에서각맵핑방법의테이블크기는다음과같다. 여기서 L1테이블과 L2테이블은각각 2048개의엔트리를가질수있다. 그림 5 Best-fit Composition 맵핑테이블 슈퍼블록의크기 : 1MB, 슈퍼블록의개수 : 2 15 개 슈퍼페이지의크기 : 16KB, 슈퍼페이지의개수 : 2 21 개 슈퍼페이지맵핑테이블크기 : 21bit * 2 21 = 5.25MB 슈퍼블록맵핑테이블크기 : 15bit * 2 15 = 60KB 다중수준블록맵핑 : L0테이블 : (16bit + 3bit) * 215 = 72KB L1테이블 : (15bit + 1bit) * 211 = 4KB L2테이블 : (15bit + 2bit) * 211 = 4.25KB 총크기 : 80.25KB LSB 2번에서왼쪽두쌍의블록은 L2 테이블의 4번, 5번엔트리에 PSB 정보가기록되어있으며, 오른쪽두쌍의블록은 L1 테이블의 0번엔트리에 PSB 정보가기록되어있다. 만약메모리상에테이블을위한공간이더이상없을경우보조테이블들이가리키는블록들을새로운 PSB에옮겨서 L1테이블과 L2테이블의내용을 L0 테이블로합쳐야하는추가작업이요구된다. Best-fit 방법은 SSD의용량을최대한활용할수있지만, 블록들의위치가다른칩으로바뀌게되어일단데이터를 DRAM으로읽어왔다가쓰는횟수가많아진다. 이를막기위해플래시메모리가지원하는 copyback 명령이있다. 이명령은같은칩내부에서데이터가이동하는경우내부페이지버퍼를거치게한다. 그
688 정보과학회논문지 : 컴퓨팅의실제및레터제 15 권제 9 호 (2009.9) 러므로가급적블록들의위치를유지한채 VSB을구성하면후에갱신이일어나도 copy-back만으로새로운데이터를쓸수있게된다. 다른칩에써야할경우, 기존방법처럼읽어온후쓰기를수행한다. 이것이 Location-fit방법이며그림 6에표현되어있다. 그림 6 Location-fit Superblock Composition 위의그림 6과같이 VSB를구성하는데있어서블록들의원래위치를지키는것을볼수있다. 예를들어 VSB 0을구성하기위하여 LSB 0, 3이참여한다. VSB 0의마지막 2개블록에 LSB 2의 22, 23번블록이들어갈수도있다. 그러나 Best-fit과 Location-fit에서는남는공간을채우기위해연속된 4개의블록이나 8개의블록을억지로분리시키지않는다. 따라서 VSB 0은버퍼에남게되고, 대신완전한 VSB 2가희생대상으로선택되는것이다. 이방법에선 L1, L2테이블에서위치정보를포함할필요가없다. 하지만위치를지키다보니완전한슈퍼블록을구성하기힘들어지는경우가발생하게되며, 버퍼의용량부족등의원인으로인하여어쩔수없이써야할경우플래시메모리내에서데이터의불필요한이동이발생하게된다. (Wear-leveling) 방법은이논문의주요관심사가아니므로할당받을블록이없을때에만무효화된블록을지우고, 블록을할당받을때블록의지워진횟수는고려하지않고지워진횟수가십만번이넘으면더이상지울수없는블록으로관리하게하였다. 실험에쓰인트레이스 (Trace) 는데스크탑컴퓨터에서프로그램설치및실행, MP3 플레이어, 웹브라우저와게임등의다양한응용프로그램을실행하며수집한트레이스와 2GB의 JPEG 파일을복사하면서생기는순차적인접근들을수집한트레이스를사용하였다. 4.2 실험결과그림 7은데스크탑컴퓨터에서다양한작업을수행할때발생한쓰기요청을보여주고있다. 세로축은슈퍼블록단위의쓰기횟수를나타내며가로축은기법들을나타내고있다. 여기서 Default는슈퍼블록단위를그대로사용하는방법이다. Size는슈퍼블록에모인데이터의양을기준으로선정하는것이고, LRU기법과 Size를같이고려하는경우가 LRU+Size이다. 가장우측의 FlushAll로표기된부분은 DRAM 버퍼를비울때모든데이터를내보내는가장기본적인방법이다. 그리고막대의형태는완전한슈퍼블록과불완전한슈퍼블록을나타낸다. 4. 실험과분석 4.1 실험조건실험은 16MB DRAM 버퍼와 32GB의 4 채널, 2 웨이 SSD의시뮬레이터를만들어서수행하였다. 맵핑의수준이최소블록 2개단위로이루어지기때문에블록수준의명령을처리하도록하였다. 실험의낸드플래시메모리는 SLC(Single Layer Cell) 이다. 그리고한페이지는 2KB이고, 한블록은 64 개의페이지로이루어져있다. 한개의낸드플래시메모리칩은 8192개의블록으로이루어져 1GB이된다. 쓰기버퍼의데이터들은슈퍼블록단위로관리한다. 사용량이 90% 를넘으면버퍼를비우기시작하고, 가용량이전체용량의 50% 이상이될때까지수행한다. 맵핑테이블들의크기에제한을두지않고 DRAM에서맵핑테이블들이차지하고있는영역은고려하지않았다. 폐영역회수 (Garbage Collection) 방법과웨어레벨링 그림 7 데스크톱에서다양한작업수행시성능비교가장기본적인방법인 FlushAll을보면불완전한슈퍼블록이많이발생하고있음을확인할수있다. 희생대상선정방법들을비교하기위해 Default를보면, Size 가슈퍼블록쓰기횟수를가장많이줄이고불완전한슈퍼블록도가장적게발생시키는것을볼수있다. 그러나특정데이터가버퍼에계속머무르는것을막기위해 LRU를도입했지만 LRU는불완전한슈퍼블록들로인해성능이떨어진다. 따라서 LRU+Size를사용하면데이터가골고루희생대상으로선정되면서성능개선도이룰수있다. 이때 Size는 FlushAll에비하여 46% 만큼슈퍼블록쓰기횟수를줄었고 LRU+Size도 35% 의감소를보여준다.
다중 - 채널및다중 - 웨이반도체디스크를위한플래시변환계층 689 LRU나 LRU+Size의경우불완전한슈퍼블록이많이발생하기때문에 Best-fit과 Location-fit을통해서쓰기횟수를더줄일수있다. Default와 Size의조합에서는불완전한슈퍼블록의비중이작기때문에 Best-fit으로인한개선을기대하기힘들고, Default와 LRU+Size의조합에선 Best-fit 기법을통해추가적으로 9% 를줄일수있음을알수있다. Location-fit 기법의경우 Best-fit 기법보다완전한슈퍼블록을만드는데효율이약간떨어졌다. 그림 8은 2GB의 JPEG 파일을복사할때 SSD의플래시메모리에보내진쓰기요청을보여주고있다. 그래프의형식은그림 7과동일하다. 이경우, 순차적인접근이주로발생하므로 FlushAll에서도완전한슈퍼블록이많이생긴다. 또한 Default에서 Size와의조합보다 LRU와의조합이슈퍼블록의쓰기횟수가더줄어들었다. 그이유는 Size에선동일한슈퍼블록에연속적으로쓰기명령이들어오는도중에그슈퍼블록이희생대상으로선정되어써지기때문이다. 그러나 LRU 경우엔가장최근에접근된슈퍼블록이므로희생대상으로선정되지않는다. LRU+Size는접근된지오래되면서병렬처리의효율을높일수있는슈퍼블록을선택하므로쓰기횟수를더줄일수있다. 여기에 Best-fit을적용하여최종적으로 FlushAll에비해 22% 만큼쓰기횟수를줄일수있다. 그림 9 Best-fit과 Location-fit의비교없고시간이더걸린다는단점이있다. 블록들의위치를고려하지않는 Best-fit과달리, Location-fit 기법은블록들의위치를지키기위해노력하므로 R&W의횟수가줄어들고, 처리속도가더빨라진다. 하지만 Best-fit 기법은플래시메모리의공간을최대한사용할수있기때문에각각의장단점이있다. 5. 결론본논문에선다중채널다중웨이 SSD가슈퍼블록맵핑을사용하면병렬성을제대로활용하지못할수있음을보였다. 그리고병렬처리의효율을극대화하기위하여버퍼에서플래시메모리로내보낼희생슈퍼블록을선정하는방법을제시하였고, 슈퍼블록을구성할수있는다양한방법들과이를지원하기위한다중레벨맵핑방법도제시하였다. 또한버퍼를비우는방법과슈퍼블록을구성하는방법에따라서 44% 까지슈퍼블록쓰기횟수를줄일수있다는것을실험을통해서보였다. 마지막으로 L1 테이블과 L2 테이블을효율적으로관리하는방법을연구하는것이추가연구주제이다. 참고문헌 그림 8 2GB의 JPEG파일을복사할때성능비교그림 9에서는그림 7과동일한실험에서 Best-fit과 Location-fit을비교하기위한결과를보여주고있다. 가로축은실험한방법들을나타내고있으며세로축은블록단위의쓰기횟수를나타낸다. R&W(read-andwrite) 는 copy-back 대신우선 DRAM으로읽어왔다가다른칩의블록에쓰는것을의미한다. R&W를수행해야하는경우는, 첫번째, 슈퍼블록내에서블록의위치가바뀌어서다른버스의칩으로데이터를옮겨야하는경우이고, 두번째는다른슈퍼칩으로데이터를옮겨야하는경우이다. copy-back은수행중에다른칩에명령을보낼수있지만, R&W는읽고쓰면서버스를점유하기때문에다른칩에명령을보낼수 [1] Samsung Electronics. "Solid State Drive Data Sheet, "http://www.samsung.com/global/business/semicon ductor/products/flash/products_flashssd.html. [2] J.KIM, J.M.Kim, S.H.Noh, S.L.Min, Y.Cho, "A space-efficient flash translation layer for compact flash systems," IEEE Transactions on Consumer Electronics, vol.48, no.2, pp.366-375, 2002. [ 3 ] S.W.Lee, D.J.Park, T.S.Chung, W.K.Choi, D.H.Lee, S.W.Park, H.J.Song, "A log buffer based flash translation layer using fully associative sector translation," ACM Transactions on Embedded Computing Systems, vol.6, no.3, 2007. [4] J.U.Kang, J.S.Kim, C.Park, H.Park, J.LEE, "A Multi-channel Architecture for High-performance NAND flash-based storage system," Journal of Systems Architecture, vol.53, no.9, pp.644-658, 2007.