[DDIA 9장] 일관성과 합의 — 불확실한 분산 환경에서 정확성 보장하기

[DDIA 9장] 일관성과 합의 — 불확실한 분산 환경에서 정확성 보장하기

Designing Data-Intensive Applications (Martin Kleppmann) 를 읽으며 정리한 시리즈입니다.
1장 | 2장 | 3장 | 4장 | 5장 | 6장 | 7장 | 8장

---

들어가며

8장에서 분산 시스템의 불확실성을 배웠다. 네트워크는 패킷을 유실시키고, 클럭은 제멋대로 흐르고, 프로세스는 예고 없이 멈춘다. 이 모든 게 당연하다는 전제를 깔았다.

그렇다면 이 혼돈 속에서 어떻게 올바른 시스템을 만들 수 있는가?

9장은 그 답을 다룬다. 일관성 보장(Consistency Guarantees) 과 합의 알고리즘(Consensus Algorithms). 불확실성을 전제하면서도 시스템이 "올바르게 동작한다"는 것을 보장하는 방법이다.

2부의 마지막 장이자 이론적으로 가장 깊은 장이다. 쉽지 않지만, 이 장을 이해하면 ZooKeeper가 왜 존재하는지, Kafka가 왜 리더 선출에 특정 알고리즘을 쓰는지, etcd가 왜 그토록 신뢰받는지가 연결된다.

---

일관성 보장의 스펙트럼

모든 복제 DB는 복제 지연 문제를 가진다. 리더에 쓴 데이터가 팔로워에 즉시 반영되지 않는다. 이 현실 위에서 어느 수준의 일관성을 보장할 것인가가 핵심 선택이다.

일관성 보장은 스펙트럼으로 존재한다. 약한 보장에서 강한 보장으로 갈수록 성능이 나빠지고 구현이 복잡해진다.

약한 보장 ←————————————————————→ 강한 보장
최종 일관성    인과적 일관성    선형화 가능성
(Eventual)   (Causal)       (Linearizability)

---

선형화 가능성 (Linearizability)

가장 강한 일관성 보장이다. 시스템이 하나의 데이터 복사본만 있는 것처럼 동작하게 만드는 것이다.

핵심 아이디어

어느 클라이언트가 어느 시점에 읽어도, 그 이전에 이미 커밋된 쓰기가 반영된 값을 읽는다. "가장 최근에 쓴 값"이 무엇인지에 대해 모든 클라이언트가 동의한다.

일상적인 비유로 설명하면 이렇다. 월드컵 결승전 결과를 전화로 들었다. 그 순간부터 인터넷 어디서 검색해도 같은 결과가 나와야 한다. 어떤 서버는 아직 "경기 중"이고 어떤 서버는 "한국 우승"이라고 하면 선형화 가능성이 깨진 것이다.

선형화 가능성이 필요한 상황

리더 선출: 여러 노드 중 정확히 하나가 리더가 되어야 한다. "자신이 리더다"라는 값에 대해 모든 노드가 동의해야 한다. ZooKeeper, etcd가 이 용도로 사용된다.

분산 락: 락을 잡은 프로세스가 정확히 하나임을 보장해야 한다.

유일성 제약: 사용자명, 결제 ID처럼 중복이 허용되지 않는 값. 두 노드가 동시에 같은 값을 할당하면 안 된다.

선형화 가능성의 비용

선형화 가능성을 구현하려면 모든 읽기와 쓰기가 단일 리더를 통해야 한다. 또는 쓰기 후 모든 복제가 완료될 때까지 기다려야 한다. 성능 비용이 크다.

더 근본적인 문제가 있다. 네트워크 파티션 시 선형화 가능성을 포기해야 한다.

---

CAP 정리 — 오해와 진실

분산 시스템에서 가장 유명한 이론이다.

Consistency(일관성), Availability(가용성), Partition tolerance(파티션 내성) — 세 가지 중 두 가지만 선택할 수 있다.

흔한 오해: "CA, CP, AP 중 하나를 선택하면 된다."

책의 입장: 이 정리는 사실 실용적으로 별 도움이 안 된다.

현실에서 네트워크 파티션은 반드시 발생한다. 즉 P(파티션 내성)는 선택 사항이 아니다. "P를 포기한 CA 시스템"은 현실에서 존재하지 않는다. 결국 파티션 발생 시 C(일관성)와 A(가용성) 중 하나를 선택하는 것뿐이다.

더 중요한 문제는 CAP이 이분법적으로 표현한다는 것이다. 실제로는 일관성의 종류도, 가용성의 종류도 스펙트럼으로 다양하다. CAP은 이 스펙트럼을 표현하지 못한다.

---

순서화 보장 — 인과성이 핵심이다

선형화 가능성보다 약하지만 실용적인 보장이 있다. 인과적 일관성(Causal Consistency) 이다.

인과성이 뭔가

"A가 B의 원인이다"라는 관계가 보존되어야 한다는 것이다. 질문이 먼저 보이고 답변이 나중에 보여야 한다. 결제 요청이 먼저 처리되고 영수증이 발송되어야 한다.

5장에서 본 Consistent Prefix Read 문제가 인과성이 깨진 예시였다.

전순서 vs 편순서

선형화 가능한 시스템은 전순서(Total Order) 를 제공한다. 모든 연산이 하나의 타임라인 위에 순서대로 나열된다.

인과적으로 일관된 시스템은 편순서(Partial Order) 를 제공한다. 인과관계가 있는 이벤트들 사이에는 순서가 있지만, 인과관계 없는 이벤트들은 순서가 없어도 된다.

편순서는 성능 면에서 훨씬 유리하다. 인과관계 없는 이벤트들을 병렬로 처리할 수 있기 때문이다.

람다크록 (Lamport Timestamp)

인과적 순서를 추적하는 고전적인 방법이다. 각 노드가 카운터를 가지고 이벤트마다 증가시킨다. 메시지를 받을 때 자신의 카운터와 수신한 카운터 중 큰 값으로 갱신한다.

노드A: 카운터 = 5, 이벤트 발생 → (5, A)
노드A가 노드B에 메시지 전송
노드B: 현재 카운터 = 3, 수신 → max(3, 5) + 1 = 6 → (6, B)

이렇게 하면 인과관계가 있는 이벤트들 사이에서는 타임스탬프 순서가 인과 순서와 일치한다.

한계: 두 이벤트의 타임스탬프를 보고 어느 것이 먼저인지 알 수 있지만, 두 이벤트가 인과관계가 있는지 없는지는 알 수 없다.

전체 순서 브로드캐스트 (Total Order Broadcast)

모든 노드가 모든 메시지를 같은 순서로 받는 것을 보장하는 프로토콜이다.

두 가지 속성이 보장된다.

• 신뢰성: 메시지가 유실되지 않는다. 한 노드가 받으면 모든 노드가 받는다.
• 순서: 모든 노드가 동일한 순서로 메시지를 받는다.

왜 중요한가? 전체 순서 브로드캐스트가 있으면 복제 로그를 만들 수 있다. 모든 노드가 같은 순서로 같은 연산을 적용하면 상태가 동일해진다. Kafka가 이 아이디어를 구현한다. 파티션 내의 메시지는 전체 순서 브로드캐스트 의미론을 가진다.

---

분산 트랜잭션과 합의

이제 9장의 핵심인 합의 문제로 들어간다.

합의(Consensus): 여러 노드가 어떤 값에 동의하도록 만드는 것.

단순해 보이지만 분산 환경에서 노드가 죽거나 네트워크가 끊길 수 있는 상황에서는 매우 어렵다.

합의는 다음 조건을 만족해야 한다.

• 일치성(Agreement): 모든 정상 노드가 같은 값에 동의한다
• 무결성(Integrity): 동의된 값은 어떤 노드가 제안한 값이다
• 유효성(Validity): 제안된 값만 선택될 수 있다
• 종료성(Termination): 정상 노드는 결국 어떤 값에 동의한다

2단계 커밋 (2PC, Two-Phase Commit)

여러 노드에 걸친 트랜잭션을 원자적으로 커밋하기 위한 고전적인 프로토콜이다. 분산 DB, XA 트랜잭션에서 사용한다.

1단계 — Prepare
코디네이터가 모든 참여자에게 "커밋할 준비가 됐는가?"를 묻는다.
참여자는 Yes 또는 No로 응답한다. Yes를 응답한 참여자는 커밋할 것을 약속한다.

2단계 — Commit/Abort
모든 참여자가 Yes라고 응답하면 코디네이터가 Commit 명령을 전송한다.
하나라도 No라고 하면 Abort 명령을 전송한다.

코디네이터
    │
    ├── Prepare? ──▶ 참여자1 ──▶ Yes
    ├── Prepare? ──▶ 참여자2 ──▶ Yes
    │
    ├── Commit! ──▶ 참여자1
    └── Commit! ──▶ 참여자2

2PC의 문제 — 코디네이터 장애

2PC의 치명적 약점은 코디네이터다. 코디네이터가 Prepare는 보냈는데 Commit/Abort를 보내기 전에 죽으면 어떻게 되나?

참여자들은 Yes를 응답했다. Yes를 응답한 참여자는 혼자서 Abort할 수 없다. 코디네이터의 결정을 기다려야 한다. 하지만 코디네이터는 죽었다. 참여자들은 불확정 상태(In-Doubt) 에 빠진다. 락을 잡은 채로 무한정 기다린다.

2PC는 코디네이터가 단일 장애점이다. 이 때문에 2PC를 "차단 프로토콜(Blocking Protocol)"이라고 한다.

Paxos와 Raft — 결함 허용 합의

2PC의 한계를 극복하기 위한 합의 알고리즘이다. 노드 과반수가 살아있는 한 계속 동작한다.

Paxos

1989년 Leslie Lamport가 발표한 알고리즘이다. 분산 합의의 이론적 기반이다.

동작 원리를 단순화하면 이렇다.

Phase 1 — Prepare
제안자(Proposer)가 고유한 제안 번호 n을 들고 수락자(Acceptor)들에게 "이 번호 이상의 제안은 무시하겠다고 약속해달라"고 요청한다.

Phase 2 — Accept
과반수가 약속하면, 제안자가 실제 값을 제안한다. 과반수가 수락하면 합의가 이루어진다.

Paxos는 증명이 복잡하고 구현이 어렵기로 유명하다. Lamport 본인도 "Paxos는 이해하기 어렵다"고 인정했다.

Raft

2013년 Diego Ongaro와 John Ousterhout가 "이해하기 쉬운 합의 알고리즘"을 목표로 설계했다. etcd, CockroachDB, TiKV가 Raft를 사용한다.

Raft는 세 가지 서브문제로 나눈다.

리더 선출(Leader Election)
모든 노드는 팔로워로 시작한다. 리더에게서 일정 시간 동안 하트비트가 없으면 후보(Candidate)가 된다. 자신에게 투표하고 다른 노드에게 투표를 요청한다. 과반수의 투표를 받으면 리더가 된다.

각 리더십 기간을 텀(Term) 이라고 한다. 텀 번호는 단조 증가한다. 오래된 텀의 리더는 새 텀을 보는 순간 자신의 리더십을 포기한다.

텀 1: 노드A 리더 (하트비트 전송)
네트워크 파티션 발생
텀 2: 노드B 후보 → 과반수 투표 획득 → 노드B 리더
파티션 복구
노드A: 텀 2를 수신 → 텀 1 리더십 포기 → 팔로워로 전환

로그 복제(Log Replication)
클라이언트의 쓰기 요청은 리더에게만 간다. 리더는 로그에 추가하고 팔로워들에게 전달한다. 과반수가 로그를 저장했다고 확인하면 커밋한다. 팔로워들은 리더의 로그를 그대로 따른다.

안전성(Safety)
한 텀에 리더는 반드시 하나다. 이미 커밋된 로그 엔트리는 절대 덮어써지지 않는다. 리더가 될 수 있는 노드는 가장 최신 로그를 가진 노드로 제한한다.

Paxos vs Raft 비교

	Paxos	Raft
이해 난이도	높음	낮음
성능	비슷	비슷
리더 선출 방식	복잡한 준비 단계	텀 기반 투표
사용처	Chubby(Google)	etcd, CockroachDB
특징	이론적 기반	실용적 설계

---

ZooKeeper — 합의를 서비스로

Paxos 계열 합의 알고리즘을 직접 구현하는 건 극도로 어렵다. ZooKeeper는 이 합의를 서비스 형태로 제공한다.

ZooKeeper가 제공하는 것들:

선형화 가능한 원자적 쓰기: 여러 클라이언트가 동시에 쓰더라도 한 번에 하나씩 처리된다. 이걸 이용해 분산 락을 구현할 수 있다.

전체 순서 브로드캐스트: 모든 클라이언트가 동일한 순서로 업데이트를 받는다.

임시 노드(Ephemeral Node): 클라이언트 연결이 끊기면 자동으로 삭제되는 노드. 서비스 디스커버리, 리더 선출에 활용한다.

Watch: 특정 값이 변경되면 알림을 받는 메커니즘.

ZooKeeper를 직접 쓰는 건 복잡하다. 그래서 Kafka, Hadoop, HBase 같은 분산 시스템이 내부적으로 ZooKeeper를 사용해서 리더 선출, 설정 관리, 서비스 디스커버리를 처리한다. 최근 Kafka는 KRaft 모드로 ZooKeeper 의존성을 제거하는 방향으로 가고 있다.

---

멤버십과 코디네이션 서비스

9장 후반부는 ZooKeeper 같은 코디네이션 서비스가 제공하는 고수준 추상화를 다룬다.

서비스 디스커버리: 어떤 IP 주소에 어떤 서비스가 떠 있는가. 노드가 시작하면 ZooKeeper에 자신을 등록하고, 다른 서비스는 ZooKeeper에 질의해서 주소를 얻는다.

멤버십 관리: 어떤 노드가 클러스터에 속해 있는가. 노드가 죽으면 임시 노드가 삭제되어 자동으로 클러스터에서 제거된다.

리더 선출: 여러 서비스 인스턴스 중 어느 것이 리더인가. ZooKeeper의 임시 노드와 Watch를 조합해서 구현한다.

---

2부를 마치며 — 분산 시스템의 핵심 긴장

5장부터 9장까지 2부 전체를 관통하는 긴장이 하나 있다.

성능과 정확성의 트레이드오프.

선형화 가능성은 정확하지만 느리다. 최종 일관성은 빠르지만 이상 현상이 생긴다. 어느 수준의 일관성을 선택할지는 비즈니스 요구사항에 달려 있다.

결제 시스템에서 잔액이 음수가 되면 안 된다면 강한 일관성이 필요하다. SNS 좋아요 수가 몇 초 늦게 반영돼도 괜찮다면 최종 일관성으로 충분하다.

그리고 합의 알고리즘은 은탄환이 아니다. Raft를 쓴다고 해서 모든 분산 문제가 해결되지 않는다. 합의는 특정 문제(리더 선출, 원자적 커밋)를 해결하는 도구다. 그 위에서 어떻게 시스템을 설계하느냐는 여전히 개발자의 몫이다.

---

마치며 — 내 실무와 연결되는 점

9장을 읽고 나서 etcd와 ZooKeeper가 왜 Kubernetes와 Kafka의 핵심 의존성인지 이해가 됐다. 리더 선출과 설정 분산을 위해 합의 알고리즘이 필수적이고, 그걸 직접 구현하는 건 극도로 어렵기 때문에 ZooKeeper나 etcd를 가져다 쓰는 것이다.

그리고 Kafka의 KRaft 전환이 왜 의미 있는 변화인지도 이해됐다. ZooKeeper 의존성을 제거하고 Kafka 자체가 Raft 기반으로 메타데이터를 관리하게 되면, 운영 복잡도가 줄어들고 확장성이 높아진다.

2PC의 코디네이터 단일 장애점 문제도 실무와 연결된다. 분산 트랜잭션을 써야 하는 상황이라면 코디네이터 장애 시 불확정 상태가 발생할 수 있다는 걸 알고 설계해야 한다. 마이크로서비스 환경에서 2PC 대신 사가(Saga) 패턴을 쓰는 이유가 바로 이 때문이다.

이제 3부 — 파생 데이터로 넘어간다. 10장은 배치 처리, 11장은 스트림 처리다. MapReduce, Spark, Kafka Streams가 어떤 문제를 풀기 위해 설계됐는지, 그리고 배치와 스트림을 어떻게 통합할 것인가를 다룬다.

---

읽어주셔서 감사합니다. 잘못된 내용이나 보완할 점이 있으면 댓글로 알려주세요.