디렉토리의 구조

2020년 6월 18일

파일시스템에서 유저가 특정 파일명에서 오프셋 위치에 있는 데이터에 접근하려고 할 때 실제 디스크에 접근하기 위해 일어나는 일은 두 단계로 나뉜다.

파일명으로부터 디스크에 저장되어있는 inode를 찾아서 읽는다.
inode와 오프셋으로부터 해당 파일에서 오프셋 위치에 있는 블럭의 디스크상의 물리 주소를 구한다.

여기서 inode(information node)는 실제 데이터의 포인터와 기타 정보들을 담고 있는 데이터로, 디스크에서 위와 같이 inode array의 형태로 관리된다.

이 글에서는 1번을 용이하게 만들어주는 디렉토리에 대해서 다루려고 한다.

디렉토리도 일종의 파일이다.

디렉토리도 파일과 크게 다르지 않다. 디렉토리도 그 디렉토리가 포함하는 하위 파일/디렉토리 정보를 디스크에 저장하고, 그 위치를 탐색하기 위해 해당 디렉토리의 inode 또한 디스크에 저장된다.

예를 들어 /home/minus21/workspace/app01/main.py라는 파일에 접근하는 상황을 생각해보자. 루트 디렉토리인 /는 inode 인덱스가 고정되어있기 때문에 inode를 찾아낼 수 있고, 이 inode를 통해 하위 디렉토리들의 이름이 inode 인덱스로 다음과 같이 매핑된다. (이 매핑을 구현하기 위해 다양한 자료구조가 사용될 수 있다)

name | inode index
-----|-------------
bin  | 737
usr  | 924
home | 14
proc | 47

그러면 home의 inode 인덱스 14로부터 inode에 접근할 수 있고, 이 inode가 가리키는 블럭에는 또 같은 형태의 매핑이 존재한다.

name   | inode index
-------|-------------
minus21| 287
user01 | 894

이런 식으로 반복하여 최종적으로 app01 디렉토리의 inode에 접근하고, 이 inode가 가리키는 블럭에 저장된 main.py라는 파일의 inode를 찾아내어 위에 적은 2번 과정을 하면 된다.

큰 디렉토리

디스크는 블럭 단위(4KB)로 정보가 관리되는데, 디렉토리의 하위 파일/디렉토리가 아주 많아서 정보가 4KB를 넘어가면 어떻게 될까? 이 범람을 해결하기 위해서는 한 디렉토리를 여러 블럭으로 관리해야 하는데, 디렉토리를 접근하는 다음 두 상황을 모두 고려해야 한다.

파일명(또는 디렉토리명)으로부터 파일에 해당하는 inode를 찾는다.
디렉토리 내부의 파일(또는 디렉토리)들을 빠르게 순서대로 탐색할 수 있다.

즉, 쉽게 말해서 무작위 접근, 순차적 접근 모두 빨라야 한다. 그래서 디렉토리를 구현할 때 B+ 트리와 같은 형태가 사용될 수 있다.

출처

[1] 2020 Spring CS330 Operating System Lecture of KAIST