데이터베이스: 인덱스와 트랜잭션

주문 내역 화면이 처음에는 빨랐는데 주문이 수백만 건 쌓이자 몇 초씩 걸린다. 같은 주에 한정판 상품의 재고가 1개였는데 주문이 2건 확정됐다는 문의도 들어온다. 첫째는 데이터베이스가 행을 어떻게 찾느냐의 문제고, 둘째는 동시에 들어온 요청이 같은 행을 어떤 순서로 읽고 쓰느냐의 문제다. 이 장은 둘을 인덱스와 트랜잭션으로 나눠 본다. 개념 정리는 B-트리, 인덱스, ACID 노트에 있다.

전체 스캔과 인덱스 탐색

데이터베이스는 표와 인덱스를 고정 크기 페이지(page) 단위로 저장하고 읽는다. PostgreSQL의 페이지는 보통 8 kB다(PostgreSQL 문서: 페이지 구조). 그래서 "몇 행을 비교했나"보다 "페이지를 몇 번 읽었나"가 비용을 더 잘 말해 준다. 행은 들어온 순서대로 쌓일 뿐 user_id 순서로 정렬돼 있지 않다. 인덱스가 없으면 찾는 값이 어느 페이지에 있는지 알 길이 없다.

B-트리 높이와 복합 인덱스 순서

인덱스가 빠른 이유는 높이에 있다. 페이지 하나에 키가 몇 개 들어가느냐(팬아웃, fanout)는 키 크기와 페이지 크기에 따라 다르다. 계산을 위해 페이지 하나에 키가 300개 들어간다고 치자. 높이가 1이면 300개, 2면 300² = 9만 개, 3이면 300³ = 2,700만 개를 가리킨다.

행이 2,700만 개여도 뿌리부터 잎까지 페이지 3개만 읽으면 된다. 전체 스캔은 행 수에 비례하고(O(n)), 인덱스 탐색(index scan)은 높이에 비례한다(O(log n). O 표기는 『개발 수학』 Unit 3). 행이 300배 늘어야 높이가 한 층 는다. 이렇게 "몇 층인가", 곧 300을 몇 번 거듭 곱해야 n에 이르는가를 세는 수가 log n이다. 거듭제곱(300³)과 로그는 같은 관계를 반대 방향에서 묻는 것이다. 로그가 낯설면 『개발 수학』 Unit 2를 먼저 보자. 행이 늘어날 때 트리는 잎 페이지가 넘치면 쪼개고, 뿌리까지 넘치면 그 위에 새 뿌리를 얹어 한 층 높아진다(PostgreSQL 문서: B-Tree 구현).

열 여러 개로 만든 복합 인덱스(multicolumn index)는 첫 열로 정렬하고, 첫 열이 같으면 둘째 열로 정렬한 목록이다. 전화번호부가 성으로 정렬되고 성이 같으면 이름으로 정렬된 것과 같다. 성만 알면 범위를 좁힐 수 있지만 이름만 알면 처음부터 훑어야 한다. PostgreSQL 문서는 규칙을 이렇게 적는다. 앞쪽(왼쪽) 열들의 같음(=) 조건, 그리고 같음 조건이 없는 첫 열의 범위 조건이 인덱스에서 훑을 구간을 좁힌다(PostgreSQL 문서: 복합 인덱스).

같은 두 열인데 순서만 바꿔도 훑는 양이 "그 사용자의 최근 주문"과 "모든 사용자의 최근 주문"으로 갈린다. 같음 조건을 거는 열을 앞에, 범위 조건을 거는 열을 뒤에 두는 것이 기본이고, 열 순서부터 맞추는 것이 먼저다. 예외가 하나 있다. PostgreSQL 18부터는 앞 열에 같음 조건이 없어도 스킵 스캔(skip scan)으로 뒤 열 조건까지 써서 훑는 구간을 줄이는 경우가 있다. 하지만 앞 열의 값 종류가 적을 때만 효과가 나는 최적화다(PostgreSQL 18 릴리스 노트, PostgreSQL 문서: 복합 인덱스).

트랜잭션과 격리 수준

트랜잭션(transaction)은 여러 문장을 하나로 묶어 모두 반영하거나 하나도 반영하지 않는 단위다. ACID는 그 약속이다. 원자성(Atomicity), 일관성(Consistency), 격리성(Isolation), 지속성(Durability). 이 중 격리성은 정도를 고를 수 있다. 완전히 격리하면 동시에 도는 트랜잭션들이 차례로 하나씩 돈 것과 같은 결과를 내지만 그만큼 기다리거나 실패해 다시 하는 일이 늘어난다. 격리 수준(isolation level)은 어떤 이상 현상까지 허용할지를 정한 단계다. 이상 현상은 셋이다. 더티 리드(dirty read)는 다른 트랜잭션이 아직 커밋하지 않은 값을 읽는 것이다. 반복 불가능한 읽기(nonrepeatable read)는 같은 행을 두 번 읽었는데 그사이 다른 트랜잭션이 커밋해 값이 바뀐 것이다. 팬텀 읽기(phantom read)는 같은 조건으로 두 번 조회했는데 행 집합이 달라진 것이다.

표는 PostgreSQL 문서의 표에서 세 열만 옮긴 것이다. 원표에는 직렬화 이상(serialization anomaly) 열이 더 있다(PostgreSQL 문서: 트랜잭션 격리).

기본값은 데이터베이스마다 다르다. PostgreSQL은 Read Committed가 기본이다(PostgreSQL 문서). MySQL InnoDB는 Repeatable Read가 기본이다(MySQL 문서: InnoDB 격리 수준). 같은 코드를 두 데이터베이스에 올리면 동시성 동작이 다를 수 있다는 뜻이다. 다음 절에서 볼 잃어버린 갱신(lost update, 두 트랜잭션이 같은 값을 읽고 각자 고쳐 써서 한쪽 변경이 사라지는 현상)은 이 표에 없지만, 기본 격리 수준에서 실무에 가장 자주 나오는 문제다. 격리 수준을 Repeatable Read로 올리면 막히는지도 데이터베이스마다 다르다. PostgreSQL Repeatable Read에서는 트랜잭션이 시작된 뒤 다른 트랜잭션이 고치고 커밋한 행을 고치려 하면 could not serialize access due to concurrent update 오류로 실패하고, 애플리케이션이 트랜잭션을 처음부터 다시 시도해야 한다(PostgreSQL 문서: Repeatable Read). MySQL InnoDB Repeatable Read에서는 SELECT만 트랜잭션 시작 때의 스냅숏을 읽고, UPDATE는 오류 없이 다른 트랜잭션이 커밋한 최신 행을 고친다(MySQL 문서: 일관된 읽기). 그래서 읽어 둔 값으로 계산해 쓰는 코드는 MySQL의 기본 격리 수준에서 잃어버린 갱신을 그대로 겪는다.

재고 차감 경쟁

재고를 줄이는 가장 흔한 코드는 읽고(SELECT stock), 애플리케이션에서 1을 빼고, 그 값을 쓰는(UPDATE ... SET stock = 0) 세 단계다. 트랜잭션으로 묶어도 Read Committed에서는 두 트랜잭션이 같은 값을 읽을 수 있다.

읽고 → 고치고 → 쓰기(read-modify-write)에서 T1 읽기 → T2 읽기 → T1 쓰기 → T1 커밋 → T2 쓰기 → T2 커밋 순서로 실행하면 둘 다 재고 1을 읽고 0을 쓴다. 재고는 0인데 주문은 2건이다. T1이 커밋하기 전에 T2가 쓰려 하면 T2는 행 잠금(row-level lock)을 기다린다. 하지만 기다린 뒤에도 자기가 읽어 둔 1에서 뺀 0을 그대로 쓴다. 잠금은 쓰기끼리 겹치지 않게 할 뿐, 낡은 값을 읽은 것까지 고쳐 주지 않는다.

막는 방법은 두 가지다. 첫째, 읽을 때부터 잠근다. SELECT ... FOR UPDATE는 읽은 행을 수정할 것처럼 잠가서, 다른 트랜잭션의 UPDATE나 FOR UPDATE가 이 트랜잭션이 끝날 때까지 기다리게 한다(PostgreSQL 문서: 행 수준 잠금). 기다리던 쪽은 잠금이 풀린 뒤 갱신된 행을 받는다. 그래서 T2는 0을 읽고 품절 처리한다. 단, Repeatable Read나 Serializable에서는 기다린 행이 그사이 바뀌었으면 오류가 난다(같은 문서).

둘째, 읽기와 쓰기를 문장 하나로 합친다. UPDATE items SET stock = stock - 1 WHERE id = 1 AND stock > 0. PostgreSQL Read Committed에서 둘째 UPDATE는 첫째가 커밋하기를 기다린 뒤, 갱신된 행으로 WHERE 조건을 다시 확인한다(PostgreSQL 문서: 트랜잭션 격리). 재고가 0이 됐으니 stock > 0이 거짓이고, 바뀐 행 수가 0이다. 애플리케이션은 바뀐 행 수가 0이면 품절로 처리하면 된다. 문장 하나라 잠금을 쥐는 시간도 짧다. 이 동작은 PostgreSQL 문서 기준이다. 다른 데이터베이스는 그 문서에서 확인하자. 트랜잭션 경계를 코드에서 어떻게 잡는지는 @Transactional 노트에 있다.

n = 3 → 재시도 ?번
n = 4 → 재시도 ?번