18. File Systems Implementation

Implementing a File System

• File system implementation은 크게 두 가지를 본다.

1. On-disk structures
   • file과 directory를 disk 위에 어떻게 표현할 것인가?
   • inode, bitmap, superblock 같은 metadata를 어떻게 관리할 것인가?
2. Access methods
   • open(), read(), write(), close() 같은 API가 내부적으로 어떤 단계를 거치는가?

VSFS(Very Simple File System)

• disk를 fixed-size block들로 나눈다.
  • 예: 4KB block
  • block size는 sector size의 배수다.
• disk block의 대부분은 user data를 저장하는 데 쓰이고, 일부 block은 file system metadata를 저장하는 데 예약된다.

S : superblock
i : inode bitmap
d : data bitmap
I : inode table block
D : data block

Data Blocks

• Data block은 실제 파일 내용을 저장하는 block이다.
• 예를 들어 hello.txt의 내용이 "hello world"라면, 이 byte들이 data block에 저장된다.
• 대부분의 disk block은 data region에 속한다.
• 파일이 커지면 여러 개의 data block을 사용한다.

file A -> data block 10, 11, 12
file B -> data block 20, 25

• 여기서 중요한 문제는 “파일 하나가 여러 block을 가질 때, 그 block들의 위치를 어떻게 기록할 것인가?”다.
• 이 질문이 뒤에서 나오는 allocation strategy로 이어진다.

Inodes

• inode는 파일의 metadata를 저장한다.
• 각 inode의 크기는 고정되어 있다.
  • 보통 128B ~ 256B
• 강의안 예시에서는 inode가 256B이고 block size가 4KB이면, 한 block에 inode 16개가 들어간다.
  • 4KB / 256B = 16
• inode block이 5개라면 총 inode 수는 다음과 같다.
  • 16 \times 5 = 80
• 파일 시스템에서 만들 수 있는 파일 수의 최대값은 inode 개수에 의해 제한된다.

inode에는 보통 다음이 들어간다.

file type
file size
permissions
owner
timestamps
data block pointers

• 핵심은 inode가 파일 이름을 저장하는 곳이 아니라는 점이다.
• 파일 이름은 directory entry에 있고,
• inode는 파일의 metadata와 data block 위치를 저장한다.

Bitmaps

• inode bitmap
• data bitmap
  • 각 bit는 해당 inode 또는 data block이 free인지 in-use인지 나타낸다.
    • 0: free
    • 1: in-use

• 하나의 bitmap block이 4KB라면 bit 수는 다음과 같다.
  • 4KB = 4096B = 32768bits
• 즉 하나의 bitmap block으로 최대 32768개의 block 또는 inode 상태를 표현할 수 있다.
• 다만 강의안 예시에서는 one bitmap block이 up to 4096 data blocks or inodes를 support한다고 설명한다.
• 따라서 일반 bit 계산인 32768과 강의안 예시 숫자 4096을 분리해서 기억해야 한다.
  • 새 data block을 할당할 때는 bitmap에서 0인 bit를 찾아 1로 바꾼다.
  • 파일을 삭제할 때는 해당 block의 bit를 다시 0으로 바꾼다.

Superblock

• Superblock은 파일 시스템 전체에 대한 metadata를 저장한다.
• 예를 들어 다음 정보를 가진다.

file system type
block size
total number of blocks
number of inodes
number of data bitmap blocks
number of inode bitmap blocks

Allocation Strategies

파일의 logical block을 실제 disk block에 어떻게 mapping할 것인가?

• allocation strategy를 설계할 때 고려해야 할 기준은 다음과 같다.
  • fragmentation이 얼마나 생기는가
  • 파일이 커질 수 있는가
  • sequential access 성능이 좋은가
  • random access가 빠른가
  • metadata overhead가 얼마나 큰가

Contiguous Allocation

• Contiguous allocation은 파일 하나를 disk의 연속된 block들에 배치하는 방식이다.

<starting block number, length>

예를 들어:

file A: start = 10, length = 3

이면 file A는 disk block 10, 11, 12를 사용한다.

장점

• sequential access 성능이 매우 좋다.
  • disk block들이 연속되어 있기 때문이다.
• random access 계산도 쉽다.
  • logical block i는 start + i로 바로 계산된다.
• metadata overhead가 작다.
  • 시작 block과 길이만 저장하면 된다.

단점

• external fragmentation이 심하다.
  • 연속된 빈 공간을 찾아야 하기 때문이다.
• 파일이 커지기 어렵다.
  • 바로 뒤에 빈 block이 없으면 파일을 이동해야 할 수 있다.
• 주기적인 compaction이 필요할 수 있다.

free free A A A free B B free free

여기서 4 block짜리 파일을 만들고 싶어도, 전체 free block 수는 충분하지만 연속된 4개가 없으면 할당이 어렵다.

Linked Allocation

• Linked allocation은 파일의 data block들을 linked list처럼 연결하는 방식이다.
• 각 block 안에 다음 block을 가리키는 pointer가 들어간다.
• metadata는 시작 block만 있으면 된다.

장점

• external fragmentation이 없다.
  • 아무 빈 block이나 가져와서 연결하면 된다.
• 파일이 쉽게 커질 수 있다.
  • 새 block을 하나 할당해서 list 끝에 붙이면 된다.

단점

• random access가 매우 느리다.
  • 100번째 block을 읽으려면 첫 block부터 pointer를 따라가야 한다.
• sequential access 성능도 block들이 흩어져 있으면 나빠진다.
• block마다 pointer 공간이 낭비된다.
• pointer가 손상되면 뒤의 block들을 잃을 수 있다.

A1 -> A2 -> A3 -> A4

이 구조에서 A2의 pointer가 깨지면 A3, A4에 접근하기 어려워진다.

FAT(File Allocation Table)

• pointer를 각 data block 안에 넣지 않고, 별도의 table에 모아둔다.
• 즉 file system 전체 block들의 next block 정보를 FAT에 저장한다.

장점

• data block 안에 pointer를 넣지 않아도 된다.
• FAT를 memory에 cache하면 random access가 linked allocation보다 나아진다.
• MS-DOS, Windows의 FAT12, FAT16, FAT32가 이 방식의 예다.

단점

• FAT 전체가 커질 수 있다.
• 큰 file system에서는 table 크기가 부담이 된다.
• 여전히 block chain을 따라가야 하므로 완전한 direct indexing보다는 random access가 불리하다.

Indexed Allocation

• Indexed allocation은 inode 또는 별도 index block에 data block pointer 배열을 저장하는 방식이다.

장점

• random access가 가능하다.
• 파일이 쉽게 커질 수 있다.
• external fragmentation이 없다.
  • data block들이 연속될 필요가 없다.

단점

• metadata overhead가 크다.
• 작은 파일에는 pointer 배열이 낭비될 수 있다.
• 최대 파일 크기가 index pointer 개수에 의해 제한될 수 있다.

Multi-level Indexing

• Multi-level indexing은 indexed allocation의 확장이다.
• 작은 파일은 direct pointer만 사용하고,
• 큰 파일은 indirect pointer를 통해 pointer block을 추가로 사용한다.
• Unix FFS, Linux Ext2/3 같은 시스템에서 쓰이는 방식이다.
• direct pointer
  • inode가 data block을 직접 가리킨다.
• indirect pointer
  • inode가 pointer block을 가리킨다.
  • pointer block 안에는 data block pointer들이 들어 있다.

Multi-level Indexing in VSFS

• 강의안 예시는 다음 조건을 둔다.
  • inode는 12개의 direct pointer를 가진다.
  • inode는 1개의 single indirect pointer를 가진다.
  • disk address는 4 byte다.
  • block size는 4KB다.
• 그러면 indirect block 하나에는 pointer가 몇 개 들어갈까?

4KB / 4B = 1024 pointers

• 따라서 최대 file size는 다음과 같다.

(12 direct blocks + 1024 indirect blocks) * 4KB
= 1036 * 4KB
= 4144KB

Max file size = (12 + 1024) * 4KB = 4144KB

• 작은 파일은 direct pointer만 써서 빠르게 접근한다.
• 큰 파일은 indirect block을 추가로 써서 더 많은 data block을 가리킨다.

Direct Pointer

• inode 안에 data block 번호가 직접 들어 있는 pointer다.

inode.direct[0] = 100
inode.direct[1] = 101

• 장점:
  • 빠르다.
  • 추가 block read가 필요 없다.
• 작은 파일에 적합하다.
• 대부분의 파일은 작기 때문에 direct pointer는 매우 유용하다.

Indirect Pointer

• inode가 data block을 직접 가리키는 것이 아니라, pointer들이 모여 있는 block을 가리킨다.

inode.indirect -> indirect block
indirect block -> [200, 205, 300, 301, ...]

• 장점:
  • 큰 파일을 지원할 수 있다.
• 단점:
  • indirect block을 먼저 읽어야 하므로 추가 disk read가 필요할 수 있다.
  • 다만 indirect block은 memory에 cache될 수 있다.

Extent-based Allocation

• Extent-based allocation은 여러 개의 연속된 block 묶음, 즉 extent를 파일에 할당하는 방식이다.
• extent는 다음과 같은 정보로 표현된다.

<starting block number, extent size>

예를 들어:

file A:
extent 1 = <100, 8>
extent 2 = <300, 4>

의미는:

block 100~107 사용
block 300~303 사용

• Linux Ext4가 extent-based allocation을 사용한다.
• 보통 extent들을 B+tree 같은 multi-level tree 구조로 관리한다.

장점

• contiguous allocation의 sequential performance 장점을 어느 정도 얻는다.
• 하나의 pointer가 여러 block을 표현하므로 metadata overhead가 작다.
• 파일이 여러 extent로 나뉠 수 있으므로 contiguous allocation보다 유연하다.

단점

• 어느 정도 external fragmentation은 생길 수 있다.
• random access를 위해 extent tree를 탐색해야 한다.
• 구현이 단순 indexed allocation보다 복잡하다.

Allocation Strategy 비교

Directory Organization

• directory는 특별한 file이다.
• 그 내용은 directory entry들이다.
• directory entry는 보통 다음 mapping을 가진다.

<file name, inode number>

• 큰 directory는 여러 data block을 사용한다.
• inode 안의 file type bit를 통해 일반 file인지 directory인지 구분할 수 있다.

1. Table / Linear list
   • directory entry를 순서대로 저장한다.
   • 찾으려면 처음부터 선형 탐색해야 한다.
   • 단순하지만 directory가 커지면 느리다.
2. Tree
   • entry를 정렬된 tree로 관리한다.
   • 평균 search time을 줄일 수 있다.
   • sorted directory listing에도 유리하다.
3. Hash table
   • filename을 hash해서 빠르게 찾는다.
   • 빠르지만 file 수가 많아질 때 확장성을 잘 설계해야 한다.

VSFS Directory

• VSFS에서는 directory를 linear list로 설명한다.
• 각 entry는 대략 다음 정보를 가진다.

inode number
record length
name length
name

• Linux Ext2 directory와 비슷하게 variable-sized name을 지원한다.
• 예를 들어 /dir 안에 foo, bar가 있으면 directory file의 내용은 이런 entry들의 나열이다.

inode  name
2      .
1      ..
12     foo
13     bar

• .은 현재 directory를 의미한다.
• ..은 parent directory를 의미한다.
• 삭제된 entry는 <deleted entry>처럼 빈 공간으로 남을 수 있고, 나중에 재사용될 수 있다.

Read I/O Path

• read()를 호출하면 file system은 먼저 page cache 또는 buffer cache를 확인한다.

read() from file

1. block이 cache에 있는지 확인
2. 있으면 cache에서 user에게 반환
3. 없으면 disk에서 읽음
4. 읽은 block을 cache에 넣음
5. user에게 반환

cache hit:
read -> cache -> user

cache miss:
read -> disk -> cache -> user

• cache hit이면 disk I/O가 없으므로 빠르다.
• cache miss이면 disk I/O가 필요하므로 느리다.
• OS가 buffer cache/page cache를 두는 이유는 같은 block을 반복해서 읽을 때 성능을 높이기 위해서다.

Reading a File: /foo/bar 읽기

• 예를 들어 /foo/bar를 열고 3 block을 읽는다고 하자.
• 내부적으로는 대략 다음 단계가 필요하다.

1. root directory inode를 찾는다.
2. root directory data block을 읽어서 foo entry를 찾는다.
3. foo의 inode를 읽는다.
4. foo directory data block을 읽어서 bar entry를 찾는다.
5. bar의 inode를 읽는다.
6. bar inode의 block pointer를 보고 data block 3개를 읽는다.

/
└── foo
    └── bar

• 이 과정에서 inode block, directory data block, file data block을 여러 번 읽을 수 있다.
• cache가 잘 되어 있으면 많은 read가 cache hit이 된다.
• cache가 비어 있으면 pathname translation부터 file data read까지 여러 disk I/O가 발생한다.

Write I/O Path

• write()는 보통 즉시 disk에 쓰지 않는다.
• 먼저 memory의 page cache 또는 buffer cache에 쓴다.
• 나중에 OS가 적절한 시점에 disk로 flush한다.

write() to file

1. user data를 page cache에 씀
2. 해당 page/block을 dirty로 표시
3. 나중에 OS가 disk에 flush
   - periodic flush
   - fsync()

• write를 지연하는 이유는 성능 때문이다.
  • 여러 작은 write를 모아서 한 번에 쓸 수 있다.
  • 같은 block에 여러 번 write가 발생하면 마지막 상태만 disk에 쓰면 된다.
  • disk scheduling을 더 잘할 수 있다.
• 하지만 reliability 문제가 생긴다.
  • write가 cache에만 있고 disk에 아직 없다면 crash 시 데이터가 사라질 수 있다.
  • 이 문제가 뒤의 crash consistency, journaling 단원으로 이어진다.

Writing a File: /foo/bar 생성 후 3 block 쓰기

• 예를 들어 /foo/bar를 만들고 data block 3개를 쓴다고 하자.
• 단순히 data block만 쓰면 끝나는 것이 아니다.
• 여러 metadata update가 필요하다. 대략 필요한 작업은 다음과 같다.

1. root에서 foo directory를 찾는다.
2. foo directory에 bar라는 directory entry를 추가한다.
3. 새 파일을 위한 inode를 할당한다.
4. inode bitmap을 update한다.
5. data block 3개를 할당한다.
6. data bitmap을 update한다.
7. file inode에 size와 block pointer를 기록한다.
8. data block 3개에 실제 file contents를 쓴다.

create /foo/bar
write block 0
write block 1
write block 2

• 여기서 inode bitmap, data bitmap, directory block, inode block, data block이 모두 바뀔 수 있다.
• 그래서 write/create는 read보다 crash consistency 문제가 더 중요하다.
• 중간에 crash가 나면
  • inode는 block을 가리키는데 bitmap은 free라고 하거나,
  • bitmap은 allocated라고 하는데 inode가 아무도 안 가리키는 상태가 될 수 있다.
• 이게 20단원 file system consistency로 이어지는 핵심 배경이다.

Metadata vs Data

• file system에서는 data와 metadata를 구분해야 한다.

data:
실제 파일 내용

metadata:
파일을 찾고 관리하기 위한 정보

metadata 예시:

superblock
inode bitmap
data bitmap
inode table
directory entry
block pointer
file size

• data block만 제대로 써도 metadata가 틀리면 파일을 찾을 수 없다.
• metadata만 제대로 써도 data block 내용이 garbage라면 읽은 내용이 이상할 수 있다.
• 그래서 file system reliability에서는 metadata consistency가 특히 중요하다.

시험에서 자주 헷갈리는 포인트

1. inode는 파일 이름을 저장하지 않는다
   • 이름은 directory entry에 있다.
   • inode는 metadata와 block pointer를 가진다.
2. bitmap은 free space management용이다
   • inode bitmap: 어떤 inode가 사용 중인지
   • data bitmap: 어떤 data block이 사용 중인지
3. superblock은 파일 시스템 전체 정보다
   • block size, inode 수, block 수, layout 정보 등
4. contiguous allocation은 빠르지만 파일 증가와 fragmentation에 약하다
   • sequential/random 둘 다 좋지만 연속 공간이 필요하다.
5. linked allocation은 grow는 쉽지만 random access가 나쁘다
   • pointer를 따라가야 하기 때문이다.
6. FAT는 linked allocation의 pointer 정보를 table로 뺀 방식이다
   • FAT를 memory에 cache하면 random access가 좀 나아진다.
7. indexed allocation은 random access가 좋다
   • logical block number로 pointer array를 index하면 된다.
8. multi-level indexing은 작은 파일과 큰 파일을 동시에 잘 다루려는 방식이다
   • 작은 파일은 direct pointer
   • 큰 파일은 indirect pointer
9. extent는 연속된 block 묶음을 표현한다
   • <start, length> 여러 개로 파일을 표현한다.
   • Ext4에서 사용한다.
10. write는 보통 disk에 즉시 가지 않는다
    • page cache에 먼저 쓰이고 나중에 flush된다.
    • fsync()는 강제로 disk에 반영하도록 요청한다.