[OSTEP][영속성] CH43 로그 기반 파일 시스템

발표 날짜 2024.12.06 FRI 

 

CH43 로그 기반 파일 시스템 

로그 기반 파일 시스템의 연구 동기는 아래와 같은 관찰 결과이다 

* 시스템 메모리 크기가 증가 추세였다 - 메모리 용량이 커지면서 읽기는 캐시에서 처리되고, 디스크의 사용은 쓰기 위주가 되었다 

* 임의 I/O 와 순차 I/O 의 성능 간의 격차가 크게 벌어졌다 - 하드 디스크 드라이브의 전송 대역폭이 꾸준히 증가한 것에 비해 탐색과 회전 지연 비용은 느린 속도로 줄어들었다 

* 많은 일반적인 워크로드에서 기존 파일 시스템들의 성능이 좋지 않았다 - FFS 는 파일 하나를 생성하기 위해 여러 번의 쓰기를 해야 한다, FFS 는 여러 번의 짧은 탐색과 연이는 회전 지연을 발생시키기 때문에 최대 순차 대역폭이 낼 수 있는 성능에 한참 못 미치는 성능을 보인다 

* 파일 시스템이 RAID 를 고려하지 않았다 - RAID-4 와 RAID-5 는 하나의 블럭을 쓰더라도 4번의 물리적 I/O 가 발생하는 문제가 있지만, 이런 최악의 현상을 회피하려는 노력을 하지 않았다 

 

이러한 문제들을 해결하기 위해 로그 기반 파일 시스템 Log-Structured File System, LFS 이 개발되었다 

LFS 는 메타데이터를 포함한 모든 갱신 정보를 세그먼트라 불리는 메모리 자료 구조에 보관하고 

세그먼트가 가득 차면 (기존의 내용을 덮어쓰지 않고) 디스크에서 빈 공간을 찾아서 한 번에 기록한다 

핵심 질문 - 모든 쓰기를 어떻게 순차 쓰기로 변형시킬까?
읽기 대상이 디스크 상에 흩어져 있을 가능성이 있기 때문에, 읽기 동작을 순차적으로 변형하는 것은 원천적으로 불가능하다, 하지만 쓰기의 경우 파일 시스템이 쓰기 위치를 선택할 수 있다, 선택의 여지를 최대한 활용해보자 

43.1 디스크에 순차적으로 쓰기 

데이터 블럭을 기록하면 데이터가 갱신되고 메타데이터도 같이 갱신되어야 한다, 아이노드도 디스크에 기록하고 아이노드가 데이터 블럭을 가리키도록 해야 한다 

모든 갱신 (데이터 블럭과 아이노드 등) 을 디스크에 순차적을 기록한다는 것이 LFS 의 핵심이다 

43.2 순차적이면서 효율적으로 쓰기 

디스크에 순차적으로 쓰는 것만으로는 효율적인 쓰기를 보장할 수 없다 

다수의 순차쓰기를 (또는 하나의 큰 크기의 쓰기) 한번에 디스크에 내려 보내야 빠른 쓰기 성능을 얻을 수 있다

이를 위해 LFS 는 갱신 내용을 메모리에 보관하고, 갱신 내용이 충분히 쌓였다면 디스크로 한번에 내려 보내는 쓰기 버퍼링 기법을 사용한다

LFS 가 단일 집합으로 묶어서 쓰기 위해 사용하는 쓰기 단위, 또는 한번에 디스크에 기록하는 단위를 세그먼트라고 하고

디스크에 데이터를 기록할 때 쓰기 내용들을 세그먼트 버퍼에 유지하고, 세그먼트가 차면 세그먼트 버퍼를 한번의 쓰기 연산으로 디스크에 기록한다, 세그먼트가 충분히 크면, 쓰기 연산은 효율적이 된다 

43.3 적절한 버퍼의 크기는?

매번 쓰기 시 디스크 헤드를 이동하는 데 일정 시간이 소요된다고 가정했을 때, 위치 잡기 비용을 상쇄 Amortize 하기 위해서

세그먼트의 크기는 클수록 좋고, 최대 대역폭에 더 근접할 수 있다 

위치 잡기 시간을 Tposition초, 디스크 전송 속도는 RpeakMB/s, 세그먼트 크기 D MB, 데이터 청크를 쓰는 데 소요되는 시간 Twrite, 실제 쓰기 속도 Reffective, 최대 속도의 특정 비율 F 라고 하면 Twrite = Tposition + D/Rpeak 이고, Reffective = F X Rpeak 이다 

D 에 대해서 식을 정리하면 세그먼트 크기는 아래와 같이 정의할 수 있다 

🐣 디스크에 데이터를 쓰려면 항상 고정 오버헤드가 발생한다

* 포지셔닝 시간 : 디스크 헤드가 올바른 위치로 이동하고 회전하는 데 걸리는 시간

* 데이터 전송 시간 : 데이터를 실제롤 디스크에 쓰는 데 걸리는 시간

LFS에서 버퍼링할 데이터의 양은 디스크의 포지셔닝 시간과 최대 전송 속도를 기반으로 계산된다, 실제 시스템의 메모리 크기나 응답 시간 요구사항을 고려해 적절한 타협이 필요하다 🐣

43.4 문제 - 아이노드 찾기 

전통적인 파일 시스템에서는 각 아이노드의 위치가 정해져 있어, 배열을 사용하면 아이노드의 위치를 매우 빠르게 찾을 수 있다 

* 아이노드 번호 * 아이노드 크기 + 시작 주소 

FFS 는 아이노드 테이블을 분할하여 실린더 그룹마다 아이노드 그룹을 넣어 두기 때문에, 분할된 테이블의 크기와 각각의 시작 주소를 알아야 계산할 수 있다, 위치 계산은 배열 기반과 유사하여 간단하다 

LFS 의 경우 아이노드가 디스크 전역에 흩어져 있고, 최신 아이노드의 위치가 계속 변한다 

43.5 간접 계층을 이용한 해법 - 아이노드 맵 

계속적으로 이동하는 아이노드의 위치를 파악하기 위해 아이노드 맵 inode map, imap 이라는 자료 구조가 개발되었다 

imap 자료 구조는 아이노드 번호를 입력으로 하여 가장 최신 아이노드의 디스크 위치를 구할 수 있고, 항목 당 4바이트의 간단한 배열로 구현될 수 있다 

LFS 에 크래시가 발생할 때 아이노드의 위치를 파악할 수 있도록 imap 은 안전하게 보관되어야 한다 

LFS 에서는 아이노드 맵을 새로이 기록된 데이터와 아이노드들 옆에 함께 기록한다 

🐣 아이맵 imap 이란, 아이노드 번호를 입력 받아 최신 아이노드의 디스크 주소를 반환하는 데이터 구조다

아이맵을 쓰는 이유

LFS에서 아이노드가 디스크의 여러 위치로 옮겨질 수 있기 때문에, 아이맵을 통해 최신 아이노드를 빠르게 찾을 수 있다. 이를 통해서 디스크에서 아이노드를 찾는 과정이 간단해진다.

아이맵은 각 항목당 4바이트를 갖는 간단한 배열로 구현될 수 있다. 디스크에 아이노드가 기록될 때 아이맵은 새로운 위치를 가리키도록 갱신된다.

아이맵은 디스크에 써서 안전하게 보관되어야한다. 아이맵은 잦은 갱신으로 인해 성능이 저하될 수 있다.

LFS에서는 이를 해결하기 위해 데이터를 디스크에 기록할 때 아이맵 조각을 함께 저장한다. 예를 들어, 데이터 블록과 아이노드, 관련된 아이맵 정보를 같은 세그먼트에 기록한다. 🐣

43.6 해법의 완성 - 체크포인트 영역 

아이노드 맵 역시 블럭으로 나누어져서 디스크 상에 흩어져 있기 때문에, imap 블럭들의 위치를 기록하는 영역이 필요하고

이를 체크포인트 영역 Checkpoint Region, CR 이라고 부른다 

체크포인트 영역은 최신의 아이노드 맵을 이루는 블럭들을 가리키는 포인터 (즉, 주소) 를 가지고 있고, 주기적으로 갱신된다 

blk[0]:A0 은 첫번째 블럭의 주소가 A0, I[K] 는 K번째 아이노드, map[K]:A1 는 K번째 아이노드가 A1 에 위치해 있다는 뜻이다 

43.7 디스크에서 읽기 - 요약 

메모리에 아무것도 없을 때 가장 처음 읽어야 하는 디스크 상의 자료 구조는 체크포인트 영역이다 

체크포인트 영역에서 전체 아이노드 맵 블럭 전체를 메모리에 캐시하고, 가장 최신의 아이노드를 읽어들인다 

보통의 경우 LFS 는 일반 파일 시스템이 수행하는 개수만큼의 I/O 를 처리하여 파일을 읽는다 

imap 전체가 캐시되어 있기 때문에 LFS 가 추가로 하는 일은 imap 에서 아이노드 주소를 찾아 읽는 것뿐이다 

🐣 CR -> imap -> inode -> Data 로 접근 🐣

43.8 디렉터리 관리 방법은? 

디렉터리는 매핑 정보 (이름과 아이노드 번호) 로 구성되어 있다, 파일을 생성할 때 LFS 는 새로운 아이노드와 데이터 그리고 파일을 가리키는 디렉터리 데이터와 디렉터리 아이노드도 같이 써야 하고, LFS 는 이 정보들을 디스크에 순차적으로 기록한다 

아이노드가 갱신되면 디스크 상의 아이노드 위치가 바뀐다, 만약 디렉터리의 항목들이 아이노드의 위치를 직접 가리키도록 설계되었다면 아이노드의 위치가 변경되면 디렉터리의 데이터 블럭도 갱신되어야 하고, 그 부모까지 타고 올라가면 루트까지 갱신되어야 한다 

LFS 는 imap 을 이용하여, 아이노드 위치가 변경되더라도 변경 내용을 디렉터리 내에 직접 반영하지 않고, 동일한 이름-아이노드 번호 매핑으로 간접 참조를 활용하여 재귀 갱신 문제 Recursive Update Problem 을 해결한다 

🐣 파일이 갱신되도 내용은 데이터 블럭에 있으니,  imap 에는 위치만 저장한다 🐣

🐣 Recursive Update Problem(재귀 갱신 문제)

LFS는 간접 참조를 통해 해당 문제를 해결한다.

해당 문제는 아이노드의 위치가 바뀔 때, 해당 디렉터리와 부모 디렉터리까지 수정해야하는 문제이다.

LFS는 아이노드 위치 변경은 아이맵만 갱신하고 디렉터리 항목에는 영향을 주지 않게 했다. 디렉터리 항목은 아이노드 번호만 저장하므로 위치 변경에 따른 수정을 하지 않아도 된다 🐣

43.9 새로운 문제 - 가비지 컬렉션 

LFS 는 갱신된 파일 (아이노드와 데이터) 을 계속 디스크의 새로운 위치에 쓴다, 쓰기 동작은 효율적으로 수행되지만, 예전 값들이 디스크에 남아 있게 된다, 이 예전 내용들을 가비지 Garbage 라고 부른다 

구 버전의 아이노드와 데이터 블럭 등을 예전 버전으로 복원하는 데 사용할 수도 있다, 이와 같이 파일의 여러 버전을 관리하는 파일 시스템을 버전 파일 시스템 Versioning File System 이라고 부른다

하지만 LFS 는 파일의 최신 버전만을 유지하기 때문에, 주기적으로 이전 버전의 데이터, 아이노드 등을 찾아 제거한다, 이 작업은 가비지 커렉션의 일종이고, 가비지 컬렉션은 프로그램 언어에서 프로그램이 사용하지 않는 메모리를 자동적으로 해제하는 동작을 일컫는다 

쓰기 작업의 효율성을 위해 (큰 공간 단위로 공간을 해제하기 위해) LFS 의 가비지 컬렉터는 세그먼트 단위로 동작한다 

🐣 가비지 컬렉션 과정

* 오래된 세그멘트를 읽어서 사용 중인 데이터와 가비지를 구분한다.

* 사용 중인 데이터를 새로운 세그멘트로 복사한다.

* 기존 세그멘트의 모든 블록을 해제해서 새로운 쓰기 공간을 확보한다.

하지만 두 가지 문제가 있다.

* LFS는 어떻게 살아 있는 데이터를 알 수 있을까?

* 가비지 컬렉터는 얼마나 자주 실행되어야하고 몇 개의 세그멘트를 가비지 컬렉션 해야할까?🐣 

43.10 블럭의 최신 여부 판단 

LFS 는 각 데이터 블럭 D 에 대해 D 가 속한 파일의 아이노드 번호 (어떤 파일에 속하는지) 와 파일 내에서 오프셋 (해당 파일에 몇 번째 블럭인지) 를 저장하고, 이 정보를 세그먼트 첫 머리에 있는 세그먼트 요약 블럭 SEgment Summary Block 자료 구조에 저장한다 

세그먼트 요약 블럭에서 블럭 D 의 아이노드 번호 N 과 오프셋 T 을 파악하고, imap 에서 아이노드 N 위치를 찾아 디스크에서 N 을 읽는다, 아이노드 (or 간접 블럭 블럭) 을 이용해서 오프셋 T 에 해당하는 블럭의 디스크 위치를 알아낸다 

파악된 위치가 주소 A 와 일치하면 블럭 D 는 유효한 블럭이고, D 의 위치와 다르다면 D 는 유효하지 않다고 할 수 있다 

데이터 블럭 D 의 유효성 여부를 검사하는 의사 코드와 imap 에서 아이노드의 위치를 파악하는 그림

이 방법은 복잡하기 때문에 성능이 문제가 될 수 있다, 좀 더 빠른 유효성 판단 기준으로, 버전 번호 Version Number 를 증가시키고 그 새로운 버전 번호를 imap 에 기록해 둘 수 있다, 버전 번호를 디스크 상의 세그먼트에 같이 기록해 두고 LFS 는 디스크 상의 버전 번호와 imap 의 버전 번호를 비교하면, 추가적인 읽기도 방지할 수 있다 

43.11 정책 - 어떤 블럭을 언제 정리하는가

가비지 컬렉션 시기는 주기적으로 수행하거나 유휴 시간에 하거나 디스크가 가득 차서 어쩔 수 없이 할 수 밖에 없을 때 하면 된다

어느 블럭들을 카비지 컬렉션할지는 세그먼트를 핫 Hot 과 콜드 Cold 로 구분하여 정할 수 있다

해당 세그먼트의 내용이 빈번하게 갱신되는 세그먼트를 핫 세그먼트라고 하고, 몇 개의 무효 블럭 Dead Block 들이 있지만 대부분의 블럭들은 갱신이 되지 않는 세그먼트를 콜드 세그먼트라고 할 때 콜드 세그먼트는 자주, 핫 세그먼트를 긴 간격으로 클리닝하는 것이 효율적이다 

43.12 크래시로부터의 복구와 로그 

LFS 에서는 디스크에 쓰는 도중에 시스템이 크래시되면 어떻게 되는가?

일반적인 파일 시스템 동작에서, LFS 는 쓰기 데이터를 세그먼트 버퍼에 먼저 기록하고 해당 세그먼트 버퍼를 디스크에 기록한다, 체크포인트 영역에 첫번째와 마지막 세그먼트를 가리키는 포인터를 두고, 각 세그먼트는 다음 세그먼트를 가리키는 포인터를 둬서 일종의 링크드 리스트로 연결시킨다 

체크포인트 영역의 정보는 주기적으로 갱신되는데, 체크포인트 영역은 원자적으로 갱신되어야 하기 때문에 LFS 는 디스크 양 끝에 체크포인트 영역을 두고 교대로 갱신한다, 먼저 체크포인터 헤더를 기록한 후에 체크포인터 영역에 내용을 쓰고, 체크포인트 영역의 마지막 블럭을 갱신한다, 체크포인트 영역이 성공적으로 갱신될 경우에는 헤더 블럭의 시간값이 마지막 블럭의 시간값보다 작게 되지만, 체크포인트 영역 갱신 중에 크래시가 발생할 경우, 시간 값을 비교하여 헤더 블럭의 시간이 더 크다면 갱신 중에 크래시가 발생했다고 볼 수 있다 

 

세그먼트를 쓸 때 크래시가 발생하는 경우를 보자면, LFS 는 약 30초마다 체크포인트 영역을 갱신한다, 디스크에 저장된 체크포인트 영역의 내용 (파일 시스템 스냅샷) 은 크래시 시점 기준으로 최대 30초 이전의 상태를 반영할 수 있다, 재부팅 시 복구 과정에서 체크포인트 영역을 읽어서 imap 조각들이 가리키는 곳을 확인하여 파일과 디렉터리들을 복원한다 

여기서 마지막 수초 간의 갱신 내용이 손실되기 때문에, 데이터베이스에서 사용되는 롤 포워드 Roll Forward 기법을 적용할 수 있다, 체크포인트가 가리키는 다음 세그먼트를 따라가며 마지막 세그먼트를 읽어서 마지막 체크포인트 이후의 데이터와 메타데이터를 복구할 수 있다

 

🐣 * CR 업데이트 중 크래시 해결

체크포인트 영역은 원자적으로 갱신되어야 한다. 이를 위해 두 개의 체크포인트 영역을 디스크의 양쪽 끝에 저장하고 교대로 갱신한다.

CR 업데이트시 먼저 체크포인트 헤더를 기록한 후 체크포인트 영역에 내용을 쓰고 최종적으로 체크포인트 영역의 마지막 블럭을 갱신한다.

크래시가 발생하면, 두 체크포인트 중 헤더의 시간 값이 마지막 블럭보다 커지게된다. LFS는 유효한 시간 쌍을 갖는 가장 최근 체크포인트 영역을 선택한다.

* 세그멘트 기록 중 크래시 해결

LFS는 롤 포워드 방식을 이용한다.

롤 포워드의 과정은 아래와 같다.

1. 가장 최신의 체크포인트 영역을 로드한다.
2. 체크포인트에 저장된 로그의 마지막 세그멘트 위치를 확인한다.
3. 체크포인트 영역 이후의 로그를 스캔해서 유효한 세그멘트를 복구한다.
4. 복구된 데이터를 반영해서 아이맵과 아이노드를 최신 상태로 업데이트한다. 🐣 

43.13 요약

LFS 는 파일을 생성할 때 항상 디스크에서 사용되지 않은 부분에 쓰고 나중에 오래된 것들을 가비지 컬렉션해서 공간을 확보한다 

이 방법을 데이터베이스 시스템에서는 쉐도우 페이징 Shadow Paging, 파일 시스템에서는 쓰기 시 복사 Copy-on-Write 라고 부른다

모든 갱신들을 메모리 상의 세그먼트에 다 같이 모아서 순차적으로 쓸 수 있기 때문에 이 기법의 쓰기는 매우 효율적이다 

하지만 LFS 기법은 가비지를 만들어 낸다, 오래된 데이터 블럭들이 디스크 여기저기에 흩어져 있어서 가비지 컬렉터가 필요하다 

가비지 컬렉션 때문에 LFS 가 큰 여파를 일으키지 못 했지만, LFS 를 기반으로, 상용 파일 시스템은 Copy-on-Write 방식을 사용하고

파일 시스템 이전 버전들을 스냅샷 Snapshot 으로 유지하는 파일 시스템도 있다