20. File System Consistency

Crash Consistency

• Crash consistency는 system crash 이후에도 disk 위 file system structure가 모순되지 않도록 유지하는 문제다.
• 목표는 file system을 one consistent state에서 another consistent state로 atomic하게 이동시키는 것이다.
• 파일 시스템은 system call 하나를 처리하기 위해 여러 disk block을 update할 수 있다.
  • creat()
  • write()
  • unlink()
  • rename()
• 그런데 disk는 보통 single sector write 정도만 atomic하게 보장한다.
• 즉 여러 block write 전체가 하나의 transaction처럼 자동으로 처리되지는 않는다.
• 그래서 중간에 crash가 나면 일부 block만 disk에 반영되고, 나머지는 반영되지 않는 상태가 될 수 있다.

예를 들어 file append는 다음을 바꿀 수 있다.

1. data block 새로 쓰기
2. data bitmap update
3. inode update

• 이 중 일부만 disk에 반영되면 file system metadata가 서로 안 맞게 된다.

Consistent State

• consistent state란 file system의 metadata들이 서로 모순되지 않는 상태다.
• 예를 들어 다음 조건들이 맞아야 한다.
  • inode가 어떤 data block을 가리키면, data bitmap도 그 block이 allocated라고 표시해야 한다.
  • data bitmap이 allocated라고 표시한 block은 적어도 어떤 inode가 사용 중이어야 한다.
  • inode link count와 directory entry 수가 맞아야 한다.
  • 같은 data block을 두 inode가 동시에 소유하면 안 된다.
• crash consistency 문제는 단순히 “최근 write가 저장되었나?”가 아니다.
• 더 중요한 것은 저장된 metadata들이 서로 말이 되는가다.

Example: Appending Data

• 예를 들어 기존 file이 data block Da만 가지고 있다고 하자.
• 여기에 새 data block Db를 append하려면 최종 상태는 다음과 같아야 한다.
• 즉 최소한 다음 세 가지 update가 필요하다.
  1. 새 data block Db 쓰기
  2. data bitmap에서 Db를 allocated로 표시
  3. inode를 I에서 I'로 update해서 Db를 가리키게 함

Crash Scenario 1: Everything or Nothing

• 가장 쉬운 경우는 둘 중 하나다.

Everything touched media: No problem

Nothing touched media: No problem

• 아무 update도 disk에 반영되지 않음.

• append가 없었던 것처럼 보임. 즉 old consistent state로 남아 있는 상태.

Crash Scenario 2: Only Data Block Written > OK

• 새 data block Db만 disk에 쓰인 경우다.
• 이 경우 inode는 Db를 가리키지 않고, data bitmap도 Db를 free라고 표시한다.
• 그래서 file system 입장에서는 Db가 없는 block처럼 보인다.
• Db에 데이터가 쓰였지만 아무도 참조하지 않으므로 큰 metadata inconsistency는 아니다.
• 새 데이터는 잃어버릴 수 있지만, file system 구조 자체는 모순되지 않는다.

Crash Scenario 3: Only Inode Written > Inconsistent

• updated inode I'만 disk에 쓰인 경우다.
• inode는 이제 Db를 가리킨다.
• 하지만 data bitmap은 Db를 free라고 말한다.
• 문제가 생긴다.

inode: Db is part of file
bitmap: Db is free

• 이 상태는 inconsistent하다.
• 더 큰 문제:
  • file을 읽으면 Db에서 garbage data 또는 old contents를 읽을 수 있다.
  • 나중에 file system이 Db를 free block이라고 생각하고 다른 file에 할당할 수 있다.
  • 그러면 두 inode가 같은 data block을 공유하는 심각한 corruption이 생긴다.

Crash Scenario 4: Only Data Bitmap Written > Inconsistent

• data bitmap만 update된 경우다.
• bitmap은 Db가 사용 중이라고 말한다.
• 하지만 어떤 inode도 Db를 가리키지 않는다.

bitmap: Db allocated
inode: nobody points to Db

• 이 상태도 inconsistent하다.
• 결과적으로 Db는 다시 사용되지 못한다.
• 즉 lost data block, 또는 space leak가 생긴다.

Crash Scenario 5: Inode and Bitmap Written >OK

• inode와 data bitmap은 쓰였지만, data block Db는 쓰이지 않은 경우다.

• metadata만 보면 일관적이다.
  • inode가 Db를 가리킨다.
  • bitmap도 Db를 allocated라고 말한다.
• 하지만 실제 Db 내용은 아직 새 데이터가 아닐 수 있다.
• file을 읽으면 garbage data 또는 old contents를 읽을 수 있다.

metadata consistency: OK
data correctness: may be bad

• 강의안도 이 경우 metadata는 consistent하지만 read 시 garbage data를 얻을 수 있다고 설명한다.

Crash Scenario 6: Inode and Data Block Written > Inconsistent

• inode와 data block은 쓰였지만, data bitmap은 쓰이지 않은 경우다.
• inode는 Db를 가리킨다.
• Db에는 새 데이터도 들어 있다.
• 하지만 bitmap은 Db를 free라고 말한다.

inode: Db allocated to file
bitmap: Db free

• inconsistent하다.
• 나중에 Db가 다른 file에 재할당될 수 있다.
• 그러면 같은 block이 두 파일에 의해 공유되는 corruption이 생길 수 있다.
• 강의안도 이 경우를 inconsistent라고 정리한다.

Crash Scenario 7: Bitmap and Data Block Written > Inconsistent

• data bitmap과 data block은 쓰였지만, inode는 쓰이지 않은 경우다.
• bitmap은 Db가 allocated라고 한다.
• 하지만 inode는 여전히 Db를 가리키지 않는다.
• 따라서 Db는 어떤 file에서도 접근할 수 없다.
• lost block, space leak가 생긴다.

bitmap: Db allocated
inode: nobody points to Db

• 이것도 inconsistent하다.
• 강의안도 bitmap과 data block만 쓰인 경우를 inconsistent, lost data block이라고 설명한다.

Crash Scenario Summary

• 이 표에서 중요한 점은:
  • crash 이후 file system은 “완전히 이전 상태”거나 “완전히 이후 상태”면 괜찮다.
  • 문제는 부분적으로만 update된 상태다.
  • 특히 inode와 bitmap의 말이 다르면 큰 문제가 된다.

FSCK

• FSCK = File System Checker
  • Unix 계열에서 file system inconsistency를 찾아 고치는 도구. crash 이후 whole file system을 scan해서 contradictions를 찾고 fix함.
  • Windows의 Scandisk와 비슷하다고 보면 된다.
• 보통 crash 이후 file system을 mount하기 전에 실행된다.
• 전체 file system을 scan하면서 모순을 찾고 고친다.

FSCK가 검사하는 것

• FSCK는 다음과 같은 consistency를 검사한다.

1. Inode bitmap consistency
   • 실제 사용 중인 inode와 inode bitmap이 일치하는가?
2. Data bitmap consistency
   • inode들이 실제로 가리키는 data block과 data bitmap이 일치하는가?
3. Inode link count
   • directory entry들이 가리키는 수와 inode의 link count가 맞는가?
4. Duplicated data block pointers
   • 같은 data block을 여러 inode가 동시에 가리키고 있지는 않은가?
5. Invalid data block pointers
   • inode가 존재하지 않는 block 번호를 가리키지는 않는가?
6. Superblock, inode, directories integrity
   • file system 전체 구조가 말이 되는가?

FSCK: Fixing Data Blocks

• 예를 들어 data bitmap은 block 5가 free라고 말하는데, 어떤 inode가 block 5를 가리킨다면?
• 둘 중 하나가 틀린 것이다.
• FSCK는 inode들을 scan해서 실제 참조되는 block 목록을 만들고, bitmap과 비교한다.
• 이 경우 보통 bitmap을 고쳐 block 5를 allocated로 표시할 수 있다.

반대로:

bitmap says: block 5 is allocated
no inode points to block 5

• 이 경우 block 5는 lost block이다.
• FSCK는 bitmap을 free로 고치거나 lost block 처리한다.

FSCK: Duplicated Data Block Pointer

• 두 inode가 같은 data block을 가리키는 경우도 있다.
• 이것은 심각한 inconsistency다.
• 한 file을 수정하면 다른 file 내용까지 망가질 수 있다.
• FSCK는 duplicated block pointer를 찾아서 한쪽을 복구하거나, 새 block을 할당해 복사하거나, 사용자 개입이 필요한 상태로 표시할 수 있다.

FSCK: Inode Link Count

• inode는 자신을 가리키는 hard link 수를 가지고 있다.
• directory tree를 scan하면 실제로 몇 개의 directory entry가 해당 inode를 가리키는지 알 수 있다.
• 이 경우 link count가 inconsistent하다.
• FSCK는 inode의 link count를 실제 directory entry 수에 맞게 고친다.

FSCK: Lost File

• 어떤 inode가 allocated되어 있고 data block도 가지고 있는데, directory entry가 하나도 없다면?
• 이 file은 이름이 없어서 일반 pathname으로 접근할 수 없다.
• 즉 lost file이다.
• FSCK는 이런 file을 /lost+found 아래 임시 이름으로 연결할 수 있다.
• 강의안도 lost file의 경우 /lost+found에 temporary file을 만든다고 설명한다.

/lost+found/tmp123 -> lost inode

FSCK의 장점

• 기존 file system 구조를 크게 바꾸지 않아도 된다.
• crash 이후 전체 scan을 통해 inconsistency를 찾아 고칠 수 있다.
• 단순하고 오래된 방식이다.
• 실제로 어떤 metadata가 틀렸는지 사후적으로 확인할 수 있다.

FSCK의 문제점

• 가장 큰 문제는 너무 느리다는 것이다.
• 전체 directory tree와 block pointer를 scan해야 한다.
• disk가 커질수록 시간이 매우 오래 걸린다.
• 강의안은 fsck가 5 phases를 거치고, 600GB disk를 fsck하는 데 약 70분이 걸릴 수 있다고 설명한다.
• 또한 FSCK는 file system 구조를 아주 잘 알아야 한다.
• 무엇이 “올바른 상태”인지는 모른다.
• 단지 모순되지 않는 “consistent state”로 고칠 뿐이다.

예를 들어:

• 사용자는 append가 성공했다고 생각했을 수 있다.
• 하지만 crash 후 FSCK는 append 이전 상태로 정리할 수도 있다.
• 즉 FSCK는 semantic correctness를 보장하지 않는다.
• file system이 구조적으로 말이 되게 만들 뿐이다.

Journaling

• FSCK의 느린 문제를 해결하기 위해 나온 대표적 방식이 journaling이다.
• Journaling은 database의 write-ahead logging과 같은 아이디어다.
• 핵심은 다음과 같다.

실제 위치에 update를 쓰기 전에, 어떤 update를 할 것인지 journal area에 먼저 기록한다.

• journal은 disk의 별도 영역이다.
• file system은 metadata/data update를 곧바로 최종 위치에 쓰지 않고, 먼저 log에 남긴다.
• journal이 안전하게 disk에 기록된 뒤에야 실제 위치에 update한다.
• 강의안도 journaling을 on-disk data structure의 change를 journaling area에 기록하고, journal이 safely written 된 후 final location에 checkpoint한다고 설명한다.

Write-Ahead Logging

• Write-ahead logging의 기본 원칙은:

Before writing actual update,
first write the log describing the update.

• crash가 나도 log를 보고 판단할 수 있다.
  • commit 전 crash: journal을 버린다.
  • commit 후 crash: journal을 기반으로 redo한다.
• 그래서 전체 file system을 scan할 필요가 없다.
• journal area만 보면 된다.
• 이 때문에 FSCK보다 recovery가 훨씬 빠르다.
• Ext3/4, ReiserFS, JFS, XFS, NTFS 등 현대 file system에서 사용된다.

Journaling: Appending Data Example

• 다시 data block Db를 append하는 예시를 보자.
• update해야 하는 것은 다음과 같다.

IN' : updated inode block
DB' : updated data bitmap block
Db  : new data block

• journaling에서는 이들을 먼저 journal에 쓴다.

Step 1: Journal Write

• journal area에 transaction 내용을 기록한다.
• 강의안 예시는 다음 block들을 journal에 쓴다.
  • journal header block TxB
  • updated inode block IN'
  • updated data bitmap block DB'
  • data block Db

Journal:
TxB(id=1) | IN' | DB' | Db

• 이 단계에서는 아직 final on-disk location에 update하지 않는다.
• 먼저 “나는 이런 update를 할 것이다”라는 기록을 남긴다.

Step 2: Journal Commit

• journal write가 끝나면 commit block을 쓴다.
• commit block은 보통 TxE로 표시된다.

Journal:
TxB(id=1) | IN' | DB' | Db | TxE(id=1)

• TxE가 있으면 이 transaction은 committed된 것이다.
• 즉 crash가 나더라도 이 update는 완료되어야 한다.
• TxE가 없으면 transaction은 committed되지 않은 것이다.
• recovery 때 버리면 된다.

Step 3: Checkpoint

• commit까지 끝난 뒤, journal에 있던 update들을 실제 final location에 쓴다.
• 이것을 checkpointing이라고 한다.

Final locations:
inode block <- IN'
data bitmap block <- DB'
data block <- Db

• checkpoint가 끝나면 journal space는 다시 재사용할 수 있다.

Recovery Case 1: Crash between Journal Write and Commit

• Step 1은 진행되었지만 Step 2 commit이 끝나기 전에 crash가 난 경우다.
• commit block이 없으므로 transaction은 committed되지 않았다.
• recovery는 journal을 버린다.
• file system은 append 이전 상태로 rollback된다.
• 강의안도 journal write가 committed되지 않았으면 simply discard한다고 설명한다.

Recovery Case 2: Crash between Commit and Checkpoint

• commit block TxE까지는 쓰였지만, final location에 일부만 반영되다가 crash가 난 경우다.
• 이때는 final location이 어떤 상태인지 중요하지 않다.
• journal에 committed transaction 전체가 있으므로, recovery는 이를 다시 final location에 쓴다.
• 이를 redo logging 또는 roll-forward recovery라고 한다.
• 강의안도 crash between step 2 and 3에서는 어떤 metadata/data block이 실제로 update되었는지와 상관없이 journal data로 final location을 overwrite한다고 설명한다.

Rollback vs Roll-forward

• commit 전 crash:
  • transaction을 버린다.
  • append 이전 상태로 남긴다.
  • rollback에 가깝다.
• commit 후 crash:
  • journal을 보고 update를 다시 수행한다.
  • append 이후 상태로 만든다.
  • roll-forward 또는 redo recovery다.

No TxE  -> discard journal
Has TxE -> redo journal

Why Journaling Works

• journaling의 핵심은 commit block이 transaction의 기준점이 된다는 것이다.
• commit block이 없으면:
  • incomplete transaction
  • 반영하지 않음
• commit block이 있으면:
  • complete transaction
  • 반드시 final location에 반영
• 그래서 crash 후에는 항상 둘 중 하나가 된다.

old consistent state
or
new consistent state

• 중간의 inconsistent state를 피할 수 있다.

Optimizing Journaling

• journaling은 안정성을 높이지만 overhead가 있다.
• 같은 데이터를 journal에 한 번, final location에 한 번 쓸 수 있기 때문이다.
• 그래서 여러 optimization이 쓰인다.

Circular Log

• journal area를 circular log처럼 사용한다.
• transaction이 checkpoint까지 끝나면 그 journal space를 free로 표시하고 재사용한다.

[Tx1][Tx2][free][free]
checkpoint Tx1
-> [free][Tx2][free][free]

• journal 공간을 계속 새로 잡는 것이 아니라 원형 buffer처럼 돌려 쓴다.

Batching Log Updates

• 여러 update를 하나의 global transaction으로 묶는다.
• 예를 들어 몇 초 동안 발생한 여러 file system update를 모아서 journal에 쓴다.
• 강의안은 Ext3/4에서 5초 단위 batching 예시를 언급한다.
• 장점:
  • journal write 횟수를 줄인다.
  • 성능이 좋아진다.
• 단점:
  • commit 전 crash가 나면 최근 몇 초의 update가 사라질 수 있다.

Journal Checksums

• journal block들이 제대로 쓰였는지 checksum으로 확인한다.
• commit block과 journal contents 사이의 write ordering 부담을 줄일 수 있다.
• 즉 journal이 찢겨 쓰이거나 부분적으로 손상된 경우를 감지할 수 있다.

Metadata Journaling

• 모든 data와 metadata를 journal에 쓰면 안정성은 좋지만 너무 비싸다.
• 그래서 많은 file system은 metadata만 journal에 기록한다.
• 이를 metadata journaling이라고 한다.
• metadata consistency는 보장하지만, file data 내용까지 항상 최신이라고 보장하지는 않는다.
• 예:
  • inode
  • bitmap
  • directory block 같은 metadata는 journal에 넣는다.
  • 실제 file data는 journal에 넣지 않을 수 있다.

Ordered Journaling

• Metadata journaling에서 문제가 될 수 있는 상황:
  • inode가 새 data block을 가리키도록 metadata는 commit되었는데,
  • 정작 data block 내용은 아직 disk에 쓰이지 않았다면,
  • crash 후 garbage data를 파일 내용으로 볼 수 있다.
• 이를 막기 위해 ordered journaling은 data block을 먼저 disk에 쓰고, 그 다음 metadata journal commit을 한다.
• 강의안도 Ext3/4의 ordered journaling은 metadata가 garbage를 가리키지 않도록 data write를 journal commit 전에 강제한다고 설명한다.

1. write data block Db to final location
2. write metadata to journal
3. commit journal
4. checkpoint metadata

• 이렇게 하면 metadata가 가리키는 data block에는 최소한 새 data가 존재한다.

Data Journaling vs Metadata Journaling

FSCK vs Journaling

시험에서 자주 나오는 포인트

1. disk는 multi-block update를 atomic하게 보장하지 않는다
   • system call 하나가 여러 disk write를 필요로 할 수 있다.
   • crash가 중간에 나면 일부만 반영된다.
2. inode와 bitmap이 서로 모순되면 inconsistent
   • inode는 block을 가리키는데 bitmap은 free라고 하면 위험하다.
   • bitmap은 allocated인데 inode가 안 가리키면 space leak다.
3. data only write는 구조적으로는 OK
   • 아무도 그 block을 가리키지 않고 bitmap도 free라면 file system metadata는 모순되지 않는다.
4. inode + bitmap only는 metadata consistent지만 data는 garbage일 수 있다
   • metadata consistency와 data correctness를 구분해야 한다.
5. FSCK는 전체 scan이라 느리다
   • file system이 클수록 오래 걸린다.
   • correct state가 아니라 consistent state로 고친다.
6. Journaling은 write-ahead logging
   • final location에 쓰기 전에 journal에 먼저 쓴다.
7. Commit block이 기준이다
   • commit block 없으면 discard
   • commit block 있으면 redo
8. Checkpoint는 journal 내용을 실제 위치에 반영하는 것
   • commit 이후 final location에 update한다.
9. Ordered journaling
   • data를 먼저 쓰고 metadata journal commit을 한다.
   • metadata가 garbage data를 가리키는 것을 막는다.