파일 시스템 연속, 연결, 색인 할당

핵심 인사이트 (3줄 요약)

본질: 디스크에 파일을 저장할 때, 수많은 데이터 블록들을 어떤 방식으로 흩뿌리고 이어 붙일 것인가를 결정하는 물리적 파일 할당(File Allocation) 기법의 3대장이다.

3가지 방법: 디스크에 순서대로 쫙 붙여서 저장하는 연속 할당(Contiguous), 블록들을 기차처럼 포인터로 꼬리에 꼬리를 물게 만든 연결 할당(Linked), 그리고 목차(색인 블록) 하나를 두고 모든 블록의 위치를 적어두는 색인 할당(Indexed) 방식이 있다.

가치: 연속은 속도가 빠르지만 단편화(구멍)로 멸망했고, 연결은 단편화는 잡았지만 탐색 속도가 너무 느렸으며, 색인 할당은 이 둘의 장점을 섞어 현대 UNIX/리눅스 파일 시스템(i-node)의 뼈대가 되었다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념:
- 파일 할당 (File Allocation): 하드디스크의 텅 빈 공간(Blocks)들에 파일의 데이터를 어떻게 분배하고, 나중에 그 파일들을 다시 찾기 위해 디렉터리에 어떻게 기록해 둘 것인지 결정하는 방법.
- 연속 할당 (Contiguous Allocation): 파일 데이터를 디스크의 물리적으로 연속된 빈 블록에 저장함.
- 연결 할당 (Linked Allocation): 파일 데이터를 디스크 아무 데나 흩뿌리고, 각 블록의 끝에 '다음 블록의 주소(포인터)'를 적어 이어줌.
- 색인 할당 (Indexed Allocation): 파일 데이터를 흩뿌려 두되, '인덱스 블록(목차)' 하나를 따로 만들어서 흩어진 블록들의 주소를 한 곳에 싹 모아둠.
필요성 (디스크 공간과 탐색 속도의 트레이드오프):
- 파일을 연속해서 저장하면 디스크 헤드가 한 번만 징~ 움직이면 되니까 속도가 엄청 빠르다. 하지만 파일을 지웠다 썼다 하면 중간중간 빈 공간(외부 단편화)이 생겨서, 나중엔 큰 파일을 저장할 수 없게 된다.
- 빈 공간을 없애려고 데이터를 찢어서 아무 데나 막 저장하면(연결 할당), 10번째 블록을 찾기 위해 헤드가 디스크 전체를 10번이나 이리저리 뛰어야 하는 탐색(Seek) 지옥이 열린다.
- 해결책: "빈 공간도 알뜰하게 쓰면서(비연속), 10번째 블록도 한 번에 훅 찾아갈 수 있는(직접 접근)" 중간 타협점(색인 할당)이 필요했다.
💡 비유:
- 연속 할당: 영화관에서 친구 5명이 무조건 **'연속된 5자리'**에만 앉는 것. 한 번에 찾기 쉽지만, 남은 자리가 띄엄띄엄 있으면 영화를 못 본다.
- 연결 할당: 친구 5명이 극장 아무 데나 흩어져 앉는다. 대신 1번 친구에게 "2번 친구 어디 앉았어?" 묻고, 2번 친구에게 가서 "3번 어딨어?" 묻는 방식. 자리가 남기만 하면 무조건 앉을 수 있지만, 5번 친구를 찾으려면 1, 2, 3, 4번을 다 거쳐야 한다 (속도 최악).
- 색인 할당: 친구들은 아무 데나 앉되, 매표소 직원(인덱스 블록)이 **'5명의 좌석 번호가 모두 적힌 장부'**를 들고 있다. 5번 친구를 찾으려면 직원에게 장부만 보면 0.1초 만에 바로 찾아갈 수 있다.
발전 과정:
1. 연속 할당: 마그네틱 테이프 시절이나 읽기 전용 CD-ROM에서 주로 쓰임.
2. 연결 할당: MS-DOS의 FAT(File Allocation Table) 파일 시스템으로 발전.
3. 색인 할당: 현대 UNIX의 ext4 (i-node 구조), Windows NTFS 등 거의 모든 운영체제 스토리지의 표준.
📢 섹션 요약 비유: 짐(파일)을 창고(디스크)에 넣는 3가지 방식입니다. 하나로 묶어서 큰 통에 넣거나(연속), 짐들을 밧줄로 길게 묶어서 흩어놓거나(연결), 짐을 흩어놓고 보물지도(색인)를 그리는 것입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

3가지 할당 방식의 구조와 디렉터리 구성

디렉터리(폴더)가 각 파일의 정보를 어떻게 기록하는지가 핵심이다.

1. 연속 할당 (Contiguous Allocation)

디렉터리 기록: [파일 이름] | [시작 블록 번호] | [파일 길이(블록 수)]
동작: 파일 A가 시작: 10, 길이: 3이면 무조건 10, 11, 12번 블록에 저장됨.
장점: 순차 접근과 직접 접근(Random Access, 예: $10 + i$) 모두 광속이다. 헤드 이동이 거의 없다.
단점: 파일을 키울 수 없다(파일 뒤에 남이 자리 잡고 있으면 꼼짝 못 함). 외부 단편화가 극심하다.

2. 연결 할당 (Linked Allocation)

디렉터리 기록: [파일 이름] | [시작 블록 번호] | [끝 블록 번호]
동작: 시작: 9. 9번 블록으로 가면 데이터와 함께 "다음은 16번 블록"이라는 포인터가 있음. 16번으로 가면 "다음은 1번"... 이렇게 꼬리를 묾.
장점: 외부 단편화 0%. 디스크가 꽉 찰 때까지 무조건 저장 가능. 파일 크기를 마음대로 늘릴 수 있음.
단점: 직접 접근 불가(100번째 블록을 보려면 1번부터 99번까지 다 읽어야 함). 포인터를 저장할 4바이트 때문에 블록 크기(512바이트)가 508바이트로 줄어들어 2의 승수 연산이 깨짐. 포인터 하나 끊어지면 파일 뒷부분이 통째로 날아감.

3. 색인 할당 (Indexed Allocation)

디렉터리 기록: [파일 이름] | [인덱스 블록 번호]
동작: 인덱스 블록 19를 가리킴. 19번 블록을 열어보니 [9, 16, 1, 10, 25] 라고 파일의 모든 데이터 블록 주소가 배열처럼 쫙 적혀있음.
장점: 흩어져 있어도 단편화가 없고, 인덱스 배열 덕분에 i번째 블록을 한 번에 찾아가는 직접 접근($O(1)$)이 가능함.
단점: 1바이트짜리 작은 파일을 저장해도, 인덱스 블록 1개와 데이터 블록 1개, 총 2개의 블록을 무조건 써야 하는 공간 낭비(Overhead)가 발생함.

Ⅲ. 융합 비교 및 다각도 분석

할당 방식별 파일 접근 속도(I/O Performance) 비교

할당 방식	순차 접근 (Sequential)	직접 접근 (Random/Direct)	헤드 탐색(Seek) 페널티
연속 할당	매우 빠름	매우 빠름 ($O(1)$)	거의 없음 (연속해서 읽음)
연결 할당	보통 (포인터 따라감)	매우 느림 ($O(N)$)	극심함 (디스크 이리저리 뜀)
색인 할당	빠름	빠름 ($O(1)$)	보통 (인덱스를 먼저 읽어야 함)

과목 융합 관점

자료구조 (Data Structure): 디스크 할당 방식은 램(RAM)의 자료구조와 완벽한 평행이론을 이룬다.
- 연속 할당 = 배열 (Array)
- 연결 할당 = 연결 리스트 (Linked List)
- 색인 할당 = 포인터 배열 (Array of Pointers)
컴퓨터구조 (CA): 디스크 암(Arm)의 움직임은 엄청나게 비싸다(ms 단위). 색인 할당에서 최악의 시나리오는 인덱스 블록을 읽기 위해 헤드가 1번 움직이고, 실제 데이터 블록을 읽기 위해 헤드가 2번 움직이는 Double I/O 병목이다. 이를 막기 위해 현대 OS는 인덱스 블록(inode)을 램(RAM)의 캐시에 통째로 올려두고(VFS inode cache) 디스크 헤드를 움직이지 않게 방어한다.
📢 섹션 요약 비유: 연속 할당은 백과사전 1,2,3권을 나란히 꽂는 것(배열), 연결 할당은 1권 끝에 '다음 권은 2층 서재에 있음' 쪽지를 남기는 것(링크드 리스트), 색인 할당은 도서관 검색대 PC에 1,2,3권의 위치를 전부 저장해 두는 것(포인터 배열)입니다.

Ⅳ. 실무 적용 및 기술사적 판단

실무 시나리오

시나리오 — 동영상 편집 서버의 파일 시스템 설계 (연속 할당의 부활): 유튜브 같은 동영상 처리 서버에서는 10GB짜리 영상을 처음부터 끝까지 순차적으로 쫙 읽어 들이는 작업(Sequential Read)이 핵심이다.
- 아키텍처 판단: 여기서 색인 할당(ext4)을 써서 파일이 1만 개의 조각으로 찢어지면, 헤드가 1만 번 튀어 영상이 미친 듯이 버벅거린다.
- 대응 (Extent Allocation): 최신 파일 시스템(XFS, btrfs, ext4의 Extent)은 색인 할당의 유연성에 연속 할당의 속도를 합쳤다. 파일을 4KB 단위로 조각내지 않고, 아예 "10번부터 1,000번까지 연속으로 990개!"라는 식의 Extent(거대한 연속 덩어리) 단위로 인덱스를 묶어버린다. 동영상 서버에 특화된 극강의 순차 읽기 성능을 발휘한다.
시나리오 — 1바이트짜리 로그 파일 수백만 개와 색인 할당의 저주 (No space left on device): 개발자가 서버에 로그를 남기는데, 파일 1개당 "OK" (2바이트)만 적어서 파일 100만 개를 생성했다. 디스크 용량은 1TB 중 1GB밖에 안 썼는데, 갑자기 "No space left on device" 에러가 뜨며 서버가 뻗었다.
- 원인 분석: 전형적인 색인 할당(i-node)의 함정이다. 색인 할당은 파일 1개를 만들 때 무조건 '목차(인덱스 블록)'를 1개 만들어야 한다. 리눅스 ext4는 포맷할 때 이 목차 장부(i-node table)의 개수를 미리 정해놓는다(예: 100만 개).
- 1TB 용량은 남았지만, 100만 개의 인덱스 장부가 꽉 차버려서(inode exhaustion) 더 이상 새 파일을 만들 수 없게 된 것이다.
- 대응 (기술사적 가이드): 자잘한 파일을 많이 다루는 서버(메일 서버, 이미지 썸네일 서버)는 파일 시스템 포맷(mkfs) 시 -i 옵션을 주어 inode 덴시티(밀도)를 높이거나(목차를 많이 만들거나), 자잘한 파일을 지원하는 XFS 같이 inode를 동적 할당하는 최신 파일 시스템으로 인프라를 변경해야 한다.

의사결정 및 튜닝 플로우

  ┌───────────────────────────────────────────────────────────────────┐
  │                 워크로드 특성에 따른 파일 할당(File System) 아키텍처      │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [새로운 스토리지 서버(SAN/NAS) 포맷 시 파일 시스템 아키텍처 선택]            │
  │                │                                                  │
  │                ▼                                                  │
  │      주로 저장되는 파일이 '작고(Small)' 개수가 '무수히 많은가(Millions)'?    │
  │          ├─ 예 ─────▶ [인덱스(i-node) 최적화 FS 필수]                 │
  │          │            (ReiserFS, XFS 등 inode 동적 할당 FS 적용 또는       │
  │          │             ext4 포맷 시 inode ratio 극대화 튜닝)            │
  │          └─ 아니오 (기가바이트 단위의 거대한 파일이 주를 이룬다)              │
  │                │                                                  │
  │                ▼                                                  │
  │      거대 파일들을 '임의 접근(Random Access)'으로 자주 뒤섞어서 읽는가?        │
  │      (예: RDBMS 데이터 파일, 가상머신 이미지)                             │
  │          ├─ 예 ─────▶ [색인 할당(Indexed) + B-Tree 구조 적용]         │
  │          │            (ZFS, Btrfs 같은 고성능 B-Tree 인덱스 파일 시스템)    │
  │          │                                                        │
  │          └─ 아니오 ──▶ (순차 접근 위주의 동영상, 백업 파일)                 │
  │                         [연속 할당(Extent)이 지원되는 ext4 / XFS 사용]    │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] "그냥 리눅스 깔 때 기본인 ext4 쓰면 되는 거 아니야?"라는 마인드는 레거시 환경에서만 통한다. 1초에 수만 개의 이미지 메타데이터를 저장하는 서버에 색인 할당의 오버헤드를 그대로 맞으면 디스크 IOPS가 터진다. 아키텍트는 저장될 데이터의 크기, 개수, 접근 패턴(순차 vs 랜덤) 3가지를 분석해 디스크 할당 철학을 디자인해야 한다.

도입 체크리스트

거대 파일의 인덱스 한계 (Indirect Block): 인덱스 블록(목차) 1개가 4KB라면, 그 안에 담을 수 있는 주소는 기껏해야 1,000개(4MB 분량)다. 만약 10GB짜리 영화를 넣으려면? 인덱스 블록이 또 다른 인덱스 블록을 가리키게 만드는 다중 간접 할당(Multi-level Indexed Allocation) 구조로 성능이 심하게 저하(I/O 깊이 증가)됨을 인지하고, 이를 Extent 기법으로 상쇄시킬 수 있는지 체크했는가?
📢 섹션 요약 비유: 1바이트짜리 메모를 쓰기 위해 매번 양장본 가죽 다이어리(인덱스 블록)를 하나씩 사서 쓰는 것은 낭비(inode 고갈)입니다. 내가 쓰는 데이터가 일기장(작은 파일 다수)인지, 백과사전(거대 파일)인지에 따라 노트의 제본 방식(할당 방식)을 다르게 골라야 합니다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분	연속 할당 (Contiguous)	연결 할당 (Linked)	색인 할당 (Indexed)
외부 단편화	심각함 (OOM 주범)	없음 (100% 활용)	없음
파일 크기 변경	거의 불가능	무한정 확장 가능	무한정 확장 가능
직접 접근(Random)	$O(1)$ (빛의 속도)	$O(N)$ (치명적으로 느림)	$O(1)$ (매우 빠름)
메타데이터 낭비	0% (없음)	약간 (포인터 4바이트)	조금 심함 (인덱스 블록 통째로 낭비)

미래 전망

객체 스토리지(Object Storage)로의 진화: 블록 단위로 쪼개고 목차를 그리는 복잡한 파일 시스템의 시대는 지나가고 있다. AWS S3 같은 클라우드는 파일을 블록으로 쪼개지 않고 통째로(Object) 던진 뒤, 고유한 해시 ID 값(URL)으로 단방향 매핑해 버리는 플랫(Flat)한 아키텍처를 사용하여 디스크 할당 오버헤드를 아예 네트워크 레이어로 숨겨버렸다.

결론

파일 시스템의 연속, 연결, 색인 할당은 "데이터를 디스크라는 물리적 원판에 어떻게 아름답게 펼쳐 놓을 것인가?"에 대한 운영체제의 50년 고민이 담긴 발자취다. 속도를 위해 연속을 택했다가 파편화의 저주를 맞았고, 파편화를 잡으려 연결을 택했다가 끔찍한 탐색 속도에 좌절했다. 결국 인간은 '목차(Index)'라는 가장 오래된 정보 검색의 진리를 디스크에 이식(색인 할당)함으로써 두 마리 토끼를 모두 잡았다. 현대의 어떤 화려한 분산 파일 시스템도 결국 이 '색인(Index)'이라는 완벽한 타협점 위에서 뼈대를 세우고 있다.

📢 섹션 요약 비유: 무식하게 줄을 세우는 것(연속)과 무책임하게 흩어놓는 것(연결)의 양극단을 피하고, 자유롭게 흩어놓되 그 모든 위치를 꿰뚫어 보는 지휘통제실(색인)을 둔 것이 현대 파일 시스템이 혼돈(디스크) 속에서 질서를 유지하는 유일한 비결입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
External Fragmentation (외부 단편화)	연속 할당의 몰락을 가져온 주범. 디스크 공간 중간중간에 쓰지 못하는 자투리가 남아 큰 파일을 저장하지 못하게 됨
i-node (Index Node)	색인 할당(Indexed Allocation)을 유닉스/리눅스 환경에서 구체화한 데이터 구조체. 파일의 모든 메타데이터와 블록 주소를 가짐
Extent (익스텐트)	연속 할당의 속도와 색인 할당의 유연성을 결합하기 위해, 블록 수만 개를 하나의 연속된 덩어리로 묶어서 인덱싱하는 현대적 포인터 기법
Sequential Access (순차 접근)	테이프처럼 처음부터 끝까지 차례대로 읽는 방식. 연속 할당과 연결 할당이 유리함
Random Access (직접 접근)	파일의 1,000번째 바이트를 한 번에 훅 찔러서 읽는 방식. 연결 할당에선 불가능하고 오직 연속/색인 할당에서만 가능

👶 어린이를 위한 3줄 비유 설명

일기장을 쓸 때, 1페이지부터 10페이지까지 쭉 이어서(연속 할당) 쓰면 읽기 편하지만, 중간에 내용을 추가하고 싶을 땐 자리가 없어서 지우고 다시 써야 해요.
그래서 오늘 1페이지 쓰고, 내일은 50페이지에 쓰면서 "다음 일기는 50페이지에 있음!"이라고 **꼬리표(연결 할당)**를 달았어요. 자리는 안 모자라지만, 5번째 일기를 찾으려면 1페이지부터 꼬리표를 계속 따라가야 해서 너무 힘들어요.
아하! 그래서 공책 맨 앞장에 **'목차(색인 할당)'**를 만들었어요. 목차에 "1일차: 1p, 2일차: 50p, 5일차: 30p"라고 다 적어두니까, 일기를 아무 데나 써도 목차만 보면 한 번에 찾을 수 있게 되었답니다!