제목, 태그, 카테고리로 검색

모든 태그

# Database Internals

12개의 글

DB 내부 ⑫ (회고): 나는 왜 DB를 밑바닥부터 만들었나, 만들어서 증명한 것들

이 글은 db-hobby의 회고이자, 이 시리즈 전체의 포트폴리오다. 출발점은 하나의 자각이었다. '인덱스는 B+Tree라 빠르다'고 말할 수는 있는데, 왜 이진 트리가 아니라 B+Tree인지, 커밋의 fsync가 정확히 무엇을 보장하는지 설명하지 못했다. 설명할 수 없으면 모르는 것이다. 그래서 페이지 한 장부터 Raft 합의까지 C로 직접 만들었고, 모든 주장을 직접 측정한 수치로 바꿨다: 인덱스는 10만 행에서 풀 스캔보다 416배 빨랐고, 같은 5천 행 적재가 fsync 횟수에 따라 23배 갈렸고, 12코어 병렬화는 2.16배가 천장이었는데 그 천장의 정체(버퍼 풀 latch의 I/O 직렬화)를 A/B 실험으로 확증하고 고치자 콜드 스캔이 4워커 기준 1.08배에서 2.39배가 됐다(8워커는 0.62배에서 1.36배). 성능 작업 중 조용히 틀린 답을 내던 집계 버그를 발굴했고, 구현과 검증을 분리한 적대적 리뷰가 '테스트는 초록인데 원리상 틀린' 합의 버그 일곱을 잡았다. 694개 테스트, ThreadSanitizer/ASan 계측, 크래시 주입, 결정적 시뮬레이션. 무엇을 만들었는지가 아니라 어떻게 검증했고 왜 그 선택을 했는지의 기록이다. 무엇을 안 했는지(정직한 경계)까지 포함해서.

DB 내부 ⑪: SQL 실행기, 텍스트에서 행까지, 조인 3형제와 3값 논리

SQL은 '무엇을'만 말하는 선언형 언어다. 그 텍스트가 실제 행이 되기까지의 파이프라인을 해부한다. 렉서(maximal munch, 예약어는 왜 생기나), 재귀 하강 파서(문법 규칙 하나 = 함수 하나, 서브쿼리에서 파서가 자기 자신을 부른다, 손 파서 vs bison/Lemon의 갈림), 그리고 실행기에서 스트리밍과 materialize가 갈리는 이유. 본론은 조인 3형제로, 모든 조인의 출발점인 중첩 루프(이중 루프), 안쪽을 점 조회로 바꾸는 인덱스 NLJ, O(N+M)의 해시 조인, 그리고 안 만든 정렬 병합까지 선택 기준을 표로. GROUP BY가 왜 정렬(또는 해시)을 요구하는지(GroupAggregate vs HashAggregate), HAVING은 왜 그룹의 WHERE인지. 마지막으로 BETWEEN이 실행기 0줄로 끝난 이유(문법 설탕), LIKE의 백트래킹 two-pointer 매칭과 LIKE '%x%'가 B-tree를 못 타는 이유(트라이그램·역색인으로의 탈출구), uncorrelated 서브쿼리의 1회 실행 캐시, 그리고 NULL의 3값 논리(UNKNOWN, NOT IN + NULL 함정)까지, 시리즈의 실행기 축을 완결한다.

DB 내부 ⑩: Raft, primary가 죽으면 누가 결정하는가, 합의에서 HA DB까지

복제의 최대 약점은 'primary가 죽으면?'이다. replica 승격을 사람이 하면 밤에 전화가 오고, 자동으로 하면 split-brain이 온다. 이건 결국 합의(consensus) 문제고, 답이 Raft다. 리더 선출(임기·과반·무작위 타임아웃), 로그 복제(prevLogIndex 정합 검사), 그리고 '과반에 있어도 현재 임기여야만 커밋'이라는 §5.4.2의 미묘함까지, 다섯 안전성 성질을 결정적 시뮬레이션 네트워크(분단·크래시·재정렬을 재현 가능하게 주입) 위에서 확인한다. 이어서 프로덕션의 조각들: 재시작 후 이중 투표를 막는 지속성(currentTerm/votedFor fsync, §5.1), 무한히 크는 로그를 자르는 스냅샷(§7, 그리고 오프셋 0이 no-op이라 기존 테스트가 버그를 못 잡는 함정), 돌아가는 중에 노드를 넣고 빼는 멤버십 변경(§6, 겹치는 과반), 상태기계 복제(SMR)로 진짜 SQL 엔진을 복제해 리더가 죽어도 살아남는 HA DB, 마지막으로 파티션된 옛 리더가 낡은 값을 주지 않게 하는 선형화 읽기(ReadIndex, §8)까지. 적대적 리뷰가 잡아낸 실제 버그들(스냅샷 미설치 발산, apply 에러 무시, read barrier의 epoch 부재)이 각 절의 정직한 경계다.

DB 내부 ⑨: 복제, 복구의 redo를 스트림으로, base backup + WAL 스트리밍까지

복제의 첫 통찰은 '복제가 거의 공짜'라는 것이다. no-force WAL이 이미 커밋의 순차 스트림이라, replica가 할 일은 크래시 복구의 redo를 '파괴적 일회성'이 아니라 '증분·연속'으로 돌리는 것뿐이다. PostgreSQL에서 walreceiver가 WAL을 받아 쓰고 startup process가 replay하는 그 구조. 이를 소켓에 올리면 walsender/walreceiver가 되는데, 스트림엔 경계가 없어 길이 프레이밍이 필요하고, 수신자는 읽기 전용 fd에 쓸 수 없어 실제로 교착을 밟았다. 마지막은 캡스톤, 곧 진짜 엔진의 커밋이 복제본에서 SELECT되기까지다. 코드보다 어려웠던 건 조용히 깨지는 landmine 셋: 재오픈이 WAL을 truncate하고 LSN을 리셋해 replica가 신규 커밋을 조용히 스킵하는 것, base 스냅샷에 steal된 미커밋 페이지가 딸려오는 것, 카탈로그의 낡은 next_txn이 복제된 행을 미커밋으로 보이게 하는 것. 셋을 정리하면 필연적으로 실제 시스템과 같은 모델, 곧 pg_basebackup + streaming replication에 도달한다. 구조가 그렇게 강제한다.

DB 내부 ⑧: 병렬 실행: latch를 계층별로 걷어내고, 자로 재고, 병목을 고치기

커넥션마다 스레드를 줘도 실행이 굵은 latch 하나로 직렬화돼 있으면 멀티코어는 한 코어처럼 돈다. 그 latch를 계층별로 걷어내는 여정: B+Tree latch crabbing(노드별 rwlock, 자식이 안전하면 조상 해제), 병렬 풀 스캔(워커가 disjoint 페이지 범위를 스레드 안전 버퍼 풀 위에서 동시에, 락 없는 워커별 지역 결과), 실제 SELECT 배선(워커는 가시성+WHERE 판정, 출력은 leader, 직렬과 바이트 동일), 병렬 집계(하다가 조용히 틀리던 materialize cap 절단 버그를 발견해 고침), 그리고 진짜 부분 집계(행을 안 모으고 누적만, PostgreSQL의 Partial→Finalize Aggregate, 메모리 O(1)). 그다음 자로 쟀다. 워밍 최고 2.16배(4워커, 이상 4배 대비), 2~4워커 정점 후 하락. 콜드의 천장은 CPU가 아니라 공유 latch였다: 콜드 캐시에서 풀 latch가 디스크 I/O를 직렬화해 8워커가 0.62배(직렬보다 느림). read-in-progress로 I/O를 latch 밖으로 빼자 같은 조건이 2.39배로 올랐다. 측정→수정→재측정의 A/B로 인과를 확증했다. 모든 단계는 ThreadSanitizer로 data race 0을 계측하며.

DB 내부 ⑦: 저장 엔진의 세 철학: 힙 vs 클러스터드 vs LSM, 그리고 USING lsm

같은 행들을 저장하는 세 가지 철학이 있다. PostgreSQL의 힙(순서 없이 쌓고 인덱스가 RID로 가리킴), InnoDB의 클러스터드(데이터 자체를 PK 순서로, 보조 인덱스는 PK를 들고 이중 조회), RocksDB의 LSM(제자리에서 절대 안 고침: memtable→SSTable→compaction). 한 코드베이스에 셋을 세워 실측하면 교과서의 문장들이 숫자가 된다: PK 점 조회 1.2배·범위 3.8배 클러스터드 우세(지역성), 보조 점 조회는 2배 열세(이중 조회), LSM은 쓰기가 순차화되는 대신 읽기가 여러 SSTable을 뒤진다(read amplification). 마지막은 이 시리즈의 캡스톤이다. LSM을 진짜 엔진의 PK 인덱스로 배선하며(CREATE TABLE ... USING lsm) 부딪힌 벽: MVCC 다중버전 때문에 인덱스는 비유니크 멀티맵이어야 하고, unique LSM으로는 담을 수 없어 dedup 단위를 (key,val)로 바꾼 멀티값 모드가 필요했다. 자체 WAL이 없어 트랜잭션 롤백에 못 끼는 이 LSM 인덱스를 'heap에서 재구축되는 파생 가속기'로 다루는 설계까지. MyRocks가 테이블 단위로 저장 엔진을 고르게 하듯, pluggable 엔진 API의 축소판이다.

DB 내부 ⑥: 비용 기반 옵티마이저, 플래너가 멍청해지는 순간을 통계로 고치기

'인덱스가 있으면 무조건 쓴다'는 규칙은 id > 100 앞에서 무너진다. 행마다 한 번씩 901번의 힙 페치가 7페이지 순차 스캔보다 백 배 비싸게 과금되기 때문이다. 비용 기반 최적화(CBO)의 세 재료를 순서대로 짓는다: ANALYZE(행 수·페이지 수·PK min/max를 재는 통계), 선택도(균등분포 가정으로 매칭 행 수 추정, 히스토그램이 필요한 이유까지), 비용 모델(순차 = 페이지 수, 인덱스 = 1 + 매칭 행수만큼의 힙 페치). 그러면 같은 PK 범위 조건이 매칭 양에 따라 점 조회/인덱스/순차로 갈리는 크로스오버가 실제로 나타난다. '인덱스를 걸었는데 왜 안 타요?'의 정답이다. 후반부는 다중 테이블의 진짜 고민, 조인 순서다: 순서 하나가 2.8배를 가르고, n!을 2ⁿ으로 줄이는 Selinger의 부분집합 DP(1979), 교차곱을 피하는 연결성 규칙, 조인 방법(인덱스 NLJ vs 해시)까지 한 번에 고르는 계획기를 짓는다. EXPLAIN이 실행기와 같은 결정 함수를 공유해 '플랜이 거짓말하지 않는' 원칙도 함께.

DB 내부 ⑤: 진짜 psql이 붙는 서버, PostgreSQL wire protocol 해부

DB 서버와 클라이언트 사이엔 '프로토콜이라는 계약'이 있다. 그 계약만 지키면 상대는 내가 진짜 PostgreSQL인지 구분하지 못한다. PostgreSQL wire protocol v3를 바이트로 뜯는다: 유일한 변칙인 startup 핸드셰이크와 SSLRequest 거절, [타입 1B][길이 4B][페이로드] 프레임, RowDescription/DataRow/CommandComplete의 세 가지 응답 모양, 그리고 psql 프롬프트(=> / =*> / =!>)를 바꾸는 ReadyForQuery 상태 바이트 한 개까지. 400줄 서버로 실제 psql 14가 접속했고, 좋은 계층 분리 덕에 SQL 실행기는 한 줄도 안 바꿨다. 클라이맥스는 두 psql 터미널이다. 한쪽이 미커밋 UPDATE를 쥔 채로 다른 쪽이 옛 버전을 막힘 없이 읽는, MVCC의 존재 이유가 네트워크 너머에서 증명되는 장면이다. 커넥션당 스레드와 그 뒤에 숨은 굵은 latch의 한계까지 정리한다.

DB 내부 ④: 격리, 2PL에서 MVCC 스냅샷 격리까지, reader가 writer를 안 막기까지

동시에 여럿이 읽고 쓸 때 DB는 어떻게 안전한가. 두 철학이 있다. 충돌을 미리 막는 2PL(잠금)과 버전을 갈라 충돌을 피하는 MVCC다. MVCC의 두뇌는 가시성 규칙 한 줄(xmin 커밋 AND xmax 미커밋이면 보인다)이고, 그 규칙이 성립하려면 DELETE조차 지우면 안 된다(xmax 도장). 그 순간 힙을 읽는 아홉 갈래 전부에 가시성 게이트가 필요해지고, '인덱스는 MVCC를 모른다'는 원칙이 선다. 일부러 만든 쓰레기(dead tuple)는 VACUUM이 치우는데, PostgreSQL nbtree처럼 병합 없는 lazy 삭제로 충분한 이유, VACUUM해도 파일이 안 줄어드는 이유까지 코드로 확인한다. 마지막으로 reader의 락을 제거하고 BEGIN 시점 스냅샷(PG의 xmax/xip 축소판)을 고정하면, 한 트랜잭션이 미커밋 UPDATE를 쥐고 있어도 다른 쪽이 옛 버전을 막힘 없이 읽는 진짜 스냅샷 격리가 선다. 그 여파로 PK 인덱스가 다중 버전 멀티맵이 되어야 했던 것까지, C 구현으로 확인하며 정리한다.

DB 내부 ③: WAL과 크래시 복구, redo-only에서 steal + no-force까지

쓰다가 전원이 꺼지면 어떻게 되는가. WAL 프로토콜의 본질(데이터보다 로그 먼저, fsync 한 번이 내구성의 분기점)에서 시작해, 복구 규칙이 'redo 아니면 discard' 하나로 끝나는 가장 단순한 형태를 짓고, 그 단순함의 대가(버퍼 풀보다 큰 트랜잭션이 죽는다)에 부딪혀 steal을 켜고(before-image·undo의 필연), 마지막으로 no-force(커밋 = 로그 fsync 하나)로 옮겨 로그가 진실의 원천이 되기까지. STEAL/FORCE 사분면이 어떤 복구 로직을 필수로 만드는지, 진짜 ARIES(physiological 로깅·pageLSN·CLR·3-패스)와의 거리는 어디인지, fsync의 가격(같은 5천 행 적재가 23배 차이)은 얼마인지, 크래시를 실제로 주입한 테스트와 실측으로 확인하며 정리합니다.

DB 내부 ②: B+Tree 인덱스와 O(log n), 그리고 인덱스는 왜 단순 key→value가 아닌가

인덱스는 왜 이진 트리가 아니라 B+Tree인가. 답은 디스크다(노드=페이지, fan-out이 높이를 무너뜨린다). 가장 어려운 노드 분할(리프는 copy-up, 내부는 push-up), 범위 스캔을 공짜로 만드는 리프 사슬, 그리고 유일성을 내려놓는 순간 부딪히는 문제들, 곧 중복 키의 하한 탐색(>= 한 글자가 조용히 틀린 결과를 만든다)과 '인덱스는 후보일 뿐, 진실은 힙에 있다'는 재검사(recheck)까지. 인덱스 vs 풀 스캔을 실측하면 1천 행에서 11배, 10만 행에서 416배로 벌어진다. O(log n)과 O(n)의 모양 그 자체다. 해시·LSM과의 갈림길, PostgreSQL·InnoDB 대조를 C 구현으로 확인하며 정리한다.

DB 내부 ①: 저장의 뼈대, 페이지·슬롯·행 포맷·힙·버퍼 풀은 어떻게 맞물리는가

관계형 DB의 맨 아래는 다섯 겹이다. 고정 크기 페이지(왜 모든 DB가 블록 단위인가), 슬롯 페이지(가변 행 + 안정적 주소), 행 포맷(null 비트맵), 힙 파일(RID), 그리고 버퍼 풀(캐시인데 안 깨지는 이유). PostgreSQL 8KB·InnoDB 16KB가 왜 그 크기인지, TID/RID가 왜 인덱스의 기반인지, NULL은 왜 값이 아니라 비트로 저장되는지, pin 프로토콜이 어떻게 latch와 분업해 멀티스레드에서 페이지를 지키는지를, C로 미니 DB를 직접 구현하고 ThreadSanitizer로 계측하며 확인한 내용을 1차 자료 기준으로 정리합니다.