[Operating System] LFS (Log-Structured File System)

파일 시스템의 종류

1. Local

• FFS (Fast File System)
• LFS (Log-Structured File System)

2. Network

• NFS (Network File System)
• AFS (Andrew File System)

 

---

LFS의 목적, 특징

• COW(copy-on-write)의 사용: COW 방식은 journaling으로 인해 2번 중복 write하는 오버헤드가 없으며, 공간적인 오버헤드도 없다.
• FFS는 read를 보다 빨리 하는 것에 초점이 맞춰져 있다면, LFS에서는 wrtie를 빨리하는 것에 초점을 두었다.

 

목적

• RAID-5와 같은 경우 sequential write와 random write의 성능 차이가 매우 심하다. (random이 너무 별로다.)
• 따라서 LFS에서는 오직 sequential write만 수행을 하도록 한다. (read는 sequential이 아닐 수도 있음)
• easy for write
  • 남은 블록 중에 가까운 것에 새로운 copy를 만드는 식이라서 write가 빠르고 RAID-5랑도 잘 맞는다.
• hard for read
  • write 시점에 가까운 공간에 write를 하기 때문에 read 시엔 sequential 함을 보장할 수가 없음
  • 하지만 메모리의 크기가 증가함에 따라서 read에 의한 문제는 사실 많이 사라짐 (요즘 LFS를 쓰는 이유)

 

작동 방식

• LFS는 메모리에 충분한 데이터(> 10MB)가 모일 때까지 버퍼링을 했다가 버퍼링 된 segment를 한 번에 disk에쓴다.
  • crash가 발생하면 buffer의 데이터가 날아가는 문제가 있긴 함.
• Overwrite를 하지 않음 (old copy는 앞에 남아 있는 상태에서 뒤에 공간을 할당)
• 무조건 새로운 위치에 write를 하고 포인터를 바꾸기 때문에 garbage collection이 필요하다.
• 리눅스 파일 시스템 상에서는 딱 하나의 파일에 write를 하더라도 상위 디렉토리의 inode들도 함께 업데이트를 해줘야 하는 오버헤드가 존재한다. $\to$ 만약 동일한 디렉토리에서 여러 파일이 수정되었다면 상위 디렉토리의 inode를 한번에 segment 단위로 수정하여 positioning 오버헤드를 감소시킬 수 있다.
  • 한번 write를 시도할 때마다 그 크기와 관계없이 positioning time이 소모됨.
  • segment 크기가 증가할 수록 전체 positioning time을 줄일 수 있음.

 

LFS에서 inode를 어떻게 찾는가?

• Inode는 디스크에 흩어져서 저장되어 있기 때문에 imap (inode map)이 필요함. (imap의 위치를 가리키는 포인터는 반드시 메모리에 상주해야함)
• Imap에는 inode number가 저장되고 이를 통해서 디스크에 존재하는 inode의 위치를 파악할 수 있다.
• Inode를 통해서는 data block에 접근 가능하다.

 

Checkpoint Region

이전 포스팅에서 살펴본 checkpoint의 개념과 LFS에서의 checkpoint의 개념에는 차이가 있다.

• Journaling을 하는 FFS의 checkpoint = journaling 후 실제로 업데이트를 하는 것
• LFS의 checkpoint = inode map이 어디있는지 적어놓는 것

 

Checkpoint Region

 

위의 그림에서  가장 왼쪽에 CR이라고 적힌 부분이 checkpoint region에 해당하며, 이는 imap들 가리키는 포인터들의 배열이라고 볼 수 있다. (imap[k:k+N])

 

• Checkpoint region: 디스크의 특정 고정된 위치에 imap들을 가리키는 포인터들을 저장해놓아서 이를 빠르게 메모리에 올리고 imap을 쉽게 찾아갈 수 있도록 함
• Checkpoint region에는 가장 최신의 imap들의 정보가 들어가는데 이를 매번 업데이트하면 오버헤드가 크므로 약 30초 단위마다 주기적으로 업데이트를 함. (segment write 보다 긴 주기)

 

LFS: Disk에서 파일을 읽는 순서

imap이 inode를 가리키고, inode는 data block을 가리킨다.

1. memory에 캐싱된 것이 없다면 checkpoint region을 읽어서 imap의 위치를 파악
2. 전체 imap을 메모리에 캐싱함
3. 가장 최근 사용된 inode를 읽음
4. direct, indirect pointer를 통해서 data block을 읽음

 

Garbage Collection

• LFS는 지속적으로 비어있는 위치에 새로운 버전의 copy를 write하게 되고, 그 이전에 있던 버전은 garbage가 된다.
• 여러개의 버전이 있다면 최신 버전만 남기고 지우는 것이 garbage collection이다.
  • overwrite하는 경우: 옛날 data와 inode가 모두 garbage가 됨
  • append하는 경우: data block은 여전히 유효하기 때문에 옛날 inode만 garbage가 됨

Overwrite와 append 상황에서의 GC 동작.

 

• LFS의 목적은 sequential write인데 만약 block 단위로 GC를 한다면 alignment가 띄엄띄엄하게 되어 segment 단위의 sequential write를 하지 못하게 될 수 있다.
  $\to$ 따라서 버퍼링한 segment 단위로 GC를 수행한다.
• Block이 유효한지(살아있는지) 어떻게 판단하는가?
  • Segment Summary(SS) Block
  • SS block은 각 segment마다 존재하며, inode number와 각 data block에 대한 오프셋이 기록된다.
  • 가장 최신의 imap 상에서 inode에 의해 참조되는 block이면 살아있음
• 언제 clean 시키는가?
  • 주기적으로 / idle할 때 / 디스크가 꽉 찼을때
• 어떤 block을 clean 시키는가?
  • 가장 비어있는 segment부터
  • coldest segment부터
    • hot segment: 자주 overwrite 되는 블록들
    • cold segment: 기다려봤자 다시는 잘 사용되지 않을 블록들

 

Crash Recovery

Crash 이후 tail에 있는 가장 최근 버전의 imap을 사용한다.

• CR (Checkpoint Region)은 head와 tail segment를 가리키고, 각 segment는 다음 segment를 가리킨다. (따라서 CR을 통해서 현재 사용 중인 공간에 대한 정보를 파악할 수 있다.)
• Checkpoint가 이루어질 때마다 새로운 버전의 imap이 쓰여지고, 새롭게 생성된 imap은 CR의 tail에 연결된다. 즉, CR의 tail이 가리키는 imap이 가장 최신 버전의 imap이라고 할 수 있다. 
• 따라서 crash가 발생하더라도 가장 최신 버전의 imap을 읽음으로써 해당 상태에 맞게 복원을 할 수 있다. (물론 CR은 30초 정도 주기로 업데이트 되므로 어느 정도 이전 시점으로 복원됨)
• CR을 업데이트 하다가 crash가 날 수도 있기 때문에 CR은 2개의 copy를 만들어둔다. (time stamp를 통해서 어떤 것이 더 최신인지 구분할 수 있음)
  • time stamp 업데이트 $\to$ 새로운 CR 업데이트 $\to$ time stamp 업데이트
• 좀 더 개선된 복원 방법: CR 전체(전체 imap)을 읽는 건 시간이 너무 많이 걸리기 때문에, 가장 마지막 checkpoint시에 쓰여진 imap을 가리키는 포인터를 CR의 맨 앞에 저장해둔다. (linked list 순회 시간 단축)

 

LFS 자료구조 특징

• LFS는 결코 overwrite 하지 않기 때문에 update가 발생하면 inode number가 바뀐다.
• 만약 file 하나를 업데이트 한다면 그 상위 directory의 정보들까지 모두 COW 방식으로 업데이트 되어야한다.
  • 하지만 이 경우에 root 디렉토리까지 업데이트가 propagate 되어서 오버헤드가 너무 커질 수 있기 때문에, inode number를 constant로 유지한다.
• LFS에서는 imap이 있기 때문에 FFS에서 사용하는 data bitmap, inode bitmap을 사용할 필요가 없다.
• imap은 어디에 위치하는가?
  • imap: inode number를 통해서 디스크 상에서의 inode 위치를 매핑해줌
  • imap에는 각각 4바이트 크기의 수십만개의 inode number가 들어있음
  • 따라서 imap 전체를 항상 메모리에 올려두기엔 너무 사이즈가 크고, 이를 업데이트 하는 것도 쉽지 않음
  • 해결 방법: 메모리에는 imap 전체가 아닌 imap의 각 segment들을 가리키는 포인터와 가장 최근 버전의 imap만 저장한다.