10. Ext4 Filesystem

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

Ext4 §

• Minix FS 에서 진화한 Ext FS 가 계속 발전해 지금의 Ext4 까지 왔다.
  • FS 전체 용량은 최대 1EB 까지 늘릴 수 있고
  • 파일 하나당의 크기는 16TB 까지 늘릴 수 있다고 한다.

Direct, indirect blocks (~Ext3) §

• 뭐 기본적으로 생긴 것은 똑같다.
  • Inode 하나는 256byte 크기이고,
  • Direct 에는 data block 이 연결되고 Single-indirect/Double-indirect 에는 indirect block 이 연결되는
• Ext4 이전 상황은 아래와 같다고 하더라
  • 4Ki 사이즈 block 를 기준으로 했을 때, Inode 하나에는
    • Direct block: 파일 사이즈 $10\ast 4Ki=40Ki$ 까지 감당 가능
    • Single indirect block: 1 개의 블럭이 indirect block 으로 사용됨
      • Indirect block (4Ki) 하나에는 (32bit address 기준) 1024 개의 entry 를 저장할 수 있음
      • 따라서 single indirect 에는 파일 사이즈 $1024\ast 4Ki=4Mi$ 까지 감당 가능
    • Double indirect block: indirect block 계층이 하나 더 추가되므로, 파일 사이즈 $1024\ast 4Mi=4Gi$ 까지 감당 가능
  • 보다시피 파일 최대 크기가 4Gi 좀 넘기 때문에 아주 작다
  • 그리고, 1GB 파일을 4Ki block 들에 저장하려면 2^20 / 4 = 262,144 개의 block 을 연결해야 했기에 아주 번거롭다.
• 이 문제를 지금은 뒤에 나올 Extent 로 해결한다.

Block Group §

• Block Group 은 FFS 에서의 cylinder group 과 유사하다.
  • 128MB 고정크기를 가진다고 한다.
• Superblock 은 FS 전체에 대한 메타데이터, Group Descriptor 는 block group 에 대한 메타데이터인 것 같음
  • 얘네들은 모든 block group 에 동일하게 복제된다? FS init 시에만 그렇다는건지 아니면 항상 sync 되어 있다는 것인지는 모르겠음
• 각 Block group 이 하나의 disk 인 양 여기에 superblock, IB, DB 등이 들어가 있음
  • DB 와 IB 를 1 block 으로 한정

Ext4 extent §

• 기존에는 inode 에 각 block 마다 mapping 이 되어 있었지만, Ext4 로 오면서 연속된 공간은 하나의 mapping 으로 처리하는 Extent 개념이 도입된다.
• Extent 는 연속된 LBA 주소공간이 PBA 주소공간에도 동일하게 저장되어 있을 때 이 연속된 공간을 대표하는 하나의 descriptor 이다.
• Extent 자료구조는 offset, length, physical_length 세 필드를 가진다.
  • offset: LBA 시작점
  • length: 연속된 갯수
  • physical_length: 는 뭔지 잘 모르겠음
• 이제 이 Extent 를 사용했을 때에 최대 사이즈에 대해 계산해보자.
  • length 는 15bit 이다: 따라서 $2^{15}$ 개의 연속된 block 을 나타낼 수 있다.
    • 결과적으로 하나의 extent 는 최대 $2^{15}\ast 4Ki=128Mi$ 의 공간을 대표할 수 있다.
  • #draft 저 16TB file, 1EB filesystem 을 이걸로 어떻게 계산할 수 있을 것 같은데 일단 패스
• 이렇게 하면 당연히 차지하는 공간이 작기 때문에 좋지만, random access 를 위해서는 각각의 extent 를 다 꺼내 계산을 해야 하기 때문에 시간이 오래 걸리게 되는 문제점이 생긴다.
  • 따라서 이러한 선형 연산을 하지 않기 위해 extent 가 4개 이상으로 많아지면 tree 형태로 관리된다고 한다.
• Multi-block allocator: Block 을 할당할 때도 이 Extent 단위로 한다.
  • Ext3 까지는 블럭을 한번에 하나씩만 allocate 했다면
  • Ext4 부터는 이 Extent 단위로 연속된 block 들을 한번에 쭉 할당한다.
  • 이렇게 하면 fragmentation 도 줄어들고 allocate call 도 적게 하게 되므로 CPU utilization 을 줄일 수 있다더라.

Flex Block Group §

• 기존의 block group 이 128Mb 인데 여기 앞에는 전부 metadata 가 들어가서
• large sequential write 을 하려고 할 때 자꾸 이 metadata 때문에 중간중간 건너뛰어야 한다.
• 따라서 위처럼 block group 의 각 부분을 모아서 저장하는 방법을 Flex Block Group 이라고 한댄다.

#draft Record: 1h 11m

Delayed Allocation §

Record: 1h 15m

• Block allocation 을 매 write() syscall 마다 하는 것이 아닌 메모리에 일단 모아놨다가 나중에 flush() 할 때 수행하는 것.
  • 단점은 flush 를 하기 위해서는 os 의 허락을 받아야 하는데 이게 쉽지 않다?

여기부터는 2024-04-04 강의

• 이짓을 왜하느냐,,
  • Filesystem fragmentation: 오랜 기간 동안 파일들이 썻다 지웠다 하다 보니 파일의 각 block 이 여기저기 흩어지게 되는 문제가 있었음
  • 예를 들면 프로세스 세개가 각각 A, B, C 세 파일을 4KB 씩 계속 쓰면 ABCABC 이런식으로 할당되고 C 가 지워지면 AB-AB- 이렇게 돼서 external fragmentation 이 발생하게 되는 것
• 이것을 Ext4 에서는 write 시에 allocation 을 하지 않고 flush 시에 수행해서 방지한다.

Directory indexing: H-tree (Hash Tree) §

#draft Record 15m

• Ext4 에서는 H-tree 를 사용하여 directory 내의 filename 을 찾는다고 한다.
• “찾기 (indexing)” 에 사용되는 data structure 는 거의 무조건 tree 아니면 hash 이다.
  • Hash 는 빠르지만 worst case 가 존재하고
    • 아마 worst case 가 collision 을 의미하는 것 같다: collision 이 없게 하자니 메모리 사용량이 너무 많아지고, collision 을 어느정도 허용하자니 linear search 를 해야되고
  • Tree 는 비교적 느리지만 안정적
• H-tree 는 이 둘을 섞은 것이다.
  • 우선 file name 을 hash 한다 - digest 비교는 integer 비교이기 때문에 string 보다 훨씬 빠름
  • 그리고 hash collision 에 대해서는 digest 당 tree 를 구성한다.
    • Collision string 비교를 선형적으로 하는 것보다 트리를 사용하는 것이 훨씬 빠르기 때문
  • 즉, file name 이 주어지면 일단 hash 해서 digest 를 구하고 해당 digest 에 해당하는 tree 로 가서 file name 을 찾는 것.

Journaling §

• ext2 까지는 fsck 로 부팅시에 디스크를 full scan 해 망가진 데이터를 복구
• ext3 부터 journaling 이 도입
• 다음의 세 mode 로 작동한다:

• Data mode 는 다음처럼 수행
  • journal 영역에 inode 와 data 를 적고
  • sync() 해서 버퍼공간이 아닌 media 에 journal 이 반영되게 하고, 완료되면 commit 표시
  • 이후 실제 data flush 는 천천히
• Writeback mode 는 data mode 와 다르게 metadata 에 대한 journaling 과정을 따로 하는 것이다.
  • Metadata sync 가 안맞으면 다음과 같은 상황이 발생할 수 있다:
    • Block bitmap 에서는 없다고 하는데 inode direct/indirect 에는 pointer 가 있는 경우
    • Inode bitmap 에서는 있다고 하는데 연결된 directory entry 는 없는 경우
      • 이때에는 inode 의 reference counter 와 이놈을 참조하고 있는 directory entry 의 갯수를 추적해서 비교하고, directory entry 가 없으면 inode 를 삭제한다.
  • 따라서 Metadata (Bitmap-Directory-Inode) 셋 간의 sync 를 맞추는게 중허다.
  • 이를 위해 metadata write 전에 metadata journaling 먼저 하고, data block write 는 아무때나 수행하는 방법을 Writeback mode 라고 한다.
  • 하지만 이 모드는 단점이 있다.
    • Block 이 할당되었음을 block bitmap 이랑 inode 에 모두 명시해줘서 metadata sync 는 맞췄는데
    • 이 상황에서 data 가 commit 되기 전에 crash 가 나면
    • 이후에 해당 파일에 이 block 에 대한 이전의 data 가 보임
    • 근데 이전 data 가 내가 쓴 것이 아닐 수 있기 때문에 privacy 문제가 있다.
• 그래서 나온 것이 Ordering mode 이다. (기본)
  • 여기서는 data commit 를 먼저 한 이후에 metadata journaling + commit 를 수행한다.