CAP을 넘어 PACELC로: 평상시 트레이드오프와 합의 알고리즘

CAP을 넘어 PACELC로: 평상시 트레이드오프와 합의 알고리즘

이전 1편: 피터 도이치의 8가지 오류에서 분산 환경의 물리적 한계, 2편: CAP 이론에서 P 상황의 트레이드오프, 3편: 주문/결제 시스템에서 CP와 AP 선택하기에서 1·2차 방어선으로 풀어내는 실무 전략을 다뤘습니다.

3편 §5의 도메인 매트릭스에서 우리는 "정합성이 절대적인 도메인에는 CP 기반 분산 락(ZooKeeper/etcd)"이라고 정리했습니다. 그 CP 락 안에서는 무슨 일이 일어나고 있을까요? 그리고 CAP 이론이 다루지 못한 "평상시 트레이드오프"는 어떻게 설명할까요? 이번 4편은 이 두 질문에 답합니다.

Hook: 네트워크 장애가 안 나면 CAP은 끝인가요? — 평상시에도 시스템은 트레이드오프에 직면합니다. PACELC 이론과, "정합성을 정말로 보장하고 싶을 때" 쓰는 Quorum과 Raft 합의 알고리즘을 다룹니다.

---

1. CAP 이론의 한계 — 평상시에도 트레이드오프가 있다

2편에서 우리는 CAP 이론을 정리했습니다. "P는 무조건 전제, C와 A 사이에서 하나를 포기". 3편에서는 이 트레이드오프를 실제 이커머스 주문 시스템에 대입해 1차(§3 동기 선차감) + 2차(§4 사가+멱등성+UX)의 이중 방어선으로 풀어냈습니다.

그런데 CAP에는 빈틈이 있습니다. CAP는 P(파티션, Partition) 가 발생한 상황에서의 선택만 다룹니다. 네트워크가 끊어지는 순간이 아니라, 평상시(Normal Operation)에도 시스템은 트레이드오프에 직면합니다.

평상시의 고민 — "응답 속도 vs 정합성"

평상시 주문 API를 생각해봅시다.

• 응답을 빠르게: 모든 노드에 쓰기 전파가 끝나기 전에 리더만 응답 → 일관성이 약간 깨질 수 있지만 latency 5ms
• 응답을 느리게: 모든 노드에 쓰기 전파 후 응답 → 강한 일관성 보장하지만 latency 50ms

둘 다 "P 상황"은 아닙니다. 네트워크는 멀쩡합니다. 그럼에도 우리는 응답 속도(Latency)와 일관성(Consistency) 사이에서 선택해야 합니다. CAP 이론은 이 평상시 트레이드오프를 설명하지 못합니다.

이 빈틈을 메우기 위해 2012년 Daniel Abadi가 제안한 것이 PACELC 이론입니다.

• P(Partition) 발생 시: A(가용성) vs C(일관성) — CAP와 동일
• E(lse, 그 외의 경우 = 평상시): L(atency) vs C(onsistency) — 새로 추가

PACELC는 CAP를 "P 상황"과 "평상시" 두 축으로 확장한 것입니다. 모든 분산 시스템은 이 2×2 매트릭스 위에 자신의 위치를 갖고, §2에서 구체적으로 살펴봅니다.

---

2. PACELC — 2×2 매트릭스로 시스템 분류

§1에서 PACELC는 CAP의 빈틈(평상시 트레이드오프)을 메운다고 했습니다. 구체적으로 PACELC는 두 축으로 시스템을 분류합니다.

두 축 = 4가지 위치

	평상시 Latency 우선 (EL)	평상시 Consistency 우선 (EC)
P 시 Availability 우선 (PA)	PA/EL	PA/EC
P 시 Consistency 우선 (PC)	PC/EL	PC/EC

• PA/EL: 평상시엔 빠르게, 파티션 시엔 가용성 우선
• PC/EC: 평상시엔 일관성 위해 기다림, 파티션 시에도 일관성 지킴
• PA/EC: 파티션 시엔 가용성, 평상시엔 일관성
• PC/EL: 파티션 시엔 일관성, 평상시엔 빠르게

실제 시스템의 PACELC 위치

시스템	PACELC	해석
DynamoDB	PA/EL	파티션 시 가용성, 평상시 eventual latency 최적화
Cassandra	PA/EL	위와 유사 (튜닝 가능)
MongoDB (default)	PC/EL	단일 leader가 응답 → 평상시 빠름, 파티션 시 leader 격리되면 fail
Kafka KRaft	PC/EL	메타데이터 합의를 위해 leader가 쓰기 직렬화
CockroachDB / TiDB	PC/EC	Raft 합의로 강한 일관성, 평상시에도 quorum 대기
Google Spanner	PC/EC	Paxos + TrueTime, 글로벌 강한 일관성
etcd / ZooKeeper	PC/EC	Raft/Zab으로 모든 상태 합의, latency 비용 감수
RDBMS 단일 노드	CA (사실상 P 없음)	네트워크 분할 자체 없음

3편 §5와의 연결 — "AP/CP"가 사실은 4가지

3편 §5의 도메인 매트릭스가 PACELC로 다시 읽힙니다.

• 재고 차감 (대략 정확) — AP → DynamoDB/Cassandra 같은 PA/EL
• 재고 차감 (정확한 카운트) — CP → ZooKeeper/etcd 같은 PC/EC
• 결제 정산 — CP → Spanner/CockroachDB 같은 PC/EC
• 상품 조회 — AP → MongoDB default 같은 PC/EL
• 쿠폰 사용 (선착순) — 하이브리드 → 상황에 따라 PA/EL 또는 PC/EC 선택

3편에서 우리는 "AP 또는 CP"라는 1차원 선택만 했지만, PACELC로 보면 4가지 위치 중 어디에 서느냐가 더 정확한 질문입니다. 그리고 평상시(E) 트레이드오프는 우리가 매 요청마다 무의식적으로 선택하고 있는 것이었습니다.

---

3. 일관성 모델의 스펙트럼 — 강한 일관성부터 최종 일관성까지

PACELC는 시스템이 "어느 쪽을 택하는가"를 알려주지만, "정합성"이라는 단어 자체가 사실은 스펙트럼 위에 있습니다. 일관성 모델은 강한 쪽에서 약한 쪽으로 4단계로 나뉩니다.

4단계 일관성 스펙트럼

graph LR
    A[Strong<br/>Linearizability] -->|느슨해짐| B[Causal]
    B -->|느슨해짐| C[Read-your-writes]
    C -->|느슨해짐| D[Eventual]

1. 강한 일관성 (Linearizability)

• 정의: 모든 읽기가 가장 최근 쓰기를 본다. 시스템이 단일 노드처럼 동작.
• 트레이드오프: latency 최악 (모든 replica 전파 대기)
• 예시: etcd/ZooKeeper, Spanner, DynamoDB (강한 일관성 모드)

2. 인과적 일관성 (Causal Consistency)

• 정의: 인과 관계가 있는 작업(예: 댓글 → 답글)은 모든 노드가 같은 순서로 본다. 독립적인 작업은 순서 무관.
• 트레이드오프: latency 중간 (인과 관계만 추적)
• 예시: COPS, Facebook TAO 일부 모드

3. 읽기 본인 일관성 (Read-your-writes)

• 정의: 클라이언트가 쓴 데이터는 최소한 본인은 즉시 본다. 다른 클라이언트에 대한 보장은 없음.
• 트레이드오프: latency 낮음 (자기 세션만 보장)
• 예시: sticky session + read-from-primary, 일반적인 웹 앱

4. 최종 일관성 (Eventual Consistency)

• 정의: 새 업데이트가 없으면 결국 모든 replica가 같은 값에 도달. 순서 보장 없음.
• 트레이드오프: latency 최저, 가용성 최고
• 예시: DynamoDB default, Cassandra default, DNS

일관성 모델과 PACELC의 매핑

일관성 모델	PACELC	시스템 예시
Linearizability	PC/EC	Spanner, etcd
Causal	PC/EL or PA/EL (구현에 따라)	COPS
Read-your-writes	PC/EL (보통)	MongoDB default
Eventual	PA/EL	DynamoDB, Cassandra

3편에서 우리가 "AP"라 부른 것은 사실 최종 일관성이었고, "CP"라 부른 것은 선형화 가능한 일관성이었습니다. 이 둘 사이에는 인과적 일관성과 읽기 본인 일관성이 존재하고, 실제 많은 시스템은 이 중간 지점에 위치합니다.

§4에서는 이 중 선형화 가능한 일관성(Strong Consistency)을 실제로 구현하는 방법 — Quorum과 Raft 합의 알고리즘을 다룹니다.

---

4. Quorum과 Raft — 강한 일관성을 실제로 구현하는 법

§3에서 강한 일관성(Linearizability)을 정의했습니다. 이번 절에서는 그 강한 일관성을 실제로 구현하는 두 가지 핵심 메커니즘을 다룹니다.

§4-1. Quorum — "과반수가 본 것은 진실이다"

Quorum은 N개의 replica 중 쓰기(W)와 읽기(R)가 각각 다른 replica에 분산되어 적용되되, W+R > N이 되도록 설계하는 방식입니다.

        N=3 replicas
       ┌──────────────┐
       │              │
   ┌───┴──┐       ┌───┴──┐
   │  R1  │       │  R3  │
   └──────┘       └──────┘
       │              │
       │  ┌──────┐    │
       └──│  R2  │────┘
          └──────┘
   W=2 writes to: R1, R2
   R=2 reads from: R1, R3
   → R1에서 겹침 → 가장 최근 쓰기 보장 (W+R=4 > N=3)

• N=3, W=2, R=2 → W+R=4 > 3 → 강한 일관성 보장
• N=5, W=3, R=3 → W+R=6 > 5 → 강한 일관성
• N=3, W=1, R=1 → W+R=2 ≤ 3 → 약한 일관성 (DynamoDB default)

§4-2. Raft — 합의 알고리즘의 "이해 가능 버전"

Quorum이 "읽기·쓰기 단일 작업의 정합성"을 보장한다면, Raft는 "시스템 전체의 상태가 하나로 합의되어 있다"를 보장합니다. 3가지 역할과 2단계 메커니즘으로 동작합니다.

3가지 역할:

• Leader: 모든 쓰기·읽기 처리. 단 1개.
• Follower: Leader의 지시를 따르며 상태 복제. 평소 상태.
• Candidate: Leader가 죽었을 때 Follower가 승격 후보로 변한 상태.

리더 선출 (Leader Election):

sequenceDiagram
    participant F1 as Follower 1
    participant F2 as Follower 2
    participant F3 as Follower 3

    Note over F1,F3: Leader heartbeat 타임아웃
    F1->>F1: election timeout 만료
    F1->>F1: Candidate로 전환, term++

    F1->>F2: RequestVote (term=2)
    F1->>F3: RequestVote (term=2)

    F2-->>F1: Yes (vote)
    F3-->>F1: Yes (vote)

    Note over F1: 과반수(2/3) 확보 → Leader 전환
    F1->>F2: AppendEntries (heartbeat)
    F1->>F3: AppendEntries (heartbeat)

• Follower가 Leader의 heartbeat를 못 받으면 (보통 150~300ms) → Candidate로 전환
• 다른 노드에게 표 요청 (RequestVote)
• 과반수 득표 시 Leader로 전환
• 새 term 번호로 모든 Follower에 heartbeat 전송

로그 복제 (Log Replication):

sequenceDiagram
    participant Client as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2

    Client->>L: SET x = 5
    L->>L: 로그 엔트리 추가

    L->>F1: AppendEntries (x=5)
    L->>F2: AppendEntries (x=5)

    F1-->>L: ACK
    F2-->>L: ACK

    Note over L: 과반수 ACK → commit
    L->>F1: commit (x=5)
    L->>F2: commit (x=5)
    L-->>Client: OK

• Client가 Leader에 쓰기 요청
• Leader가 로그 엔트리로 추가하고 Follower에 전파
• 과반수 Follower가 ACK하면 commit
• Leader가 모든 Follower에 commit 알림 → 일관성 보장

§4-3. "모르고 쓰는 Raft" — 모두 이미 사용 중

시스템	Raft/Paxos 사용	만나는 순간
K8s (etcd)	Raft	kubectl apply
Kafka 3.0+	KRaft (자체 Raft)	토픽 생성, 컨트롤러
CockroachDB / TiDB	Raft	모든 분산 트랜잭션
ZooKeeper	Zab (Paxos 변형)	분산 코디네이터
Google Spanner	Paxos + TrueTime	글로벌 트랜잭션
AWS S3 (2020~)	Paxos-like	강한 일관성 GET
결제 시스템 (토스/카카오페이)	Paxos/Raft	금융 원장 합의

3편 §5로의 회귀 — "CP 도메인의 본체"

3편 §5의 "재고 차감 (정확한 카운트) — CP + ZooKeeper/etcd 락"이 사실은 이 Raft 합의 위에서 동작합니다. "락"이라는 단어가 추상적이었다면, 본체는 Quorum으로 읽고 쓰는, Raft로 상태 합의하는 시스템입니다.

§4 정리. Quorum(W+R>N)이 단일 작업의 정합성을, Raft가 시스템 전체 상태의 합의를 보장합니다. 둘이 결합되어 PACELC 매트릭스의 PC/EC 셀에 위치하는 강한 일관성 시스템을 만듭니다.

---

5. 마치며 — "굳이 강한 일관성을 도입할 도메인은?"

4편을 통해 PACELC로 평상시 트레이드오프를, Quorum과 Raft로 강한 일관성의 구현 원리를 정리했습니다. 마지막으로 답해야 할 질문은 이겁니다. "그래서, 우리 시스템은 Raft/Quorum을 도입해야 하나?"

대부분의 답: 안 해도 된다.

이 시리즈를 읽고 "우리도 Raft 도입해야겠다!"라고 결론 내리면 그건 오독입니다. Raft/Quorum은 비싼 비용(latency, 운영 복잡성)을 정합성이라는 가치와 교환하는 결정입니다. 대부분의 시스템은 그 교환이 필요 없습니다.

Raft/Quorum 도입이 정당화되는 5가지 신호

1. 돈의 흐름이 있는가? (Financial integrity)

   • 결제 정산, 환불, 정산 배치, 포인트 차감
   • "1,000원이 사라졌다/중복 차감됐다"는 사고가 CS 비용·신뢰 손실로 직결

2. 정확한 카운트가 SLA인가? (Zero-oversell)

   • 한정판 드롭, 한정 수량 쿠폰, 좌석 예매
   • 오버셀 = 환불 폭주 + 브랜드 손상

3. 중복 실행이 치명적인가? (Idempotency at infrastructure level)

   • 정산 배치, 일 1회 푸시, 백업
   • "한 번만 실행"이 인프라 차원에서 보장돼야 함

4. 리더가 단 1개여야 하는가? (Single-leader requirement)

   • K8s 컨트롤러, Kafka 컨트롤러, DB primary
   • split-brain = 데이터 손상

5. 글로벌 트랜잭션이 필요한가? (Cross-region consistency)

   • 다중 리전 쓰기, 글로벌 결제
   • Google Spanner급의 Paxos + TrueTime 필요 영역

4편 시리즈 결론 — 강한 일관성은 도구일 뿐, 답이 아니다

이 시리즈의 서사 아크를 정리하면 이렇습니다.

편	핵심 질문	답
1편	왜 분산 환경은 고통스러운가?	물리적 한계 (빛, 전파) + 8가지 오류
2편	트레이드오프는 어떻게 정의되는가?	CAP: P는 전제, C/A 중 하나 포기
3편	실무에서 어떻게 풀어내는가?	AP + 1차 선차감 + 2차 사가+멱등성+UX
4편	평상시는? 정말 강한 일관성이 필요하면?	PACELC + Quorum + Raft

엔지니어의 일은 "강한 일관성을 쓰는 것"이 아니라, "내 도메인이 어느 일관성 스펙트럼 위에 있는지 판단하는 것"입니다. 그리고 그 판단을 팀·아키텍처·SLA에 정직하게 기록하는 것까지 포함해서요.

---

Outro — 시리즈를 마치며

4편에 걸친 분산 시스템 시리즈를 마무리합니다.

1편에서 8가지 오류로 시작해 물리적 한계를 확인했고, 2편에서 CAP으로 트레이드오프의 수학적 정의를 짚었고, 3편에서 주문 시스템을 통해 1차·2차 방어선으로 풀어내는 실무 전략을 정리했고, 4편에서 PACELC로 평상시 트레이드오프까지 확장하고 Quorum·Raft로 강한 일관성의 본체를 살펴봤습니다.

이 시리즈의 목표는 "분산 시스템을 마스터하는 법"이 아니었습니다. "내 서비스가 분산 환경의 어느 지점에 서 있는지 판단할 수 있는 눈" 을 키우는 것이었습니다.

• 네트워크는 끊어지고 (1편)
• C와 A는 동시에 못 잡고 (2편)
• AP는 응답을 살리되 부작용을 만들고 (3편)
• 평상시에도 latency와 consistency 사이에서 매번 선택하고 (4편)

이 4가지 사실을 정직하게 인지하고, 도메인별로 다른 결정을 내리고, 그 결정을 코드와 운영으로 옮기는 것 — 이게 분산 시스템 엔지니어의 실제 일입니다.

마지막으로 한 줄.

"완벽한 분산 시스템은 없다. 다만, 도메인에 맞는 정직한 트레이드오프가 있을 뿐이다."