ISSN 2383-630X(Print) / ISSN 2383-6296(Online) Journal of KIISE, Vol. 41, No. 12, pp. 1026-1034, 2014. 12 http://dx.doi.org/10.5626/jok.2014.41.12.1026 부분 가비지 컬렉션을 이용한 로그 구조 파일시스템의 쓰기 성능 개선 (Partial Garbage Collection Technique for Improving Write Performance of Log-Structured File Systems) 곽현호 신 동 군 (Hyunho Gwak) (Dongkun Shin) 요 약 최근 플래시 저장장치의 사용이 대중화되면서 플래시 저장장치의 특성에 맞는 로그 구조 파일 시스템에 대한 관심도 높아지고 있다. 로그 구조 파일시스템은 사용자의 임의 쓰기를 파일시스템에서 순차 쓰기로 바꾸어 처리한다. 이 순차 쓰기를 유지하기 위해 파일시스템에서 가비지 컬렉션(Garbage Collection)을 해 주어야 하는데, 이때 오버헤드로 인해 쓰기 성능이 감소하는 것을 막기 위한 기법으로 SSR (Slack Space Recycling)이 제시되었다. 그런데, SSR은 임의 쓰기를 발생시키기 때문에, 임의 쓰기 성능이 낮은 저가형 저장장치에서 쓰기 성능을 감소시키는 문제가 있다. 본 논문에서 제시하는 부분 가비 지 컬렉션은 SSR방식으로 데이터를 기록하기 전에 유효한 블록들을 일부만 복사하여 옮김으로써 무효화 된 공간의 크기를 늘려 임의 쓰기 수를 줄여서 쓰기 성능을 증가시키는 기법으로, SD 카드에서 쓰기 성 능을 최대 두 배 이상 증가시켰다. 키워드: 로그 구조 파일시스템, 플래시 저장장치, 가비지 컬렉션, 유휴공간 재활용 Abstract Recently, flash storages devices have become popular. Log-structured file systems (LFS) are suitable for flash storages since these can provide high write performance by only generating sequential writes to the flash device. However, LFS should perform garbage collections (GC) in order to reclaim obsolete space. Recently, a slack space recycling (SSR) technique was proposed to reduce the GC overhead. However, since SSR generates random writes, write performance can be negatively impacted if the random write performance is significantly lower than sequential write performance of the target device. This paper proposes a partial garbage collection technique that copies only a part of valid blocks in a victim segment in order to increase the size of the contiguous invalid space to be used by SSR. The experiments performed in this study show that the write performance in an SD card improves significantly as a result of the partial GC technique. Keywords: log-structured file systems, flash storage, garbage collection, slack space recycling 본 연구는 미래창조과학부 및 정보통신기술연구진흥센터의 정보통신 방송 연구 개발사업의 일환으로 수행하였음. [10041244, 스마트TV 2.0 소프트웨어 플랫폼] 이 논문은 2014 한국컴퓨터종합학술대회에서 부분 가비지 컬렉션을 이용한 로 그 구조 파일시스템의 쓰기 성능 개선 의 제목으로 발표된 논문을 확장한 것임 논문접수 : 2014년 8월 22일 (Received 22 August 2014) 심사완료 : 2014년 9월 25일 (Accepted 25 September 2014) CopyrightC2014 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작물 학생회원 : 성균관대학교 전자전기컴퓨터공학과 의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, gusghrhkr@gmail.com 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 종신회원 : 성균관대학교 컴퓨터공학과 교수(Sungkyunkwan Univ.) 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위 dongkun@skku.edu 를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. (Corresponding author임) 정보과학회논문지 제41권 제12호(2014. 12)
부분 가비지 컬렉션을 이용한 로그 구조 파일시스템의 쓰기 성능 개선 1027 1. 서 론 플래시 저장장치는 저전력, 작은 크기, 높은 내구성, 높은 임의 접근 성능 등의 특성을 가지고 있어서 휴대 전화 같은 임베디드 시스템에서 많이 사용되어 왔다. 최 근에는 SSD나 SD 카드 등의 가격이 낮아지면서 플래 시 저장장치가 점점 대중화되는 중이다. 또한, 플래시 저장장치에 적합한 파일시스템인 로그 구조 파일시스템 [1]에 대한 관심도 높아지고 있다. 로그 구조 파일시스템은 기존 파일시스템들과 달리 데이터를 업데이트 할 때 원래 위치에 덮어쓰는 것이 아니라, 전에 기록한 데이터는 무효화하고 새로 쓰여지 는 데이터는 다른 곳에 기록하며 순차적으로 쓴다. 따라 서, 작은 임의 쓰기 요청들을 모아서 하나의 큰 순차 쓰 기 요청으로 처리할 수 있다. 이러한 로그 구조 파일시 스템의 쓰기 방식은 임의 쓰기 성능이 순차 쓰기 성능 보다 낮은 플래시 저장장치에 유리하기 때문에, 플래시 저장장치에서 사용되는 YAFFS2[2], JFFS2[3], UBIFS[4] 등과 같은 플래시 파일시스템들이 로그 구조 쓰기 방식 을 사용하고 있다. 특히, SSD와 같은 플래시 저장장치 의 경우에 여러 페이지를 기록하는 큰 크기의 쓰기 요 청은 병렬적으로 접근이 가능한 여러 플래시 칩에서 동 시에 처리가 가능하므로 쓰기 성능이 개선된다[5]. 플래 시 저장장치 외에도 하드디스크와 같은 대부분의 저장 장치에서 임의 쓰기 성능이 순차 쓰기 성능보다 낮기 때문에, 로그 구조 파일시스템을 사용하면 쓰기 성능을 증가시킬 수 있다. 로그 구조 파일시스템은 세그먼트 단위로 순차 쓰기 를 보장하는데, 순차 쓰기를 할 연속된 여유 공간인 프 리 세그먼트를 확보하기 위해, 무효화된 데이터들을 모 아서 프리 세그먼트를 만드는 가비지 컬렉션(Garbage Collection)을 파일시스템에서 해주어야 한다. 그런데, 사 용할 프리 세그먼트가 부족하여 가비지 컬렉션이 필요 하게 되면, 유효한 데이터들을 복사하는 가비지 컬렉션 의 오버헤드 때문에 쓰기가 지연되므로 쓰기 성능이 크 게 감소할 수 있다. 그래서, 로그 구조 파일시스템에서 가비지 컬렉션의 오버헤드로 인해 쓰기 성능이 감소하 는 것을 줄이기 위해 다양한 기법들이 사용되고 있다. SSR (Slack Space Recycling)[6]은 로그 구조 파일시 스템의 가비지 컬렉션의 오버헤드로 인해 쓰기 성능이 감소하는 것을 막기 위해 제안된 기법이다. SSR은 연속 된 여유 공간이 부족할 때 가비지 컬렉션을 하지 않고 데이터를 더티 세그먼트의 무효화된 데이터 자리에 기 록함으로써 가비지 컬렉션을 지연시키는 기법이다. 그래 서, 가비지 컬렉션이 사용자 쓰기 요청 처리 중에 발생 하지 않고, 백그라운드에서 발생되도록 지연시켜 가비지 컬렉션으로 인한 쓰기 성능 감소를 막을 수 있다. 하지 만, SSR을 사용하면 남아있는 유효한 데이터들로 인해 작은 크기의 연속된 유휴공간들이 많아서 저장장치에 임의 쓰기를 유발하는 문제가 있다. 특히 임의 쓰기 성 능이 순차 쓰기 성능에 비해 낮은 저장장치에서 큰 성 능저하를 유발할 수 있기 때문에, SSR을 사용하는 것 보다 가비지 컬렉션을 하는 것이 오히려 쓰기 성능이 더 좋을 수 있다. 본 논문에서 제시하는 부분 가비지 컬렉션은 이 점에 착안해서, SSR을 사용할 때 저장장치의 순차, 임의 쓰 기 성능 차이와 가비지 컬렉션의 오버헤드를 비교하여 가비지 컬렉션의 오버헤드보다 순차 쓰기로 인한 성능 증가가 더 크다면 해당 쓰기 공간에 부분적으로 가비지 컬렉션을 적용하여 쓰기 성능을 증가시키는 기법이다. 실험 결과, 플래시 저장장치에서 F2FS(Flash Friendly File System)[7]를 사용하여 실험했을 때, SSR 또는 가비지 컬렉션만을 사용하는 것 보다 부분 가비지 컬렉 션을 사용하여 쓰기 성능을 최대 두 배 이상 증가시킬 수 있었다. 2장에서는 로그 구조 파일시스템에서 가비지 컬렉션 오버헤드를 줄이기 위한 기법들에 대해 설명하며, 3장에 서는 로그 구조 파일 시스템에 대해 설명한다. 4장에서 부분 가비지 컬렉션이 어떻게 구현되었는지 다루고, 5장 에서는 실험을 통해 기존 기법과 부분 가비지 컬렉션을 사용한 결과를 비교한다. 그리고, 마지막으로 6장에서 결론을 낸다. 2. 관련연구 SSR 이외에도 로그 구조 파일 시스템에서 가비지 컬 렉션의 오버헤드를 줄이기 위해 다양한 기법들이 제시 되었다. 먼저, 가비지 컬렉션을 적용하는 희생(Victim) 세그먼트를 효과적으로 선택하기 위해 그리디(Greedy) 알고리즘[8]이 사용된다. 그리디 알고리즘을 사용하면 세그먼트 안의 남아있는 유효한 페이지가 가장 적은 세 그먼트를 희생 세그먼트로 선정한다. 그래서, 희생 세그 먼트 안의 유효한 페이지들을 복사하는 가비지 컬렉션 의 오버헤드를 최소화한다. CB(Cost-Benefit)[9] 알고리 즘은 세그먼트 안의 남아있는 유효한 페이지의 수와 함 께 페이지들의 경과 시간도 고려해서 희생 세그먼트를 선정한다. 페이지의 경과 시간은 페이지가 처음 기록되 고 나서 무효화 될 때까지 경과한 시간이다. 그래서, a 가 페이지들의 경과 시간 중에서 가장 작은 값이고, u가 유효한 페이지의 비율일 때, 각 세그먼트당 a (1-u) / 2u 값을 비교하여 이 값이 가장 큰 세그먼트를 희생 세 그먼트로 선정한다. CB 알고리즘은 그리디 알고리즘보 다 복사할 페이지의 수가 많아서 오버헤드가 더 클 수
1028 정보과학회논문지 제41권 제12호(2014. 12) 있다. 하지만, 업데이트가 잘 되지 않아서 경과 시간이 큰 페이지들을 모아둠으로써 장기적으로 봤을 때 희생 세그먼트를 선택할 때 유효한 페이지들이 감소하여 가 비지 컬렉션의 오버헤드를 줄일 수 있다. WOLF[10]는 데이터의 업데이트 빈도에 따라서 핫 (Hot)과 콜드(Cold) 데이터로 분리하여 서로 다른 세그 먼트에 기록하는 파일시스템이다. SFS[11]도 데이터를 업데이트 빈도에 따라 구분하여 서로 다른 세그먼트에 쓰는 파일시스템이다. 또한, 가비지 컬렉션을 적용할 때 도 희생 세그먼트와 같은 데이터 타입의 세그먼트에 유 효한 블록을 복사한다. WOLF와 SFS은 업데이트 빈도 가 낮아서 가비지 컬렉션을 할 때 높은 확률로 남아있 는 데이터들을 구분하여 저장하게 된다. 그래서, 가비지 컬렉션을 할 때 유효한 페이지의 수를 감소시켜 가비지 컬렉션의 오버헤드를 줄일 수 있다. Hole Plugging[12]은 가비지 컬렉션을 할 때 유효한 페이지들을 더티 세그먼트의 무효화된 공간에 복사하는 기법이다. 기존 로그 구조 파일 시스템의 가비지 컬렉션 은 유효한 페이지들을 프리 세그먼트에 복사하기 때문에 하나의 프리 세그먼트를 소모하게 된다. 그래서, Hole Plugging을 사용하면 프리 세그먼트를 확보하기 위해 필요한 가비지 컬렉션의 횟수를 줄일 수 있다. 3. 배경지식 3.1 로그 구조 파일시스템 로그 구조 파일시스템은 EXT4등의 전통적인 파일시 스템에서 사용하는 제자리(In-Place) 업데이트 방식을 사용하지 않고 다른 자리(Out-of-Place) 업데이트 방식 을 사용하여, 데이터가 업데이트 될 때 해당 데이터가 기록되어 있는 페이지에 덮어쓰는 것이 아니라, 전에 기 록되었던 페이지는 무효화 하고 새로운 페이지에 쓴다. 그래서, 로그 구조 파일시스템은 MB 단위의 큰 연속된 페이지들의 집합인 세그먼트 단위로 순차 쓰기를 보장 할 수 있다. 하지만, 로그 구조 파일시스템은 다른 파일 시스템들과 달리 파일시스템에서 가비지 컬렉션이라는 추가적인 작업을 통해 프리 세그먼트를 확보하는 것이 필요하다. 가비지 컬렉션을 사용하면, 먼저 희생 세그먼 트들을 선택하고, 그 세그먼트 안의 남아있는 유효한 페 이지들을 모두 다른 세그먼트로 복사하여 프리 세그먼 트를 확보한다. 그림 1(a)는 가비지 컬렉션을 적용하여 프리 세그먼트를 만드는 것을 보여준다. 세그먼트 17이 가비지 컬렉션을 적용할 희생 세그먼트로 선정되어, 세 그먼트 안의 남아있는 모든 유효한 페이지들을 세그먼 트 6으로 복사하고 세그먼트 17을 프리 세그먼트로 만 든다. 이와 같이, 가비지 컬렉션은 유효한 페이지들을 복사하는 오버헤드가 발생한다. 그래서, 사용자 쓰기 요 (a) Garbage Collection (b) SSR 그림 1 로그 구조 파일시스템의 가비지 컬렉션과 SSR Fig. 1 Garbage Collection and SSR of LFS 청을 처리하는 중에 프리 세그먼트가 부족해져서 프리 세그먼트를 확보해야 할 경우 가비지 컬렉션의 오버헤 드로 인해 사용자 쓰기가 지연되어 쓰기 성능이 크게 감소할 수 있다. 로그 구조 파일시스템의 가비지 컬렉션 오버헤드를 줄이기 위해 다양한 기법들이 제시되었고, SSR도 그 중 하나이다. SSR은 프리 세그먼트가 부족할 때 가비지 컬 렉션을 통해 프리 세그먼트를 확보할 필요 없이 더티 세그먼트 안의 무효화된 페이지 자리에 새로운 데이터 를 덮어쓴다. 그래서, 가비지 컬렉션으로 인해 사용자 쓰기가 지연되어 쓰기 성능이 감소하는 것을 막을 수 있다. 하지만, SSR은 더티 세그먼트에 쓰기 요청을 처 리하므로 임의 쓰기를 하게 된다. 그림 1(b)는 세그먼트 17에 SSR을 사용하여 P 1~P 5 다섯 개 페이지를 쓰는 것을 보여준다. 세그먼트 17에 남아있는 유효한 페이지 들로 인해 사용자 쓰기 요청이 P 1, P 2, P 3~P 5 세 개의 쓰기 요청으로 분리된다. 3.2 Flash Friendly File System 본 논문에서는 로그 구조 파일시스템중 하나인 F2FS 를 사용하여 부분 가비지 컬렉션을 구현하였다. F2FS는 플래시 메모리의 특성에 맞추어 설계된 파일시스템으로 플래시 저장장치에서 높은 성능을 보인다. F2FS의 기본 쓰기 단위는 4KB 블록이고, 연속된 512개의 블록의 집 합인 세그먼트를 할당 받아서 순차 쓰기를 한다. F2FS는 기존 로그 구조 파일시스템과 달리 메타 데 이터들을 다른 데이터들과 구분하여 관리한다. F2FS는 그림 2에서 보여주는 것처럼 메타 데이터들을 파일 시 스템의 앞부분에 구분하여 저장한다. 파일시스템의 슈퍼 블록(Super Block), 체크포인트 영역(Checkpoint Area), 세그먼트들에 대한 정보를 가지고 있는 SIT(Segment Information Table)와 SSA(Segment Summary Area), 노드에 대한 정보를 가지고 있는 NAT(Node Address
부분 가비지 컬렉션을 이용한 로그 구조 파일시스템의 쓰기 성능 개선 1029 그림 2 F2FS 개요 Fig. 2 F2FS Overview Table)들이 다른 데이터들과 구분되어 저장된다. 이 메 타 데이터들은 제자리 업데이트 방식으로 저장된다. 그 외 데이터들은 F2FS의 주 영역(Main Area)에 다른 자 리 업데이트 방식을 사용하여 순차적으로 저장된다. 이 때, 데이터는 업데이트 빈도가 많은 순서대로 핫, 웜 (Warm), 콜드 타입으로 분류되어 서로 다른 세그먼트 에 기록된다. 가비지 컬렉션 시에 복사되는 유효한 블록 들은 자주 업데이트 되지 않는다고 판단되어서 콜드 세 그먼트로 옮겨진다. F2FS도 로그 구조 파일시스템이므로 기본적으로 프리 세그먼트를 확보하기 위한 가비지 컬렉션을 사용해야 한 다. F2FS는 포어그라운드와 백그라운드 두 가지 가비지 컬렉션을 사용하며 각각 다른 희생 세그먼트 선택 알고 리즘을 적용한다. 할당 받은 세그먼트를 다 채우면 새로 프리 세그먼트를 할당 받는데, 이때 남은 프리 세그먼트 의 수가 미리 정의된 값보다 작을 경우 포어그라운드 가 비지 컬렉션을 사용한다. 포어그라운드 가비지 컬렉션은 가비지 컬렉션의 오버헤드로 인해 쓰기가 지연되는 것을 최소화 하기 위해 그리디 알고리즘을 사용하여 유효한 페이지가 가장 적은 세그먼트를 희생 세그먼트로 선택한다. 백그라운드 가비지 컬렉션은 파일시스템에서 작업이 없을 때 백그라운드에서 일어나며 미리 프리 세그먼트 를 확보한다. 이때는 당장 프리 세그먼트가 필요한 상황 이 아니므로 CB 알고리즘을 사용하여 희생 세그먼트를 선택한다. 포어그라운드와 백그라운드 가비지 컬렉션이 사용되면, 희생 세그먼트 안의 남아있는 유효한 블록들 을 모두 콜드 세그먼트로 이동시켜 프리 세그먼트를 만 든다. 이때, 콜드 세그먼트가 프리 세그먼트가 아닐수도 있는데, 그때는 유효한 페이지들을 콜드 세그먼트의 유 휴공간에 분산하여 복사한다. 하지만, F2FS는 포어그라운드 가비지 컬렉션의 오버 헤드로 인해 쓰기 성능이 감소하는 것을 막기 위해 프리 세그먼트의 개수가 작을 경우에 미리 SSR을 사용한다. 프리 세그먼트를 새로 할당 받을 때 남은 프리 세그먼트 수가 미리 정의된 오버프로비젼(Over-Provison) 값보다 작을 경우 SSR모드로 쓰기 시작한다. 그래서, 프리 세그 먼트 대신 더티 세그먼트를 할당 받아서 임의 쓰기를 하 게 된다. 이때 오버프로비젼 값은 포어그라운드 가비지 컬렉션을 사용하기 시작하는 값보다 크다. 그러므로, SSR이 가비지 컬렉션보다 먼저 사용되고, 가비지 컬렉 션의 오버헤드로 인해 쓰기가 지연되는 것을 막는다. 시스템이 갑작스럽게 종료되면, 저장장치에 대한 마지 막 몇 개의 작업들이 불완전하게 수행된 상태로 시스템 이 종료될 수 있다. 그래서, F2FS는 체크포인팅(Checkpointing)으로 저장장치와 파일시스템간에 일관성을 유 지한다. 체크포인팅은 메모리에서 저장장치에 기록되지 않은 데이터와 메타 데이터들을 모두 저장장치에 저장 한다. 그리고, 마지막으로 쓰여진 세그먼트의 정보와 그 세그먼트를 가리키는 포인터를 체크포인트 영역에 저장 한다. 그래서, 체크포인트 영역을 참조하여 가장 최근에 체크포인팅된 상태로 되돌아갈 수 있다. 체크포인팅은 파일시스템이 언마운트 될 때 사용되며 파일시스템이 마운트 될 때 체크포인트 영역을 읽어서 파일시스템이 종료했던 상태로 복구하는데 사용된다. 그래서, 시스템 이 갑작스럽게 종료되어 체크포인팅 전에 파일시스템이 종료되면, 마지막으로 체크포인팅 된 상태로 돌아가서 파일시스템과 저장장치간에 일관성을 유지한다. 그런데, 체크포인팅 된 상태로 돌아갔을 때 일관성을 유지하기 위해서는 가비지 컬렉션을 사용할 때 체크포인팅을 사 용 할 필요가 있다. 시스템이 갑작스럽게 종료되면 유효 한 블록들이 복사된 후에 변경된 메타 데이터를 저장장 치에 저장하지 못하고 파일시스템이 종료될 수 있다. 그 리고, 무효화된 블록에 새로운 데이터가 덮어 쓰였다면, 파일시스템이 복구되었을 때 이전 메타 데이터를 가지 고 있으므로 잘못된 데이터를 가리키게 된다. 따라서, F2FS는 가비지 컬렉션으로 하나의 프리 세그먼트를 확 보할 때마다 체크포인팅을 사용한다. 마찬가지로, SSR 을 사용하여 무효화된 블록 자리에 쓸 때도 같은 문제 가 발생한다. 그래서, SSR은 가장 최근의 체크포인팅 전에 무효화 된 블록들의 자리에만 쓰기 요청을 처리한다. 4. 부분 가비지 컬렉션 4.1 SSR과 가비지 컬렉션 SSR모드로 쓰기를 시작할 때 더티 세그먼트에 남아있 는 유효한 블록들이 적고, 저장장치의 임의 쓰기 성능이 순차 쓰기 성능에 비해 크게 낮다면 SSR을 사용하지 않 고 가비지 컬렉션을 하는 것이 쓰기 성능이 더 좋을 수 있다. 그림 3의 그래프는 F2FS로 마운트된 세 가지 저 장장치에서 SSR을 사용한 쓰기 성능과 SSR을 사용하 지 않고 가비지 컬렉션을 사용한 쓰기 성능을 비교한 것 이다. 실험은 유효한 블록의 비율이 30%인 상황에서 쓰 기 성능이 다른 클래스 2 SD 카드 A와 클래스 10 SD 카드 B, C에서 진행하였다. SD 카드 A에서는 SSR을 사용함으로써 가비지 컬렉션보다 쓰기 성능이 두배 이상 증가하는 것을 보여준다. 이처럼, 상황에 따라 SSR을 사 용하지 않는 것이 쓰기 성능이 더 좋을 수 있다.
1030 정보과학회논문지 제41권 제12호(2014. 12) (a) SSR 그림 3 SSR과 가비지 컬렉션 Fig. 3 Write performance of SSR and Garbage Collection 4.2 부분 가비지 컬렉션의 적용 부분 가비지 컬렉션(Partial Garbage Collection)은 SSR모드로 쓰기를 시작해서 더티 세그먼트를 할당 받았 을 때 사용된다. 세그먼트 단위로 사용되는 기존 가비지 컬렉션과 달리, 부분 가비지 컬렉션은 세그먼트 안의 연 속된 유효한 블록 단위로 사용된다. 그래서, 각 유효한 블록들에 대해 가비지 컬렉션을 적용하는 것이 쓰기 성 능이 더 좋아지는 경우에만 해당 블록들에 대하여 가비 지 컬렉션을 적용한다. 이처럼 세그먼트 안에서 부분적 으로 가비지 컬렉션을 적용함으로써 SSR이나 가비지 컬 렉션 보다 더 좋은 쓰기 성능을 제공할 수 있다. 그림 4(a)는 SSR을 사용하여 세그먼트 21에 B 1~B 5 다섯 개 블록에 대한 쓰기 요청을 처리하는 것을 보여준다. 이때 세그먼트 안에 남아있는 하나의 유효한 블록 B 6으로 인 해 쓰기 요청이 나누어진다. 그런데, B 6 블록 하나만 복 사하여 무효화한다면 B 1~B 5 다섯 개 블록을 순차적으로 기록할 수 있으므로 쓰기 성능을 증가시킬 수 있다. 하지 만, 기존 가비지 컬렉션을 사용하면 세그먼트 21에 남아 있는 모든 유효한 블록들을 복사하게 되는데, 세그먼트 21의 나머지 공간이 거의 유효한 블록들인 경우에는 가 비지 컬렉션의 오버헤드가 커지므로 SSR을 사용하는 것 보다 쓰기 성능이 감소할 수 있다. 그래서, 블록 단위로 적용되는 부분 가비지 컬렉션을 사용하면 SSR과 가비지 컬렉션 모두보다 쓰기 성능이 더 좋아질 수 있다. 부분 가비지 컬렉션은 가비지 컬렉션을 적용할 때 Inter-GC (Inter-Segment Garbage Collection) 와, Intra-GC (Intra-Segment Garbage Collection) 두 가 지 방식을 사용한다. Inter-GC은 기존 가비지 컬렉션과 마찬가지로 세그먼트 안에 남아있는 유효한 블록들을 콜 드 세그먼트, 즉 다른 세그먼트로 복사하는 것이다. 그림 4(b)는 Inter-GC을 사용하여 B6 블록을 콜드 세그먼트 로 복사함으로써 B 1~B 5 다섯 개 블록을 순차적으로 쓰 는 것을 보여준다. 하지만, F2FS에서는 유효한 블록들이 가비지 컬렉션에 의해 복사되어 기록되는 세그먼트가 프 리 세그먼트가 아니고 일부 유효한 블록들을 가진 더티 (b) Inter-Segment Garbage Collection (c) Intra-Segment Garbage Collection 그림 4 (a) SSR, (b) Inter-GC, (c) Intra-GC를 사용할 때 세그먼트의 상태 Fig. 4 States of segments using (a) SSR, (b) Inter-GC, (c) Intra-GC 세그먼트가 될 수도 있다. 그래서, 유효한 블록을 콜드 세그먼트에 복사하는 것보다 유효한 블록이 있는 세그먼 트에 복사할 때 쓰기 성능이 높아서 오버헤드가 더 적을 수 있다. 그림 4(c)는 Intra-GC을 사용하여 B 6 블록을 세그먼트 21에 복사함으로써 B 1~B 5 다섯 개 블록을 순 차적으로 쓸 수 있는 공간을 확보하는 것을 보여준다. 그 런데, Intra-GC은 그림 4(c)처럼 확보한 쓰기 공간에 유 효한 블록이 복사되어 Inter-GC에 비해 확보되는 쓰기 공간이 작아질 수 있다. 이점을 유효한 블록을 복사하는 오버헤드와 같이 고려하여 Inter-GC과 Intra-GC 중에 서 사용할 기법을 선택해야 한다. 가비지 컬렉션과 마찬가지로 부분 가비지 컬렉션을 적용한 세그먼트를 활용하기 위해서는 체크포인팅이 필 요하다. 그런데, 체크포인팅은 체크포인트 영역에 페이 지를 기록하는 쓰기 오버헤드가 발생한다. 그래서, 체크 포인팅의 오버헤드가 부분 가비지 컬렉션을 통해 얻는 이익보다 더 작은 경우에만 부분 가비지 컬렉션을 적용 해야 한다. 이때, 최대한 많은 세그먼트에 부분 가비지 컬렉션을 적용한 후 체크포인팅을 사용하면 체크포인팅 의 오버헤드를 상대적으로 줄일 수 있다. 그런데, 두 개 이상의 세그먼트에 미리 부분 가비지 컬렉션을 적용하 면, 세그먼트들을 다 사용하기 전에 백그라운드 가비지
부분 가비지 컬렉션을 이용한 로그 구조 파일시스템의 쓰기 성능 개선 1031 컬렉션으로 프리 세그먼트가 확보될 수 있다. 그렇다면 사용되지 않은 세그먼트들은 불필요한 오버헤드가 되므 로, 이로인해 쓰기 성능이 SSR을 사용하는 것보다 감소 할 수 있다. 그래서, 부분 가비지 컬렉션은 기존 가비지 컬렉션처럼 하나의 세그먼트 단위로 체크포인팅을 사용 하는 방식을 사용한다. 4.3 부분 가비지 컬렉션의 쓰기 성능 비교 부분 가비지 컬렉션을 사용하기 위해서는 각 연속된 블록들마다 SSR, Inter-GC, Intra-GC의 쓰기 성능을 비교해야 한다. 그래서, 쓰기 성능이 가장 좋은 기법을 선택하여 사용할 수 있어야한다. 쓰기 성능을 비교하기 위해서 각 기법을 사용했을 때 쓰기 요청을 처리하는 시간을 계산한다. 그리고, 가장 작은 쓰기 시간을 가지 는 기법을 선택하여 사용한다. 쓰기 요청을 처리하는 시간은 다음과 같이 계산할 수 있다. 먼저, 사용하는 저장장치에서 읽기, 쓰기 요청 크 기에 따른 성능을 측정한다, 그리고, 이를 바탕으로 저 장장치에 대한 읽기 요청의 크기가 n개의 블록일 때 읽 기 요청을 처리하는 시간 T read(n)과 쓰기 요청의 크기가 n개의 블록일 때 쓰기 요청을 처리하는 시간 T write(n) 을 구할 수 있다. 그리고, 할당받은 더티 세그먼트에서 H left, H right 크기의 빈 공간 사이의 연속된 유효한 블록 들이 B valid이고 B valid 블록들이 있는 세그먼트와 콜드 세그먼트의 빈 공간의 평균 크기를 H intra avg, H inter avg 라 고 하면, SSR, Inter-GC, Intra-GC을 사용하여 H left + H right 크기의 쓰기 요청을 처리하는 시간 T SSR, T Inter-GC, T Intra-GC 을 다음과 같이 모델링할 수 있다. T SSR(H left, H right)=t write(h left)+t write(h right) T Inter-GC(H left, H right, B valid, H inter avg ) = ((H left +H right)/ (H left +H right +B valid)) T write(h left +H right +B valid)+ T read(b valid)+(b valid /H inter avg ) T write(h inter avg ) T Intra-GC(H left,h right,b valid,h intra avg )=T write(h left +H right)+ T read(b valid)+(b valid /H intra avg ) T write(h intra avg ) SSR을 사용하면 H left개의 블록과 H right개의 블록으로 쓰기 요청이 나누어진다. 따라서, T SSR은 H left개의 쓰기 요청을 처리하는 시간 T write(h left)와 H right개의 쓰기 요청 을 처리하는 시간 T write(h right) 의 합으로 계산할 수 있다. Inter-GC을 사용하여 B valid개의 블록들을 복사하고 무 효화하면, H left +B valid +H right 크기의 쓰기 공간을 확보 할 수 있다. 따라서, H left +H right개의 쓰기 요청을 순차적 으로 처리할 수 있다. 로그 구조 파일 시스템의 특성상 쓰기 요청은 H left +B valid +H right개의 블록 크기까지 합쳐 지기 때문에 H left +B valid +H right크기의 쓰기 요청을 처리 하는 시간에서 H left +H right개의 쓰기 요청이 차지하는 시 간은 ((H left +H right) /(H left +H right +B valid)) T write(h left + H right +B valid)으로 계산할 수 있다. T Inter-GC 값은 여기에 B valid개의 유효한 블록들을 복사하는 오버헤드를 더하면 된다. 복사 오버헤드는 B valid개의 블록을 읽는 시간 T read(b valid)와 콜드 세그먼트에 쓰는 시간(B valid /H inter avg ) T write(h inter avg )의 합으로 구할 수 있다. T Intra-GC도 Inter-GC과 같은 방식으로 계산할 수 있 다. 그런데, Intra-GC을 사용하면 B valid개의 유효한 블록 들을 자기 세그먼트에 복사하므로 블록들이 확보한 쓰기 공간이 줄어서 H left +H right개의 쓰기 공간만 확보할 수 있다. 그래서, H left +H right개의 쓰기 요청을 순차적으로 처리하는 시간은 T write(h left +H right)으로 계산할 수 있다. inter 복사 오버헤드는 Inter-GC에서H avg 대신 H intra avg 를 사용한다는 것만 다르다. 그림 4(a)를 예로 들면 H left, B valid, H right값이 각각 3, 1, 3인 환경에서 SSR을 사용할 경우 쓰기 요청이 3개의 블록과 3개의 블록으로 나누어지므로 2 T write(3)시간이 소모된다. Inter-GC을 사용한다면 그림 4의 (b)처럼 7개 블록을 쓸 수 있는 쓰기 공간을 확보할 수 있다. 여기에 6개의 블록을 순차적으로 쓴다면 (6/7) T write(7) 시간이 소모된다. 그리고 1개의 유효한 블록을 콜드 세그먼트로 복사하는 오버헤드로 T read(1)와 (1/H inter avg ) T write(h inter avg ) 시간이 소모되게 된다. Intra-GC을 사용하면 그림 3의 (c)처럼 6개의 블록을 쓸 수 있는 쓰기 공간을 확보하여 T write(6)시간이 소모된다. 이때 복사 오버헤드는 T read(1) 와 (1/H intra avg ) T write(h intra avg )로 계산할 수 있다. 그리고, 저장장치마다 다른 T read와 T write, 그리고 파일시스템의 상태에 따른 H inter avg 와 H intra avg 에 따라 가장 쓰기 시간이 적은 기법이 선택되어 사용된다. 세그먼트 안의 남아있는 연속된 블록들 마다, Inter- GC이 사용되었다면 T Inter-GC -T SSR만큼 쓰기 시간이 감 소하고, Intra-GC이 사용되었다면 T Intra-GC -T SSR만큼 쓰기 시간이 감소한다. 세그먼트 안에서 가비지 컬렉션 이 적용된 블록들에 대하여 감소된 쓰기 시간을 모두 더 함으로써 부분 가비지 컬렉션을 적용했을 때 감소하는 쓰기 시간을 게산할 수 있다. 이 값을 체크포인팅에 소모 되는 시간 T Check와 비교하여, T Check값이 더 큰 경우에는 체크포인팅의 오버헤드로 인해 쓰기 성능이 부분 가비지 컬렉션을 적용하지 않았을 때보다 감소하므로 부분 가비 지 컬렉션을 사용하지 않는다. T Check값은 사용하는 저장 장치의T write을 이용하여 체크포인팅을 할 때 기록하는 메타 데이터의 쓰기 시간을 계산함으로써 구할 수 있다. 5. 실험 결과와 분석 5.1 실험 환경 실험은 안드로이드 4.2.2, 리눅스 커널 3.4.5 버전의
1032 정보과학회논문지 제41권 제12호(2014. 12) 그림 5 쓰기 요청 크기에 따른 쓰기 성능 Fig. 5 Write performance by write request size 쿼드코어, 2GB RAM을 가지는 안드로이드 모바일폰에 서 진행하였으며, 총 세 개의 플래시 저장장치, 클래스 2 SD 카드 A, 클래스 10 SD 카드 B와 C를 각각 장착 하여 실험하였다. 각 SD 카드는 서로 다른 성능을 가지 고 있으며, 그림 5의 그래프에서 저장장치별 임의 쓰기 크기당 쓰기 성능을 확인할 수 있다. 플래시 저장장치의 특성에 따라 임의 쓰기 성능과 순차 쓰기 성능의 차이 가 크므로, 로그 구조 파일시스템을 사용하기 적합한 저 장장치이다. 부분 가비지 컬렉션은 F2FS를 기반으로 구현되었다. 그래서, 부분 가비지 컬렉션의 쓰기 성능을 비교하기 위 해서 F2FS에서 SSR모드로 쓰기가 시작되기 전까지 저 장장치를 채운 후 쓰기 성능을 비교하였다. 이때 실험 환경을 설정하기 위해서 tiobench[13]를 사용하였다. 저 장장치에 웜 데이터와 콜드 데이터를 써서 저장장치를 채우는데, 웜 데이터의 유효한 블록 비율과 콜드 데이터 의 유효한 블록 비율을 변경하면서 SSR을 사용하기 시 작할 때 쓰기 환경을 다르게 하여 실험하였다. 웜 데이 터의 경우 유효한 블록 비율을 30%, 50%, 70% 세 가 지로 구분하고, 콜드 데이터의 경우 유효한 블록 비율을 0%와 70% 두 가지로 구분하여 실험하였다. F2FS에서 는 가비지 컬렉션을 할 때 콜드 세그먼트에 유효한 블 록들을 복사하므로, 콜드 데이터가 적혀있지 않은 0%에 서는 기존 로그 구조 파일 시스템과 같이 프리 세그먼 트에 가비지 컬렉션을 하게 되지만, 70%에서는 더티 세 그먼트에 가비지 컬렉션을 하게 된다. 5.2 실험 결과 실험은 tiobench를 사용해서 앞서 설명한 실험 환경 에 같은 크기의 순차 쓰기를 했을 때 SSR, 가비지 컬 렉션, 부분 가비지 컬렉션의 쓰기 성능을 측정하였다. 로그 구조 파일 시스템의 특성상 임의 쓰기와 순차 쓰 기의 차이 없이 쓰기 요청들을 모아서 처리하므로, 더티 세그먼트를 채우는 쓰기 성능은 모두 같다. (a) Write Performance of PGC and GC normalized to SSR (b) Write Ratio 그림 6 SSR, 가비지 컬렉션, 부분 가비지 컬렉션 비교 Fig. 6 Comparison on SSR, Garbage Collection, Partial Garbage Collection
부분 가비지 컬렉션을 이용한 로그 구조 파일시스템의 쓰기 성능 개선 1033 그림 6은 SSR, 가비지 컬렉션, 부분 가비지 컬렉션의 실험 결과를 비교한 것이다. 실험 결과는 쓰기 성능 그 래프 (a)와 부분 가비지 컬렉션에서 각 기법의 사용 비 율 그래프 (b)로 정리되었다. (a) 그래프는 부분 가비지 컬렉션의 쓰기 성능과, SSR을 사용하지 않고 가비지 컬 렉션을 사용했을 때 쓰기 성능을, 각 실험 환경에서 기 존 기법인 SSR을 사용한 쓰기 성능에 정규화한 그래프 이다. 부분 가비지 컬렉션을 적용하여 SSR의 쓰기 성능 과 가비지 컬렉션의 쓰기 성능보다 같거나 좋은 성능을 보여주고 있다. (b) 그래프는 부분 가비지 컬렉션이 사 용되었을 때 Inter-GC, Intra-GC, SSR을 사용한 비율 을 나타낸 그래프이다. SD 카드 A, B, C 순으로 임의 쓰기별 성능 차이가 크므로, SD 카드 C에서 부분 가비 지 컬렉션을 사용했을 때 성능 증가율이 가장 크고 SSR이 거의 사용되지 않았다. 반면, 임의 쓰기별 성능 차이가 가장 작은 SD 카드 A에서는 부분 가비지 컬렉 션을 사용했을 때 거의 SSR만이 사용되며 쓰기 성능에 변화가 없는 것을 보여주고 있다. 실험 환경은 크게 두 가지로 구분할 수 있다. 하나는 콜드 세그먼트의 유효한 블록 비율이 0%로 프리 세그 먼트인 경우고, 다른 하나는 70%로 더티 세그먼트인 경 우다. 두 환경에서 가비지 컬렉션의 오버헤드가 크게 차 이나기 때문에, 부분 가비지 컬렉션을 사용했을 때 대비 되는 결과를 보여준다. 5.2.1 프리 콜드 세그먼트 콜드가 프리 세그먼트일 때는 가비지 컬렉션을 사용 하여 유효한 블록들을 복사할 때 순차 쓰기를 하게 되 므로 오버헤드가 작다. 따라서, 부분 가비지 컬렉션을 사용했을 때 거의 Inter-GC을 사용하여 가비지 컬렉션 을 하게 된다. 가비지 컬렉션을 사용하면 더티 세그먼트 를 프리 세그먼트로 만든 뒤 순차 쓰기를 하므로 모든 유효한 블록 비율에서 같은 순차 쓰기 성능을 갖는다. 그런데, 유효한 블록 비율이 높을수록 임의 쓰기 성능이 감소하므로 SSR을 사용할 때 쓰기 성능이 낮다. 따라 서, 웜 데이터의 유효한 블록 비율이 높을수록 성능 증 가율이 커지게 된다. 유효한 블록 비율이 높을 때는 유 효한 블록들이 많으므로 가비지 컬렉션을 할 때 오버헤 드도 증가한다. 하지만, 복사되는 블록들을 프리 콜드 세그먼트에 순차적으로 쓰게 되므로, 쓰기 성능이 증가 하는 것에 비해 오버헤드가 상대적으로 작아져서 성능 증가율에 크게 영향을 끼치지 않는다. SD 카드 A에서 웜 데이터의 유효한 블록 비율이 가 장 낮을 때만 쓰기 성능이 증가하는 것보다 체크포인팅 의 오버헤드가 더 크므로 부분 가비지 컬렉션이 사용되 지 않고 SSR이 사용되었다. 5.2.2 더티 콜드 세그먼트 콜드가 더티 세그먼트일 경우에는 가비지 컬렉션을 사 용하였을 때 유효한 블록들을 임의 쓰기를 하게 되므로 오버헤드가 커진다. 그리고, 콜드 세그먼트의 유효한 블 록의 비율이 70%로 웜 데이터의 유효한 블록 비율이 가 장 높을 때와 같으므로, Inter-GC이 사용되지 않고 Intra-GC이 사용되는 것을 보여준다. 또한, Intra-GC을 사용해도 임의 쓰기를 하기 때문에, 이전 실험 결과에서 거의 Inter-GC이 사용되었던 것과 달리 SSR도 일정 비 율 사용되는 것을 보여준다. Intra-GC을 사용하면 자기 세그먼트에 유효한 블록들을 복사하므로, 더티 세그먼트 에 임의 쓰기를 하게 되어 오버헤드의 비중이 커지게 된 다. 그래서, 웜 데이터의 유효한 블록 비율이 낮을수록 오버헤드가 작아져서 성능 증가율이 증가한다. 또한, 웜 데이터의 유효한 블록 비율이 작으면 Intra-GC의 사용 비율이 증가하므로 쓰기 성능이 더 증가하게 된다. 웜 데이터의 유효한 블록 비율이 콜드 데이터와 같은 70%일 때는 Intra-GC과 함께 Inter-GC도 사용되는 것 을 보여준다. 하지만, SD 카드 B, C에서는 그때 부분 가비지 컬렉션이 사용되지 않으므로, SD 카드 C에서만 확인할 수 있다. 콜드가 프리 세그먼트일 때에 비해 오버헤드가 크기 때문에 성능 증가율이 더 낮다. 따라서, 체크포인팅의 오버헤드가 더 커서 부분가비지 컬렉션을 사용해도 SSR만이 사용되는 환경이 많다. 6. 결 론 본 논문에서는 SSR과 가비지 컬렉션 중에서 더 좋은 기법을 선택적으로 사용함으로써 두 기법보다 쓰기 성 능을 증가시킬 수 있는 부분 가비지 컬렉션 기법을 제 시한다. 기존 기법인 SSR과 본 논문에서 제시하는 Inter-GC, Intra-GC 중에서 가장 좋은 쓰기 성능을 가 지는 기법을 사용함으로써, SSR만을 사용하는 기존 기 법에 비해 쓰기 성능을 최대 두배 이상 증가시켰다. References [1] M. Rosenblum and J. Ousterhout, "The design and implementation of a log-structured file system," ACM Transactions on Computer Systems, Vol. 10, pp. 26-52, 1992. [2] Aleph One. (2002). "YAFFS2: Yet Another Flash File System" [Online]. Available: http://www.yaffs.net/ (downloaded 2014, Jun. 30) [3] D. Woodhouse. (2001). "JFFS2: The journaling flash file system, version 2" [Online]. Available: http:// sources.redhat.com/jffs2/ (downloaded 2014, Jun. 30) [4] T. Gleixner, et al. (2006). "UBIFS: Unsorted block images file system" [Online]. Available: http://www. linuxmtd.infradead.org/ (downloaded 2014, Jun. 30)
1034 정보과학회논문지 제41권 제12호(2014. 12) [5] J. Kang, et al., "A multi-channel architecture for high-performance NAND flash-based storage system," Journal of Systems Architecture, Vol. 53, pp. 644-658, 2007. [6] Y. Oh, et al., "Optimizations of LFS with slack space recycling and lazy indirect block update," ACM Proceedings of the 3rd Annual Haifa Experimental Systems Conference, pp. 2, 2010. [7] J. Kim. (2012). "F2FS: introduce flash-friendly file system" [Online]. Available: http://lwn.net/articles/ 518988 (downloaded 2014, Jun. 30) [8] M. Wu, W. Zwaenepoel, "envy: A non-volatile, main memory storage system," ACM SigPlan Notices, Vol. 29, pp. 86-97, 1994. [9] K. Atsuo, et al., "A flash-memory based file system," USENIX Annual Technical Conference, pp. 155-164, 1995. [10] W. Jun, H. Yiming, "WOLF-A novel reordering write buffer to boost the performance of log-structured file systems," USENIX Conference on File and Storage Technologies (FAST), pp. 47-60, 2002. [11] C. Min, et al., "SFS: Random write considered harmful in solid state drives," USENIX Conference on File and Storage Technologies (FAST), pp. 12, 2012. [12] W. John, et al., "The HP AutoRAID hierarchical storage system," ACM Transactions on Computer Systems, Vol. 14, pp. 108-136, 1996. [13] M. Kuoppala. (2004). "Tiobench-Threaded I/O bench for linux" [Online]. Available: http://directory.fsf.org/ tiobench.html (downloaded 2014, Jun. 30) 곽 현 호 2014년 성균관대학교 컴퓨터공학과(학사) 2014년~현재 성균관대학교 전자전기컴 퓨터공학과 석박통합과정. 관심분야는 임 베디드 시스템, 파일시스템, 플래시 메모 리 등 신 동 군 1994년 서울대학교 계산통계학과(학사) 2000년 서울대학교 전산과학과(석사). 2004 년 서울대학교 컴퓨터공학부(박사). 2004 년~2007년 삼성전자 소프트웨어 센터 책임연구원 2007년~현재 성균관대학교 정보통신대학 부교수. 관심분야는 임베디 드 시스템, 실시간 시스템, 저전력 시스템 등