저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할

Transcription

1 저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할수없습니다. 변경금지. 귀하는이저작물을개작, 변형또는가공할수없습니다. 귀하는, 이저작물의재이용이나배포의경우, 이저작물에적용된이용허락조건을명확하게나타내어야합니다. 저작권자로부터별도의허가를받으면이러한조건들은적용되지않습니다. 저작권법에따른이용자의권리는위의내용에의하여영향을받지않습니다. 이것은이용허락규약 (Legal Code) 을이해하기쉽게요약한것입니다. Disclaimer

2 공학석사학위논문 낸드 플래시 기반 저장 장치의 수명 향상을 위한 고효율 데이터 압축 계층의 설계 2016 년 2 월 서울대학교 대학원 컴퓨터 공학부 전호윤

3 공학석사학위논문 낸드 플래시 기반 저장 장치의 수명 향상을 위한 고효율 데이터 압축 계층의 설계 2016 년 2 월 서울대학교 대학원 컴퓨터 공학부 전호윤

4 낸드 플래시 기반 저장 장치의 수명 향상을 위한 고효율 데이터 압축 계층의 설계 지도교수 김 지 홍 이 논문을 공학석사학위논문으로 제출함 2016 년 2 월 서울대학교 대학원 컴퓨터 공학부 전호윤 전호윤의 석사학위논문을 인준함 2016 년 2 월 위 원 장 부위원장 위 원 민상렬 김지홍 이재진 (인) (인) (인)

5 요약 낸드 플래시 메모리는 공정 개선을 통한 고집적화와 multi-level cell 기술의 발 전으로 인해 가격 대 용량비가 개선되면서 하드 디스크를 대체할 수 있는 차세대 저장장치로 각광받고 있다. 그러나 동시에 이러한 발전이 단위 셀당 P/E 사이클 의 감소를 수반하면서, 낸드 플래시의 수명을 관리하기 위한 소프트웨어적 기법의 필요성이 커지고 있다. 본 논문에서는 이러한 기법들 중 하드웨어 데이터 압축 모 듈을 활용한 개선 방법에 주목하고자 한다. 데이터 압축 모듈의 도움으로 장치로 전달되는 쓰기 요청의 양을 감소시킨다면 성능 및 수명 개선을 기대할 수 있지만 필연적으로 발생하는 내부 단편화 문제와 함께, 읽기 위주의 workload에서 발생할 수 있는 비효율적인 읽기 연산으로 인하여 특정한 workload에서는 읽기 성능의 감소를 불러오는 경우가 발생할 수 있다. 이에 본 논문에서는 추가적인 쓰기 버퍼를 활용한 지연된 쓰기(delayed batch write)와 chunk단위로 관리되는 읽기 버퍼를 도입하여 이러한 문제를 해결한다. 낸드 플래시 저장장치 시뮬레이터에 구현하여 실제 환경에서 수집한 트레이스를 바탕으로 실험한 결과 기존 기법 대비 평균 32%의 추가적인 공간을 확보할 수 있 었으며, 읽기 위주의 트레이스를 대상으로 실험하였을 때 평균 45% 읽기 연산의 횟수를 줄일 수 있었다. 주요어: 낸드, 플래시, SSD, 압축, 단편화, Read buffer 학번: i

6 목차 요약 i 목차 ii 그림 목차 iv 표 목차 vi 제 1 장 서론 연구 배경 연구 동기 연구의 기여 제 2 장 기존 압축 방식의 문제점 내부 단편화 문제 읽기 성능의 저하 Garbage collection의 비효율성 제 3 장 최적화된 데이터 압축 계층의 설계 내부 단편화 문제 해결을 위한 chunk 이어 쓰기 압축이 고려된 읽기 버퍼를 통한 읽기 연산 성능 향상 압축을 고려한 garbage collection 최적화 ii

7 제 4 장실험및분석 실험환경 실험결과 제 5 장결론 결론 향후연구 참고문헌 39 Abstract 40 iii

8 그림 목차 그림 1.1 공정별 삭제 횟수[1] 그림 1.2 낸드 플래시 압축 적용시 발생하는 내부 단편화 문제 그림 1.3 Chunk 단위 압축을 통한 내부 단편화 감소 그림 1.4 압축 계층이 추가된 낸드 플래시 메모리 기반 저장장치의 구조 6 그림 1.5 Ubuntu VM 파일의 내부 단편화 그림 2.1 내부 단편화 그림 2.2 Workload별 내부 단편화 정도 그림 2.3 순차적 읽기에 대한 읽기 요청 감소 그림 2.4 Chunk 이어쓰기로 인한 읽기 증폭 현상 그림 2.5 Partially invalid chunk의 문제 그림 3.1 쓰기 버퍼를 이용한 chunk 이어쓰기 그림 3.2 Chunk table 구조 및 offset 추가 그림 3.3 Sub page단위 offset 관리 그림 페이지 이상의 크기로 압축된 chunk의 비효율성 그림 3.5 Compression-aware read buffer 그림 3.6 Greedy-Dual-Size 알고리즘 그림 3.7 Partially invalid chunk와 reclaim iv

9 그림 3.8 Partially invalid chunk로 인한 GC의 비효율성 그림 3.9 DEV workload의 압축률 지역성 그림 3.10 Partially invalid chunk와 reclaim 그림 4.1 내부 단편화를 제거했을 떄 확보되는 용량 그림 4.2 Chunk 이어쓰기로 인한 읽기 증폭 현상 그림 MB Compression-aware buffer 사용시 읽기 횟수 감소.. 31 그림 4.4 읽기 버퍼 내의 entry 개수 그림 4.5 Chunk 이어쓰기로 인한 GC 효율 증가 그림 4.6 GC 최적화를 통한 효율 증가 그림 4.7 Block 별 block density 분포 그림 4.8 optimized caftl을 사용한 수명 향상 v

10 표 목차 표 4.1 낸드 플래시 시뮬레이터 설정 표 4.2 실험에 사용한 workload 표 4.3 읽기 실험을 위한 trace 표 4.4 실험에 사용한 가공 workload vi

11 제 1 장 서론 1.1 연구 배경 낸드 플래시 메모리는 기계적 장치 없이 반도체로 이루어진 저장매체로써, 충 격, 진동, 온도에 대한 우수한 내구성과 빠른 랜덤 읽기 속도, 작은 폼 팩터 등 많은 장점을 가지고 있다. 특히 이러한 특성들을 활용하기 쉬운 모바일이나 높은 성능을 요구하는 I/O 캐시 등의 환경에서 폭넓게 활용된다. 이와 더불어 한 cell에 서 표현할 수 있는 정보의 수를 늘리는 MLC (multi-level cell), TLC (triple-level cell) 와 같은 기술의 등장으로 인해 단위 용량당 가격이 낮아지면서, 기존 저장 매체 시장의 대다수를 차지하고 있는 하드 디스크(HDD)의 영역까지 그 영향력을 넓히고 있다. 그림 1.1 공정별 삭제 횟수[1] 1

12 그러나 이와 같은 반도체 집적 기술의 발전은 내구성의 저하라는 단점을 함께 야기한다. 그림 1.1은 낸드 플래시 메모리의 공정이 발전하면서 단위 셀당 한계 삭 제 횟수(Program/Erase cycle)의 변화를 나타낸 그래프이다. 그림 1.1을 통하여 확인할 수 있듯이, 집적도의 증가는 셀당 한계 삭제 횟수의 감소를 수반하며 이는 낸드 플래시 메모리로 구성된 디바이스 전체의 수명에 큰 영향을 끼친다. 이렇듯 줄어든 물리적 내구성 감소를 보완하기 위하여 다양한 소프트웨어적 기법들이 제시되었다. 이들은 주로 FTL (Flash Translation Layer)에서 wearleveling, garbage collection, deduplication 등의 기법들을 통하여 쓰기/삭제 요청 이 특정 셀에 편중되는 현상을 완화시키고 중복된 쓰기 데이터들을 제거함으로써 디바이스의 성능과 수명을 향상시킨다. 그러나 구현 및 적용 과정에 소모되는 자원 및 추가적인 쓰기/삭제 요청의 발생으로 인해, 모든 경우에 성능 향상을 담보하는 해법으로 받아들여지지는 않는다 [2] [3]. 데이터 압축을 활용한 낸드 플래시 메모리의 내구성 개선은 소프트웨어를 활 용하여 내구성을 향상시키기 위한 시도 중 하나이다. 별도의 압축 모듈을 호스트, 또는 장치단에 구현하여 쓰여지는 데이터를 압축하여 보관함으로써 장치에 가해 지는 쓰기 요청의 양을 획기적으로 줄일 수 있다. 특히, BlueZip[5]에서 소개한 것과 같이 별도의 하드웨어 압축 모듈을 활용하는 경우, 매우 빠르게 압축 연산을 수행할 수 있기 떄문에 적은 쓰기 연산은 곧 빠른 쓰기 성능으로 이어진다. 실제 일 상생활에서 사용하는 데이터의 많은 부분이 반복되는 패턴을 가지고 있기 떄문에, 이러한 압축 알고리즘의 효용성을 담보할 수 있다. 그러나 고정된 페이지(page) 단위로 수행되는 낸드 플래시 메모리의 I/O 처리 과정에서 압축 계층을 통해 인위적으로 데이터의 크기를 변화시킬 경우, 내부 단편 2

13 화(internal fragmentation) 및 읽기 성능 감소와 같이 기존 시스템에서 고려되지 않았던 문제가 발생한다. 본 논문에서는 이러한 문제가 발생하는 원인을 분석하고, FTL에서의 추가적인 관리 기법을 통해 개선함으로써 보다 효율적인 데이터 압축 계층을 구현하는 것을 그 목표로 한다. 3

14 1.2 연구 동기 낸드 플래시 메모리에 기반한 저장장치에 압축을 적용하는 아이디어는 이미 여러 연구자들에 의해 그 가능성을 평가받아 왔다. 압축을 통해 장치로 전달되는 쓰기 요청의 양을 줄인다면, 쓰기 및 블록 삭제 횟수 감소를 통한 수명 향상은 물론, 하드웨어 가속 장치 등 압축 비용을 최소화하는 방법과 함께 쓰기 요청의 효율마저 상승하는 결과를 기대할 수 있다. 그러나 실제 압축을 활용하여 수명 향상을 꾀할 경우, 페이지 단위 I/O의 크기 변화로 인한 내부 단편화 문제를 반드시 해결해야 한다. 그림 1.2 에서 내부 단편화 문제를 확인할 수 있다. 실제 압축을 통해 페이지 기록되는 양을 감소시켰더라도, 항상 페이지 단위로 I/O를 수행하는 낸드 플래시 메모리의 제약으로 인하여 실제 쓰기 요청되는 페이지 수를 감소시키지 못하게 된다. 이 때, 압축으로 인해 데이 터가 기록되지 않는 공간의 경우 다른 데이터가 기록되지 못하고 버려지며, 이를 내부 단편화 (internal fragmentation)라고 정의할 수 있다. 그림 1.2 낸드 플래시 압축 적용시 발생하는 내부 단편화 문제 내부 단편화 문제를 해결하기 위해 기존 BlueZip[5] 연구에서는 chunk 단위로 데이터를 모아 압축하는 방법을 제시하였다. 그림 1.3 에서 확인할 수 있듯이, 한 페이지를 그대로 압축하지 않고 몇 개의 페이지 단위를 chunk로 모아 함께 압축한 4

15 다음 기록함으로써 발생하는 내부 단편화를 최소화 할 수 있다. 그림 1.3 Chunk 단위 압축을 통한 내부 단편화 감소 그림 1.4는 이렇게 chunk 단위 압축 방식을 적용한 BlueZip의 구조를 도식화 한 것이다. 해당 논문에서는 호스트 또는 장치 내부가 아닌, 별도의 Compressor / Decompressor 하드웨어 모듈을 통해 쓰기/읽기 연산을 수행할 때 압축 및 압축 해제가 이루어짐을 가정하였다. 또한 하드웨어 모듈을 활용하여 실제 이러한 구 조를 구현하고 평가함으로써 chunk 단위 압축 및 하드웨어를 통한 가속이 충분히 효용성이 있음을 보이고 있다. 호스트에서 파일 시스템과 block I/O 계층을 거쳐서 쓰기 요청이 전달되면, 임시 쓰기 버퍼 영역에 데이터가 우선적으로 저장된다. 저장된 데이터는 내부 단 편화 감소 및 압축 효율 향상을 위해 4 페이지 단위로 구성된 chunk로 모아져 압축 모듈로 보내지며, 이들은 별도의 chunk address table mapping을 통해 chunk 단위 로 주소가 기록된 후 낸드 플래시 메모리에 쓰여진다. 이후 이미 압축되어 저장된 데이터를 읽기 위한 요청이 들어왔을 경우에는 chunk address table을 참조하여 5

16 해당 페이지가 포함된 chunk의 위치를 찾아낸 다음 압축 해제 모듈을 통해 chunk 째로 읽어낸 데이터가 임시 버퍼를 거쳐 호스트 영역으로 전달된다. 그림 1.4 압축 계층이 추가된 낸드 플래시 메모리 기반 저장장치의 구조 6

17 그러나 이렇듯 chunk를 사용하더라도 내부 단편화를 완전히 해결할 수 없다. 그림 1.5은 실험에서 샘플로 사용한 Ubuntu virtual machine 이미지 파일을 chunk 단위로 압축하여 관리할 때 발생하는 내부 단편화의 빈도를 나타낸 것이다. 4 KB 의 물리적 페이지를 가정하였으며, 4 KB중 내부 단편화 영역이 차지하는 크기에 따라 15개로 구간을 나눠 히스토그램을 표시하였다. 그림 1.5 Ubuntu VM 파일의 내부 단편화 그림 1.5에서는 수집된 전체 chunk중 50%이상의 영역에서 2KB 이상의 저장 공간이 낭비되고 있음을 확인할 수 있다. 특히 압축률이 매우 높아 하나의 물리 페이지보다 압축된 전체 chunk의 크기가 매우 작은 경우, 우수한 압축률로 인한 나머지 공간이 모두 내부 단편화로 처리되기 때문에 높은 압축률만큼의 이득을 얻을 수 없게 된다. 7

18 1.3 연구의 기여 논문에서는 낸드 플래시 메모리를 위한 기존의 데이터 압축 계층 발전시켜 내 부 단편화 문제를 획기적으로 감소시킬 수 있는 chunk 이어쓰기 기법을 통해 압축 효율을 높이고자 한다. 특히 기법을 구현하면서 발생할 수 있는 세 가지 문제에 초점을 맞추어, 쓰기 버퍼를 활용한 chunk 이어 쓰기와 압축을 고려한 읽기 버퍼 (compression-aware read buffer), 압축을 고려한 gc 대상 선정 알고리즘을 추가 함으로써 그 효용성을 높이고자 하였다. Chunk 이어 쓰기의 경우 추가적인 쓰기 버퍼 내에서 chunk들을 모아서 연속적으로 기록함으로써 내부 단편화를 근본적으 로 해결하는 방법이며, 압축을 고려한 읽기 버퍼의 경우 chunk단위로 읽기 버퍼를 관리하여 일반적인 읽기 버퍼보다 성능을 크게 개선시킨다. 압축을 고려한 gc 대 상 선정 알고리즘에서는 block 별로 서로 다른 압축률과 partially invalid chunk 를 고려한 압축 대상 선정을 통해 gc 효율을 증가시킨다. 논문의 구성은 다음과 같다. 1장에서는 데이터 압축을 이용한 낸드 플래시 성 능 개선의 의의와 적용 시의 문제점을 살펴본다. 2장에서 실제 본 논문이 구현한 지연된 쓰기 및 압축을 고려한 읽기 버퍼 기법을 설명하며, 3장에서 이를 실제 workload및 트레이스를 대상으로 적용하였을 때의 결과를 소개한다. 마지막 4장 에서는 결론과 함께 이후의 연구 방향에 대하여 언급할 것이다. 8

19 제 2 장 기존 압축 방식의 문제점 2.1 내부 단편화 문제 하드 디스크를 비롯한 대부분의 저장 장치는 공간적 지역성(spacial locality) 및 I/O 장치의 속도 문제 등으로 인하여, 바이트 단위가 아닌 블록(block) 또는 페이지(page)와 같이 보다 큰 단위로 I/O 명령을 수행한다. 이는 낸드 플래시 기 반 저장장치의 경우도 예외가 아니며, 반도체의 물리적 특성으로 인하여 플래시 메모리는 물리 페이지(일반적으로 4 KB, 8 KB 등) 단위로 I/O 요청을 수행한다. 그림 2.1 내부 단편화 이러한 환경에서 압축을 통한 데이터의 축약은 의도하지 않은 페이지 정렬상 의 불균형을 가져올 수 있다. 이를 완화하기 위해 BlueZip[5] 에서는 chunk 단위 압축을 도입하였지만, 이것 또한 내부 단편화를 완전히 해결하지 못한다. 그림 2.1 에서와 같이 압축률이 매우 높아 한 페이지보다 훨씬 적은 크기로 chunk가 압축되 거나, 압축 이후의 크기가 page 단위 경계와 일치하지 않아 많은 부분이 낭비되는 경우가 발생할 수 있다. 특히 압축률이 매우 높은 경우, 압축을 통한 효율을 극 9

20 대화 할 수 있음에도 불구하고 내부 단편화 현상 발생으로 인해 그 효용을 모두 발휘하지 못하게 된다. 본 실험에서 사용한 workload들을 4 페이지 단위 chunk를 사용한 압축을 사 용하여 압축한 뒤 내부 단편화 정도를 확인할 경우 그림 2.2와 같은 결과를 얻을 수 있다. Workload의 특성에 따라 조금씩 달라질 수 있지만, 평균 21%의 공간이 내부 단편화로 인해 낭비되고 있음을 확인할 수 있다. 그림 2.2 Workload별 내부 단편화 정도 10

21 2.2 읽기 성능의 저하 그림 2.3 순차적 읽기에 대한 읽기 요청 감소 Chunk 단위의 입/출력 연산을 수행할 경우 발생할 수 있는 또 다른 문제는 읽기 성능의 저하이다. 이미 압축된 chunk를 읽고 압축을 푸는 읽기 연산의 경우 압축이 적용되지 않은 FTL에 비해 응답 시간의 지연이 발생할 수 있다. 이는 chunk 를 구성하는 페이지를 읽어내기 위해 전체 chunk를 읽어낸 다음 압축을 해제하는 과정이 필수적이기 때문인데, 사실 이로 인한 성능 저하는 workload의 특성에 의해 그 정도가 크게 달라질 수 있다. 특히 그림 2.3와 같이 연속적으로 기록된 데이터 들에 대하여 순차 읽기 요청이 발생할 경우, 각각의 페이지를 하나 하나 읽는 대신 전체 chunk를 읽은 뒤 압축을 해제함으로써 오히려 읽기 요청의 수를 감소시킬 수 있다. 그림 2.4 Chunk 이어쓰기로 인한 읽기 증폭 현상 그러나 반대로 workload의 특성과 chunk를 구성에 따라 그림 2.4 와 같은 상황 11

22 이 자주 발생한다면 페이지 읽기 연산의 수가 크게 증가할 수 있으며, 이는 읽기가 중심이 되는 workload및 트레이스에서 발생할 확률이 높다. 특히 내부 단편화를 해결하기 위해 후술할 chunk 이어 쓰기 기법을 적용하였을 경우, 이러한 현상이 심해질 수 있으며, 이러한 문제는 특정 workload에서 큰 비효율성을 야기할 수 있기 때문에 낸드 플래시 메모리에서 데이터 압축 계층을 범용적으로 사용하는 데 장애가 될 수 있다. 12

23 2.3 Garbage collection의 비효율성 Chunk 단위 압축을 사용할 때 또 한가지 고려가 필요한 문제는 garbage collection 과정에서의 비효율성이다. 하나의 page의 valid, invalid 여부를 바로 판단할 수 있는 기존 페이지 단위 mapping에서와는 달리, chunk의 도입으로 인하여 chunk 전체가 invalid 되지 않는 이상 해당 page를 invalid로 볼 수 없게 된다. 그림 2.5는 이러한 partially invalid chunk를 표현한 그림이다. 그림 2.5 Partially invalid chunk의 문제 이렇게 partially invalidate 된 chunk들은 별도의 조치가 없는 이상 계속하 여 partially invalid 상태로 남아 있기 때문에, 읽기 및 garbage collection 수행 시 overhead로 작용할 수 있다. 따라서 chunk 단위 압축을 적용한 FTL에서는 partially invalid chunk를 모아 다시 재압축하는 reclaim 과정이 필수적이며, 이를 고려한 새로운 gc victim 선택 알고리즘의 필요성이 대두된다. 13

24 제 3 장 최적화된 데이터 압축 계층의 설계 3.1 내부 단편화 문제 해결을 위한 chunk 이어 쓰기 내부 단편화 현상은 압축이라는 별도의 처리 과정을 통해 이미 페이지 단위로 정렬된 데이터 크기를 바꾸면서 필연적으로 야기된다. 여러 개의 페이지를 묶은 chunk단위로 압축을 수행할 경우 단일 페이지를 압축했을 경우에 비해 내부 단편 화 정도를 줄일 수 있지만 단편화 문제를 완전히 해결할 수는 없다. 4개 page가 묶인 chunk의 압축률에 따라 여전히 내부 단편화 현상이 발생할 수 있으며, 압축 결과는 항상 올림 처리되어 페이지에 기록되어야 하기 떄문에 2.1 page 크기로 압축된 chunk는 3개 page에 기록된다. 그림 3.1 쓰기 버퍼를 이용한 chunk 이어쓰기 본 연구에서는 이를 해결하기 위해 별도의 쓰기 버퍼를 두고 페이지 크기에 맞는 chunk 이어 쓰기 기법을 사용한다. Chunk 이어 쓰기는 그림 3.1와 같이 먼저 14

25 압축된 데이터를 쓰기 버퍼에 저장하고, 연속된 chunk 쓰기가 들어왔을 때 그들을 연속적으로 기록한 다음 내보냄으로써 내부 단편화를 근본적으로 해결할 수 있다. 이 방법을 사용할 경우 하나의 물리적 페이지에 서로 다른 두 개의 chunk에 속한 데이터들이 혼재하는 섞인 페이지(mixed page)가 나타나게 된다. 이를 관리 하기 위해서는 기존의 chunk table에서 chunk를 구성하는 물리적인 페이지들에 대하여 offset을 추가로 기록해야 할 필요성이 있다. 실제 읽기 연산이나 garbage collection등으로 인하여 chunk를 읽어내야 할 경우에는 chunk table에 기록된 offset을 바탕으로, 필요한 페이지들을 모두 읽어낸 다음 그 중 일부만을 사용함으 로써 원하는 데이터를 가져올 수 있다. 그림 3.2 Chunk table 구조 및 offset 추가 그러나 실제 offset을 기록하기 위해서는 기존의 chunk table에 시작 page의 offset 및 끝 offset을 기록해야 하는 추가적인 overhead가 발생한다. 그림 3.2을 통해 이를 확인할 수 있다. 하나의 chunk는 같은 block안에 연속적으로 기록되기 때문에 start physical page 정보 및 size 만으로 chunk를 표현할 수 있다. 이 떄, 15

26 기존 메타 정보 저장을 위해 start physical page를 제외하고 1 byte의 정보만을 필요로 한 데 반해 (no valid pages, no physical pages 등은 최대 4 이므로 각각 2 bit로 표현가능), chunk 이어쓰기 적용으로 인해 추가적인 offset 저장의 필요성 이 생긴다. 4 KB 페이지를 가정하였을 때 특정 byte offset을 가리키기 위해서는 12 bit가 필요하며, 이는 총 2 * 12 = 24 bit = 3 byte의 추가 공간을 의미한다. Physical page number의 범위에 따라 다르지만 이는, 1.5 2배의 page table 추가 공간 확장이 필요하다. 이후 서술할 read buffer 등으로의 활용 가능성을 위해서도, 한정된 DRAM 공간을 이렇게 사용하는 것은 바람직하지 못하다. 그림 3.3 Sub page단위 offset 관리 이를 해결하기 위해 그림 3.3와 같이 sub page단위의 offset 관리를 도입하였다. 이는 페이지 내 전체 byte offset을 모두 표기하는 대신, 이를 sub page로 나누어 sub page index를 기록함으로써 약간의 내부 단편화를 발생하는 대가로 offset 저 장에 드는 용량을 크게 줄이는 방법이다. 실제 데이터를 바탕으로 실험하였을 때 16개의 sub page (4 KB 페이지의 경우 sub page당 256 byte)를 사용하였을 떄 16

27 90% 이상의 내부 단편화를 제거하면서 동시에 offset으로 인해 소모되는 공간을 1/3로 크게 감소시킬 수 있었다. 한 가지 추가적인 최적화를 적용할 수 있는 가능성은 chunk가 항상 4 page로 구성되어 있다는 사실이다. 이를 활용하여 압축 해제 모듈에서 항상 4 page의 고정 된 크기가 압축 해제되고 난 뒤 압축 해제 과정을 종료시킨다면 start offset 만을 저장하고 end offset 대신 4 page가 압축 해제될 때 까지 압축 해제를 수행하는 것 으로 대체가 가능하다. 단 이 경우 garbage collection 등에서 추가적인 overhead가 발생하게 되며, stream 형식으로 데이터를 받아들이는 하드웨어 압축 해제 모듈을 활용할 경우에는 압축 해제 시점을 어떻게 판단할 것이냐도 문제가 될 수 있으므로 국소적인 최적화 방법이라 할 수 있다. 그림 페이지 이상의 크기로 압축된 chunk의 비효율성 또한 실제 4 페이지 chunk를 대상으로 할 때, 이 방법을 적용한다면 압축이 완료된 후 그 크기가 3 페이지 이상인 데이터들은 그림 3.4와 같이 그 효용성을 상실하게 된다. 테이블 관리 등의 효용을 위해 압축 후 2 페이지 이하의 크기를 가지는 경우만 chunk단위로 관리하고 나머지 데이터는 기존처럼 페이지 단위로 기록해 줌으로써 압축으로 인해 발생할 수 있는 비효율성을 미연에 방지할 수 있다. 17

28 3.2 압축이 고려된 읽기 버퍼를 통한 읽기 연산 성능 향상 저장장치보다 읽기 및 쓰기 성능이 우수한 버퍼 또는 캐시 메모리를 사용하여 전체 시스템의 성능을 높이는 기법은 컴퓨터 과학에서 일반적으로 널리 사용된다. 실제 낸드 플래시 메모리 기반의 SSD 저장장치에서도 페이지 테이블 저장, I/O 연산의 성능 향상 등 다양한 목적을 위해 DRAM 등으로 구성된 버퍼 영역을 사용 한다. 특히, 현대의 빅 데이터 및 서버향 SSD와 같이여 읽기 연산 성능이 중요한 저장장치의 경우 읽기 버퍼를 위한 영역을 명시적으로 할당함으로써 성능을 향상 시킬 수 있다.이 때, 압축 계층이 적용된 FTL의 I/O가 기본적으로 chunk단위로 이루어지고 있음에 착안하면 기존의 LRU 방식 페이지 버퍼보다 높은 효율을 갖는 읽기 버퍼를 고안할 수 있다. 그림 3.5은 기존의 페이지 대신 chunk단위로 구성한 읽기 버퍼를 보여준다. 압축된 chunk단위로 항목들을 관리함으로써 기존 읽기 버퍼에 비해 훨씬 큰 용량 의 읽기 버퍼를 가지고 있을떄와 비슷한 성능을 기대할 수 있다. 비록 workload의 형태에 따라 차이가 있지만, 보다 많은 항목을 버퍼 내에 보관하여 cache miss를 줄이는 것은 평균 읽기 성능 향상으로 이어질 수 있다. 그림 3.5 Compression-aware read buffer 18

29 또한 이처럼 chunk단위로 버퍼 메모리를 관리할 경우, 각 데이터의 압축률에 따라 실제 버퍼에서 차지하는 크기는 조금씩 달라진다. 우리는 여기서 각 항목의 접근 빈도가 비슷할 경우, 보다 많은 항목을 버퍼 내에 유지할수록 cache miss를 회피하는 측면에서 유리하다는 사실에 주목할 필요가 있다. 즉, 고효율로 압축되어 적은 용량으로 많은 항목을 담고 있는 chunk가 있다면, 해당 chunk를 버퍼 안에 오래 유지하는 것이 성능에 유리하게 작용할 수 있다. 그림 3.6 Greedy-Dual-Size 알고리즘 본 논문에서는 이를 위해 Greedy-Dual-Size [6] 알고리즘에 착안하였다. 해당 알고리즘은 웹 환경에서 서로 다른 접근 시간을 가진 자원들의 캐시를 관리할 때 사 용되는 알고리즘으로, LRU (Least-recently Used)와 같은 최근 접근 여부와 함께 각 자원들을 가져오기 위해 필요한 소모 비용이 큰 항목들에 우선 순위를 부여한 다. 해당 알고리즘은 그림 3.6와 같이 각 항목의 cost를 기준으로 가장 작은 cost를 가진 항목을 쫓아내면서 해당 항목의 cost값을 전체 영역에서 빼는(decay) 방식으 로 동직한다. 버퍼 내에 위치한 항목에 대해 cache hit이 발생할 경우 해당 항목에 19

30 한해 원래의 cost를 회복시키도록 함으로써, 상대적으로 cost가 높은 항목들은 몇 번의 eviction이 일어나더라도 버퍼 내에 남아있을 수 있으며 자주 접근되는 항목 역시 항상 본인의 cost를 유지함으로써 두 경우 모두에게 우선 순위를 부여할 수 있다. Data: incoming read request p initialize L to 0; while process incoming request p do if p is in buffer then read the chunk C that containing p from buffer; set H(C) = L + valid pages(c)/size(c); else read the chunk C that containing p; if there is not enough room for C then Let L be the minimum H(D) over all chunks D in buffer; Evict q such that H(D) = L; Bring p into the buffer; Set H(D) = L + valid pages(d)/size(d); else end end Algorithm 1: Greedy-Dual-Size 알고리즘 알고리즘 1은 압축을 고려한 compression-aware read buffer 구현 시 사용한 Greedy-Dual-Size 알고리즘을 의사 코드로 표현한 것이다. 코드에서 확인할 수 있듯이 각 chunk가 가지고 있는 valid 페이지 개수를 chunk의 크기로 나눈 값이 20

31 metric으로 사용된다. 이는 chunk에 포함 된 valid page의 개수가 많을수록, 또한 압축된 chunk의 크기가 작을수록 우선 순위를 부여하여 buffer에 오래 남아있는 효과를 가져온다. 알고리즘의 최적화를 위해 다음과 같은 기법을 사용하여 수행 시간을 감소시켰 다. 원래 그림 3.6와 같이 개념적으로는 전체 entry에서 가장 적은 cost에 해당하는 값을 빼는 방식이지만, 이 방법을 그대로 적용할 경우 매 eviction 마다 O(N)에 해당하는 탐색 및 업데이트 작업을 수행함으로 인해 알고리즘의 성능이 크게 저하 될 수 있다. 이를 회피하기 위해서는 가장 적은 cost를 빼는 대신, 새로운 entry가 삽입될 때, 해당 entry의 그때까지의 가장 작은 cost 값 L만큼의 가중치를 더해 삽 입하여 inflation 효과를 줌으로써 전체 buffer의 priority 측면에서 동일한 효율을 거둘 수 있다. 21

32 3.3 압축을 고려한 garbage collection 최적화 압축된 chunk 형태로 데이터를 관리하게 되면서 발생할 수 있는 또 하나의 문 제는 chunk를 구성하고 있는 일부 page만이 invalid되는 partial invalid 현상이다. 특히 이렇게 partially invalid chunk들의 경우에는 chunk 관리로 인한 overhead 는 계속 발생함에도 불구하고 단위 용량당 유효한 데이터 크기가 작은 채로 계속 유지될 수 있기 때문에 garbage collection 발생 시마다 재 압축을 통해 정리해주는 과정이 필요하다. 그림 3.7는 이러한 과정을 나타낸 모식도이다. 그림 3.7 Partially invalid chunk와 reclaim 그러나 종래의 invalid page 개수만을 고려하는 garbage collection 기법의 경우 이러한 partially invalid chunk로 인한 영향을 제대로 고려하지 못하는 경우가 발 생 할 수 있다. 그림 3.8는 실제 4개의 page를 가지는 block을 가정하였을 때 발생할 수 있는 문제점을 나타낸 모식도이다. 이 그림에서, partially invalid chunk로 인해 오른쪽 block은 valid page가 3개로 나타나 왼쪽보다 GC 효율이 낮아 보이지만, 실제 압축 reclaim 과정을 거쳤을 때 얻을 수 있는 free page의 개수가 왼쪽 block 보다 많음을 확인할 수 있다. 이는 기존 valid page만을 고려하던 victim selection 22

33 방법에서는 chunk의 압축된 정도 및 chunk가 소유하고 있는 logical valid page에 대한 고려가 전혀 되어 있지 않기 때문이라 분석할 수 있다. 그림 3.8 Partially invalid chunk로 인한 GC의 비효율성 위와 같이 logical valid page를 기준으로 reclaim작업이 발생한 이후 free page 의 개수를 예측하기 위해서는 현재 block에 위치한 logical page들이 재 압축 과정 을 거치고 난 뒤 어느 정도의 압축률로 physical page를 차지할지에 관한 예측이 필요하다. 이러한 예측은 순수히 workload에 의존적이며, 정확한 예측이 어렵기 때문에 어느 정도 휴리스틱한 방법을 사용해야 할 필요가 있다. 23

34 그림 3.9 DEV workload의 압축률 지역성 다양한 샘플 데이터들을 대상으로 테스트해 본 결과 압축률에도 어느 정도 지역 성을 기대할 수 있음을 가정할 수 있다. 그림 3.9 처럼 시간축 요청 순서별로 chunk 압축률을 표시하였을 때, 압축이 잘 되지 않는 (압축률이 1에 가까운) 요청들은 연 속적으로 들어오고, 압축률이 높은 데이터들 역시 어느 정도 연속성을 보이고 있다. 이는 데이터의 압축률이 데이터 패턴, 형태, 특성에 따라 비슷한 경향성을 보이기 때문이며, 압축이 잘 되지 않는 암호화, 압축된 데이터들 역시 랜덤하게 입력되기 보다 특정 명령에 의해 비슷한 데이터들이 같이 요청되기 떄문으로 풀이된다. 24

35 그림 3.10 Partially invalid chunk와 reclaim 그림 3.9의 결과를 바탕으로 같은 block 안에 위치한 chunk들의 압축률이 압축 률의 지역성으로 인해 비슷하다고 가정하였을 때 그림 3.10과 같은 식으로 reclaim 이후의 free page 개수를 추정할 수 있다. 이는 실제 압축된 chunk를 reclaim할 때 결과 chunk가 기존의 chunk가 가지고 있던 압축률과 흡사할 것이라는 가정에서 출발하며, 이를 이용하여 단순히 valid page 개수만을 고려하는 방법에 비해 보다 정확한 free page 개수를 추정할 수 있다. 25

36 제 4 장 실험 및 분석 4.1 실험 환경 본 연구에서는 실험을 위해 FlashBench [4]에 기반한 시뮬레이션 환경을 활 용하였다. 본 논문에서는 BlueZip [5]에서와 같이 하드웨어 압축 모듈이 존재하는 상황을 가정하고, 여기에 지연된 쓰기 및 압축을 고려한 읽기 버퍼 기능을 추가하여 그 성능을 평가하였다. 압축 알고리즘의 경우, 구현의 편의성 및 복잡성을 고려하여 BlueZip [5]에서 사용하였던 lzrw3 알고리즘을 사용하였으며, 블록 당 64 페이지, 칩 당 128개 블록, 총 32개의 칩 및 4 KB 페이지 크기 설정을 사용하였다. 칩 개수 32 칩 당 블록 개수 128 블록 당 페이지 수 64 페이지 크기 4 KB 표 4.1 낸드 플래시 시뮬레이터 설정 26

37 Trace 총 I/O 요청 읽기 비율(%) 설명 PC 개인 PC 작업 1 (vim, 문서작업 등) PC 개인 PC 작업 2 (vim, 문서작업 등) DEV 개인 PC 개발 작업 (gcc, grep등) SENSOR 하드웨어 센서 입력 SENSOR 하드웨어 센서 입력 및 처리 SYNTH 하드웨어 Synthesis WEB Web Cache 1 WEB Web Cache 2 표 4.2 실험에 사용한 workload Trace 총 I/O 요청 읽기 비율(%) 설명 multi glimpse + cscope 동시 실행 multi gnuplot + BLAST 동시 실행 표 4.3 읽기 실험을 위한 trace 실험을 위하여 실제 요청에 사용된 binary data를 포함한 트레이스 정보가 필 요하였기 떄문에 연구실에서 수집한 아래 트레이스들을 사용하였다. 트레이스들의 특성은 표 4.2와 같다. 또한 읽기 성능에 의한 차이를 나타내기 위해, 표 4.3의 트레이스를 바탕으로 추가적인 평가를 진행하였다. 해당 트레이스들의 경우 실제 I/O 요청에서 사용된 데이터가 포함되어 있지 않기 때문에, 일반적인 텍스트 데이터를 기준으로 약 0.6 의 압축률(압축된 크기/원본 크기)로 데이터가 기록되어 있음을 가정했다. 27

38 Trace 설명 Highly compressible 압축률이 매우 높은 파일들 (압축률 5) Zero compressible 압축이 되지 않는 파일들 (압축률 1) 압축률이 높은 파일 (압축률 2.5)과 Mixed1 압축이 되지 않는 파일 (압축률 1) 혼합 구성 압축률이 매우 높은 파일 (압축률 5)와 Mixed2 압축이 되지 않는 파일 (압축률 1) 혼합 구성 표 4.4 실험에 사용한 가공 workload 여기에 압축률이 높고 낮은 데이터가 번갈아가며 삽입되는 상황을 살펴보기 위해 synthetic한 가공의 workload를 만들어 사용하였다. 실제 한 가지 작업만을 수행하는 일반 workload에서는 발생하기 힘들지만, 여러 특성을 가진 workload가 섞여서 입력되는 서버 등의 환경이라면 이러한 특성 설정이 의미가 있을 수 있다. 28

39 4.2 실험 결과 Chunk 이어쓰기를 통해 내부 단편화를 제거하였을 때 나타날 수 있는 결과를 그림 4.1에 그래프로 표시하였다. 기존의 chunk 단위 압축 계층을 사용한 결과를 compression-aware FTL (caftl) 이라 표시하고, 이 때 얻을 수 있는 용량을 100% 기준으로 하여 normalize한 비율로 결과를 표시하였다. 각 workload의 압축률에 따라 결과가 조금씩 다르지만, 적용하지 않았을 때와 비교하여 평균 32%에 해당 하는 용량을 추가로 확보할 수 있음을 보이고 있다. 또한 압축이 거의 되지 않는 경우을 대상으로 평가를 진행하였을 때, 얻을 수 있는 수명 향상이 거의 없음을 확인할 수 있다. 그림 4.1 내부 단편화를 제거했을 떄 확보되는 용량 29

40 위에 제시된 결과들의 경우 대부분 쓰기 연산을 중심을 수집된 트레이스이기 때문에 읽기 성능 저하를 평가하기 적합하지 않다. 또한 chunk 이어쓰기 기법을 적 용할 경우, 적용하지 않은 경우에 비해 읽기 횟수는 확실히 증가하게 된다. 그림 4.2 를 통해 실제 읽기 증폭 현상의 발생을 확인할 수 있다. 특히 multi1과 같은 trace 들에서는 압축을 적용하지 않은 baseline에 비해서도 읽기 횟수가 크게 증가하고 있음을 확인할 수 있다. 그림 4.2 Chunk 이어쓰기로 인한 읽기 증폭 현상 이에 압축을 고려한 compression-aware read buffer를 적용하였을 때 개선되는 정도를 그림 4.3을 통해 나타내었다. 앞의 결과와 마찬가지로 workload 중 읽기 연산이 매우 적은 trace들은 평가에서 제외되었다. 버퍼를 거치지 않고 직접 장 치까지 전달되어 읽기 연산을 수행한 경우에만 읽기 횟수를 카운트하였으며 읽기 버퍼를 통한 경우 그 비용이 0이라 가정하였다. 읽기 버퍼의 경우, 일반적인 LRU 방식의 64 MB 읽기 버퍼를 사용했을 때 와 비교하여 그 성능을 평가하였다. Workload의 특성에 따라 다르지만, 압축으로 인한 버퍼 크기의 증가가 데이터의 지역성을 고려한 읽기 연산의 범위를 넘어설 정도로 커질 경우 매우 급격하게 cache hit이 증가하는 양상을 확인할 수 있었다. 특히 multi1 트레이스의 경우, 일반적인 읽기 버퍼를 사용하였을 때에 비해 압축을 30

41 고려한 chunk 단위 읽기 버퍼를 사용하였을 때 그 개선폭이 매우 크다. 이는 해당 트레이스의 전체 워킹 셋 크기가 434 MB 정도로 작은 경우임을 감안할 필요가 있다. 그림 MB Compression-aware buffer 사용시 읽기 횟수 감소 31

42 Compression-aware read buffer를 적용하였을 때 일반적으로 그림 4.4와 같이 buffer에 저장하고 있는 엔트리가 2.6배까지 증가하고 있음을 볼 수 있다. 이는 64 MB 버퍼가 아닌 약 166 MB의 버퍼를 사용하고 있는 것과 동일한 효율이다. 다만 실제 entry 개수의 증가가 바로 읽기 성능의 향상을 담보하는 것은 아니라는 점에 주의할 필요가 있다. 그림 4.4 읽기 버퍼 내의 entry 개수 32

43 실제 workload를 바탕으로 garbage collection을 적용하였을 때 chunk 이어쓰 기를 통해 개선 효과를 얻을 수 있는데 이는 그림 4.5 에서 확인할 수 있다. Chunk 이어쓰기를 통해 장치로 인가되는 데이터가 줄어들면 gc의 발동 횟수 자체가 줄어 들게 되고 그로 인해 gc시 발생하는 page copy수 역시 줄어든다. 이는 gc최적화로 인한 영향이 아닌 쓰기 횟수 감소 및 수명 향상으로 인해 자연스럽게 발생하는 결과임에 주의할 필요가 있다. 그림 4.5 Chunk 이어쓰기로 인한 GC 효율 증가 Chunk 이어쓰기를 적용한 상태에서 순수한 gc 최적화의 효율만을 살펴보면 그림 4.6 와 같다. 평균적을 약 10%의 GC page copy를 줄일 수 있으며, synthetic workload를 통해 압축률이 매우 높은 block과 매우 낮은 block이 공존하도록 환경 을 조성할 경우 최대 39.1%까지 감소율이 높아질 수 있다. GC 최적화의 기대보다 낮은 효율은 block별 압축률의 분포, 즉 block density 의 차이에 의해 기인한다. 그림 4.7 에서 서로 다른 workload 간 block density 분포의 차이를 확인할 수 있다. 실제 workload 중 비교적 압축률 분포가 다양한 DEV1의 경우 gc최적화로 인해 이득을 얻을 가능성 또한 높기 때문에 비교적 높 33

44 은 개선치 (약 15%)를 얻을 수 있으나, 대부분의 block density가 비슷한 sensor 의 경우 새로운 victim selection 알고리즘으로 높은 효율을 기대할 수 없게 된다. 인위적으로 매우 높은 압축률의 block과 낮은 압축률의 block을 공존시킬 경우 큰 효율을 기대할 수 있다. 그림 4.6 GC 최적화를 통한 효율 증가 그림 4.7 Block 별 block density 분포 34

45 그림 4.8 optimized caftl을 사용한 수명 향상 압축을 적용하지 않은 baseline 대비하여 기존의 caftl을 통한 수명 증가 및 최적화를 통한 개선 정도를 그림 4.8를 통해 확인할 수 있다. 기존 chunk 기반의 압축 방식을 사용하여 37%의 수명 향상을 기대할 수 있었지만, 본 논문에서 사용 한 최적화 기법들을 통해 그 효율성을 개선하여 총 54% 의 쓰기 횟수 감소 (수명 향상)를 확인할 수 있다. 35

46 제 5 장 결론 5.1 결론 하드웨어 압축 계층을 활용하여 낸드 플래시 기반 저장장치의 수명과 성능을 높이는 것은 이미 연구된 바 있지만, 압축 과정을 도입하면서 발생하는 내부 단편화 에 대해서는 심도 있는 논의가 이루어지지 않았다. 기존 연구에서는 내부 단편화를 완화하기 위해 chunk 단위 압축을 도입하여 효과가 있음을 보였으나, 수집한 샘플 workload를 대상으로 실험한 결과 4 페이지 chunk를 사용했을 때에도 평균 21% 의 공간이 내부 단편화로 인해 낭비되고 있음을 확인하였다. 본 논문에서는 이를 해결하기 위해 chunk 이어쓰기 기법을 제안하였다. 별도의 buffer 영역에서 입력되 는 chunk를 page 안에서 붙여 씀으로써 내부 단편화 문제를 근본적으로 해결할 수 있다. 그러나 이 방법을 사용할 경우 필연적으로 발생하는 offset 관리의 overhead 를 줄이기 위하여 16개의 sub page 단위로 관리하는 기법을 도입하였다. Chunk 이어쓰기를 도입할 경우 일부 읽기 중심 workload에서는 읽기 증폭 현상이 발생 할 수 있으며, 기존 chunk 기반 압축에 비해서는 반드시 읽기 횟수가 증가한다. 본 논문에서는 이를 완화하기 위해 compression-aware read buffer를 제안하였다. 종전의 page단위 대신 entry를 chunk 단위로 관리함으로써 저장된 entry의 수를 2.6배 증가시킬 수 있으며, 이를 통해 평균 56% 의 읽기를 buffer에서 처리할 수 있었다. 또한 압축이 적용된 환경에서의 gc 효율성 개선을 위해 새로운 victim 선 정 알고리즘을 고안하였다. 종래의 valid page 개수만을 확인하는 기법과는 달리 36

47 block의 압축률을 통해 reclaim이 일어난 뒤의 page copy 수를 예측함으로써 약 10%더 적은 page copy가 발생하는 victim을 선정할 수 있다. 이는 workload의 특성에 따라 압축률이 높은 블록과 낮은 블록이 공존할 경우 그 효과가 극대화된 다. 종합적으로 최적화 기법들을 적용하여, 기존의 chunk 사용한 방식의 caftl과 비교해본 결과 기존 기법을 68% 개선하여 최대 수명을 약 1.85배 증가시킬 수 있 었으며, 읽기 위주의 트레이스를 대상으로 실험하였을 때 기존 LRU page 방식에 비해 평균 45% 읽기 연산의 횟수를 줄일 수 있었다. 37

48 5.2 향후 연구 Chunk table 관리는 현재의 sub page 기법을 사용하더라도 어려운 문제다. 특히 현재의 chunk를 같은 block에 배치하는 구현의 경우 장치의 parallelism을 충분히 살리지 못하는 문제가 있다. 실제 같은 chunk가 빈번하게 같이 읽기게 되 는 점을 감안한다면 chunk를 구성하는 page들을 흩어 쓰는 것이 올바른 방향이 될 수 있으나, 그 경우 chunk를 구성하는 각각의 물리 페이지들을 모두 매핑하여 관리할 필요가 생긴다. 특히 chunk 이어쓰기와 같은 기법을 통해 page boundary 가 모호해 질 경우 이로 인한 overhead가 매우 클 수 있다. 또한 읽기 비효율성의 경우, 결국 어떤 페이지들이 같은 chunk에 묶이게 되 느냐에 의해 그 성능이 크게 좌우된다. 이는 압축이 적용된 환경에서 garbage collection을 수행하는 경우에도 마찬가지로, 같은 chunk안에 위치해 있는 항목들 이 모두 같이 invalid되어야만 chunk 전체를 invalid 처리할 수 있기 때문이다. 이를 해결하기 위해서는 hot-cold separation과 같은 적절한 데이터 구분 기법을 통해 어느 페이지를 같은 chunk에 묶어야 하는가에 관한 연구를 진행할 필요성이 있다. 본 논문에서는 데이터 압축 기법을 대상으로 하여 동적인 크기의 읽기/쓰기 요청에 대응하기 위한 관리 기법을 소개하였다. 특히 여기에서 사용한 chunk는 가변적인 크기를 가진 임의의 큰 단위 데이터를 표현할 수 있는 추상적인 개념으 로써, 꼭 압축이 아니더라도 다양한 원인에 따라 가변적인 크기를 가질 수 있는 요청이라면 여기서 제시된 것과 비슷한 방법을 사용하여 관리하는 것이 가능할 것이라 생각된다. 38

49 참고문헌 [1] N. Sommer, Signal Processing and the Evolution of NAND Flash Memory Embedded Computing Design, Vol. 8, No. 8, Pages 8-10, Dec [2] T. Kim et al, FineDedup: A Fine-Grained Deduplication Technique for Flash-Based SSDs International Conference on Memory Architecture and Organization Workshop 2012, Tampare, Finland, Oct [3] L. Chang, On Efficient Wear Leveling for Large-scale Flash-memory Storage Systems Proceedings of the 2007 ACM Symposium on Applied Computing, Seoul, Korea, Mar [4] S. Lee et al, FlashBench: A Workbench for a Rapid Development of Flash- Based Storage Devices International Symposium on Rapid System Prototyping 2012, Tampare, Finland, Oct [5] S. Lee et al, Improving Performance and Lifetime of Solid-State Drives Using Hardware-Accelerated Compression IEEE Transactions on Consumer Electronics, Vol. 57, No. 4, pp , Nov [6] Pei Cao et al, Cost-aware WWW Proxy Caching Algorithms Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, pp , Dec

50 Abstract Design and Implementation of a High-Performance Data Compression Layer for SSDs with Long Lifetime Hoyoon Jun School of Computer Science Engineering Collage of Engineering The Graduate School Seoul National University Scale-down of NAND flash sell size and multi-level cell (MLC) technology introduced a chance for wide-spread acceptance of NAND flash device as a primary storage. However, performance and reliability of a single memory cell keeps deteriorating with such technological advances. In this paper, we present a systemic method to improve performance and lifetime of a SSD using hardware-assisted compression. Compression can reduce the amount of data read/written in the device significantly, but it can also trigger a new problem of data management due to its varying request size. Especially, internal fragmentation and read amplification, and partially invalid 40

51 chunks (pages) can be occur in the specific condtion and workload. In order to fully exploit the power of compression, we purpose three novel optimization techniques for compression-assisted NAND Flash, namely continous chunk write, chunk-based compression-aware read buffer, and compressionaware victim selection. Our evaluation results shows that these optimization techniques can reduce the physical amount of written data by 56%and compressionaware buffer can reduce device read operation by 45%. Keywords: NAND, Flash memory, SSD, compression, fragmentation, read buffer, batching Student Number: