분산 시스템 CAP 정리

분산 시스템을 공부하면 반드시 만나게 되는 이론이 있다. 바로 CAP 정리다. "Consistency, Availability, Partition Tolerance" 중 두 가지만 선택할 수 있다"는 문장은 개발자라면 한 번쯤 들어봤을 것이다. 그런데 이 문장 자체가 오해를 품고 있다.
이번 글에서는 CAP 정리의 이론적 배경부터 세 가지 속성의 정확한 정의, 추측에서 형식적 증명까지의 맥락, 그리고 실제 분산 시스템(ZooKeeper, Cassandra, Redis Cluster, Aurora DB)에서의 구현 방식과 후속 모델인 PACELC까지 정리한다.

---

1. C, A, P — 각 속성의 정확한 정의

CAP에 대한 오해는 대부분 세 속성의 정의를 부정확하게 이해하는 데서 시작된다. 하나씩 명확하게 알아보자.

1. Consistency(일관성) - Linearizability (선형화가능성)

CAP에서 말하는 Consistency는 우리가 흔히 사용하는 "데이터 정합성"이나 ACID의 C와 다른 개념이다.

CAP의 C는 Linearizability(선형화가능성)을 의미한다. 이것도 뭔소리인지 모르겠어서 더 풀어서 말하면, 어떤 작업이 완료된 후, 그 뒤에 오는 다른 모든 작업은 이전 작업의 결과를 즉시 볼 수 있어야 한다는 규칙인 것이다. 분산 시스템의 모든 노드에서, 어느 노드에 읽기 요청을 보내든, 가장 최근에 완료된 쓰기의 결과를 반드시 돌려받아야 한다.

 

커머스 시스템을 예로 들어보자.

관리자가 상품 가격을 10,000원 → 8,000원으로 수정했다. 이 시스템이 3대의 노드로 구성되어 있다면, CAP의 Consistency가 보장되려면 노드 1, 2, 3 어디에 SELECT를 날려도 8,000원이 나와야 한다. 노드 2에서 아직 10,000원이 나온다면 그 순간 CAP의 C는 깨진 것이다.

 

ACID의 C와의 차이를 명확히 구분하면 다음과 같다.

구분	의미	예시
ACID의 C	DB 제약조건(Unique, 음수 졔약 등)이 트랜잭션 전후로 위반되지 않음	FK 참조 무결성, Unique 제약
CAP의 C	분산 시스템의 어느 노드에서 읽어도 최신값을 반환	Linearizability (선형화가능성)
Eventual Consistency	시간이 지나면 모든 노드가 같은 값으로 수렴	Aurora Reader Replica의 복제 지연

AWS Aurora DB를 사용해 본 경험이 있다면 체감할 수 있는 부분이 있다. Writer 인스턴스에 UPDATE를 치고 Reader 인스턴스에서 즉시 SELECT하면, 복제 지연(replication lag) 동안 과거 값이 반환될 수 있다. 이 상태가 Eventual Consistency이며, 이 순간 CAP의 C는 충족되지 않는 것이다.

2. Availability(가용성) — 모든 살아있는 노드의 응답 보장

Availability도 일상적인 의미와 CAP에서의 정의가 다르다.

장애가 나지 않은(non-failing) 모든 노드는, 반드시 응답을 돌려줘야 한다.

 

두 가지를 짚어야 한다.

1. "장애가 나지 않은 노드"라는 조건이 붙는다. 물리적으로 죽은 노드는 대상이 아니다. 살아있는 노드에 요청이 도착했다면, 그 노드는 반드시 응답해야 한다는 뜻이다.
2. 응답이 최신값이 아니어도 된다. 에러가 아닌 유효한 응답을 돌려주기만 하면 A는 만족하는 것이다. Aurora Reader가 복제 지연 때문에 10,000원(옛날 값)을 돌려줬다면, C는 깨졌지만 A는 만족한 상황이다.

구분	의미
운영 관점의 가용성	99.99% 업타임, 빠른 응답, 헬스체크 통과
CAP의 A	살아있는 노드는 반드시 응답 (느려도, 옛날값이어도 OK)

3. Partition Tolerance — 전제조건

여기서 파티션은 네트워크 파티션을 말한다. 네트워크 파티션이란 노드 간 통신이 두절되는 상황을 의미한다. 데이터가 쪼개지는 것이 아니라, 노드끼리 서로 연락이 안 되는 것이다.

정상 상태:
  [노드1] ←→ [노드2] ←→ [노드3]

파티션 발생:
  [노드1] ←→ [노드2]   ✕   [노드3]
                         ↑
                    네트워크 끊김

노드3은 살아있고 요청도 받을 수 있다. 그러나 노드1, 2와 대화를 못 한다. 이것이 네트워크 파티션이다.

Partition Tolerance의 정의: 네트워크 파티션이 발생하더라도 시스템이 계속 동작한다.

 

여기서 결정적인 사실이 있다. 분산 시스템에서 네트워크 파티션은 선택의 문제가 아니다.

해저 케이블 장애, 스위치 고장, AWS 가용영역 간 통신 장애 등 이것은 피할 수 없는 물리적 현실이다.

즉, P는 포기할 수 있는 옵션이 아니라 받아들여야 하는 전제조건이다.

4. 파티션 발생 시 강제되는 선택

관리자가 노드1에 가격을 8,000원으로 UPDATE 쳤다. 그런데 노드3이 네트워크 파티션으로 고립된 상태에서 고객이 노드3에 가격 조회 요청을 보냈다.

이 순간 시스템은 둘 중 하나를 선택해야 한다.

• 선택지 A: 노드3이 자기가 가진 옛날 값(10,000원)을 그냥 돌려준다 → C 위반, A 충족
• 선택지 B: 노드3이 "최신값을 확인할 수 없으니 응답을 거부한다" → A 위반, C 보호

이것이 CAP의 본질이다. 파티션이 발생하면 일관성과 가용성 사이에서 선택이 강제된다.

---

2. "3개중 최대 2개만 충족" 오해

1. 원래 주장

2000년, 에릭 A. 브루어 교수가 분산 컴퓨팅 강연에서 다음과 같이 주장한다. (IBM 참고)

"분산 시스템은 Consistency, Availability, Partition Tolerance 중 최대 두 가지만 동시에 만족할 수 있다."

 

이걸 벤다이어그램으로 그리면 CP, AP, CA 세 조합이 깔끔하게 나온다.

        C
       / \
      /   \
    CP     CA
    /       \
   P ─ AP ── A

이 그림이 너무 직관적이었기 때문에 모든 개발자들이 "세 가지 메뉴에서 두 개를 고르는 것"으로 인식해버렸다.

2. 세 가지 문제점

첫 번째, P는 선택이 아니다.

• 분산 시스템에서 네트워크 파티션은 반드시 발생할 수 있는 물리적 현실이다. P를 "포기한다"는 건 "네트워크가 절대 안 끊긴다고 가정한다"는 건데, 현실에선 불가능하다.
• 그렇다면 CA 조합은 가능할까? P를 포기한다는 것은 "네트워크 파티션이 발생하면 시스템이 동작하지 않아도 된다"는 뜻이다. 하지만 네트워크 파티션이 발생하면서 고립된 노드 쪽에도 클라이언트가 존재한다. 일관된 응답(C)을 위해 고립된 노드를 중지시키면 그 클라이언트는 응답을 못 받게 되고, 이 순간 가용성(A)이 위반된다.
• 결국 CA는 네트워크 파티션이 아예 발생하지 않는 단일 노드 시스템(전통적 RDBMS)에서만 가능하다. 노드가 두 대 이상인 순간, 분산 시스템의 실질적 선택지는 CP 아니면 AP 두 개뿐이다.

두 번째, 항상 포기하는 게 아니다.

• CP 시스템이라 하면 "항상 A를 포기한다"로 보이지만, 실제로는 파티션이 발생한 그 순간에만 트레이드오프가 강제되는 것이다. 네트워크가 정상일 때는 C와 A를 둘 다 제공할 수 있다.

[정상 구간]         [파티션 발생]        [복구]
C ✓  A ✓  P -      C vs A 선택 강제     C ✓  A ✓  P -
                         ↑
                   여기서만 트레이드오프

 

세 번째, 이분법이 아니라 스펙트럼이다.

• 현실의 시스템은 CP/AP 두 칸으로 깔끔하게 나뉘지 않는다. "일관성을 약간 느슨하게 하되 가용성은 최대한 확보한다" 같은 튜닝이 가능하다. 이 부분은 Apache Cassandra (분산형 NoSQL DB) 사례로 확인해보자.

3. 브루어 교수 본인의 교정

Brewer는 2012년에 직접 글을 통해 다음과 같이 밝힌다.

"2 out of 3 이라는 표현은 오해를 부른다. 파티션은 드물게 발생하고, 파티션이 없는 동안에는 C와 A를 모두 제공할 수 있다."

즉, 이론을 제안한 본인이 세간의 이해 방식이 잘못되었다고 교정한 것이다.

 

따라서 정확한 이해는 이것이다.

"C, A, P 중 두 개를 고른다"

"분산 시스템에서 네트워크 파티션이 발생하면, 그 순간 일관성과 가용성 사이에서 선택해야 한다."

 

---

3. 브루어 교수의 추측에 대한 세스 길버트-낸시 린치의 형식적 증명

1. 추측과 증명

2000년에 브루어 교수가 제시한 것은 "추측"이었다. "나는 이렇다고 본다"라는 주장이지, 수학적으로 증명된 것이 아니었다.

학계의 반응은 "직관적으로는 그럴 것 같은데, 정말 불가능한 건지 아직 방법을 못 찾은 건지 어떻게 아는가?"였다.

 

2002년에 Seth Gilbert와 Nancy Lynch가 이 추측을 형식적으로 증명한다. 증명이 되면 더 이상 시도할 필요가 없어진다. "영리한 알고리즘을 만들면 세 개 다 되지 않을까?"라는 희망을 논리적으로 차단한 것이다.

2. Gilbert-Lynch 증명

증명 자체는 생각보다 매우 단순한 구조이다.

전제: 노드 2개(G1, G2), 둘 사이에 파티션 발생

1. 클라이언트가 G1에 write(x = 8000) 요청
2. G1은 성공적으로 저장
3. 파티션 때문에 G2에 전파 불가
4. 클라이언트가 G2에 read(x) 요청

이 순간:
- G2가 응답하면(A 충족) → 옛날값 반환(C 위반)
- G2가 거부하면(C 보호) → 응답 없음(A 위반)
- 어떤 알고리즘을 써도 이 구조를 벗어날 수 없음

노드 2개, 메시지 1개로 불가능성을 보인 것이다.

핵심은 파티션으로 인해 두 노드 간 메시지 전달이 불가능한 상태에서, C와 A를 동시에 만족시키는 응답이 논리적으로 존재하지 않는다는 것이다.

---

4. 실제 시스템에서의 CP / AP 구현

1. CP 시스템 — ZooKeeper

ZooKeeper는 분산 시스템의 코디네이터 역할을 하는 시스템이다. 리더 선출, 설정 관리, 분산 락 등에 사용된다.

내부적으로 ZAB(Zookeeper Atomic Broadcast) 프로토콜을 사용하며, Leader/Follower 구조로 동작한다.

[Follower1]
     ↕
[Leader] ←→ [Follower2]
     ↕
[Follower3]

쓰기 요청이 들어오면 Leader가 받아서 과반수(quorum) 이상의 노드에 복제가 완료된 후에 클라이언트에게 성공 응답을 준다.

 

파티션이 발생하면 어떻게 될까?

[Follower1] ←→ [Leader]    ✕    [Follower2] ←→ [Follower3]
        (그룹 A: 2대)                  (그룹 B: 2대)

5대 구성에서 과반수는 3대이다. 그룹 A에 Leader가 있지만 2대뿐이므로 과반수를 못 채운다. 이 상황에서 ZooKeeper는 쓰기 요청을 거부한다. 일관성을 지키기 위해 가용성을 포기한 전형적인 CP선택이다.

 

과반수를 기준으로 삼는 이유 - 교집합 보장

근데 왜 과반수이상의 노드에 복제가 되어야 성공 응답을 줄까?

왜 하필 과반수 일까?

 

노드가 5대이고 과반수가 3대일 때, 쓰기 시점에 3대에 복제하고, 읽기 시점에 3대에서 조회하면, 5대 중 3대짜리 그룹을 두 번 뽑은 셈이다. 따라서 3 + 3 = 6 > 5이므로 최소 1대는 반드시 겹친다. 이 겹치는 노드가 최신 데이터를 갖고 있는 증인 역할을 한다.

 

이를 쿼럼(Quorum) 공식으로 일반화하면 다음과 같다.

W + R > N

W = 쓰기 시 복제할 노드 수
R = 읽기 시 조회할 노드 수
N = 전체 노드 수

이 조건을 만족하면 읽기/쓰기 그룹 사이에 반드시 겹치는 노드가 존재하여 일관성이 보장된다.

단, ZooKeeper는 이 쿼럼 공식을 읽기에 직접 적용하지 않는다. 기본 읽기는 아무 Follower 한 대에서 즉시 응답하며(최신값이 아닐 수 있음), 최신값이 필요하면 sync 명령을 통해 Leader와 동기화한 후 읽기를 수행한다. 쿼럼 공식이 직접 적용되는 시스템은 바로 다음에 살펴볼 Cassandra이다.

2. AP 시스템 — Apache Cassandra (분산형 NoSQL DB)

Cassandra는 Facebook이 개발하고 현재 Apache 프로젝트로 운영되는 분산 NoSQL 데이터베이스이다.

아래 구조를 봐보자. ZooKeeper는 Leader/Follwer 구조였는데 카산드라는 리더가 없다.

ZooKeeper:           Cassandra:
[Leader]              [노드1]
  ↕   ↕                ↕   ↕
[F1] [F2]            [노드2]─[노드3]
                       ↕      ↕
리더가 쓰기 통제         [노드4]─[노드5]

                   모든 노드가 동등 (Peer-to-Peer)

리더가 없으므로 아무 노드에나 읽기/쓰기가 가능하다. 이 구조만으로도 가용성을 극대화하려는 설계 의도가 드러난다.

Cassandra에서는 앞서 설명한 쿼럼 공식이 직접 적용된다. 개발자가 요청마다 일관성 레벨을 설정할 수 있다.

 

Quorum 설정

설정	의미
ONE	노드 1대만 확인
QUORUM	과반수 확인
ALL	전체 노드 확인

 

N=3인 클러스터에서 적용하면 다음과 같다.

W=QUORUM(2), R=QUORUM(2) → 2+2=4 > 3 ✓ 일관성 보장
W=ONE(1),    R=ONE(1)    → 1+1=2 ≤ 3 ✗ 일관성 미보장
W=ALL(3),    R=ONE(1)    → 3+1=4 > 3 ✓ 일관성 보장

 

파티션 발생 시 동작이 ZooKeeper와 정반대이다.

[노드1] ←→ [노드2]   ✕   [노드3]

클라이언트가 노드3에 쓰기 요청 →

ZooKeeper였다면: 과반수 못 모으니 거부
Cassandra(W=ONE): 노드3이 혼자 저장하고 성공 응답 반환

파티션이 복구되면 노드 간 데이터를 맞추는 메커니즘이 동작하여 Eventually Consistent 상태로 수렴한다. 즉, 지금은 일관성이 안 맞지만, 나중에 맞춰진다는 AP 선택이다.

다만, Cassandra는 위에서 보다시피 Quorum 튜닝이 가능하다보니 "W=QUORUM, R=QUORUM" 으로 설정하면 CP처럼 동작할 수도 있다. 즉, Cassandra는 "AP 시스템"이라고 딱 잘라 말하기보단, 개발자가 요청 단위로 CP와 AP 사이를 튜닝할 수 있는 시스템이다.

 

이것이 앞서 말한 "CP/AP는 이분법이 아니라 스펙트럼"이라는 것의 실제 사례이다.

3. Redis Cluster - 유사 CP 시스템

Redis Cluster는 데이터를 16,384개의 해시 슬롯으로 나누어 여러 마스터 노드에 분산 저장한다.

파티션 또는 마스터 장애 발생 시 Redis Cluster는 해당 슬롯에 대한 요청을 거부(CLUSTERDOWN 에러)한다. 과거 데이터를 돌려주는 게 아니라 아예 에러를 내는 것이다. 즉, 일관성을 지키기 위해 가용성을 포기하는 CP선택이다.

[마스터A 담당: 슬롯 0~5000]  ← 이 노드가 죽음
[마스터B 담당: 슬롯 5001~10000]
[마스터C 담당: 슬롯 10001~16383]

마스터A가 죽은 직후 ~ 레플리카 승격 완료 전:
→ 슬롯 0~5000에 대한 요청은 CLUSTERDOWN 에러 반환

 

단, Redis Cluster가 완벽한 C를 보장하지는 않는다. 마스터 → 레플리카 복제가 비동기이기 때문이다.

1. 클라이언트 → 마스터A: SET price 8000 → "OK"
2. 마스터A가 레플리카에 복제하기 전에 죽음
3. 레플리카 승격 → price는 여전히 10000
4. 방금 쓴 데이터 유실

이래서 현실의 시스템을 CP/AP로 깔끔하게 분류하기 어렵다. Redis Cluster는 CP에 가깝지만 비동기 복제로 인해 완전한 C는 아닌 시스템이다.

4. Amazon Aurora DB - 특이 케이스

Aurora DB는 지금까지 본 시스템과 구조 자체가 다르다.

일반적인 분산 DB:
[노드1: 컴퓨트+스토리지] ←복제→ [노드2: 컴퓨트+스토리지]

Aurora:
[Writer 인스턴스]  [Reader 인스턴스1]  [Reader 인스턴스2]
       ↘               ↓                ↓
       ==========================================
       |        공유 분산 스토리지 레이어          |
       |   (3개 AZ × 2카피 = 6카피 자동 복제)     |
       ==========================================

Aurora 구조의 경우 스토리지와 컴퓨트가 분리되어 있다.

데이터가 노드마다 따로 있는 게 아니라 스토리지가 하나의 공유 레이어이고, Writer와 Reader 모두 같은 스토리지를 바라본다.

 

스토리지 레이어에는 Quorum 공식이 적용된다.

N=6, W=4, R=3
W+R = 4+3 = 7 > 6 ✓

 

일관성 (Consistency)

[지키는 부분]

Writer가 죽으면 Reader 중 하나를 Writer로 자동 승격시킨다. Redis Cluster와 다른 점은, Writer가 죽어도 스토리지 레이어에 4/6 쿼럼으로 이미 쓰기가 완료된 상태이므로 데이터 유실이 발생하지 않는다는 것이다.

그리고 Writer는 단 1대이므로, Cassandra처럼 양쪽에서 동시에 다른 값을 쓰는 쓰기 충돌이 원천적으로 발생하지 않는다. 파티션이 발생해도 Reader는 어차피 쓰기를 못 하기 때문이다.

[못 지키는 부분]

Writer와 Reader 사이의 레플리케이션이 아닌, Reader의 버퍼 캐시 갱신 지연으로 인해 최신값이 아닌 데이터가 읽힐 수 있다. Aurora는 전통적 "노드 → 노드" 복제가 아닌 공유 스토리지 구조 덕분에 CAP의 전통적 분류가 잘 맞지 않는 특수 케이스이다.

5. 시스템 비교 종합

시스템	파티션/장애 시 선택	핵심 특징
ZooKeeper	CP	과반수 못 모으면 쓰기 거부. ZAB 프로토콜 기반
Cassandra	AP (튜닝 가능)	Peer-to-Peer 구조. 개발자가 일관성 레벨 선택
Redis Cluster	CP (비동기 복제로 C 불완전)	담당 마스터 없으면 CLUSTERDOWN 에러
단일 RDBMS	CA	단일 노드이므로 파티션 자체가 없음
Aurora DB	전통적 분류 부적합	스토리지-컴퓨트 분리 구조. 레이어별로 다른 선택

---

5. PACELC — CAP의 한계 보완

1. CAP이 설명하지 못하는 것

CAP은 "파티션이 발생하면 C와 A 중 선택하라"고 말한다. 맞는 이야기다. 그런데 현실에서 네트워크 파티션은 간혈적으로 발생한다. 대부분의 시간은 네트워크가 정상이다. 그렇다면 아래 궁금증이 나온다.

파티션이 없는 평상시에는 아무 트레이드오프도 없는 것인가?

 

파티션이 없어도 노드 간 데이터 동기화에는 시간이 걸린다.

• 모든 노드 복제 완료까지 기다린 후 응답할 것인가(C 강화, Latency 증가)
• 일부만 복제하고 바로 응답할 것인가(Latency 감소, C 약화)

이 선택은 파티션과 무관하게 항상 존재한다.

2. PACELC 모델의 구조

이러한 CAP의 허점을 보완한 PACELC 모델은 이름 자체가 구조를 나타낸다.

P가 발생하면(Partition) → A vs C 선택
E(Else, 평상시)         → L(Latency) vs C(Consistency) 선택

"파티션 시에는 A와 C 중 선택하고, 평상시에도 지연시간(Latency)과 일관성(Consistency) 사이에서 선택해야 한다."

3. PACELC로 본 실제 시스템

시스템	파티션 시 (PA/PC)	평상시 (EL/EC)	표기	의미
ZooKeeper	PC	EC	PC/EC	항상 일관성 우선
Cassandra (기본)	PA	EL	PA/EL	항상 가용성·속도 우선
Redis Cluster	PC	EL	PC/EL	파티션 시 C, 평상시 L 우선
Aurora (스토리지)	PC	EC	PC/EC	쿼럼 쓰기 완료 대기

Redis Cluster를 보면 PACELC의 가치가 드러난다. CAP으로는 그냥 "CP"였는데, PACELC로 보면 파티션 시에는 C를 선택하지만, 평상시에는 Latency를 선택(비동기 복제)한다는 설계 특성이 명시적으로 표현된다.

 

"CP인데 완벽한 C는 아니다"라는 찝찝함의 정체가 바로 이것이다. CAP만으로는 "평상시에 비동기 복제를 써서 일관성을 약간 포기하고 있다"는 설계 선택이 표현되지 않는다. PACELC는 이를 **EL(평상시 Latency 우선)**이라고 명시해 준다.

---

6. 정리

CAP 세 속성 정의

C (Consistency)	모든 노드에서 최신값 반환 (Linearizability)	ACID의 C와 다른 개념
A (Availability)	살아있는 모든 노드가 반드시 응답	느려도, 옛날값이어도 OK
P (Partition Tolerance)	파티션 발생해도 시스템 동작	포기 불가능한 전제조건

핵심 원칙

1. CAP의 정확한 의미: "3개 중 2개 선택"이 아니라, "파티션 발생 시 C와 A 중 선택이 강제된다."
2. P는 전제조건: 분산 시스템에서 네트워크 파티션은 반드시 발생할 수 있으므로, 실질적 선택지는 CP 또는 AP이다.
3. CP/AP는 이분법이 아니라 스펙트럼: Cassandra처럼 요청 단위로 일관성 레벨을 튜닝하는 시스템이 존재한다.
4. CAP만으로는 부족하다: 평상시의 Latency vs Consistency 트레이드오프를 표현하려면 PACELC가 필요하다.
5. 현실의 시스템은 깔끔하게 분류되지 않는다: Aurora처럼 레이어별로 다른 선택을 하는 시스템도 있고, Redis Cluster처럼 CP이면서도 비동기 복제로 완전한 C를 보장하지 못하는 시스템도 있다.