03( ) CST13-08.hwp

Size: px

Start display at page:

Download "03(166-174) CST13-08.hwp"

아진 감
8 years ago
Views:

1 166 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) SSD 장치 내 NCQ를 활용한 쓰기 버퍼 관리 기법 (A Write Buffer Management Scheme Exploiting the NCQ of SSDs) 김성민 김 태 석 (Seongmin Kim) (Taeseok Kim) 요 약 본 논문에서는 SSD(Solid-State Drives) 내의 NCQ(Native Command Queueing)가 가진 정보 를 활용하는 쓰기 버퍼 관리 기법을 제안한다. 호스트로부터 SATA 인터페이스를 통해 요청되는 입출력 명 령들은 우선 NCQ에 도착하여 처리할 준비가 완료될 때까지 큐에서 대기하게 되고, 큐에 존재하는 명령에 관 련된 데이터는 가까운 미래에 반드시 참조된다. 따라서 제안하는 기법은 과거의 참조 패턴 정보와 함께 NCQ 내의 입출력 명령들로부터 얻을 수 있는 미래 참조 패턴 정보를 활용하고, 이를 통해 버퍼 관리 기법의 효율 을 높일 수 있다. 또한, 이 기법은 기존의 여러 버퍼 관리 기법들에 쉽게 적용할 수 있다는 장점이 있다. 모의 실험을 통한 성능평가 결과, 제안하는 기법에 의해 버퍼 히트율이 최대 7.3% 상승하였다. 키워드: NAND 플래시 메모리, SSD, 버퍼 관리 기법, NCQ Abstract In this paper, a write buffer management scheme that exploits the informations within NCQ (Native Command Queueing) of SSDs (Solid-State Drives) is presented. In SSDs with SATA interface, there exist the pending I/O commands in NCQ, and we observed that the data belonging to the I/O commands queued in NCQ would be needed in the near future. We maximize the efficiency of buffer management by using the existence of NCQ in order to obtain the information of future reference pattern as well as past reference pattern. It is important to note that the proposed scheme can be integrated with other existing buffer management schemes without large modification. Through the trace-driven simulation, we show that the proposed scheme outperforms the LRU scheme in terms of hit ratio uo to 7.3%. Keywords: NAND flash memory, SSD, buffer management scheme, NCQ 1. 서 론 본 연구는 지식경제부 및 한국산업기술평가관리원의 산업원천 기술개발 사업(정보통신)의 일환으로 수행하였음. [No , 차세대 메모리 기반의 스마트 디바이스용 임베디드 시스템 소프트웨어] 학생회원 : 광운대학교 컴퓨터공학과 zinjja2@kw.ac.kr 비 회 원 : 광운대학교 컴퓨터공학과 교수 tskim@kw.ac.kr (Corresponding author임) 논문접수 : 2013년 7월 24일 (Received 24 July 2013) 논문수정 : 2014년 2월 12일 (Revised 12 February 2014) 심사완료 : 2014년 2월 27일 (Accepted 27 February 2014) CopyrightC2014 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작 물의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지: 시스템 및 이론 제41권 제4호(2014.8) SSD(Solid-State Drives)는 낮은 데이터 접근 시간, 저전력, 무소음 등의 장점이 있지만, NAND 플래시 메 모리의 특성으로 인하여 읽기 연산에 비해 상대적으로 느린 쓰기 연산, 제한된 삭제 연산 횟수 등의 단점을 함 께 가지고 있다. 이러한 단점을 극복하기 위해 SSD에 서는 쓰기 버퍼를 사용하여 NAND 플래시 메모리에 실 제로 쓰여지는 데이터양을 줄임으로써 쓰기 성능을 향 상시킬 뿐만 아니라 SSD의 수명을 개선한다. 일반적으 로 이러한 쓰기 버퍼는 그 공간이 제한되어 있어 효율 적인 버퍼 관리 기법이 필요하고, 이를 위한 NAND 플 래시 메모리 기반 SSD를 위한 다양한 버퍼 관리 기법 이 연구되었다[1-5]. 그러나 대부분의 연구들은 입출력 워크로드의 지역성(locality)과 NAND 플래시 메모리의 일부 특성만 고려하는데 그치고 있다.

Queueing)가 가진 정보 를 활용하는 쓰기 버퍼 관리 기법을 제안한다. 호스트로부터 SATA 인터페이스를 통해 요청되는 입출력 명 령들은 우선 NCQ에 도착하여 처리할 준비가 완료될 때까지 큐에서 대기하게 되고, 큐에 존재하는 명령에 관 련된 데이터는 가까운 미래에 반드시 참조된다.

2 SSD 장치 내 NCQ를 활용한 쓰기 버퍼 관리 기법 167 본 논문에서는 SSD내에 존재하지만 지금껏 고려되지 못하였던 NCQ(Native Command Queue)를 활용하는 버퍼 관리 기법을 제안한다. 제안하는 기법은 큐에 보관 된 명령들로부터 미래 참조 패턴 정보를 얻고 이를 버 퍼 관리 정책에 활용한다. 원래 NCQ는 SATA 인터페 이스를 사용하는 디스크에서 입출력 명령을 쌓아두고 스케줄링을 통해 입출력 처리 시간을 개선하기 위한 기 법이었는데, SSD에서도 여러 개의 입출력 명령들을 동 시에 처리함으로써 호스트 시스템에서 느끼는 지연시간 을 줄이기 위한 목적으로 여전히 활용되고 있다[6]. NCQ에는 가까운 미래에 반드시 처리될 입출력 명령들 을 가지고 있으므로 이들로부터 유효한 미래 정보를 획 득할 수 있고, 버퍼 내의 해당 데이터를 별도 관리함으 로써 버퍼의 히트율을 향상시킬 수 있다. 본 논문은 다음과 같이 구성되어 있다. 2절에서는 버 퍼 관리 기법과 관련한 기존 연구와 함께 SSD의 내부 에 존재하는 NCQ에 대해 살펴본다. 3장에서는 제안하 는 새로운 버퍼 교체 기법에 대해 설명하고, 4장에서는 성능을 평가한다. 마지막으로, 5장에서는 연구 결과를 요약한다. 2. 관련연구 및 배경지식 2.1 버퍼 관리 기법 관련 연구 SSD 혹은 NAND 플래시 저장장치에서 입출력 성능 과 수명을 향상시키기 위한 버퍼 관리 기법에 관해 이 미 많은 연구가 진행되어 왔다. 이러한 버퍼 관리 기법 은 크게 세 가지로 나눌 수 있는데, 첫 번째로 워크로드 의 특성만을 고려하는 기법, 두 번째로 플래시 메모리의 특성만을 고려한 기법 그리고 마지막으로 앞의 두 가지 를 혼용한 기법이다. 워크로드의 특성만을 고려하는 기법에는 가장 널리 알려진 LRU(Least Recently Used)와 LFU(Least Frequently Used)가 있다. 이 기법들은 초기 버퍼 관리 기 법들의 연구에 많이 활용되었으며, 여전히 많은 버퍼 관 리 기법을 연구하는데 있어 기본이 되고 있다. 플래시 메모리의 특성만을 고려하는 기법에는 대표적 으로 FAB[1], BPLRU[2] 등이 있다. FAB[1] 기법은 희생 블록(victim block)으로 선정된 논리 블록의 모든 페이지를 한 번에 교체 한다. 가장 많은 페이지를 가진 논리 블록을 희생 블록으로 선정함으로써 가비지 컬렉 션(garbage collection)의 비용을 줄이고 순차 쓰기 패 턴(sequential write pattern)의 워크로드에서 성능을 향 상시킨다. BPLRU[2] 기법은 FAB과 유사하지만, LRU 기반으로 희생 블록을 선정한다. 또한, 블록 채우기 (block padding) 기법을 사용하여 로그 블록(log block) 에 모든 페이지를 순차적으로 기록하여 완전 병합(full merge) 대신 비용이 적은 스위치 병합(switch merge) 이 발생하도록 한다. 워크로드와 플래시 메모리의 특성만을 고려하는 버퍼 관리 기법은 각자 좋은 성능을 보여주고 있지만 SSD에 최적화된 버퍼 관리 기법을 위해서는 두 가지 특성을 모두 고려할 필요가 있다. 이에 따라 최근 여러 가지 버 퍼 관리 기법들이 연구되었으며, 이 중 대표적인 기법에 CLC[3], BPAC[4], ExLRU[5] 등이 있다. CLC[3] 기법 은 FAB과 BPLRU를 혼용한 기법이다. 버퍼 공간을 두 영역으로 나누어 첫 번째 영역은 LRU 방식으로 블록들 을 관리하고, 두 번째 영역은 블록에 속한 페이지의 개 수 순으로 관리함으로써, 워크로드의 지역성 및 NAND 플래시 메모리의 특성을 활용하고 있다. BPAC[4] 기법 은 워크로드의 지역성을 적응적으로 고려하기 위해 재 참조율이 높은 데이터를 관리하는 리스트와 재참조율이 낮은 데이터를 관리하는 리스트로 나누어 버퍼 내의 데 이터를 관리하고, 재참조율을 분석하기 위해 워크로드 모니터링 기법을 사용 한다. ExLRU[5] 기법은 FAB과 BPLRU에서 재참조율이 높은 페이지가 속한 블록이 버 퍼에서 교체되거나, 재참조율이 낮은 페이지가 버퍼에 오래 유지될 수 있는 문제점을 해결하기 위해 버퍼 내 의 블록들에 대해 비용 모델을 설계하였다. ExLRU는 비용 모델에 의해 버퍼 내의 페이지들의 단위시간당 재 참조율을 계산하고 이를 이용해 다시 블록들의 단위시 간당 재참조율 등을 계산하여 비용 값을 얻어낸 뒤, 블 록들 중 가장 비용 값이 낮은 블록을 희생 블록으로 선 정하게 된다. 위와 같이 NAND 플래시 메모리 기반의 저장장치를 위한 다양한 버퍼 관리 기법이 연구되었으며, 그 연구들 중 대부분은 기존 버퍼 관리 기법에서 고려 요소를 추 가하여 성능을 향상시키고 있다. 하지만 아직까지의 연 구들에서는 과거 참조 패턴 정보와 SSD 내 아키텍쳐 중 일부분만을 고려하고 있다는 한계를 가지고 있으며, NCQ 내의 정보를 활용한 연구는 전무한 실정이다. 2.2 SSD 내에서의 NCQ NCQ는 HDD와 같은 SATA장치의 성능을 향상시키 기 위해 도입된 기술로, 먼저 입출력 명령을 큐에 보관 한 다음 디스크 헤드의 전체 이동거리를 최소화할 수 있도록 명령들의 순서를 재배열한다. SSD에는 HDD의 헤더와 같은 기계적 움직임을 갖는 요소가 없지만, 최근 엔 SSD에서도 NCQ를 이용한 입출력 명령들의 병합 처리를 통해 성능을 향상시키기 위한 연구가 진행되고 있으며[7], 큐 길이(queue length)에 따라 데이터의 동 시처리가 가능하기 때문에 NCQ 지원여부에 따라 30% 이상의 성능차가 발생하게 된다[8]. 큐 길이는 호스트에서 저장장치로 동시에 요청되는

NCQ에는 가까운 미래에 반드시 처리될 입출력 명령들 을 가지고 있으므로 이들로부터 유효한 미래 정보를 획 득할 수 있고, 버퍼 내의 해당 데이터를 별도 관리함으 로써 버퍼의 히트율을 향상시킬 수 있다. 본 논문은 다음과 같이 구성되어 있다. 2절에서는 버 퍼 관리 기법과 관련한 기존 연구와 함께 SSD의 내부 에 존재하는 NCQ에 대해 살펴본다.

3 168 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) 그림 2 가상 MRU의 사용 Fig. 2 The use of virtual MRU 그림 1 SSD내에서의 입출력 명령 처리 절차 Fig. 1 The procedure for handling an I/O command within SSD 명령의 개수를 의미한다. SATA 인터페이스의 표준화 규격에서 NCQ의 최대 큐 길이를 32로 명시하고 있으 며, 비 표준화 SSD에서는 최대 큐 길이가 128까지 사 용될 수 있다[9,10]. 일반적으로 응용프로그램에 의해 입 출력 명령이 빈번하게 요청되어 저장장치가 바쁜(Busy) 상태가 되면 큐에서 대기하는 명령의 개수가 늘어나 큐 길이가 길어지게 되며, 큐 길이가 길수록 최대치에 가까 운 대역폭(Bandwidth)을 사용하게 된다[11]. 그림 1은 호스트로부터 SATA 인터페이스를 통해 SSD로 전송된 입출력 명령이 처리되는 과정을 보여준 다. SSD에 전달된 입출력 명령은 먼저 NCQ에 쌓이게 되고, 명령이 수행될 준비가 되면 디스패치(dispatch)되 어 버퍼를 통해 처리한다. 이 때, 처리할 입출력 명령의 데이터가 버퍼에 존재할 경우 바로 응답 처리가 가능하 고, 그렇지 않은 경우 FTL(Flash Translation Layer) 을 거쳐 플래시 메모리에서 읽기 및 쓰기 연산이 수행 된다. 3. NCQ를 활용한 버퍼 관리 기법 본 논문에서는 앞서 살펴 본 기존 버퍼 관리 기법들이 이용하지 못했던 SSD 내에 NCQ를 활용하는 쓰기 버퍼 관리 기법을 제안한다. NCQ에 보관중인 입출력 명령들 은 가까운 미래에 반드시 처리되기 때문에 이를 이용하 면 보관중인 명령의 양만큼 미래 참조 패턴 정보를 획득 할 수 있다. 제안하는 기법은 이러한 미래 참조 패턴 정 보를 바탕으로 호스트로부터 NCQ에 전달된 입출력 명 령이 필요로 하는 데이터가 버퍼에 존재할 경우, 해당 데이터가 사용될 때까지 버퍼에서 교체되지 않도록 별도 관리한다. 이러한 기법은 버퍼 내의 곧 사용될 데이터가 사용 직전에 교체되어 미스(miss)가 발생하는 상황을 차 단함으로써 버퍼의 히트율 향상을 가져올 수 있다. 본 논문에서는 제안하는 기법을 간단한 LRU 기법에 적용하여 구현하였으며, QLRU(NCQ-aware LRU)라고 명칭한다. QLRU는 기존의 LRU 기법과 마찬가지로 버 퍼 내의 데이터가 참조될 경우 MRU(Most Recently Used) 위치로 이동하며, LRU 위치의 데이터를 교체 대 상으로 삼는다. 여기에 QLRU 기법을 위해 미래 참조 패턴 정보 기반의 버퍼 데이터를 보존하기 위한 가상 MRU(virtual MRU)라는 포인터를 구현하였다. 가상 MRU란 그림 2와 같이 NCQ에 도착한 명령이 요구하 는 데이터가 버퍼에 존재할 경우, 해당 데이터를 가상 MRU로 이동시킨다. 가상 MRU로 이동된 데이터는 가 까운 미래에 반드시 참조되기 때문에, 해당 명령이 디스 패치 되기 전 최대한 오랜 시간동안 버퍼 내에 유지되 게 된다. 또한 이 기법은 단순한 포인터 이동으로 구현 되기 때문에, 발생하는 오버헤드가 매우 적고, 추가적인 공간을 요구하지 않는다는 장점이 있다. 그림 4는 NCQ를 고려하는 QLRU가 LRU와 비교하 여 어떤 효과가 있는지 보여준다. 그림 4(1)은 NCQ와 버퍼의 초기 상태를 나타내며, QLRU와 LRU의 비교를 위해 각 기법에 의해 동작하는 두 개의 버퍼를 동시에 보여준다. 이 후 그림 4(2)와 같이 새로운 명령 C2가 NCQ에 도착한 경우, QLRU 버퍼에서는 C2가 요구하는 데이터 5를 가상 MRU로 이동시킨다. 이 과정이 QLRU 의 핵심으로, 아직 C2 명령이 처리된 것은 아니지만, NCQ에 도착해서 조만간 이 명령이 처리될 것이 명확하 기 때문에 이 명령에 해당되는 버퍼 상의 데이터 5를 가상 MRU로 옮겨 교체되지 않도록 한 것이다. 이 상태 에서 그림 4(3)과 같이 C1 명령이 디스패치 될 경우, LRU와 QLRU 모두에서 버퍼 미스가 발생하고, 데이터 3을 MRU 위치에 넣기 위해 LRU 위치에 있던 데이터 를 각각 교체한다. 마지막으로 그림 4(4)와 같이 C2 명 령이 디스패치 되면, 데이터 5가 교체된 LRU 기법의 버퍼에서는 미스가 발생하지만, QLRU에서는 히트(hit) 가 발생하게 된다. 여기에서는 쓰기 버퍼 관리 기법 설계시 과거의 참조 패턴 정보뿐만 아니라, NCQ에 있는 미래 참조 패턴 정 보를 함께 활용하는 것이 효과적임을 보여주기 위해 가 장 간단한 LRU 기법에 기반하여 설명하였다. 또한,

일반적으로 응용프로그램에 의해 입 출력 명령이 빈번하게 요청되어 저장장치가 바쁜(Busy) 상태가 되면 큐에서 대기하는 명령의 개수가 늘어나 큐 길이가 길어지게 되며, 큐 길이가 길수록 최대치에 가까 운 대역폭(Bandwidth)을 사용하게 된다[11].

4 SSD 장치 내 NCQ를 활용한 쓰기 버퍼 관리 기법 169 그림 3 QLRU의 알고리즘 Fig. 3 Algorithm of QLRU QLRU는 LRU 기법과 NCQ 정보를 활용하는 기법을 융합하여 만들어졌으며, NCQ를 가진 SSD라면 관련연 구에서 언급한 기존의 다른 쓰기 버퍼 관리 기법들에 그대로 적용 가능하다. 심지어는 NCQ 기반의 하드디스 크에서도 쓰기 버퍼 관리 기법에 적용 가능하다. 4. 실험 결과 및 분석 4.1 실험 환경 제안한 버퍼 관리 기법의 성능을 평가하기 위해 FlashSim[12] 시뮬레이터에 기반하여 QLRU를 구현하 였다. 실험을 위해 시뮬레이터에서 설정한 SSD의 물리

구에서 언급한 기존의 다른 쓰기 버퍼 관리 기법들에 그대로 적용 가능하다.

5 170 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) 그림 4 QLRU의 효과 Fig. 4 Effectiveness of QLRU 표 1 SSD의 물리적 특성 Table 1 Specification of the SSD Specification Capacity 64 Gb The number of Channels 8 Page program time 200 us Flash size blocks Block size 128 pages Page size 4096 bytes 였다. 실험을 위해 시뮬레이터에서 설정한 SSD의 물리 적 특성은 표 1과 같이 64 Gb의 용량을 가지며, 각 페 이지 크기는 4 Kb로 설정하였고, 8개의 독립적인 채널 을 통해 병렬적인 입출력 명령의 처리가 가능하다. 또한, FTL은 페이지 단위 주소 매핑(page level address mapping)을 사용하며, NAND 플래시 메모리 와 버퍼가 비어있는 환경에서 실험을 진행하였다. 쓰기 버퍼는 쓰기 명령에 대한 데이터만을 흡수하며, 읽기 명령이 수행될 경우, 해당 데이터가 버퍼에 존재하 면 히트를 발생시킬 수 있지만, 미스가 발생했을 때 해 당 데이터를 버퍼에 저장하지는 않고 호스트로 바로 데 이터를 전달하게 된다. 이에 따라 읽기 명령에 의한 버 퍼 상태의 변화가 없으며 쓰기 명령의 성능에 영향을 끼치지 않기 때문에, 실험에서 사용된 워크로드는 모두 쓰기 명령만 사용하여 성능만을 측정하였다. 그리고 각 실험은 SSD를 깨끗하게 비운 상태에서 시작하여 SSD 가 꽉 차는 경우에는 가비지 컬렉션(garbage collection) 이 발생할 수 있도록 하였다. 버퍼의 크기는 32 MB부터 512 MB까지, NCQ의 최 대 큐 길이는 32부터 512까지 변경하며 버퍼의 히트율 에 중점을 두고 결과를 분석하였다. 현재 상용화된 많은 SSD에서는 NCQ의 최대 큐 길이를 32에서 128 정도로 제한하고 있지만, NCQ의 큐 길이가 제안하는 기법에 주는 영향을 검증하기 위해 최대 큐의 길이를 512까지 늘려가며 실험하였다. 4.2 실험 결과 워크로드에 따른 QLRU의 효과 실험을 위해 사용된 워크로드는 Iometer[13] 벤치마 크 툴을 사용하여 워크로드를 수집하였고, 각각의 특성 은 표 2와 같다. 각 워크로드는 512 KB부터 1 GB까지 다양한 크기의 파일에 대해 입출력을 수행하는 12개의 쓰레드에 의해 수집되었으며, 쓰레드별 입출력 요청의 크기는 4 KB부터 512 KB까지이다. 그리고 데이터 접 근 패턴의 경우 워크로드 A는 모두 임의 접근으로 구성 되어 있고, 워크로드 B는 임의 접근과 순차 접근이 절 반씩 섞여 있으며, 워크로드 C는 모두 순차 접근이다. 또한, IOmeter를 사용할 경우 디스크에 쓰기 명령을 전 달할 때, 운영체제의 버퍼 캐시를 거치지 않고 물리 디 스크에 직접적인 접근이 발생하게 되어, 버퍼 캐시에 의 표 2 사용된 워크로드의 특성 Table 2 Characteristics of the workloads used The number of threads File size Record size The number of requests Avg. interarrival time Access pattern A B C KB~ 1 GB 4 KB~ 512 KB 512 KB~ 1 GB 4 KB~ 512 KB 512 KB~ 1 GB 4 KB~ 512 KB 500, , , ms 90 ms 72 ms Random Random + Sequential Sequential

Page size 4096 bytes 였다. 실험을 위해 시뮬레이터에서 설정한 SSD의 물리 적 특성은 표 1과 같이 64 Gb의 용량을 가지며, 각 페 이지 크기는 4 Kb로 설정하였고, 8개의 독립적인 채널 을 통해 병렬적인 입출력 명령의 처리가 가능하다.

6 SSD 장치 내 NCQ를 활용한 쓰기 버퍼 관리 기법 171 그림 5 워크로드에 따른 버퍼 히트율 Fig. 5 Hit ratio with various workloads 한 쓰기 명령 흡수가 발생하지 않는다. 따라서 이 실험 에서는 운영체제의 버퍼 캐시가 워크로드에 끼치는 영 향을 배제한 상황을 가정한다. 먼저 워크로드에 따라 QLRU의 효과를 검증하기 위 해 쓰기 버퍼의 크기를 32 MB, NCQ의 최대 큐 길이 는 512개로 설정한 뒤, 각 워크로드에 대해 버퍼 히트율 을 측정하였다. 그림 5는 해당 실험 결과를 나타낸다. 결과를 확인하면 모든 워크로드에서 약 25% 이상의 버 퍼 히트가 발생한 것을 확인할 수 있다. 이는 각 워크로 드에서 입출력을 수행한 쓰레드가 서로 균등한 입출력 빈도를 갖고 있으며, 이 때, 상대적으로 작은 크기의 파 일에 대해 입출력을 수행하는 쓰레드에서 필요로 하는 데이터는 거의 대부분 버퍼에 존재할 수 있기 때문이다. 하지만 접근 패턴에 따라 워크로드간 전체 버퍼 히트율 이 차이가 나고 있으며, 모든 워크로드에서 LRU 대비 QLRU의 버퍼 히트율의 절대 수치가 6-7% 가량 향상 되었다. 이러한 결과에 따라 QLRU가 미래 참조 패턴 예측으로 인해 파일의 접근 패턴에 큰 영향을 받지 않 고 LRU 대비 성능이 향상됨을 확인할 수 있다 버퍼 크기 및 최대 큐 길이에 따른 효과 버퍼 크기와 NCQ의 최대 큐 길이를 변경하며 QLRU 의 효과를 확인하기 위해 모든 워크로드에 대해 실험한 결과, 파일 접근 패턴에 따른 LRU 대비 QLRU 성능상의 차이가 거의 없었기 때문에 여기에서는 워크로드 A에 대 한 실험 결과만 제시한다. 그림 6에서 볼 수 있듯이, 버퍼 크기가 32MB, 최대 큐 길이는 512일 때, QLRU의 버퍼 히트율의 절대 수치가 LRU보다 7.3% 향상되어 가장 높 은 성능향상 폭을 보였다. 결론적으로 버퍼 크기가 작을 수록, 그리고 최대 큐 길이가 길수록 QLRU가 LRU 대비 좋은 성능을 발휘하는 것을 확인할 수 있다. 이는 QLRU가 효과를 얻기 위해서는 가상 MRU 개 념이 충분히 활용되어야 하기 때문이다. 즉, 반대로 이 야기하면 큐에서 얻은 미래 참조 패턴 정보로부터 확인 한 버퍼 내의 데이터를 가상 MRU로 이동시키지 않아 도 히트가 발생할 수 있는 데이터라면 가상 MRU를 사 용할 필요가 없게 된다. 그림 6에서 본 바와 같이 버퍼 크기가 커질수록 LRU 대비 QLRU의 효과가 줄어드는 것을 통해 이를 확인할 수 있다 요청시간 간격에 따른 효과 다음으로 NCQ에 대기 중인 명령들의 개수가 QLRU 알고리즘에 미치는 영향을 살펴보기 위해 워크로드 A의 밀집도(density)를 조정하며 실험하였다. 즉, 쓰기 명령 이 요청되는 시간 간격을 조정하여 명령이 빈번하게 요 청되는 바쁜 상태(busy state)와 드물게 요청되는 유휴 상태(idle state)에서 QLRU의 효과가 어떻게 변화하는 지 측정하였다. 그림 6 버퍼 크기 및 최대 큐 길이에 따른 버퍼 히트율 Fig. 6 Hit ratio as a function of buffer sizes and the maximum queue lengths

이는 각 워크로 드에서 입출력을 수행한 쓰레드가 서로 균등한 입출력 빈도를 갖고 있으며, 이 때, 상대적으로 작은 크기의 파 일에 대해 입출력을 수행하는 쓰레드에서 필요로 하는 데이터는 거의 대부분 버퍼에 존재할 수 있기 때문이다.

7 172 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) 그림 7 조정 값에 따른 평균 큐 길이 Fig. 7 Avg. queue length as a function of scaling factor 그림 8 조정 값에 따른 버퍼 히트율 Fig. 8 Hit ratio as a function of scaling factor 그림 9 조정 값에 따른 쓰기 대역폭 Fig. 9 Write bandwidth as a function of scaling factor 그림 10 조정 값에 따른 IOPS Fig. 10 IOPS as a function of scaling factor 그림 7에서 볼 수 있는 조정 값(scaling factor)이란, NCQ에 명령들이 가득 차서 저장 장치의 바쁜 상태를 1 로 정의하고, 요청시간 간격을 조정 값 비율만큼 증가시 켜 서서히 유휴 상태로 만들어 가며 실험하기 위해 사 용하였다. 이전 실험에서와 마찬가지로 버퍼 크기를 32 MB, NCQ의 최대 큐 길이는 512이다. 먼저, 그림 7은 각 조정 값에 따라 평균적으로 큐에 쌓이는 명령들의 개수를 나타낸다. 조정 값이 1일 때 쓰 기 명령이 빈번하게 요청되며, 평균 큐 길이는 최대 길 이인 512에 가깝게 나타나고, 조정 값이 늘어감에 따라 명령의 요청시간 간격이 늘어나 점점 평균 큐 길이가 줄어드는 것을 확인할 수 있다. 또한, QLRU는 과거의 참조 패턴 정보 뿐만 아니라 미래의 참조 패턴 정보를 활용함으로써 버퍼의 히트율이 증가하게 되고, 이에 따 라 SSD 장치의 처리능력이 향상되어 평균 큐 길이가 LRU보다 짧게 나타나는 것을 확인할 수 있다. 그림 8은 그림 7과 같은 조정 값들에 따른 버퍼의 히 트율을 실험한 결과이며, 큐에 얼마나 많은 명령이 존재 하느냐에 따라 QLRU의 히트율이 달라지는 것을 확인 할 수 있다. LRU에서는 워크로드의 요청시간 간격에 의한 평균 큐 길이에 상관없이 동일한 히트율을 유지하 는 반면, QLRU에서는 큐에 쌓인 정보의 양이 많을수록 높은 히트율을 보이며, 평균 큐 길이가 줄어들수록 LRU 의 히트율에 근접하게 된다. 그림 9와 그림 10은 그림 8과 동일한 실험에서 쓰기 대역폭(write bandwidth)과 IOPS(Input / Output Operations Per Second) 성능을 측정한 결과이다. 여기서도 마찬가지로, 큐에 명령들이 많을수록 LRU 대비 QLRU 의 성능향상 폭이 가장 높고, LRU는 거의 동일한 성능 을 나타낸다. 다만, 조정 값이 일정 이상이 되면 LRU 성능도 함께 떨어지는 것처럼 보이는데 이는 유휴 구간 이 늘어남에 따라 쓰기 대역폭이나 IOPS가 점차 떨어 지기 때문이다 실제 워크로드 실험을 통한 QLRU의 효과 실제 워크로드를 사용해 QLRU의 효과를 검증하고, 동작 간에 발생하는 현상을 분석하기 위해 표 2와 같은 특성의 두 가지 워크로드를 사용하였다. OLTP 워크로 드는 금융기관에서 실행되는 OLTP(Online Transaction Processing) 응용 프로그램에서 추출한 워크로드로 써, 데이터 입력 및 거래 조회 등을 위한 트랜잭션 지향 의 접근 패턴으로 작은 요청 크기로 임의 접근이 발생 되는데, 쓰기 명령이 발생하는 데이터 입력 패턴에서 비 교적 높은 지역성을 갖고 있다. kernel compile 워크로 드는 커널 컴파일 수행 중의 저장장치 입출력을 직접 추출한 워크로드로써, 여러 가지 소스 파일들에 대한 입 출력 명령이 수행되어 지역성이 매우 낮으며, 비교적 다

10 IOPS as a function of scaling factor 그림 7에서 볼 수 있는 조정 값(scaling factor)이란, NCQ에 명령들이 가득 차서 저장 장치의 바쁜 상태를 1 로 정의하고, 요청시간 간격을 조정 값 비율만큼 증가시 켜 서서히 유휴 상태로 만들어 가며 실험하기 위해 사 용하였다.

8 SSD 장치 내 NCQ를 활용한 쓰기 버퍼 관리 기법 173 표 3 실제 워크로드의 특성 Table 3 Characteristics of the real workloads OLTP kernel compile The number of requests The ratio of write request % 75.15% Avg. request size 4KB 28 KB Avg. inter-arrival time 85 ms 61 ms 양한 요청 크기의 명령들로 이루어져 있다. 실험을 위해 먼저 쓰기 버퍼의 크기를 32MB, NCQ의 최대 큐 길이 를 512개로 설명하였다. 실험을 통해 LRU와 QLRU에 서의 버퍼 히트율을 측정한 결과, OLTP 워크로드는 LRU에서 60.3%, QLRU에서 60.4%로 측정되어 버퍼 히 트율의 절대 수치가 0.1% 상승하였고, kernel compile 워크로드는 LRU에서 7.5%, QLRU에서 8.6%로 측정되 어 버퍼 히트율의 절대 수치는 1.1% 상승되어 OLTP보 다 kernel compile에서 QLRU의 성능향상 폭이 상대적 으로 높았음을 확인할 수 있었다. 이는 OLTP 워크로드 는 지역성은 높은 편이지만 요청 크기가 작음에 따라 NCQ가 보유 할 수 있는 정보의 양이 매우 적기 때문 에 QLRU에 의한 효과를 충분히 얻을 수 없었던 반면 에, kernel compile 워크로드는 지역성은 낮지만 각 요 청 크기가 상대적으로 커서 NCQ가 보다 많은 정보를 보유할 수 있었기 때문이다. 하지만 두 가지 실제 워크 로드에서 성능향상의 절대치는 매우 낮은 수치를 보였 는데, 이는 OLTP와 같이 요청 크기가 너무 작아서 NCQ가 보유할 수 있는 정보가 너무 적으면 QLRU의 이점을 제대로 활용할 수 없다는 것과, kernel compile 과 같이 워크로드의 지역성 때문에 버퍼 히트율이 너무 낮은 워크로드는 QLRU를 제대로 이용하기 위해서 더 많은 NCQ 길이를 요구하기 때문에 사실상 성능향상을 기대하기 힘들다는 것이 원인으로 분석되었다. 5. 결 론 본 논문에서는 SSD 내에 존재하는 NCQ를 고려한 쓰기 버퍼 관리 기법을 제안하였다. 이 기법은 과거의 참조 패턴 정보를 활용할 뿐만 아니라, 앞으로 처리할 명령들이 대기하고 있는 NCQ를 통해 미래 참조 패턴 정보를 획득함으로써, 버퍼의 히트율을 향상시킬 수 있 었다. 실험 결과, 과거의 참조 패턴 정보에만 의존하는 LRU와 비교하여 미래의 참조 패턴 정보까지 활용 가능 한 QLRU가 대부분의 환경에서 더 높은 성능을 보였다. 특히, NCQ로부터 획득할 수 있는 정보의 양이 많을수 록 즉, NCQ의 최대 길이가 길수록 혹은 NCQ에 대기 하는 명령들의 개수가 많을수록 높은 성능향상을 얻을 수 있었다. 무엇보다 제안한 기법은 SSD 내에서 그동 안 사용되지 않았던 NCQ가 지닌 정보를 버퍼 관리 기 법을 위하여 활용하였기 때문에, 기존에 연구되었던 어 떠한 다른 쓰기 버퍼 관리 기법들에 쉽게 적용할 수 있 다는 큰 장점이 있었다. 하지만 제안하는 기법에서 OLTP 및 kernel compile 과 같은 실제 워크로드에서의 성능향상 폭이 매우 낮다 는 문제점을 보였는데, 이는 QLRU가 워크로드의 지역 성, 입출력 크기, 입출력 명령의 요청 빈도와 수에 따른 제한적인 환경에서 효과적으로 활용할 수 있기 때문이다. 이에 따라 향후 연구로 QLRU를 효과적으로 활용할 수 있는 엔터프라이즈(enterprise)급 시스템에 대한 연 구와 실험을 진행하고, 다양한 버퍼 관리 기법과 함께 동작시키는 것에 대한 연구를 진행할 예정이다. References [1] H. Jo, J.-U. Kang, S.-Y. Park, J.-S. Kim, and J. Lee, "FAB: Flash-Aware Buffer Management Policy for Portable Media Players," IEEE Trans. on Consumer Electronics, vol.52, no.2, pp , [2] H. Kim and S. Ahn, "BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage," Proc. of the 6th USENIX Conf. on File and Storage Technologies, pp , [3] S. Kang, S. Park, H. Jung, H. Shim, and J. Cha, "Performance trade-offs in using nvram write buffer for flash memory-based storage devices," IEEE Trans. on Computers, vol.58, no.6, pp , [4] G. Wu, B. Eckart, and X. He, "BPAC: An adaptive write buffer management scheme for flash-based Solid State Drives," Proc. of the 26th IEEE Symposium on Massive Storage Systems and Technologies, pp.1-6, [5] L. Shi, J. Li, C. J. Xue, C. Yang, and X. Zhou, "Exlru: A unified write buffer cache management for flash memory," Proc. of the 9th ACM International Conference on Embedded software, pp , [6] G. Gasior, "Intel s X25-E Extreme solid-state drive," The technical report, [7] Dishi Lai, et al., "METHOD AND APPARATUS FOR EFFECTIVELY INCREASING A COMMAND QUEUE LENGTH FOR ACCESSING STORAGE," U.S. Patent No. 20,130,091,307, [8] KingSpec, "How to obtain maximum performance from your SSD," Company news, [9] E. Seppanen, M. T. OKeefe, and D. J. Lilja, "High performance solid state storage under linux," Proc. of the 26th IEEE Symposium on Massive Storage Systems and Technologies, pp.1-12, [10] Marvell Technology Group Ltd., "88F619x - Integrated Controller Hardware Specifications," Product

3%, QLRU에서 60.4%로 측정되어 버퍼 히 트율의 절대 수치가 0.1% 상승하였고, kernel compile 워크로드는 LRU에서 7.5%, QLRU에서 8.6%로 측정되 어 버퍼 히트율의 절대 수치는 1.1% 상승되어 OLTP보 다 kernel compile에서 QLRU의 성능향상 폭이 상대적 으로 높았음을 확인할 수 있었다.

9 174 정보과학회논문지 : 시스템 및 이론 제 41 권 제 4 호(2014.8) specifications, [11] S. Baumann, G. de Nijs, M. Strobel, and K.-U. Sattler, "Flashing Databases: Expectations and Limitations," Proc. of the 6th International Workshop on Data Management on New Hardware, pp. 9-18, [12] A. Gupta, Y. J. Kim, B. Tauras and B. Urgaonkar, "FlashSim: A Simulator for NAND Flash-Based Solid-State Drives," Proc. of the International Conference on Advances in System Simulation, pp , [13] D. D. Levine, "Iometer User's Guide," Intel Server Architecture Lab 김 성 민 2011년 광운대학교 컴퓨터공학과 졸업 (학사). 2014년 광운대학교 컴퓨터공학과 졸업(석사). 2014년~현재 광운대학교 컴 퓨터공학과 박사과정. 관심분야는 운영체 제, 플래시 메모리, 차세대 비휘발성 메 모리 등 김 태 석 2000년 서울대학교 전산과학과 졸업(학 사). 2002년 서울대학교 컴퓨터공학부 졸 업(석사). 2007년 서울대학교 컴퓨터공학 부 졸업(박사). 2007년~2008년 삼성전자 책임연구원. 2008년~현재 광운대학교 컴 퓨터공학과 조교수. 관심분야는 운영체제, 스토리지 시스템, 임베디드 시스템 등

Urgaonkar, "FlashSim: A Simulator for NAND Flash-Based Solid-State Drives," Proc. of the International Conference on Advances in System Simulation, pp. 125-131, 2009. [13] D. D. Levine, "Iometer User's Guide," Intel Server Architecture Lab.

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA 166 정보과학회논문지 : 시스템및이론제 41 권제 4 호 (2014.8) SSD 장치내 NCQ 를활용한쓰기버퍼관리기법 (A Write Buffer Management Scheme Exploiting the NCQ of SSDs) 김성민 김태석 (Seongmin Kim) (Taeseok Kim) 요약본논문에서는 SSD(Solid-State Drives) 내의