2. SSD의 깊숙한 이론! Log buffer-based FTL (BAST , FAST)
이하 내용은 논문 A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation 을 참고하고, 정리하였다. SSD의 이론적 내용을 이해하는 데 아주 좋은 갓갓갓 논문이다.
1. FTL 과 flash memory
FTL(flash translation layer) 은 file system과 NAND flash memory사이의 소프트웨어 계층이다. SSD는 host가 생각하는 logical address와 flash에 실제 저장되는 physical address가 서로 다르다. 이 부분을 속도(band width) 향상을 위해서 erase연산을 최소화시키는게 핵심이므로, ftl은 이 목표에 맞게 맵핑위치를 정한다. FTL은 두가지 기능이 또한 있는데, consistency 와 uniform wear leveling 이다.
-consistency라 함은 ssd가 예상치못하게 전원이 나가도 mapping table을 온전히 보존하여야 한다는 것이다. 이를 위해 ssd는 flash memory 에 또한 mapping table을 보관하고, 이를 주기적으로 sdram의 mapping table과 synchronize 시켜준다.
-uniform wear leveling : flash memory의 각 block 은 하드웨어 특성상 erase 횟수가 제한되어 있다. 예를 들어 10000번의 erase를 한 block 에서 하고나면 그 block은 다시는 사용할 수 없게 되어버린다. 이를 예방하기 위해 FTL은 다양한 block 에 골고루 write를 하도록 구현되어야 한다.
FTL에는 여러 이론이 있지만, 우리가 이번에 다룰 것은 바로 log FTL이다.
2. block-level mapping VS sector-level mapping
FTL은 logical address와 physical address를 연결해주는 mapping table을 가지고 있다. (sdram) 여기서 이슈는, 맵핑단위를 block 단위로 하느냐, sector 단위로 하느냐이다.(1block = 4 sector 가정)
-block-level mapping table vs sector-level mapping table
block mapping의 장점은 mapping table size를 줄일 수 있다는 것이다. mapping table size는 너무나 중요한 cost인데 이유는 비싼 sdram에 저장되기 때문이다. sector단위의 mapping table에 비해 block 단위의 mapping table 은 4배로 size가 줄어들기 때문에 비용면에서 아주 유리하다.
예를 들어보자. flash memory size = 100G, 1 sector = 512 byte 라고 했을때, mapping table에 저장되어야 하는 맵핑갯수는 100G/512 byte = 2억개에 육박한다. 한 맵핑사이즈를 4byte 로 잡아도, 8억 byte=800MB의 mapping table이 필요한 것이다. 그런데 이를 블락사이즈단위로 계산시, 200MB의 맵핑테이블이면 된다.
반면으로 sector mapping 의 장점은 flexible 하다는 것이다. 예를 들어 임의의 한 sector를 overwrite시킬 경우, sector단위의 mapping table에 기존의 sector을 invalid 시키고 (-1) 새로운 physical address를 한 sector만 할당하여 mapping table에 업로드시키면 된다. 반면에 block 의 경우에는 아주 골치아프다. block-level mapping table에는 block단위로만 맵핑 되어있을 뿐, sector offset은 logical address 와 physical address 를 같은 아이로 취급한다.(그림 1)
여기서 문제는 sector단위의 overwrite시, 이를 맵핑시킬 방법이 없다는 것이다. 따라서 block mapping table은 블락을 통째로 free block 에 copy하고, 원래 block 을 erase하고, write를 수행해야 한다. 이는 매우 cost가 비싼 일이다.
이와 같은 문제를 해결하기 위해 양쪽의 장점을 취합한 hybrid 방식을 사용한다. 즉, sector 단위의 mapping table과 block 단위의 mapping table을 전부다 사용하는 것이다. 이 방식을 이용한 대표적인 녀석이 log ftl 이다.
3. log FTL
log FTL 의 구조는 다음과 같다. mapping table 은 block단위, sector단위로 나누어 가지고 있으며, 실제 data가 저장되는 block 은 다수의 data block과 소수의 log block으로 나누어 관리한다.
여기서 log block 은 overwrite시 write를 하게된다. 즉, 기존의 ftl은 overwrite를 하게 되면, block을 통째로 copy하고 free block을 할당하여 write하고, 기존의 block을 erase해야 한다. logblock에 대신 이를write함으로써 이 cost높은 erase과정을 최대한 뒤로 미루어보자는 것이다.
4. log FTL - BAST
BAST에서 overwrite된 녀석들은 우선적으로 log block 에 저장된다.
그러나, log block이 가득 차거나, 특정 data block에 대응(그림 3)되는 log block이 없는 경우에는 새로운 log block 을 할당해주어야 한다. 할당하는 방식은 merge operation 과 switch operation 이 있다.
-merge operation
merge operation은 대채적으로 사용되는 방식으로써, 그림 4와 같은 방식으로 새로운 new block 을 할당한다. log block을 할당해야하는 경우가 생기면 아래와 같이 행동한당.
1. log block과 data block에서 최신정보만을 free block에 copy 한다. 이 free block은 data block으로 재설정하기위해 block단위 mapping table을 업로드한다.
2. 기존의 log block, data block을 erase 한다.
3. 새로운 log block을 할당한다.
이 과정에서 2 erase + 1 copy를 거치게 된다. swith operation은 이 연산을 조금더 줄여준다.
-switch operation
switch operation은 sequential write시 사용하게 되는 더욱 효율적인 operation이다. sequential write의 대표적인 예는 사진 저장이 있겠다. 이런 경우, log block 에는 그림5와 같이 block4와 같은 순서로 저장하게 되는데, 이 경우 굳이 cost가 비싼 merge operation을 수행 할 필요가 없다.
1. exchange : block mapping table에서 data block4의 physical address 를 해당 log block 으로 바꾼다.
2. erase : 기존 data block 4를 erase한다.
3. 새로운 log block을 할당한다.
이 과정에서는 1 erase + 1 copy의 과정을 거치게 된다. 즉, merge operation보다 한번 덜 erase 하는 이득을 맛볼 수 있다.
-BAST의 한계
BAST 의 한계는 특정 data block내의 page들은 한 log block 에만 대응될 수 있다(그림 3)는 특성에서 비롯된다. 이로 인해 block thrashing과 block-level associativity 가 발생하여 low-space utilization을 낳는다.
-block thrashing : 1block= 4sectors이고 log block이 2개 있다고 가정하자. p0, p4, p8, p12, p0 ... 과 같은 식으로 write명령이 host로부터 오면 p8부터 매우 아쉬운 일이 벌어진다.
그림6을 보면, p8을 write하기 위해서는, block9에 대응되는 log block을 생성하기 위해서 3sectors가 비어있는 log block을 erase한다. 이를 block thrashing이라고 한다. 이후로 p12, p0 ...을 write할때도 같은 문제가 발생한다. 이 경우 space utilization = 0.25가 된다.
-block-level associativity : 이 문제는 한 블락의 페이지만 집중적으로 write 할때 발생하는 문제이다. 예를 들어, p0,p2,p1,p3,p1,p0,p2... 와 같은 방식으로 write를 하게 되면 p1 부터 다음과 같은 문제가 발생한다.
그림 7을 보면 아직 logblock이 하나 남아있는데도 불구하고 erase 를 수행하고 새로운 log block 을 할당한다. 이후로도 계속 block7에 집중적으로 할당하면 한 log block만을 사용하게 되는 문제가 발생한다. 이 경우 space utilization=0.5이다.
-BAST 정리
BAST는 log block을 추가하여 erase 연산을 획기적으로 줄이고 속도를 끌어 올린 점에서 큰 의의가 있다. 또한, mapping table로 block-level 뿐 아니라 sector-level도 관리함으로써 sdram의 size를 줄이는 동시에 flexibility를 확보하였다. 그러나 이 좋은 BAST도 log block 과 data block 이 1:1 대응이라는 부분에서 여러가지 문제점이 발생하였고 그 결과는 low space utilization으로 이어졌다. 다음에는 이 BAST의 문제를 해결하기 위한 방식인 FAST를 알아보고자 한다.
5. log FTL - FAST(Fully-Associative Sector Translation)
앞서말한 BAST의 한계는 log block과 data block 이 1:1 대응이라는 특성에서 비롯된 것이었다. FAST는 이 특성을 없애고 fully-associative방식을 채택했다. 즉, log block에 data block이 자유롭게 대응될 수 있는 것이다. 하지만 그 과정에서 BAST의 강점이었던 sequential write일 경우에 merge 를 switch operation으로 바꿀수 있는 특성이 사라지고 말았다. 이를 보완하기 위하여 FAST는 log block을 1개의 SW(sequential wrtie) log block 과 다수의 RW(random write) log block 으로 나누게 되었다.
-FAST 구조
FAST 는 BAST의 구조와 거의 유사하다. 다만 log block 이 sequential write를 담당하는 SW log block 1개와 random write를 담당하는 다수의 RW log block 로 구성되어 있다는 차이가 있다.
-FAST read / write
overhead in read operation : 우선 FAST 은 read operation 에서 약간의 overhead가 나타난다. read 를 하는 과정에서, FTL 은 가장 최신의 data 를 sector-level mapping table로 부터 찾는 과정을 거치는데, fully associative 이기 때문에 block단위가 아닌 sector-mapping table 통째로 다 찾아보아야 한다. 그러나 이 over head는 전체 read시간에 비하여 미미한 편이다. (약 10% 미만)
write operation
FAST는 무엇을 기준으로 SW log block 에 write를 하고 RW log block에 write를 할까? 이는 lsn(logical sector number) 에 달려있다. SW log block 의 목적은 Sequential한 buffer 을 write 할 때, 이를 캐치하고 switch operation이 가능하도록 설정하는 것이다. 알고리즘은 이를 가능케 하도록 구성된다.
즉, 1block=4sectors라 하면, lsn%4=0 이되는 lsn이 overwrite될 경우에 RW log block이 아닌 SW log block으로 write된다. 이후에는 lsn%4=1 이 되는 lsn이 overwrite될 경우 SW log block에 write된다. 이와 같은 방식으로 SW block 이 가득차면, 이는 merge operation이 아닌 switch operation이 가능해진다. 따라서 sequential write의 경우에 SW log block에 기가 막히게 write 되게 된다. 또, 꽉찰때마다 switch operation이 아름답게 일어난다. SW log block은 겨우 한개에 불과한데, 엄청난 퍼포먼스의 향상이 이루어진다.
그림 8을 예를 들어 보자.
case 1: lsn=4 이므로 lsn%4=0 이 된다. 즉 write 는 SW log block에 일어난다. 여기서 만일 SW log block이 empty하지 않다면 우선 erase를 하고 write한다.
case 2.1: 처음에 SW log block 에 write 되고, 두번째 역시 lsn=5, lsn%4=1이므로 SW log block 에 순차적으로 write 가 일어난다.
case 2.2 : 두번째에서 RW log block 에 write 된다.
case 2.3 : 두번째까지는 SW log block, 세번째는 RW log block 에 write 된다.
SW log block은 lsn%4==0 인 lsn이 write될때 erase가 일어나며, RW log block은 가득 찼을 때 erase가 일어난다.
이에 관련된 알고리즘은 참고하길 바란다.
1. FTL 과 flash memory
FTL(flash translation layer) 은 file system과 NAND flash memory사이의 소프트웨어 계층이다. SSD는 host가 생각하는 logical address와 flash에 실제 저장되는 physical address가 서로 다르다. 이 부분을 속도(band width) 향상을 위해서 erase연산을 최소화시키는게 핵심이므로, ftl은 이 목표에 맞게 맵핑위치를 정한다. FTL은 두가지 기능이 또한 있는데, consistency 와 uniform wear leveling 이다.
-consistency라 함은 ssd가 예상치못하게 전원이 나가도 mapping table을 온전히 보존하여야 한다는 것이다. 이를 위해 ssd는 flash memory 에 또한 mapping table을 보관하고, 이를 주기적으로 sdram의 mapping table과 synchronize 시켜준다.
-uniform wear leveling : flash memory의 각 block 은 하드웨어 특성상 erase 횟수가 제한되어 있다. 예를 들어 10000번의 erase를 한 block 에서 하고나면 그 block은 다시는 사용할 수 없게 되어버린다. 이를 예방하기 위해 FTL은 다양한 block 에 골고루 write를 하도록 구현되어야 한다.
FTL에는 여러 이론이 있지만, 우리가 이번에 다룰 것은 바로 log FTL이다.
2. block-level mapping VS sector-level mapping
FTL은 logical address와 physical address를 연결해주는 mapping table을 가지고 있다. (sdram) 여기서 이슈는, 맵핑단위를 block 단위로 하느냐, sector 단위로 하느냐이다.(1block = 4 sector 가정)
-block-level mapping table vs sector-level mapping table
block mapping의 장점은 mapping table size를 줄일 수 있다는 것이다. mapping table size는 너무나 중요한 cost인데 이유는 비싼 sdram에 저장되기 때문이다. sector단위의 mapping table에 비해 block 단위의 mapping table 은 4배로 size가 줄어들기 때문에 비용면에서 아주 유리하다.
예를 들어보자. flash memory size = 100G, 1 sector = 512 byte 라고 했을때, mapping table에 저장되어야 하는 맵핑갯수는 100G/512 byte = 2억개에 육박한다. 한 맵핑사이즈를 4byte 로 잡아도, 8억 byte=800MB의 mapping table이 필요한 것이다. 그런데 이를 블락사이즈단위로 계산시, 200MB의 맵핑테이블이면 된다.
반면으로 sector mapping 의 장점은 flexible 하다는 것이다. 예를 들어 임의의 한 sector를 overwrite시킬 경우, sector단위의 mapping table에 기존의 sector을 invalid 시키고 (-1) 새로운 physical address를 한 sector만 할당하여 mapping table에 업로드시키면 된다. 반면에 block 의 경우에는 아주 골치아프다. block-level mapping table에는 block단위로만 맵핑 되어있을 뿐, sector offset은 logical address 와 physical address 를 같은 아이로 취급한다.(그림 1)
 |
| 그림 1 |
여기서 문제는 sector단위의 overwrite시, 이를 맵핑시킬 방법이 없다는 것이다. 따라서 block mapping table은 블락을 통째로 free block 에 copy하고, 원래 block 을 erase하고, write를 수행해야 한다. 이는 매우 cost가 비싼 일이다.
이와 같은 문제를 해결하기 위해 양쪽의 장점을 취합한 hybrid 방식을 사용한다. 즉, sector 단위의 mapping table과 block 단위의 mapping table을 전부다 사용하는 것이다. 이 방식을 이용한 대표적인 녀석이 log ftl 이다.
3. log FTL
log FTL 의 구조는 다음과 같다. mapping table 은 block단위, sector단위로 나누어 가지고 있으며, 실제 data가 저장되는 block 은 다수의 data block과 소수의 log block으로 나누어 관리한다.
 |
| 그림 2 출처 : A log buffer-based flash translayer using Fully-associative sector translation |
여기서 log block 은 overwrite시 write를 하게된다. 즉, 기존의 ftl은 overwrite를 하게 되면, block을 통째로 copy하고 free block을 할당하여 write하고, 기존의 block을 erase해야 한다. logblock에 대신 이를write함으로써 이 cost높은 erase과정을 최대한 뒤로 미루어보자는 것이다.
4. log FTL - BAST
BAST에서 overwrite된 녀석들은 우선적으로 log block 에 저장된다.
그러나, log block이 가득 차거나, 특정 data block에 대응(그림 3)되는 log block이 없는 경우에는 새로운 log block 을 할당해주어야 한다. 할당하는 방식은 merge operation 과 switch operation 이 있다.
 |
| 그림 3. BAST 에서 datablock내의 page는 한 log block에만 대응될 수 있다. |
-merge operation
 |
| 그림4.(존 잘 그린듯;) |
merge operation은 대채적으로 사용되는 방식으로써, 그림 4와 같은 방식으로 새로운 new block 을 할당한다. log block을 할당해야하는 경우가 생기면 아래와 같이 행동한당.
1. log block과 data block에서 최신정보만을 free block에 copy 한다. 이 free block은 data block으로 재설정하기위해 block단위 mapping table을 업로드한다.
2. 기존의 log block, data block을 erase 한다.
3. 새로운 log block을 할당한다.
이 과정에서 2 erase + 1 copy를 거치게 된다. swith operation은 이 연산을 조금더 줄여준다.
-switch operation
 |
| 그림 5. |
1. exchange : block mapping table에서 data block4의 physical address 를 해당 log block 으로 바꾼다.
2. erase : 기존 data block 4를 erase한다.
3. 새로운 log block을 할당한다.
이 과정에서는 1 erase + 1 copy의 과정을 거치게 된다. 즉, merge operation보다 한번 덜 erase 하는 이득을 맛볼 수 있다.
-BAST의 한계
BAST 의 한계는 특정 data block내의 page들은 한 log block 에만 대응될 수 있다(그림 3)는 특성에서 비롯된다. 이로 인해 block thrashing과 block-level associativity 가 발생하여 low-space utilization을 낳는다.
-block thrashing : 1block= 4sectors이고 log block이 2개 있다고 가정하자. p0, p4, p8, p12, p0 ... 과 같은 식으로 write명령이 host로부터 오면 p8부터 매우 아쉬운 일이 벌어진다.
 |
| 그림6. p0->p4->p8 순서로 write시 |
그림6을 보면, p8을 write하기 위해서는, block9에 대응되는 log block을 생성하기 위해서 3sectors가 비어있는 log block을 erase한다. 이를 block thrashing이라고 한다. 이후로 p12, p0 ...을 write할때도 같은 문제가 발생한다. 이 경우 space utilization = 0.25가 된다.
-block-level associativity : 이 문제는 한 블락의 페이지만 집중적으로 write 할때 발생하는 문제이다. 예를 들어, p0,p2,p1,p3,p1,p0,p2... 와 같은 방식으로 write를 하게 되면 p1 부터 다음과 같은 문제가 발생한다.
 |
| 그림7. p0->p2->p1->p3으로 write시 |
그림 7을 보면 아직 logblock이 하나 남아있는데도 불구하고 erase 를 수행하고 새로운 log block 을 할당한다. 이후로도 계속 block7에 집중적으로 할당하면 한 log block만을 사용하게 되는 문제가 발생한다. 이 경우 space utilization=0.5이다.
-BAST 정리
BAST는 log block을 추가하여 erase 연산을 획기적으로 줄이고 속도를 끌어 올린 점에서 큰 의의가 있다. 또한, mapping table로 block-level 뿐 아니라 sector-level도 관리함으로써 sdram의 size를 줄이는 동시에 flexibility를 확보하였다. 그러나 이 좋은 BAST도 log block 과 data block 이 1:1 대응이라는 부분에서 여러가지 문제점이 발생하였고 그 결과는 low space utilization으로 이어졌다. 다음에는 이 BAST의 문제를 해결하기 위한 방식인 FAST를 알아보고자 한다.
5. log FTL - FAST(Fully-Associative Sector Translation)
앞서말한 BAST의 한계는 log block과 data block 이 1:1 대응이라는 특성에서 비롯된 것이었다. FAST는 이 특성을 없애고 fully-associative방식을 채택했다. 즉, log block에 data block이 자유롭게 대응될 수 있는 것이다. 하지만 그 과정에서 BAST의 강점이었던 sequential write일 경우에 merge 를 switch operation으로 바꿀수 있는 특성이 사라지고 말았다. 이를 보완하기 위하여 FAST는 log block을 1개의 SW(sequential wrtie) log block 과 다수의 RW(random write) log block 으로 나누게 되었다.
-FAST 구조
FAST 는 BAST의 구조와 거의 유사하다. 다만 log block 이 sequential write를 담당하는 SW log block 1개와 random write를 담당하는 다수의 RW log block 로 구성되어 있다는 차이가 있다.
-FAST read / write
overhead in read operation : 우선 FAST 은 read operation 에서 약간의 overhead가 나타난다. read 를 하는 과정에서, FTL 은 가장 최신의 data 를 sector-level mapping table로 부터 찾는 과정을 거치는데, fully associative 이기 때문에 block단위가 아닌 sector-mapping table 통째로 다 찾아보아야 한다. 그러나 이 over head는 전체 read시간에 비하여 미미한 편이다. (약 10% 미만)
write operation
FAST는 무엇을 기준으로 SW log block 에 write를 하고 RW log block에 write를 할까? 이는 lsn(logical sector number) 에 달려있다. SW log block 의 목적은 Sequential한 buffer 을 write 할 때, 이를 캐치하고 switch operation이 가능하도록 설정하는 것이다. 알고리즘은 이를 가능케 하도록 구성된다.
즉, 1block=4sectors라 하면, lsn%4=0 이되는 lsn이 overwrite될 경우에 RW log block이 아닌 SW log block으로 write된다. 이후에는 lsn%4=1 이 되는 lsn이 overwrite될 경우 SW log block에 write된다. 이와 같은 방식으로 SW block 이 가득차면, 이는 merge operation이 아닌 switch operation이 가능해진다. 따라서 sequential write의 경우에 SW log block에 기가 막히게 write 되게 된다. 또, 꽉찰때마다 switch operation이 아름답게 일어난다. SW log block은 겨우 한개에 불과한데, 엄청난 퍼포먼스의 향상이 이루어진다.
 |
| 그림8. 출처 : A log buffer-based flash translayer using Fully-associative sector translation |
case 1: lsn=4 이므로 lsn%4=0 이 된다. 즉 write 는 SW log block에 일어난다. 여기서 만일 SW log block이 empty하지 않다면 우선 erase를 하고 write한다.
case 2.1: 처음에 SW log block 에 write 되고, 두번째 역시 lsn=5, lsn%4=1이므로 SW log block 에 순차적으로 write 가 일어난다.
case 2.2 : 두번째에서 RW log block 에 write 된다.
case 2.3 : 두번째까지는 SW log block, 세번째는 RW log block 에 write 된다.
SW log block은 lsn%4==0 인 lsn이 write될때 erase가 일어나며, RW log block은 가득 찼을 때 erase가 일어난다.
이에 관련된 알고리즘은 참고하길 바란다.
 |
| 그림 9. 출처 : A log buffer-based flash translayer using Fully-associative sector translation |
댓글
댓글 쓰기