[OS] Fast File System의 File System 성능향상 아이디어 - OS 공부 29

안녕하세요 Pingu입니다! 🐧

 

저번 글에서는 VSFS(Very Simple File System)으로 알려진 파일 시스템을 구현하는 방법을 알아봤습니다. 그로 인해 아무런 정책 없이 파일 시스템을 구현하면 디스크 I/O가 너무 많이 발생하여 성능을 저하시킨다는 것을 알게 되었습니다. 이번 글에서는 이러한 성능 저하를 줄이는 정책들을 적용한 Fast File System에 대해 알아보려고 합니다. 이름에서부터 Fast라고 하니 얼마나 빠른지 기대가 됩니다.😆 제가 공부할 때 참고하고 있는 책인 OSTEP에서는 Chapter 41 - Fast File System 부분 입니다!

Locality and The Fast File System

UNIX 운영 체제가 처음 도입되었을 때 첫 번째 파일 시스템은 아래와 같은 데이터 구조를 가지고 있었습니다.

위와 같은 구조는 이전 글들에서 알아본 대로 S는 슈퍼 블록으로 파일 시스템에 대한 정보가 포함되어 있고 Inode 부분에는 모든 inode 정보가 들어있었습니다. 마지막으로 Data 블록이 존재하는 것을 볼 수 있습니다. 정말 단순한 구조인데요, 당시에는 정말 많은 발전이 있던 구조였다고 합니다. 위와 같은 데이터 구조로 파일, 디렉터리 계층 구조를 지원했기 때문이죠.

The Problem: Poor Performance

그럼 아까 본 정말 단순한 디스크 구조의 단점이 무엇이었을까요? 바로 성능이 매우 나쁘다는 점이었습니다. 위와 같은 구조를 갖는 디스크는 디스크 대역폭의 2%만을 제공할 정도로 성능이 나쁘다고 합니다. inode와 데이터 블록이 많이 떨어져 있을 수 있기 때문에 Seek time이 많이 발생할 수 있었습니다.

 

또한 여유 공간에 대하여 관리 방법을 따로 정하지 않았기 때문에 파일 시스템이 조각화 될 수 있었고 이는 결국 파일들을 접근할 때 비 효율적으로 접근하게 되는 원인이 되었습니다. 예를 들어 디스크 블록 2개를 사용하는 파일 4개가 있는 상황을 생각해보겠습니다.

여기서 만약 B, D 파일이 제거된다면 아래와 같이 변하게 될 거예요.

만약 이와 같은 상황에서 디스크 블록 4개를 사용해야 하는 E라는 파일을 할당하려고 하면 아래와 같이 할당됩니다.

위와 같이 E 파일은 디스크에서 연속적으로 존재하지 못하고 분산되어 존재하게 되며 E 파일에 접근할 때 디스크 성능은 나빠지게 됩니다. 파일은 디스크에서 연속적으로 존재해야 가장 좋은 성능을 낼 수 있기 때문에 disk defragmentation tool(디스크 조각 모음 도구)가 도움이 될 수 있습니다. 디스크 데이터를 재구성하여 파일을 연속적으로 배치하고 여유공간을 만들기 위해 데이터를 이동하고 inode를 다시 작성하는 작업으로 성능을 높일 수 있습니다.

 

이전 글까지 디스크 블록의 크기는 4KB로 가정했었는데요, 예전에는 그렇지 않고 512바이트와 같이 작은 블록 크기를 사용했습니다. 디스크 블록의 크기가 작으면 내부 단편화 문제는 최소화할 수 있었지만 블록에 접근할 때 오버헤드가 발생할 수 있기 때문에 데이터를 읽고 쓰기에는 좋은 방법이 아닙니다. 파일 시스템은 이러한 성능 문제를 어떻게 하면 해결할 수 있을까요?

FFS: Disk Awareness Is The Solution

아까 언급한 성능 문제들에 대한 연구가 계속되었고 결국 더 좋은 파일 시스템을 만들어 냈습니다. 이는 Fast File System이라고 불리며 disk aware이라는 아이디어로 성능 문제를 해결합니다. 이는 디스크의 구조와 할당 정책을 설계하여 성능을 향상하는 것으로 하나의 정책을 미리 말하자면, inode와 해당 inode가 가리키는 디스크 블록은 근처에 배치하여 seek time을 줄일 수 있습니다. 이 외에도 어떤 방법으로 파일 시스템의 성능을 향상했는지 지금부터 알아보겠습니다.

Organizing Structure: The Cylinder Group

첫 번째는 디스크 구조를 변경하는 것이었습니다. 아까도 잠깐 말했듯 inode와 디스크 블록이 너무 멀어지면 seek time이 많이 발생하고 이는 결국 성능 저하로 연결됩니다. 이를 최소화하기 위한 방법이 지금부터 알아볼 방법인데, 일단 그전에 디스크의 구조를 알아야 합니다.

디스크는 위와 같이 여러 개의 플래터가 존재하며 각각의 플래터는 많은 트랙을 가집니다. 같은 트랙에 존재하는 데이터에 접근할 때는 seek time이 발생하지 않고 rotate time만 발생합니다. Cylinder라는 용어가 등장하는데, Cylinder는 같은 위치의 트랙들을 말하며 위의 그림에서 진한 회색의 트랙들이 각 플래터마다 존재하는데, 이들을 모두 모은 것이 하나의 Cylinder라고 할 수 있습니다. Cylinder Group은 이러한 Cylinder를 모은 것으로 하나의 디스크는 결국 Cylinder Group으로 나타낼 수 있게 됩니다. 위의 그림에서는 인접한 3개의 Cylinder를 모아 하나의 Cylinder group으로 나타냈으며 Cylinder가 인접해있는 것을 모았기 때문에 Seek time도 최소화할 수 있게 됩니다.

 

FFS에서는 이러한 Cylinder 아이디어를 통해 inode와 데이터 블록을 같은 Cylinder, 혹은 Cylinder Group에 배치하여 디스크 성능을 향상하는 방법을 사용합니다. 또한 동일한 디렉터리에 존재하는 파일과 같이 비슷한 파일들을 동일한 그룹에 배치하여 공간 지역성을 사용한 성능 향상을 이뤄냅니다. FFS가 하나의 Cylinder group에서 유지하는 내용에 대한 예를 보며 이해해보겠습니다.

위의 그림은 하나의 Cylinder Group의 구성요소를 나타낸 것입니다. FFS는 안정성을 위해 각 그룹에 S(슈퍼 블록) 블록의 사본을 보관합니다. 이는 파일 시스템을 마운트 할 때 필요하며 여러 개의 복사본을 가지고 있기 때문에 안정적으로 파일 시스템을 마운트하고 접근할 수 있습니다. 또한 그룹별 inode bitmap(ib), data block bitmap(db)를 위한 공간을 가지고 있으며 inode, data를 위한 공간도 존재합니다. 이와 같은 구조가 디스크 하나에 하나만 존재하는 것이 아닌 Cylinder Group마다 존재하게 되고 이는 Seek Time을 줄여 성능 향상에 도움을 주게 됩니다.

Policies: How To Allocate Files and Directories

방금 알아본 Cylinder Group 구조가 적용되었다면 이젠 파일과 디렉터리, 그리고 해당 파일들의 메타 데이터를 디스크에 배치하는 방법을 결정해야 합니다. 아까도 잠깐 언급했듯 비슷한 파일, 디렉터리를 같은 그룹에 배치하는 아이디어에서 출발합니다.

 

그렇다면 비슷한 것들을 어떻게 결정할 수 있을까요? 이를 구현하기 위해서는 몇 가지를 생각하면 됩니다. 먼저 디렉터리의 배치입니다. 할당된 디렉터리 수가 적은 Cylinder Group, 사용 가능한 inode가 많은 그룹을 찾습니다. 이는 각각의 그룹마다 디렉터리를 균등하게 배치하기 위함입니다.

 

다음으로 파일이 있는데요 파일의 경우 FFS는 두 가지 작업을 수행합니다. inode와 동일한 그룹에 있는 파일의 데이터 블록을 할당하여 inode와 데이터 블록 간 seek time을 줄입니다. 그리고 해당 파일과 동일한 디렉터리에 있는 모든 파일을 해당 디렉터리의 그룹에 배치합니다. 예를 보며 이해해볼까요?

위와 같이 파일과 디렉터리가 존재할 때 디스크에 어떻게 배치하는지 살펴보겠습니다.

위와 그림은 그룹은 0~7까지 8개 존재할 때 아까 본 파일과 디렉터리들을 FFS가 디스크에 배치하는 방법입니다. a, b, c, d는 같은 디렉터리에 존재하므로 그룹 1번에 모두 배치한 것을 볼 수 있고 b, f도 동일한 이유로 2번 그룹에 배치한 것을 볼 수 있습니다. 이렇게 배치하게 되면 inode와 데이터 블록이 가까이 배치되어 파일 접근이 빨라집니다. 

 

그렇다면 모든 그룹에 공평하게 배치하는 예도 한 번 볼까요?

위와 같이 디렉터리와 파일들을 모두 그룹별로 하나씩 배치할 수도 있습니다. 하지만 이렇게 배치하면 지역성이 유지되지 않으며 a 디렉터리의 모든 파일에 접근하고 싶을 때 4개의 그룹에 접근해야 하는 상황이 발생합니다. 실제로 디렉터리의 파일들은 함께 접근되는 경우가 많기 때문에 위와 같이 배치하면 성능이 나빠질 수 있습니다.

The Large-File Exception

그럼 만약 하나의 파일이 하나의 그룹을 모두 채울 만큼 큰 사이즈 일 때는 어떻게 배치해야 할까요? 아무런 규칙이 없다면 그냥 하나의 그룹에 해당 파일을 다 넣어버릴 거예요.

위와 같이 a라는 파일이 너무 커서 그룹의 블록들을 거의 다 사용해 버릴 수 있다는 얘기가 됩니다. 이렇게 된다면 만약 a파일이 있는 디렉터리에 다른 파일들이 있을 때 다른 파일들은 동일한 그룹에 존재하지 못할 수 있게 됩니다. 이러한 문제를 해결하기 위해 FFS는 a 파일과 같은 대용량 파일은 몇 개의 그룹에 chunk 단위로 분산하여 배치합니다. Chunk 단위란 하나의 그룹에 저장할 블록 개수라고 보면 됩니다. 그럼 아까의 구조 말고 chunk를 블록 5개로 정해서 디스크에 배치해보겠습니다.

위와 같이 a 파일을 여러 개의 그룹에 배치하는 것이죠. 이렇게 하면 하나의 그룹에 대한 사용률도 분산할 수 있습니다. 근데 이렇게 배치해버리면 a라는 파일을 연속적으로 읽을 수 없기 때문에 성능이 저하된다고 생각되는데요, 이러한 문제는 chunk 크기를 주의 깊게 정하면 해결할 수 있습니다. chunk 크기가 충분히 크다면 거의 대부분의 시간을 데이터를 전송하는데 쓸 수 있고 전체 시간에서 다음 chunk로 이동하는 시간의 비율을 낮게 유지할 수 있습니다. 이러한 것을 amortization(상각)이라고 합니다. 예를 보며 정말 그런지 볼까요?

 

디스크가 특정 블록을 찾는 평균 시간을 10ms라고 하고 40MB/s의 속도로 데이터를 전송한다고 가정해보겠습니다. 우리의 목표는 디스크가 다음 Chunk로 이동하는 시간에 전체 시간의 50%만 사용하고 싶다고 한다면 10ms만큼 이동하고 10ms만큼 데이터를 전송하면 됩니다. 그럼 chunk의 크기를 얼마로 하면 될까요? 이를 계산하는 방법은 아래와 같습니다.

즉 한 번 블록을 찾으러 가기 전에 409.6KB만큼의 데이터를 전송한다면 전체 시간의 50%를 전송에 사용할 수 있다는 말이 됩니다.

이 비율은 위의 그래프를 보면 알 수 있듯이 Chunk의 크기가 커지면 커지게 됩니다. 하지만 이러한 계산을 FFS에서 사용하진 않습니다. 대신 inode 자체의 구조를 기반으로 간단한 접근 방식을 사용합니다. 이전 글에서 알아본 Indirect block, direct block을 기억하시나요? 이 개념을 FFS에서 사용하게 되는데, 12개의 direct block들은 inode와 동일한 그룹에 배치합니다. 그 외의 indirect block 들과 indirect block들이 가리키는 블록들은 모두 다른 그룹에 배치하게 됩니다. 디스크는 전송속도보다 디스크 회전 속도, seek time 속도가 현저히 느리기 때문에 더 나은 성능을 위해선 다음 chunk 블록으로 이동하기 전에 더 많은 데이터를 전송해야만 합니다.

 

A Few Other Things About FFS

FFS에는 몇 가지 다른 혁신들도 도입했는데요, FFS를 만든 사람들은 아주 작은 파일에 대한 걱정이 많았습니다. 당시엔 대부분의 파일의 크기가 2KB 정도였고 4KB 블록을 사용하게 되면 내부 단편화가 발생하여 공간 효율성이 좋지 않았기 때문인데요, FFS를 만든 사람들은 아주 간단하게 이를 해결합니다. 그냥 블록의 크기를 작게 만들어버리는 방법을 선택한 것인데요, 따라서 하나의 블록의 크기가 512B인 블록도 만들기로 정하게 됩니다. 즉 1KB와 같이 4KB보다 작은 파일들에는 512B 짜리 블록을 할당하고 4KB가 넘는 파일은 4KB 블록과 512B 블록을 적절히 사용하여 저장하는 것이죠.

 

물론 말로만 봐도 이러한 작업이 복잡하고 뭔가 추가적인 작업을 해줘야 할 것을 알 수 있습니다. FFS는 이러한 오버헤드를 libc 라이브러리를 수정하여 해결할 수 있었습니다. 라이브러리는 쓰기를 바로 하지 않고 어느 정도 모은 뒤 4KB가 되면 그때서야 chunk로 발행하여 오버헤드를 피할 수 있었습니다.

 

FFS에서 도입한 또 다른 혁신은 성능에 최적화된 disk layout이었습니다. FFS가 만들어진 당시엔 디스크가 지금보다는 덜 발달되어있었으며 이는 연속 읽기에서 문제를 발생했습니다.

위의 그림에서 왼쪽 디스크와 같이 블록들을 배치하면 문제가 발생합니다. 0번부터 5번 블록까지 읽으라는 요청이 발생했을 때, FFS는 0번 블록 읽기를 먼저 수행하겠죠? 근데 0번을 모두 읽고 1번을 읽으려고 하다 보니 이미 디스크가 회전해서 1번 블록을 읽으려면 디스크를 한 바퀴 또 돌려야 하는 문제가 발생하는 것이죠. 이와 같은 문제를 해결하기 위해서 위의 그림에서 오른쪽과 같은 디스크 레이아웃을 사용합니다. 0~5번 블록을 읽으라는 요청이 발생해도 블록 간에 거리가 좀 있어서 0번 블록을 읽고 1번 블록을 읽을 때 아까와 같이 한 바퀴 회전해야 하는 문제를 해결할 수 있는 것이죠.

 

그런데 이러한 레이아웃에서는 최대 대역폭의 50%의 성능만 얻게 됩니다. 그 이유는 전체 블록에 한 번씩 접근할 때 디스크가 총 2번 회전해야 하기 때문이죠. 따라서 최신 디스크에서는 디스크 캐시(track buffer)를 사용하여 이를 해결합니다. 전체 디스크를 한 번 읽은 뒤 이를 디스크 캐시에 버퍼링 합니다. 그 후의 읽기에 대해서는 캐시에서 데이터를 가져오게 됩니다. 

 

또한 FFS에서는 파일 이름을 길게 하는 것을 가능하게 하는 최초의 파일 시스템이었습니다. FFS 이전엔 8글자가 최대 이름 길이였는데 FFS에서 더 긴 이름을 가질 수 있게 되었습니다. 또한 Symbolic link라는 새로운 개념이 도입되었고 이전 글에서 알아본 대로 hard link는 디렉터리를 가리킬 수 없고 파일 시스템에서 꼬일 우려가 있기 때문에 파일만 가리키는 심볼릭 링크를 사용할 수 있었습니다. 또한 FFS은 파일 이름을 바꾸는 rename() 작업도 도입했죠. 즉 FFS는 성능 향상뿐만 아닌 사용성도 많이 향상한 파일 시스템이라고 할 수 있습니다.

Summary

이번 글에서 알아본 FFS는 파일 시스템 역사에서 아주 큰 발전이었다고 합니다. 이후에 만들어진 파일 시스템들은 대부분 FFS에서 영감을 받았다고 하네요! 그러한 FFS를 다시 정리해보면 파일과 디렉터리를 지역화를 적용한 배치를 통해 디스크 탐색 시간을 줄였으며 그 결과로 파일과 디렉터리를 동일한 그룹에 배치했습니다. 또한 사이즈가 많이 큰 파일에 대한 처리와 FFS에서 추가된 다양한 방법들에 대해서도 알아봤습니다. 다음 글에서는 드디어 파일 시스템의 Consistency(일관성)을 위한 FSCK와 Journalin에 대해 알아보도록 하겠습니다! 감사합니다.