- Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho, Samsung Electronics Co., Ltd.
- USENIX Conference on File and Stoarage Technologies (FAST 15)
1. Introduction
a. Flash Memory의 한계점
- 쓰기 작업 전 지우기 (erase-before-write requirement)
- 순차적으로 지워진 Blocks에 쓰기 (need to write on erased blocks sequentially)
- 제한된 쓰고 지우기 cycles (limited write cycles per erase block)
b. Flash Memory 사용의 증가
- 이때까지는 HDD를 계속해서 저장 매체로 썻으나 점점 더 많은 저장 매체가 필요하고 빠른걸 원하게 되었다.
- 저장 매체의 필요성 증가에 의해 다수의 Flash chips를 controller에 연결해서 사용하는 해결책이 일반적이 되었다. (Flash Chip의 가격 하락으로)
c. Flash Memory에 대한 이해 부족으로 인한 단점
- 위의 a의 문제점에 의해 HDD처럼 계속해서 I/O를 하면 Flash Memory의 특징을 잘 못살리게 된다.
- 오히려 I/O latency 가 증가하고 수명을 빠르게 깍게 된다.
d. 기존의 연구
- 위와 같은 점들을 고려하여 선행연구에서 LFS(Log-Structured File System)의 접근 방법과 Copy-On-Write 전략으로 위의 한계점을 극복할수 있다.
- 예시로 BTRFS(B+-Tree File System)과 NILFS2(이건 먼지 모르겠네요 ㅠ)가 NAND Flash SSD에서 잘 동작한다. (cf. NAND 기반과 NOR 기반으로 크게 나뉜다.)
- 하지만 기존 선행 연구는 Flash Memory 의 특징을 전부 고려하지 못했고 성능과 수명 측면에서 좋지 않았다.
- 따라서 새로운 F2FS를 제시한다.
e. F2FS의 특징
- Flash-friendly on-disk layout : Segment, section and zone
- Segment, section 그리고 zone이라는 개념을 통해 Flash에 친화적인 layout을 사용한다.
- Cost-effective index structure : NAT (Node address table)
- 비용 측면(시간과 공간 둘다)에서 효율적인 index 구조를 필요로 한다.
- SSD나 Flash Memory는 LBA(Logical Base Address)가 존재하지 않지만, 이를 호환성 측면에서 제공해야하고 (FTL-Flash Translation Layer) 이를 효과적으로 제시한다.
- Multi-head Logging
- 기존 연구의 LFS에서 착안하여 Logging Strucutre를 사용하지만 Multi-head를 사용하여 병렬처리를 하고, Hot/Cold 를 분류한다.
- Adaptive Logging
- dirty segment를 Cleaning 하지 않고 새로운 데이터를 기록한다.
fsyncacceleration with roll-forward recovery- 예시 상황 : sqlite3
2. Design and Implementation of F2FS
2.1 On-Disk Layout
Superblock(SB)
- 파티션 정보, F2FS의 default parameter가 들어있으며 format time에 주어지며 바뀌지 않는 값
Checkpoint(CP)
- file system의 상태, 유요한 NAT/SIT set들의 bitmap, orphan inode list들 그리고 활성화된 segment들의 요약 entries
Segment Information Table(SIT)
- valid blocks의 개수 같은 segment information,
Main Area의 모든 block의 validity bitmap - Cleaning process 동안 victim segment를 고르기 위해, valid block을 식별하기 위해 사용된다.
Node Address Table(NAT)
- Main Area에 저장된 모든 node block의 위치 Table
Segment Summary Area(SSA)
- Summary entries prepresnting the owner information of all blocks in the Main Area
- Cleaning 과정 동안 valid block 이동하기전 parent node blocks을 구별하게 된다.
Main Area
- 4KB 크기의 blocks로 채워져 있다.
- 각 block은 node이거나 data이다.
- node block은 inode를 포함하거나 data blocks을 가리킨다.
- data block은 directory이거나 user file data를 가진다.
- block은 동시에 node 이거나 data일수 없다.
2.2. File Structure
Node Structure
- inode의 확장
- indexing block을 더 두기 위해서 사용
- 고유한 nodeID가 존재하고 NAT(Node Address Table)에서 nodeID를 키, Physical Address를 value로 들고 있는다.
- 3가지 종류 (inode, direct, indirect)
- inode : file의 metadata(filename, inode number, atime, dtime)
- direct : data block의 주소
- indirect : 다른 node block들의 nodeID
- 데이터가 변경될 때 direct node만 변경하고 NAT entry를 수정해주면 변경을 손쉽게 처리할수 있다.
- inlinde data와 inline extended attributes를 지원한다. (inline data란 metadata에서 비어있는, 예약되어 있는 영역의 크기보다 데이터가 더 작을 경우 그곳에 데이터를 넣는 것을 지칭한다.)
- F2FS에서는 200bytes를 extended attributes로 지원하고 있다.
2.3. Directory Structure
- 4KB 크기의 directory entry(앞으로 dentry라고 지칭) block 은 bitmap과 2개의 array of slots를 가지고 있다.
- bitmap 은 각각의 slot들이 valid한지를 들고 있고, 각 slot은 hash value, inode number, length of filename and filetype을 들고있다.
- F2FS에서 directory 내 주어진 filename 찾기 예시
- filename의 hash value를 계산해서 hash table을 level 0부터서 inode 상 최대 할당된 level까지 돌아다닌다. 각 level에서 2개나 4개의 dentry block들 중 하나를 scan한다.
- 위의 과정은
O(log(# of dentries))의 복잡도를 가진다. dentry를 더 빨리 찾기 위해 bitmap, hash value, filename 순으로 접근하여 비교한다.
2.4. Multi-Head Logging
- F2FS는 hot/cold data의 분리의 효과를 최대화 하기 위해서 6개의 major log area를 가진다. 또한 F2FS는 다음과 같이 node와 data block의 온도를 나눈다.
- Log 파일을 총 6개(각각의 Type과 Temp마다), 4개(Hot Node, Hot Data, Other Nodes, Other Data), 2개(Node, Data)
FTL(Flash Translation Layer) Algorithm
- 일반적으로 FTL algorithm은 data와 log flash blocks 사이 연관성에 따라 3가지(block-associative, set-associative, full-associative)로 구별짓는다.
- 초기 파일 시스템을 포멧할 때 log flash blocks이 설정된다. 이때 설정된 log flash blocks은 data flash blocks이 할당될 때 생성된다.
- 현대 FTL algorithms은 random-write를 다루기 위해서 full-associative나 set-associative를 채택한다.
- F2FS에서 주목할만한것은 multi-head logging을 사용했기 때문에 병렬적으로 로깅이 가능하다는 것이고, 이런 로그들을 분리하기 위해서 FTL에서 서로 다른 zone을 가지고 있다는 것이다.
2.5 Cleaning
- 흩뿌려져있는 유요하지 않은 Blocks을 재사용 가능하게 하고 Logging을 위해 free segments를 보장해주는 작업
- F2FS는 Foreground, Background로 구별되게 존재한다.
Foreground
- 충분히 빈 공간이 없을 때 시작한다
Cleaning 단계
Victim selection
비어 있지 않은 sections 중 victim을 고른다.
greedy 방법과 cost-benefit 방법 2가지가 존재한다.
greedy 방법 : valid blocks 수가 가장 적은 section을 고른다. (Foreground)
cost-benefit 방법 : SIT(Segement Information Table)로 부터 last modification time을 가져와 section 안 segments의 평균을 매겨 section의 age를 매긴다 (cost = # valid blocks)
Valid block identification and migration
- SIT 로부터 segment 당 valid bitmap을 가져와서 valid blocks을 알아낸다.
- SSA 로부터 parent node blocks을 알아낸다
- Foreground로 돌아가고 있다면 free logs 에 옮긴다.
- Background라면 page cache로 blocks을 옮기고 dirty로 표기한다.
Post-Cleaning Process
- victim section을 pre-free 라고 체크한 뒤 checkpoint를 만들어 저장한다.
논문을 읽으면서 궁금했던 점.
LFS가 왜 좋은지, 왜 채택한건지, 어떤 단점이 있고 이 논문에서는 어떻게 극복한건지
2.1 Log-Structured File System (LFS) LFS는 저장장치를 세그먼트 단위로 분할하고, 각 세그 먼트를 다시 블록으로 분할한다. 그리고 쓰기 요청을 처 리할 때 이 블록들을 순차적으로 할당하여 임의 쓰기 요 청들을 순차 쓰기로 변환시킨다. 최근, 이러한 LFS의 순 차 쓰기 방식은 임의 쓰기에 취약한 플래시 메모리에 적 합하기 때문에 플래시 메모리를 위한 파일시스템으로써 널리 연구되고 있다. 하지만 이 순차 쓰기 방식 때문에 LFS는 invalid 처리 된 블록을 회수하는 Garbage Collection (GC)이라는 작업 이 필요하다. 기존의 많은 연구들은 LFS에서 GC 오버헤 드를 줄이기 위해 In-Place Update (IPU) 정책을 같이 사 용하는 등 다양한 노력을 해왔지만, 여전히 LFS에서 GC 는 파일시스템 성능에 큰 영향을 미치는 요소이다 [출처] F2FS 파일시스템의 버전별 변화 및 성능 영향 분석 이준호O , 곽현호, 신동군 성균관대학교 반도체시스템공학과 crow6316@skku.edu, gusghrhkr@skku.edu, dongkun@skku.edu왜 Hot과 Cold는 서로 분리되어야 하는가?
- Hot과 Cold가 서로 같이 존재하면 Hot이 지워지거나 갱신될때마다 Cold도 같이 Copy-On-Write가 일어나서 동시에 쓸수있는 Hot 데이터(위에서 말하는 Data가 아닌, 기록되어야할 모든 정보 의미)의 양이 감소하고, Cold Data는 갱신이 되지 않음에도 불구하고 NAT를 계속해서 갱신해주어야하기 때문에