12. File Translation Layers, FTL

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

SSD FTL §

• SSD 는 read + program + erase 밖에 안되기 때문에 이것을 기존의 sector r/w 인터페이스로 전환해주는 것이 File Translation Layer, FTL 이다.
• Address mapping - overwrite 가 안돼 위치가 바뀌니 위치 바뀌는 것을 추적하기 위한 것
• 이 DRAM 이 비싼 리소스이기 때문에 어떻게 address mapping 을 할지가 중요했다
  • 적게 쓰면서 더 잘하기
  • Page mapping 과 block mapping 이 있고, 이들을 합친 hybrid mapping 의 등장
  • 근데 최근의 ssd 는 그냥 page mapping ftl 을 사용한다고 한다.
    • 그래서 zns 논문에서 page mapping ftl 을 지적했구만

Page Mapping §

• 용어정리를 좀 해보자
  • Logical Block Address (LBA) 은 기존 HDD sector 에 대한 addressing system
    • 즉, 보통 512byte 다.
    • Logical Sector Number (LSN) 와 혼용해서 쓰는 용어인듯
  • Logical Page Number (LPN) 은 일반적으로 4Ki 사이즈인 단위이다
    • 그래서 LBA 8 개가 하나의 LPN 이 됨
  • Physical Page Number (PPN) 은
• 모든 Logical Page Number (LPN) 을 Physical Page Number (PPN) 에 대응시켜 변환하는 것을 Page Mapping 이라고 한다.
• 이 매핑은 Page Mapping Table (PMT) 이라는 테이블을 이용한다.
  • 이놈은 Logical-to-Physical (L2P) Table 이라고도 불린다.
  • PMT 의 entry 개수가 OS 에서 보이는 page 개수가 된다.
• L2P table 의 사이즈는 SSD 사이즈의 1/1024 이다:
  • 1Ti SSD 를 생각해 보자.
  • 그럼 SSD 의 용량을 byte 단위로 생각하면 $2^{40}$ byte 가 될것이고, (LPN 크기는 4Ki = $2^{12}$ byte 이므로) SSD 에는 $2^{28}$ 개의 LPN 이 매핑되어야 할 것이다.
  • L2P entry 하나의 사이즈는 4byte 라는 가정 하에, 전체 L2P table 의 크기는 $2^{28}\ast 4byte$ = $2^{30}byte$ = 1Gi 가 된다.
  • 즉, SSD 의 크기인 1Ti 와 비교하면 1/1024 인 것.
• 그래서 주소 변환 과정은 크게
  • 우선 LSN 을 LPN 으로 변환하고
  • LPN 을 L2P 를 이용해 PPN 으로 바꾸는 과정으로 이루어진다.

Page Mapping Example §

• 그림이 좀 헷갈릴 수 있는데 Data Block 에 적혀있는 저 012845 는 데이터이다; LPN 값을 write 한 것.
• 일단 new write 요청 (L2P mapping 이 되지 않은) 에 대해 PPN 이 어떻게 할당되는지 보자.
  • SSD 에서는 page 를 block 내에서 sequential write 한다.
  • 즉, 들어온 LPN 에 따라 PPN 0 부터 쪽 write 한 다음에 mapping 만 해주는 것.
  • 위의 예시에서 LPN 0, 1, 2, 8, 4, 5 에 write 했더니, PPN 은 0 ~ 5 에 write 되고 실제로 write 된 PPN 을 L2P table 의 LPN 에 매핑해놓은 것을 알 수 있다.
    • 가령 LPN(8) write 의 경우에는 4번째 write 요청이기 때문에 PPN(3) 에 write 되었고, 따라서 L2P 의 LPN(8) entry 에 PPN(3) 이 적혀있는 것.
• 그리고 이때 read 요청은 그냥 이 L2P 를 쭉 따라가면 된다.
  • LPN(8) read 는 L2P 에 의해 PPN(3) read 로 바뀌고, 따라서 여기에 들어있던 데이터가 읽혀지는 것.

• 이때 update 는 위처럼 작동한다.
  • LPN(5) 에 데이터 5 를 적고자 하면
    • …물론 기존에도 5 가 적혀 있지만 동일한 데이터로 update 한다고 가정
  • 다음으로 write 될 위치는 PPN(8) 이므로 여기에 5 를 적고
  • L2P 의 LPN(5) entry 를 PPN(8) 로 업데이트한다.
  • 그리고 기존에 데이터가 저장되어 있던 PPN(5) 는 invalidate 시키게 되는 것.

장단점 §

• 장점으로는
  • LBA 어디든 써도 되니까 아주 유연
  • small size random write 시에 쓰고 mapping 만 하면 되니까 아주 빠름
    • read 도 마찬가지
• 단점은
  • DRAM 이 많이 필요
    • 이 단점을 완화하기 위해 flash block 의 크기를 늘리는 방법도 있음
      • 하지만 당연히 internal fragment 가 커지는 문제가 있다.
  • LFS 처럼 여유 공간을 구비해 둬야 함 - OP 공간
    • 성능과 가용 공간의 trade off

Garbage Collection §

• Garbage Collection (GC) 에서는
  • GC 시에 page 를 옮길 Spare block 을 하나 이상 남겨두고
  • Invalid 가 가장 많은 놈을 greedy 로 택해서
    • 보통은 그냥 단순하게 greedy 하게 victim 을 잡고, cost-benefit 은 잘 안쓰인다고 한다.
  • Live block 을 옮기고 erase
• GC 로 옮겨진 데이터는 상대적으로 cold 이다 - 딴애들 죽을때까지 살아있었으니까
  • 근데 새로 write 된 놈은 (비록 알 수는 없지만) 비교적 hot 일 확률이 높고
  • 따라서 GC 로 뭉쳐진 곳에는 new data 를 잘 write 하지 않는다
  • 그래서 한번에 많은 block 들을 GC 해 여기에 살아있는 애들을 최대한 뭉쳐놓게 된다.
• 파일의 크기가 크면 cold 일 것이다 라고 가정하는 ftl 도 있음
  • 보통 크기가 큰 image 같은 애들이 cold 이기 때문
• 아니면 LBA 공간의 update count 로 history 관리하기도 하고
• 이런 아이디어도 있다
  • 일단 처음에는 hot
  • gc 한번 살아남으면 warm
  • 두번 살아남으면 cold
  • 세번은 colder
  • 이런식으로 계층화

GC Example §

• LPN(1) write 를 하고 싶은데, Spare block 인 PBN(3) 말고는 남아있는 것이 없는 상황.
• 그래서 일단 GC 를 한다.
  • Invalid 가 많은 PBN(1) 을 greedy 하게 victim 으로 선정해서
  • 여기에 있는 PPN(4) 를 PPN(12) 로 옮긴다.
  • 이에 따라 L2P 에 원래 PPN(4) 에 매핑되어 있던 LPN(4) 의 entry 가 PPN(12) 로 바뀐다.
• 이후 LPN(1) write 를 수행
  • GC 이후 다음으로 write 될 PPN 은 PPN(13) 이기 때문에 여기에 write 를 하고
  • L2P 에는 LPN(1) entry 를 PPN(13) 으로 바꾼다.

시간에 따른 SSD 성능 변화 §

• Fresh-out-of-box (FOB) 는 SSD 구매 직후를 말한다: 모든 block 이 clean 이기 때문에 아주 빠름
• FOB 를 넘어가면 GC 가 수행되서 성능이 저하되는 것이 보이고 (Transition)
• 성능이 일정하게 유지되면 Steady State 라고 부르고 이 시점에서의 성능과 성능 변동을 이용해 SSD 의 성능을 시험하는듯

여기부터는 2024-04-11 강의

Write Amplification §

• host 가 write 한 양 대비 실제로 write 된 양
• GC 때문에 보통 추가적인 write 이 발생 (1이 넘음)
• compression 이나 deduplication 을 이용하면 1 보다 작아지는 것도 가능하다

WAF calculation example §

• 직접해보자; LPN(0, 1, 2, 8, 4, 5, 9, 3, 5, 8, 9, 3, 1) 순서로 write 가 들어왔고, 이 과정에서 GC 가 발생해 LPN(4) 가 옮겨졌으니까 13/14 = 1.08 이 된다.

WAF in GC policies §

• SSD 와 LFS 는 유사점이 있다
  • segment 가 physical block 에 대응
  • cleaning 은 gc 에 대응
• 따라서 LFS 에서의 cleaning policy 를 ftl GC policy 에도 적용할 수 있다.
  • Greedy: lfs 에서처럼 util 가 작은놈을 선정
    • Block 당 valid page 개수를 count 할 필요가 있다.
      • L2P 를 훑으면서 valid count 를 계산하기보다는 L2P 에 별도의 공간을 할애해 count 를 추적한다.
      • 즉, 추가적인 DRAM 공간이 필요하게 되는 셈
    • 완전 minimum 한 놈을 gc 하는 것보다 대충 정해서 gc 하는게 더 좋을 수도 있다고 한다,,
      • 특정 threshold 만 넘으면 가능하게
      • 주의: 찌라시임
  • Cost-benefit: lfs 과 유사 하지만, 전부 다 read 할 필요는 없으니까 cost 가 1+u 에서 2u 로 바뀐다.
    • 근데 ssd 에서는 거의 안쓴다
      • Cost-benefit policy 에서는 나눗셈 연산이 들어가기 때문에, SSD controller 에 floating point 연산이 되도록 해야 하는데 이것이 굳이? 이기 때문.
• 대강 아래와 같은 장단점이 있다고 한다.

	GREEDY	COST-BENEFIT
PROS	간단한 구현	Hot-cold 에 따라 다르게 GC 를 할 수 있음
CONS	Cold 에 대해서는 GC 가 잘 안됨	구현의 복잡함

Over Provisioning (OP) §

• LBA 공간보다 더 많은 공간을 PBA 로 둬서 GC 시에 write buffer 로 쓰는 등으로 활용
• 대략 다음과 같은 수식이 있다.
  • 100% 가 넘어가는 것은 $PhysicalCapacity$ 가 $LogicalCapacity$ 크기의 2배가 넘는다는 것

$$OP=\frac{PhysicalCapacity}{LogicalCapacity}-1=\frac{ExtraCapacity}{LogicalCapacity}$$

• GB vs GiB 차이에 의한 것이 기본 (Inherent OP)
• data center 용도로 나오는 ssd 의 op 가 더 높게 설정 (더 많이 여분으로 남김)
• 이것은 다음과 같은 용도로 사용된다고 정리해 볼 수 있다
  1. write buffer 로 사용
  2. 펌웨어 이미지 저장
  3. (L2P map table - journal / logging 식으로 관리하는듯) + metadata
  4. Bad block 교체용 (wear level 등)
  5. 다만 OP 에는 ECC 를 저장하지 않는다 - parity 는 page 끝에 저장
• SSD utilization 과 OP 는 GC 에 영향을 미친다.
  • Util 이 적을때 GC 를 하면 조금만 copy 하면 되니까 더 좋고
  • OP 가 많은 것은 OP 공간을 buffer 로 사용하며 시간을 끌어 victim block 이 더 많이 invalidate 될 수 있게 해주기에 더 좋다

Block mapping L2P §

• pba block size 로 lba 를 나누고
• pba 에서의 block 내 offset 과 lba 내 block offset 을 동일하게 유지
• mapping table 의 크기가 작아지니까 dram 이 적게 필요
• 따라서 logical block number 를 physical block number 로 바꾼 뒤 offset 은 그대로 가져가면 lba 를 pba 로 바꿀 수 있음
• logical block 과 physical block 의 내부 데이터 순서가 무조건 같아야 한다는 제약사항
  • 이 제약사항때문에 page 의 주소가 바꾸려면 해당 page 의 block 에 있는 모든 page 가 같이 움직여야 한다.
• sequential write 의 경우에는 나름 괜찮을 수 있지만 random write 에는 쥐약이다.
  • Sequential write 의 경우에는 어차피 LPN-PPN 매핑이 바뀌지 않으니까 (in-place update 를 하지 않으니까) 괜찮지만
  • Random write 의 경우에는 in-place update 를 하며 PPN 이 바뀌게 되는데 이때 그럼 전체 block 을 전부 옮겨야 하기 때문.
  • 그래서 ZNS 논문 에서는 page mapping 의 DRAM 사용량을 문제로 꼽으며 이 ZNS 를 사용하면 (sequential write 이기 때문에) block mapping 을 사용할 수 있다라고 한 것.

Hybrid mapping §

• 이렇게 산다:
  • 기본적으로는 block mapping 으로 작동하되
  • Update 시에 page 를 딴곳에 적어야 하는데 이때 block 전체를 옮겨야 하는게 문제였기에
  • Update page 만 Log block 이라는 공간 (아마 OP 공간에 있는) 에 적고 여기에 대해서만 page mapping 을 한다.
    • Log block (Log Flash Block) 은 updated page 을 page mapping 으로 관리하는 공간인 셈.
  • Log block 이 부족해지면 그것을 Data block 으로 바꿔 block mapping 이 되게 하는 방법
    • Data block (Data Flash Block) 은 new page 를 block mapping 으로 관리하는 공간인 셈.
• 이렇게 하면 hot page 는 page mapping 으로 관리하고 cold page 는 block mapping 으로 관리하는 효과가 난다.

Mapping type §

• Log block 과 Data block 간의 관계에 따라 다음과 같이 나눌 수 있다.
  • Direct-mapped (1:1 mapping): 1개의 Log block 과 1개의 Data block 을 매핑
    • 즉, 1개의 Log block 에 쌓이는 page 들은 1개의 Data block 에서의 updated page 들이다.
    • Updated page 는 양이 적을 수 있기 때문에, 이 방법을 사용하면 Log block 들에 대한 utilization 이 낮아 낭비일 수 있다.
  • Set-associated (1:N mapping): 1개의 Log block 과 N개의 Data block 을 매핑
    • 즉, 1개의 Log block 에 쌓이는 page 들은 N 개의 Data block 에서의 updated page 들이다.
  • Fully-associated (M:N mapping): M개의 Log block 과 N개의 Data block 을 매핑
    • 즉, 1개의 Log block 에 쌓이는 page 들은 N 개의 Data block 에서의 updated page 들이되, 해당 Data block 들의 updated page 가 다른 Log block 에도 쌓일 수 있는 것.
    • 여기서 M 은 모든 Data block 개수인듯 - 모든 Data block 에서 생기는 updated page 들을 N 개의 Log block 에 담는 것

Merge type §

• Log block 을 Data block 으로 바꾸는 것은 위와 같이 세 방법이 있다.
  • Full merge: Data block 와 Log block 의 valid 들을 free block 에 모으고, 기존의 Data block 과 Log block 모두 밀어버리는 방법
  • Partial merge: Log block 에 Data block 의 valid 들을 담을 수 있는 충분한 free page 가 있는 경우 Data block 의 valid 들을 옮기고 Log block 을 Data block 으로 전환한 뒤 기존 Data block 은 밀어버리는 방법
  • Switch merge: Data block 이 전부 invalid 이고, Log block 이 전부 valid 일 때 Log block 을 Data block 으로 전환하고 기존 Data block 은 밀어버리는 방법

FAST (BAST) §

• Fully-Associative Sector Translation (FAST) 는 기존의 Fully-associated 방식으로 작동하되
• Log block 을 Sequential write log block (SW Log) 1개와 Random write log block (RW Log) 여러개로 Log block 에 대한 타입을 나눠
• 연속된 page 들에 대한 update 는 SW Log 에, 듬성듬성이는 RW Log 에 저장하는 방법
• 뭐 장단점은
  • 장점: (1) log block util 이 올라가고 (2) 불필요한 merge 가 줄어들고
  • 단점: (1) merge time 이 늘어나고 (2) Sequential write 를 SSD 입장에서 알아내기 어렵고
• 위와 같은 작동 방식에서 Fully-associated 말고 Direct-mapping 버전은 BAST (Block-Associative Sector Translation) 라고 한다.