[Operating System] FFS (Fast File System)

1. 어떻게 복잡한 파일 시스템의 성능을 올릴 것인가?
2. 시간이 지남에 따라 파일 시스템의 성능이 저하되는 이유는 무엇인가?
3. 어떻게 적절한 블록 크기를 고를 수 있을까?
4. Internal fragmentation을 피하는 방법은?
5. 디스크 상에서 서로 관련 있는 블록끼리 가까이 위치시키는 방법은?

 

파일 시스템의 종류

1. Local

• FFS (Fast File System)
• LFS (Log-Structured File System)

2. Network

• NFS (Network File System)
• AFS (Andrew File System)

 

---

기존 파일 시스템의 문제

여기에서 말하는 기존 파일 시스템은 이전 포스팅에서 설명한 가장 기본적인 파일 시스템 구조를 말한다.

 

1. 시간이 흐름에 따라 fragmentation이 심화

아래의 그림과 같이 시간이 지날수록 파일시스템을 구성하는 linked list가 복잡하게 얽혀가고 점점 fragmentation이 누적되어 할당 가능한 block을 찾는게 어려워진다.

 

 

2. 블록 크기

블록 하나의 크기가 작을 수록 전체 positioning time(seek + rotation)이 증가한다. 블록 크기가 커지면 internal fragmentation은 심해지겠지만 접근 시간은 크게 단축시킬 수 있다.

 

3. 블록 레이아웃

파일에 접근을 하면 inode와 data block이 모두 접근이 되는데, 서로 관련 있는 inode와 data block이 멀리 떨어져 있으면 매우 비효율적이다. 마찬가지로 같은 디렉토리에 있는 파일들은 접근시에 같은 상위 폴더의 inode에 접근을 하는데, 이들이 서로 떨어져있어도 비효율적이다.

 

 

위와 같은 문제를 해결하기 위해서는 meta-data와 data를 어디에 위치시킬 것인지, 커다란 블록 사이즈를 사용하면서도 internal fragmentation을 줄이려면 어떻게 해야할지 고민해야한다.

 

1. Bitmaps

문제 해결을 위한 첫 번째 방법은 freelist 대신 bitmap을 사용하는 것이다.

 

- 더 넓은 global view를 가짐

- 연속적인 free block을 더 빠르게 찾을 수 있음.

 

 

2. Cylinder Group

위의 그림에서 보듯이 같은 실린더에 있는 섹터들은 서로 다른 플레이트의 같은 트랙에 존재하기 때문에 헤드가 움직일 때 같이 처리될 수 있다. 따라서 서로 관련 있는 파일들, 예를 들어 특정 디렉토리와 그 안에 들어 있는 파일을 같은 실린더 그룹에 둔다면 seek time을 크게 감소시킬 수 있다.

 

각 실린더 그룹은 이와 같은 자료구조를 가진다.

 

각 실린더 그룹마다 위와 같은 자료구조를 따로 가지고 있는 이유는?

inode block과 data block 간의 위치가 멀어질 수록 포지셔닝에 걸리는 시간이 길어져서 성능이 떨어진다. 따라서 inode와 관련된 data는 같은 실린더 블록에 위치시키는 것이 좋다. 만약 위와 같은 자료구조를 디스크 전체에 대해서 적용을 한다면 inode 블록들과 data 블록들 간의 거리가 멀어질 수밖에 없다. 따라서 서로 관련된 데이터들끼리 모인 실린더 그룹마다 위와 같은 자료구조를 가지면 inode와 관련된 data block이 물리적으로 가깝게 위치할 수 있다.

실제 EXT2~EXT4 파일 시스템에서는 실린더 그룹은 아니지만 block들의 단위로 이루어진 작은 그룹을 사용하며 각 그룹은 위와 비슷한 독립적인 자료구조를 갖는다.

 

어디에 할당할 것인가?

1. 디렉토리 할당

여러 실린더 그룹 중에서 할당된 디렉토리 수는 적고, free한 inode는 많은 실린더 그룹에 파일을 할당한다.

 

2. 파일 할당

같은 디렉토리를 공유하는 파일들끼리 같은 실린더 그룹에 할당하는 것이 좋다.

 

 

3. 큰 블록 사이즈와 작은 블록을 함께 사용

블록 사이즈를 충분히 크게 만들어서 double indirect access보다 깊은 level의 access가 발생하지 않도록 하는 것이 좋다. 블록 크기를 크게 잡을수록 bandwidth가 커져서 이쪽저쪽 포지셔닝을 해가며 다른 블록을 읽을 필요가 없어진다.

 

하지만 무작정 블록 크기를 키울 수 없는 이유는 실제 시스템에서 4KB보다 작은 파일들이 매우 많기 때문이다. 따라서 무작정 블록 크기를 늘렸다간 internal fragmentation이 매우 심해질 수 있다.

 

 

해결 방안

 

커다란 블록 하나를 여러 개의 작은 블록 segment들로 나누고 segment 단위로 할당을 하되 특정 파일 하나가 블록 하나를 꽉 채우면 새로운 블록 하나를 통째로 할당 해준다.

 

 

4. Group Descriptor (Summary Block)

각 그룹이 가지고 있는 자료구조

 

효율적으로 inode와 data를 할당하기 위해서는 각 그룹에 할당되어 있는 디렉토리는 몇개인지, free한 inode는 몇 개인지와 같은 정보가 필요하다. 이러한 정보는 summary block을 통해서 관리한다.

 

 

---

HDD가 SSD로 대체되어 감에 따라서 새로운 파일 시스템이 사용되어야 하며,  실제로 이 글에서 살펴본 것과는 다른 파일 시스템이 사용되고 있다.