19. Fast File system (FFS)

The Original Unix FS

• 초기 Unix file system은 매우 단순한 구조였다.
• 크게 세 영역으로 나뉜다.

1. Superblock
   • file system의 기본 정보를 저장한다.
   • inode와 data block의 freelist head를 가진다.
2. Inode list
   • 모든 inode가 한 곳에 모여 있다.
   • inode는 inode list 안의 index로 참조된다.
   • 모든 inode는 같은 크기다.
3. Data blocks
   • 실제 file contents가 저장되는 곳이다.
   • 하나의 data block은 한 file에만 속한다.

• 이 구조는 구현하기 쉽고 직관적이지만, disk 성능을 제대로 활용하지 못했다.

Why So Slow?

• 기존 Unix FS가 느린 이유는 크게 세 가지다.

Problem 1: Blocks Too Small

• 기존 Unix FS의 block size는 작았다.
  • 예: 512 bytes
• block이 너무 작으면 다음 문제가 생긴다.
  • file 하나를 표현하기 위해 필요한 block 수가 많아진다.
  • file index가 커진다.
  • indirect block이 더 많이 필요하다.
  • disk에서 한 번에 가져오는 양이 작아서 transfer rate가 낮다.

예를 들어 같은 4KB 파일을 저장한다고 하면:

512B block 사용  -> 8 blocks 필요
4KB block 사용   -> 1 block 필요

• 작은 block은 공간 낭비는 줄일 수 있지만, 큰 파일을 읽을 때는 너무 많은 block 접근이 필요하다.
• disk는 seek와 rotational delay가 비싸기 때문에, 작은 block을 여러 번 읽는 것은 성능에 불리하다.

Problem 2: Unorganized Freelist

• 기존 Unix FS는 free block을 freelist로 관리했다.
• freelist는 “첫 번째 free block이 다음 free block을 가리키고, 그 block이 또 다음 free block을 가리키는” 방식이다.

free block 5 -> free block 100 -> free block 12 -> free block 300 ...

• 문제는 시간이 지나면 free block들이 disk 전체에 흩어진다는 점이다.
• 파일을 새로 만들 때 연속된 block을 얻기 어렵다.
• 그 결과 하나의 파일 block들이 disk 곳곳에 흩어진다.

A1 ... B1 ... A2 ... C1 ... A3 ...

• 파일 A를 순차적으로 읽어도 disk head가 계속 이동해야 한다.
• 이것이 fragmentation due to aging이다.
• file system이 오래 사용될수록 block들이 더 흩어지고 성능이 나빠진다.

Problem 3: Poor Locality

• 기존 Unix FS에서는 inode list와 data blocks가 분리되어 있었다.
• 그래서 inode와 그 inode가 가리키는 data block이 멀리 떨어질 수 있다.
• pathname traversal이나 file manipulation에서는 inode와 data block을 번갈아 읽는 경우가 많다.
• 이때 inode와 data가 멀리 있으면 seek가 많이 발생한다.

예를 들어:

Inode List: iA, iB, iC ...
Data Blocks: A1, A2, A3, B1, B2 ...

• iA를 읽고 나서 A1을 읽어야 하는데 둘이 멀리 있으면 disk seek가 발생한다.
• 또 같은 directory 안의 파일들이 서로 가까운 inode slot에 있지 않을 수 있다.
• 그래서 ls, grep foo *.c처럼 directory 안 여러 파일을 훑는 작업도 느려진다.
• 강의안은 이를 “inodes far from data blocks”, “inodes for directory not close together”, “poor enumeration performance”로 설명한다.

FFS의 기본 방향

• FFS는 BSD Unix 쪽에서 기존 Unix FS를 redesign한 파일 시스템이다.
• 중요한 점은 interface는 그대로 유지하고 internal implementation만 바꿨다는 것이다.
  • 사용자는 여전히 open, read, write, close 같은 Unix API를 쓴다.
  • 하지만 내부 disk layout과 allocation policy가 달라진다.
• FFS의 핵심은 interface를 바꾸는 것이 아니라, internal implementation을 disk-aware하게 바꾸는 것이다.
• FFS의 핵심은 disk-awareness다.
• 즉 disk를 random-access memory처럼 취급하지 않고, seek와 locality를 고려해서 배치한다.
• 관련 있는 것들을 가까운 cylinder에 둬서 seek를 줄인다.
• 강의안도 FFS의 기본 아이디어를 “place related things on nearby cylinders to reduce seeks”라고 설명한다.

Solution 1: Larger Blocks

• 기존 Unix FS의 작은 block 문제를 해결하기 위해 FFS는 block size를 키웠다.
  • 예: 4096B 또는 8192B
• block size를 키우면 sequential access 성능이 좋아진다.
• 이유는 한 번의 disk access로 더 많은 데이터를 가져오기 때문이다.

512B block  -> 작은 단위로 여러 번 읽음
4KB block   -> 한 번에 더 많이 읽음
8KB block   -> 더 큰 단위로 읽음

• 큰 block은 특히 큰 파일을 순차적으로 읽을 때 유리하다.
• 하지만 문제가 있다.

block이 커지면 internal fragmentation이 커질 수 있다.

예를 들어 block size가 4KB인데 파일 크기가 1KB라면:

사용한 공간: 1KB
낭비된 공간: 3KB

• 그래서 FFS는 큰 block과 작은 fragment를 함께 사용한다.

Fragments

• Fragment는 큰 block을 더 작은 단위로 나눈 것이다.
• FFS는 큰 block size를 사용하되, 작은 파일이나 파일의 마지막 부분에는 fragment를 사용할 수 있게 한다.
• 강의안에서는 FFS가 4096B 또는 8192B의 큰 block을 사용하고, block을 2, 4, 8개의 fragment로 쪼갤 수 있다고 설명한다.

예를 들어:

Block size = 4KB
Fragment size = 1KB

• 1KB 파일은 4KB block 전체를 차지하지 않고 1KB fragment 하나만 쓸 수 있다.
• 5KB 파일은 4KB block 하나 + 1KB fragment 하나로 저장할 수 있다.

file size 5KB
= 4KB full block + 1KB fragment

Fragment의 장점

• 큰 파일에서는 큰 block을 써서 transfer speed를 높인다.
• 작은 파일이나 파일 끝부분에서는 fragment를 써서 낭비를 줄인다.
• 즉 성능과 공간 효율을 동시에 잡으려는 절충안이다.

Solution 2: Bitmap

• FFS는 free space management에서 freelist 대신 bitmap을 사용한다.
• bitmap은 각 block이 free인지 allocated인지 bit 하나로 표현한다.

1 0 0 1 1 0 1 ...

의미는:

1: 사용 중
0: 비어 있음

• bitmap의 장점은 더 global한 view를 제공한다는 것이다.
• freelist는 단순히 다음 free block을 따라가는 구조라서 전체 free space 패턴을 보기 어렵다.
• 반면 bitmap은 연속된 free block을 찾기 쉽다.

예를 들어 bitmap이 다음과 같다면:

111100001111

• 가운데 0000을 보고 연속된 free block 4개를 쉽게 찾을 수 있다.
• 그래서 파일 block들을 더 연속적으로 배치할 수 있고, fragmentation을 줄일 수 있다.
• 강의안도 bitmap이 contiguous free blocks를 더 빠르게 찾고 file fragmentation을 줄이는 데 도움을 준다고 설명한다.

Freelist vs Bitmap

• FFS는 bitmap을 통해 “조금 더 많은 metadata 공간을 쓰더라도 allocation decision을 더 똑똑하게 하자”는 방향을 선택했다.

Solution 3: Cylinder Groups

• FFS의 가장 중요한 구조 중 하나가 cylinder group이다.
• disk를 여러 개의 cylinder group으로 나눈다.
• 각 cylinder group 안에 관련 metadata와 data를 함께 둔다.

Cylinder Group 0 | Cylinder Group 1 | ... | Cylinder Group N

• 핵심은 파일 시스템 전체에 inode와 data를 한 곳씩 몰아두지 않고, 각 group 안에 함께 배치하는 것이다.

Block group 0: superblock copy, inode bitmap, data bitmap, inodes, data blocks
Block group 1: superblock copy, inode bitmap, data bitmap, inodes, data blocks
...

• 현대 disk는 예전처럼 실제 cylinder geometry를 그대로 노출하지 않기 때문에, 현대 파일 시스템에서는 cylinder group 대신 block group이라는 표현을 많이 쓴다.
• Linux Ext2/3/4도 block group 구조를 사용한다.
• 강의안에서도 modern file systems는 block groups로 구성한다고 설명한다.

On-Disk Layout

• FFS는 각 cylinder group 안에 여러 구조를 함께 둔다.
• 여기서 S는 superblock copy다.
• superblock을 여러 group에 복제하는 이유는 reliability 때문이다.
• 한 곳의 superblock이 손상되어도 다른 copy를 이용해 복구할 수 있다.
• FFS는 block size도 4KB 정도로 키워 throughput을 개선한다.

Clustering in FFS

• FFS는 locality를 높이기 위해 clustering을 한다.
• 핵심 원칙은 다음과 같다.

1. Sequential blocks should be close
   • 파일의 연속 block들을 가까운 sector에 둔다.
   • 한 block을 읽으면 다음 block도 곧 읽을 가능성이 높기 때문이다.
   • 이것은 spatial locality를 활용하는 것이다.
2. Inode and data blocks should be close
   • 어떤 inode를 읽으면, 그 파일의 data block도 곧 읽을 가능성이 높다.
   • 따라서 inode와 data를 같은 cylinder group에 배치한다.
3. Files in same directory should be close
   • 같은 directory 안의 파일들은 함께 접근될 가능성이 높다.
   • 예: ls -l, grep foo *.c
   • 따라서 같은 directory의 inode들을 같은 cylinder group에 두려고 한다.

Allocation Policies

Keep related stuff together.

Directory Allocation

• directory는 여러 파일을 묶는 기준이 된다.
• FFS는 directory를 cylinder group들에 균형 있게 배치하려고 한다.
• 새 directory를 만들 때는 다음 조건을 고려한다.
  • 이미 allocated directory 수가 적은 group
  • free inode 수가 많은 group
• 이유는 directory들이 특정 group에 몰리면 그 group만 혼잡해지기 때문이다.
• 그래서 directory는 여러 group에 분산시켜 전체 disk 공간을 균형 있게 사용한다.

File Allocation

• 같은 directory 안의 file들은 함께 접근될 가능성이 높다.
• 따라서 FFS는 같은 directory 안의 file들을 해당 directory가 있는 cylinder group에 배치하려고 한다.
• 일반 file의 data block은 그 file의 inode와 같은 group에 배치한다.

directory /src -> cylinder group 3
/src/a.c       -> cylinder group 3
/src/b.c       -> cylinder group 3
/src/main.c    -> cylinder group 3

• 이렇게 하면 /src 안의 파일들을 읽을 때 seek가 줄어든다.

Large File Allocation

• 큰 파일은 하나의 cylinder group에 전부 넣지 않는다.
• 큰 파일을 한 group에 모두 넣으면 그 group의 공간을 너무 많이 차지하고, 다른 파일 배치가 어려워진다.
• 그래서 FFS는 large file의 data block을 chunk 단위로 나누어 여러 cylinder group에 분산시킨다.

large file:
chunk 1 -> group 2
chunk 2 -> group 3
chunk 3 -> group 4
...

• 이는 locality와 space balance 사이의 절충이다.
• 작은 파일은 locality가 중요하므로 같은 group에 몰아두고,
• 큰 파일은 전체 disk bandwidth와 공간 균형을 위해 여러 group에 분산한다.

FFS Performance Numbers

• Original Unix FS는 최대 disk bandwidth의 약 2%만 달성했다.
• 강의안 summary 기준으로 original Unix FS는 대략 disk bandwidth의 3%~5% 수준이었다.
• FFS는 disk bandwidth의 약 14%~47%를 달성했다.
• 하지만 file system이 거의 full 상태가 되면 좋은 block 배치가 어려워져 throughput이 절반 정도로 떨어질 수 있다.

Other Features

• FFS는 cylinder group과 bitmap 외에도 여러 기능을 도입했다.

1. Fragments
   • internal fragmentation을 줄이기 위한 기능.
   • 작은 파일이나 파일 끝부분에 사용한다.
2. File system parameterization
   • disk 회전 특성을 고려해 다음 block이 disk head 아래에 올 타이밍을 맞춘다.
   • 예전 HDD에서는 block을 무조건 바로 옆에 두면, 다음 요청을 처리할 때 이미 지나가 버릴 수 있었다.
   • 그래서 일부 block을 건너뛰어 배치하는 방식이 쓰였다.
3. Free space reserve
   • file system이 너무 꽉 차면 좋은 배치를 하기 어려워진다.
   • 일정량의 free space를 남겨둬야 allocation policy가 제대로 동작한다.
4. Long file names
   • 더 긴 파일 이름을 지원한다.
5. Atomic rename
   • rename이 중간 상태 없이 atomic하게 보이도록 한다.
   • crash consistency와도 관련이 있다.
6. Symbolic links
   • pathname을 가리키는 link를 지원한다.

Original Unix FS vs FFS