[OSTEP] 스터디 16주차 Fast File System (FFS) 와 로그 구조화 파일 시스템 (LFS)

Fast File System (FFS)은 1984년 Berkeley의 Kirk McKusick이 기존 UNIX 파일 시스템(UFS, Old Unix File System)의 성능 문제점을 해결하기 위해 설계한 파일 시스템이다. FFS의 핵심은 디스크의 지역성(Locality)을 활용하여 I/O 효율을 극대화하는 것이다.

---

Fast File System (FFS)

1. FFS 탄생 배경: 기존 UNIX FS의 문제점

기존 UNIX 파일 시스템(UFS)은 단순하고 깔끔했지만, 다음 두 가지 주요 문제 때문에 성능이 매우 나빴다.

1. 작은 블록 크기 (Small Block Size): UFS는 512 바이트의 작은 블록 크기를 사용했다. 이는 하나의 파일을 읽을 때 디스크 I/O 횟수가 많아져 효율성이 떨어지고, 파일 전체를 읽는 데 많은 시간이 걸렸다.
2. 데이터 지역성 부재 (Lack of Data Locality): UFS는 Inode(파일 메타데이터)와 데이터 블록을 디스크 전체에 무작위로 할당하는 경향이 있었다. 파일의 Inode를 읽고 해당 데이터 블록을 읽기 위해 디스크 헤드가 먼 거리를 이동해야 했으므로 탐색 시간(Seek Time)이 길어지고 회전 지연(Rotational Latency)이 증가하여 성능이 크게 저하되었다.

2. FFS의 주요 개선 사항 (핵심 메커니즘)

FFS는 하드웨어, 특히 디스크의 기하학적 구조(Disk Geometry)를 인지하는 설계를 도입하여 이러한 문제를 해결했다.

① 큰 블록 크기 도입

• 개선: FFS는 블록 크기를 4KB 또는 8KB로 늘렸다.
• 효과: 한 번의 디스크 I/O로 더 많은 데이터를 전송할 수 있게 되어, 파일당 필요한 I/O 횟수가 줄고, 전송 효율(Transfer Efficiency)이 극대화되었다. (단, 작은 파일의 내부 단편화(Internal Fragmentation) 문제가 생길 수 있어, 이를 해결하기 위해 프래그먼트(Fragment) 개념을 도입했다.)

② 실린더 그룹 (Cylinder Group, CG)

• 개념: 디스크를 논리적인 실린더 그룹 단위로 나눈다. 각 실린더 그룹은 디스크의 연속된 트랙(Cylinder) 묶음으로 구성된다.
• 구조: 각 CG는 자체적인 슈퍼블록 복사본, 자유 공간 비트맵, Inode 목록, 그리고 데이터 블록 영역을 가진다.
• 효과: 파일의 Inode와 데이터 블록을 같은 실린더 그룹 내에 할당하려고 시도한다. Inode와 데이터가 지리적으로 가까워지면서 디스크 헤드의 이동 거리(Seek Time)가 최소화되고 성능이 크게 향상되었다.

③ 지역성을 위한 할당 정책

FFS는 지역성을 높이기 위해 다음과 같은 할당 정책을 따른다.

1. 새로운 파일 할당: 새로운 디렉토리에 파일을 만들 때, FFS는 현재 디렉토리와 다른 실린더 그룹을 선택하려고 노력한다. 이는 여러 디렉토리에 걸쳐 I/O를 분산시키기 위함이다.
2. 동일 파일 블록 할당: 파일의 첫 번째 데이터 블록을 할당한 후, 나머지 데이터 블록들은 가급적 동일한 실린더 그룹 내의 연속된 영역에 할당하려고 시도한다. 이는 파일을 순차적으로 읽을 때 탐색 시간을 최소화한다.
3. 데이터와 메타데이터의 근접성: Inode와 해당 파일의 데이터 블록을 같은 실린더 그룹 내에 배치하여 메타데이터 접근 후 데이터 접근 시의 헤드 이동을 최소화한다.

FFS는 "디스크의 구조를 인지하고 데이터를 할당하자"는 철학을 바탕으로 지역성(Locality)을 극대화하여 기존 UFS의 고질적인 성능 문제를 해결했다. FFS의 설계는 이후 모든 파일 시스템 설계에 큰 영향을 미쳤다.

---

LFS(Log-structured File System)

LFS(Log-structured File System)는 1990년대 초 버클리 대학에서 제안된 혁신적인 파일 시스템이다. FFS가 디스크의 지역성을 개선했다면, LFS는 "모든 쓰기를 순차적(Sequential)으로 처리하여 디스크 성능을 극대화하자"는 아이디어에서 출발했다.

1. LFS의 탄생 배경 (Why LFS?)

1. 메모리 크기의 증가: 시스템 메모리(RAM)가 커지면서 읽기 요청은 대부분 캐시에서 처리된다. 따라서 파일 시스템의 성능은 결국 쓰기 성능에 의해 결정되게 되었다.
2. 임의 쓰기(Random Write)의 한계: 기존 FFS는 메타데이터와 데이터를 업데이트할 때 디스크의 여러 위치를 오가며 쓰기 때문에 탐색 시간(Seek Time)이 많이 발생한다.
3. 순차 쓰기의 압도적 속도: 하드 디스크는 임의 쓰기보다 순차 쓰기가 수십 배 이상 빠르다.

2. 핵심 메커니즘: 쓰기 버퍼링과 로그 (The Write Buffer)

LFS는 데이터를 바로 디스크에 쓰지 않는다. 대신 메모리에 '세그먼트(Segment)'라고 불리는 큰 버퍼를 두고 쓰기 요청을 모은다. 버퍼가 가득 차면, 이를 디스크의 비어 있는 연속된 공간에 단 한 번의 순차 쓰기로 기록한다.

• 로그(Log) 구조: 디스크는 하나의 거대한 로그처럼 취급된다. 새로운 데이터, 수정된 데이터, 심지어 아이노드(Inode)까지도 항상 로그의 끝에 추가(Append)된다.

3. 아이노드 맵 (Inode Map, imap)

데이터가 항상 다른 위치에 써진다면, 아이노드(Inode)의 위치도 계속 변하게 된다. 이를 해결하기 위해 LFS는 아이노드 맵이라는 간접 층을 도입했다.

• imap: 아이노드 번호를 입력하면 현재 그 아이노드가 디스크 어디에 있는지(주소)를 알려주는 테이블.
• 체크포인트 지역(CR): imap 자체의 위치를 알기 위해 디스크의 고정된 장소에 CR을 둔다.

4. 가비지 컬렉션 (Garbage Collection / Cleaning)

데이터를 수정할 때 기존 데이터를 덮어쓰지 않고 새로운 곳에 쓰기 때문에, 디스크에는 '오래된 데이터(Garbage)'가 남게 된다. 이를 정리하여 빈 공간을 만드는 과정이 필요하다.

1. 청소기(Cleaner) 동작: 가득 찬 세그먼트들을 읽어 들여 현재 유효한(Live) 데이터만 골라낸다.
2. 새로운 세그먼트 생성: 살아남은 데이터들만 모아서 다시 새로운 세그먼트에 순차적으로 쓴다.
3. 공간 확보: 데이터가 모두 옮겨진 옛날 세그먼트들은 이제 빈 공간으로 재사용된다.