[OSTEP][영속성] CH40 파일 시스템 구현

CH40 파일 시스템 구현 

UNIX 파일 시스템을 단순화한 vsfs (Very Simple File System) 을 학습한다 

파일 시스템은 CPU 가상화나 메모리 가상화와 달리 성능 개선을 위해 하드웨어를 추가하지 않는다 
물론, 잘 동작하는 파일 시스템을 만들려면 장치 특성을 반영해야 한다 

핵심 질문 - 어떻게 간단한 파일 시스템을 만들 것인가
간단한 파일 시스템을 어떻게 만들 수 있을까? 디스크 위에는 어떤 자료 구조가 필요할까?
그러한 자료 구조는 어떤 정보를 추적해야 하는가? 그 자료 구조들은 어떻게 접근되어야 하는가? 

40.1 생각하는 방법

파일 시스템에 대해 학습할 때는 두 가지 측면에서 접근하면 좋다 

1) 파일 시스템의 자료 구조 

파일 시스템이 자신의 데이터와 메타데이터를 관리하기 위해 어떤 종류의 자료 구조를 사용해야 하는지 

ex. 배열과 같은 간단한 자료 구조 또는 좀 더 복잡한 트리 기반의 자료 구조 사용 

2) 접근 방법 Access Method 

프로세스가 호출하는 명령 (open(), read(), write()) 들은 파일 시스템의 자료 구조와 어떤 관련이 있는지 

특정 시스템 콜을 실행할 때 어떤 자료 구조들이 읽히는지, 어떤 것들이 쓰이는지,

이 모든 과정이 얼마나 효율적으로 동작하는지 

 

파일 시스템의 자료 구조와 접근 방법을 이해했다면, 실제 동작 방식에 대한 개념 모델을 제대로 정립하는 것이고

그것이 시스템적 사고 방식의 핵심이다 

40.2 전체 구성 

vsfs 파일 시스템의 자료 구조에 대해 디스크 상의 전체적인 구성을 개발하기 위해 가장 먼저 할 일은

디스크를 블럭 Block 으로 나누는 것이다 (+ 간단한 파일 시스템은 단일 블럭 크기만 사용한다)

 

파일 시스템 대부분의 공간은 사용자 데이터로 이루어져 있고 또한 그래야만 한다 

사용자 데이터가 있는 디스크 공간을 데이터 영역 Data Region 이라고 한다 

 

파일 시스템은 각 파일에 대한 정보를 관리하고, 그 정보가 메타데이터 Metadata 의 핵심이다 

(파일을 구성하는 데이터 블럭들과 그 파일의 크기, 소유자, 접근 권한, 접근과 변경 시간 등)

파일 시스템은 이 정보를 보통 아이노드 inode 라는 자료 구조에 저장한다 

이 아이노드들을 저장할 디스크 공간을 아이노드 테이블 inode table 이라고 하고

아이노드 테이블에는 아이노드들이 배열 형태로 저장된다 

 

아이노드나 데이터 블럭의 사용 여부를 표현할 할당 구조 Allocation Structure 도 꼭 필요하다 

블럭이 사용 중인지 아닌지를 표현하는 데는 다양한 방법이 존재하고,

예를 들어 프리 리스트 Free List 를 사용하여 사용 중이 아닌 블럭들을 링크드 리스트 형태로 관리할 수 있다 

아이노드는 첫번째 프리 블럭의 위치만 기억하면 되고, 다음 프리 블럭의 위치는 각 프리 블럭에서 정해진 위치에 기록한다 

 

데이터 영역에 있는 블럭들의 사용 여부를 데이터 비트맵 Data Bitmap 으로,

아이노드 테이블에 있는 아이노드들이 사용 중인지 여부를 아이노드 비트맵 inode Bitmap 로 나타낼 수 있다 

비트맵은 비트들의 배열이고, 각 비트는 해당 블럭이나 객체 (여기서는 아이노드) 가 사용 중인지 아닌지를 나타낸다 

 

마지막 한 블럭은 슈퍼블럭 Superblock 의 공간이고, 슈퍼블럭은 파일 시스템 전체에 대한 정보를 담고 있다 

그렇기 때문에 파일 시스템이 깨진다는 것은 슈퍼블럭이 저장된 디스크 블럭이 훼손되는 것이다

일반적으로 대부분의 파일 시스템은 슈퍼블럭을 몇 개 복사해둔다 

 

파일 시스템을 마운트할 때, 운영체제는 우선 슈퍼블럭을 읽어 들여서 파일 시스템의 여러가지 요소들을 초기화하고,

그 후에 각 파티션을 파일 시스템 트리에 붙이는 작업을 진행하면서 자료 구조의 위치를 파악한다 

 

40.3 파일 구성 - 아이노드

파일 시스템의 디스크 자료 구조 중 가장 중요한 아이노드 inode 는 인덱스 노드 index node 의 약어이다 

이 노드들은 원래 배열로 되어 있었는데, 각 배열은 특정 아이노드를 접근하기 위해 탐색된다 

 

각 아이노드는 아이-넘버 i-number 라고 불리는 숫자로 표현된다 

vsfs 는 아이-넘버를 사용하여 해당 아이노드가 디스크 상에 어디에 있는지 직접적으로 계산할 수 있다 

🐣 계산을 어떻게 하는지는 공부하지 않았다, 나중에 필요할 때 보면 되니까 🐣 

아이노드 블럭의 섹터 주소 sector 는 다음과 같이 계산할 수 있다고 한다

blk = (inumber * sizeof(inode_t)) / blockSize;
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;

 

사용자 데이터가 아닌 기타 정보를 통틀어서 흔히 메타데이터라고 부르고, 이 정보는 아이노드에 담겨 있다

아이노드를 설계할 때 데이터 블럭의 위치를 표현하는 방법이 중요하다

간단한 방법은 아이노드 내에 디스크 블럭을 가리키는 여러 개의 직접 포인터 Driect Pointer (디스크 주소) 를 두는 것이다 

멀티 레벨 인덱스 

큰 파일을 지원하기 위해서 아이노드 내에 간접 포인터 Indirect Pointer 를 추가한다 

간접 포인터가 가리키는 블럭에는 데이터 블럭을 가리키는 포인터들이 저장된다 

더 큰 파일을 위해서 이중 간접 포인터 Double Indirect Pointer,

삼중 간접 포인터 Triple Indirect Pointer 도 사용할 수 있다 

 

그리고 간단한 포인터를 사용하는 대신 익스텐트를 사용할 수도 있다 

익스텐트 Extent 는 단순히 디스크 포인터와 길이 (블럭 단위) 로 이루어진다 

포인터 기반의 접근법은 자유도는 높지만 많은 양의 메타데이터를 사용하는 반면에

익스텐트 기반의 접근법은 자유도는 낮지만 좀 더 집약되어 있어서 

디스크에 여유 공간이 충분히 있고 파일들을 연속적으로 배치할 수 있을 때 잘 동작한다 

 

대부분 파일의 크기는 작기 때문에 비대칭적 트리 형태가 유용하다

아이노드는 자료 구조이고, 파일 시스템 소프트웨어는 손쉽게 변경이 가능하므로

워크로드 특성의 변화에 따라 새로운 파일 구성 방식을 연구 개발해야 한다

40.4 디렉터리 구조

디렉터리는 (항목의 이름, 아이노드 번호) 쌍의 배열로 구성되어 있고, 

디렉터리의 데이터 블럭에는 문자열과 숫자가 쌍으로 존재하며 문자열 길이에 대한 정보도 있다 

항목의 길이를 명시하는 이유 중에 하나는, 파일이 삭제되면 (ex. unlink() 호출) 디렉터리 중간에 빈 공간이 발생하기 때문이다 

 

디렉터리는 자신의 아이노드를 가지며, 아이노드는 아이노드 테이블에 존재한다 
아이노드의 type 필드에 "일반 파일" 대신에 "디렉터리"라고 명시되어 있다 

디렉터리는 자신의 데이터 블럭을 가지고 있으며, 이들 블럭의 위치는 아이노드에 명시되어 있다

 

디렉터리가 B-Tree 형식으로 구성되어 있다면 파일 생성 시 현재 디렉터리에 동일한 이름의 파일이 있는지를 먼저 검사해야 하고 

디렉터리가 선형 배열로 구성되어 있는 경우에는 항목들을 모두 검색해야 한다 

여담 - 링크 기반의 파일 구조 
아이노드를 설계할 때 연결 리스트를 사용할 수도 있다, 링크 기반의 파일 블럭 구성 성능을 개선하기 위해서 
링크드 리스트의 포인터 정보들만 테이블로 관리할 수 있고, 그러면 각 블럭을 따로 읽는 연산을 하지 않아도 된다 
메모리 내의 테이블을 스캔하여 원하는 블럭을 찾고, 디스크 내의 해당 위치에 접근하면 되기 때문이다 
이러한 방식은 File Allocation Table, FAT 파일 시스템의 기본 구조이다 
이 방식은 아이노드가 없고, 파일의 메타데이터는 디렉터리 항목에 저장되기 때문에 하드 링크를 만들 수 없지만 
가장 광범위하게 사용되었던 파일 시스템이다 
여담2 - 빈 공간의 관리
빈 공간을 관리하는 방법 중에 하나는 비트맵이다, 프리 리스트 Free List 를 사용하여 슈퍼블럭 안의 한 포인터가 첫 번째 프리 블럭을 가리키도록 하면, 그 블럭은 다른 프리 블럭을 가리키는 포인터를 갖는 식으로 리스트를 만들 수 있다 
현재의 방식은 B-Tree 의 일종을 사용하여 디스크의 어느 공간이 비어 있는지를 작은 크기로 표현할 수 있다 

40.5 빈 공간의 관리 

파일 시스템은 새로운 파일이나 디렉터리를 할당할 공간을 찾기 위해, 아이노드와 데이터 블럭 사용 여부를 관리해야 한다 

vsfs 에서 빈 공간 관리 Free Space Management 를 하기 위해서는 두 개의 비트맵을 사용한다 

파일을 생성할 때 파일 시스템은 아이노드 비트맵을 탐색하여 비어 있는 아이노드를 찾아 해당 아이노드에 파일을 할당하고 

해당 아이노드 비트멥을 사용 중으로 표기한다 (1로 표기), 디스크 비트맵도 적절하게 갱신한다 

 

그리고 데이터 블럭을 할당할 때 가능하면 여러 개의 블럭들이 연속적으로 비어 있는 공간을 찾아서 할당한다 

연속적으로 여러 개의 블럭들이 비어있는 공간을 할당해주면 해당 파일에 대한 입출력 성능을 개선할 수 있다 

이러한 선할당 Pre-allocation 정책은 데이터 블럭 할당 시 자주 사용된다 

40.6 실행 흐름 - 읽기와 쓰기 

디스크에서 파일 읽기 

1) open() 호출 

파일 시스템은 해당 파일에 대한 아이노드를 찾아서 파일에 대한 기본적인 정보를 획득하고 

경로명을 따라가서 (traverse) 원하는 아이노드를 찾는다 

경로명을 따라가는 것은 항상 루트 디렉터리 Root Directory 부터 시작한다 

아이노드를 찾기 위해서는 i-number 를 알아야 하는데, UNIX 파일 시스템에서 루트 디렉터리의 아이노드 번호는 2번이다 

 

파일 시스템은 읽어들인 아이노드에서 데이터 블럭의 포인터를 추출하여 디렉터리 정보를 읽고 파일 항목을 찾는다 

그 다음은 경로명을 따라가서 원하는 아이노드를 찾고, 해당 파일에 대한 접근 권한을 확인해서

open-file-table 에서 파일 디스크립터를 할당받아 사용자에게 리턴한다

 

2) read() 호출

read() 시스템 콜을 통해 파일을 읽고, 파일을 마지막으로 읽은 시간을 아이노드에 기록한다 

파일 오프셋으로 파일을 읽거나 쓸 때, 해당 작업을 수행할 위치를 저장하는데 

read() 는 open-file-table 에서 해당 파일 디스크립터에 대한 오프셋을 갱신한다 

 

3) 파일 닫기 

할당된 파일 디스크립터를 해제하는 것이 파일을 닫는 것이다 (디스크 I/O 는 발생하지 않는다)

I/O 발생 횟수는 경로의 길이와 비례하고, 경로가 추가될 때마다 아이노드와 해당하는 데이터를 읽어야 한다

디스크에 파일 쓰기

먼저 파일을 열고, write() 를 호출하여 새로운 내용으로 파일을 갱신하고, 파일을 찾는다 

기존 블럭의 내용이 갱신되는 것이 아니라면, 블럭 할당을 필요로 할 수 있다

새로운 파일을 쓸 때는 파일에 어느 블럭을 할당할지를 결정해야 하고 그에 따라 디스크에 다른 자료 구조들을 갱신해야 한다 

 

파일에 대한 쓰기 요청은 논리적으로 다섯 번의 I/O 를 생성한다

1) 데이터 비트맵 읽기 

2) 비트맵 쓰기 - 디스크에 새로운 상태 반영 

3) 아이노드 읽기 

4) 아이노드 쓰기 - 새로운 블럭의 위치 반영 

5) 실제 블럭 기록하기 

 

파일 생성 시, 파일 시스템은 아이노드를 할당하고, 새로운 파일을 위한 디렉터리 항목을 할당해야 한다 

핵심 질문 - 파일 시스템의 I/O 비용을 어떻게 줄일까 
파일 열기, 읽기 또는 쓰기와 같은 단순한 동작이 디스크 위 여기저기에 엄청나게 많은 I/O를 발생시킨다 
파일 시스템은 이렇게 많은 I/O 에 대한 엄청난 비용을 줄이기 위해서 무엇을 할 수 있을까?

40.7 캐싱과 버퍼링 

파일 시스템들은 성능 개선을 위해 자주 사용되는 블럭들을 메모리 DRAM 에 캐싱한다 

정적 기법은 낭비가 많지만, 동적 파티션 방식으로 일원화된 페이지 캐시 Unified Page Cache 를 사용할 수 있다 

캐싱을 하게 되면 첫 번째 열기에서 디렉터리 아이노드와 데이터로 인해서 많은 읽기 I/O 가 발생되긴 하지만 

그 뒤를 따르는 같은 파일에 대한 파일 열기의 경우 캐시에서 히트가 되기 때문에 추가 I/O 가 필요 없다 

+ 동적 할당은 가상메모리의 페이지 정책을 사용할 수 있다 

+ 디스크에 쓰기 작업을 진행할 때 버퍼링

여기는 못 읽었음 

40.8 요약

디렉터리는 특수 파일로서 파일 이름과 아이노드 번호 간의 연결 정보를 저장한다 

팁 - 영속성과 성능 간의 절충
저장 장치 시스템에서 데이터의 영속성과 시스템 성능은 동전의 양면이다 

파일 시스템 설계가 정말 재미있는 이유는 자유롭다는 것이다 

새로운 파일이 생성되었을 때 디스크 어디에 파일을 배치해야 할지는 다음 장들에서 다룰 예정이다