Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

파일 시스템은 파일, 디렉토리, 메타데이터 등의 추상화를 구현하기 위해 자료구조들을 관리한다. 대부분의 자료구조들과 달리 파일 시스템 자료구조는 영구적이어야 한다.

파일 시스템이 다뤄야 할 주된 문제 중 하나는, 전원 손실과 시스템 충돌이 발생할 수 있음에도 어떻게 그런 영구적 자료구조를 갱신할 수 있느냐 하는 것이다. 구체적으로, 만약 디스크 상의 구조를 업데이트하는 도중에 누군가 전원 코드를 뽑아버리면 무슨 일이 일어날까? 혹은 운영체제가 버그와 충돌을 마주하는 경우에는 어떨까? 전원 손실과 충돌 때문에 영구적 자료 구조의 업데이트는 상당히 까다로워질 수 있다. 이는 충돌-일관성 문제(crash-consistency problem)라 불리는, 파일 시스템 구현의 흥미로운 문제로 이어진다.

특정 연산을 완료하기 위해 두 개의 디스크 상 구조 $A$, $B$를 업데이트해야 한다고 해보자. 디스크는 한 번에 하나의 요청만 처리하므로, 이 두 요청들 중 하나는 디스크에 먼저 도달한다. 만약 해당 쓰기가 완료한 직후 시스템 충돌이나 전원 손실이 일어나는 경우, 디스크 상 구조는 비일관적인 상태로 남게 된다.

두 쓰기 작업 사이에서 시스템 충돌이나 전원 손실이 일어날 수 있고, 그 경우 디스크 상 상태는 부분적으로만 업데이트 된다. 충돌이 일어난 후 시스템이 부팅되고 파일 시스템을 다시 마운트한다고 해보자. 충돌이 임의의 시점에서 일어날 수 있다면, 어떻게 파일 시스템은 디스크 상 상태가 적절한 상태로 유지할 수 있을까?

이 장에서는 이 문제에 대해 자세하게 알아보고, 파일 시스템이 이를 극복하기 위해 사용한 여러 방법들을 살펴볼 것이다. 가장 먼저 파일 시스템 체커(file system checker, fsck)라 불리는, 오래된 파일 시스템들이 취했던 방법을 알아볼 것이다. 이후로는 각 쓰기에 약간의 오버헤드를 더하기는 하지만 충돌이나 전원손실이 일어났을 때 더 빠르게 복구할 수 있는 저널링(journaling) 기술에 대해 알아본다.

1. A Detailed Example

저널링에 대해 알아보기 위해 우선은 예시를 한 번 살펴보자. 일단은 디스크 상 구조를 업데이트하는 워크로드가 필요하다. 여기서는 이미 있는 파일에 하나의 데이터 블럭을 추가하는, 간단한 워크로드를 가정한다. 이는 파일을 열고, lseek()으로 파일 오프셋을 파일의 끝으로 움직이고, 하나의 4KB 쓰기 요청을 보내고, 파일을 닫음으로써 이루어진다.

또한 여기서는 표준적인 간단한 파일 시스템 구조를 사용한다고 가정한다. 이는 아이노드 비트맵(한 아이노드 당 1비트, 총 8비트), 데이터 비트맵(한 데이터 블럭당 1비트, 총 8비트), 아이노드(0에서 7까지 총 8개. 네 블럭에 퍼져있음), 데이터 블럭(0에서 7까지 총 8개)로 이루어져있다. 아래는 이 파일 시스템의 다이어그램이다.

하나의 아이노드(2번)가 할당되어 있고, 아이노드 비트맵에도 표시되어 있다. 한 데이터 블럭도 할당되어 있고, 이 또한 데이터 비트맵에 표시되어있다. 아이노드는 I[v1]으로 표기되어 있는데, 이는 해당 아이노드가 첫 번째 버전임을 가리킨다.

I[v1]의 내부를 살펴보면 다음과 같다.

이 단순화된 아이노드에서, 파일의 size는 1(한 블럭)이고, 첫 번째 직접 포인터는 블럭 $4$를 가리키고 있다. 나머지 세 직접 포인터들은 null로 설정되어 있다. 물론 실제 아이노드는 더 많은 필드들을 가진다.

파일에 새 데이터 블럭을 추가하기 위해서는 세 개의 디스크 상 구조를 업데이트해야 한다. 아이노드, 새 데이터 블럭(Db), 그리고 데이터 비트맵(B[v2]라 하자)이다.

그러므로 시스템 메모리 내에는 디스크에 써야할 세 블럭들이 있는 것이다. 업데이트된 아이노드는 이제 다음과 같다.

업데이트된 데이터 비트맵(B[v2])은 00001100이 된다. 데이터 블럭 Db에는 사용자가 파일에 넣고 싶은 어떤 내용이든지 넣어서 저장될 것이다.

이렇게 업데이트가 끝나고 난 후의 파일 시스템은 다음과 같을 것이다.

이와 같은 상태가 되기 위해, 파일 시스템은 세 별개의 디스크 쓰기를 수행해야 한다. 다만 이 쓰기들이 보통 사용자가 write() 시스템 콜을 호출할 때, 즉시 일어나는 것은 아니라는 것을 염두에 두자. 아이노드, 비트맵, 데이터의 변경 사항은 일단은 디스크에 쓰이지 않은 상태로 메인 메모리에 있다가, 파일 시스템이 디스크에 쓰기로 결정할 때, 그제서야 디스크에 쓰이게 된다. 불행하게도 이때 시스템 충돌이 일어날 수 있고, 이러한 디스크 업데이트를 방해할 수도 있다. 특히 이 쓰기들 모두가 아니라 그 일부만 완료된 후 시스템 충돌이 발생하면, 시스템은 이상한 상태로 남게 된다.

Crash Scenarios

충돌 시나리오 하나를 예로 들어보자. 오직 하나의 쓰기만 성공했다고 생각해보자. 이 경우 세 가지의 가능한 결과가 있다.

• Db만 쓰임
  + 데이터는 디스크에 있지만, 이를 가리키는 아이노드와, 이것이 할당되었다 말해주는 데이터 비트맵은 업데이트 되어 있지 않게 된다. 이는 쓰기가 전혀 일어나지 않은 것과 같다. 파일 시스템의 충돌-일관성의 측면에서는 문제가 되지 않는다.
• 아이노드만 쓰임
  + 이 경우 아이노드는 Db가 쓰였어야 할 디스크 주소를 가리키지만 Db에는 데이터가 없다. 만약 아이노드를 믿고 사용하는 경우, 해당 주소에 있는 쓰레기값을 불러 읽게 될 것이다.
  + 파일 시스템 비일관성(file-system inconsistency)이라 불리는 새로운 문제가 일어난다. 디스크 상의 비트맵은 5번 데이터 블럭이 아직 할당되지 않았다고 말하지만, 아이노드는 해당 블럭이 할당되었다고 말한다. 비트맵과 아이노드 사이에 비일관성이 발생하는 것이다. 파일 시스템을 사용하고자 한다면 이 문제를 어떻게든 해결해야만 한다.
• 데이터 비트맵만 쓰임
  + 데이터 비트맵은 5번 블럭이 할당되었다고 말하지만, 이를 가리키는 아이노드는 없다. 파일 시스템은 또 비일관적인 상태가 된다. 이 문제는 해결되지 않으면 공간 누수(space leak)로 이어진다. 파일 시스템은 5번 블럭을 다시는 쓰지 않게될 것이기 때문이다.

이번에는 두 개의 쓰기가 성공하고, 하나는 실패하는 경우를 살펴보자.

• Db에만 안 쓰임
  + 파일 시스템 메타데이터는 일관적이다. 아이노드도 5번 블럭을 가리키고, 비트맵도 5번 블럭이 할당되었다고 말하기 때문이다. 문제는 해당 블럭에 쓰레기값이 담겨있다는 것이다.
• 비트맵에만 안 쓰임
  + 아이노드는 제대로 가리키고 있지만, 비트맵은 그렇지 않다. 아이노드와 비트맵 사이에 비일관성이 발생한다.
• 아이노드만 안 쓰임
  + 이 경우에도 아이노드와 데이터 비트맵 사이에 비일관성이 발생한다. 데이터 블럭과 비트맵에는 정보가 들어가 있지만, 어떤 아이노드도 해당 파일을 가리키지 않는다.
  

The Crash Consistency Problem

이 시나리오들로부터 충돌로 인해 일어날 수 있는 많은 문제들을 볼 수 있다. 파일 시스템 자료 구조에 비일관성이 일어날 수 있고, 공간 누수가 일어날 수 있다. 사용자에게 쓰레기 데이터를 반환할 수도 있다. 이상적으로는 파일 시스템을 원래의 일관적인 상태에서 다른 일관적인 상태로, 원자적으로 바꿀 수 있어야 한다. 하지만 이는 쉬운 일이 아니다. 디스크는 한 번에 하나의 쓰기만 처리할 수 있고, 충돌이나 전원 손실은 이 업데이트들 사이에서 일어날 수도 있기 때문이다. 이 일반적인 문제를 가리켜 충돌-일관성 문제(혹은 일관적-갱신 문제)라 부른다.

2. Solution #1: The File System Checker

초기 파일 시스템들은 간단한 접근법을 취했다. 기본적으로 이들은 비일관적 상태를 허용하고, 나중에 이를 수정한다. 그 대표적인 예는 fsck다. fsck는 그런 비일관성을 찾고 수정하는 UNIX 툴이며, 다른 시스템들에도 비슷하게 디스크 파티션을 확인하고 고치는 툴들이 있다. 다만 이러한 방식이 모든 문제를 해결할 수는 없다는 것에 유의하자. 예를 들어, 파일 시스템은 일관적인 상태에 있지만 아이노드가 가리키는 것은 쓰레기 데이터인 경우를 생각해보자. 이 방식의 유일한 목적은 파일 시스템의 메타데이터가 내부적으로 일관적이게 만드는 것 뿐이다.

fsck는 여러 단계로 작업을 진행한다. fsck는 파일 시스템이 마운트되어 사용 가능해지기 전에 실행된다. 이 작업이 마치면 디스크 상 파일 시스템은 일관적이고 사용자들에게 접근 가능해진다. 다음은 fsck가 무엇을 하는지에 대한 요약이다.

• 슈퍼블럭 : fsck는 우선 슈퍼블럭이 제대로 되어있는지를 확인한다. 이 작업의 대부분은 파일 시스템의 크기가 할당된 블럭의 수보다 많은지를 확인하는 것 등의 sanity 체크다. 이러한 sanity 체크의 목적은 손상되었을 것으로 의심되는 슈퍼블럭을 찾는 것이고, 그 경우 시스템은 슈퍼블럭의 다른 복제본을 쓰도록 결정한다.
• 가용 블럭 : 다음으로 fsck는 아이노드, 간접 블럭, 이중 간접 블럭 등을 스캔해 현재 파일 시스템 내에 어떤 블럭들이 할당되어있는지를 파악한다. 이 정본느 할당 비트맵의 올바른 버전을 만들기 위해 사용된다. 만약 비트맵과 아이노드 사이에 비일관성이 있는 경우, 아이노드의 정보를 사용한다. 마찬가지의 확인이 모든 아이노드들에 대해서도 수행되어, 사용 중인 것 같은 아이노드들은 아이노드 비트맵에도 사용 중이라 표시된다.
• 아이노드 상태 : 각 아이노드는 손상 등의 문제가 있는지 검사 받는다. 예를 들어 fsck는 각 할당된 아이노드가 유효한 타입 필드를 가지고 있는지를 확인한다. 만약 아이노드 필드에 쉽게 고칠 수 없는 문제들이 있다면, 해당 아이노드는 잘못된 것으로 생각되어 fsck에 의해 비워진다. 그에 상응하는 아이노드 비트맵도 업데이트 된다.
• 아이노드 링크 : fsck는 각 할당된 아이노드의 링크 카운트도 검증한다. 링크 카운트는 이 특정 파일에 대한 참졸를 가지는 서로 다른 디렉토리의 수를 말한다. 이를 검증하기 위해 fsck는 루트 디렉토리부터 시작해 전체 디렉토리 트리를 스캔하고, 파일 시스템 내의 모든 파일 및 디렉토리에 대해 링크 카운트들을 만든다. 만약 새로 계산한 카운트와 아이노드 내에 있는 것이 서로 맞지 않는다면, 수정 작업이 일어나야 한다. 보통은 아이노드 내의 카운트를 수정한다. 만약 할당된 아이노드가 발견되었지만 어떠한 디렉토리도 이를 참조하고 있지 않다면, 이는 lost+found 디렉토리로 옮겨진다.
• 중복 : fsck는 중복 포인터들, 즉 서로 다른 두 아이노드가 같은 블럭을 참조하는 경우도 확인한다. 만약 한 아이노드가 명백히 좋지 않다면, 이는 비워진다. 혹은 가리켜지는 블럭이 복사되어 각 아이노드가 서로 다른 블럭을 가리키게 할 수도 이다.
• 배드 블럭 : 배드 블럭 포인터들에 대한 체크는 모든 포인터들의 리스트를 스캔할 때 수행된다. 포인터는 자신이 가리킬 수 있는 유효 범위 밖에 있는 것을 가리킬 때, "나쁜 것"으로 생각된다. 이 경우 fsck는 해당 포인터를 아이노드나 간접 블럭으로부터 삭제한다.
• 디렉토리 확인 : fsck는 사용자 파일의 내용에 대해서는 알지 못한다. 하지만 디렉토리는 파일 시스템 자신이 만든, 구체적으로 형식화된 정보를 가지고 있다. 그러므로 fsck는 각 디렉토리의 내용들에 대한 추가적인 무결성 확인을 수행해, ".", ".."이 가장 앞의 엔트리인지, 디렉토리 엔트리에 할당된 각 아이노드들이 할당되어 있는지를 확실히 하고, 어떤 디렉토리도 전체 계층 구조에서 한 번보다 많이 링크되지 않음을 보증한다.

fsck 제작은 파일 시스템에 대한 복잡한 지식을 필요로 한다. 하지만 fsck 및 그와 유사한 방법들에는 그보다 큰, 그리고 아마 더 근본적인 문제점이 있다. 너무 느리다는 것이다. 아주 큰 디스크 볼륨의 경우, 할당된 모든 블럭들을 찾고 전체 디렉토리 트리를 읽기 위해 전체 디스크를 스캔하는 것은 수 분에서 수 시간이 걸릴 수 있다. fsck의 성능은 디스크의 용량이 커지고 RAID 사용이 보편화되면서 극심하게 좋지 않아졌다.

높은 수준에서 fsck의 기본 전제도는 좀 비이성적인 것처럼 보인다. 위의 예를 다시 한 번 보자. 세 블럭만이 디스크에 쓰인다. 고작 세 블럭의 업데이트 동안 일어날 수 있는 문제들을 고치기 위해 전체 디스크를 스캔하는 것은 너무나도 비효율적이다.

3. Solution #2: Journaling (or Write-Ahead Logging)

일관적-갱신 문제에 대한 가장 보편적인 해결법은 아마 DBMS에서 사용하던 아이디어에 기반할 것이다. 로그 선행 기입(write-ahead logging, WAL)이라 불리는 이 아이디어는, 정확히 이러한 종류의 문제를 해결하기 위해 만들어졌다. 파일 시스템에서는 역사적인 이유로, 이를 보통 저널링(journaling)이라 부른다.

기본 아이디어는 다음과 같다. 디스크를 업데이트 할 때, 자료구조를 덮어쓰기 전에 먼저 무엇을 하려하는지에 대한 작은 노트를 남겨 놓는 것이다. 이러한 노트를 디스크에 씀으로써, 구조 업데이트 도중에 충돌이 일어나는 경우 그 전으로 돌아가, 노트를 보고, 원래 진행했어야 할 일을 재개할 수 있게 된다. 전체 디스크를 스캔하지 않고도, 무엇을 어떻게 고쳐야할지를 알 수 있는 것이다.

Linux ext3가 어떻게 저널링을 사용하고 있는지를 살펴보자. 대부분의 디스크 상 구조는 Linux ext2와 같다. 새로운 핵심 구조는 저널이며, 이는 파티션 또는 다른 장치 내의 작은 공간을 차지하고 있다. 저널링이 없는 ext2 파일 시스템은 다음과 같다.

저널이 동일한 파일 시스템에 위치한다고 한다면, ext3 파일 시스템은 다음과 같이 생겼다.

유일한 차이는 저널의 존재 여부와, 이것이 어떻게 쓰이는가 하는 것 뿐이다.

Data Journaling

데이터 저널링의 작동 방식에 대해 이해하기 위한 간단한 예제를 살펴보자. 앞서의 아이노드(I[v2]), 비트맵(B[v2]), 데이터 블럭(Db)을 디스크에 쓰려했던 예제를 다시 보자. 이것들을 최종 디스크 위치에 쓰기 전에 우선은 그것들을 로그에 쓴다. 로그에서는 다음과 같을 것이다.

여기에 다섯 개의 블럭을 썼음을 볼 수 있다. 트랜잭션 시작(TxB)은 파일 시스템의 미처리된 업데이트들에 대한 정보, 트랜잭션 식별자(TID) 등을 포함한 여러 정보들을 담고 있다. 중간의 세 블럭은 해당 블럭들의 바로 그 내용들을 담고 있다. 이를 물리적 로깅(physical logging)이라 부르는데, 저널에 업데이트될 바로 그 물리적인 내용들을 집어넣기 때문이다. 마지막 블럭(TxE)는 트랜잭션의 끝을 표시하기 위함이며, 이 또한 TID를 가지고 있다.

이 트랜잭션이 디스크에 쓰이고 나면 파일 시스템 내의 오래된 구조를 덮어 쓸 수 있게 된다. 이러한 과정을 가리켜 체크포인팅(checkpointing)이라 말한다. 파일 시스템을 체크포인팅하기 위해서는 I[v2], B[v2], Db를 위에서 본 디스크 위치에 쓰도록 요청해야 한다. 만약 이 쓰기 작업이 성공적으로 완료되면, 파일 시스템을 성공적으로 체크포인팅 한 것이다.

1. Journal Write: 트랜잭션 시작 블럭, 미처리 업데이트들, 트랜잭션 끝 블럭을 포함한 트랜잭션을 로그에 기록한다. 이 작업이 마치기를 기다린다.
2. Checkpoint: 미처리 메타데이터 & 데이터 업데이트를 파일 시스템 내 최종 위치에 쓴다.

위 예에서는 우선 TxB, I[v2], B[v2], Db, TxE를 저널에 쓴다. 이 쓰기가 완료되고 나면 이것들을 디스크 상 최종 위치에 체크포인팅 함으로써 업데이트를 마친다.

저널에 쓰는 도중에 충돌이 발생하는 경우는 좀 더 까다로울 수 있다. 여기서 우리는 트랜잭션 내 블럭들을 디스크에 쓰려고 한다. 이를 위해서는 간단하게, 한 번에 하나씩 요청을 보내고, 완료되기를 기다리고, 다음 요청을 보내는 방법을 사용할 수 있다. 하지만 이 방법은 느리다. 이상적으로는 다섯 블럭을 한 번에 쓰는 것이 좋을 것이다. 블럭을 하나씩 다섯 번 쓰는 것은 너무 느리기 때문이다. 하지만 이 방법은 안전하지 않다. 이런 큰 쓰기 작업이 있을 때, 디스크는 내부적인 스케줄링을 통해 큰 쓰기를 작은 조각들로 나눠 임의의 순서로 쓴다. 그렇기 때문에 디스크는 내부적으로 TxB, I[v2], B[v2], TxE를 우선 쓰고, 그러고 나서 Db를 쓸 수도 있다. 하지만 만약 그 사이에 전력 손실이 일어난다면 다음과 같은 결과로 이어질 것이다.

이게 왜 문제일까? 이 트랜잭션에는 서로 일치하는 TID를 가지는 트랜잭션 시작과 끝이 있다. 파일 시스템은 네 번째 블럭을 보고 이것이 잘못됐음을 알지 못하고 임의의 사용자 데이터로 판단한다. 그러므로 만약 시스템은 리부팅되고 복구를 진행될 때, 이 트랜잭션을 실행해 Db가 있었어야 할 위치의 쓰레기 블럭 "??"의 내용들을 복사해버리고 말 것이다. 만약 이러한 일이 슈퍼블럭 등, 파일 시스템의 핵심 부분에서 일어난다면 문제는 더 나빠진다.

이러한 문제를 피하기 위해, 파일 시스템은 트랜잭션 쓰기 요청을 두 단계로 진행한다. 먼저 TxE 블럭을 제외한 모든 블럭을 한 번에 저널에 쓴다. 이 쓰기가 끝나면 저널은 다음과 같이 생겼을 것이다.

이 쓰기 작업이 끝나면 파일 시스템은 TxE 블럭에 대한 쓰기 요청을 만들어, 저널을 최종의 안전한 상태로 만든다.

이 과정의 중요한 점은 디스크에 의해 제공되는 원자성 보장이다. 디스크는 512 바이트 쓰기에 대한 원자성을 제공하므로, TxE 쓰기가 원자적임을 보장하기 위해서는, 이 또한 하나의 512 바이트 블럭 안에 있어야 한다. 파일 시스템 업데이트의 현재 프로토콜은 다음과 같다.

1. 저널 쓰기 : 트랜잭션의 내용을 로그에 쓴다. 쓰기가 완료될 때까지 기다린다.
2. 저널 커밋 : 트랜잭션 커밋 블럭(TxE를 포함)을 로그에 쓴다. 완료되기를 기다린다.
3. 체크포인트 : 업데이트될 내용을 최종 디스크 상 위치에 쓴다.

Recovery

이제 어떻게 파일 시스템이 저널의 내용을 통해 시스템 충돌로부터 복구할 수 있는지에 대해 알아보자. 충돌은 이러한 업데이트 시퀀스의 어느 때에나 일어날 수 있다. 만약 충돌이 트랜잭션이 로그에 안전하게 쓰이기 전에 일어난다면 해야할 작업은 쉽다. 미처리 업데이트는 그냥 스킵된다.

만약 충돌이 트랜잭션이 로그가 커밋된 이후, 체크포인트 완료 전에 일어난다면, 파일 시스템은 다음과 같이 업데이트를 복구할 수 있다. 시스템이 부팅될 때, 파일 시스템 복구 프로세스는 로그를 스캔하고 디스크에 커밋된 트랜잭션들을 찾는다. 이 트랜잭션들은 순서대로 재생된다. 파일 시스템이 트랜잭션 내의 블럭들을 최종 디스크 위치에 쓰려고 하는 것이다. 이러한 방식은 redo logging이라 불리는 것으로, 가장 간단한 방식의 로깅들 중 하나다. 저널 내의 커밋된 트랜잭션들을 복구함으로써 파일 시스템은 디스크 상 구조가 일관적임을 보증한다.

체크포인팅 도중에는 언제든 충돌이 일어나도 괜찮다. 최악의 경우, 업데이트의 일부가 복구 과정 중에 다시 수행될 수도 있지만, 복구 자체가 드물게 일어나는 작업이므로, 적은 중복 쓰기 정도는 걱정할 만한 것이 아니다.