[FTL 기술흐름]

요즘 FTL에 대한 연구를 하고 있는데 그동안 연구되었던 FTL의 기술 발전 흐름을 정리해 보았습니다. 

• NAND flash의 단점과 FTL의 등장

  NAND flash는 비 휘발성 메모리 저장장치로 사용하기에 적합하다. 그 이유는 용량대비 가격이 저렴하기 때문이고, 대용량 device를 만들기 용이하기 때문이다. 하지만, NAND flash는 태생적인 단점이 몇 가지 있다.

  • Byte 단위의 접근을 허용하지 않는다. Page단위의 Read/Write 만 가능하다. (XIP 불가능)
  • 덮어쓰기가 되지 않는다. Write를 하기 위해서는 Erase후 program해야 한다.
  • Program과 Erase의 단위가 다르다. Program 하는 단위보다 Erase하는 단위가 월등히 크다
  • Program/Erase 할 수 있는 횟수(P/E cycle)가 무한하지 않다.

     

  이러한 문제 때문에 H/W적으로는 NAND interface protocol 이 S/W적으로는 FTL (Flash Translation Layer)이 필요하게 되었다. FTL 논문을 중심으로 FTL기술이 어떻게 발전해 왔는지 알아보기로 한다.

     

     

• BAST (2002)

  NAND에서 덮어쓰기 동작을 구현하는 가장 간단한 방법은 쓰기 동작시 마다 해당 page가 속한 Block을 통째로 지우고 다시 쓰는 방법을 사용하는 것이다. 하지만, 이 방법은 한 Block내에 속한 page가 update될 때마다 erase되어야 하고 나머지 page들을 copy해 주어야 하기 때문에 성능면이나 NAND의 수명 측면에서 문제가 되었다. 그래서 등장한 것이 Mapping이라는 개념이고 Write cache(log block)라는 개념이다.

     

  

  BAST 는 log block이라는 cache block을 할당하여 write operation을 수행하는 방법을 사용하였다. Log block은 1:1로 연관되는 Data block이 있으며, 해당 Block에 속한 page들을 write한다. In place order로 program해야 하는 Data block과 달리 Log Block은 Out of place order로 write하고 page map을 관리하는 방법을 사용하였다. Log block은 Data block에 비해 매우 작은 숫자이기 때문에 비어 있는 free block이 필요하면 이전에 사용된 Log block의 데이터를 Data block으로 전송하고 erase하는 방법을 사용하였다. 이를 Merge, Migration, Compaction 또는 Garbage collection이라고 한다.

  파일시스템의 write 패턴에 따라 log block이 data block으로 migration되는 방법이 다르다.

  

  유효한 데이터가 Data block과 Log block에 모두 있는 경우에는 Free block에 data block과 Log block에 있는 데이터를 copy한 뒤 Data block과 log block을 erase하여 Free block으로 만든다.(Full merge) 이 때는 2번의 erase, 1Block copy가 발생한다. 유효한 데이터가 Log block에만 있는 경우 Free block에 Log block의 내용을 copy하고 Log block을 erase한다.(Partial merge) 이 때는 1번의 erase와 1 block copy가 일어난다. 마지막으로 log block의 내용이 모두 유효하면서 in place order로 적혔을 때이다. 이 경우는 Log block을 그대로 Data block으로 mapping만 바꿔주면 된다. 이 때는 erase한번만 일어난다.

  Free block을 얻는 목적은 같은데, 시나리오에 따라서 merge하는 비용은 다른 것을 알 수 있다.

  BAST 는 적용이 간단하고 Sequential data의 비중이 많은 응용에서는 높은 성능을 발휘할 수 있어, card나 USB스토리지에서 널리 사용되었다. 하지만, random 패턴에서는 낮은 성능이 문제가 되었다. 또한, page와 Block의 크기가 커지면서 Switch merge의 비중이 줄고 Full merge가 늘면서 복잡한 응용에서의 FTL로는 부족한 점이 많았다.

  하지만, 적은 리소스로 큰 용량의 NAND를 관리할 수 있다는 점과, 초창기 NAND의 한계를 극복할 수 있다는 가능성을 제시한 의미있는 논문이다.

     

• FAST, Superblock (2006)

  BAST이후 이 분야에 대한 연구도 활발해 졌다. FAST와 Superblock은 BAST를 기본으로 하면서 BAST 의 단점인 Full merge의 비율을 줄이는데 초점을 두었다.

  

  BAST-위 그림의 (a)의 특징은 Update(log) block과 Data block이 1:1로 대응된다는 점이다. 만약 파일시스템의 Write 패턴이 random이면서 그 범위가 다양하다면(여러 Block boundary를 넘나든다면) I/O의 크기에 비해 많은 수의 log block이 필요로 하게 된다. 이는 log block이 다 차기도 전에 migration하는 결과를 가져와 빈번한 merge로 인해 성능효율성이나 write한 용량대비 많은 erase횟수 유발하게 된다. 게다가 이 때 merge는 full merge나 partial merge이 된다.

     

  FAST는 Update block과 Data block 의 연관 관계를 1:1 에서 1:N으로 확장하여 한 Update block에 여러 Data block이 연관 될 수 있게 하였다. 이렇게 되면 한 Update block에 여러 data block의 data를 담을 수 있어 넓은 범위의 random write가 발생하는 경우 BAST 보다는 Update block에 최대한 많은 양의 data를 write할 수 있었다.(공간 이용도가 높아진다). 하지만, N이 커지면 커질 수록 Migration하는 비용이 커지고, mapping 데이터 양이 커지는 단점이 있다. 즉, migration하는 횟수는 줄었지만, 반대로 비용은 커진 것이다.

     

  Superblock 은 FAST의 연장선에서, FAST의 1:N을 유지하면서도 인접한 Data block을 Group으로 묶어 Superblock이라 칭하고 Superblock내에서는 out of place로 관리하여 Migration 비용을 줄이고자 하였다. 장점은 BAST에 비해 Update block의 활용이 많고, superblock내에서는 out of place로 관리하기 때문에 partial merge를 switch merge로 대신할 수 있다는 장점이 있다. 하지만, superblock도 merge를 해야 하기 때문에 full merge시 비용이 큰 단점이 있다. 또한, out of place map을 유지하는 비용도 추가로 필요하다.

     

• SAST (2007)

  BAST 와 FAST 는 각각 장.단점이 있다. BAST 는 메모리사용량이 적은 반면, random 패턴의 write시 log block활용도가 낮아 잦은 merge가 일어나고, FAST는 Disk 공간 사용도가 높은 반면 garbage collection의 비용이 큰 단점이 있다. 이를 적절하게 조절할 수 있는 N:N+K mapping 알고리즘이 제안되었다.

  

  SAST 는 Log block과 Log block에 연관되는 Data block의 개수를 조절하여 log block의 공간 활용도를 높이면서 log block에 연관되는 data block의 개수를 제한하여 merge 비용을 줄이려고 하였다.

     

• LAST (2009)

  Data의 write 패턴은 Random 과 Sequential, Hot과 Cold로 구분 할 수 있다. 이러한 패턴을 고려한 mapping방법이 제안되었다.

  

     

  LAST는 기본적으로 FAST를 계승하는 알고리즘이다. Random과 Sequential을 구별하여 Log block을 할당하였고, Random log block중에서도 Hot과 Cold를 구별하였다. LAST 는 Random 패턴을 구별하기 위해 Write 요청 단위(4KB)를 사용하였다. Hot과 Cold는 최초 write요청은 cold로 지정하고 같은 주소의 요청이 반복되면 hot으로 변경한다. hot random write를 따로 관리하기 때문에 merge 횟수를 줄일 수 있다.

     

• A-SAST, KAST (2009)

  SAST 이후 이 알고리즘들을 보완하거나 FAST, Superblock의 장점을 융합, 발전시키는 알고리즘들이 등장하였다.

  A-SAST는 기본적으로 SAST의 N:K mapping방법을 사용하지만, N과 K를 runtime시 변경할 수 없었던 SAST 를 개량하여 write 패턴에 따라 동적으로 변경하는 방법을 사용하였다.

  

  A-SAST 는 Log block의 공간 활용도가 떨어질 때는, log block과 연관된 Data block을 늘려 공간활용도를 높이고, 반면 log block의 공간 활용도가 증가하면 log block과 data block의 개수를 줄여 merge 횟 수와 비용을 동시에 줄이는 방법을 제안하였다.

  KAST는 FAST를 바탕으로 하되, 하나의 Log block에 N개의 Data block이 연관되었던 것을 최대 K 개로 제한하였다.

  

  또한, Random log block(RLB)과 Sequential log block(SLB)을 구분하여 data의 패턴에 따라 상호 변환이 가능하게 하였다.

  

  조건에 따라 RLB 를 확장하거나 SLB로 전환하는 방법이 제안되었다. 이 방법의 특징은 data padding을 사용하여 RLB를 SLB로 전환하는 알고리즘이다. Log block에서 대부분 in place order로 write될 수 있는 건인데 조금 틀어진 경우도 swap merge를 유도 할 수 있다.

     

• 결론

  FTL은 BAST 를 시작으로 KAST에 이르기 까지 서로의 장.단점을 계승 보완하여 발전하였다.FTL이 발전되온 과정을 살펴보면 "Merge 횟수 및 비용 최소화"라는 공통적인 목표를 발견할 수 있다. 이 목표는 성능 뿐 아니라 NAND의 수명에도 영향을 미치기 때문에 중요한 요소이다. Merge 횟수와 비용을 줄이려는 노력은 아래와 같은 방법으로 구체화 되었다.

     

  • Log block의 공간 활용도 증대
  • Write 패턴에 최적화된 Log block 운용 (Random / Sequential, Hot / Cold)
  • Log block와 Data block의 연관 관계 다변화 (1:N, N:K)
  • Block mapping 바탕의 부분적인 Page mapping 운용

     

  SSD의 등장으로 고비용 고사양 device의 시대가 열렸다. 또한, NAND의 Block 및 page의 크기가 계속해서 증가할 것이므로 Block mapping에는 한계가 있다. 따라서 Block mapping의 일부분을 Page mapping으로 보완하려는 시도가 좀 더 발전 할 것으로 예상된다.

  또한, 평균 merge비용 뿐 아니라 순간 최고 merge 비용에 대한 연구, NAND의 공정이 미세화 될 수록 점점 특성이 나빠지는 현상을 고려한 연구도 필요할 것으로 생각된다.