4-5장. 파일 시스템 구현

파일 시스템은 순수한 소프트웨어다. 이점은 앞부분에서 다룬 CPU 가상화, 메모리 가상화 부분과 다른 점이다. CPU 가장화나 메모리 가상화에서는 하드웨어가 필요하다. (특권 모드로의 변환을 위한 명령어, 페이징을 위한 하드웨어 등이 그것이다) 파일 시스템의 종류는 매우 다양하다. 모든 파일 시스템들이 서로 다른 자료 구조를 가지고 있으며 각각은 장단점이 있다. 여기서는 간단한 파일 시스템 (Very Simple File System, vsfs)을 사용하여 개념을 소개하고, 파일 시스템에 대한 사례들을 다루며 현실에서 어떻게 동작하는지 이해해 보도록 하겠다.

 

생각하는 방법

파일 시스템에 대해 학습할 때, 두 가지 측면에서 접근할 것을 권장한다. 그 두 측면을 다 이해하게 되면 파일 시스템이 기본적으로 어떻게 동작하는지 이해하게 될 것이다.

 

첫 번째는 파일 시스템의 자료구조이다. 즉, 파일 시스템이 자신의 데이터와 메타데이터를 관리하기위해 디스크 상에 어떤 종류의 자료 구조가 있어야 하겠는가? 우리가 보게 될 첫 파일 시스템은 블럭과 다른 객체들을 배열과 같은 간단한 자료구조로 표현하지만, 실제 파일 시스템들은 좀 더 복잡한 트리 기반의 자료구조를 사용한다.

 

파일 시스템의 두 번째 측면은 접근방법이다. 프로세스가 호출하는 open(), read(), write() 등의 명령들은 파일 시스템의 자료구조와 어떤 관련이 있는가? 특정 시스템 콜을 실행할 때에 어떤 자료구조들이 읽히는가? 어떤 것들이 쓰이며, 이 모든 과정이 얼마나 효율적으로 동작하는가? 

 

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

 

전체 구성

이제 vsfs 파일 시스템의 자료구조에 대해 디스크 상의 전체적인 구성을 개발해 보자. 가장 먼저 해야 할 것은 블럭(block)들로 나누는 것이다. 간단한 파일 시스템은 단일 블럭 크기만 사용하기 때문에 여기서도 그렇게 한다. 일반적으로 사용되는 크기인 4KB를 사용한다.

 

우리가 파일 시스템을 만들려는 디스크 파티션 구조는 단순하다. 4KB 블럭들로 나열되어 있다. N개의 4KB블럭의 크기를 갖는 파티션에서 블럭은 0부터 N - 1까지의 주소를 가지고 있다. 블럭이 64개 있는 작은 디스크를 가정하자.

 

파일 시스템을 생성하기 위해서 이들 블럭에 어떤 것을 저장할지 생각해 보자. 가장 먼저 떠오르는 것은 사용자 데이터이다. 사실, 파일 시스템의 대부분의 공간은 사용자 데이터로 이루어져 있고 그렇게 되어야 한다. 사용자 데이터가 있는 디스크 공간을 데이터 영역(data region)이라고 하자. 간단하게 64개의 디스크 블럭 중 마지막 56개의 블럭처럼 디스크의 일정 부분을 데이터 영역으로 확보하자.

 

파일 시스템은 각 파일에 대한 정보를 관리한다. 그 정보가 메타데이터(metadata)의 핵심이다. 파일을 구성하는 데이터 블럭(데이터 영역 내의)들과 그 파일의 크기, 소유자, 접근 권한, 접근과 변경 시간 등과 같은 정보들이 이에 해당한다. 파일 시스템은 이 정보를 보통 아이노드(inode)라고 부르는 자료 구조에 저장한다. 

 

아이노드들의 저장을 위해 디스크 공간이 필요하다. 이 영역을 아이노드 테이블(inode table)이라 한다. 아이노드 테이블에는 아이노드들이 배열 형태로 저장된다. 디스크 상의 자료 구조의 배치는 다음 그림에서 보는 것과 같다. (5개의 블럭이 아이노드를 저장하기 위해 할당된 것으로 가정하자)

 

아이노드는 일반적으로 128에서 256bytes 정도로 그렇게 크지 않다. 아이노드당 256bytes를 가정하면 4KB 블럭에는 16개의 아이노드를 저장할 수 있으며 우리 파일 시스템에서는 총 80개의 아이노드를 저장할 수 있다. 64개의 블럭으로 구성된 작은 파일 시스템 파티션에 최대 80개의 파일을 만들수 있다는 것을 의미한다. 같은 파일 시스템이라도 더 큰 디스크 파티션에 생성한다면 아이노드 테이블을 더 크게 만들 수 있기 때문에 생성 가능한 최대 파일 개수를 증가시킬 수 있다.

 

예제 파일 시스템에는 데이터 블럭(d)과 아이노드 블럭(i)이 존재한다. 아직 완전하지 않다. 꼭 필요한 정보는 아이노드나 데이터 블럭의 사용여부에 대한 것이다. 각 블럭이 현재 사용 중인지 아닌지를 표현할 할당 구조(allocation structure)가 필요하다. 블럭이 사용 중인지 아닌지를 나타내는 정보는 어느 파일 시스템이든 꼭 있어야 한다.

 

블럭이 사용 중인지 아닌지를 표현하는 데에는 다양한 방법이 존재한다. 예를 들면 프리 리스트(free list)를 사용하여, 사용 중이 아닌 블럭들을 링크드 리스트 형태로 관리할 수 있다. 아이노드는 첫 번째 프리 블럭의 위치만 기억하면 된다. 다음 프리 블럭의 위치는 각 프리 블럭에서 정해진 위치에 기록한다. 여기서는 단순한 비트맵(bitmap)을 사용한다. 데이터 영역에 있는 블럭들의 사용여부를 표현하기 위해서 데이터 비트맵(data bitmap)을, 아이노드 테이블에 있는 아이노드들이 사용 중인지를 나타내기 위해서 아이노드 비트맵(inode bitmap)을 사용한다. 비트맵은 비트들의 배열이다. 각 비트는 해당 블럭이나 객체가 사용 중인지 아닌지를 나타낸다. 아래 그림 i, d가 위 두 비트맵에 해당한다.

 

그럼 이제 남은 한 블럭의 존재는 무엇일까? 이 블럭은 슈퍼블럭(superblock)을 위한 공간이다. 슈퍼블럭은 이 파일 시스템 전체에 대한 정보를 담고 있다. 예를 들면 파일 시스템에 몇 개의 아이노드와 데이터블럭이 있는지, 아이노드 테이블은 어디서 시작하는지 같은 정보를 담고 있다. 파일 시스템을 식별할 수 있는 매직 넘버도 갖고 있을 것이다. 파일 시스템이 깨진다는 것은 곧 슈퍼블럭이 저장된 디스크 블럭이 훼손되는 것이다. 일반적으로 대부분의 파일 시스템은 슈퍼블럭을 몇 개 복사해둔다. 아래 그림에서는 S라고 표기된 위치의 블럭이 슈퍼블럭이다.

 

파일 시스템을 마운트할 때, 운영체제는 우선 슈퍼블럭을 읽어 들여서 파일 시스템의 여러 가지 요소들을 초기화하고, 그 후 각 파티션을 파일 시스템 트리에 붙이는 작업을 진행한다. 이렇게 함으로 해서 디스크 파티션에 있는 파일들을 접근할 때, 해당 파일을 읽거나 쓰는 데 필요한 자료 구조의 위치를 파악한다.

 

파일 구성 : 아이노드

파일 시스템의 디스크 자료구조 중 가장 중요한 것은 아이노드이다. 거의 모든 파일 시스템들이 비슷한 구조를 가지고 있다. 아이노드는 인덱스 노드(index node)의 줄임말로서 역사적으로는 UNIX의 창시자인 켄 톰슨이 처음 사용하였다. 이 노드들은 원래 배열로 되어 있었는데, 각 배열은 특정 아이노드를 접근하기 위해 탐색된다.

 

각 아이노드는 숫자(아이넘버(inumber)라고 불림)로 표현된다. 앞 장에서는 이것을 파일의 저수준 이름(low-level name)이라고 불렀었다. vsfs에서는 아이넘버를 사용하여 해당 아이노드가 디스크 상에 어디에 있는지를 직접적으로 계산할 수 있다. 위에서 사용한 vsfs의 아이노드 테이블을 예로 사용해 보자. vsfs 파일 시스템 파티션의 시작 부분은 아래의 그림과 같이 구성되어있다.

 

32번 아이노드를 읽기 위해서는 파일 시스템은 아이노드 영역에서의 오프셋을 계산한다. (32 * sizeof(inode) 또는 8192) 그 후 아이노드 테이블의 시작 위치를 더하면(12KB), 원하는 아이노드 블럭의 정확한 바이트 주소를 구할 수 있다.(20KB) 디스크는 바이트 단위로는 접근이 불가능하면 대신에 대체적으로 512바이트 크기를 갖는 섹터(sector)로 이루어졌다. 32번 아이노드가 존재하는 블럭을 가져오기 위해서는 파일 시스템은 섹터 주소 (20 * 1024) / 512 또는 40에 대한 읽기 요청을 하여 해당 앙이노드 블럭을 가져온다. 아이노드 블럭의 섹터 주소 iaddr은 다음과 같이 계산될 수 있다.

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

아이노드에는 파일에 대한 정보가 다 들어 있다. 파일의 종류, 크기, 할당된 블럭 수 , 보호 정보, 시간 정보와 더불어 데이터 블럭이 디스크 어디에 존재하는지와 같은 정보들이 담겨 있다. 이와 같은 파일에 대한 정보들을 메타데이터(metadata)라고 한다. 사용자 데이터가 아닌 기타 정보를 통틀어서 흔히 메타데이터라 부른다. 

 

아이노드를 설계 시 가장 중요한 결정 중 하나는 데이터 블럭의 위치를 표현하는 방법이다. 간단한 방법은 아이노드 내에 여러 개의 직접 포인터(direct pointer, 디스크 주소)를 두는 것이다. 각 포인터는 파일의 디스크 블럭 하나를 가리킨다. 그러나 이 방법에는 파일 크기의 제한이 있다. 파일 크기가 (포인터 개수) * (블럭 크기)로 제한된다.

 

멀티 레벨 인덱스

큰 파일을 지원하기 위해서 파일 시스템 개발자들은 아이노드 내에 다른 자료 구조를 추가해야 했다. 일반적으로 사용되는 방법 중 하나는 간접 포인터(indirect pointer)라는 특수한 포인터를 사용하는 것이다. 간접 포인터는 데이터 블럭을 가리키지 않는다. 간접 폰인터가 가리키는 블럭에는 데이터 블럭을 가리키는 포인터들이 저장된다. 직접 포인터와 간접 포인터를 결합해서 사용할 수 있다. 아이노드에는 정해진 수의 직접 포인터(예를 들어 12개), 그리고 하나의 간접 포인터가 있다. 큰 파일에 대해서는 간접 블럭이 할당이 되고, 아이노드의 간접 포인터는 이 간접 블럭을 가리킨다. 블럭이 4KB이고 디스크 주소가 4바이트라고 하면 1024개의 포인터들을 추가할 수 있게 된다. 최대 파일 크기는 (12개 + 1024) * 4K 또는 4144KB가 된다.

 

4144KByte는 사실 그리 큰 파일이 아니다. 더 큰 파일을 저장하고 싶을 수도 있다. 그 경우 아이노드에 이중 간접 포인터(double indirect pointer)를 추가한다. 이중 간접 포인터가 가리키는 블럭에는 간접 포인터들이 저장되어 있다. 각 간접 블럭은 데이터 블럭을 가리키는 포인터들을 가리키고 있다. 이중 간접 블럭을 사용하면 파일은 4KB * 1024 * 1024, 약 백만개의 4KByte 블럭을 가질 수 있다. 즉, 4GB가 넘는 크기의 파일을 지원할 수 있게 된다. 더 큰 파일을 표현해야 한다면, 다음에는 무엇이 나올지 감이 잡혔을 것이다. 삼중 간접 포인터(triple indirect pointer)를 사용하면 된다. (약 4TB가 넘는 크기의 파일을 지원할 수 있게 된다)

 

지금까지 했던 설명들을 종합하면, 디스크 블럭들은 일종의 트리 형태로 구성되어 하나의 파일을 이룬다. 약간 한쪽으로 치우쳐진 형태의 트리이다. 이러한 구성 방식을 멀티 레벨 인덱스 기법이라 한다. 많은 파일 시스템들이 멀티 레벨 인덱스를 사용한다. 

 

재미있는 사실은 트리의 형태가 매우 편향적이다. 파일의 시작 부분을 이루는 블럭들은 한 번의 포인터로 접근이 가능하다. 큰 파일의 경우, 파일의 끝부분에 있는 블럭들은 포인터를 세 번 따라가야 실제 블럭을 읽을 수 있다. 왜 이렇게 했을까? 이는 오랜 고민과 연구의 결과이다. 많은 연구자들이 파일 시스템 사용형태를 분석해서 발견한 아주 중요한 "사실"이 있다. 대부분의 파일 크기는 작다는 것이다. 비대칭적 트리를 채용한 이유는 이러한 특성을 반영한 것이다. 대부분의 파일들이 작다면, 작은 파일을 빨리 읽고 쓸 수 있도록 파일구조를 설계해야 한다.

 

파일은 위에서 다룬 방법 말고도 다양한 방식으로 구성할 수 있다. 아이노드는 자료구조다. 데이터와 관련 내용들을 효율적으로 읽고 쓸 수 있다면, 어떤 방식도 사용가능하다. 

 

디렉토리 구조

vsfs의 디렉토리는 간단하다. 디렉토리는 (항목의 이름, 아이노드 번호) 쌍의 배열로 구성되어 있다. 디렉터리의 데이터 블럭에는 문자열과 숫자가 쌍으로 존재하며 문자열 길이에 대한 정보도 있다. (디렉토리 또한 파일이다)

 

예를 들어 dir이라는 디렉토리(아이노드 5번) 에는 foo, bar와 foobar라는 3개의 파일이 있고 각각의 아이노드 번호는 12, 13 그리고 24라고 하자. dir의 데이터 블럭은 아래와 같은 내용을 가지고 있을 것이다.

inum    |    reclen    |    strlen    |    name
   5              4              2               .
   2              4              3               ..
  12              4              4               foo
  13              4              4               bar
  24              8              7               foobar

inum -> 아이노드 번호
reclen -> 레코드 길이
strlen -> 문자열 길이
name -> 항목의 이름

여기서 . (dot) 디렉토리는 현재 자신을 기리키며, ..(dot-dot) 디렉토리는 부모 디렉토리(루트)를 가리킨다. 

 

파일이 삭제되면(unlink()) 디렉토리 중간에 빈 공간이 발생한다. 영역이 비었다는 것을 표시할 방법이 필요하다. 항목의 길이를 명시하는 이유 중에 하나가 중간에 빈 공간이 생기기 때문이다. 새로운 디렉토리 항목을 생성할 때, 기존 항목이 삭제되어 생긴 빈 공간에 새로이 생성된 항목을 위치시킬 수도 있기 때문이다. 

 

디렉토리들은 정확히 어디에 저장될까? 대부분 파일 시스템에서 디렉터리는 특수한 종류의 파일로 간주한다. 디렉토리는 자신의 아이노드를 가지며, 이 아이노드는 아이노드 테이블에 존재한다. 디렉토리는 자신의 데이터 블럭을 가지고 있으며, 이들 블럭의 위치는 일반 파일과 마찬가지로 아이노드에 명시되어 있다. 이 데이터 블럭들을 데이터 블럭 영역에 존재한다. 

 

예제에서 디렉토리는 가변 크기 레코드로 구성된 배열이다. 이 외에도 많은 방식이 존재할 수 있다. 앞에서도 언급했듯 제대로 돌아만 간다면 어떤 자료 구조라도 상관없다. 예를 들면 XFS는 디렉터리를 B-tree 형식으로 구성한다. 파일 생성 시 현재 디렉토리에 동일한 이름의 파일이 있는지를 먼저 검사해야 한다. B-tree와 같은 검색 전용 자료구조를 사용할 경우, 검색시간이 단축된다. 파일 생성을 좀 더 빨리 할 수 있다. (단, 중복 제외)