[OS] File System 구현

이 글은 포스텍 박찬익 교수님의 운영체제(CSED312) 강의를 기반으로 재구성한 것입니다.

 이 글에서는 File System & Directory 포스팅에서 다룬 file system의 구현에서 고려할 점을 살핀다.

 

 

File System 구현

 file system의 구현을 알아보기 전에 몇 가지 먼저 살펴보자.

 

inode in UNIX

 file header를 담는 data structure를 inode라고 하며, UNIX에서 사용한다. 모든 file은 각각의 inode를 가지며 inode는 이름 빼고 file의 모든 정보를 담고 있다. inode는 fixed size array로 관리하는데, 이 때 index를 inode number(i-number)라고 한다.

 한편, directory는 filename과 i-number를 매핑한다. 이를 통해 directory로 file header를 찾고, file 정보를 찾을 수 있는 것이다.

 

 

Components

 file system의 구현을 위해 다음 내용들을 구현해야 한다.

• data structure
  • directory : file name으로 file metadata를 찾아야 한다.
  • file metadata : file data block을 찾아야 한다.
  • free map : disk에서 free block을 찾아야 한다.
• challenges
  • index structure : file block이 disk에 어디있는지 어떻게 찾는지
  • index granularity : block size를 어떻게 결정하는지
  • free space : disk의 free block을 어떻게 찾는지
  • locality : locality를 어떻게 만들어 줄 것인지
  • reliability : crash가 난 경우 어떻게 대응할 것인지

 

 이를 크게 4가지로 나누면 다음과 같다. 이제부터는 아래 4가지 요소를 어떻게 구현하는지 살펴 볼 것이다.

• disk management : disk space 관리
• name과 directory : indexing
• efficiency와 performance
• reliability와 protection : 문제가 발생했을 때 복구

 

 

Disk Management

 disk 관리는 크게 2가지로 나뉜다.

1. file data가 어디에 있는지 - 이 결과로 file metadata를 찾을 수 있다.
2. free space가 어디에 있는지

 전체 file system을 순회할 수 있지만 매번 이렇게 하기에는 너무 비효율적이다.

 

Free Space 관리

Bitmap

 block이 free인지 여부를 bit로 표기하는 bitmap으로 free space를 관리할 수 있다.

 

 장단점은 아래와 같다.

• contiguous space를 찾기 쉽다.
• space overhead가 작다. (block당 1bit만 차지한다.)

 

• bitmap을 위한 추가 공간이 필요하다.
• scalable하지 않다.
  • disk size가 매우 크면 memory에 올릴 수 없기 때문에 disk에 bitmap이 올라가야 한다. 그러면 scanning 과정이 disk read를 하는데 이는 너무 느리다.

 

Variation

 bitmap을 chunk로 나누어 사용하는 방법이 있다.

 simple bitmap을 사용할 때 1PB file system에서 32GB bitmap을 사용한다고 하자. 32GB는 memory에 올라가기에는 너무 크다. 기존 방식 대신 bitmap을 쪼갠 부분을 사용해, 10^6개의 bit를 한 덩어리로 묶는다면 memory에 올라간다.

 

 

Linked List

free linked list

 free spae를 linked list로 묶어서 사용하는 방식이다.

 

 contiguous space를 쉽게 찾을 수 없다. 그렇지만 extra space가 필요없다는 장점이 있다.

 

 

Allocation 관리

 free space를 allocation할 때 공간을 효과적으로 사용하고, file에 빠르게 접근할 수 있어야 한다.

 

Contiguous Allocation

cointiguous allocation

 file을 disk의 연속된 free space에 할당하는 방법이다. contiguous free space에 할당하기 때문에 linked list나 bitmap을 순회해야 한다.

 file header에는 filre의 first sector와 sector 개수만 가지고 있다. 이 정보를 이용해 disk의 해당 위치에 access하면 된다.

 

 장단점으로는 아래와 같다.

• sequential access가 빠르고, random access가 쉽다.
• external fragmentation이 발생하고, file size를 키우기가 어렵다.

 

Extent

 extent는 disk의 contiguous block을 말하며, 이를 allocation 단위로 두는 것이다. (contiguous allocation을 약간 변형시킨 방법) file은 하나 이생의 extent로 이루어진다.

 그렇지만 internal fragmentation과 external fragmentation이 발생한다.

 

Linked Allocation

linked allocation

 각 file을 disk block의 linked list로 만드는 방법이다.

 이를 위해 disk block을 [pointer + data 영역]으로 나누어야 한다.

 

 장단점은 아래와 같다.

• file size를 동적으로 늘일 수 있다.
• 공간 낭비가 없다. (external fragmentation이 없다.)

 

• disk random access이기 때문에 효율이 매우매우 낮다.
• unreliable : 중간에 끊겨버리면 나머지를 모두 잃어버리는 것과 같기에 안정성이 낮다.
• space overhead : disk block에 pointer를 저장하기 위한 추가 공간이 필요하다.

 

FAT, File Allocation Table

 linked allocation을 개선한 방법으로, disk random access의 효율을 높이기 위해 disk block에 있던 모든 pointer를 linked list의 형태로 memory에 올리는 방법이다.

 

 

 장단점은 아래와 같다.

• free block을 찾기 쉽고, file size를 추가하기 쉽다. 마찬가지로 삭제도 쉽다. 

 

• linked allocation보다는 빠르지만 여전히 disk random access를 하기 때문에 느리다.
• fragmentation : block이 흩어져 있기 때문에 locality가 매우 낮다.

 

Single Level Indexed Allocation

single level indexed allocation

 linked allocation의 random access를 해결하기 위한 방법이다. file header가 disk block을 가리키는 pointer array을 가진다. file header를 보고 disk block을 바로 찾아가기 때문에 기존 방식보단 random access가 적다.

 

 장단점은 아래와 같다.

• limit까지는 file size를 올리기 쉽다.
• random access가 빠르다.
• external fragmentation이 없다.

 

• 정해둔 limit보다 file size를 키우기 어렵다.
• 탐색이 너무 많다.

 

Multi Level Indexed Allocation

multi level indexed allocation

 single level indexed allocaiton의 limit을 해결하기 어렵다는 단점을 해결하기 위한 방법이다.

 index를 여러 단계로 두어 각 index가 disk block, 또는 index를 가리키게 한다.

 

 

Combined Scheme

UNIX comibned scheme

 UNIX는 multi level indexed allocation을 조금 변형한 combined scheme을 사용한다.

 header에 총 13개의 pointer가 있다. 10개의 direct pointer, 1개의 1-level pointer, 1개의 2-level pointer, 1개의 3-level pointer가 있다.

 

 장단점은 다음과 같다.

• 작은 file도 direct pointer를 사용해 관리할 수 있다.
• 3-level pointer까지 사용해 file size를 키울 수 있다. (16GB까지)

 

• index를 여러 번 타야 하기 때문에 탐색이 너무 많다.

 

 

Name과 Directory

구현

 File System & Directory 포스팅에 작성한 tree structured directory, acyclic graph directory 등으로 구현한다.

 

directory 탐색

 directory는 filename과 inode mapping을 저장하는, 그냥 하나의 file이다. 이 때 hierarchy를 탐색하기 위해서 필요한 것이 root directory "/"이다. system이 켜지면 inode 2에 root가 할당된다.

 이외에도 아래와 같이 명령어로 특정 directory에 접근한다.

• current directory는 "."
• parent directory는 ".."
• home directory는 "~"

 

 file access를 할 때, filename을 턱정해서 inode를 찾고, inode로 metadata를 찾는다. 그 과정은 아래와 같다.

1. root inode element에 접근
2. match element를 찾아 match directory를 계속 찾아간다.

 

예시

 왼쪽과 같은 namespace가 주어지고, 오른쪽과 같은 physical organization이 주어졌을 때 c.c를 탐색하기 위해 어떤 과정을 거치는지 보자.

• root(2) - <a, 3> - b - <b, 5> - 5 - <c.c, 14> - 14 - inode 14에 있는 metadata
  1. root는 inode 2에 있다. 여기 안에 있는 a의 위치를 찾아낸다. <a, 3>을 보고, a가 inode 3에 있는 것을 알았다.
  2. 3번을 보고 여기 안에 있는 b의 위치를 찾아낸다. <b, 5>를 보고 b가 inode 5에 있는 것을 알았다.
  3. 5번을 보고 여기 안에 있는 c.c의 위치를 찾아낸다. <c.c, 14>를 보고 c가 inode 14에 있는 것을 알았다.

 

Default Context

 매번 root부터 시작하는 경로를 입력하기는 너무 번거롭기 때문에, path가 root인 /부터 시작하지 않는 경우 자동적으로 입력한 path의 앞에 current directory path를 붙인다. (relative path)

 

 

예시 :  UNIX open-read-close cycle

1. process가 open() call을 보낸다.
2. kernel이 작동한다. (process wide descriptor table에 새로운 element 할당 후 fd number return)
   1. process의 현재 working directory를 가져온다.
   2. namei를 call한다.
      • namei는 path를 파싱해 inode를 얻어오는 함수이다.
   3. process의 file descriptor table에서 빈 칸을 찾는다. (fd라고 하겠다.)
   4. fd에 inode로의 pointer를 만들어 넣는다.
   5. fd의 초기 file pointer 값을 0으로 만든다. (file에서 참조하는 위치)
   6. fd를 리턴한다.
3. process가 read() call을 보낸다.
4. kernel이 작동한다. (fd에 해당하는 file의 block을 disk에서 읽어 buffer에 작성한다..)
   1. read() call에서 받은 fd 값으로 file pointer를 찾는다. (이미 open()했기 때문에 memory에 올라가 있는 상태)
   2. file system block size를 기반으로 block이 저장된 위치를 찾는다.
   3. inode를 읽는다.
   4. UNIX이므로 combined scheme가 적용되어 있다. block number를 기반으로 disk에서 읽을 block의 위치를 찾는다.
   5. disk에서 block을 읽는다.
   6. block을 buffer에 작성한다.
5. process가 close() call을 보낸다.
   1. process wide file descriptor table에서 fd에 해당하는 element를 삭제한다.

 

 

Efficiency와 Performance

 disk 공간의 효율은 disk allocation 방법, directory algorithm, file directory에 들어있는 file type에 영향을 받는다.

 file system은 disk에 있기 때문에 속도가 매우 느리다. 따라서 operation은 가능한 한 cache로 만드는 것이 성능 향상에 좋다. 향상을 위한 방법은 아래와 같다.

1. disk cache
2. free behind and read ahead
3. memory의 일부를 virtual disk로 사용

 

Disk Cache

disk controller cache

 disk controller에 작은 on-board cache로 사용하는 방법이다. 단, memory는 volatile이기 때문에 write할 때는 조심해서 사용해야 한다.

 위 그림에서 controller에 있는 track buffer에 cache를 추가한다.

 

 

Free Behind and Read Ahead

 free behind는 다음 page가 요총되면 원래 보던 page를 buffer에서 삭제하는 방법이다. 기존에 보던 page는 더 이상 사용되지 않을 가능성이 높고, buffer의 공간을 낭비하기 때문이다.

 read ahead는 요청된 page와 그 뒤에 있는 page를 미리 읽고 caching하는 방법이다.

 

 이 방법을 사용하면 write 이후 바로 release하고, read할 때 다음 것을 미리 읽기에 read/write 속도를 올릴 수 있다.

 

 

Memory의 일부를 Virtual Disk로 사용

 임시 파일은 매우 자주 불리고, 매우 자제 삭제된다. 따라서 이 파일들은 disk보다 memory에 저장하는 게 속도가 훨씬 빠르다. 이를 위해 memory의 일부를 virtual disk로 사용해 성능 향상을 꾀할 수 있다.

 

 

Unified Buffer Cache

unified buffer cache

 시스템에는 disk block을 caching하는 buffer cache가 있다. 한편 memory는 block보다 page를 사용하기 때문에 page cache가 있다. 이 두 cache가 각각 따로 있는 경우, 왼쪽 그림처럼 2개의 cache가 분리되어 있는 상태가 된다. 이 경우, memory mapped I/O가 page cache와 buffer cache 2개의 cache를 거쳐 필요없는 operation이 발생한다.

 이를 해결하기 위해 2개의 cache를 합친 unified buffer cache를 사용해 성능 향상을 꾀할 수 있다.

page cache는 buffer cache에 기반하기 때문에 main memory에 있다.

 

 

Reliability와 Protection

 작업을 하던 중 전원이 꺼져 crash가 나는 경우를 생각해 보자. operation은 완료 된 상태, 실행 중이어서 없어지는 상태 2가지로 나뉠 것이고, 이 때문에 disk block에 값을 쓰다가 종료되어 일부만 작성될 수 있다.

 file system은 이러한 상황을 대비하기 위해 reliability를 갖추어야 한다.

 

Multiple Updates

 어떤 operation을 완료하기 위해 multiple update가 필요한 상황이라면, update하는 도중에 crash날 수 있다.

예를 들어 file의 directory를 옮기는 경우, 기존 directory에서 file을 삭제하고 새 directory로 file을 옮겨야 한다.
새 file을 생성하는 경우, disk에 file header와 data의 공간을 할당하고, 그 값들을 disk에 쓰고, file을 directory에 추가해야 한다.

 

 disk를 쓰는 경우 효율을 위해 cache를 사용한다. cache는 write-through나 write-back 2가지 정책을 사용하지만 이 둘은 atomic이 보장되지 않기 때문에 disk에 값을 쓰던 중 crash가 나면 reliability를 보장할 수 없다.

 

 

Crash 대응 방법

 크게 2가지가 있다.

• consistency preserving approach : disk가 consistent한 상태를 유시할 수 있는 순서로 disk update를 하는 방식
• disk update를 transaction처럼 수행하기 : transaction처럼 수행하기 때문에 atomic을 보장할 수 있다.

 

 

Careful Ordering

 consistency preserving의 방법 중 하나.

 file system이 write하는 순서를 잘 맞춰 operation을 실행하며, 만약 crash가 나면 disk drive의 정보를 모으고 recover하는 방식을 취한다. 이 경우 full scan이 필요하기에 시간이 오래 걸린다.

 

Meta Data Consistency

 한 예시로, metadata와 user data의 consistency model을 다르게 쓸 수 있다. metadata는 특정한 순서로 synchronous write-through를 하고, user data는 30초마다 disk에 write back하는 형식이다.

 예를 들어 file이 생성되었지만 directory에 들어가지 않았다면 해당 file을 삭제하고, block이 할당되었지만 bitmap에 없는 경우 bitmap을 update하는 식이다. (post crash recover)

 

장단점

• file system이 모든 일을 하기 때문에 disk drive의 지원이 필요 없고, 대부분의 multi update에 대해 동작한다.

 

•  crash가 난 경우 recover하기 때문에 시간이 걸린다.
• concurrent operation을 사용할 수 없다.

 

 

Soft Update

 consistency preserving의 다른 방법 중 하나로, consistency를 항상 유지하는 방법이다. 

 앞에서 설명했듯 disk는 cache를 사용하는데, cache에 값을 쓰거나 cache에 있는 값을 disk에 쓸 때 consistency를 유지하는 순서로 수행하는 방법이다. 이를 위해 flush라는 것을 사용한다.

 

Flush

 disk에 값을 작성할 때, 실제 구현은 buffer가 있어 어떤 것이 disk에 먼저 쓰일지 모른다. 때문에 memory barrier처럼 buffer를 비우는 flush를 사용해 operation 순서를 보장할 수 있다.

 

 

Copy On Write

 file system을 update할 때 기존에 있던 값을 유지하면서 새로운 값을 쓰는 방법이다. 이 방법은 cost가 높아 보이지만, 실제로 update를 한 번에 하고 disk write가 동시에 진행될 수 있기 때문에 생각보다는 cost가 낮다.

 copy on write는 write를 할 때 copy하는 방법이라고 살펴봤었는데, 이것과 유사하다. 만약 어떤 값을 update해야 할 때, 원래 위치에 update하는 것이 아니라 새로 만든 후 pointer를 옮기는 방식이다.

 

Copy On Write Garbage Collection

 효율적인 disk write를 위해서는 contiguous block이 있어야 하기 때문에 가능한 한 많은 block이 free된 상태여야 좋다. 마찬가지로 효율적인 disk read를 위해서는 disk가 같은 block group에 있으면 좋다.

 따라서, block을 최대한 모아야 하는 것이 read/write의 성능 향상에 좋다. 그러나 copy on write는 old version과 new version을 만들기 때문에 block이 모이기 힘들고, 사용하지 않는 old version도 계속 남아있다. 이를 없애기 위해 garbage collection이 필수적이다.

 

장단점

• consistency가 항상 보장된다.
• 원래 값이 유지되기 때문에 crash가 날 경우 recover하기 쉽다. (new version을 삭제하면 된다)

 

• latency가 높을 가능성이 있다. (pointer를 바꾸기 때문에)
• 작은 변화가 많은 write를 필요로 한다.
• garbage collection이 꼭 필요하다.

 

 

Logging

 operation을 transaction처럼 사용하는 방법이다. 때문에 commit과 rollback 2개의 추가 operation이 필요하다.

 disk에 직접 값을 수정하는 것이 아니라 변화를 log로 남기는 방법이다. 만약 어떤 update가 있다면 log에 먼저 쓰고, log를 기반으로 disk에 쓰는 방식이다. 모든 update가 log로 남겨지기 때문에 crash가 나도 복구할 수 있다.

• atomic : operation이 일어나거나, 일어나지 않거나 둘 중 하나이다. 일어나다가 중단되는 일은 없다.
• serializable : transaction은 순서대로 일어난다.
• durable : 한 번 transaction이 수행되었으면 계속 수행된 상태로 유지된다.
• commit : transaction이 끝난 경우 commit한다. (durable)
• rollback : transaction이 중간에 멈춘 경우 원 상태로 돌린다. (atomic)

 

예시

 x = x+1; y = y-1; 2개의 operation이 transaction으로 수행된다고 하자. 그러면 다음과 같은 순서로 write를 수행한다.

1. x의 새 값을 log에 쓴다.
2. y의 새 값을 log에 쓴다.
   • 이 위에서 crash가 나는 경우 commit이 없으므로 log가 없다. 따라서 변화를 무시한다
3. commit한다.
   • commit 중간에는 crash가 날 수 없게 atomic operation을 사용해야 한다.
4. x를 disk에 쓴다.
5. y를 disk에 쓴다.
   • commit 이후에 crash가 나는 경우 log에 있는 값을 다시 disk에 쓴다. (redo)
6. log를 저장했던 공간을 free한다.

 

성능 향상

 logging을 사용할 경우 성능이 많이 향상된다. 

• crash 이후 recover하는 경우 file system full scan을 해야 하기 때문에 시간이 많이 걸렸는에 이 경우 log만 살펴보면 되기 때문이다.
• dependency가 없는 transaction들의 경우 concurrent하게 실행되기 때문에 시간을 더 아낄 수 있다.

 

 

Journaling File System

 logging의 아이디어를 file system에 적용한 방식으로, file system의 update record를 transaction으로 저장하는 방식이다.

 

 Journaling은 3가지 level이 있다.

• journal : metadata와 data 둘 모두 transaction으로 작성.
• ordered : metadata만 transaction으로 작성, data는 write order를 유지
• writeback : metadata만 tranasction으로 작성, write order를 보장하지 않는 방법.

 

 

Log Structure

 만약 flash storage나 RAID구조같이 write cost가 매우 큰 경우, log structure를 사용한다.

 log structure는 storage 안에 log만 작성하고, disk에 직접 수정하지 않는 방법이다. 이 경우 file system은 log로 이루어져 있다. 

 이 방법을 사용하면 recover는 가장 최근에 성공한 write부터 다시 시작하는 방식으로 만든다.

 

장단점

• write performace가 향상된다.

 

• garbage collection을 해야 한다. in place update(같은 file update)가 많은 경우 필요없는 log가 많아진다.

 

 

Storage Availability & RAID

 storage availability는 data를 쓰고 싶을 때 쓸 수 있는 것을 의미한다. (정상적으로 사용가능한 정도) 이를 보장하기 위해 RAID를 사용한다.

 

RAID

 availability를 위해 data의 사본을 두는 것이다. 여기서는 RAID 0과 RAID 1만 다룰 것이다.

 RAID 0은 사본을 만들지 않는 방법, RAID 1은 2개 이상의 disk에 data mirroring을 하는 방법이다.

 

 

 

 

 

 

 

잘못된 내용이나 오탈자에 대한 지적, 질문 등은 언제나 환영합니다.