낙관적 락의 시작에는 락이 없었다
들어가며
동시성 제어의 방법으로 낙관적 락을 도입해서 해결했다는 이야기를 종종 본다. 낙관적 락이라는 것이 보통 트랜잭션에서 동시 처리를 막지 않고, 사후에 버전 비교 등을 통해 처리하는 방식을 지칭한다고 알고 있었다. 그런데 이 낙관적 락이라는 것이 무슨 락을 낙관한다는 건지 그다지 선명하게 다가오지는 않았다.
그래서 이번 글을 통해 낙관적 락의 구현 자체보다는 이 개념의 시작과 문제 의식을 한번 살펴보려 한다.
락은 쉽지만 비싸다
락은 보통 우리가 DB 트랜잭션에서 마주하는 개념이다.
흔히 보는 계좌 이체 예시를 보자. 만약 각기 다른 트랜잭션(T1, T2)이 동시에 읽기, 쓰기를 처리한다면 어떻게 될까? 100의 잔액이 있고, 실행 시점이 겹치면 잔액 계산이 엉망이 되는 아래와 같은 상황이 발생한다.
balance = 100
T1: 100 읽음
T2: 100 읽음
T1: +50 → 150
T2: -30 → 70
결과: 70
→ T1의 +50이 사라졌다.이런 상황 때문에 동시성에 대한 제어가 필요하다. 가장 익숙한 대응으로는 트랜잭션 사이에 락을 걸어서 이를 해결하는 방법이 있다. 데이터가 충돌하기 전에 막아버리는 것이다.
T1 ─ lock ─────── unlock
T2 ───── wait ────T1이 먼저 락을 획득하면 T2는 기다리게 된다. T1이 100을 150으로 변경하고 락을 해제한 뒤에야 T2가 작업을 수행하므로, 최종 잔액은 120이 된다.
만약 충돌이 적다면
만약 이런 충돌이 적다는 가정이 있다면 다른 방법을 써볼 수 있을까? 여기서 등장하는 것이 바로 우리가 흔히 낙관적 락(Optimistic Locking)이라고 부르는 방식이다. 낙관적 락의 기본 아이디어는 충돌을 미리 막기보다는 일단 실행한 뒤에 나중에 충돌 여부를 검증하겠다는 것이다.
T1 ─ 'B' read ─ calculate ─ validate ─ write
T2 ─ 'B' read ─ calculate ───── validate ─ 폐기 후 재실행
'B'는 balance락을 쓰지 않는다면 어떻게 락을 쓸 때와 같은 정합성을 보장할 수 있을까? 이를 위해 도입된 것이 바로 ‘검증(Validation)’ 단계다.
T2가 B를 읽은 뒤 T1이 B를 변경했다면, T2가 처음 읽었던 상태를 그대로 반영하는 것은 문제가 된다. 따라서 T2는 자신의 작업을 반영하기 전에, 자신이 작업하는 동안 다른 트랜잭션과 충돌이 발생했는지 검증한다. 충돌이 발견되면 T2의 작업을 폐기하고 다시 실행한다.
이런 폐기와 재실행이 매번 발생한다면, 굳이 낙관적 락을 사용할 필요는 없다. 충돌이 있을 때는 이렇게 처리하지만, 이 상황 자체가 거의 없을 것이라고 생각하기 때문에 낙관적 락이 효과적이라고 판단하는 것이다.
얼마나 낙관적일 때 쓸 수 있을까
그렇다면 저자들은 충돌이 얼마나 드물다고 보았던 것일까? 이 아이디어를 처음 제안한 것으로 알려진 Kung과 Robinson의 1981년 논문 On Optimistic Methods for Concurrency Control 에서 답을 찾을 수 있다. 다만 논문이 계산한 것은 트랜잭션 일반의 충돌 확률이 아니다. B-tree에 키를 넣는 삽입 두 개를 놓고, 한 삽입이 동시에 실행 중인 다른 삽입을 재실행시킬 확률을 구한다. 그리고 트리의 깊이가 3이고, 한 페이지가 자식을 199개까지 가지며, 맨 아래 페이지가 1만 장이라는 조건에서 그 확률의 상한이 0.0007, 즉 0.07%다.
이 숫자가 어디에서 나온 것인지는 생각보다 재미있다. 키를 하나 넣으면 보통 맨 아래 페이지 한 장만 고치고 끝나지만, 그 페이지가 가득 차 있으면 둘로 쪼개면서 위층까지 번진다. 논문은 이렇게 번지는 정도까지 따져서 두 삽입이 겹칠 확률을 계산한다.
낙관적 락이라는 말은 논문에 없다
논문에서 또 흥미로운 지점은 ‘optimistic locking’이라는 표현 자체가 등장하지 않는다는 것이다. 논문은 제목에서부터 optimistic methods for concurrency control이라는 표현을 사용하고, 초록에서는 nonlocking concurrency controls라는 표현을 사용한다. 즉, 저자들이 처음 제안한 것은 새로운 종류의 락이라기보다, 락을 사용하지 않고 동시성을 제어하는 방법이었다.
1981년에 동시성 제어가 필요했던 이유
오늘날 DB에서는 락을 건다고 해도, 행 단위 락으로 처리되거나 수십GB의 메모리에 캐싱된 데이터로 처리될 수도 있으며, 디스크 I/O가 발생하더라도 SSD를 사용하면 수십 밀리초가 아니라 수백 마이크로초 수준으로 처리된다. 이런 환경에서는 락의 비용을 그렇게 크게 체감하기 어려울 수 있다.
반면 논문이 나온 1981년에는 사정이 달랐다. 논문은 데이터베이스의 상당 부분이 보조기억장치에 있으면 자주 접근되는 노드를 잠근 채 그 접근을 기다리게 되고, 그동안 동시성이 크게 떨어진다는 것을 락의 단점으로 꼽는다.
이렇듯 하드웨어적 한계가 명확했기에, 동시성 제어의 방식을 바꾸자는 아이디어가 등장한 셈이라고 볼 수 있다. 그렇다고 해도 락을 걸지 않고 동시성을 제어할 수 있다는 생각을 했다는 것이 지금에 봐도 혁신적인 것 같다.
마치며
낙관적 락이라는 단어가 크게 와닿지가 않아서 이번 글을 써보려 했는데, 막상 그 시작점을 따라가 보니 동시성 제어 자체에 대해 먼저 이해해야 할 것들이 많았다.
그 중 특히 자세히 써보려고 했던 0.07%라는 숫자가 어떻게 나왔는지는 이 글에서 다루지 않았다. B-tree의 구조와 페이지 분할 확률을 따라가다 보면 이 숫자가 어떤 가정 위에서 나온 계산인지 확인할 수 있다. 다음 글에서는 이 계산을 직접 따라가 보고, 왜 B-tree에서 충돌 가능성이 낮다고 판단할 수 있었는지 살펴보려 한다.