[OSTEP] 41. 지역성과 FFS (Locality and The Fast File System)

1.1 옛날 유닉스 파일 시스템의 구조적 문제#

초기 파일 시스템은 대략 다음처럼 단순 배치였습니다.

• superblock
• inode 영역
• data 영역

이 설계가 만들어낸 문제는 대표적으로 아래 세 가지입니다.

1. 긴 탐색 거리 inode와 데이터가 물리적으로 멀리 떨어지기 쉬워, 파일을 읽을 때 메타데이터 접근과 데이터 접근 사이에 seek가 자주 발생합니다.

2. 단편화(Fragmentation) free list 기반의 거친 관리로 연속 할당이 깨지기 쉽고, 순차 읽기조차 중간중간 seek를 유발합니다.

3. 작은 블록 크기 512B 같은 작은 블록은 전송 효율이 낮고, 같은 파일을 읽어도 더 많은 I/O를 발생시켜 $T_{\mathrm{seek}} + T_{\mathrm{rot}}$ 비중을 키웁니다.

이제 목표는 명확합니다.

• 관련 있는 것들을 물리적으로 가깝게 두어 $T_{\mathrm{seek}}$와 $T_{\mathrm{rot}}$를 줄인다
• 전송 단위를 키워 $T_{\mathrm{xfer}}$가 지배하도록 만든다

3.1 디렉터리 배치: 분산을 통해 균형을 만든다#

디렉터리는 파일들의 부모입니다. 디렉터리가 한 그룹에 몰리면, 그 그룹은 곧 inode와 데이터 블록이 부족해져서 이후 파일들이 다른 그룹으로 밀려나고 지역성이 깨집니다.

따라서 FFS는 디렉터리를 분산시키는 정책을 택합니다.

• 디렉터리 수가 상대적으로 적고
• free inode가 많은 그룹을 선호

이것은 단순히 디렉터리를 흩뿌리는 것이 아니라, 미래의 파일 생성까지 고려한 load balancing입니다.

3.2 파일 배치: 부모 디렉터리와 가깝게 둔다#

파일은 보통 다음 패턴으로 접근됩니다.

• 디렉터리 탐색으로 inode를 찾고
• inode를 읽은 뒤
• 그 inode가 가리키는 데이터 블록을 읽는다

즉, 메타데이터와 데이터는 함께 움직입니다. 그래서 FFS는 다음을 기본 규칙으로 둡니다.

• 파일 inode는 부모 디렉터리와 같은 그룹에 둔다
• 파일 데이터 블록은 그 inode와 같은 그룹에 두고, 가능하면 연속적으로 배치한다

이 정책은 디렉터리 워크로드(ls, 디렉터리 아래 파일들 연속 접근)와 파일 열기 워크로드(open 후 read)를 동시에 개선합니다. 이것이 FFS가 말하는 공간 지역성(Spatial Locality) 입니다.

3.3.1 시나리오 A: ls -la 같은 메타데이터 중심 워크로드#

ls -la는 단순히 디렉터리 엔트리 목록만 읽는 것이 아니라, 각 파일의 권한, 소유자, 시간 등을 보여주기 위해 inode를 대량으로 읽습니다.

• 디렉터리 데이터 블록을 읽고
• 각 엔트리의 inode를 따라가며 메타데이터를 읽는다

이때 inode들이 디렉터리와 멀리 흩어져 있으면, inode마다 seek가 유발되어 $T_{\mathrm{seek}} + T_{\mathrm{rot}}$가 반복됩니다.

FFS의 기본 규칙은 여기서 효과가 큽니다.

• 부모 디렉터리와 같은 그룹에 파일 inode를 배치
• 결과적으로 한 디렉터리의 inode들이 같은 그룹 근처에 모임
• inode read가 더 연속적으로 진행되어 seek가 줄어듦

즉, ls -la는 파일 데이터가 아니라 메타데이터 지역성에서 이득을 봅니다.

3.3.2 시나리오 B: open 후 read 같은 데이터 중심 워크로드#

일반적인 파일 열기 패턴은 다음 순서를 가집니다.

• 디렉터리 탐색으로 inode를 찾고
• inode를 읽고
• 데이터 블록을 읽는다

inode와 데이터가 서로 멀면, open 직후 read에서 바로 큰 seek가 발생합니다. FFS는 다음을 보장하려 합니다.

• inode와 데이터 블록을 같은 그룹에 배치
• 가능하면 데이터 블록을 연속 배치

따라서 작은 파일이 많은 워크로드에서, inode 접근과 데이터 접근이 물리적으로 가까워져 open-read 경로가 빨라집니다.

3.3.3 시나리오 C: create 폭탄, 예를 들어 untar, 빌드 트리 생성#

압축 해제나 빌드처럼 다음 작업이 반복되는 워크로드가 있습니다.

• 디렉터리 생성
• 작은 파일 다량 생성
• 같은 디렉터리 아래에 파일이 쏟아짐

만약 디렉터리를 한 그룹에 몰아두면, 그 그룹은 빠르게 고갈되고 다음 문제가 생깁니다.

• 디렉터리와 파일 inode, 데이터가 서로 다른 그룹으로 튐
• 같은 디렉터리 아래 파일인데도 locality가 깨짐
• 결과적으로 나중에 그 디렉터리를 스캔할 때 seek가 폭증

그래서 FFS는 디렉터리를 분산해 그룹별로 균형을 만들고, 그 위에 파일을 디렉터리 근처로 붙이는 전략을 택합니다.

5.1 큰 블록과 작은 파일: fragments#

블록을 크게 잡으면 순차 전송 효율은 좋아지지만, 작은 파일에서 내부 단편화가 커집니다. 예를 들어 4KiB 블록에 1KiB 파일을 저장하면 3KiB가 낭비됩니다.

FFS는 이를 완화하기 위해 fragments를 도입합니다.

• 큰 단위로는 4KiB 블록을 사용해 전송 효율을 얻고
• 작은 파일은 더 작은 fragment 단위(예: 512B)로 저장해 공간 낭비를 줄인다
• 파일이 커지면 fragment들을 모아 full block으로 승격시키는 방식으로 관리한다

이로써 성능과 공간 효율 사이의 트레이드오프를 완화합니다.

5.2 파라미터화(Parameterization)와 디스크 인식#

FFS는 디스크의 물리적 특성을 반영하기 위해 다양한 파라미터를 활용했습니다.

• 트랙, 실린더 배치
• 회전 지연을 고려한 배치
• 연속 블록 접근에서 섹터를 놓치지 않기 위한 스큐(skew)와 유사한 기법

이런 디스크 인식 최적화는 현대 디스크, 컨트롤러(큰 캐시, 내부 재배치, NCQ 등)에서는 의미가 약해진 부분도 있지만, 중요한 메시지는 남습니다.

• 파일 시스템은 저장장치의 비용 구조를 이해하고 설계되어야 한다