Fast File System(FFS) 정리: 로컬리티와 성능을 이해하는 파일시스템 설계
0. FFS를 이해하기 위한 한 줄 정리
FFS는 결국 이 한 줄로 요약할 수 있습니다.
“디스크는 랜덤 액세스 메모리가 아니다.
디스크 특성을 고려해서(=disk aware) 관련된 것들을 가까이 붙여라.”
- 옛 UNIX 파일시스템은 디스크를 메모리처럼 막 써서 성능이 디스크 대역폭의 2% 수준까지 떨어짐.
- FFS는 디스크 구조와 접근 패턴(로컬리티)을 고려해서 배치 정책을 바꿈.
- API(open, read, write, close 등)는 그대로 두고, 내부 구현만 갈아끼운 것이 포인트.
“같이 쓰는 것들을 근처에 붙인다”는 아주 단순한 원칙이 실제로 큰 성능 차이를 만듭니다.
1. 옛 UNIX 파일시스템 문제: 왜 이렇게 느렸나?
1-1. 옛 구조
S | Inodes | Data Blocks
- Superblock(S): 파일시스템 전체 정보(크기, inode 개수, free list 포인터 등)
- Inodes: 모든 파일의 inode 영역
- Data: 데이터 블록들
구조는 단순했고, 파일/디렉터리 계층 구조를 지원하는 데에는 성공했습니다.
1-2. 근본 원인: 디스크를 “그냥 랜덤 메모리”처럼 씀
- 파일의 inode와 데이터 블록이 디스크 여기저기 멀리 떨어져 배치됨 → inode 읽고, 멀리 seek, 데이터 읽고… 반복.
- free list로 블록을 관리하면서 빈 공간이 디스크 전체에 흩어짐 → 파일 한 개가 여기저기 조각나서 저장(fragmentation).
- 블록 크기가 512바이트로 너무 작아서, 블록당 전송량이 적고, 위치 맞추는 오버헤드가 상대적으로 큼.
예시 – 조각난 파일
초기: A1 A2 B1 B2 C1 C2 D1 D2
B,D 삭제 후: A1 A2 C1 C2
새 파일 E(4블록): A1 A2 E1 E2 C1 C2 E3 E4
→ E는 E1 E2 / E3 E4 로 쪼개져 저장 → 중간에 seek 필요
현대 시스템에서도 로그, 업로드 파일 등을 막 저장하면 비슷한 형태의 문제(랜덤 I/O 폭발)가 재현됩니다.
2. FFS의 핵심 아이디어: Cylinder Group / Block Group
2-1. Cylinder Group이란?
FFS는 디스크를 “한 덩어리”로 보지 않고, 여러 개의 지역 그룹(cylinder group)으로 나눕니다.
- Cylinder: 디스크 여러 플래터에서 중심으로부터 같은 거리의 트랙 묶음.
- Cylinder Group: 연속된 여러 cylinder를 모아 만든 그룹.
현대 디스크는 내부 구조를 안 알려주기 때문에, 실제 구현(ext2/3/4 등)에서는 그냥 연속된 블록 묶음(block group)으로 사용합니다.
2-2. 각 그룹 안에는 무엇이 들어있나?
한 Cylinder / Block Group 내부:
S | ib | db | Inodes | Data
- S: superblock 복사본(여러 그룹에 복제해서 신뢰성 ↑)
- ib: inode bitmap – 이 그룹 안의 inode 할당 여부
- db: data bitmap – 이 그룹 안의 데이터 블록 할당 여부
- Inodes: 이 그룹이 가진 inode 테이블 일부
- Data: 이 그룹 전용 데이터 블록들
옛 시스템은 전역적으로 inode / data / free list를 한 덩어리로 관리했고,
FFS는 그룹마다 inode / data / bitmap을 “지역(local) 단위”로 분리해서 관리합니다.
3. FFS의 배치 정책: “관련된 건 붙이고, 안 관련된 건 떼어놓기”
구조(그룹)가 생겼으니 이제 “어디에 배치할지 정책(Policy)”을 정해야 합니다. FFS가 쓰는 기본 만트라는 딱 이거입니다.
“관련된 것들은 같은 그룹에, 관련 없는 것들은 다른 그룹에.”
3-1. 디렉터리 배치 정책
- 디렉터리는 그룹 전체에 균형 있게 분산시키고 싶음.
- 그래서 새 디렉터리를 만들면:
- “디렉터리 개수가 적고”
- “inode가 많이 남아 있는” 그룹을 골라서 그 그룹에 디렉터리 inode + 데이터를 배치.
3-2. 파일 배치 정책
파일은 두 가지 원칙을 따릅니다.
- 파일의 inode와 데이터 블록을 같은 그룹에
→ inode 읽고 데이터 읽을 때 긴 seek를 피함. - 같은 디렉터리 안의 파일들은 같은 그룹에
→ /a/c, /a/d, /a/e 같은 애들을 한 그룹에 모아두면, 빌드·링크처럼 같은 디렉터리 파일들을 연속으로 읽을 때 seek를 최소화.
3-3. 예시로 보는 효과
다음과 같은 디렉터리/파일 구조가 있다고 하자. (각 파일은 2블록 크기)
/ (root)
/a
/b
/a/c, /a/d, /a/e
/b/f
FFS 정책 적용 시
group inodes data
0 /--------- /---------
1 acde------ accddee---
2 bf-------- bff-------
...
- /a, /a/c, /a/d, /a/e → 같은 그룹(1번)에 모여 있음
- /b, /b/f → 다른 그룹(2번)에 같이 있음
나쁜 예 – inode만 균등 분산
group inodes data
0 /--------- /---------
1 a--------- a---------
2 b--------- b---------
3 c--------- cc--------
4 d--------- dd--------
5 e--------- ee--------
6 f--------- ff--------
...
이 경우, 각 파일의 inode–data 거리는 가깝지만, 같은 디렉터리의 파일들이 그룹 전체에 흩어져 있어서 /a/c, /a/d, /a/e를 읽으려면 여러 그룹 사이를 계속 왔다갔다 해야 합니다.
FFS는 “디렉터리 = 관련성 단위”라고 보고, 디렉터리 단위로 로컬리티를 유지하는 쪽을 택합니다.
4. 실제 접근 패턴: 정말 디렉터리 단위 로컬리티가 있을까?
논문에서는 SEER 트레이스를 분석해서, 파일 오픈 순서의 “경로 거리(path difference)”를 측정합니다.
- 같은 파일을 연속으로 열면 거리 0.
- 같은 디렉터리 안의 다른 파일이면 거리 1.
- 공통 상위 디렉터리까지 거슬러 올라가는 깊이에 따라 거리 2, 3, …
결과(대략):
- 약 7%: 바로 직전에 연 파일을 다시 엶 (거리 0)
- 약 40%: 같은 파일 또는 같은 디렉터리 안의 다른 파일 (거리 0 또는 1)
- 추가 25%: 거리 2 (예:
proj/src/foo.c→proj/obj/foo.o)
→ 즉, 디렉터리 기반 로컬리티 가정은 꽤 설득력 있음. 다만 거리 2 패턴까지 잡아내지는 못한다는 한계도 보여줍니다.
5. Large File Exception: 큰 파일은 예외적으로 흩뿌리기
5-1. 문제: 큰 파일이 그룹 하나를 다 잡아먹는다
만약 큰 파일 하나가 어떤 그룹의 데이터 블록을 거의 다 채워버리면, 그 그룹 안에는 “관련 파일”을 나중에 붙일 자리가 없어집니다.
예시 (Large-file 예외가 없을 때)
/a : 30 blocks
group inodes data
0 /a-------- /aaaaaaaaa aaaaaaaaaa aaaaaaaaaa a---------
1 ---------- ----------
2 ---------- ----------
→ 그룹 0이 /a 로 거의 꽉 차서, 이후 / 안에 다른 파일을 만들 공간이 부족해짐.
5-2. 해결: 큰 파일은 “덩어리(chunk)” 단위로 그룹을 나눠서 배치
FFS는 큰 파일에 대해 다음 전략을 씁니다.
- inode와 직접 포인터 영역(예: 12 블록)은 inode가 있는 그룹에.
- 그 이후 indirect block + 그가 가리키는 블록들은 다른 그룹으로.
- 다음 indirect 영역은 또 다른 그룹으로… 이런 식으로 큰 덩어리 단위로 퍼뜨림.
Large-file 예외 적용 예시 (각 chunk 5블록 가정)
group inodes data
0 /a-------- /aaaaa----
1 ---------- aaaaa-----
2 ---------- aaaaa-----
3 ---------- aaaaa-----
4 ---------- aaaaa-----
5 ---------- aaaaa-----
...
물론 이렇게 흩어지면 큰 파일을 순차적으로 읽을 때 그룹 사이를 seek해야 해서 손해가 있어 보이지만, chunk를 충분히 크게 잡으면 전송시간이 seek 오버헤드를 “평균화(amortization)”해서 괜찮은 성능을 냅니다.
네트워크, DB, 분산스토리지 설계에서도 그대로 등장합니다. (예: HDFS block, DB page 그룹 등)
6. 작은 파일 최적화: Sub-block(프래그멘테이션 줄이기)
FFS는 성능을 위해 블록 크기를 4KB 정도로 크게 쓰고 싶었지만, 그럼 작은 파일(예: 1KB)이 4KB 전체를 차지해서 내부 단편화가 심해집니다
해결: 4KB 블록을 여러 개의 512B sub-block으로 쪼개어 관리
- 작은 파일은 필요할 때까지만 512B 단위 sub-block을 할당.
- 파일이 커져서 full 4KB가 되면:
- 4KB 블록 하나를 잡고,
- 기존 sub-block 내용을 그 블록으로 복사,
- sub-block들을 free로 돌림.
이 과정은 I/O가 추가로 들어서 비싸지만, libc 레벨에서 4KB 단위로 write를 버퍼링하여 대부분의 경우 sub-block 특수처리가 안 일어나도록 최적화합니다.
7. 디스크 레이아웃 튜닝: Parameterized Placement (옛날 디스크 한정)
예전 디스크에서는 트랙을 도는 동안 블록 0을 읽고, OS가 다음 블록 1을 요청하기 전에 블록 1이 지나가버리는 문제가 있었습니다. 그러면 한 바퀴를 더 돌아야 해서, 순차 읽기인데도 회전 지연이 큽니다.
FFS의 해결책
- 블록을 0,1,2,3 순서로 붙여놓지 않고, 0,2,4,… 이런 식으로 “스텝을 둬서” 배치.
- 이렇게 하면 0을 읽고 OS가 준비하는 동안 1은 그냥 지나가도, 2가 올 때 요청이 준비되어 있을 확률이 높음.
- 디스크 특성을 측정해서(회전 속도, 전송 속도 등) 얼마나 건너뛸지(parameterization)를 자동으로 계산.
현대 디스크는 트랙 단위 버퍼(cache)를 자체적으로 가지고 있어서, 파일시스템 수준에서 이렇게 세밀하게 신경 쓸 필요는 거의 없습니다. 디스크가 트랙 전체를 읽어서 내부 캐시에 올려두고, 이후 요청은 캐시에서 바로 응답할 수 있기 때문입니다.
8. 그 외 FFS가 가져온 “사용성” 개선들
FFS는 성능뿐 아니라, 실제로 쓰기 편하게 만드는 기능들도 여럿 도입했습니다.
- 긴 파일 이름 지원: 8글자 제한 같은 것에서 벗어나 보다 표현력 있는 이름 사용 가능.
- Symbolic link:
- 하드링크는 디렉터리/다른 파일시스템 볼륨 등에 제약이 많음.
- 심볼릭 링크는 “경로 문자열”을 들고 다니는 유연한 별칭.
- Rename의 원자성 보장:
rename()을 atomic하게 구현해서, 중간 상태가 보이지 않도록 함(안정적인 “안전 업데이트” 패턴의 기반).
FFS는 성능 + 실제 개발자/사용자가 원하는 기능(긴 이름, symlink, rename)을 같이 가져가면서 성공했습니다.
9. 이 챕터에서 꼭 가져가야 할 핵심 요약
- 옛 UNIX FS의 병목은 디스크 로컬리티를 무시한 배치 + 작은 블록 때문에 생겼다.
- FFS는 디스크를 Cylinder/Block Group으로 나누고, 각 그룹 안에 superblock/bitmap/inode/data를 따로 둔다.
- 정책의 핵심: “같은 디렉터리의 파일 + 그 디렉터리 inode/데이터”를 같은 그룹에 붙인다.
- 실제 워크로드(트레이스)를 보면, 파일 접근에는 디렉터리 기반 로컬리티가 꽤 많이 존재한다.
- 큰 파일은 Large-file Exception으로 그룹을 다 먹지 않게 chunk 단위로 분산한다.
- 작은 파일은 Sub-block(512B 등)으로 내부 단편화를 줄이고, 라이브러리 버퍼링으로 성능 손해를 줄인다.
- 옛 디스크 시대에는 트랙·섹터 배치(Parameterization)도 신경 썼지만, 현대에는 디스크 내부 캐시/추상화가 대부분 처리한다.
- FFS는 성능뿐 아니라, 긴 파일명, symlink, atomic rename 같은 사용성도 함께 개선했다