Chapter#25 Log-structured File Systems

대망의 마지막 챕터

Chapter#25 Log-structured File Systems

---

Log-structured File System

Journaling은 TxB, TxE도 쓰고 double write하여 오버헤드 있음 > Log-structured File System(LFS) 사용

e.g. F2FS, NetApp's WAFL, Btrfs, ZFS, ...

장점 : 

no consistent update problem

no double writes

write performance가 좋다 - disk는 sequential I/O operation에 optimized되어있음

 

Data block을 쓰고 순차적으로 metadata block도 쓴다.

 

Single data block을 하나씩 쓰면 latency가 커지므로 buffer을 사용한다.

 

write buffer에 계속 update를 track하고, 충분히 버퍼가 차면 한번에 disk에 작성한다

segment : 버퍼가 가득차서 한번에 적혀져 나온 것

D MB buffer data를 write하는데 걸리는 시간

*Twrite = Tposition + D/Rpeak

(Tposition : positioning time (sec), Rpeak : disk transfer rate (e.g. 100MB/s))

효율적인 writing

*Reffective = D/Twrite = D/(Tposition + D/Rpeak)) = F x Rpeak

(F : 0~1.0, fraction of peak disk transfer rate)

 

D = F x Rpeak x (Tposition + D/Rpeak) = F/(1-F) x Rpeak x Tposition

 

Finding Inode in LFS

기존 file system : 고정된 위치에 inode table 존재

LFS : disk 전역에 흩뿌려져있음

- 해결 : indirection "Inode Map" (imap)

 

Inode Map

Option 1 : fixed disk location에 map을 두고 inode 생성 시 map에 저장

- 헤더를 왔다갔다 해야되니 퍼포먼스가 오히려 안좋음

Option 2 : chunks of inode map을 inode쓰듯이 씀

Checkpoint Region

inode map은 또 어떻게 찾느냐? = fixed location인 Checkpoint region 사용

Checkpoint region은 latest inode map의 pointer들을 가짐

- 주기적으로 갱신 (e.g. every 30 seconds)

- performance가 그리 나쁘진 않음

 

Reading File from Disk : A Recap

1. Read checkpoint region

2. Read entire inode map and cache it in memory

3. Read the most recent inode

4. Read block from file by using direct or indirect or doubly-indirect pointers

 

Grabage Collection

LFS는 newer version을 new location에 저장함

older version은 그대로 garbage로써 남아있음

Garbage의 두가지 예시

 

One possibility : Versioning file system

- older version을 그대로 두고, restore할 때 사용

LFS approach : Garbage Collection(GC)

- periodically latest live version만 두고 old dead versions는 제거

- GC는 segment-by-segment basis로 작동

 

Determining Block Liveness

Segment summary block(SS)

segment의 head에 위치 (SS가 head에 저장되면, 얘도 HDD seek time에서 performance가 낮지 않나?)

Inode number와 각 data block의 offset기록

Determining Liveness : latest inode가 block을 가리키면 block은 live하다

ex) A0에 위치한 block D의 liveness check

1. SS를 보고 inode number N과 block number T를 찾음 (여기선 N=k, T=0)

2. main memory에 cache된 imap확인하여 N이 live한지 보고 disk에서 해당 inode위치를 read

3. 읽은 T-th block위치와 SS의 T값이 같은지 확인

4. 같으면 live 다르면 dead로 간주

 

언제 어떤 Blocks를 Clean할까?

When :

- disk가 다 찼을때

- idle time 도중

- Periodidcally

Which :

segmets 정의 (hot/cold) :

- Hot segment : frequently over-written : 금방 dead block 생김

- Cold segment : relatively stable : 적은 dead block 가짐, 다른 block은 stable

=> cold segment는 sooner, hot segment는 later Clean

 

Crash Recovery and Log

일반적으로 LFS Buffer는 segment단위로 disk에 write하며 주기적으로 checkpoint region에 update됨

log에는 다음과 같이 저장함

- Checkpoint Region(CR)은 head/tail segment를 가리킴

- 각 segment는 다음에 쓰일 segment를 가리킴

- 주기적으로 CR 갱신

Crash가 CR이나 segment를 write할 때 발생한다면?

Case 1 : crash가 CR write할 때 발생

- LFS가 번갈아가면서 두 CR 사용

- CR은 두 개의 time stamp TS1, TS2를 가지는데, TS1은 시작할때, TS2는 끝날 때 시간을 찍음

- Crash가 발생하면 inconsistent한 timestamp pair가 있는걸 감지할 수 있음

- consistent timestamp를 가진 most recent CR을 택하면 file system의 consistency 유지 가능

Case 2 : crash가 segment를 write할 때 발생

- LFS에서 CR은 30초마다 write되므로 last consistent snapshot은 오래되었을 것

- roll forward를 통해 segments rebuild 시도

 1. last CR에서 시작(e.g. CR1)

 2. CR의 마지막 log 확인

 3. 거기서부터 다음 segment read

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.