[운영체제]Advanced File System

기타/운영체제

[운영체제]Advanced File System

stonesy 2022. 6. 4. 14:05

728x90

1. Locality and Fast File System

2. Crash Consistency: FSCK and Journaling

3. Summary. Feature of Various FS: Ext2/3/4, FAT, Flash FS

2. Crash Consistency: FSCK and Journaling

3. Summary. Feature of Various FS: Ext2/3/4, FAT, Flash FS

Advanced File System

1. Locality and Fast File System

UFS(Unix File System)

:Unix가 처음 만들어졌을 때 만들어졌던 Unix File system이다.

구조

Boot sector	시스템에 처음 전원이 들어왔을 때 부팅에 필요한 정보
Superblock	file system에 대한 Meta-data를 관리
Bitmap	가용 공간 관리
Inode	파일에 대한 Meta-data관리
User data	사용자 데이터

접근 방법

Inode와 data에 번갈아가면서 접근하게 되는데, 이때 성능(Performance)과 일관성(Consistency) 측면에서 문제가 생긴다.

성능(Performance)	Inode와 data가 다른 track에 위치하여 seek time이 오래 걸린다. 따라서 성능면에서 좋지 못하다. →inode와 data를 좀 더 가까운 track에 같이 배치하면 성능이 좋아질 것이다.
일관성(Consistency)	데이터 하나를 write하기 위해서는 상당히 많은 I/O가 발생한다.(multiple I/O가 발생한다.)

*UFS, VSFS의 단점

-성능이 매우 나쁘다.

: file을 오픈하기 위해서는 inode와 data를 번갈아가면서 읽어야 한다. disk 구조상에서 이를 수행하기 위해서는 long seek distance가 소요된다.

→inode와 data를 좀 더 가까운 track에 같이 배치하면 성능이 좋아질 것이다.

FFS(Fast File System from BSD OS)

-inode와 user data를 가깝게 위치시킨다.

→같은 cylinder(같은 track number를 가짐)에 위치시킨다. 같은 cylinder에 있는 data에 접근하기 위해서는 seek time이 따로 필요없기 때문이다.

→실제로 ext2,3,4(linux에서 사용되는 기본 file system)도 이 개념을 적용한다.

*FFS in detail

Partition은 여러 개의 cylinder group으로 나누어 지는데, 각 cylinder group마다 superblock, bitmap, inode, data blocks들을 따로 가진다. superblock은 file system을 통틀어서 1개만 필요하지만 신뢰성 향상을 위해서 똑같은 정보를 여러 개 가지고 있는다.

*Issue

directory, file을 새로 만들 때, 어느 group에 만들 것인가?

규칙1. load balancing을 고려하기 위해서 free한 inode가 가장 많은 group을 선택해서 directory를 만들어준다.

규칙2. file이 속한 directory에 같이 만든다. directory 내부의 파일들은 같이 읽힐 확률이 높은데, 이를 namespace locality라고 한다.

Even allocation(load balancing을 최대로 하는 기법)과 FFS allocation기법을 비교하자.

Even allocation	FFS allocation
load balancing을 최대로 하기 위해서 모두 다른 group에 균일하게 할당하였다.	새로 만들어진 directory는 규칙1에 의해서 비어있는 3,4,5,6,7에 만들어질 것이다. 반면, 새로 만들어지는 파일은 규칙2에 의해서 directory와 같은 위치에 만들어지고자 할 것이다.

규칙3. 하나의 그룹에 들어갈 수 있는 block의 개수를 제한함으써 namespace locality의 가능성을 높인다. 큰 파일을 다루기 위한 규칙이다.

→큰 파일은 한 group을 다 채울 수 있고, 같은 gourp에 모두 할당하면 namespace locality를 떨어뜨린다. 따라서 제한된 개수만큼만 같은 directory와 같은 group에 할당하고 넘치면 다음 group으로 넘어간다.

→ 규칙 3을 적용하면, namespace locality의 가능성을 높일 수 있지만, 한 파일 내의 지역성에서는 손해이다.

Rule3에 대한 분석

large file을 읽을 때, rule 3을 적용하면 중간중간에 seek overhead가 걸리는데 얼마나 걸리는지 분석해보자.

Assumption. seek time=10ms, bandwidth=40MB/s

Example1. 한 group에 최대로 할당할 수 있는 데이터의 크기를 4MB라고 하자.(4MB동안은 seek time 없이 데이터를 읽을 수 있는 것이다.)

-Transfer time: 4MB/40(MB/s)=100ms

-seek time=10ms→100/110=90%

*Example2.*한 group에 최대로 할당할 수 있는 데이터의 크기를 400KB라고 하자.

-Transerfer time: 0.4MB/(40MB/s)=10ms

-seek time=10ms→50%=10/20

: chunk size(한 group에 할당할 수 있는 최대 데이터의 크기)를 크게하면 seek overhead를 줄일 수 있다.

FFS에 대한 다른 특징

cylinder group: 같은 track number를 가지는 집합이다.
→inode와 data를 같은 cylider group에 넣어 seek time을 줄이다. namespace locality를 활용하여 seek time을 줄인다.
실제 I/O연산을 하는 block의 크기를 늘렸다.→단점: 내부 단편화가 생긴다.※내부 단편화: disk block의 할당된 부분을 모두 사용하지 않고 일부는 사용하지 않는 문제
※외부 단편화: 데이터들이 연속적으로 존재하지 않고, 불연속적으로 존재하는 것(free space가 떨어져 있는 것)→disk의 입장에서는 seek time이 많이 발생하기 때문에 많이 발생한다.
→장점: 크기가 커져서 seek time을 줄일 수 있고, transfer을 많이 할 수 있다. 즉, disk의 bandwidth usage가 높아진다.
내부 단편화 해결을 위해서 sub-blocks를 할당한다. 내부 단편화는 할당한 disk block의 전체를 사용하지 않았을 때 발생한다. 따라서 file의 크기가 크면 block의 크기를 크게 할당하고, 반대로 file의 크기가 작으면 block의 크기를 작게 할당한다.(fragment 단위로 나눠서 작게 할당한다.)
Parameterization: transfer하는 동안 회전해서 지나갈 수 있다. trasfer의 시간만큼 여유공간을 삽입한다.
Symbolic link를 처음 도입.. 등

Consistency

disk는 비휘발성이므로 전원이 공급되지 않더라고 데이터가 유지된다. 하지만 이 경우, 문제가 발생했을 때 전원을 껐다 키더라도 문제는 사라지지 않는다.→문제가 없는 상태로 유지하는 것이 굉장히 중요하다.

Consistency란?

valid한 상태를 유지하는 것이다.

ex) inconsistency한 상태: 실제로 사용 중임에도 bitmap에서 free한 상태라고 말하는 것이다.

→갑자기 전원 결함이 발생했을 때, bug가 발생했을 때 이와 관련된 문제가 발생할 수 있다.

Solution

-FSCK(File System Check)

-Journaling

*파일의 크기가 4KB→8KB로 변화하였다. 무엇이 변화되는가?

Bitmap
Inode
User data의 3가지 영역이 변경되어야 한다.

→이 3개가 한 번에 disk로 내려가는 것이 아니라, **delayed write using cache(queuing)**이 발생한다.

→도중에 전원결함이 발생하면, 일부만 쓰여질 수 있다.(일관성의 문제)

1.Data만 쓰여진 경우: 사실상 문제가 없다.→file system은 여전히 일관적인 상태이다.

2.Bitmap만 쓰여진 경우: space leak이 발생한다.

실제로는 사용중이지 않은 공간인데, 사용 중이라고 표시된다.

3.Inode만 쓰여진 경우: 1)garbage read가 발생할 수 있다. 2)일관성이 깨진 상태가 된다.(Inode와 Bitmap이 서로 다른 내용을 가리킨다.)

4.Inode가 쓰여지지 않은 경우: Bitmap과 Inode가 서로 다른 정보를 가지고 있다.→일관성이 깨져 있따. space leak 발생

5.Data와 Inode만 사용 가능: 마찬가지로 일관성이 깨진 상태이다.

6.Data가 쓰여지지 않은 경우: garbage read가 발생한다.

해결책

fsck

: file system에 문제가 생겼을 때 가장 유명한 도구: file system을 처음부터 check해서 문제가 있는 부분을 고친다.

file system의 layout의 처음부터 끝까지 분석한다.

-superblock: file system을 위한 가장 기본적인 meta-data로, sanity check 등을 한다.

-free blocks: 모든 bitmap을 보고, 모든 inode와 data block을 따라가면서 check한다.

-inode: link 수가 잘못된 것이 있는지, link 수가 0인데 계속 남아있는 파일이 있으면 삭제한다.

-directory checks: 실제 user data는 file system입장에서 check하기 어렵다. directory를 확인한다.

문제

-너무 느리다.

Journaling

: 쓰기 전에 어떤 작업을 할 것인지 log를 남겨 둔다. 그리고 문제가 발생하면 log를 참고한다.

-redo: 내 의도대도 다시 동작

-undo: 옛날 상태로 돌아가기

Journaling FS

Journaling기법을 사용하는 file system

*ext3는 ext2에 journaling 기법을 도입한 file system이다.

Data journaling

step1: journaling

jornal 공간에 inode, bitmap, data를 쓴다. 3개를 전부 쓰거나 아예 쓰지 말아야 하는 원자성을 만족해야하기 때문에 이를 으로 묶는다.

Log

-physical logging: 최근 많이 사용하는데, 원래 위치에 써야할 내용과 동일한 내용을 쓴다.

-logical loggig: 동일한 내용이 아닌 의도를 작게 만들어서 쓴다.

step1: checkpointing

원래 위치에 data를 쓰는 단계

결함이 발생하면 복구해야한다.→Recovery의 필요성

-redo: journal이 있는 내용으로 다시 replay한다.

-undo: journal을 성공하지 못한 상태에서 결함이 발생했다면 undo한다.

Journaling의 단점

-성능상의 단점

Approach 1: Transaction start, Inode, Bitmap, Data block, Transaction end를 한 번에 다 쓴다. 이 방법은 안전하지 않다.

Approach 2: 각각을 쓰면서 fsync()한다. 이 방법은 너무 느리다.

Approach 3: transaction end를 쓰는 것을 다른 것과 구분한다.(commit)

-write volume의 단점

사실상 데이터가 2번씩 쓰여지는 것이다. I/O traffic을 증가시켜 성능을 저하시킬 수 있다. 특히, 큰 파일을 쓰는데 그 문제가 심각하다.

Metadata Journaling

:Metadata만 journaling한다.

*data를 쓰는 것과 journal을 쓰는 것과 순서가 중요한가?→중요하다. 앞에서 일관성이 깨진 여러가지 예에서 data가 쓰여지기 전에 meta-data가 쓰여지면 garbage read 등의 문제가 발생한다고 하였다. meta-data가 쓰여지지 않고 data가 쓰여져도 큰 문제는 발생하지 않지만, data가 쓰여지지 않고 meta-data data가 쓰여지면 큰 문제가 발생한다. 따라서 항상 data를 먼저 써야 한다.

*순서를 지켜주지 않는 journaling mode를 writeback 모드라고 한다.(data와 meta-data를 쓰는 순서를 지키지 않는다.)

File system에서 consistency를 유지하기 위한 기법들

1.fsck: A lazy approach

→고장이 발생한 이후에 해결하는 방식

2.Journaling: An active approach

→고장이 발생하기 전에 미리 log를 남겨놓고 고장을 예방하고자 함

3.Soft update

항상 safe한 상태를 유지하도록 write 순서를 잘 조절한다.

4.COW(Copy on Write)

Write가 사용되었을 때 copy를 사용한다.

기존의 data를 link하거나, 새로 생긴 data를 link하므로 link가 무조건 보장된다.

5.Optimistic crash consistency

성능을 최대로 향상시키고, 쓸때마다 integrity를 보장할 수 있는 signal(checksum)을 만든다.

*Ext, Ext2, Ext3, Ext4

Ext⇒UFS

Ext2⇒FFS

EXT3⇒Ext2+Journaling

EXT4⇒Large size file 지원

-Extent-based mapping

:고정된 크기의 disk block을 지원하는 것이 아니라, 가변 크기의 disk block을 지원한다.

-해시 기반의 directory 검색 기능

FAT(File Allocation Table)

작은 storage를 위해서 만들어진 storage이다.

storage 공간이 작다. meta-data를 위한 공간이 작다.

작은 storage에서 굉장히 효과적이다.

Bitmap, Inode의 기능을 하나로 합쳐 FAT을 만들었다.

Directory는 파일에 대한 정보를 갖고 있으면서 FAT의 첫번째 index를 가지고 있다. 그리고 이 index를 따라 disk block을 찾아가면 파일을 읽을 수 있다.