27. File Structures

 

average accress time을 최소화하는 것에 이어 file structure를 정해보겠습니다. OS에 존재하는 대부분의 파일은 굉장히 크기가 작습니다. 큰 파일의 수는 적지만 디스크 스페이스의 대부분의 용량을 차지합니다. 우리가 실행하는 I/O operation은 주로 이러한 large data file에 대해서 일어납니다.

 

이를 통해서 파일 시스템을 설계할 때 large file에 대한 좋은 퍼포먼스가 필요하다는 것을 알 수 있습니다. 이러한 large file의 대부분은 멀티미디어 콘텐츠 파일로 이 파일에 액세스가 느려지면 유저 perception이 나빠지게 됩니다. 

 

large file을 위한 file structure를 설계하는 방법은 옵션이 그렇게 많지는 않습니다. linked files와 indexed files 이렇게 두 가지 옵션으로 나뉩니다.

 

 

 

파일이 파일 시스템에 생성되려면 데이터 콘텐츠를 저장하기 위한 공간을 할당받아야 합니다. 파일 시스템에서 디스크 스페이스는 블록 단위로 할당합니다. 스토리지 디바이스의 섹터와 블록이 서로 관련이 있습니다. 어떤 파일 시스템은 섹터 하나가 하나의 블록이 되거나 또는 섹터의 2의 n 승이 하나의 블록이 될 수 있습니다.

 

이런 형태의 allocation을 한다는 것은 디스크의 블록 단위로 파일에게 공간을 할당하는 걸 의미합니다. 그래서 파일이 생성되어 데이터 콘텐츠가 생기게 되면 다수의 블록을 할당받게 됩니다. 이 블록을 어떻게 관리하느냐에 따라서 file struecture가 결정되게 됩니다.

 

linked files은 파일들에 할당된 블록들을 linked list로 구성해서 관리하는 방법입니다. 위 사진은 linked files을 보여줍니다. 파일 A가 존재할 때 A는 두 개의 디스크 블록을 가지고 있습니다. A의 inode에 첫 번째 블록에 대한 포인터를 두고  첫 번째 블록의 제일 끝 부분에 다음 블록에 대한 포인터를 두면 됩니다.

 

C라는 파일의 세 번째 블록을 random access를 통해서 읽어본다면 C 파일의 inode를 읽어야 하니 1번의 disk operation을 진행해야 합니다. 읽어온 정보에서 첫 번째 디스크 블록에 대한 정보를 얻을 수 있습니다. 첫 번째 블록 마지막 데이터는 다음 블록의 주소이니 이걸 통해서 두 번째 블록, 같은 방법으로 세 번째 블록을 읽어오게 됩니다. 

 

이 데이터 구조의 경우 3번 블록을 읽어오는데 여러 번의 disk operation이 필요하다는 것을 알 수 있습니다. 

 

 

 

linked files은 굉장히 flexible한 시스템입니다. 어떤 파일의 콘텐츠가 증가한다면 블록을 뒤에 할당해 주고 링크만 연결해 주면 됩니다. 그리고 블록 단위로 allocation을 진행하기 때문에 스토리지 디바이스 상에서 fregmentation이 발생하지 않습니다.(fregmentation이 발생하려면 allocation unit의 사이즈가 제각각이어야 하지만 여기서는 블록 단위)

 

또한 sequential access에 대해서 좋은 성능을 보여줍니다. 순차적으로 읽어나가는 중 다음 블록에 대한 포인터를 얻을 수 있는 장점이 존재해서 입니다. 하지만 random access의 경우 n번째 블록을 액세스 하려면 (n+1) 번에 disk block access를 진행해야 합니다.

 

 

 

linked files의 단점으로 인해 현재에는 indexed files 구조가 사용됩니다. 마찬가지로 C에 3개의 블록이 존재할 때 이 3개의 블록에 대한 포인터를 C파일의 inode에 두게됩니다. 이 구조로 inode를 통해 각각의 블록들에 바로 access 할 수 있게 됩니다. (table과 비슷한 개념)

 

 

 

이렇게 indexed files을 사용할 경우 linked files의 단점을 보완할 수 있습니다. random access와 sequential access 모두 다 괜찮은 성능을 보여줍니다. (어떤 접근이든지 inode를 읽고 block을 읽는 2번의 과정이면 접근 가능)

 

마찬가지로 블록 단위이기 때문에 fregmentation이 없지만 block based allocation이기 때문에 seek 상의 문제가 생기게 됩니다. 디스크에서 데이터를 읽어오려면 arm을 특정 트랙에 특정 실린더로 이동시켜야 하는데 이 동작을 담당하는 opearation이 seek입니다. (굉장히 시간이 많이 소요되는 오퍼레이션)

 

그래서 인접한 블록들을 할당할 때 같은 실린더에 있는 블록들에 할당하면 seek을 0으로 만들 수 있지만 indexed allocation에서는 실린더 정보를 활용할 수 없으니 seek optimization을 할 수 없게 됩니다. 이 때문에 디스크 스토리지에 개별적으로 할당되어 굉장히 많은 seek가 발생할 수 있습니다.

 

또한 indexed files은 inode 안에 디스크 블록에 대한 인덱스를 몇 개까지 가지고 있느냐에 따라 파일의 크기가 결정된다는 단점이 존재합니다. inode안에 블록 인덱스가 10개라면 최대 10개 데이터 블록 밖에 할당 못 받는다는 단점이 존재합니다. 

 

 

 

BSD unix에서 fast file system은 indexed file structure가 가지는 크기 제한을 해결하기 위한 기법을 제시합니다. BSD unix 파일 시스템에서 파일의 inode는 14개의 인덱스를 가집니다. (14개의 블록 포인터만 보관 가능)

 

 

 

4.3 BSD 파일 시스템의 어떤 파일의 inode 모습으로 0~13까지 14개의 블록 인덱스를 가지고 있습니다. 그중 0~11까지의 블록 인덱스는 그 파일의 데이터 콘텐츠 블록을 바로 가르키고 있어 12개의 디스크 블록까지 저장이 가능합니다. 한 블록의 사이즈는 4kb이며 기본 스토리지의 섹터 사이즈는 0.5k입니다.

 

    - (어떤 파일이 48kb 이내면 다이렉트 인덱스를 가지고 액세스가 가능)

 

48kb 이상이라면 인덱스 12번을 이용하면 됩니다. 12번 인덱스도 블록에 대한 포인터로 데이터 블록에 대한 포인터를 가지고 있습니다. indirect block에 대한 포인터를 가지고 있어 그것이 가리키는 많은 데이터가 존재하게 됩니다. 이런 형식으로 데이터 블록의 사이즈를 증가시킬 수 있습니다.

 

이보다 더 큰 데이터 블록이 들어오면 14번째 인덱스에 double indirect addressing을 하게 됩니다. 이와 같이 multiple index tree 형태를 만들어 파일 콘텐츠의 사이즈를 증가시킬 수 있습니다.

 

 

 

4.3 BSD의 장점은 굉장히 단순하여 구현이 용이합니다. direct / indirect index를 사용하는 것 외에는 기본적인 index file structure와 다를 게 없습니다. 그리고 파일 콘텐츠 사이즈 확장이 가능하며 small file에 대한 액세스도 편합니다.

 

단점으로는 block by block allocation을 진행하기에 seek optimization 관점에서는 아쉬운 점들이 많습니다. 추가적으로 큰 파일이 저장된 뒤쪽 블록에 액세스 할 때는 double direct, indirect로 인해서 추가적인 disk operation이 발생한다는 단점이 있습니다. 

 

 

 

disk block management에 대해서 알아보겠습니다. disk block management를 설계할 때는 마찬가지로 성능 저하를 최소화하며 성능 향상을 극대화한다라는 목표가 존재합니다.

 

그러기 위해서는 먼저 disk block들을 조작하는 데이터 구조의 manipulation overhead를 축소시켜야 합니다. 그리고 allocation을 진행할 때 seek가 발생하지 않도록 seek optimizaiton을 진행해야 합니다.

 

 

 

disk block management의 대상이 되는 disk block들은 위 사진과 같이 플레이트와 트랙, 섹터로 구성되어 있는 3차원적인 자료구조입니다. 이 섹터들은 3차원적으로 흩어져 있지만 0, 1, 2, 3 이렇게 번호를 매기면 linearize 시킬 수 있습니다. 이 섹터 하나를 디스크 블록에 일대일 매핑을 시키면 디스크 블록 0번부터 N번까지 linear array로 만들 수 있습니다.

 

 

 

이 디스크에 있는 블록들은 4가지 용도로 쓰입니다. 파일 콘텐츠를 저장하는 디스크 블록의 경우 data block이라고 부릅니다. 파일의 메타 데이터 inode를 저장하는 디스크 블록의 경우 inode block 이라하며 파일 시스템 전체에 대한 어떤 정보 파일 시스템 메타 데이터를 저장하기 위한 블록의 경우 super block이라고 부릅니다. 마지막 4번째는 bootloader code를 숨겨두는 스토리지 볼륨으로 주로 0번 블록을 감추는 목적으로 사용합니다.

 

이제 파일 콘텐츠를 담고있는 블록들을 할당하는지 알아보겠습니다. 설계자의 입장으로 본다면 디자인 옵션들은 3가지 정도 나옵니다.  (continguous allocation, block based allocation, extent based allocation)

 

 

 

Continguous allocation

 

 

continguous allocation은 가장 원시적인 방법으로 현재는 사용되지 않습니다. 단순하게 파일의 모든 컨텐츠를 연속적인 블록 시퀀스에 저장하는 방법입니다. 이 경우 fregmentation 문제가 발생합니다.

 

 

 

Block based allocation

 

 

block based allocation은 섹터로부터 추출된 디스크 블록이라는 유닛으로 파일의 스토리지를 할당해 줍니다. 일정한 크기의 유닛으로 할당하여 fregmentation 문제를 해결했습니다. 파일 콘텐츠를 블록 단위로 할당하고 블록 단위로 반환을 합니다. linkead file structure와 indexed file structure의 모습입니다.

 

 

 

하지만 치명적인 단점이 있는데 block을 할당할 때 해당 블록인 동일한 실린더에 있는가를 확인할 수 없습니다. seek opearation 최적화가 불가능합니다. (1970년대까지 사용되던 기법), inode가 index를 관리하고 있기 때문에 direct access가 쉽게 가능하다는 장점이 있습니다.

 

 

 

Extent based allocation

 

 

extent는 어떤 블록들의 그룹으로 extent의 사이즈가 블록의 개수입니다. 20블록을 할당할 때 이 기법은 연속적인 20개의 블록을 한 번에 할당받게 됩니다. 이러면 20개의 블록에 대해서는 sequential access 할 때 seek를 굉장히 최적화할 수 있습니다.

 

여전히 storage allocation의 단위가 임의의 개수의 블록이라 fregmentation 문제를 잘 고민하여 구현해야 합니다.

 

 

 

다음과 같이 인덱스 노드가 3개 있을 때 세 개의 extent를 할당받았다고 해보겠습니다. 그러면 inode의 0번 인덱스는 extent의 모든 블록을 포인팅 하는 것이 아니라 첫 번째 블록만 포인팅 하고 그 extent의 사이즈만 기록합니다. inode 0번의 경우 길이는 7이고 extent 0의 시작 부분을 포인팅하는 걸 위 사진에서 보실 수 있습니다. (inode는 table과 비슷한 역할을 합니다.)