Database Concurrency Control
다중 트랜잭션이 동시에 DB를 수정할 때 일관성을 보장하면서 처리량을 극대화하는 락 전략과 알고리즘
핵심 개념
데이터베이스 동시성 제어는 동시에 실행되는 읽기/쓰기 연산이 서로 간섭하지 않도록 하면서 가능한 높은 동시성을 달성하는 기법이다. B-tree 인덱스 관리에서는 페이지(노드) 수준의 래치(latch)와 락(lock) 전략이 핵심이다.
B-tree에서의 동시성 문제
B-tree의 구조 변경 작업(SMO, Structure Modification Operation) — 노드 분할(split), 병합(merge) — 은 여러 노드를 동시에 수정하므로 동시 검색·삽입과 충돌 위험이 있다.
전통적 접근의 한계
- 락 커플링(Lock Coupling): 부모-자식 노드를 동시에 래치로 보호 → 동시성 제한
- 락 서브트리: 수정 범위를 트리의 서브트리 단위로 잠금 → 범위 계산 복잡, MySQL InnoDB의 어려운 점
Blink-tree: 락 없는 고동시성 B-tree
Lehman-Yao(1981)가 제안한 Blink-tree는 두 가지 작은 추가로 lock-free 검색을 가능하게 한다:
핵심 변경
- 링크 포인터(Link Pointer): 각 노드에 우측 형제 노드로의 포인터 추가
- 하이 키(High Key): 각 노드에 저장 가능한 최대 키 값 기록
작동 원리
검색 중 SMO(노드 분할)가 발생하면:
- 찾는 값이 현재 노드의 하이 키보다 크면 → 링크 포인터로 우측 노드로 이동
- 부모 노드와의 동시 래치 보유 불필요
PostgreSQL vs. InnoDB 비교
PostgreSQL Blink-tree
- 검색 시 현재 레이어에만 래치 보유 (부모-자식 동시 보유 없음)
- SMO 시 최대 3개 노드 래치 동시 보유 (자식, 부모, 부모의 링크 페이지)
- 검색이 SMO를 블록하지 않음 → 더 높은 동시성
| 연산 | 최대 동시 래치 수 |
|---|---|
| 검색 | 1 (읽기) |
| 삽입(상승 중) | 1 (쓰기) |
| 삭제(상승 중) | 2 (쓰기) |
MySQL InnoDB
- 락 커플링 사용: 하강 시 부모-자식 동시 래치 보유
- 락 서브트리 범위 계산 복잡도 높음
- Bayer-Schkolnick(1977) 알고리즘 기반
실무적 시사점
- 읽기 집약적 워크로드: Blink-tree 방식이 SMO와 검색이 충돌하지 않아 처리량 높음
- 쓰기 집약적 워크로드: 락 세분성(granularity)이 동시 삽입 성능의 핵심 결정 요인
- 인덱스 설계: 인덱스 수준 락 없이 페이지 수준 래치만으로 안전성 달성 가능