1. Redundancy

---

1. File System Redundancy

File System은 어느정도의 중복된 데이터를 포함하고 있습니다.

• superblock : file system에 있는 전체 block의 개수를 저장하고 있음 (N개)
• inode : data block을 가리키는 포인터를 포함하고 있음

이 정보들은 중복되었지만, 이를 통해 N번째 포인터나 그 이후의 포인터는 invalid하다는 것을 알 수 있습니다.

2. 특징

1. 장점
이러한 redundancy를 통해 reliability를 높일 수 있습니다.

또한, Raid 미러링을 통해 읽기 속도를 개선하거나, FS의 bitmap 등을 통해 look up을 수행하며 performance가 향상되기도 합니다.

2. 단점
그러나, 이러한 데이터들로 인해 consistency 이슈가 발생하기도 합니다.

2. Consistency Challenging

---

1. Crash Consistency

File system가 2개의 redundant block에 data를 작성하는 상황을 가정해봅시다. 그런데 1개의 block에만 write했는데, 갑자기 예상치 못한 interrupt가 발생했습니다.

결과적으로 한 block은 다른 값이 저장되었고, 또 다른 block은 기존 데이터로 남아있어 inconsistent한 state가 되었습니다.

둘 중 어느 block의 데이터가 옳은 것인지 어느 기준을 가지고 판단해야 할까요?
또한 어떻게 disk의 상태를 되돌려야 할까요?

2. Senario

먼저, crash 시나리오를 바탕으로 consistent / inconsistent state를 구분해봅시다.

File System이 새로운 데이터를 write하려고 합니다.

1. inode
2. data bitmap
3. data block

이 세 가지를 모두 업데이트하려는데 중간에 Crash가 발생했습니다. 어느 데이터를 갱신했을 때 어떤 상황이 되는지 알아보겠습니다.

1. bitmap만 disk에 썼을 때

• data block은 작성되지 않았는데 bitmap만 갱신됨 -> data loss
• 해당 block은 이미 bitmap이 작성되었기 때문에 재사용도 불가함 -> space leak

-> inconsistent

2. data block만 disk에 썼을 때

• FS입장에서는 아무 일도 일어나지 않았음
• inode는 작성되지 않았으므로, 해당 data block에 나중에 다른 값으로 덮어씌워질 수도 있음 -> data loss

-> consistent

3. inode만 disk에 썼을 때

• data block은 작성하지 않았으므로, 이상한 다른 garbage를 가리키게 됨
• bitmap을 작성하지 않았으므로, 다른 inode와 중복 할당이 일어날 수도 있음

-> inconsistent

4. bitmap + data block만 disk에 썼을 때

• block loss

-> inconsistent

5. bitmap + inode만 disk에 썼을 때

• data block을 남이 덮어서 작성할 수는 없음
• 그러나 data를 작성하지 않았으므로 garbage를 가리키게 됨
  

-> consistent

6. data block + inode만 disk에 썼을 때

• data bitmap을 작성하지 않았으므로, data block을 다른 파일이 나중에 덮어씌울 수도 있음 -> data loss

-> inconsistent

결과적으로, bitmap, inode를 동시에 갱신하거나 둘 다 갱신하지 못했다면 consistent합니다.

둘 중 하나만 갱신했다면 inconsistent하며, data block은 다시 갱신하면 되기 때문에 중요하지 않습니다.

3. Inconsistent State

위의 시나리오에서 확인할 수 있는 inconsistent state는 다음과 같습니다.

1. inode가 bitmap에 의해 할당되지 않은 잘못된 block을 참조
   inode만 갱신된 경우 → 3, 6
   
2. 사용되지 않은 data block에 bitmap을 할당
   bitmap만 갱신된 경우 → 1, 4

이러한 문제를 해결하기 위해, 파일의 갱신은 atomic하게 이루어져야 하며, Crash Consistency 문제를 해결하기 위해 OS는 fsck, journaling 등의 방법을 이용합니다.

3. fsck

---

fsck는 inconsistent state를 발견하고 고치는 도구입니다.

1. Strategy

• crash 이후에 전체 disk를 scan하며 고칠 수 있으면 고침
• FSCK가 완료될 때까지 offline 상태로 두어야 함

2. 동작 원리

fsck의 동작 원리는 다음과 같습니다.

• Superblock 내용 오류 검사
  • FS의 크기보다 superblock에 정의된 전체 블락의 개수가 더 큰지 확인
• Free block 검사
  • inode block, indirect block 등 검사
  • 기존 bitmap과 일치하지 않으면 inode 정보를 기반으로 block bitmap을 재구성
• inode 검사
  • 각 inode의 손상 여부 확인
  • 해결 불가하면 inode 초기화 + inode bitmap 갱신
• inode reference count 검사
  • root부터 탐색해 연결된 링크 개수를 수집
  • 수집한 개수와 저장된 개수가 다르면 inode 갱신
  • 할당된 inode는 있으나 참조하는 디렉토리가 없을 경우 /lost+found 디렉토리에서 찾음
• duplicate 검사
  • 중복된 포인터, 동일한 data block을 가리키는 다른 inode가 있는지 확인함
• bad pointer 검사
  • 포인터 목록을 스캔하며 함께 수행
  • bad : 해당 포인터가 유효하지 않은 공간을 참조하고 있음
• directory 검사
  • 파일의 내용은 확인하지 못하나 dir의 내용은 확인할 수 있음
  • 첫 항목이 ‘.’ , ‘..’인지, inode가 할당되어 있는지 확인

3. 특징

fsck는 개념적으로 간단하며, fix를 위한 별도의 writing overhead가 적습니다.

그러나, 모든 inconsistent state를 해결하지 못한다는 한계가 있습니다. fsck는 Metadata간의 일치를 목적으로 하기 때문에, 시나리오의 2, 5번과 같은 garbage data를 읽는 문제는 해결하지 못합니다.

또한, 속도가 느리고 file system에 대한 많은 지식이 요구된다는 단점이 있습니다.

4. journaling

---

1. Strategy

journaling은 file system 자체에 도입된 메커니즘으로, crash 이후 recovery 작업을 수행해 correct state로 되돌리는 것을 목적으로 합니다.

journaling의 주요 전략은 다음과 같습니다.

1. 디스크에 모든 새로운 데이터가 안전하게 저장되기 전까지는 기존 데이터를 절대 삭제하지 않음
2. redundancy로 인해 발생한 문제를 해결하기 위해 redundancy를 추가함

2. 기본 동작 원리

block 0에 10, block 1에 5를 write하는 상황을 가정해봅시다.

이 때, FS는 disk에 바로 data를 작성하지 않고, extra block에 data를 작성합니다. 그리고 valid bit을 이용해 모든 변경사항이 모두 extra에 작성되었는지를 표시합니다.

이러한 상황에서 crash가 났을 때,

valid bit이 0이라면, 아직 모든 변경사항이 extra에 작성되지 않은 상태이므로, 기존 disk에 있는 데이터로 롤백합니다.

반대로 valid bit이 1이라면, 모든 변경사항이 extra에 작성된 상태이므로 extra의 데이터로 롤백하면 됩니다.

실제 FS에서는 extra block, valid bit이 아닌 아래와 같은 명칭으로 불립니다.

terminology	description
journal	extra blocks
journal transaction	journal에 data를 write하는 행위
journal commit block	마지막에 위치하는 valid bit 역할을 하는 block

3. Optimization

위와 같은 간단한 journaling system이 존재한다고 가정해봅시다. 이 때, 이 system의 성능을 높이기 위해 어떤 최적화가 필요한지 하나씩 살펴봅시다.

1. Small journal size

data block이 N개일 때, 저널링을 위해 N+1개만큼의 블락이 추가로 필요합니다. 때문에, 최악의 경우 bandwidth가 1/2가 되어 성능이 저하됩니다.

• journal block size = N
• journal commit block = 1

이를 해결하기 위해, 아래와 같은 방식으로 변환할 수 있습니다.

저널의 크기를 줄이고 디스크에는 업데이트 된 데이터만 기록하자

트랜잭션마다 헤더를 생성하고 헤더에 데이터를 작성할 블락의 번호를 저장합니다. 이후, 헤더를 기반으로 disk에 실제 위치에 데이터를 작성하면 됩니다.

이 때, 저널에 있는 데이터를 실제 위치에 작성하는 행위를 check point라고 합니다.

위의 내용을 바탕으로 4번 블락에 C, 6번 블락에 D를 작성하는 상황을 가정했을 때, 아래와 같이 동작합니다.

1. 처음 commit block은 0
   

2. 9번 block(header)에 4, 6이라는 block 위치 작성 + 저널링 완료했으므로 commit block 1 표시
   

3. 실제 4, 6번 block에 데이터를 작성하고 commit block 0 표시
   

2. Barriers

4번 블락에 C, 6번 블락에 D를 작성할 때 어떤 작업이 수반되어야 하는가
1. 9번 : 헤더 읽어서 위치 확인
2. 10번, 11번 : 어떤 데이터 읽을지 확인
3. 12번 : commit 블락 확인
4. 4번 : 데이터 작성
5. 6번 : 데이터 작성
6. 12번 : commit 블락 확인

위와 같이 지금까지의 방식은 write order이 random write를 야기해서 비효율적입니다.

따라서, random write 횟수를 줄이기 위해, 쓰기 작업을 그룹화해 sequential write를 유도하고자 합니다.

barrier을 세워, 저널이 꽉 차지 않아도 조건을 만족하면 check point를 수행합니다. check point를 수행하는 Key point, 즉 barrier을 세우는 조건은 다음과 같습니다.

1. journal commit 전
   • journal transaction entry 완료 ~
   • 9, 10, 11번
2. checkpoint 전
   • journal commit 완료 ~
   • 12번
3. journal을 free하기 이전
   • check point 완료 ~
   • 4, 6번

3. Checksums

2번의 내용대로라면, 9, 10, 11 | 12 | 4, 6 | 12 순서대로 실행됩니다.
이 때, 11, 12 사이의 barrier를 없앨 수 없을까요?

이를 위해 앞선 트랜잭션의 내용을 요약한 check sum을 만들어 commit block에 기록하는 방법이 도입됩니다.

12번 블락에 9, 10, 11에 대한 check sum이 들어가는거죠.

checksum 기반 복구 검증 로직
1. commit block 읽어 check sum 값 확인
2. 해당 트랜잭션의 내용인 블락의 내용 읽고 check sum 재계산
3. 두 check sum이 일치할 경우, 트랜잭션은 유효함
4. 일치하지 않을 경우, 문제가 있으니 해당 트랜잭션 무시 및 롤백

4. Circular journal

앞선 내용들로 보았을 때, 저널링은 sequential하지만 checkpoint는 random합니다. 따라서, 성능 개선을 위해 checkpoint 시점을 뒤로 미루어 한 번에 write하고자 합니다.

circular buffer를 도입해, 디스크에서 check point가 발생하기 전까지 데이터를 메모리에 저장해둡니다.

• 오래된 저널부터 checkpoint 수행, 해당 공간은 재사용
  • head : 새로운 트랜잭션이 저장되는 위치
  • tail : 가장 오래된 트랜잭션의 위치
• 동작원리
  • 새로운 데이터가 오면 head를 늘려서 메모리에 저장
  • 백그라운드에서 tail에 있는 데이터를 틈틈이 checkpoint 수행 후 tail을 앞으로 당김
  • head가 tail을 따라잡으면 disk에 공간이 없으니 checkpoint 수행해 공간 확보

5. Logical Logging

지금까지의 내용은 physical logging입니다.

블락의 변경된 실제 내용이 아니라 연산이나 명령어를 기록하는 logical logging 방법이 등장합니다. 트랜잭션의 시작(TxB), 끝(TxE)에 identifier 표시를 함께 남겨 중복 연산을 수행하지 않도록 합니다.

logical logging 기반 복구 검증 로직
로그를 읽고 해당 연산부터 다시 실행하면 됨

• 현재 트랜잭션 identifier가 로그의 번호보다 크다면
  → 이미 실행한 연산이므로 무시
• 작다면
  → crash로 인해 수행하지 못한 연산이므로, 해당 연산 실행

4. Journaling 종류

1. Data Journaling

필요한 모든 정보를 기록하는 방식입니다. 지금까지의 내용은 data journaling 방식입니다.

그러나, data를 저널에 기록하고 또 블락에 기록하기 때문에 기록을 두 번 수행한다는 문제점이 있습니다.

2. Metadata Journaling

1번과 다르게 meta data만 저널링해서 중복 기록을 피하는 방식입니다. 속도는 빠르나 data block의 복구가 안될수도 있습니다.

해당 방식은 option으로 두 방식을 선택할 수 있습니다.

1. ordered journaling

• default
• 데이터가 완전히 작성된 이후에야 meta data를 기록함
• 동작원리
  1. 실제 데이터를 실제 위치에 작성함
  2. 데이터가 모두 작성된 것이 확인되면 메타 데이터를 저널링하고 commit함
  3. 나중에 check point를 수행해 메타 데이터를 disk에 작성함
• 장점
  • crash가 나도 garbage value가 없음
  • meta data가 가리키는 곳에는 유효한 데이터가 저장되어 있음
• 단점
  • 시간이 오래 걸림

2. writeback journaling

• 동작원리
  1. 메타 데이터 저널링
  2. 실제 데이터는 시간 날 때 disk에 작성함
  3. check point 수행해 메타 데이터 disk에 작성함
• 장점
  • ordered journaling에 비해 시간이 빠름
• 단점
  • crash가 났을 때 garbage value가 있을 수 있음

5. Example

위의 내용을 기반으로 현재 가장 많이 사용되는 metadata journaling + ordered 방식의 저널링 예시를 간단하게 살펴보겠습니다.

사용자는 example.txt라는 파일을 작성하려고 한다고 가정합니다.

1. 트랜잭션 시작
   • 이 작업을 하나의 트랜잭션으로 묶음
2. 데이터 쓰기
   • 실제 파일의 내용을 disk에 작성함
   • 작성이 완료될 때까지 대기 (barrier)
3. meta 데이터 저널링
   • inode N번을 생성 / 파일 명은 example.txt / data block은 100~102번
4. 저널 커밋
   • 저널에 commit block을 씀
5. checkpoint
   • 나중에 저널에 적힌 meta data를 disk에 옮겨 적음

이러한 상황에서 write 도중 crash가 발생할 경우 각 케이스에 따른 복구 과정과 결과는 다음과 같습니다.

Crash 1 : 데이터 쓰기 도중 Crash 발생

• 복구
  • 저널을 확인함
  • 저널 커밋이 없으므로 해당 트랜잭션은 완료되지 않은 것으로 간주함
  • 따라서 해당 트랜잭션을 무시함
• 결과
  • 파일 유실
  • 그러나 consistent함

Crash 2 : 메타 데이터 저널링 후 저널 커밋 도중 Crash 발생

• 복구
  • 1번 예시와 동일하게 저널 커밋이 없으므로 무시

Crash 3 : 저널 커밋 이후 Crash 발생

• 복구
  • 저널을 확인함
  • 저널 커밋이 있으므로 저널의 메타데이터를 disk에 다시 작성함
• 결과
  • data는 이미 작성되었고, 메타 데이터를 올바르게 옯겨 써서 파일을 안전하게 복구할 수 있음