📚 지식 노트

페이지와 힙 파일

디스크는 바이트 하나가 아니라 블록 단위로 읽고 쓴다. 그래서 데이터베이스도 파일을 고정 크기 페이지(page)로 나눠 다룬다. PostgreSQL은 8KiB, MySQL InnoDB는 16KiB가 기본이다. 행 하나를 읽어도 그 행이 든 페이지 전체를 메모리로 가져온다.

길이가 제각각인 행을 페이지에 담는 흔한 방법이 슬롯 페이지(slotted page)다. 페이지 앞쪽의 슬롯 배열이 각 행의 위치와 길이를 적고, 바깥에서는 행을 "(페이지 번호, 슬롯 번호)"로 가리킨다. 행을 지우거나 길이가 바뀌어 페이지 안에서 자리를 옮겨도 슬롯 값만 고치면 되므로, 이 주소를 들고 있는 인덱스를 고칠 필요가 없다. PostgreSQL 문서의 Database Page Layout이 실제 구조(24바이트 머리말, 4바이트 항목 포인터, 끝쪽의 행)를 적어 둔다.

테이블의 페이지를 순서 없이 모아 둔 파일이 힙 파일(heap file)이다. 새 행은 빈 공간이 있는 아무 페이지에나 들어가고, 어느 페이지에 빈 공간이 얼마나 있는지는 따로 둔 빈 공간 지도(free space map)가 알려 준다. 힙에는 순서가 없으니 조건에 맞는 행을 찾으려면 모든 페이지를 훑거나(순차 스캔) 아래의 인덱스를 써야 한다. MySQL InnoDB처럼 테이블 자체를 기본 키 순서의 B+ 트리로 두는 엔진(클러스터드 인덱스)도 있다.

버퍼 풀

디스크 읽기는 메모리 읽기보다 수천 배 이상 느리다(RAM 노트의 메모리 계층). 그래서 데이터베이스는 큰 메모리 영역을 페이지 크기의 프레임으로 나눠 최근에 쓴 페이지를 들고 있는다. 이것이 버퍼 풀(buffer pool)이다. 실행 엔진은 "페이지 7을 달라"고만 하고, 디스크에서 올지 메모리에서 올지는 버퍼 풀이 정한다.

• 페이지 테이블: 페이지 번호 → 프레임 번호의 해시 표. 여기 없으면 디스크에서 읽어야 한다(miss).
• pin 수: 지금 이 페이지를 쓰는 스레드 수. 0이 아니면 내보낼 수 없다.
• dirty 표시: 메모리에서 고쳤지만 디스크에는 아직 옛 내용이 있다는 뜻. 내보내기 전에 써야 하고, 그 전에 로그가 먼저 디스크에 있어야 한다(다음 절의 WAL).
• 교체 정책: 가장 오래 안 쓴 것(LRU)이나 그 근사인 CLOCK을 쓴다. 다만 테이블 하나를 끝까지 훑는 순차 스캔이 버퍼 풀 전체를 밀어내지 않도록, 스캔용 작은 고리 버퍼를 따로 두는 식의 보정이 붙는다.

운영체제에도 페이지 캐시가 있지만 데이터베이스가 따로 버퍼 풀을 두는 이유는, 언제 디스크에 써도 되는지(WAL 순서), 무엇을 먼저 내보낼지를 데이터베이스가 가장 잘 알기 때문이다. 버퍼 풀 설계는 Carnegie Mellon 대학 데이터베이스 강의의 버퍼 풀 강의 노트에 자세하다.

B+ 트리 인덱스

인덱스는 "값 → 행 주소"를 정렬해 둔 별도 구조다. 데이터베이스의 기본 인덱스는 거의 다 B+ 트리다. B-트리의 넣기·가르기 원리는 알고리즘의 트리 노트에 있고, 여기서는 디스크용으로 바꾼 점을 본다.

• 노드 하나 = 페이지 하나: 노드에 열쇠를 수백 개 넣어 가지 수(fanout)를 키운다. 가지가 400개면 4층으로 항목 256억 개를 가리킨다. 높이가 곧 읽는 페이지 수다.
• 값은 잎에만: 안쪽 노드에는 길을 가르는 열쇠만 둔다. 그래서 안쪽 노드에 열쇠가 더 많이 들어가 트리가 낮아지고, 잎을 가를 때 오른쪽 첫 열쇠가 부모에 복사된다(그림의 30·50·70·90).
• 잎끼리 연결: 잎이 옆 잎을 가리켜 BETWEEN 30 AND 60 같은 범위 질의는 첫 잎을 찾은 뒤 옆으로만 읽는다.
• 지우기: 잎이 반 아래로 줄면 옆 잎에서 빌리거나 합친다. 실제 엔진은 비용을 아끼려 합치기를 미루기도 한다.

여러 스레드가 동시에 트리를 고칠 때는 내려가면서 부모 잠금을 풀어 주는 래치 크래빙(latch crabbing) 같은 기법을 쓴다. 인덱스로 무엇을 할 수 있고 없는지는 인덱스와 쿼리 실행 노트에서 다룬다.

WAL과 체크포인트

버퍼 풀에서 고친 페이지를 커밋 때마다 디스크에 쓰면 느리다. 페이지는 디스크 여기저기 흩어져 있기 때문이다. 그렇다고 안 쓰고 두면 전원이 꺼질 때 커밋한 변경이 사라진다. 이 둘을 함께 푸는 것이 먼저 적어 두는 로그(write-ahead log, WAL)다. 무엇을 어떻게 바꿨는지를 로그 파일 끝에 이어 쓰고, 커밋은 로그가 디스크에 닿았을 때 끝난 것으로 친다. PostgreSQL 문서의 Write-Ahead Logging (WAL) 절이 같은 설명을 한다.

로그 기록마다 순번인 LSN(log sequence number)을 붙이고, 페이지 머리말에는 그 페이지를 마지막으로 고친 기록의 LSN(pageLSN)을 적는다. 디스크에 내려간 로그 끝(flushedLSN)과 비교하면 페이지를 내보내도 되는지 바로 안다. 덕분에 데이터 페이지는 커밋과 상관없이 아무 때나 모아서 쓸 수 있다.

로그가 끝없이 길어지면 복구 때 처음부터 다시 읽어야 한다. 체크포인트(checkpoint)는 주기적으로 dirty 페이지를 디스크에 써 두고 "여기까지는 데이터 파일에 반영됐다"는 기록을 로그에 남긴다. 복구는 마지막 체크포인트 근처부터 시작하면 되고, 그보다 앞선 로그는 지우거나 보관용으로 넘긴다. 체크포인트가 잦으면 복구가 빠르지만 쓰기가 늘어나는 맞바꿈이 있어, PostgreSQL은 WAL Configuration의 checkpoint_timeout·max_wal_size로 간격을 정한다.

장애 복구: ARIES

WAL만 있으면 재시작 때 무엇을 해야 할까. 널리 쓰이는 답이 IBM의 Mohan 등이 1992년 논문 「ARIES: A Transaction Recovery Method…」에서 정리한 방법이다. 핵심 전제는 두 가지다. 커밋 전에도 dirty 페이지를 내보낼 수 있고(steal), 커밋 때 페이지를 쓰지 않아도 된다(no-force). 그래서 디스크에는 커밋 안 된 변경이 섞여 있을 수 있고, 커밋한 변경이 빠져 있을 수도 있다.

1. 분석(analysis): 마지막 체크포인트부터 로그를 읽어, 장애 때 진행 중이던 트랜잭션과 dirty였을 페이지 목록을 만든다.
2. 다시 하기(redo): dirty 페이지 중 가장 오래된 변경 위치부터 로그를 다시 적용한다. 이때 이긴 쪽·진 쪽을 가리지 않고 "역사를 되풀이"한다. 페이지의 pageLSN이 기록의 LSN보다 크거나 같으면 이미 반영된 것이라 건너뛴다.
3. 되돌리기(undo): 커밋하지 못한 트랜잭션의 변경을 뒤에서부터 취소한다. 취소할 때마다 보상 기록(CLR)을 로그에 남겨, 복구 도중 또 장애가 나도 같은 취소를 두 번 하지 않는다.

실제 구현은 엔진마다 다르다. PostgreSQL은 MVCC 덕분에 커밋 안 된 버전이 남아 있어도 보이지 않으므로 별도의 undo 단계 없이 redo만 한다. 원리는 CMU 15-445 복구 강의 노트가 예와 함께 따라간다.

LSM 트리

B+ 트리는 쓰기마다 디스크의 제자리를 고친다. 쓰기가 아주 많으면 이 흩어진 쓰기가 병목이다. 1996년 O'Neil 등의 「The Log-Structured Merge-Tree (LSM-Tree)」는 반대로 접근한다. 쓰기를 메모리에 모았다가 정렬된 덩어리로 한 번에 내려 쓰고, 디스크의 덩어리들은 나중에 병합한다. 지금은 RocksDB·LevelDB·Cassandra 같은 엔진의 기본 구조다.

• memtable: 메모리의 정렬된 표(보통 스킵 리스트). 쓰기는 WAL 한 줄과 memtable 넣기로 끝나 매우 빠르다.
• SSTable(sorted string table): memtable이 차면 정렬된 채로 파일 하나에 쓴다. 한 번 쓴 파일은 고치지 않는다. 고치기·지우기도 새 기록(지움 표시)을 더하는 것뿐이다.
• compaction: 파일이 쌓이면 여러 파일을 병합 정렬해 한 줄로 다시 쓰며 옛 값과 지움 표시를 버린다. 레벨마다 크기를 약 10배씩 키우는 레벨식(leveled)과, 비슷한 크기끼리 모아 합치는 계층식(tiered)이 대표적이다.
• 읽기: 새것부터 차례로 본다. 파일마다 블룸 필터(해싱 노트)를 두어 "이 파일엔 없다"를 디스크를 읽지 않고 알아낸다.

증폭으로 본 B+ 트리와 LSM 트리

두 구조를 비교하는 흔한 잣대는 세 가지 증폭(amplification)이다. 쓰기 증폭은 사용자가 쓴 바이트에 견줘 디스크에 실제로 쓴 바이트, 읽기 증폭은 값 하나를 읽으려고 본 페이지·파일 수, 공간 증폭은 데이터 크기에 견줘 디스크를 차지한 크기다. 하나를 줄이면 다른 것이 늘어나는 관계라 어느 쪽이 낫다기보다 무엇을 아낄지 고르는 문제다.

표의 숫자는 1TB 데이터, 맨 위 레벨 256MB, 레벨 크기 비 10이라는 가정으로 계산한 어림이다. 실제 값은 캐시, 압축, compaction 방식, 갱신 패턴에 따라 크게 달라지므로, 고를 때는 자기 부하로 측정한다. 각 구조를 쓰는 실제 엔진은 같은 데이터베이스 탭의 종류별 노트에서 다룬다.