분산 트랜잭션과 합의 — 여러 노드가 하나의 결정에 이르는 법

한 대의 데이터베이스에서 COMMIT은 결정이라기보다 선언에 가깝다. 되돌릴 근거도, 다시 적용할 근거도, 남이 끼어들지 못하게 막는 장치도 전부 그 한 프로세스 안에 있다. 트랜잭션과 동시성 제어가 다루는 세계가 그쪽이다 — Undo와 Redo가 원자성과 영속성을 각각 받치고, 락과 MVCC가 서로 간섭하지 않게 막는다. 무엇을 커밋할지 물어볼 상대가 없으니 협상도 없다.

파티셔닝의 출발점에서 시작한 축을 따라 데이터를 나누고 복사하고 나면 이 전제가 무너진다. 하나의 업무가 여러 노드나 파티션에 걸치면 어떤 노드에서는 성공하고 어떤 노드에서는 실패할 수 있다. 원자성을 그대로 유지하려면 이제 모든 노드가 트랜잭션의 결과에 동의해야 한다. 커밋은 선언에서 합의로 성격이 바뀐다.

이 글은 그 합의를 다룬다. 2PC가 무엇을 보장하고 어디서 무너지는지, 3PC·Calvin·Spanner와 Saga가 그 대가를 어디로 옮기는지, 한 층 아래에서 하나의 값을 확정하는 Paxos·Raft·PBFT가 각각 어떤 장애를 견디도록 설계됐는지, 그리고 같은 합의 위에 서면서도 데이터베이스와 갈라지는 분산 원장이 무엇인지다.

2PC — 커밋을 두 단계로 쪼갠다

2단계 커밋은 이름 그대로 커밋을 둘로 나눈다. 모든 참가자에게 "커밋할 수 있는가"를 묻고, 전원이 그렇다고 답한 뒤에야 "커밋하라"를 보낸다. 묻는 쪽이 코디네이터, 답하는 쪽이 코호트다.

코디네이터가 지휘하는 두 단계

도식에서 눈여겨볼 자리는 코호트가 ok를 보낸 직후다. 그 ok는 "커밋했다"가 아니라 "커밋하겠다고 약속했다" 는 뜻이다. 약속한 이상 코호트는 물러설 수 없고, 2단계 메시지가 올 때까지 자기 상태를 붙들고 있어야 한다.

코디네이터는 어느 시점에 죽었는가

2PC의 성질은 코디네이터가 언제 사라지느냐로 완전히 갈린다.

두 행의 차이를 만드는 것은 시간이 아니라 약속이다. 준비 요청 전이라면 코호트에게 의무가 없어 혼자 판단해도 안전하지만, ok를 보낸 뒤로는 커밋도 중단도 혼자 고를 수 없다. 다른 코호트가 no를 보냈을 수도 있고 그것을 아는 것은 코디네이터뿐이다. 이 상태를 in-doubt라 부른다.

단일 DB에서 후행 트랜잭션이 선행을 기다리는 것은 오류가 아니라 정상 동작이고, 앞이 끝나면 반드시 풀린다. in-doubt 블로킹은 풀어 줄 주체가 이미 죽어 있다.

2PC가 매 커밋마다 내는 비용

네 행 중 앞의 셋은 대가이고 마지막 한 행은 그럼에도 2PC가 살아남은 이유다. 블로킹은 장애가 났을 때만 아프지만, 디스크 로그 선기록은 장애가 없어도 매번 지불한다. 결정을 잃어버리면 코호트를 영원히 매달아 두게 되므로 코디네이터는 응답하기 전에 디스크에 먼저 적어야 하고, 그 쓰기가 커밋 경로 위에 얹힌다. 셋째 행이 "반드시"인 이유도 같다 — 대비책 없이 2PC를 켜면 단일 장애점이 커밋 경로 한복판에 선다.

2PC 다음의 세 갈래

2PC의 블로킹은 결정 권한이 코디네이터 한 곳에 몰려 있어 약속한 코호트가 혼자 판단할 수 없다는 데서 온다. 아래 세 알고리즘은 그 구조의 서로 다른 층을 건드리고, 겨냥하는 것도 블로킹 하나가 아니다.

세 행이 손대는 층이 다르다. 3PC는 단계를 늘려 코호트끼리 상태를 공유하게 하고, Calvin은 커밋에서 합의를 빼내 순서 결정으로 옮기며, Spanner는 2PC 위에 시계를 얹는다. 3PC의 개선점이 블로킹 완화이지 제거가 아니라는 표기도 그대로 읽을 값어치가 있다.

Spanner가 특별한 이유는 하드웨어로 CAP의 제약을 우회하지 않고, 불확실성의 상한을 알아냈다는 점이다.

TrueTime은 "지금 시각"이 아니라 "지금 시각은 [earliest, latest] 구간 안에 있다"를 반환한다. 커밋 시 그 구간이 지날 때까지 의도적으로 기다리면(commit-wait), 전역 순서가 보장된다.

대가는 매 커밋마다 수 밀리초의 대기다. 즉 Spanner도 PACELC의 EC(정상 시 일관성 우선, 지연 지불)를 선택한 것일 뿐이다.

Saga — 원자적 커밋 자체를 포기한다

MSA에서는 서비스마다 DB가 분리되어 2PC를 걸 대상 자체가 없다. Saga는 긴 트랜잭션을 로컬 트랜잭션의 연쇄 + 보상 트랜잭션으로 대체한다. 각 단계는 자기 DB에서 곧바로 커밋하고, 실패하면 앞 단계를 되돌리는 별도 트랜잭션을 실행한다.

실선과 점선의 방향이 반대인 것이 이 그림의 전부다. 정상 흐름은 앞으로 가고 보상은 뒤로 되짚는데, 그 경로가 롤백이 아니라 직접 작성한 취소 로직이라는 것이 2PC와의 차이다.

누가 다음 단계를 부르는가

두 방식의 대립은 앞 절에서 본 코디네이터 문제의 재판이다. 안무는 지휘자를 없애 단일 장애점을 지우는 대신 전체 흐름이 어디에도 적혀 있지 않게 되고, 오케스트레이션은 흐름을 한곳에 모으는 대가로 그 한곳을 다시 단일 장애점으로 만든다. 마지막 행이 실무 기준이다.

2PC와 Saga는 무엇을 맞바꾸는가

표에서 가장 비싼 행은 첫째 행이다. 격리성이 없다는 말은 결제는 승인됐고 재고 차감은 아직인 상태를 다른 트랜잭션이 정상적으로 조회한다는 뜻이다. 2PC의 블로킹은 그 중간 상태를 감추려고 락을 붙들던 비용이었으므로, Saga가 얻은 "블로킹 없음"과 잃은 격리성은 같은 거래의 앞뒤다.

Saga의 실전 함정은 보상 불가능한 작업이다. 메일 발송, 외부 결제 승인은 되돌릴 수 없다. 그래서 되돌릴 수 없는 단계는 Saga의 마지막에 배치(pivot transaction 이후)하는 것이 설계 원칙이다.

합의 알고리즘 — 하나의 값을 확정한다

지금까지는 "이 트랜잭션을 커밋할 것인가"에 관한 합의였다. 한 층 아래에 더 일반적인 문제가 있다 — 여러 노드가 하나의 값에 동의하는 문제다. 리더가 누구인지, 로그의 5번 칸에 무엇이 들어가는지가 전부 여기로 환원된다. 아래 세 알고리즘은 같은 문제를 서로 다른 장애 가정 아래에서 푼다.

Paxos

그리스 섬 팍소스의 입법·투표 방식에서 유래했다. 여러 노드가 하나의 값에 합의하기 위해 사용하며, 노드 간 통신이 불안정하거나 일부 노드가 실패하는 환경에서도 안전하게 동작하도록 설계되었다.

세 역할은 물리적 노드 구분이 아니다. 한 노드가 동시에 여러 역할을 수행할 수 있다.

핵심은 "이미 수락된 값이 있으면 제안자가 자기 값을 버리고 그 값을 이어받는다"는 규칙이다. 이 한 줄이 서로 다른 두 값이 동시에 합의되는 것을 막는다. 도식의 PROMISE에 "이전 수락 제안 없음"이 붙어 있는 이유도 여기에 있다 — 이전 값이 있었다면 제안자가 보낸 'car'는 그 값으로 바뀌었을 것이다.

이 규칙이 작동하려면 제안자가 과반의 수락자에게 묻고 받아야 한다. 한 대에게만 묻고 받는다면 두 제안자가 서로 다른 수락자에게서 각각 "이전 값 없음"을 듣고 서로 다른 값을 확정할 수 있다. 임의의 두 과반은 반드시 겹치므로, 앞서 수락된 값이 있었다면 새 제안자의 응답 집합에 그것이 반드시 들어온다. 뒤에 나오는 Raft가 과반으로 얻는 것과 같은 성질이다. 이 보충은 이 글의 정리다.

Raft

Paxos보다 이해와 구현이 쉬운 알고리즘이다.

Paxos의 세 역할이 한 노드에 겹칠 수 있었던 것과 달리, 여기서 셋은 한 노드가 시점마다 하나씩 갖는 상태다. 그래서 도식도 상태 전이로 그려진다.

세 개념은 도식의 화살표와 짝을 이룬다. 하트비트가 끊기면 팔로워가 후보자가 되고, 과반 득표가 리더를 만들며, 그 뒤는 로그 복제가 리더의 일상이다.

Raft가 스플릿 브레인을 막는 방식은 두 조건으로 끝난다.

리더는 과반의 표를 받아야 하고, 표는 term당 1회만 준다. 과반은 정의상 두 집합이 동시에 존재할 수 없으므로, 리더는 같은 term에서 항상 최대 1명이다.

그리고 Request Vote에 최종 로그 ID를 실어 보내는 이유는, 자기보다 로그가 뒤처진 후보에게는 표를 주지 않기 위해서다. 이로써 커밋된 로그를 가진 노드만 리더가 될 수 있다.

PBFT — 거짓말하는 노드까지 견딘다

Paxos와 Raft는 노드가 죽거나 응답하지 않는 상황만 가정한다. 노드가 틀린 값을 적극적으로 퍼뜨리는 경우는 다루지 않는다. 그쪽이 비잔틴 장군 문제이고, PBFT가 그 가정 위에서 동작한다.

두 표기는 같은 식을 방향만 바꿔 쓴 것이다. f = (n-1)/3을 n에 대해 풀면 n = 3f + 1이 된다. 숫자를 넣어 확인하면 f = 1일 때 n = 4이고, 역으로 n = 4를 (n-1)/3에 넣으면 f = 1이 나온다. 거짓말하는 노드 하나를 견디는 데 전체 4대가 든다는 뜻이다.

f = 1을 대입하면 각 문턱이 prepare 2개, commit 3개, 클라이언트 응답 2개가 된다. 마지막 문턱이 f+1인 이유는 f개까지는 거짓 응답일 수 있으므로, f+1개가 같아야 그중 최소 하나가 정직한 노드의 답이기 때문이다. 준비 단계에서 팔로워가 리더가 아니라 모든 노드에게 메시지를 보내는 것도 같은 가정에서 나온다 — 리더 자체가 거짓말할 수 있으므로 팔로워끼리 직접 대조해야 한다.

네 행이 위에서 아래로 인과로 이어진다. 장애 모델에 거짓말을 넣는 순간 노드 요구량이 2f+1에서 3f+1로 오르고(f = 1이면 3대에서 4대로), 팔로워끼리 전부 대조해야 하므로 메시지가 O(N)에서 O(N²)로 뛴다. 마지막 행의 적용 구분은 그 비용을 누가 낼 만한가에 대한 답이다.

분산 원장은 데이터베이스인가

세 정의가 한 단계씩 조건을 더한다. 분산 데이터베이스와 분산 원장을 가르는 것은 데이터가 흩어져 있느냐가 아니라 누가 관리하느냐다.

분산 원장의 특징은 다음과 같다. P2P 분산 아키텍처와 동일하고, 비잔틴 장군 문제가 존재하며(악의적 노드), 모든 노드가 동일 데이터를 유지하고, 하나의 기관이 아닌 다수 이해관계자가 참여하며, 합의 프로세스가 반드시 필요하다. 앞 절에서 PBFT가 허가형 블록체인에 배치된 이유가 두 번째 항목에 있다.

블록체인을 쓰지 않아도 되는 경우

Hyperledger Besu의 판단 차트는 네 가지 조건을 든다.

기술 선택 판단에서 가장 실용적인 체크리스트다. "신뢰할 수 없는 다수의 참여자가 같은 데이터에 쓰기를 해야 하는가" — 이 질문에 Yes가 아니면 분산 원장은 과잉이다.

뒤의 세 조건이 각각 그 질문의 한 조각을 부정한다. 2번은 "쓰기"를, 3번은 "신뢰할 수 없는"을, 4번은 "다수가 직접"을 지운다. 하나라도 지워지면 남는 것은 비용뿐이다 — 허가형 원장을 쓴다면 앞에서 본 3f+1대의 노드와 O(N²)의 메시지가 그것이다.

정리

이 글이 다룬 선택들을 질문 단위로 다시 배열했다.

다섯 행이 같은 모양이다. 무엇을 보장할지 정하면 그 값을 대기 시간·메시지 수·노드 대수 중 어딘가로 내야 한다. 청구서를 없앨 수는 없고 받을 자리를 고를 수 있을 뿐이다.

여기까지가 이 시리즈가 다룬 선택지 전부다. 마지막 편 데이터베이스 확장 Q&A는 이 선택지들을 트레이드오프와 장애 시나리오에 놓고 문답 형식으로 종합한다.