[ASPLOS 2009] DFTL

Gupta, A., Kim, Y., and Urgaonkar, B. 2009. DFTL: a flash translation layer employing demand-based selective caching of page-level address mappings. In Proceeding of the 14th international Conference on Architectural Support For Programming Languages and Operating Systems (Washington, DC, USA, March 07 - 11, 2009). ASPLOS '09. ACM, New York, NY, 229-240.

하드디스크는 해당 데이터를 찾기 위해서 기계적으로 헤더를 움직이고 플래터를 고속으로 회전 시켜야 하기 때문에 delay가 길고 또한 파워를 많이 소비한다. 반면 Flash 타입의 대용량 메모리는 하드디스크에 비해 파워와 Delay 측면에서 많은 이점이 있다. 그러나 Flash는 데이터를 write 하기 위해서는 반드시 해당 블록을 erase 해줘야 한다. 이러한 특성으로 인해서 workload의 특성에 따라서 Flash 메모리의 성능이 크게 차이가 나게 된다. 예를들어 빈곳에만 데이터를 계속해서 쓰게 된다면 erase 작업이 필요없으므로 성능이 좋을 수 있으나 데이터가 쓰여진 블록을 계속해서 write 하게 되면 당연히 성능이 저하될 수 밖에 없다. erase-before-write 현상을 줄이기 위해서 Flash Translation Layer(FTL)을 사용하게 되며 이는 virtual 주소와 physical 주소를 변환해주는 역할을 한다. 이 논문은 새로운 Demand-based FTL을 제안하고 있으며 flash 기반 device에서 random write의 성능을 높이는 것이 목표이다.

먼저 간략하게 FTL에 대해서 알아보면,
virtual-to-physical address mapping을 위하여 작고 빠른 SRAM을 사용한다.
(Flash는 RAM에 비해 느리기 때문에 Flash 메모리를 mapping table로 사용하게 되면 너무 overhead가 크다.)

두가지 방법이 있는데 Page-level FTL과 Block-Level FTL이 있다.
Page-level로 매핑 테이블을 관리하게 되면 효율적으로 Flash를 사용할 수 있기때문에 좋지만 그대신 mapping table이 너무 커지게 된다. 16GB용량에 2KB 크기의 page를 사용할 경우 32MB의 SRAM이 필요하다. 크헉. 너무비싸!
Block-level로 매핑 테이블을 관리하면 적은 SRAM으로 가능하지만 garbage collection(GC)의 비용이 너무 많이 든다.
그래서 Page-level과 Block-level의 중간적 형태인 Hybrid FTL이 제안되고 있다. (이 논문의 DFTL도 Hybrid-FTL의 일종이다.)
하이브리드 FTL은 Data와 Log 블록으로 나누어지며 Data 블록은 block-level, Log 블록은 page-level mapping을 담당한다.
하이브리드 FTL에서 GC는 더 이상 유효한 log block이 없을 경우 수행되며 log block과 data block을 merge하는 것이다.
GC에는 기본적으로 3가지가 있으며 다음과 같다.

(a) Switch Merge의 경우 LPN(Logical Page Number)가 동일하지만 Data Block A에서는 모두 I 상태(Invalid)이기 때문에 모두 V 상태(Valid)인 Log Block B로부터 Switch만 하면 된다.

(b) Partial Merge의 경우는 부분적으로만 유효한 경우 유효한 놈들끼리 모아서 하나의 Valid한 Block을 만들 수 있다. 그리고 Data Block을 날려버리면 공간이 확보된다.

(c) Full Merge는 여러 블록으로부터 가져와야 하는 경우인데 이미 지워진 또다른 블록에다가 부분적으로 유효한 페이지들을 모아서 넣는다. 나머지는 지워버려서 공간을 확보할 수 있다.

그런데 Full Merge를 수행하는 것은 비용이 매우 비싸겠지. 여러테이블에서 가져와야 하고 심지어 네개의 블록에서 하나의 블록을 만들게 될 수도 있으니까.

 이러한 문제점을 해결하기 위해서 이 논문은 다음과 같은 DFTL이란 새로운 scheme을 제안하고 있다.

DFTL은 기본적으로 Page-level mapping을 사용한다. 아까 page-level mapping을 하게 되면 SRAM의 크기가 커져서 비용이 매우 많이 든다고 했는데 ..... ㅋㅋ. 그래서 DFTL은 page-level mapping 테이블을 FLASH에다 저장한다. 그럼 SRAM에 비해서 너무 느려지는데.... ㅋㅋ. 그래서 SRAM에서 이 mapping table을 caching 한다. ㅋㅋ
 

어떻게 동작하는지 볼까? (아놔 나 너무 친절한듯..ㅋㅋ)

LPN이 1280인 Data Page를 요구한 경우
(1) Cached Mapping Table에서 해당 DLPN을 찾는다. 그러나 이경우에는 없네. 아놔 여기 있으면 바로 데이터로 접근이 가능한데. 우띠. 그럼 일단 CMT를 하나 버려야겠군. Victim entry로 DLPN 1이 선택되었다.
(2) DLPN=1, DPPN(Physical Page Number)=260인데 DLPN=1이니까 512로 나누어 내림하면 0이니 Global Translation Directory(GTD)에서 MVPM이 0번을 찾는다. MPPN은 21이네.
(3) MPPN이 21이니 Translation Block에서 MPPN=21인 걸 찾으니 가운데것이군. 근데 Valid인 블록에서 한 Page만 업데이트가 불가능하니(왜냐하면 Flash는 블록단위로 쓰기가 가능하니까) 다른 빈놈에다가 이걸 옮기고 값을 업데이트 해야하는군.
(4) 그래서 MPPN=23인 놈에 DLPN=1인 부분은 260으로 바꾸면서 MPPN21의 데이터를 전부 복사한다. 이제 MPPN=21은 더이상 쓸모 없으니 Invalid 상태로 만들고 MPPN=23은  Free->Valid로 변경. (크흑 아직 반도 안왔어.)
(5) MPPN=23으로 변경되었으니 GTD에도 반영을 해줘야해.
(6) GTD MVPN=0, MPPN=21을 MVPN=0, MPPN=23으로 변경 (이놈은 SRAM이니까 부분 업데이트가 바로 돼)
(7) 아놔 이제 다 공간을 맹글어놨으니까 아까 1280번 처리를 다시 시작해보자. DLPN=1280이니까 512로 나누면 2. MVPN=2가 되는군
(8) MVPN=2인 곳은 MPPN=15네. TB에서 MPPN=15를 찾아.
(9) DLPN=1280인 놈은 DPPN이 660이구만.
(10) 자 이제 DPPN도 찾았으니 이걸 CMT에다 업데이트를 해. DLPN=1280, DPPN=660
(11) DPPN=660에서 Data를 찾아서 되돌려주면 끝! (아놔 길다. 데이터 한 번 얻기 참 힘드네. 어휴)