30. Evolution of File system

Fast File System (FFS)

 

초창기 unix file system이 제어하는 스토리지가 디스크라는 사실을 인지하지 못해 seek overhead가 발생했던 것을 개선하기 위해 개발되었습니다. 우선 레이아웃 포맷을 설정하는 것이 중요합니다. 기존 indoe block, data block이 사라지고 cylinder group 이라는 블록이 생겼습니다.

 

superblock에는 파일 시스템 전체에 대한 메타 데이터 정보가 들어있습니다. 이 superblock이 1개만 존재할 시 reliablity 문제가 발생하기 때문에 superblock에 대한 복사본을 cylinder group 하나하나에 두게 됩니다. 이를 통해 superblock의 정보가 cylinder group 개수 만큼 추가로 더 존재하게 됩니다. 

 

이 cylinder group은 디스크에 인접한 실린더를 몇 개씩 묶어 그룹화를 통해 블록 전체를 하나의 cylinder group으로 만듭니다. 이 구조는 액세스하면 seek를 상당히 줄일 수 있습니다. 기존 실린더 정보를 알지 못해 발생했던 문제를 인접 실린더에 속한 블록들을 그룹으로 만들어 해결합니다.

 

 

 

cylinder group안에는 superblcok 복사본과 실린더 그룹 안에서 생성된 파일에 대한 data blocks과 inodes가 인접해서 존재합니다. 그리고 inode와 bitmap 정보들도 같이 가지고 있습니다. 기존 inode나 data block을 링크드 리스트로 만들어서 서로 멀리 있었는데 여기서는 bitmap을 사용한다는 것을 알 수 있습니다. 

 

추가적으로 어떤 파일의 콘텐츠와 inode들이 서로 인접한 곳, 같은 실린더 안에 존재한다는 것을 알 수 있습니다. 실린더 그룹안에는 superblock 정보도 가지고 있지만 자기 자체에 대한 메타 데이터도 가지고 있습니다. 이것을 per-cylinder group superblock 이라고 부릅니다. 

 

 

 

파일 시스템의 디스크 블록 사이즈는 큰 것이 좋습니다. 디스크 블록의 크기가 커지면 관리해야할 블록의 개수가 줄며, allocation, free operation의 횟수가 줄어듭니다. 하지만 내부 파편화(internel fragmentation) 문제가 존재하기에 데이터 블록보다 작은 공간을 요구하는 파일의 경우 스토리지의 효율이 떨어지게 됩니다. (디스크 블록 = 데이터 블록)

 

FFS에서는 블록 사이즈를 4KB로 키우며 한 블록의 내부를 fragment라는 작은 단위로 나눴습니다. 4KB 블록안에 8개의 fregment가 존재합니다. 1개의 fragment는 1개의 섹터로 생각하시면 되고 섹터에서 왔으니 각각 독립적으로 사용이 가능합니다. (한 블록 안에 한 fragment는 A 파일에 사용하고 그 다음 fragment를 B라는 파일에 사용이 가능)

 

즉 빈 공간은 다른 파일이 사용할 수 있어 fragmetation을 완화시킬 수 있습니다.

 

- 어차피 8의 fragment로 나누면 관리해야할 부분이 늘어나는 것 아닌가? = 디스크 블록의 개수가 많은 것과 frament가 많은 것은 파일 시스템에 다른 영향을 줍니다. 데이터 블록의 개수가 많으면 메타 데이터 크기가 증가하며, 4KB와 1KB 동일한 만큼 액세스한다면 4KB는 1번, 1KB는 4번이 필요합니다. (액세스 횟수가 줄어들며, 프로세스와 스레드 느낌으로 용량 부분이 해결되는 것)

 

 

 

FFS에는 몇 가지 규칙들이 존재합니다. 첫 번째는 무조건 seek optimization을 한다는 것입니다. 이를 위해서 어떤 파일의 데이터 블록과 그 파일의 inode는 같은 실린더 그룹에 둔다는 것과 동일한 디렉토리에 속한 파일들은 같은 실린더에 둔다는 걸 생각해 볼 수 있습니다.

 

 

 

하지만 이런 규칙에도 예외를 적용해줘야 합니다. 사이즈가 굉장히 큰 파일을 저장할 때 하나의 파일을 하나의 실린더에 다 넣는다면 연관된 파일들을 동일한 실린더 그룹에 넣을 수 없는 문제가 생기게 됩니다. 그래서 이 경우 여러 개의 인접 실린더에 나눠서 저장하게 됩니다. 

 

 

 

어떤 파일의 크기가 48K 보다 커지면, 48K를 한 실린더 그룹에 넣고, 나머지 부분을 다음 실린더 그룹에 넣습니다. 48K인 이유는 하나의 inode의 경우 12개의 direct index와 한 개의 in-direct index, 한 개의 double direct index로 이루어져 있어 48K까지의 공간을 디렉트 액세스할 수 있기 때문입니다. (12 * 4K = 48K)

 

큰 파일의 경우 48K를 하나의 실린더 공간에 넣고 그외 남은 부분은 인접한 실린더에 분산해 저장함으로써 해당 파일과 연관된 작은 파일들도 동일한 실린더 그룹에 들어올 수 있게 만드는 방법입니다.

 

 

 

두 번째 최적화는 locational latency를 최적화 시키는 것입니다. 0번 섹터를 읽고나서 1번 섹터를 읽으려고 하는데 명령이 전달되기 전에 RPM이 빨라 해당 부분이 지나가게 되면 한 바퀴 더 돌아야 1번 섹터를 읽을 수 있습니다. 이런 경우가 sequential access에서는 많이 발생하기 때문에 0, 1, 2 이렇게 1씩 증가시켜 저장하는 것이 아니라 rotdelay 만큼 섹터를 증가 시켜 저장하게 되면 문제를 해결할 수 있습니다.

 

결과적으로 이런 최적화를 사용하여 FFS는 read throghput과 write throghput이 8배에서 10배 향상되었으면 디스크 스페이스의 낭비는 거의 없고 FS와 비슷한 오버헤드만 발생시키게 됩니다. FFS도 문제를 가지고 있는데 crash recovery를 위해서 file system checker를 사용한다는 것입니다. 

 

 

 

Log Structed File System (LFS)

 

 

LFS는 디스크 스토리지가 점점 커져서 파일 시스템을 부팅할 때마다 file system checker를 사용하면시간이 너무 오래 걸린다는 문제와 파일 시스템을 탑재한 OS가 컴퓨터에서만 사용하는 것이 아니라 여러 번 끄고 키는 간단한 단말기에도 적용해야 하기 때문입니다.

 

LFS는 저널링과 비슷한 방법을 사용합니다. 파일 시스템 상태를 modify 하는 operation들이 생기면 파일 시스템을 바로바로 modify 시키지 않고 sumary 정보인 log를 만들어서 저장을 하는 것입니다. 저널링 같은 경우는 log를 디스크에 있는 Journaling area에 저장을 하는데 LFS는 메모리 상에 있는 log로 만듭니다.

 

log를 만들어 메모리에 저장하면 점점 쌓여 로그가 어느 정도 큰 세그먼트가 되면 write opearaion을 통해서 스토리지로 저장시키는 방법을 사용했습니다.

 

 

 

로그를 메인 메모리와 스토리지에 같이 저장하게 되면 crash나 power loss를 만나더라도 스토리지를 통해 쉽게 복원할 수 있게 됩니다. 정리하자면 LFS는 저널링을 메인 메모리를 통해서 구현하고 그 저널링 로그를 fast high performance wirte operation을 통해서 스토리지에 반영하는 방법입니다.

 

Linux의 경우에도 ext3, ext4와 함께 저널링과 LFS를 같이 사용하고 있습니다.

 

 

 

Disk Scheduling

 

 

Linux OS의 구조는 다음과 같이 구성되어 있습니다. 여기서 맨 밑에는 실제 데이터를 저장하는 디스크가 존재하며 그 위에 디스크 드라이버, 그 위에 디스크 드라이브로 가기 위한 디스크 I/O request가 쌓이는 queue가 존재합니다. 이 queue를 제어하는 것이 I/O 스케줄러입니다.

 

이번에는 I/O 스케줄러 밑에 있는 스토리지가 디스크일 경우 동작하게 되는 디스크 스케줄러에 대해 살펴볼려고 합니다. 디스크 I/O 스케줄러가 처리하는 request는 buffer cache miss로 인해 실제로 디스크 액세스를 진행해야 하는 request들 입니다. 

 

 

 

시간이 지나면 이런 request가 쌓이게 되는데 어떤 방식으로 처리하는지 알아보겠습니다. 다음과 같이 디스크 볼륨과 디스크 드라이브가 있는 영역 바로 앞에 I/O request queue가 존재합니다.

 

request가 쌓이는 이유는 CPU의 작업 속도에 비해서 스토리지 디바이스가 느리고 컴퓨터는 multi programming과 multi tasking을 하기 때문에 I/O 명령 실행하는 많은 프로세스가 존재합니다. 이렇게 쌓이는 request에 대한 실행 순서를 결정하는 것이 I/O 스케줄러입니다. 순서를 정할 때 가장 고려해야 할 점은 seek입니다. 

 

 

 

다음과 같이 1, 5, 2, 4, 3 실린더 순서대로 request가 도착했다고 해보겠습니다. FIFO로 동작할 시 1번이 가장 먼저 도착했으니 arm을 1번으로 옮기고 그 다음이 5번 실린더이니 4번 만큼 옮겨 읽는 방식으로 진행하게 됩니다. FIFO로 이 I/O request를 처리하면 총 seek distance가 10이 됩니다.

 

만약 1, 2, 3, 4, 5로 진행할 시 seek distance가 4로 줄어듭니다. seek는 굉장히 긴 시간인데 10번 옮길 걸 4번으로 줄일 수 있다면 굉장히 큰 수확이 될 수 있습니다.

 

 

 

디스크 스케줄링을 설계하기 위한 design goal을 알아보겠습니다. 첫 번째는 performance 부분으로 respons time을 줄이며 throughput을 maxmize 시켜야 합니다. 두 번째는 fairness로 스케줄링을 진행할 때 오랫동안 소외되는 request를 발생하지 않게 하는 것입니다. 

 

latency에 대해 살펴보면 seek time, rotational latency, transfer fime이 존재하며 이걸 다 합친 시간이 disk access time이 됩니다. 이 disk access time은 5 ~ 50 ms를 차지합니다. queuing delay는 I/O request에서 큐잉하는 시간이기 때문에 고려하지 않아도 됩니다.

 

 

 

FIFO는 CPU scheduling과 memory replacement 할 때도 사용할 수 있었지만 disk scheduling에서는 너무 많은 seek를 발생하기 때문에 최악의 성능을 보입니다. 그래서 이론적으로 최적의 스케줄링 알고리즘에 대해 생각하게 되는데 그것이 바로 Shortes Seek Time First (SSTF) 입니다.

 

현재 arm의 위치를 기준으로 request queue에 있는 request 중 가장 가까운 영역을 읽는 애들을 먼저 처리하는 방법입니다. 이 기법은 좋은 것 같지만 fairness에서 문제를 보이게 됩니다. 현재 arm이 위치하고 있는 실린더 주변으로 계속 request가 들어온다면 계속 거기서 머물러 멀리 떨어진 곳에서 들어오는 request를 무시하게 됩니다.

 

또한 I/O request에 실린더 정보가 들어 있는 경우는 거의 없기 때문에 shortest seek time을 계산하는 것이 어렵습니다. 하지만 피지컬 블록 넘버의 차이로 대충 추측할 수 있습니다. 인접한 블록들이 하나의 실린더에 들어갈 가능성이 높기 때문입니다. 이런 기법은 nearest request first 기법이라고 부릅니다. 이 방법도 fairness 상 starvation을 초래하기 때문에 사용되지 않습니다.

 

 

 

주로 많이 사용되는 기법이 elevator algorithm입니다. 한 방향으로 쭉 돌면서 버튼이 켜져 있다면 멈춰서 승객을 다 태우는 엘리베이터와 같이 arm을 한 방향으로 움직일 때 그 밑에 있는 request를 전부 처리해주고 다시 반대 방향으로 움직이면서 다 처리해주는 알고리즘을 scan algorithm 또는 elevator algorithm이라고 부릅니다. 

 

하지만 이 방법도 fairness에서 문제가 있는데 끝 부분에 있는 request에 경우 한 번밖에 처리를 못받는 반면에 중간에 있는 경우 2번씩 처리를 받게 됩니다. 이 문제를 해결하기 위해서 arm을 한 방향으로만 움직이는 기법이 C-SCAN 입니다.

 

 

 

SSTF가 가장 빠르긴 하지만 fairness 문제로 인해서 SCAN, C-SCAN 알고리즘을 사용합니다.

 

 

 

SCAN 알고리즘을 조금 더 개선한 LOOK 알고리즘의 경우 request가 없는데 끝까지 갈 필요가 없으니 arm movement를 조기 종료시키는 것입니다. 두 번째는 seek time과 rotational latency를 함께 고려해 최적화 시키는 shortest positioning time first 기법입니다.