DBPIA-NURIMEDIA

Transcription

1 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 567 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 (New Flash Memory Management Method for Reliable Flash Storage Systems) 김한준 이상구 (Han-joon Kim) (Sang-goo Lee) 요약본논문은로그파일시스템의원리를바탕으로플래시메모리저장시스템에적합한플래시메모리공간관리방법을제안한다. 플래시메모리는비휘발성, 빠른입출력속도등의장점을지니고있지만, 제자리덮어쓰기 (in-place update) 가불가능하고메모리셀에대한쓰기 (write) 횟수가제한되는단점이있다. 이러한특성은플래시메모리를저장매체로사용할때기존의저장매체관리방법과는다른방법을요구하게된다. 본논문은자유공간유지를위해필요한클리닝메커니즘의연산비용을낮추면서동시에저장공간이전체적으로균등하게사용될수있도록하는사이클평준화기법을제안한다. 제안된방법은특히메모리활용도와로컬리티가높을때좋은성능을보인다. 클리닝메커니즘은자주접근되지않는 COLD 데이타를그렇지않은데이타와격리시킴으로써그효율이향상되었으며, 사이클평준화는사용횟수간의최대차이가하드웨어적인오차를벗어나지않는수준까지이루었다. 실험을통해제안된방법은비교기준으로삼은직관적방법 (greedy policy) 에비해사이클평준화가잘이루어진상태에서최대 35% 정도의클리닝비용절감효과를보였다. Abstract We propose a new way of managing flash memory space for flash memory-specific file system based on log-structured file system. Flash memory has attractive features such as non-volatility, and fast I/O speed, but it also suffers from inability to update in place and limited usage cycles. These drawbacks require many changes to conventional storage (file) management techniques. Our focus is on lowering cleaning cost and evenly utilizing flash memory cells while maintaining a balance between the two often-conflicting goals. The proposed cleaning method performs well especially when storage utilization and the degree of locality are high. The cleaning efficiency is enhanced by dynamically separating cold data and non-cold data. The second goal, cycle-leveling is achieved to the degree where the maximum difference between erase cycles is below the error range of the hardware. Simulation results show that the proposed method has significant benefit over naxve methods: maximum of 35% reduction in cleaning cost with even spreading writes across segments. 1. 서론플래시메모리는기존의기억장치인하드디스크를대체할것으로주목받고있는차세대기억장치로서집적회로로구성된비휘발성메모리이다. 최근플래시메모리 비회원 종신회원논문접수심사완료 : : : : 서울대학교컴퓨터공학부 hjkim@europa.snu.ac.kr 서울대학교컴퓨터공학부교수 sglee@mars.snu.ac.kr 1999년 3월 25일 2000년 4월 21일 의집적도와입출력성능이계속개선되고있어이동컴퓨터의보조기억장치로뿐만아니라일반컴퓨팅시스템의저장매체로까지사용할수있게되었다 [4,13]. 플래시메모리는전기적으로입출력을수행하기때문에읽기성능은 D램과거의같은수준이며쓰기속도도하드디스크에비해수백배이상빠르다 1) [14]. 그리고이저장매체는같은크기의 D램보다그크기가약 30% 1) 플래시메모리의읽기, 쓰기연산시간은각각바이트당약 ns, 4-10μs 가소요된다.

2 568 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) 작으면서도내충격성과고장률측면에서훨씬우수하기때문에대용량화가가능하다. 또한플래시메모리에존재하는데이타는주기억장치로로드될필요없이직접플래시메모리공간상에서입출력이가능하다. 이러한특성때문에플래시메모리가기존의디스크기반저장시스템의저장매체를대체하는경우에시스템의입출력성능을획기적으로향상시킬수있다. 그러나플래시메모리를저장시스템의매체로사용하기위해서극복해야할두가지단점이있다. 첫째, 플래시메모리는디스크매체와는달리저장공간상에존재하는데이타를수정할때본래주소에서바로덮어쓰는것 (in-place update) 이불가능하다. 이는플래시메모리가쓰기 ( 갱신 ) 연산을수행할때각비트 ( 또는바이트 ) 가한쪽방향으로만토글링 (toggling) 을허락하기때문이다. 그래서플래시메모리는메모리셀상에데이타가쓰여지기전에미리 0 또는 1 로초기화 (erase) 2) 하는연산이필요하다. 결국쓰기 ( 갱신 ) 연산을수행하기위해서는초기화된저장공간을미리확보하고있어야한다. 둘째, 플래시메모리는각메모리블록에대해수행되는초기화연산의횟수가제한되어있다 3). 허용되는초기화횟수를초과한플래시메모리블록에는쓰기오류 (write failure) 가발생한다. 그래서전체플래시메모리공간이균등하게활용되지못하는경우에는사용가능한저장공간이급격히줄어드는현상이발생하게된다. 결국이 초기화횟수제한 문제는플래시메모리가신뢰성있는저장시스템을위한저장매체로사용되는데큰장애요소가된다. 플래시메모리에기반한저장시스템 ( 이하플래시저장시스템 ) 을구축하기위해서는전술한두가지단점을해결할수있는메커니즘이필요하다. 첫번째단점 ( 제자리덮어쓰기의불가능 ) 을해결하기위해서는데이타갱신방법과자유공간유지방법이관건이된다. 데이타를갱신하기위해서는우선다른주소공간에새로운데이타를쓰게하고원래데이타는무효화 (invalidation) 시키는방법을생각할수있다. 그리고사용되는전체메모리크기는한정되어있기때문에지속적으로자유공간을확보하기위해서는무효화된데이타가있는블록들에대해 가베지컬렉션 (garbage collection) 또는 클리닝연산 (cleaning operation) 을수행해주어야한다. 이때이연산에소요되는비용을최소화하도록해야한 2) 초기화연산은일반적인읽기, 쓰기연산보다훨씬많은시간 ( 약 초 ) 이소요된다. 3) 초기화횟수는일반적으로 100,000 번정도로제한되어있다. 최근에 1,000,000 번의횟수를갖는제품도출시되고있다. 다. 그리고두번째단점 ( 초기화횟수제한 ) 은가능한한모든플래시메모리블록들을균등하게활용 ( 초기화 ) 하도록하는 사이클평준화 (cycle leveling) 작업을요구한다. 이는플래시저장시스템의수명 (lifetime) 또는신뢰도를결정짓는요소이며유지되는플래시메모리공간의크기가클수록사이클평준화의중요성은더욱커진다 [4]. 일반적으로사이클평준화를위해서는자주접근되는데이타를별로사용되지않은메모리블록에둔다. 그래서어떤메모리블록이지나치게활용되었다고판단이되면, 그곳에존재하는데이타들을덜초기화된영역으로이동시키는것이필요하다. 이때데이타가다른주소의블록으로복사되면서본래데이타가존재했던블록들은무효화될것이다. 결과적으로플래시저장시스템을구축하기위해기본이되는것은클리닝연산과사이클평준화와관련된이슈들을해결하는것이라고볼수있다. 그런데이두가지목적을동시에충족시키기는쉽지않다. 만약플래시메모리관리가클리닝연산의목적에만치중할경우에저장공간의쓰임새가한쪽으로치우치게될경향이있어시스템의신뢰도가떨어질수가있고, 반면사이클평준화에치중하는경우에는많은무효블록들을생성시키기때문에클리닝연산에소요되는비용을증가시키게된다. 본논문의목적은신뢰성있는플래시저장시스템의구축을위해서상충되는두가지목표를조화시킬수있는클리닝기법과사이클평준화기법을제시하는것이다. 이를위해본논문에서는플래시메모리공간관리의기본전략으로서로그구조파일시스템 (log-structured file system)[10] 에서제안된로깅방법을사용한다. 로깅에서는쓰기연산이 로그 (log) 라는자료구조상에서붙여쓰기 (append) 를통해실현된다. 그리고로그구조파일시스템의클리닝메커니즘을기반으로클리닝비용을줄이면서사이클평준화를하기위한메커니즘을제안한다. 여기에서클리닝메커니즘의성능은로그상에퍼져있는자주접근되지않는 COLD데이타를수집하는 컬렉션 (collection) 연산에의해개선되며, 사이클평준화기능은클리닝되는세그먼트를선택하기위해고안된 클리닝지표 를통해클리닝메커니즘에통합된다. 본논문의구성은다음과같다. 2장에서관련연구를기술하고, 3장에서는로깅방법에의해서자유메모리공간이관리되는방법과이와연관된본논문의구체적인목표를기술한다. 4장에서는제시된목표를달성하기위해컬렉션연산과사이클평준화를결합한여러가지플래시메모리관리방법을소개한다. 5장에서는제안된

3 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 569 장에서결론을맺는다. 2. 관련연구플래시저장시스템과관련된과거연구는대부분클리닝연산에소요되는비용을최소화하는데중점을두고있다 [4,5,7,13]. 클리닝메커니즘의성능을높이기위한한가지해결책은접근이별로없는 COLD데이타와그렇지않은 NON-COLD데이타를섞이지않도록하는것이다. 이를위해 [13] 은자주수정되는 HOT세그먼트의클리닝비용을줄이기위해로컬리티의정도에따라데이타를정렬하는로컬리티수집기법 (locality gathering) 을사용하였으며, [7] 은 COLD데이타가 NON-COLD데이타와섞이지않도록하기위해 COLD 세그먼트를클리닝하기위한별도의세그먼트를사용하였다. 그리고디스크기반의로그구조파일시스템은버퍼안에서갱신된유효페이지들을디스크에방출하기전에나이 (age) 순으로정렬하는나이정렬기법 (agesorting) 을제안하였다 [8,10]. 이런격리방법들은그특성상데이타입출력이발생할때마다 COLD데이타와 NON-COLD데이타를분리하는데항상신경을써야하는오버헤드를가지게된다. 본연구에서는이런오버헤드를줄이기위해 COLD데이타의분산된정도를측정하여필요하다고판단되는시점에만격리작업을수행하도록한다. 그리고사이클평준화를위해제안된기존의방법들은플립플롭 (flip-flop) 의성격을가지는간단한형태이다. 예를들어, 세그먼트의초기화횟수값들의최대차가주어진임계값을초과하였을때에최대초기화횟수를가지는블록들과최소초기화횟수를가지는블록들에존재하는데이타를서로교환하는방법 (A) [13] 이있다. 이와유사하게자유공간풀 (pool) 에서최대초기화횟수를갖는블록을할당받아이곳으로최소초기화횟수를가지는블록의데이타를이동시키는방법 (B) [4] 이있다. 이런방법들은사이클평준화동안에많은시스템자원을소모하게되어일반적인데이타입출력연산을크게방해할수있다. 즉, (A) 의경우에두메모리블록들간에데이타교환을위해서세번의데이타이동 ( 복사 ) 작업이이루어져야하며, 교환되는데이타크기만큼의시스템버퍼가필요하다. 더구나교환되는데이타가쓰여지기위해서미리상대메모리블록에대해초기화연산을수행하는데이초기화연산과데이타교환 ( 이동 ) 작업이병렬적으로수행될수가없다. 본연구에서는사이클평준화로인한성능저하를줄이기위해 효능을실험을통해입증한다. 마지막으로 6 클리닝작업을수행할때동시에사이클평준화를고려하게된다. 3. 플래시메모리관리서론에서언급한바와같이본연구에서는플래시메모리공간관리를위해로그구조파일시스템의로깅방법을채택하였다. 기존의여러연구에서도플래시메모리에특성에맞는저장시스템의구현을위해로깅방법이추천되어왔다 [4,7,12]. 플래시저장시스템이로깅기법을사용하는이유는로그구조파일시스템의경우와는다르다. 로그구조파일시스템에서의로깅은쓰기버퍼 (write buffer) 에누적된데이타를한꺼번에디스크로방출함으로써쓰기성능을높이는데기여하지만, 플래시저장시스템에서그런효과를기대하지는않는다. 플래시메모리저장시스템에서로깅기법을채택하는것은그것이플래시메모리의단점들을해결할수있는여러성질을가지고있기때문이다. 즉, 로깅에서는항상쓰기 ( 갱신 ) 연산이로그말단인새로운메모리공간에서발생하기때문에 제자리덮어쓰기불가능문제 가자연스럽게해결되고, 더불어다른초기화된유효메모리공간을연속적으로사용할수있어약간의사이클평준화효과를기대할수있다. 또한플래시저장시스템은그매체의하드웨어특성상초기화연산을통해서새로운저장공간을창출해야하기때문에로그파일시스템에서제안된클리닝메커니즘 ( 또는클리너 ) 의원리를응용할수있다. 플래시메모리관리자의주요모듈운영체제래시파일관리자할당자클리너저장플래시메모리관리자시스플래시메모리매체사이클평준자콜렉터템알고리즘의인터페이스플래시메모리 : 호출플그림 1 플래시저장시스템 본논문에서는로그구조를생성하기위해플래시메모리공간을 세그먼트 단위로구분한다. 각세그먼트는한번의초기화명령으로한꺼번에같이초기화되는 초기화블록 (erase block) 4) 들의집합체이다. 그리고각 4) 초기화블록은플래시메모리칩의구성에서한번에초기화할수있는메모리단위를말한다. 대개그크기가 4-64 킬로바이

4 570 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) 세그먼트는일정한수의페이지들로구성된다. 이때 페이지 라함은플래시메모리와주기억장치간의이동되는데이타의크기인입출력단위를말한다. 여기에서소개하는 세그먼트 는로그구조파일시스템에서클리닝연산의단위가되는세그먼트와유사하다. 그런데플래시메모리는초기화되는메모리블록의수에상관없이일정한시간이걸리기때문에세그먼트의크기는충분히큰것이좋다 5). 그래서플래시저장시스템에서사용되는세그먼트는로그구조파일시스템의세그먼트보다상대적으로매우크다 6). 본장에서는플래시저장시스템의프로토타입을제시하고이를바탕으로플래시메모리공간관리의구체적인목표를기술한다. 3.1 시스템구조본논문이가정하는플래시저장시스템은그림 1과같이파일관리자 (file manager), 플래시메모리관리자 (flash memory manager), 플래시매체인터페이스 (flash media interface) 로구성된다. 파일관리자 는논리적페이지들의집합으로파일을관리하는요소로서운영체제가요구하는일반적인파일서비스를제공한다. 그리고 플래시메모리관리자 는플래시메모리를물리적인수준에서관리하여논리적인페이지의물리적인위치를결정해서필요한플래시입출력연산을발생시킨다. 이는디스크기반저장시스템에서의디스크관리자 (disk manager) 에비유할수있다. 마지막으로 플래시매체인터페이스 는플래시메모리하드웨어를위한저수준연산들의집합으로구성된다. 이는초기화 (erasing), 프로그래밍 (programming), 에러추적 (error detecting) 연산등을포함한다. 본논문은플래시저장시스템의세가지요소중 플래시메모리관리자 와관련된내용을다루게된다. 제안되는플래시메모리관리자는클리너 (cleaner), 할당자 (allocator), 사이클평준자 (cycle-leveler), 컬렉터 (collector) 등네개의모듈로구성된다. 클리너 는새로운자유공간을창출하기위해로그공간에존재하는 트이며, 이는입출력단위의페이지와구별되는것이다. 5) 초기화단위의크기는클리닝비용을고려해서결정되어야한다. 그크기가너무크다면클리닝비용이커지며, 반대로너무작게되면잦은클리닝으로인해많은수의초기화연산이발생된다. 최적의세그먼트크기를결정하는문제는본연구의범위를벗어난다. 6) 디스크기반로그구조파일시스템인 Sprite-LFS[10] 에서는 512 킬로바이트, 플래시저장시스템 envy[13] 에서는 16 메가바이트를사용한다. 무효페이지들을초기화해서시스템에반환하는모듈이다. 할당자 는클리너가반환한자유세그먼트를로그에할당함으로써지속적으로로그공간을유지하게한다. 사이클평준자 는플래시세그먼트들이균등하게사이클횟수를가지도록한다. 그리고 컬렉터 는로그상에서 COLD데이타를 NON-COLD데이타로부터격리시키는모듈로서클리너의오버헤드를줄이는데기여한다. 컬렉터로그말단 append( 쓰기 )... 로그세그먼트 1 클리너 2 3 무효 (dead) 페이지 4 할당자유효 (live) 페이지... 초기화된 (fresh) 페이지자유세그먼트 그림 2 플래시메모리관리자그림 2는플래시메모리관리자가동작하는절차를보여준다. 어떤데이타가갱신 ( 쓰기 ) 되면이는로그말단에있는새로운페이지에쓰여진다. ( 이때그새로운페이지는 유효 (live) 로표시되고, 이전데이타의페이지는 무효 (dead) 로표시된다.) 이런로깅과정이반복될때많은무효페이지들이발생하게되어가용메모리공간의크기가점차적어진다. 클리너는남아있는가용공간의크기가임계점이하로떨어질때구동된다. 여기서클리닝연산은 유효데이타복사, 세그먼트초기화 의두단계를거친다. 유효데이타복사단계에서는클리너가로그상에존재하는세그먼트들중에서클리닝연산의대상 ( 이를 클리닝세그먼트 라고부르겠다 ) 을결정하고 ( 그림 2 1), 자유세그먼트들중에서필요한만큼의세그먼트를로그에할당한다 ( 그림 2 2). 이어서클리닝세그먼트로부터유효블록들을수집하여로그말단에이를복사한다 ( 그림 2 3). 지금까지의과정은로그구조파일시스템의클리닝연산과정과유사하다. 세그먼트초기화단계에서는선택된세그먼트의모든초기화블록에대해초기화연산이병렬적으로수행된다. 이렇게해서클리닝된세그먼트는자유세그먼트풀 (pool) 로반환된다 ( 그림 2 4). 세그먼트초기화단계는단지일정한비용을지불하는하드웨어적인초기화연산만으로구성되기때문에클리너의성능은주로유효데이타복사단계에서결정된다. 그리고유효데이타복사단계에서

5 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 571 할당자모듈이어떤자유세그먼트를로그에할당할지에따라클리너와사이클평준자의성능에영향을미칠수있다 (4.2.2절에서설명 ). 또한클리너는클리닝할때마다세그먼트들이골고루사용되고있는지를검사한다. 만약사이클의편중화가주어진기준보다심해질때클리너는사이클평준자를구동시킨다. 사이클평준자는최소사이클횟수를가지는세그먼트의데이타를로그말단으로이동 ( 복사 ) 시킨다. 이연산은이동되는데이타가원래있던페이지들은무효화시키기때문에관련세그먼트가클리닝될가능성을높이게된다. 위의과정에따라많은횟수의로깅과클리닝연산이진행되면로그공간에는자주접근되지않는 COLD데이타와그렇지않은데이타가섞이게되는데이는클리닝효율을떨어뜨리는주요원인이된다 (4.1절에서설명 ). 그래서클리너는 COLD데이타의분산을억제하기위해주기적으로컬렉터를호출하여적당한량의 COLD데이타를 NON-COLD데이타로부터분리시킨다. 3.2 문제정의및성능측정치소개본절에서는플래시메모리관리의정량적인분석을위해클리닝비용, 사이클평준화정도, 그리고시스템의수명과관련된척도를제안하고자한다. 그리고이를토대로본논문이제안하는플래시메모리관리의목표를기술한다. 본논문에서제안하는클리닝비용모델은플래시메모리기반의 envy시스템 [13] 에서정의된클리닝비용모델에기반을둔다. 여기에서 μ를세그먼트활용률 ( 전체공간에서유효데이타가차지하는비율 ) 이라고할때클리닝비용을 μ/(1-μ) 로정의한다. 즉, 클리닝비용은새롭게생성되는공간 (1-μ) 에대해서복사 ( 이동 ) 되어야하는유효데이타의양 (μ) 을의미한다. 비교해서디스크기반의 Sprite-LFS시스템 [10] 은클리닝비용을 2/(1-μ) 로정의한다. 이식에서분자 2는읽기비용 (1) 과쓰기비용 (1) 의합을나타내는데디스크를매체로하는시스템에서는클리닝을위해세그먼트전체에대하여읽기, 쓰기연산을수행함을반영한것이다. 이에반해서 envy의경우에는한세그먼트내에서유효페이지들만을복사하는비용만을고려하였다. 플래시메모리는디스크처럼탐색시간, 회전지연이없을뿐만아니라읽기속도가쓰기속도에비해매우빠르기때문에세그먼트를읽어오는비용은무시할수있는것이다. 그런데이러한클리닝비용모델은플래시메모리가시간과비용이많이소요되는초기화연산을가지고있음을전혀고려하지않은것이다. 초기화연산이클리닝 할때마다일정한비용을부담하지만클리닝연산이많이발생한다면전체적인비용이커질수밖에없다. 본논문에서는 envy[13] 에서제안된클리닝비용에클리닝회수정보를가미한 누적클리닝비용 을정의한다. 결국클리너는각클리닝연산의비용을최소화해야할뿐만아니라전체클리닝연산의횟수를줄일수있어야한다. f μ 정의 1. 누적클리닝비용은 i i 이다. 이때 f는 =1 1-μ i 시스템에주어진일정량의쓰기요청스트림 (write request stream) 에대해수행된클리닝연산의횟수를의미하고, μ i 는 i 번째클리닝을위해선택된세그먼트의활용률을의미한다. 그리고전체세그먼트들의사이클횟수가얼마나균등하게분포되었는지를측정하는척도로서다음과같은사이클평준화도 (cycle leveling degree) 를제안한다. 정의 2. 사이클평준화도 ( Δ ε ) 는최대초기화횟수 ( ε max ) 와최소초기화횟수 ( ε min ) 의차이다. 사이클평준화도의척도로서모든세그먼트들의초기화횟수값에대한분산값또는표준편차값등과같은통계량을사용하지않은것은시스템의수명이사이클을가장많이소비한세그먼트의수명에의해결정되기때문이다. 일반적으로사이클평준화는완벽하게 ( 사이클평준화도가 0에가깝도록 ) 수행될필요는없다. 이는초기화횟수제한이세그먼트마다약간의오차를가지고있으며 7) 또한과도한사이클평준화는클리너의성능을떨어뜨리기때문이다. 그래서사이클평준화의목표를사이클평준화도가초기화제한횟수의오차범위내에있는것으로삼는다. 마지막으로시스템의수명 (lifetime) 을측정하기위한척도를제안한다. 우선주어진플래시메모리공간에서허용가능한쓰기연산의최대량을플래시저장시스템이갖게되는쓰기용량 (write capacity) 으로정의한다. 이를 플래시용량 (flash capacity) 이라고명명한다. 이값은고장 (failure) 시점까지수행된세그먼트초기화연산의총횟수에비례할것이다. 이때고장시점은초기화횟수의한도를초과한메모리공간의비율이임계점을넘어섰을때를말한다. 따라서시스템고장때까지사용 7) 이오차는측정이어렵기때문에아직보고되지않고있다. 본논문에서는이오차범위가특정한값 e ( 예를들어 100) 를갖는다고가정한다.

6 572 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) 된플래시용량이시스템의수명을결정한다고볼수있다. 이를 사용플래시용량 으로정의한다. N seg 정의 3. 시점 t 에서사용플래시용량은 ε t (S i ) 이 다. 이때 N seg 은시스템내에서사용되는세그먼트의수이고, ε t (S i ) 은시점 t 에서세그먼트 S i 의초기화횟수이다. 정의 3의측면에서우리가목표로하는사이클평준화는고장시점 t f 에서모든세그먼트에대한 ε t f (S i ) 값들이초기화제한횟수의오차범위내에있게하는것이다. 이와관련하여플래시저장시스템의수명을연장시키는방법은사이클평준화를이루면서동시에클리닝횟수를줄이는것이다. 가령사이클평준화를수행하지않은경우에시스템이사이클용량을 a (segments erases) 만큼을소비하였을때고장이발생하고, 사이클평준화를수행한경우에는사이클용량을 b (segments erases) 만큼을소비하였을때고장이발생한다고가정하자. 그러면사이클평준화를하였을때사용플래시용량은 b/a 비율만큼증가한것이고그만큼수명이늘어난다고할수있다. 게다가클리닝횟수가 f 만큼의비율로감소하였다면시스템의수명은 b 의비율로증가하게 a (1-f) 될것이다. 4. 플래시메모리관리의최적화 4.1 그리디방법의한계클리닝연산을요구하는시스템의성능은대개그것의클리닝알고리즘에의해좌우된다. 그리고앞서소개된클리닝비용모델에따르면클리닝비용은클리닝세그먼트의활용률 ( μ) 에의해결정된다. 그래서어떤세그먼트를클리닝할것인지가클리닝알고리즘의가장중요한이슈가된다. 직관적으로생각할수있는것은클리닝세그먼트로서로그상에서가장작은활용률을가지는세그먼트를선택하는것이다. [10] 에서는이를그리디방법 (greedy policy) 이라고한다.( 여기서는 GreedyⅠ로명명한다 ) 그러나이그리디방법은로컬리티정도가높을때는그성능이좋지못하다 [7,9,10,13]. 특히세그먼트활용률이높을때는로컬리티가클리닝성능에더크게악영향을미친다. 이것은클리닝연산과정에서로그공간에분산된 COLD데이타가더이상무효화되지않으면서필요없이여러세그먼트로옮겨다니기때문인데로컬리티가클수록이러한성향이강 i=1 해진다. 뿐만아니라클리닝횟수도증가하게된다. 이는증가된 COLD데이타로인해활용률이커진세그먼트가쓰기 ( 갱신 ) 연산에의해보다빠른속도로가용공간이소모되어클리닝연산을많이발생시키기때문이다. 4.2 COLD 데이타의분리위와같은그리디방법의제약점을극복하기위해서본논문은 COLD데이타를 NON-COLD데이타로부터격리시키는컬렉션 (collection) 연산을제안한다. 실제적으로이는플래시메모리관리자의컬렉터로구현되며이는로그상에단편화된 COLD데이타를강제적으로수집해서한곳으로모으는작업을수행한다. 이렇게함으로써 COLD데이타가수집된세그먼트는 COLD데이타의특성으로인해다른세그먼트들에비해서무효화가더디게진행될것이며, 상대적으로활용률이작아진다른세그먼트들을클리닝시키는효과를가지게된다. A 3 B 7 파일테이블 C 3 무효페이지 D E F... (a) 단계 I... (b) 단계 II 화일 ID 페이지수각페이지의포인터... c c a a a c b b b b b b c d e f 로그말단 세그먼트 1 세그먼트 2 세그먼트 3 세그먼트 N 콜렉션크기 c c c c d e f aaabbbbbbb 세그먼트 2 세그먼트 3 세그먼트 N 세그먼트 N+1 로그말단 그림 3 컬렉션연산절차 콜렉션크기의결정 수집되어야할파일인식 파일 A 와 B 의페이지들을수집, 복사 저장공간부족시클리너가구동 그림 3은컬렉션연산의두단계절차를보여준다. ( 여기서로그말단에기록되는페이지는영어대문자로표시된파일식별자의소문자로표시된다.) 우선단계 I 에서적당한시점에컬렉터가호출되어수집할 COLD 데이타의양을결정한후에 COLD데이타중에서단편화가많이진행된것을찾는다. 이때 COLD데이타로인식된파일들이단편화된정도가크지않다면컬렉션작업을수행할필요는없다. 그림 3의예에서는수집할 COLD데이타의양으로 10이주어졌으며많이단편화된 COLD데이타로파일 A, B가선택되었다. 단계 II에서는수집된 COLD데이타의페이지들이로그말단에연속적으로복사된다. 이때가용공간이충분하지못하다면클리너가구동되어새로운저장공간이생성되어야한다.

7 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 573 위컬렉션연산과정에서우리는다음세가지이슈에대하여합당한정책을가지고있어야한다. ( 컬렉터모듈은클리닝연산이 n번수행될때마다주기적으로한번씩호출되는데이때 n 값을 컬렉션주기 라부르고, 수집되는 COLD데이타를 컬렉션데이타, 수집되는 COLD데이타의양을 컬렉션크기 라고부르기로한다.) ㄱ. 어떤 COLD데이타를수집해야하는지? ( 컬렉션데이타의판정 ) ㄴ. 언제 COLD데이타를수집해야하는지? ( 컬렉션시점 ( 주기 ) 의결정 ) ㄷ. 얼마만큼의 COLD데이타를수집해야하는지? ( 컬렉션크기의결정 ) ㄱ과관련해서, 컬렉션데이타는 COLD데이타중에서로그공간전체에많이분산되어있는것들이어야한다. 이를위해 COLD데이타를판정하기위한기준과그것의단편화된정도를측정하는것이필요하다. ㄴ과ㄷ은컬렉터의성능을결정짓는요인이된다. 컬렉터가너무자주호출되거나또는지나치게많은수의페이지들을수집하는경우에는과다한페이지이동으로인해전체클리닝비용을오히려상승시킬수있다. FAW ( 파일접근창 ) A...B...B...A...B...B...C...C...C...A...C...B...B...D...D...E...F 파일접근의자취 그림 4 파일접근창 (File Access Window) COLD데이타의판정 COLD데이타를판정하기위해서컬렉터는파일이접근되는패턴을파악하는 파일접근윈도우 (File Access Window, 이하 FAW) 라는데이타구조를유지한다. 이는그림 4에서보는바와같이가장최근에접근된파일들의리스트를보관하는큐 (queue) 의형태를가진다. 이 FAW는가상메모리공간관리를위해제안된 working set[3] 과유사하다. Working set의원리에따르면로컬리티가존재할때 working set에해당하는윈도우크기만큼의프로세스시간동안같은페이지가반복적으로접근되는경향이있다. 이와유사하게최근에갱신되고단편화되는파일들은 FAW내에있다고가정하고 FAW내에포함되지않은 파일 들을 COLD로판정한다. 이때 FAW의크기는보다정확하게 COLD데이 타를가려낼수있도록잘조정해주어야한다. 여기서는최적의클리닝성능을가질때 FAW가 COLD데이타를가장잘가려낸것으로간주해서그때의값을 FAW의크기로정한다. 이렇게 FAW를통해얻은컬렉션데이타의후보중에서단편화가많이진행된것을컬렉션데이타로정하게된다. 여기서컬렉터는파일관리자 ( 그림 1 참조 ) 가유지하는파일테이블 8) ( 그림 3 참조 ) 을이용한다. 컬렉터가페이지수준이아닌파일수준에서 COLD데이타를판정하는이유는컬렉션데이타는많이단편화된 COLD데이타이어야하는데페이지수준에서단편화된정도를가리는것이불가능하기때문이다 COLD데이타의단편도측정위에서언급한바와같이컬렉션데이타를판정하기위해서최종적으로단편화된정도인단편도를측정해야하는데, 이는한파일이가지는페이지들이로그상에얼마나퍼져있는지를나타낸다. 그래서단편도 F는다음과같이정의하며결과적으로 0과 1사이의값을가진다. F = s ( 만약, p > L p seg 이면 p = L seg ) (1) 여기서 p는검사되는파일이점유하는페이지들의수이고, s는그파일이분포되어있는세그먼트들의개수를의미한다. L seg 는로그상에존재하는세그먼트들의개수이다. 여기에서 s는 L seg 보다클수없기때문에크기가큰파일은많이단편화되었다하더라도작은 F 값을가지게된다. 그래서파일의페이지수 p가 L seg 보다큰경우에는 p값을 L seg 로대체한다. 이렇게하면같은 s값에대해서크기가큰파일의단편도값이상대적으로크기가작은파일의단편도값보다작아지는것을방지할수있다 컬렉션시점과컬렉션크기의결정기본적으로컬렉션연산이수행되는최적의시점은 COLD데이타가여러세그먼트로쪼개져서클리닝비용을증가시키는원인으로작용하기시작하는시점이될것이다. 그리고알맞은컬렉션데이타의양은 COLD데이타중에서실제로크게단편화된데이타의총량일것으로예측한다. 그런데이컬렉션시점 ( 또는주기 ) 과컬렉션크기를정하는것은매우방대한탐색공간을가지는문제이다. 그래서본연구에서는컬렉션연산의구동시점과그것의작업량을세그먼트활용률과로컬리티에따라결정하는휴리스틱을사용한다. 즉, 식 (2), 8) 파일과관련된페이지정보를가지는테이블을말한다.

8 574 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) (3) 에서보는바와같이컬렉션크기 (ColSize) 는활용률과로컬리티에비례하게하고, 컬렉션주기 (ColPeriod) 는활용률과로컬리티에반비례하도록한다. 여기에서 ColSize의단위는페이지수, ColPeriod의단위는클리닝횟수이다. ColSize = k s μ avg locality f (2) ColPeriod = k p μ avg locality f (3) 여기서 μ avg 는모든세그먼트들에대한세그먼트활용률의평균값이며 locality f 는로컬리티정도를나타낸다. k s 와 k p 는비례상수로서최적의클리닝효율을가지도록실험적으로조정된값을취한다. 이와같이컬렉션크기와컬렉션주기를결정하기위해세그먼트활용률 ( μ avg ) 을고려한것은세그먼트활용률이높을수록더많은 COLD데이타를생성하기때문이며이런경향은로컬리티가높을수록더욱커지기때문이다 [13]. 또한 COLD데이타는로컬리티가높을수록필요없이다른세그먼트로이동하는경향이강해진다. 그래서세그먼트활용률이높을수록그리고로컬리티가높을수록보다자주, 보다많은양의 COLD데이타를수집할필요가있다. 이외에다른인자들을포함해서보다정밀한방법으로컬렉션주기와컬렉션크기를정할수도있을것이다. 식 (2), (3) 의계산을위해서로컬리티를정량화하는것이필요한데, 이를위해본논문에서는최근에입출력연산이집중된파일집합이얼마나큰지를측정한다. 그래서앞서소개된 FAW를이용하여로컬리티를 FAW 로계산할수있다. 여기에서 FAW 는파일접 FAW f 근윈도우의크기이며 FAW f 는 FAW내에존재하는최근에접근된각파일들의수를나타낸다. 이식이 0과 1 사이의값을갖도록다음과같이변형한다. locality f = FAW - FAW f FAW -1 만약 FAW 크기만큼의입출력연산이진행되는동안단하나의파일만이접근된다면 ( 즉, FAW f = 1 ) locality f 는최대값 1이된다. 본절에서설명한 COLD데이타의컬렉션기법과 GreedyⅠ과결합한것을 CICLⅠ 9) 로부르기로한다. (4) 클리닝비용의수정컬렉션연산도클리닝연산과마찬가지로유효블록을복사하는작업을수행하기때문에이것을정의 1(3.2 절참조 ) 의누적클리닝비용식에반영해주어야한다. μ 그래서한번의클리닝에해당하는비용식 ( 1-μ ) 을다음과같이수정한다. 클리닝비용 = 순수클리닝비용 + 컬렉션비용 = μ 1-μ + c 1-μ = μ+c 1-μ (5) ( c = Col Size Col Period 1 SegSize ) (6) 식 (5) 에서 μ는클리닝되는세그먼트의활용률을나타내며 c/(1-μ) 은컬렉션연산에소요된비용을나타낸다. 이컬렉션비용은한세그먼트에서 (1-μ) 비율만큼의자유공간을생성하기위해 c 비율만큼의유효블록이복사된것을나타낸다. 그래서수정된클리닝비용식은이컬렉션비용을정의 1의클리닝비용 ( 순수클리닝비용 ) 에더한것이된다. 컬렉션비용값은클리닝시마다컬렉션연산이수행된다고가정할때 ( 실제로는컬렉션주기만큼의클리닝연산이발생하고나서야한번의컬렉션연산이수행된다 ) 요구되는비용으로설명할수있다. 그래서 c 값은식 (6) 과같이계산된다. 여기서 SegSize는한세그먼트에포함된페이지들의수를의미한다. 예를들어, SegSize가 500페이지, 컬렉션주기가 100, 그리고한번의컬렉션을위해서 1,000페이지가 복사된다고할때 c 값은 1, =0.02가된다. 즉, 번의클리닝연산이발생하는동안에매번 0.02 만큼의컬렉션연산비용을추가적으로보태주게된다. 4.3 사이클평준화플래시저장시스템에서데이타접근이어떤유형으로발생하든지사이클사용이한쪽으로치우치게마련이다. 최악의경우에전혀접근되지않은데이타가장시간존재할때는극심한세그먼트편중화현상이발생한다. 본논문이플래시메모리관리를위해채택한로깅전략이잠재적으로사이클평준화효과를가진다할지라도신뢰성있는플래시저장시스템의구축을위해서는 2절에서기술한기존의사이클평준화기법보다안정적인방법이요구된다. 특히플래시메모리공간이크고쓰기연산이빈번한환경에서사이클평준화의중요성은더욱커진다. 9) CICL 은본연구의핵심부분인클리닝지표 (Cleaning Index) 와컬렉션연산 (CoLlection operation) 의약자이다. 클리닝지표에대한자세한설명은 절에있다.

9 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 클리닝지표 클리닝지표는클리닝세그먼트를선택하는기준값을 의미한다. 다시말해서클리닝세그먼트는가장적은클 리닝지표값 10) 을갖는세그먼트가된다. 본논문에서는 클리닝연산의비용절감과사이클평준화를동시에도모하기위해서식 (7) 과같은클리닝지표를정의한다. 클리닝지표 = (1-l) μ i +l ε i ε max +1 (7) 게하면될것이다. 예를들어, 그림 5에서 k ε 값을 10으로설정한경우에는사이클평준화도가작은값을가져도, 즉약간의사이클편중화가일어나도 l 값이급격히증가하게된다. 그리하여클리너는초기화횟수인자에큰비중을가지는클리닝지표값을가지게되면서사이클평준화작업을수행하게된다. 반대로 kε 값을 500으로설정하면사이클평준화도가 100이될때까지는 l 값이완만하게증가하기때문에사이클평준화작업이거의일어나지않을것이다. 여기에서 μ i 와 ε i 는세그먼트 i의활용률과초기화횟수를의미하며 ε max 는최대초기화횟수를나타낸다. 정의된클리닝지표는세그먼트의활용률관련인자 ( μ i ) ε 와초기화횟수관련인자 ( i ) 로구분될수있는 ε max +1 데, 이두개의인자는정규사이클평준화도 (normalized cycle leveling degree) l 에의해가중치가주어진다. 이 l 은 3.2절에서정의된사이클평준화도를 0과 1사이의범위로정규화시킨값이다. 이클리닝지표는사이클평준화가된상태에서는클리닝비용을줄이는방향으로작용하고, 사이클이편중화된경우에는사이클평준화를위해클리닝세그먼트가선택되도록작용한다. 다시말해서사이클이균등하게분배되어사이클평준화도가임계점이하인경우에는 l 값이 0에가깝기때문에 μ i 가세그먼트를선택하는주요인자가되며, 이와반대로그임계점을넘어서 l 값이 1에접근하면사이클평준화를위해초기화횟수가큰세그먼트를선택하게한다. 이때과도한사이클평준화를방지하기위해서어느정도이상의사이클편중화가진행된후에야 l 값이클리닝지표값에영향을미치도록하는것이필요하다. 그래서 l 값의계산을위해다음과같이사이클평준화도 Δ ε 에대해 S자형으로단조증가하는함수를사용한다. 2 단 l(δ ε)= 1+e { k, Δ ε ε 0 Δ ε 0 단, Δ ε =0 식 (8) 에서 kε 은이함수의기울기를결정하는상수가되며그림 5에서 kε 값이커질수록 l 값이완만하게증가하는것을관찰할수있다. 그래서이 kε 값을사이클평준화도를제어하는데사용할수있다. 만일엄격하지않게사이클을평준화시키고자한다면 kε 값을크게하고엄격하게사이클평준화를하려고한다면 kε 값을작 (8) 그림 5 k ε 의변화에따른 l의변화위와같이클리닝지표를통해사이클평준화를이루는기법을앞서소개한 CICLⅠ에결합시킨다. 이를 CICLⅡ로부르겠다 세그먼트할당정책플래시메모리관리자의할당자모듈은로그공간유지를위해어떤새로운세그먼트를할당하느냐에따라서사이클평준화를더개선할여지를가지고있다. 이를위해할당자가세그먼트를할당하게되는경우를두가지로분류해보면, ( ㄱ ) 일반적인입출력이수행되면서계속적으로로그공간을확보하고자할때와 ( ㄴ ) COLD데이타를수집한후에이를로그말단에복사할때가있다. 사이클평준화를위해서할당자는 ( ㄱ ) 의경우에는최소초기화횟수를가지는세그먼트를, ( ㄴ ) 의경우에는최대초기화횟수를가지는세그먼트를할당한다. ( ㄱ ) 의경우에적용된휴리스틱의근거는로그에새로이할당된세그먼트는그것이갖는데이타가현재빈번하게접근되는 HOT데이타일것이기때문에할당된세그먼트는클리닝될수있는기회가커질것이라는예측에 10) Sprite-LFS[10] 의 cost-benefit 정책의경우에는제안된클리닝지표값 ( age (1-μ) ) 이큰것을선택하게된다. μ

10 576 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) 있다. 그리고 ( ㄴ ) 의경우에는컬렉션연산에의해많은양의 COLD데이타가새로할당된세그먼트안에군집되어저장될것이기때문에당분간은다른세그먼트에비해상대적으로무효화가덜진행될것이다. 그래서이경우에는가장적게사이클을소비한세그먼트를할당해준다. 이러한세그먼트할당기법을가지는할당자를 CICLⅡ 에결합시켜 CICLⅢ로명명한다. 5. 성능분석 5.1 시뮬레이션과작업부하의설계성능분석을위해우리는저장매체로서 64개의세그먼트로구성된 1기가바이트용량의플래시메모리를사용하는플래시저장시스템시뮬레이터를구현하였다. 각세그먼트는 256개의초기화블록으로구성된다. 플래시메모리관리자의구현에있어서클리너가요구하는유효페이지의수와각세그먼트의초기화횟수등세그먼트관련정보는시뮬레이터내에서관리된다. 클리너는이세그먼트정보를이용하여쓰기연산이 100번수행될때마다자유공간의비율이 0.1이하인지를검사하여클리닝연산을시도한다. 그리고컬렉터는단편도가 0.8 을초과하는 COLD데이타에대해수행하며사이클평준화도를제어하는상수 k ε 는엄격한사이클평준화를위해 100으로설정하였다. 다른자세한내용은표 1에기술되어있다. 본실험에서는성능실험의신빙성을높이기위해두가지유형의작업부하 (workload) 를사용하였다. 한유형은 UNIX 작업부하로서 [6] 의 UNIX 파일크기분포에따라서생성되며여기에 COLD데이타가 HOT데이타보다그크기가크다는성질 [11] 을반영한다. 또하나의 LFS 유형의작업부하는 Sprite-LFS[10] 에서사용된 'hot-and-cold' 작업부하와유사한것으로서일정한작은크기 (4킬로바이트) 의파일에로컬리티를가지는갱신 ( 쓰기 ) 연산을가지고있다. 본논문이다루는문제는읽기연산의성능과는무관하기때문에설계된작업부하는읽기요청을포함하지않는다. 그리고각작업부하는여러수준의로컬리티에따라생성된다. ( 이때로컬리티의정도는작업부하이름과함께괄호안에표시된다.) 본논문에서는로컬리티를 Sprite-LFS[10] 에서와유사한방식으로표기한다. 예를들어, 는쓰기연산의 90% 가전체데이타의 10% 에집중되고, 그나머지 10% 의쓰기연산은 90% 의다른데이타영역에접근함 플래시메모리관련패러미터 플래시메모리타입 플래시메모리용량세그먼트크기세그먼트의수 초기화블록의수 페이지크기 표 1 시뮬레이션패러미터 1Mbit/chip 1Gbytes 16Mbytes 64 개 256개 / 세그먼트 512bytes 클리닝주기 클리닝시점 클리닝크기 컬렉션데이타인식 클리너패러미터 100 번쓰기연산마다 자유공간크기전체공간크기 < 세그먼트 컬렉터패러미터 FAW크기 = 200 단편도 > 0.8 컬렉션주기 k p =50 컬렉션크기 사이클평준화도 k s =0.3 전체메모리크기 사이클평준자패러미터 k ε =100 을나타낸다. 그래서 은로컬리티가없음을의미한다. 실제실험에서 UNIX(95 5) 작업부하를사용한경우, FAW의크기를 200으로하였을때 locality f 는약 , UNIX(50 50) 의경우에는 0.1이하로측정된다. 또한갱신이일어나지않은정적데이타가존재하는작업부하를표현하기위해또하나의패러미터를추가할수있다. 예를들어, 90 10, 80 은쓰기연산의 90% 가전체데이타의 10% 에집중되고, 나머지 10% 의쓰기연산이 80% 의다른데이타영역에접근함을의미한다. 이로컬리티를가지는작업부하에는접근되지않는 10% 의데이타영역이존재하게된다. 모든작업부하가가지는쓰기요청은 1,000,000페이지분량이고관련된파일의수는 500-2,000개정도이다. 각작업부하는초기에파일들을랜덤하게생성하고이생성된파일들을갱신또는삭제하는연산내용을담고있다. 쓰기요청시마다관련파일은의사난수 (pseudo-random number) 에따라선택되며선택된파일내에갱신되는지점도같은방식으로선택된다. 5.2 실험결과본연구에서는사이클평준화를이룬상태에서클리닝비용을줄이는데역점을두기때문에제안한기법의성능평가를위해그리디방법과기존의사이클평준화기법을조합한것을기준으로삼는다. 기존의사이클평준화기법중에서로그에새로운세그먼트를할당할때최소초기화횟수를갖는세그먼트를선택하는기법을 GreedyⅠ방법에결합시켜 GreedyⅡ로명명하고, 이보다강한사이클평준화를위해최소, 최대사이클횟수를가지는세그먼트들간에데이타를서로교환하는기법을 GreedyⅠ에병합한것을 GreedyⅢ로명명한다.

11 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 577 관리방법 GreedyⅠ GreedyⅡ GreedyⅢ 표 2 플래시메모리관리방법의분류 클리닝지표 μ COLD 데이타분리방법 없음 사이클평준화방법 없음 최대초기화세그먼트할당 데이타교환 닝비용이적다는것이다. 이는컬렉터가상대적으로적은비용을지출하면서클리닝연산비용을줄이는데크게기여하였기때문이다. 예를들어, CICLⅢ는 UNIX (95 5) 작업부하에서는전체클리닝비용중에서약 8% 정도 ( 그림 7에서컬렉션비용은막대상단에표시되어있음 ) 의컬렉션비용을부담하고 GreedyⅠ,Ⅱ의경우보다약 35% 정도의비용을감소시켰다. Cost- Benefit age (1-μ) μ 나이정렬기법없음 CICLⅠ CICLⅡ CICLⅢ μ l μ +(1-l) ε ε max +1 컬렉션연산 (4.2 절참조 ) 최대초기화세그먼트할당 최대 / 최소초기화세그먼트할당 (4.3.2 절참조 ) 또한순수하게클리닝비용측면에서다른로깅기법과비교하기위해서로그기반파일시스템인 Sprite- LFS의 cost-benefit기법을평가할것이다. 표 2에는본논문에서제안한플래시메모리공간관리방법들과이와비교평가하기위해제시된여러가지기법들이정리되어있다 클리닝비용측면그림 6(a) 는클리닝이계속진행될때마다클리닝세그먼트의활용률값의변화를보여준다. 이그림에서 GreedyⅠ은전술한바와같이 COLD데이타의단편화로인해클리닝세그먼트의활용률값이수렴하는현상을볼수있다. 그리고 CICLⅠ의클리닝효율이 GreedyⅠ 과비교해서클리닝세그먼트의활용률과클리닝횟수가감소하였는데평균적으로누적클리닝비용이약 30% 감소되었다. 그리고제안한 CICL 방법에서클리닝되는세그먼트활용률값이진동하는것은컬렉션연산에의해 COLD데이타가군집화되었다가다시단편화되는상황을나타낸다. 그림 6(b) 는누적클리닝비용의측면에서 CICLⅠ과 GreedyⅠ의클리닝의성능을비교한것이다. 이그림에서세그먼트활용률과로컬리티가높아짐에따라컬렉션연산의효과가높아짐을알수있다. 그림 7은각작업부하에대해여러가지플래시메모리관리기법을수행하였을때소요되는누적클리닝비용을보여준다. 대부분의작업부하에서제안된방법 (CICLⅠ,Ⅱ,Ⅲ) 이그리디방법보다우세한성능을보였다. 주목할것은로컬리티가존재하고세그먼트활용률이높을수록그리디방법 (GreedyⅠ,Ⅱ,Ⅲ) 과 Sprite- LFS의 cost-benefit방법 (Cost-Benefit) 보다누적클리 (a) (b) 그림 8 (a) GreedyⅠ과 CICLⅠ의비교 ( 클리닝세그먼트의활용률 ) (b) GreedyⅠ과 CICLⅠ의비교 ( 누적클리닝비용 ) CICLⅡ의경우에는클리닝지표에의한사이클평준화로인해컬렉션에의한클리닝성능향상효과가조금약화되었다. 그러나 4.2.3절에서제안한세그먼트할당휴리스틱을가지는 CICLⅢ는 CICLⅡ에서상실했던비용감소효과를회복하게된다. 사이클평준화를위해마련된휴리스틱이클리닝비용을낮추는부차적효과를얻은것이다. UNIX(95 5) 작업부하에서는오히려

12 578 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) CICLⅢ가 CICLⅠ,Ⅱ보다사이클평준화측면에서우세하면서 ( 그림 7(a) 참조 ) 동시에클리닝비용측면에서도 CICLⅠ,Ⅱ를능가한다. UNIX(90 10,80) 작업부하에서는제안된방법의클리닝비용의절감효과가다른작업부하에서보다적게나타나고있다. 이는 UNIX(90 10,80) 작업부하 10% 의비율로접근되지않는정적데이타를보유하고있기때문에다른작업부하에비해단편화되는데이타가덜발생하기때문이다. LFS작업부하에서도일정한작은크기의파일들만을포함하고있기때문에불필요하게복사되는 COLD데이타의양이 UNIX작업부하의경우보다많아제안된방법의효과가크지못한것이다. 결과적으로제안된 CICL 방법은클리닝연산시필요없이로그공간을이동하는 COLD데이타가많을수록그효과가커짐을확인할수있다. Cost-Benefit 방법은 [8,10] 에서사용된 costbenefit정책과 age-sorting기법을포함하고있는것이 다. 이기법은디스크기반의로깅시스템에서는좋은성능을보이는것으로알려져있지만본실험에서는모든경우에다른기법에비해클리닝성능이가장좋지않게나타났다. 이것은플래시저장시스템에서사용하는세그먼트의크기가 Sprite-LFS에서설정한세그먼트크기보다매우크기때문이다. cost-benefit정책은세그먼트활용률이작으면서동시에 age가큰세그먼트를클리닝함으로써성능을높인다. 하지만 age에따라페이지들을정렬한다할지라도매우큰세그먼트가가지는페이지들의 age값들이일관되지않아본래가지는 cost-benefit정책의효과가없어진다 클리닝횟수측면그림 8은제안한기법이클리닝횟수를얼마나감소시키는지를알아보기위해서각클리닝연산사이에서발생한쓰기요청회수를측정한것이다. 이값은총쓰기요청수를클리닝총횟수로나눈것으로서이를 클리닝간쓰기허용량 이라고부르겠다. 이클리닝간쓰기 Collection Cost Utilization = 0.75 Cost-Benefit Greedy I Greedy II Greedy III CICL I CICL II CICL III Utilization= Cumulative Cleaning Cost /Cleaning Frequency UNIX(80->20) UNIX(90->10,80) UNIX(95->5) Workload LFS(80->20) LFS(90->10) LFS(95->5) UNIX(80->20) UNIX(90->10,80) UNIX(95->5) LFS(80->20) LFS(90->10) LFS(95->5) Workload (a) (a) Collection Cost Utilization = 0.85 Cost-Benefit Greedy I Greedy II Greedy III CICL I CICL II CICL III Utilization= Cumulative Cleaning Cost /Cleaning Frequency UNIX(80->20) UNIX(90->10,80) LFS(90->10) UNIX(95->5) LFS(80->20) LFS(95->5) Workload UNIX(80->20) UNIX(90->10,80) UNIX(95->5) LFS(80->20) LFS(90->10) LFS(95->5) Workload (b) (b) 그림 7 (a) 누적클리닝비용의비교 ( 평균활용률 = 0.75) (b) 누적클리닝비용의비교 ( 평균활용률 = 0.85) 그림 8 (a) 클리닝간쓰기용량의비교 ( 평균활용률 = 0.75) (b) 클리닝간쓰기용량의비교 ( 평균활용률 = 0.85)

13 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 579 허용량은정의에따라누적클리닝비용과깊은관련을맺는측정치가되며시스템의수명을판단하는지표가될수있다. 이값이상대적으로크다는것은일정한쓰기요청에대해서클리닝이지연되어초기화연산이덜발생하였음을의미한다. 다시말해서세그먼트사이클을적게소비하는것이므로그만큼사용플래시용량을절약했다는것을나타낸다. 그림 8에서대부분의경우에제안된 CICL 방법들이다른방법에비해크게나타나고있으며로컬리티가클수록다른기법들이가지는값과의차가커지고있다. 그런데이클리닝간쓰기허용량이적다고해서반드시누적클리닝비용이커지는것은아니다. 예를들어, 컬렉션연산의기능이효과적으로작용하여클리닝연산의비용이크게적어지는경우가그렇다. 그림 7(b), 8(b) 에서평균활용률이 0.85이고 UNIX(80 20) 작업부하에대해측정한것을보면 CICL방법이다른방법에비해클리닝연산사이에서많은쓰기요청이발생했지만, 클리닝비용은증가하지않았음을관찰할수있다. UNIX (95->5) UNIX (80->20) LFS(90->10) LFS(80->20) 변화에따라민감하게동작한다. 그런데본논문은컬렉션주기와컬렉션크기의정밀한분석보다는컬렉션연산자체의개략적인효과에더큰의의를두고있기에컬렉션크기에대해서만다루고자한다. 컬렉션주기마다항상컬렉션연산이발생하는것이아니기때문에정밀한분석을위해서는각컬렉션주기값마다컬렉션크기값의모든조합에대한상당한실험이요구된다. cumulative cleaning cost UNIX (95->5) UNIX(80->20) LFS(90->10) LFS(80->20) collection size * segment 그림 10 컬렉션크기의변화에따른누적클리닝비용 cumulative cleaning cost FAW size 그림 9 FAW크기의변화에따른누적클리닝비용 컬렉션연산의효과컬렉션연산의성능을결정짓는인자는 FAW의크기, 컬렉션크기, 컬렉션주기등이다. 전술한바와같이 FAW는본논문에서 COLD데이타를판단하는도구로사용되는것인데그크기가너무작거나너무크면그기능을상실하게된다. 그림 9는제안하는기법을사용하여여러작업부하에대한누적클리닝비용을측정한것이다. FAW의크기가 200 전후일때클리닝비용이가장적게나타나고있다. 그래서본실험에서는 FAW의크기를 200으로설정한다 ( 표 1 참조 ). 또한컬렉션연산은컬렉션크기또는컬렉션주기의 그림 10은 CICLI기법을사용했을때컬렉션주기값을고정시켜놓고컬렉션크기의변화에따른누적클리닝비용값을측정한것이다 11). 이때컬렉션크기에해당하는세로축은세그먼트의크기, 즉페이지개수의배수로나타낸다. 이그림을통해서컬렉션연산이클리닝비용을감축하는효과를가지기위해서는컬렉션크기가어느정도이상이되어야하며, 또한지나치게많은데이타를수집하는경우에는오히려전체클리닝비용이높아질수있음을확인하였다. 컬렉션주기와관련해서도그림 10과유사한그래프를얻을수있음을충분히짐작할수있으며자세한실험설명은생략한다. 본실험에서는그림 10에근거하여컬렉션크기를결정하는비례상수 k s 값을전체메모리크기의 0.3배수로, 컬 렉션주기를결정하는비례상수 k p 값은 50으로설정하였다 ( 표 1 참조 ) 사이클평준화측면그림 11은클리닝연산이진행되고있을때마다사이클평준화도 Δ ε 를측정한것이다. 그래프의모양이작은값을가지면서진동하는것은사이클평준화가되어가 11) 그림 10 은여러컬렉션주기값중에서가장성능이좋은때를취한것이다.

14 580 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) 는과정을보여준다. UNIX(90 10,80) 작업부하의경우에 GreedyⅠ,Ⅱ기법은극심한사이클편중화현상을보인다. 이에반해서클리닝지표를사용하는 CICLⅡ기법과세그먼트할당휴리스틱을사용하는 CICLⅢ은누적클리닝비용이적음에도불구하고안정된평준화현상을보이는것을관찰할수있다. 특히 CICLⅢ기법은다른방법에비해사이클평준화정도가우수하면서도클리닝비용측면에서도뒤떨어지지않는다. 그리디클리닝방법에기존의사이클평준화기법을가미한 GreedyⅢ방법은 CICL방법에근접하는사이클평준화효과를보이고있지만클리닝비용면에서는 Cost-Benefit을제외해서가장낮은성능을보이고있다. 이것은초기화횟수의최대, 최소값을갖는세그먼트사이에서데이타교환으로많은쓰기연산이발생했기때문이다. 그리고본실험에서클리닝비용을줄이기위해제안된컬렉션연산이사이클평준화에도기여함을알수있다. 그림 11에서컬렉션연산기능만을가지는 CICLⅠ 기법은사이클평준화를위한기능이포함되어있지않음에도불구하고모든경우에사이클평준화효과를보이고있다. 이것은컬렉션연산이 COLD데이타를포함하는세그먼트내의페이지들을무효화시킴으로써이세그먼트들이클리닝될가능성을높이는것으로설명할수있다. (a) 그림 12 k ε 에의한사이클평준화도의제어 (b) (c) 그림 11 (a) 사이클평준화도의변화 (UNIX(95 5) 작업부하 ) (b) 사이클평준화도의변화 (UNIX(90 10,80) 작업부하 ) (c) 사이클평준화도의변화 (LFS(90 10) 작업부하 ) 또한앞에서제안된클리닝지표의상수 k ε 는사이클평준화도를제어할수있다고언급한바가있는데그림 12에서이사실을확인할수있다. 이그림은 CICLⅡ 기법에서상수 k ε 값이적어짐에따라사이클평준화가보다엄격하게이루어지고있음을보여준다. 그리고사이클평준화효과가강해지면서도누적클리닝비용이크게증가하고있지는않는다. 실제로이 k ε 값은플래시저장시스템이사용되는환경에맞게적절히조정하면될것이다. 만약플래시메모리의사이클제한횟수의오차범위를알수있다면이값도 k ε 에반영할수있다. 그림 13은시간 ( 쓰기요청 ) 의진행에따라서모든세그먼트들의초기화횟수값이변하는양상을보여준다. 그래서사이클편중화가발생하는경우에는골짜기형태의그래프가형성될것이다. 이그림에서 GreedyⅡ의

15 신뢰성있는플래시메모리저장시스템구축을위한플래시메모리저장공간관리방법 581 경우에는시간이지나면서깊은골짜기가생기고있지만, CICLⅢ의경우에는대체로편평한면이만들어짐을관찰할수있다. 이를통해서제안된사이클평준화기법이시스템의저장공간을잘활용하면서시스템수명을높이는기여함을확인할수있다. (a) (b) 그림 13 (a) 초기화횟수의변화 (GreedyⅡ방법) (b) 초기화횟수의변화 (CICLⅢ 방법 ) 이두예를가지고사이클평준화기법에따라시스템의수명이어떤차이를보이는지알아보자. 만일사이클링횟수가 100번으로제한되고, 가용플래시메모리공간의비율이 0.2이하일때시스템고장이발생한다고가정하자. 그리고그림 13에표시된고장시점 (failure point) 까지 GreedyⅡ의사용사이클용량은약 5,700 (segments erases) 이고 CICLⅢ은약 6,200 (segments erases) 사이클용량을소비한다. 게다가 CICLⅢ기법은 GreedyⅡ보다일정량의쓰기요청에대해클리닝횟수가약 0.1의비율로감소하였다. 결과 적으로 CICLⅢ 은시스템의수명을 GreedyⅡ 보다약 20% ( = 6,200 5,700 (1-0.1) -1.0 ) 증가시킬수있다.(3.2 절참 조 ) 지금까지의여러가지실험을통해서제안된사이클평준화기법이클리닝메커니즘과매우조화롭게동작하고있음을확인할수있었다. 기존의사이클평준화방법이클리닝연산과일반적인입출력연산의성능을저하시키는성질을가지고있는반면에제안된사이클평준화기법은클리너의클리닝지표를통해간단하게구현되어시스템에큰부하를주지않으면서효과적으로수행되었다. 이방법이클리닝연산비용을높이지않으면서안정된효과를가질수있는것은플래시공간관리전략으로사용된로깅과클리닝비용을줄이기위한컬렉션연산, 세그먼트할당을위해사용한휴리스틱등이잠재적으로사이클평준화의성질을이미가지고있기때문이다. 6. 결론 본논문은플래시메모리공간관리에서반드시해결해야할사이클평준화와클리닝비용절감문제를 COLD데이타의수집과특별히고안된클리닝지표를통해해결하였다. 더불어제안된방법을평가하기위해플래시메모리에적합한새로운클리닝비용모델을제안하였다. 플래시메모리를저장매체로하였을때의중요한문제는플래시메모리사용을균등하게분포시키는것인데이는클리닝지표와세그먼트할당과관련된휴리스틱, 컬렉션연산에잠재된평준화효과등에의해해결된다. 결과적으로제안된플래시메모리관리자가클리닝비용절감문제와사이클평준화문제를동시에해결함으로써신뢰성있는시스템을구축하는데큰도움을줄수있다. 그리고실험결과, 제안된 COLD데이타의컬렉션기법은특히플래시메모리공간활용률이높거나로컬리티정도가높을때좋은성능을보이고있기때문에쓰기연산이로컬리티를가지고빈번하게발생하는 OLTP환경이나사무 / 엔지니어링 (office/ engineering) 환경에적합할것으로본다. 또한제안된방법은로깅을전제로하고있지만, 실제로는로깅에크게의존하지는않아서다른저장전략을가지는시스템에쉽게활용할수있다. 참고문헌 [1] T. Blackwell, J. Harris, and M. Seltzer, Heuristic Cleaning Algorithms in Log-Structured File

16 582 정보과학회논문지 : 시스템및이론제 27 권제 6 호 (2000.6) Systems, Proceedings of 95 Winter, USENIX, pp , 1995 [2] R. Cáceres, F. Douglis, K. Li, and B. Marsh, Operating System Implications of solid-state mobile computers, Technical Report MITL- TR-56-93, Matsushita Information Technology Laboratory, 1993 [3] P. J. Denning, Working Sets Past and Present, IEEE Transactions on Software Engineering, Vol. SE-6, No.1, pp , 1980 [4] B. Dipert, and M. Levy, "Designing with FLASH MEMORY," Annabooks, pp , 1994 [5] F. Douglis, R. Cáceres, F. Kaashoek, K. Li, B. Marsh, and J. A. Tauber, "Storage Alternatives for Mobile Computers," Proceedings of the 1st Symposium on Operating Systems Design and Implementation, pp.25-37, 1994 [6] G. Irlam, "Unix File Size Survey," base.com/gordoni/gordoni.html, 1993 [7] A. Kawaguchi, S. Nishioka, and H. Motoda, "Flash memory Based File System," Proceedings of '95 Winter, USENIX, pp , 1995 [8] J. N. Matthews, D. Roselli, A. M. Costello, R. Y. Wang and T. E. Anderson, "Improving the Performance of Log-Structured File Systems with Adaptive Methods," Proceedings of the 16th ACM Symposium on Operating Systems Principles, pp , 1997 [9] J. T. Robinson, "Analysis of Steady-State Segment Storage Utilization in a Log-Structured File System with Least-Utilized Segment Cleaning," Operating System Review, Vol.30, No.4, pp.29-32, 1996 [10] M. Rosenblum, and J. K. Ousterhout, "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol.10, No.1, pp.26-52, 1992 [11] C. Ruemmler, and J. Wilkes, "UNIX disk access patterns," Proceedings of '93 Winter USENIX, pp , 1993 [12] D. See, and C. Thurlo, "Managing Data in an Embedded System Utilizing Flash Memory," Intel Technical Note,1995, flcomp/papers/esc_flsh.htm [13] M. Wu, and W. Zwaenepoel, "envy : A Non-Volatile Main Memory Storage System," Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems, pp.86-97, 1994 [14] Intel, Flash Memory Databook, pp.21-29, 1995 김한준 1994 년서울대학교계산통계학과졸업 ( 학사 ) 년서울대학교계산통계학과졸업 ( 석사 ) 년 3 월 ~ 현재서울대학교컴퓨터공학부박사과정. 관심분야는파일시스템, 데이타베이스, 데이타마이닝임 이상구 1985년서울대학교자연과학대학계산통계학과졸업 ( 학사 ). 1987년 Northwestern Univeristy 졸업 ( 석사 ). 1990년 northwestern University 졸업 ( 박사 ). 1989년 9월 ~ 1990년 6월 U. of Minnesota 전임강사. 1990년 ~ 1992년 7월 EDS 연구원. 1992년 8월 ~ 현재서울대학교전산과학과부교수. 관심분야는논리데이타베이스, 질의최적화, 정보검색