Digital Recipe

ExLRU 본문

컴퓨터 공학/(분야별) 스토리지(SSD)

ExLRU

노리터 2012. 1. 30. 19:59
논문제목 : ExLRU : A United Write Buffer Cache Management for Flash Memory

논문저자 : Liang Shi, Jianhua Li 외 3인 From Dept. of Computer Science, City Universirt of Hong Kong, Dept. of Computer Science, University of Science and Technology of China.

논문발표 : EMSOFT '11



1. Introduction

SSD는 Wirte 연산이 Read 연산보다 느리며 각 Flash는 제한된 수명을 가지고 있다. 이러한 특성 때문에 SSD 내부에 에 Write Buffer을 두어 SSD의 성능을 향상시키고 있다. 기존 Flash의 특성을 고려한 버퍼 관리 기법으로 FAB과 BPLRU이 있으며 이 알고리즘은 Block이 가지고 있는 정보 (Block-level, 예를 들어 같은 블록 내 속하는 페이지가 얼마나 있는가등)만을 가지고 버퍼 안의 데이터를 관리한다.


2. Related Work

FAB 


버퍼 내 모든 데이터는 같은 Block 내에 속하는 Page들의 집합으로 관리되며 버퍼에서 데이터 교체가 일어나는 경우 가장 크기가 큰 Block( 해당 Block에 속하는 Page가 많은 Block )을 Flush하게 된다. 따라서 연속적인 쓰기 패턴(Sequential Write Pattern)에 강한 모습을 보인다. (그림1)

그림1. FAB


BPLRU
 


버퍼 내 모든 데이터는 같은 Block 내에 속하는 Page들의 집합으로 관리되며 버퍼에서 데이터 교체가 일어나는 경우 가장 오랫동안 참조되지 않았던 Block이 Flush된다. 기본적으로 LRU로 관리되며 해당 Block이 관리하는 Page 중 하나라도 재참조가 일어나는 경우 Block 전체가 MRU 위치로 이동하게 된다. 따라서 임의적인 쓰기 패턴(Random Write Pattern)에 강한 모습을 보인다. (그림2)

그림2. BPLRU


이와 같은 기존의 관련 연구들은 하나의 Block이 얼마나 많은 Page를 가지고 있는지? 혹은 해당 Block이 가진 Page가 참조된지 얼마나 되었는지?와 같은 Block-Level 정보를 활용하여 버퍼 안의 데이터를 관리한다.



3. 기존 관련 연구의 문제점


기존 관련 연구들은 Block-Level 정보를 활용하여 버퍼를 관리하기 때문에 아래와 같은 문제점이 발생하게 된다.

1. Slow retirement of large cold blocks
Block이 가진 Page들이 Cold하더라도 많은 Page를 보유하고 있으면 재참조될 확률이 높아져 버퍼에서 교체될 확률이 줄어든다.

2. Early eviction of small hot blocks
Block이 가진 Page가 Hot하더라도 적은 Page를 보유하고 있으면 문제점 1번과 비교하여 재참조될 확률이 떨어진다.

3. Cold page retention in heat-imbalanced blocks.
Block이 많은 Cold Page와 적은 Hot Page를 가지고 있을 때 Hot Page에 의하여 Cold Page까지 계속 보유하게 된다.

이렇게 Block-Level 정보를 활용하는 경우 문제가 발생하기 때문에 이 논문에서는 Page-Level 정보를 활용한 버퍼 관리 기법을 제안한다.


4. 제안하는 버퍼 관리 기법 ( Cost Model of ExLRU )

그림3. ExLRU를 위한 조직도

[그림3]을 보면 ExLRU를 위해 Block은 자신이 얼마나 많은 Page를 가지고 있는지 정보(Pcnt)를 가지고 있으며 각 Page들은 자신이 얼마나 많이 재참조되었는지(Hit_Count), 언제 처음 요청되었는지(Request_number) 정보를 추가적으로 가지고 있다.

이러한 조직에서 각 페이지 별로 얼마나 자주 참조되는지 확인하기 위해 페이지가 재참조된 횟수를 자신이 버퍼에 머무른 시간으로 나눠 각 페이지마다 단위시간당 재참조율을 계산한다. (논문 Definition 1 참고)

이를 다시 Block가 가진 Page의 갯수로 나눠서 각 Block마다 단위시간당 재참조율을 계산한다. (논문 Definition 2 참고)

Definition 2의 결과값은 Block이 가진 Page 갯수에 따라 달라질 수 있기 때문에 이를 다시 Block이 가진 Page의 갯수로 나눠서 Block이 가진 Page 갯수와 관계없는 Block마다 단위시간당 재참조율을 계산한다. (논문 Definition 3 참고, 이후 UC값이라고 칭함)

이렇게 계산된 값 중 가장 작은 값을 가지는 Block을 버퍼 교체 수행시 희생하게 된다.



5. Efficient ExLRU

4번에 기술한 ExLRU는 오버헤드가 크기 떄문에 Efficient ExLRU를 제안한다.
Efficient ExLRU는 두 개의 Write Request 사이의 idle time에 수행되며 가장 낮은 계산결과값이 아닌 충분히 낮은 계산결과값을 가진 Block을 버퍼에서 Flush하는 것을 목표한다.

Efficient ExLRU는 2번의 프로세스로 이루어진다. Scanning Process와 Victim block selection process이다. 버퍼의 공간은 Work Region(WR)과 Eviction Region(ER)로 나눠져서 관리된다. idle time에 WR지역에 있는 Block 중 UC값이 일정 임계값(Tuc)보다 낮은 Block을 ER로 이동시키게 된다. 이후 ER지역에 있는 Block 중 가장 오랬동안 참조되지 않았던 Block을 버퍼에서 Flush하게 된다.






2012. 01. 30
Posted By HoSeok Seo
Comments