안티-엔트로피, 분산 트랜잭션, 합의

복제본을 일관되게 유지하고, 여러 노드에 걸친 트랜잭션을 처리하고, 궁극적으로 모든 노드가 하나의 값에 동의하는 것 — 분산 시스템의 마지막 퍼즐 세 조각이야.

일관성 모델을 정했으면 그걸 실제로 유지하는 메커니즘이 필요해. Read Repair는 읽기 시점에 불일치를 수리하는 가장 자연스러운 방법이야. 여러 복제본에서 응답을 받아 타임스탬프를 비교하고, 최신 값을 반환하면서 오래된 복제본에 최신 값을 보내서 업데이트시키는 거지. 자주 읽히는 데이터는 자연스럽게 일관성이 유지되지만, 안 읽히는 데이터는 영원히 수리되지 않을 수 있어. Hinted Handoff는 다운된 노드 대신 다른 노드가 임시로 쓰기를 저장했다가 복구 시 전달하는 방식인데, 일시적 장애에도 쓰기를 거부하지 않아서 가용성을 유지하면서 나중에 일관성을 회복할 수 있지.

그런데 복제본 전체를 비교하려면 전체 데이터를 보내야 할까? 머클 트리가 이 문제를 풀어. 데이터를 범위로 나누고 각 범위의 해시를 구해 이진 트리로 쌓아 올리면, 루트 해시만 비교해서 동일 여부를 즉시 알 수 있고, 다르면 자식 해시를 재귀적으로 타고 내려가서 불일치 구간만 O(log n) 통신으로 좁힐 수 있어.

정보를 클러스터 전체에 퍼뜨리는 건 가십 프로토콜이야. 각 노드가 주기적으로 무작위 이웃에게 자기가 아는 정보를 보내면, 전염병처럼 O(log n) 라운드만에 전체 노드에 전파돼. 확장성이 좋고 장애가 있어도 우회 경로로 전파되니까 내결함성도 높지. 순수 가십은 대역폭 낭비가 있을 수 있는데, Plumtree가 트리 기반 전파(적극적 연결)와 가십의 내결함성(소극적 연결)을 결합해서 효율과 안정성을 모두 잡아.

안티-엔트로피가 복제본을 수리하는 거라면, 분산 트랜잭션은 여러 노드에 걸친 연산의 원자성을 보장하는 문제야. 여러 노드에 걸친 트랜잭션이 왜 어려우냐면, 노드 A는 커밋 준비가 됐는데 B가 장애를 일으키면 원자성이 깨지거든. 네트워크 왕복도 많고, 가장 느린 참여자가 전체를 지연시키고, 하나만 죽어도 전체가 막혀. 2PC가 이 문제의 기본 프로토콜인데, 코디네이터가 모든 참여자에게 커밋 준비를 묻고, 전원 Yes면 커밋, 하나라도 No면 중단하는 방식이야. 치명적 약점은 코디네이터 장애 — 모두 Yes 투표 후 코디네이터가 죽으면 참여자들이 블로킹 상태에 빠지지.

분산 트랜잭션의 빈도를 줄이는 가장 실용적인 방법은 좋은 파티셔닝이야. 관련 데이터를 같은 파티션에 모으면 대부분의 트랜잭션이 단일 파티션에서 완결되거든. Calvin은 아예 다른 접근을 해 — 모든 노드가 동일한 순서로 트랜잭션을 실행하면 독립적으로 실행해도 같은 결과에 도달하니까 2PC가 필요 없다는 거야. 사전에 읽기/쓰기 셋을 알아야 하는 제약이 있지만, 수용할 수 있으면 매우 효율적이지. Google Spanner는 TrueTime(GPS + 원자 시계)으로 전 세계적 타임스탬프 순서를 보장해서 외부 일관성을 달성하고, 스냅샷 읽기를 락 없이 처리하는 기염을 토해. 궁극적 최적화는 조정 회피야. 카운터 증가처럼 순서에 관계없이 결과가 같은 연산은 조정이 아예 필요 없거든.

그리고 이 모든 것의 기반이 합의 알고리즘이야. 먼저 알아야 할 건 원자적 브로드캐스트와 합의는 동치라는 거야. 모든 노드가 같은 순서로 메시지를 받는 원자적 브로드캐스트를 구현할 수 있으면 합의를 풀 수 있고, 역도 성립해. Paxos는 Leslie Lamport가 1989년에 만든 가장 유명한 합의 알고리즘이야. Proposer가 값을 제안하고, Acceptor가 투표하고, 과반수 쿼럼이 수락하면 값이 결정돼. 과반수끼리는 항상 겹치니까 서로 다른 값이 동시에 결정될 수 없지. 다만 기본 Paxos는 값 하나에 대한 합의만 해서, Multi-Paxos가 안정적 리더를 두고 Phase 1을 한 번만 하면서 연속 합의를 단일 왕복까지 줄여. ZAB는 ZooKeeper에서 쓰이는데 리더만 제안할 수 있고, 에포크로 임기를 관리하고, 리더 선출 시 최신 로그를 가진 노드를 우선하지.

Raft는 "이해 가능한 합의"를 목표로 만들어졌어. 합의를 리더 선출, 로그 복제, 안전성 세 가지로 깔끔하게 분리하고, 강력한 리더 원칙으로 로그가 리더에서 팔로워로만 흘러서 추론이 쉬워. 임기(term) 개념으로 오래된 리더 메시지를 무시하고, 가장 최신 로그를 가진 노드만 리더가 될 수 있게 안전성을 보장하지. etcd, CockroachDB, TiKV가 Raft를 쓰는 이유야.

노드가 거짓말까지 할 수 있는 비잔틴 장애를 견뎌야 하면 훨씬 어려워져. N명 중 f명이 배신자면 N >= 3f + 1이어야 합의가 가능하고, PBFT 같은 알고리즘은 O(n^2) 메시지 복잡도라서 노드가 늘면 비용이 급증해. 전통적 DB보다는 블록체인 같은 환경에서 주로 쓰이는 이유지.

---

정리

7장 읽고 기억할 거 세 가지:

1. 머클 트리는 O(log n) 통신으로 복제본 불일치를 효율적으로 찾고, Read Repair와 Hinted Handoff가 실시간으로 일관성을 회복한다. 2PC는 분산 트랜잭션의 기본이지만 코디네이터 장애 시 블로킹 문제가 있다.
2. Calvin은 트랜잭션 순서를 미리 결정해서 합의 없이 동일 결과에 도달하고, Spanner는 TrueTime으로 전 세계적 타임스탬프 순서를 보장한다.
3. Raft는 합의를 리더 선출·로그 복제·안전성으로 분리해서 이해하기 쉽게 설계했고, Paxos의 과반수 쿼럼 원칙 위에서 현대 분산 시스템의 표준이 되었다.