실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 463 실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 (Log Buffer Management Scheme for NAND Flash Memory in Real-Time Systems) 조현진 하병민 신동군 엄영익 (Hyunjin Cho) (Byung Min Ha) (Dongkun Shin) (Young Ik Eom) 요약플래시메모리는일관된성능, 저전력및내구성등의특징으로인해실시간시스템에적합한저장장치로주목받고있다. 하지만플래시메모리는무효화된페이지의가비지컬렉션수행을위한정체시간 (blocking time) 을필요로하는데, 기존의플래시메모리관리기법에서는가비지컬렉션을위한최대정체시간 (worst case blocking time) 과최소정체시간 (best case blocking time) 의차가크다는문제점이있다. 본논문에서는 KAST 라불리는 FTL(Flash Translation Layer) 을제안하며, 제안시스템에서사용자는가비지컬렉션에따른최대정체시간을설정할수있도록한다. 실험을통해 KAST 는사용자가설정한시간내가비지컬렉션을완료하며, 기존 FTL 보다 10~15% 성능향상을보임을확인한다. 키워드 : 플래시메모리, 플래시메모리계층변환, 로그버퍼관리기법, 실시간시스템 Abstract Flash memory is suitable for real time systems because of its consistent performance for random access, low power consumption and shock resistance. However, flash memory needs blocking time to perform a garbage collection to reclaim invalidated pages. Moreover, the worst-case garbage collection time is significantly longer than the best-case garbage collection time. In this paper, we propose a FTL (Flash Translation Layer) mapping scheme called KAST (K-Associative Sector Translation). In the KAST scheme, user can control the maximum association of the log block to limit the worst-case garbage collection time. Performance evaluation using simulation shows that not only KAST completes the garbage collection within the specified time but also provides about 10~15% better average performance than existing FTL schemes. Key words :Flash memory, FTL(Flash Translation Layer), log buffer management scheme, realtime systems 이논문은 2008년정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (KRF-2008-314-D00351) 본연구는지식경제부및정보통신연구진흥원의대학 IT연구센터지원사업의연구결과로수행되었음 (IITA-2009-(C1090-0902-0046)) 학생회원 : 성균관대학교컴퓨터공학과 hjcho@ece.skku.ac.kr chaosken@ece.skku.ac.kr 정회원 : 성균관대학교컴퓨터공학과교수 dongkun@skku.edu (Corresponding author 임 ) 종신회원 : 성균관대학교컴퓨터공학과교수 yieom@ece.skku.ac.kr 논문접수 : 2009년 2월 6일심사완료 : 2009년 7월 30일 CopyrightC2009 한국정보과학회ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 시스템및이론제36권제6호 (2009.12) 1. 서론플래시메모리는저전력, 비휘발성, 높은랜덤접근성능및작은물리적공간을차지하는특징으로인해휴대용임베디드기기에널리사용되고있다. 낸드플래시메모리는 MP3 플레이어와디지털카메라같은휴대용기기의대용량저장장치로써사용이활성화되고있고, 이로인해점차시장의규모가커지고있다. 또한낸드플래시메모리기반의 SSD(Solid State Disk) 는데스크톱컴퓨터의저장장치인하드디스크를대체하려는움직임을보이고있다 [1,2]. 플래시메모리는내구성으로인해산업제어시스템, 자동차및우주왕복선같은높은신뢰성을요구하는실시간시스템에적합하다. 또한하드디스크와는달리탐구시간 (seek time) 없이원하는데이터에접근할수
464 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) 있기때문에입 / 출력성능의예측이필요한실시간시스템에적용하는것이유리하다. 하지만플래시메모리는 2가지단점으로인하여 DRAM 을사용할때처럼일관된성능을기대할수는없다. 이는플래시메모리를실시간시스템에적용하기위해반드시해결해야하는치명적인장애요소라할수있다. 플래시메모리의첫번째단점은반드시삭제된상태에서만데이터의기록이가능하다는것이다. 두번째단점은읽기, 쓰기단위와삭제의단위가다르다는점이다. 플래시메모리의읽기와쓰기는페이지단위로수행하며삭제는블록단위로수행한다. 플래시메모리의블록은다수의페이지로구성되며, 삼성전자의대용량페이지 (large page) 기반플래시메모리의경우페이지의크기는 2KB이며블록은총 64개의페이지로구성된다. 위에서언급한플래시메모리의특징으로인해플래시변환계층 (FTL: Flash Translation Layer) 이라는시스템소프트웨어가필요하다. FTL은파일시스템의논리적인주소영역과플래시메모리의물리적인주소영역간매핑 (mapping) 을수행한다. 플래시메모리매핑은매핑단위에따라블록매핑과페이지매핑으로구분된다. 블록매핑을사용하면블록단위의데이터갱신을수행해야한다. 따라서블록내한개의페이지만갱신이된다고해도나머지페이지는새롭게할당된블록에재기록되어야한다. 따라서블록매핑방법을사용할경우데이터갱신에따른오버헤드가크다. 페이지매핑을사용하면데이터기록및갱신을빨리수행할수있다. 예를들어논리페이지주소 100번지의데이터기록요청이발생하여물리페이지주소 200번지에데이터기록을했다고가정한다. 이후논리페이지주소 100번지의갱신이발생하면이전에기록된물리페이지주소 200번지의데이터를무효화 (invalidation) 한후새로운물리페이지주소 201번지에갱신된데이터를기록한다. 따라서페이지매핑을사용할경우갱신된페이지만새로운페이지에기록하면된다. 이러한데이터갱신이빈번하게발생하게되면많은수의무효화된페이지가발생한다. 그러므로, 가비지컬렉터 (garbage collector) 를통해무효화된페이지를소거하여플래시메모리의공간을확보해야한다. 이때가비지컬렉터는블록내유효페이지 (valid page) 만을새로운블록으로복사한후해당블록을삭제한다. 플래시메모리에서수행하는연산중가비지컬렉션이가장큰연산비용을소모하며해당연산에따라플래시메모리응답시간의변동이발생한다. 이러한점을고려하여페이지매핑을위한실시간가비지컬렉션기법이제안되었다 [3]. 하지만페이지매핑은 SSD와같은대용량플래시메모리를사용하는환경에서는매핑테이 블의크기가매우커진다는단점이있다. 따라서최근블록매핑기법의장점과페이지매핑기법의장점을혼합한하이브리드매핑 (hybrid-level mapping) 기법에대한연구가활발하게진행되고있다. 이기법에서는플래시메모리의물리블록을데이터블록과로그블록으로구분한다. 로그블록은로그버퍼라고도하며하이브리드매핑기법을사용하는 FTL을로그버퍼기반 FTL(log buffer-based FTL) 이라고한다. 하이브리드매핑기법에서는데이터블록은블록매핑을, 로그블록은페이지매핑을통해데이터를관리한다. 하이브리드매핑기법에서사용하는로그블록의최대개수는유지가능한페이지매핑테이블의최대크기에따라결정된다. 파일시스템에서데이터갱신이발생하면데이터블록에있는기존의데이터는무효화된후로그블록에갱신된데이터가기록된다. 만약모든로그블록에데이터가기록되어더이상기록할수없다면로그블록중하나를선택하여유효한데이터들을새로운데이터블록으로복사한후해당로그블록을삭제한다. 이과정을로그블록병합이라하며, 로그블록병합은하나의로그블록에대해서만수행하기때문에페이지매핑에서수행하는가비지컬렉션에비해오버헤드가작다. 따라서로그블록기반의플래시변환계층은실시간시스템에적합하다고할수있다. 또한페이지매핑기법에비해작은크기의매핑테이블을사용한다는장점이있다. 하지만하이브리드매핑기법은 2장에서설명할로그블록연관성에따라병합연산수행시간이달라질수있으며, 최악의경우병합연산을위해큰지연시간이발생할수있다. 시간엄수시스템 (time-critical system) 환경에서는시스템의활용률을높이기위해최대지연시간을감소시키는것이중요하다. 현재까지플래시메모리의전체 I/O 수행시간을감소시키기위해하이브리드매핑기법개선에관한많은연구가진행되었다 [4-8]. 하지만플래시메모리를사용하면서성능상의변동을최소화하는기법에대한연구는미비하다. 실시간시스템에서는해당작업의완료를예측하여정해진시간내작업을완료할수있어야한다. 본논문에서는이러한점을고려하여플래시메모리사용시성능의변동을최소화할수있는매핑기법을제안한다. KAST라불리는제안기법은사용자가플래시메모리사용시발생할수있는최대지연시간을제한할수있다. 본제안기법을이용하여사용자는낸드플래시메모리상에서 I/O 수행시가장큰오버헤드를갖는정체시간을제한할수있으며, 이에따라작업완료시간을예측해야하는실시간시스템에적용가능하다. 또한기존매핑기법과비교하여더좋은성
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 465 능을보인다. 본논문의구성은다음과같다. 2장에서는본논문과연관된기존기법에대해설명한다. 3장에서는 KAST 의전체구조를보인다. 4장에서실험결과를통해본제안기법과기존기법과의비교를수행한다. 마지막으로 5장에서결론을맺는다. 2. 관련연구 현재까지로그버퍼기반 FTL에대한많은연구가진행되었다. 로그버퍼기반 FTL은로그블록연관성에따라 BAST(Block Associative Sector Translation), FAST(Fully Associative Sector Translation), SAST(Set Associative Sector Translation) 로구분할수있다 ( 그림 1). 로그블록연관성이란하나의로그블록이얼마나많은데이터블록과연관되어있는가를나타낸다. BAST 기법에서는로그블록이하나의데이터블록과연관될수있다. FAST 기법에서로그블록은모든데이터블록의갱신된데이터를저장할수있다. 즉, 1개의로그블록이모든데이터블록과연관될수있다. SAST에서는데이터블록그룹과로그블록그룹간연관관계를갖게된다. 위에서언급한세가지기법은캐시메모리에서사용하는직접연관된 (direct-mapped) 캐시, 완전연관된 (fully-associative) 캐시그리고세트연관된 (set-associative) 캐시기법과유사하게동작한다. 그림 1에서 BAST, FAST, SAST 기법의동작을보인다. 그림 1(a) 에서전체플래시메모리영역은 6개의데이터블록 (B0~B5) 과 4개의로그블록 (L0~L3) 으로구성되며각블록은 4개의페이지로구성되어있다. 데이터블록에서데이터갱신이발생하면데이터블록에기록된이전페이지를무효화한후로그블록에기록한다. 논리로그블록번호 (LLBN: Logical Log Block Number) L0, L1, L2, L3로지정된각로그블록은논리블록번호 (LBN: Logical Block Number) B0, B1, B4, B5로지정된데이터블록의데이터갱신을담당한다. 논리페이지번호 (LPN: Logical Page Number) p16으로지정된데이터는데이터블록 B4에포함되기때문에로그블록 L0과 B4는연관관계를갖게된다. 이후 B2 또는 B3에포함된데이터의갱신이발생하면로그블록중하나를선택하고이와연관된데이터블록과병합연산을수행한후새로운로그블록을할당한다. 병합연산은완전병합 (full merge), 부분병합 (partial merge) 그리고스위치병합 (switch merge) 3 가지로구분된다 [4]. 부분병합및스위치병합은갱신된데이터가로그블록의첫번째오프셋부터순차적으로기록되어야가능한연산이다. 그림 1 로그버퍼기반 FTL 기법 BAST 기법에서는임의접근갱신데이터가많이발생한다면로그블록의병합연산을자주수행해야하며이에따라전체적인성능저하가발생한다. BAST 기법에서발생가능한이러한문제점을블록쓰레싱 (block thrashing) 이라한다. 그림 1(a) 는 p0, p4, p8, p12, p16, p20, p1, p5 의순서대로데이터갱신이발생했을때의블록들의상태를보여주고있다. p16부터갱신요청발생시매번로그블록을병합한후새로운로그블록에갱신데이터를기록해야한다. 또한, 로그블록에는유효한페이지 1개만존재한상태로병합연산을수행해야하며나머지 3개의페이지는낭비된다. 따라서 BAST 기법에서로그블록의사용률 (utilization) 이매우낮아짐을알수있다. 위에서언급한 BAST 기법의문제점을해결하기위해 FAST 기법이제안되었다. FAST 기법에서는 1개의로그블록에어떠한데이터블록의데이터도기록가능하며, 이에따라 BAST 기법에비해블록병합의수가감소하게된다 ( 그림 1(b)). 갱신된페이지는데이터블록번호와는관계없이갱신요청이발생된순서대로로그블록에기록된다. 따라서 FAST 기법을사용하면블록쓰레싱문제를예방할수있다. FAST 기법에서는 p0, p4, p8, p12, p16, p20, p1, p5 의순서대로데이터갱신이발생하여도 BAST와는달리로그블록의병합을수행하지않아도된다. 또한 FAST 기법에서는순차적인데이터갱신을위해 1개의 SLB(Sequential Log Block) 를사용한다. SLB는첫번째페이지에오프셋 0 을갖는데이터부터순차적으로기록된로그블록이다. 따라서오직하나의데이터블록과연관되며, 따라서부
466 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) 분병합및스위치병합만을수행하게된다. RLB(Random Log Block) 은 SLB와는달리임의의순서대로기 록된로그블록을말한다. 하지만 FAST 기법에서는로그블록이높은연관성 (associativity) 을가질수있다는문제점이있다. 만약 로그블록 L0를병합해야하는경우자신과연관된모 든데이터블록 (B0, B1, B2, B3) 과병합해야한다. 따라 서 16번의페이지복사연산을수행해야한다 (16 페이지 = 4개블록 * 4개페이지 ). 결국 FAST는병합연산수 행시높은병합연산비용을발생시킬수있는문제가 있다. 표 1에서본논문에서사용하는변수들을보인다. 표 1 논문에서사용하는변수 순번 변수 설명 1 L 로그블록 2 A(L) 해당로그블록과연관된데이터블록 3 k(l) 로그블록이가진연관성 4 N 로그블록내페이지개수 5 C copy 페이지복사연산값 6 C erase 블록삭제연산값 표 1의변수에따라로그블록 L의병합연산비용은 다음과같다 [6]: C merge = N k(l) C copy + (k(l) + 1) C erase k(l) 의최대값은블록내페이지개수가되며따라서 가장큰병합연산비용은 N 2 C copy +(N +1) C erase 가 된다. MLC(Multi-Level Cell) 낸드플래시메모리의 경우블록당페이지개수는 128개이며페이지읽기, 쓰 기및블록삭제비용은각각 50µs, 650µs 그리고 2ms 가소요된다. 따라서병합연산의최대값은약 6초가소요되는반면, 최소값은스위치병합연산비용인약 2ms가된다. 따라서병합연산비용의최대값은최소값에비해약 3,000배가된다. 결국 BAST 기법은블록쓰레싱으로인해성능이저하되며 FAST 기법은로그블록의연관성에따라최대, 최소병합연산비용의차이가매우커질수있다. 따라서두기법모두실시간시스템에는적합하지않다. 본논문에서제안하는 K-연관성매핑을이용한 FTL은 FAST와유사하게동작하지만사용자가결정한 K에따라최대병합시간을제어할수있는특징이있다. SAST[8] 기법에서는 1개의로그블록그룹이 K개의데이터블록으로구성된 1개의데이터블록그룹과연관된다. 그림 1(c) 에서 2:3으로구성된 SAST 매핑기법을보인다. SAST는기존의 BAST와 FAST 기법을절충한매핑기법이지만블록쓰레싱과높은블록연관성문제모두완전히해결하지못한다는단점이있다. 만약여러데이터블록그룹내데이터가번갈아가며갱신되는경우로그블록쓰레싱문제가발생하게된다. 3. K-연관성매핑기법본장에서는본논문의제안기법인 KAST에대해설명한다. 3.1 K-연관성매핑기법흐름도 KAST 기법을설명하기위해그림 2에서 KAST 전체동작의흐름도 (flow chart) 를보인다. 그림 2 KAST 흐름도 (flow chart)
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 467 KAST에서페이지 p의기록요청이발생하면이전에연관된로그블록이존재하는지확인하고 1, 존재한다면해당로그블록이 RLB 또는 SLB인지확인한다 2. 만약 RLB라면첫번째빈페이지에 p를기록하고, SLB라면 p기록으로인해순차성을유지할수있는지확인한다 3. 순차성을유지할수있다면 SLB의첫번째빈페이지에 p를기록하고순차성을유지할수없다면세부알고리즘에따라다른동작을수행한다 4. 만약이전에연관된로그블록이존재하지않는다면우선스위치병합가능한로그블록이있는지확인하고 5, 존재한다면스위치병합후새로운로그블록에 p 를기록한다. 스위치병합이불가능하면연관성을증가시키는데이터기록을시도한다 6. 만약연관성을증가시키는데이터기록을할수없다면희생로그블록을선택하여병합연산후새로운로그블록에 p를기록한다. KAST 세부동작은 3.2~3.3절에서설명한다. 3.2 K-연관성매핑기법전체구조 KAST 기법은크게 3가지기능을갖는다. 로그블록의연관성을최소화하기위해다른 LBN을갖는페이지를여러로그블록에분산시켜기록한다. 각로그블록을최대 K개의데이터블록들과연관되도록한다. 따라서 k(l) K를보장하며 K를제한함에따라병합연산에소요되는최대시간을제어할수있다. FAST에서는 SLB를 1개만사용하지만 KAST에서는 SLB를 2개이상사용할수있다. 또한순차적인데이터의갱신요청이발생하지않게되면 SLB를 RLB 로전환하여사용할수있다. SAST가데이터블록그룹내블록개수를 K보다작게유지하여로그블록의연관성을유지하는반면에 KAST는데이터블록과로그블록을그룹으로구성하지않는다. 앞에서언급한것처럼데이터블록과로그블록을그룹으로구성하면블록쓰레싱문제가발생할수있다. KAST는각로그블록의최대연관성을 K로제한한다. 또한최소한의 k(l) 을유지하기위해다른 LBN을갖는데이터를동일한로그블록에최대한기록하지않도록한다. 그림 3에서 FAST, SAST, KAST 의로그블록기록을비교한다. p1, p5, p9, p13, p17, p21, p2, p6 의순서대로페이지기록요청이발생한경우 FAST는첫번째로그블록부터순서대로데이터를기록하며, SAST는해당데이터블록그룹과연관된로그블록그룹에순서대로데이터를기록한다. 하지만 KAST는갱신요청데이터를각로그블록에분산시켜기록한다. 먼저 p1, p5, p9, p13를각각다른로그블록에기록한다. 데이터기록후 L0~L3은연관성 1을갖게된다. 이후 p17과 p21 그림 3 FTL 매핑기법에따른데이터기록비교을각각 L0과 L1에기록하고이에따라 L0, L1의연관성은 1에서 2로증가한다. 마지막으로연관성을증가시키지않기위해해당데이터가포함된데이터블록과이미연관된로그블록이있는지확인한다. 이에따라 p2과 p6를 L0과 L1에기록하며, 따라서 L0, L1의연관성은 2로유지된다. 그림 3에서보이는것처럼 KAST는가능하다면 k(l) 을증가시키지않은기록을우선적으로수행한다. KAST 는페이지기록요청이왔을때빈로그블록이없는상태그리고요청된 LBN에연관된로그블록이없는경우에만로그블록의연관성을증가시키며페이지를기록한다. KAST에서 SLB는순차적인데이터를기록하는로그블록으로연관성 1을갖는다. 처음기록요청이발생하여새로운로그블록을할당할때 SLB인지 RLB인지결정하게된다. 그림 4에서 KAST에서사용하는로그블록의상태전이도 (state transition diagram) 를보인다. 그림 4 KAST 로그블록상태전이도
468 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) F는빈로그블록 (Free log block), S는순차로그 블록 (SLB: Sequential Log Block) 그리고 R i 는연관성 i를갖는랜덤로그블록 (RLB: Random Log Block) 이 다. 처음모든로그블록은데이터가기록되어있지않 은빈블록상태를갖는다 (F 상태 ). 빈블록은 SLB(S 상태 ) 또는 RLB(R i) 로전이가능하다. 만약 R i 상태를 갖는 RLB에 d(p) A(L) (d(p) 는페이지 p가속하는 LBN을의미한다 ) 인데이터를기록한다면로그블록 L 은현재상태 R i 를유지할수있다. 또한 SLB의순차 성을무시하지않고데이터를기록한다면 SLB는 S 상 태를유지할수있다. 하지만 d(p) A(L) 인페이지를 RLB L에기록한다면 R i 는 R i+1 로전이된다. 이후 R i+1 인 L은자신이가지고있는페이지의무효화를통해 R i 로전이될수도있다. SLB는해당블록내빈페이지 의개수에따라 R 1 또는 R 2 상태로전이가능하다. 이후 SLB는부분병합 (partial merge) 및스위치병합 (switch merge) 을, RLB는완전병합 (full merge) 을수 행하여 F 상태가된다. 완전병합시 R i 상태를갖는 RLB의병합연산비용은 N i C copy +(i +1) C erase 가 된다. 3.3 로그버퍼데이터기록 본절에서는 KAST 기법의세부동작을설명한다. KAST에서페이지 p를로그블록에기록하는과정은 d(p) A(L) 인 RLB L이존재하는경우와그렇지않 은경우로구분된다. 표 2에서 p 기록과정을설명하기 위한 6가지임계값을보인다. 표 2 KAST에서사용하는 6가지임계값 임계값 설명 K 로그블록이가질수있는최대연관성 θ FP1 SLB의 RLB(R 1) 변환기준치 ( 빈페이지개수 ) θ FP2 SLB의 RLB(R 2) 변환기준치 ( 빈페이지개수 ) θ FP3 SLB의부분병합기준치 ( 빈페이지개수 ) θ gap SLB 유지기준치 ( 오프셋간격 ) θ SLB 할당가능한최대 SLB 개수 3.3.1 d(p) A(L) 인로그블록 L이존재하는경우 d(p) A(L) 인로그블록 L이존재존재한다면 k(l) 의증가없이 L 에 p 를기록가능하다. 이때 p 의오프셋 이 0 이라면새로운로그블록의첫번째페이지에 p 를 기록하여 SLB 로할당할수있다. 만약 p 의오프셋이 0 이면서 d(p) A(L) 인 RLB L 이존재하는경우 2 가지 동작중한가지를선택할수있다 ( 그림 5). 첫번째방법은 p 를 RLB L 에기록하는것이며 ( 그림 5(b)), 두번째방법은새로운로그블록의첫번째페 이지에기록하여 SLB 로할당하는것이다. 이때 p' L 이면서 d(p') = d(p) 에해당하는 p' 가존재하는경우 갱신요청이발생할때까지아무런동작도수행하지않 거나 ( 그림 5(c)) 이전에기록되어있는 L 에서 SLB 로 p' 복사후무효화할수있다 ( 그림 5(d)). 이후 SLB 의 순차성을유지하기위해중간에위치한페이지를데이 터블록 d(p) 에서 SLB 로복사하여채운다. SLB S 가있고 d(p) A(S) 인경우, p 를 S 에기록 해야하는데만약 p 의기록으로인해 S 의순차성을유 지못하게되는경우에는아래와같이크게 2 가지동작 을수행한다 ( 그림 6). 먼저 p 의오프셋이 S 의첫번째빈페이지의오프셋 보다작은경우 (offset p offset S) p 는 S 에이미기록되 어있는데이터를갱신하게되며, 이때 S 의빈페이지 수 (FP SLB) 를확인한다 ( 그림 6(a)). 만약 θ FP1 보다 FP SLB 가크다면 (θ FP1 < FP SLB), S 에 p 를기록한후 S 를 R 1 상태를갖는 RLB 로변환한다 ( 그림 6(b)). 그렇지않다면 (θ FP1 FP SLB), S 를부분병합한후새로운로그블록 을할당하여첫번째오프셋에 p 를기록한다 ( 그림 6(c)). 페이지 p 의기록이 S 에이미기록된데이터의갱신이 아니라면 (offset p > offset S) p 의오프셋 (offset p) 과 S 의 첫번째빈페이지의오프셋 (offset s) 간격의크기 (offset gap = offset p - offset s), 그리고 FP SLB 에따라다음 3 가지 중한가지동작을선택한다 ( 그림 6(d)). 만약 θ gap 보다 offset gap 이작거나같다면 (θ gap offset gap) 두오프셋 그림 5 연관성증가시키지않는페이지기록
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 469 그림 6 SLB 의순차성을무시하는페이지기록 사이에위치한페이지를데이터블록에서 S로복사한후 p를기록하여 S의현재상태를유지한다 ( 그림 6(e)). θ gap 보다 offset gap 이크다면 (θ gap < offset gap) FP SLB 를확인한다. 이때 θ FP1 보다 FP SLB 가크다면, (θ FP1 < FP SLB) S 에 p를기록한후 S를 R 1 상태를갖는 RLB로변환하고 ( 그림 6(f)) 그렇지않다면 (θ FP1 FP SLB) S에 p를기록하면서 S를부분병합한다 ( 그림 6(g)). 앞에서언급한것처럼 SLB에빈페이지가많은경우에는 SLB를 R 1 상태를갖는 RLB로변환하게되는데이것은해당 SLB에앞으로순차적인페이지기록요청이작은확률로발생할것이라판단하기때문이다. 또한 SLB에빈페이지가많을경우에 SLB를부분병합하는것보다는 RLB로변환하여빈공간을최대한활용하는것이더효율적이기때문이다. 3.3.2 d(p) A(L) 인 L이존재하지않는경우 d(p) A(L) 에해당하는로그블록이존재하지않는경우로그블록의연관성을증가시키는페이지기록을수행해야한다. 먼저스위치병합이가능한 SLB가존재하는지확인한다. 만약존재한다면해당 SLB와연관된데이터블록을삭제한후 SLB를데이터블록으로교체한다 ( 스위치병합 ). 스위치병합은복사연산이필요없기때문에다른로그블록에페이지를기록하여연관성을증가시키는것보다효율적이다. 만약스위치병합가능한 SLB가존재하지않으면로그블록중연관성증가가능한 RLB L을선택한다. 이때연관성이최소인 RLB L을선택하게되며만약최소연관성이동일한 L이 2개이상이라면빈페이지가많은 L을선택한다. 만약빈페이지개수도같다면 LRU인 L을선택한다. 이에따라로그블록들의연관성및빈페이지개수를균형있게유지하게된다. 이후 RLB L의 k(l) 이 K보다작을때까지 k(l) 을증가시키며 L에페이지를기록할수있다. 위의과정을수행하는동안 d(p) A(S) 인 SLB L 이존재하더라도빈페이지가많거나오랜시간동안페이지기록이없었다면 L의순차성을무시하는페이지기록을수행할수있다. 이때 θ FP2 보다큰수의빈페이지를갖는 SLB L이존재하는지확인하고존재한다면 L에 p를기록한다. 이후 SLB L은 R 2 상태를갖는 RLB로변환된다. 현재할당된로그블록들중빈페이지가없거나 K보다연관성이작은로그블록이존재하지않는다면어떠한로그블록에도데이터를기록할수없다. 이때기존에할당된로그블록중하나를선택한후병합하여새로운로그블록을생성해야한다. 병합대상로그블록을선택하는과정은다음과같다. 첫번째로부분병합가능한 SLB를선택한다. 만약 θ FP3 보다작은수의빈페이지를갖는 SLB L이있다면부분병합의대상이되고그렇지않다면현재상태를유지한다. SLB를부분병합하지않을경우에 S 상태를유지하여다음번기록요청이발생한경우사용한다. 두번째로병합연산비용과빈페이지의개수가최소인 RLB를병합대상으로선정하는데, 병합연산의비용의크기는로그블록의연관성에따라달라진다. 병합대상로그블록이선택되면로그블록을병합하여빈로그블록 1개를생성한다. 병합을통해확보한새로운로그블록을사용할때, 만약현재기록요청이발생한페이지의오프셋이 0이라면새로운로그블록의첫번째오프셋에기록하여 SLB로사용한다. KAST에서 SLB의개수는 FAST와는달리 0개부터최대로그블록의개수만큼할당가능하며, SLB의최대할당가능개수는사용자가설정한 θ SLB가된다. 4. 성능평가본논문의제안기법인 KAST의성능평가및검증을위해트레이스 (trace) 기반의실험을수행하였다. 실험을위해 FTL 시뮬레이션을위한프로그램을작성하
470 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) 표 3 실험에사용한낸드플래시모델사양항목세부사항낸드플래시모델 SLC(Single Level Cell) 페이지크기 2KB 블록내페이지개수 64 페이지읽기속도 25 us 페이지기록속도 200 us 블록삭제속도 2 ms 였으며이를통해 KAST를 BAST, FAST 및 SAST 기법과비교하였다. 시뮬레이션에적용한낸드플래시모델의사양은표 3과같다. 4.1 로그블록개수변화에따른성능변화비교본실험에서는로그블록개수변화에따른로그블록의사용률 (utilization) 과 I/O 수행시간을비교하였다. 로그블록의사용률은로그블록병합시로그블록에기록되어있었던페이지의비율을말한다. 실험에사용한트레이스는총 4가지로이중 2가지는실제 PC 상에서응용프로그램을동작하여추출한것이며나머지 2 가지는 bonnie[9], postmark[10] 벤치마크프로그램을이용하여추출하였다 ( 표 4). 그림 7에서각 FTL 매핑기법의로그블록사용률을보인다. 실험을위해로그블록의개수는 1개부터 32개까지 2배씩증가시켰으며 SAST, KAST에서 K는모두 64로설정하였다. 그림 7을통해 KAST의로그블록활용률이가장높은것을알수있다. BAST와 SAST에서는로그블록쓰레싱문제가발생하며 FAST에서는 SLB의블록쓰레싱문제가발생한다. 따라서로그블록의사용률이낮아지게된다. KAST에서는순차접근데이터의기록요청이발생하면최대 SLB 개수범위내에서 SLB를할당하고이후해당데이터의패턴이임의접근으로변경되면 SLB를 RLB로변경하여로그블록에데이터를기록한다. RLB로변경된로그블록은연관성이 K보다작을때까지페이지기록을수행할수있다. 따라서로그블록의활용률이다른기법에비해높다. 그림 8에서로그블록개수변경에따른각 FTL 매 표 4 실험에사용한트레이스 트레이스 트레이스설명 쓰기발생횟수 인터넷탐색기 인터넷탐색기사용시발생한디스크 I/O 추출 168,340 테스크톱 PC 윈도우 XP 기반 PC 사용시발생한디스크 I/O 추출 1,614,175 bonnie 벤치마크 bonnie 벤치마크프로그램을이용한디스크 I/O 추출 480,189 postmark 벤치마크 Postmark 벤치마크프로그램을이용한디스크 I/O 추출 2,514,990 (a) 인터넷탐색기 (b) 데스크톱 PC (c) bonnie 벤치마크 그림 7 로그블록사용률 (d) postmark 벤치마크
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 471 (a) 인터넷탐색기 (b) 데스크톱 PC (c) bonnie 벤치마크 그림 8 전체실행시간 (d) postmark 벤치마크 핑기법의 I/O 수행시간을보인다. 이결과를통해로그블록의활용률에비례하여 I/O 수행성능이좋아지는것을알수있다. 로그블록의활용률이높을수록더많은데이터를로그블록에기록할수있으며이에따라로그블록쓰레싱문제가해결된다. 또한병합되기전로그블록에더많은데이터를기록함으로써로그블록의병합연산의수행을지연시킬수있다. 로그블록의병합연산을지연시킴으로써동일한 LSN을갖는데이터가중복기록될확률이높아진다. 이에따라이전에로그블록에기록된동일한페이지를무효화하게되며결국병합연산의비용을절감할수있다. 4.2 K 변화에따른성능변화비교본실험에서는 K의증가에따른로그블록병합횟수, 로그블록연관성크기, 로그블록병합연산비용및 I/O 수행시간을비교하였다. 실험에사용한트레이스는인터넷탐색기와데스크톱 PC 사용시추출한것이며, 로그블록의개수를 32개로설정하여실험하였다. 또한 K는 1부터 64까지증가시켰다. 우선, 2가지트레이스의패턴이 SLB 활용에얼마나적합한지를비교하기위해오프셋 0을갖는페이지기록요청이후에입력된순차적인페이지의개수를측정하였다 ( 그림 9). 인터넷탐색기의트레이스에서는오프셋 0을갖는페이지이후순차적인기록요청발생횟수가대부분작 (a) 인터넷탐색기 그림 9 순차페이지발생횟수 (b) 데스크톱 PC
472 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) (a) 인터넷탐색기 그림 10 로그블록병합횟수 (b) 데스크톱 PC 으며최대연속페이지개수는 32개이다. 하지만데스크톱 PC 트레이스에서는스위치병합가능한연속페이지기록요청이 (64개의순차페이지요청 ) 약 3,000 회발생한다. 이에따라데스크톱 PC 트레이스가인터넷탐색기트레이스에비해순차적인데이터패턴이많다는것을알수있다. 그림 10에서 4가지 FTL 기법상에서얼마나많은수의병합연산이발생하는지를보인다. SAST와 KAST의경우로그블록의연관성인 K를변경하여실험하였으며 SAST에서는데이터블록그룹과로그블록그룹내블록의개수를동일하게설정하였다. 실험결과를통해 FAST에서는로그블록병합횟수가작은반면 BAST에서는블록쓰레싱으로인해로그블록병합횟수가크다는것을알수있다. SAST 와 KAST에서 K를 1로설정하였을경우 BAST와유사한횟수의로그블록병합횟수가발생하였다. 하지만 K를크게설정하면서병합연산의횟수가감소하는것을알수있다. KAST는 K가 8 이상이되면서 FAST 보다적은수의병합을수행하지만 SAST는대부분의경우 FAST보다더많은수의병합연산을수행하였다. 이는 SAST가블록쓰레싱문제를해결하지못하기때 문이다. 그림 11에서로그블록병합시측정한로그블록의연관성의크기를보인다. 로그블록의최대병합비용은최대연관성에따라결정된다. 실험결과에따라 SAST와 KAST의로그블록연관성의최대값이 K보다작게유지되는것을알수있다. FAST의최대로그블록연관성이가장크며이에따라 FAST의최대정체시간이길어질수있다. SAST와 KAST는 K를변경함에따라최대정체시간을제어할수있다. KAST는 BAST와 SAST에비해적은수의블록병합을수행하였으며또한병합연산에따른비용역시 FAST보다작다. 그림 12에서단일로그블록병합에따른정체시간분포를, 그림 13에서로그블록연관성분포를보인다. 실험결과는인터넷탐색기작업부하를이용하여측정하였으며 KAST와 SAST의경우 K를 16으로설정하였다. 그림 12에서 FAST에서 1회병합비용의최대값은 548ms가소요되었지만 KAST에서는 232ms가소요되는것을알수있다. SAST는병합하기전로그블록에적은수의데이터가남아있기때문에대부분의경우병합비용이 KAST보다작게발생하였다. 하지만 SAST는 (a) 인터넷탐색기 그림 11 로그블록연관성크기 (b) 데스크톱 PC
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 473 그림 12 로그블록병합연산비용분포 그림 13 로그블록연관성분포 가장많은수의병합연산을수행하였다 ( 그림 12). 그림 13에서 KAST와 SAST의경우로그블록연관성은최대값인 16으로제한되는것을알수있다. SAST 의경우가장낮은로그블록연관성을갖지만블록쓰레싱으로인해가장많은병합연산을수행해야한다. FAST의경우 KAST와비슷한수의병합연산을수행하지만로그블록연관성의제한이없기때문에 KAST 보다더높은연관성을갖는다. 그림 14에서각 FTL의전체 I/O 수행시간을보인다. SAST와 KAST는로그블록병합수의감소로인해 K가커질수록전체성능이향상된다. 하지만 SAST는인터넷탐색기트레이스의임의접근데이터로인해블록쓰레싱문제가발생하며이에따라 KAST보다성능이좋지않았다. KAST는 K가 8일때부터 SAST, FAST 두기법보다높은성능을보였다. 4.3. θ FP1 의변화에따른성능변화비교본실험에서는데스크톱 PC 트레이스를사용하여 θ FP1 의변화에따른성능을측정하였다 ( 그림 15). KAST에서는 SLB의순차성을무시하는데이터기록요청시해당 SLB의빈페이지가 θ FP1 보다작으면부분병합후새로운로그블록을할당하고그렇지않은경우 R 1 상태를갖는 RLB로변환한후다음기록요청을수행 한다. 따라서 θ FP1 을작게설정할수록 RLB로의변환이많아지고크게설정할수록부분병합을많이수행한다. 실험결과에따라 K가 1일때는 θ FP1 를크게설정할수록 I/O 수행성능이조금좋아지는반면, K가 2이상이되면 I/O 수행성능이 θ FP1 이커질수록저하되는것을알수있다 ( 그림 15(a)). 실험결과를설명하기위해 K가 1과 64인경우의부분병합과완전병합으로인한비용들을비교하였다. θ FP1 을크게하여부분병합횟수를증가시키면상대적으로완전병합의수가감소하여완전병합비용이감소하게된다. K가 1일때는블록쓰레싱으로인해 K가 64일때보다더많은수의완전병합을수행한다. 따라서완전병합비용은 K가 1일때 K가 64일때보다더큰폭으로감소하게된다 ( 그림 15(b)). 하지만 θ FP1 가커지면서부분병합의횟수가증가하기때문에부분병합에따른비용은증가하게된다. 따라서두연산비용의합을통해 K가 1일때 θ FP1 가커지면 I/O 수행성능이좋아지는반면 K가 64일때는 I/O 수행성능이저하된다. K와 θ FP1 의변경외 θ FP2, θ FP3, θ gap, θ SLB 의변경시전체성능에어떠한영향을주는지에대해실험하였다. 하지만해당변수의변화에따른전체성능의변화는 K 와 θ FP1 의변경에따른성능의변화만큼크지않았으며, (a) 인터넷탐색기 그림 14 전체 I/O 수행시간 (b) 데스크톱 PC
474 정보과학회논문지 : 시스템및이론제 36 권제 6 호 (2009.12) (a) I/O 수행시간 그림 15 θ FP1 의변화에따른성능변화 (b) 병합연산비용 이는로그블록에데이터기록시해당변수가적용되는부분이미비하기때문이다. 따라서실험시고정된값을적용하였으며, θ FP2 와 θ FP3 는 8로설정하였고 θ gap 과 θ SLB 의값은 4로설정하였다. 5. 결론본논문에서는실시간시스템을위한로그버퍼기반 FTL 매핑기법인 KAST를제안하였다. 로그버퍼를사용하는기존 FTL 매핑기법으로는 BAST, FAST, SAST가있다. 하지만 3가지기법모두단점을가지고있는데, BAST는블록쓰레싱으로인해로그블록의사용률이저하되며이에따라로그블록병합연산을가장많이수행한다. 따라서가장좋지않은성능을보인다. FAST는 BAST의블록쓰레싱문제를개선한기법이지만하나의로그블록이많은데이터블록과연관될수있는문제점이있다. 이에따라로그블록병합연산의최소값과최대값의차가 MLC 낸드플래시의경우최대 3,000배까지될수있다. SAST는 FAST의높은연관성문제를개선하고자하였으나블록쓰레싱문제를해결하지는못했다. 낸드플래시메모리를실시간시스템에적용할경우낸드플래시메모리의동작에따른성능상의변동을최소화해야하며병합연산의종료시간을예측할수있어야한다. 로그버퍼를사용하는 FTL의경우로그블록의병합연산이가장큰정체시간이되며, 또한로그블록병합연산비용은해당로그블록의연관성에따라달라진다. 본논문에서제안한 KAST에서는사용자가로그블록의연관성을 K로제한할수있으며이에따라병합연산은사용자가지정한 K에따른시간내에종료되는것을보장한다. 실험결과를통해 KAST는 K 변경에따른로그블록병합비용최대값을제한할수있으며이에따라로그블록병합종료시간을예측할수있음을알수있었다. 이에따라 KAST는정해진시간내작업을완료 해야하는실시간시스템에적합함을알수있다. 또한 다른기법에비해전체 I/O 수행성능역시뛰어남을알수있었다. KAST는전체 I/O 수행성능을향상시키기위해데이터기록시로그블록의연관성을최대한분산하여기록한다. 또한기록요청이순차적인성질에서랜덤한성질로바뀌면기존에사용하던로그블록의특성도함께변경하여로그블록의사용률을최대한높이게된다. 이에따라다른 FTL 매핑기법에비해효율적으로로그블록을사용할수있다. 참고문헌 [1] Y.-H. Bae. Design of a high performance flash memory-based solid state disk. Journal of Korean Institute of Information Scientists and Engineers, 25(6), 2007. [2] J.-U. Kang, J.-S. Kim, C. Park, H. Park, and J. Lee. A multichannel architecture for high-performance nand flash-based storage system. Journal of Systems Architecture, 53(9):644-658, 2007. [ 3 ] L.-P. Chang, T.-W. Kuo, and S.-W. Lo. Realtime garbage collection for flash-memory storage systems of real-time embedded systems. ACM Transactions on Embedded Computing Systems, 3(4):837-863, 2004. [4] J.-U. Kang, H. Jo, J.-S. Kim, and J. Lee. A superblock-based flash translation layer for nand flash memory. In Proc. of International Conference on Embedded Software (EMSOFT), pp.161-170, 2006. [5] J. Kim, J.-M. Kim, S.-H. Noh, S.-L. Min, and Y. Cho. A space-efficient flash translation layer for compact flash systems. IEEE Transactions on Consumer Electronics, 48(2):366-375, 2002. [6] S. Lee, D. Shin, Y. Kim, and J. Kim. Last: locality-aware sector translation for nand flash memory-based storage systems. In Proc. of IEEE International Workshop on Storage and I/O Virtualization, Performance, Energy, Evaluation and
실시간시스템용낸드플래시메모리를위한로그버퍼관리기법 475 Dependability (SPEED08), 2008. [7] S.-W. Lee, D.-J. Park, T.-S. Chung, D.-H. Lee, S. Park, and H.-J. Song. A log buffer-based flash translation layer using fully-associative sector translation. ACM Transactions on Embedded Computing Systems, 6(3), 2007. [8] S.-Y. Park, W. Cheon, Y. Lee, M.-S. Jung, W. Cho, and H. Yoon. A re-configurable ftl (flash translation layer) architecture for nand flash based applications. In Proc. of International Workshop on Rapid System Prototyping, pp.202-208, 2007. [ 9] Bonnie benchmark, http://www.textuality.com/bonnie/. [10] Postmark benchmark, J. Katcher. Postmark: A new file system benchmark, 1997. 조현진 2004 년배재대학교컴퓨터공학과 ( 학사 ) 2004 년 ~ 현재성균관대학교전자전기컴퓨터공학과석박사통합과정. 관심분야는운영체제, 낸드플래시메모리등 하병민 2009년성균관대학교전자전기컴퓨터공학과 ( 학사 ). 2009년~현재성균관대학교전자전기컴퓨터공학과 ( 석사과정 ) 관심분야는운영체제, 낸드플래시메모리등 신동군 1994년서울대학교계산통계학과 ( 학사 ) 2000년서울대학교전산과학과 ( 이학석사 ) 2004년서울대학교컴퓨터공학부 ( 공학박사 ). 2004년~2007년삼성전자소프트웨어책임연구원. 2007년~현재성균관대학교정보통신공학부조교수. 관심분야는임베디드시스템, 실시간시스템, 저전력시스템등 엄영익 1983년서울대학교계산통계학과 ( 학사 ) 1985년서울대학교전산과학과 ( 이학석사 ) 1991년서울대학교전산과학과 ( 이학박사 ) 1993년~현재성균관대학교정보통신공학부교수. 2007년~현재성균관대학교정보통신처처장. 관심분야는분산컴퓨팅, 시스템소프트웨어, 운영체제, 미들웨어, 시스템보안등