24.03.30 운영체제, PintOS

운영체제

32. 크래시 일관성 : FSCK와 저널링

• 여타 자료구조와는 다르게 파일 시스템의 자료구조는 안전하게 저장되어야 한다.
• 파일 시스템이 가진 가장 큰 어려움은 전력 손실이나 시스템 크래시가 발생하는 상황에서도, 어떻게 안전하게 디스크 상의 내용을 갱신하는 가에 대한 문제이다. 전력손실이나 크래시 때문에 디스크 상의 자료구조를 안전하게 갱신하는 것은 상당히 까다로운 작업이 된다. 파일 시스템은 크래시 일관성(crash - consistency)라는 새롭고 흥미로운 문제에 직면한다.
• 어떤 특정 작업을 위해 자료구조 A와 B를 갱신해야 한다고 했을 때 디스크는 한 번에 하나의 요청만 처리할 수 있기 때문에 두 요청 중 하나의 요청이 먼저 디스크에 도달할 것이다. 하나의 쓰기 작업만 완료한 상태에서 시스템의 전원이 나간 경우, 디스크 상의 자료구조는 일관성이 깨지게(inconsistent)가 된다.

32.1 예제

크래시 일관성 문제

• 크래시 때문에 파일 시스템 디스크 상의 자료구조에 많은 문제가 발생할 수 있다. 파일 시스템 자료구조간의 불일치가 있을 수 있으며, 공간 누수가 발생할 수 있고, 사용자에게 의미없는 데이터가 전달되는 등의 여러 문제가 있다. 우리는 파일 시스템의 일관성이 항상 유지되도록 만들고자 한다. 연산 이전의 상태에서 연산 이후의 상태로 이동할 때, 중간의 임시상태(transient state)로 파일 시스템이 남아있는 경우를 방지하는 것이 목적이다. 불행하게도 디스크는 한번에 하나의 쓰기 작업을 처리할 수 있으며 이러한 작업들 중간에 크래시나 전력 손실이 발생할 수 있어서 목적을 쉽게 달성할 수가 없다. 이러한 일반적인 문제를 크래시 일관성 문제라고 부른다.

32.2 해법 1 : 파일 시스템 검사기

• 초기의 파일 시스템은 기본적으로 파일 시스템이 일관성이 없더라도 그대로 두었다가 리부팅시에 일관성 문제를 해결하는 방식을 선택하였다. fsck는 일관성 불일치를 발견하고 수정하는 Linux의 도구다. 이 도구들의 목적은 파일 시스템 메타 데이터들 간의 일관성을 유지하는 것이다.
• fsck의 동작은 여러 단계로 구성되고 이것은 파일 시스템이 마운트 직전에 실행된다. 종료가 되면 디스크 상의 파일 시스템이 일관성을 갖게 되며 사용자가 사용할 수 있게된다.

fsck가 하는 기본적인 일

• 슈퍼블럭 : fsck는 먼저 슈퍼블럭 내용에 오류가 없는지를 검사한다. 대부분의 검사는 파일시스템에 블럭 개수가 파일시스템의 크기보다 더 큰지와 같은 기초 검사들로 이루어져있다.
• 프리블럭 : 그 다음으로 fsck는 아이노드와 간접 블럭등을 살펴보고 파일 시스템에 현재 어떤 블럭들이 할당되었는지에 대한 정보를 생성한다. 얻은 정보를 토대로 정확한 할당 비트맵을 재구성한다.
• 아이노드 상태 : 각 아이노드가 손상되었는지 다른 문제는 없는지 검사한다. 만약 아이노드 항목 중 쉽게 해결이 불가능한 문제가 존재하면, fsck는 해당 아이노드를 의심 대상으로 간주하고 초기화 한다. 아이노드 비트맵도 그에 따라 갱신한다.
• 아이노드 링크 : 각 할당된 아이노드의 링크 개수를 확인한다. 링크의 개수는 특정 파일에 대한 참조를 포함하고 있는 디렉터리들의 수를 나타낸다. 새롭게 계산된 개수와 아이노드에서 확인한 수와 다른 경우가 있다면 일반적으로 아이노드의 개수 필드를 고치는 방식으로 수정한다. 만약 할당된 아이노드는 있지만 어떤 디렉터리도 이를 참조하지 않는다면, 그 파일은 lost + found 디렉터리로 이동된다.
• 중복 : 중복된 포인터가 있는지 검사한다.
• 배드블럭 : 모든 포인터 목록을 검사하면서 배드블럭 포인터들도 함께 검사한다. 이와같은 경우 fsck는 다른 해결 방법이 없기 때문에 아이노드나 간접블럭에서 해당 포인터를 단순히 삭제한다.
• 디렉터리 검사 : fsck는 파일의 내용을 파악하는 것은 불가능하다. 하지만 디렉터리 내용에 대해서는 파일 시스템이 생성한 구체적이고 서식화된 정보가 있으므로 fsck는 각 디렉터리의 내용에 대해서는 추가적으로 모든 내용이 제대로 저장되어 있는지의 검사를 수행한다.
• fsck의 근본적인 문제는 너무 느리다는 것이다. 디스크의 용량이 커지고 RAID가 대중화 되면서 fsck는 실질적으로 사용이 불가능할 정도로 느리다.

32.3 해법 2 : 저널링(또는 Write-Ahead Logging)

• 파일 시스템에선 write-ahead logging을 역사적인 이유로 저널링(journaling)이라고 부른다.
• 기본 개념은 디스크 내용을 갱신할 때, 해당 자료구조를 갱신하기 전에 먼저 수행하고자 하는 작업을 요약해서 기록해둔다. 이렇게 앞으로 할 일을 미리 저장해놓는 것을 write-ahead라고 하고 log라는 자료구조에 기록하기 때문에 WAL이라고 부른다.
• 저널링 파일 시스템 쓰기에서 쓸 내용들에 대한 정보를 미리 로깅을 한 후에 실제 쓰기를 진행하기에 쓰기가 약간 느려진다. 하지만, 그 오버헤드가 의외로 작고, 시스템의 복구 성능을 대폭 개선하기 때문에 대부분의 파일 시스템이 채용하고 있다.
• 저널 자료구조는 저장장치의 일부 영역을 차지한다. 파일 시스템 포맷시에 설정한다.

데이터 저널링

• 트랜잭션의 시작 블럭(TxB)은 연산에 대한 정보들을 기록한다. 시작 블럭에 기록되는 정보로 갱신될 블럭들에 대한 정보와 트랜잭션 식별자(TID)와 같은 것이 있다. 디스크 상의 최종 위치에 기록될 내용들이 블럭에 기록되어 있다. 갱신해야 할 물리적 내용을 저널에 기록하기 때문에 물리 로깅으로도 불린다. 마지막으로 트랜잭션 종료블럭(TxE)은 트랜잭션의 종료를 알리며 마찬가지로 TID를 포함하고 있다. 트랜잭션 종료 블럭이 로그에 기록되면 트랜잭션은 커밋(commit) 되었다고 말한다.
• 트랜잭션이 디스크에 안전히 기록된 후, 파일 시스템 상의 자료 구조들은 이제 갱신될 수 있다. 저널에 기록된 내용을 실제 위치에 반영하는 것을 체크포인팅이라 부른다. 파일 시스템 체크 포인트시에 디스크 원래 위치에 쓰기를 요청한다.
• 저널에 기록하는 도중 크래시가 발생하게 되면 일이 복잡해진다. 디스크에 쓰는 일을 할 때 가장 간단한 방법은 하나씩 요청을 디스크에 전달하고 각각이 완료되기를 기다렸다가 다음을 요청하는 것이다. 하지만 이 방법은 너무 느리다. 이상적인 상황은 다섯 개의 요청을 한꺼번에 전송해서 디스크가 이들을 차례로 순차 쓰기로 하는 것이다. 매우 효율적일 것 같지만, 문제가 존재한다. 한 번에 많은 양을 쓰고자 할 경우, 디스크가 스케줄링을 통해 이들을 작은 단위로 나누어 기록 할 가능성이 존재한다. 그리고 이들의 완료 순서는 디스크에 의해 결정되며, 파일 시스템이 의도한 순서와 완전히 다를 수도 있다. 여기서 트랜잭션 종료 블럭의 순서 때문에 문제가 발생할 수 있다.
• 이러한 문제의 발생을 방지하기 위해 파일 시스템은 트랜잭션을 두 단계로 나누어 기록한다. 먼저 TxE를 제외한 모든 블럭을 한번의 쓰기 요청으로 저널에 쓴다. 이 쓰기가 완료되면 파일 시스템은 TxE에 대한 쓰기를 요청하여 저널을 최종적으로 안정된 상태로 만든다.
• 매우 중요한 조건이 충족되어야 한다. 디스크 쓰기 연산의 원자성이다. 트랜잭션 종료블럭은 무조건 원자적으로 기록되어야 한다.

복구

• 트랜잭션이 로그에 안전하게 기록되기 전에 크래시가 발생한다면 복구시에 아무것도 안하면 된다. 트랜잭션이 로그에 기록되었지만, 체크 포인트가 완료되기전에 크래시가 발생한다면 파일 시스템의 복구 프로세스는 시스템이 부팅할 때 로그를 탐색해서 디스크에 커밋된 트랜잭션이 있는지 파악한다.
• 커밋된 트랜잭션의 블럭들을 디스크 상의 원래의 위치에 쓴다. 이 과정을 재생(replayed)한다. 가장 간단한 방식의 로깅이다. redo logging이라고 한다. 저널에 커밋된 트랜잭션을 replay하며 디스크 자료구조간에 일관성을 보장한다. 복구 후 파일 시스템을 마운트하여 새로운 요청을 받을 수 있도록 준비한다.

로그 기록을 일괄처리 방식으로

• 이제까지 언급한 데이터 저널링 방식은 디스크에 많은 트래픽을 유발한다.
• 이런 상황을 개선하기 위해서 어떤 파일 시스템은 각각 여러개의 저널로그를 한번에 디스크에 커밋하는 방법을 사용한다. 로깅해야 할 모든 파일 시스템 갱신 내용을 트랜잭션 버퍼라는 자료구조에 보관한다. 파일 시스템 파티션마다 하나만 존재하는 전역 자료구조이다. 트랜잭션 버퍼의 내용들은 파일 시스템이 저널을 커밋 할 때 디스크에 기록된다. 파일 시스템은 메모리에 있는 갱신 내용을 정기적으로 저널에 기록한다. 이외에 fsync()나 sync() 함수가 호출되면, 해당 시점에 트랜잭션 버퍼의 내용들이 저널에 커밋된다. 저널에 기록되어야 할 블럭들을 버퍼링함으로써 많은 양의 쓰기 트래픽을 줄일 수 있다.

로그 공간의 관리

• 로그 공간이 가득 차면 두 가지 문제가 발생한다. 첫 번째 문제는 로기에 있는 모든 트랜잭션을 재실행 해야 하기 때문에 로그가 커질수록 복구소요시간은 길어진다. 두 번째 문제는 심각하다. 만약 로그가 가득차면 디스크에 더 이상의 트랜잭션을 커밋할 수가 없게된다. 파일 시스템을 갱신하는 모든 작업들이 실패한다.
• 이 문제를 해결하기 위해서 저널링 파일 시스템은 로그를 환형 자료구조 형식으로 사용한다. 로그 영역을 끝까지 다 쓰면, 앞에서부터 다시 쓰기 시작한다. 이런 이유로 저널을 환형로그 라고도 부른다. 파일 시스템은 트랜잭션이 체크 포인트가 되면 해당 로그 공간이 재사용 될 수 있도록 트랜잭션이 차지하고 있는 공간을 비운다.

메타데이터 저널링

• 특정 워크로드의 경우에 심각한 양의 쓰기 오버헤드가 추가될 수 있다.
• 모든 데이터 블럭을 두 번씩 쓰는 방법을 배제하기 위한 기법들이 존재한다. 이제까지 다룬 저널링 모드는 모든 데이터를 저널링하기 때문에 데이터 저널링이라고 부른다. 간단한 저널링의 형태는 orderd journaling이다. 저널에 데이터 블럭을 기록하지 않는다는 것을 제외하면 거의 대부분이 동일하다.
• 데이터가 먼저 기록되는 것을 강제하여 아이노드 포인터가 쓰레기 데이터를 가리키지 않는 것을 보장한다. 크래시 일관성에 있어서 핵심 법칙은 ‘포인터의 대상이 되는 객체를 그것을 가리키는 객체보다 먼저 써라’ 는 것이며 일부 크래시 일관성 기법들에서는 더 넓은 의미로 사용되고 있다.
• ordered 모드와 unorderd 모드는 둘 다 메타데이터 일관성은 보장하지만 데이터의 일관성에 대한 소장은 다르다. unordered 모드의 경우 아이노드가 쓰레기 데이터 블럭을 가리킬 수 있기 때문에 데이터의 일관성을 보장하지 않는다.
• 저널링의 올바른 동작에 있어서, 저널 쓰기 이전에 데이터 쓰기가 반드시 완료될 필요는 없다. 데이터, 저널 트랜잭션 시작블럭, 그리고 저널된 메타데이터를 동시에 쓰기 요청하더라도 괜찮다. 다만, 저널 커밋 블럭을 요청하기 전 단계는 반드시 완료되어야 한다.

32.4 해법 3 : 그외 방법

• 파일 시스템의 메타데이터 일관성을 유지하는 두 가지 방법을 설명했다.
• 하나는 fsck를 사용하는 느린 방법이고, 다른 하나는 좀 더 효율적인 저널링이라는 기법이다. 하지만 이외에도 다른 기법들이 있다. 그중에 하나는 soft update이다 이 방법은 파일 시스템의 모든 쓰기들의 순서를 잘 정해서 디스크상의 자료구조가 절대로 불일치 상태가 되지 않도록 한다. 유사한 종류의 법칙을 파일 시스템의 모든 자료구조에 적용할 수 있다. 하지만 soft update는 구현이 쉽지 않다. 저널링 기법은 파일 시스템의 자료구조에 관한 상대적으로 적은 지식만으로 구현이 가능하지만, soft update는 각 파일 시스템 자료구조에 대한 심도있는 지식이 필요로 하다.
• 다른 접근 방법은 Copy-And-Write(COW) 라고 불리는 것이다. 이 기술은 파일이나 디렉터리들을 절대로 원래 위치에 덮어쓰지 않는다. 대신에 이제까지 디스크에서 사용 안된 위치에 갱신 내용을 저장한다. 여러개의 갱신작업이 완료되면 COW 파일 시스템은 루트 자료구조에 새롭게 갱신된다. 자료구조를 가리키는 포인터를 포함하도록 변경한다. 이러한 방식으로 파일 시스템의 일관성을 유지하도록 한다.
• 또 다른 방법은 백포인터 기반 일관성(BBC : backpointer-based consistency)라고 하는 기법으로 쓰기 사이에 어떤 순서도 강요하지 않는다. 대신 시스템의 모든 블럭에 백 포인터를 추가하였다. 각 데이터 블럭은 자신이 속해있는 아이노드에 대한 참조를 갖고 있는 식이다. 파일을 접근할 때 이 파일이 일관성이 유지되고 있는지를 판단하기 위해서는 앞 방향 포인터가 가리키는 블럭이 다시 이 블럭을 가리키고 있는지를 검사하면 된다. 만약 참이라면 모든 것이 디스크로 안전하게 도달하였다는 것이고 파일이 일관성을 갖고 있음을 나타낸다. 만약 아니라면 파일 불일치 상태이며 에러를 반환한다.

PintOS

stack growth를 진행중이다. 생각보다 어려웠다.

조건에 따라서 스택을 늘려주는 과정을 거쳤고, 그러면서 스택의 포인터나 각 프로세스가 가지고 있는 스택 바텀같은 값들을 수정해주는 과정을 거쳤다.

여러가지 값을 수정해주다보니 어떤 값이 어디에 들어가야하는지 헷갈려서 실수를 하기도 했다.

결과적으로 어느정도 구현은 했지만 2가지의 stack growth 테스트가 fail이 됐다.

bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
                         bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
...
 if (rsp - 8 <= addr && USER_STACK - 0x100000 <= addr && addr <= USER_STACK)
        {
            vm_stack_growth(pg_round_down(addr));
        }
...
}

static void
vm_stack_growth(void *addr)
{
    void *stack_bottom = thread_current()->rsp_stack;

    if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1))
    {
        thread_current()->stack_bottom = stack_bottom;
    }
}

• 구현한 함수들