CAP 이론, "P를 보장한다"는 것의 진짜 의미

서론

분산 시스템을 배우기 시작하면 거의 100% 마주치는 공식이 있습니다. CAP.

"C, A, P 셋 중 두 개만 가질 수 있다."

이 한 줄이 모든 것을 잘못 가르쳤습니다. 이 글에서는 그 잘못을 바로잡고, "P는 선택이 아니라 전제"라는 Brewer의 2012년 재해석까지 도달해 보겠습니다.

---

1. 왜 다시 CAP인가? — 모든 것의 시작

2000년 7월, 포르투갈에서 열린 ACM PODC 학회 키노트 무대에 UC 버클리의 에릭 브루어(Eric Brewer)가 섰습니다. 그는 Google과 Inktomi 같은 대규모 분산 검색 시스템을 직접 구축하면서 겪은 직관을 정리해 발표했는데, 그것이 후에 "CAP 이론"으로 불리게 되는 추측이었습니다.

당시만 해도 분산 데이터베이스는 무조건 ACID(원자성·일관성·격리성·지속성)를 지켜야 한다는 것이 거의 신성불가한 원칙이었습니다. 그러나 브루어는 외쳤습니다.

"분산 환경에서는 세 가지를 동시에 가질 수 없다. 반드시 하나를 포기해야 한다."

2년 뒤인 2002년, MIT의 Seth Gilbert과 Nancy Lynch가 이 추측을 수학적으로 증명합니다. 비동기 네트워크 모델에서 어떤 알고리즘도 Consistency, Availability, Partition Tolerance를 동시에 만족시킬 수 없다는 불가능성(impossibility result)이 도출됐고, 이로써 "브루어의 추측"은 정식 "CAP 이론"이 됩니다.

그런데 이상한 일이 벌어졌습니다. 이 이론이 가장 널리 읽히기 시작한 건 2010년대, NoSQL 운동과 함께였습니다.

오라클·MySQL 같은 RDBMS는 강한 일관성(C)을 지키기 위해 단일 마스터에 락을 거는 방식을 선호했습니다. 사용자 수천만 명 시대에 샤딩을 해도, 여러 노드에 흩어진 트랜잭션이 한 마스터를 두고 줄을 서야 했습니다. 응답이 느려지고 쓰기가 막히는 일이 비일비재했습니다.

그때 등장한 것이 Cassandra, MongoDB, DynamoDB 같은 NoSQL 데이터베이스들입니다. 이들은 강한 일관성을 일부 포기하는 대신 무한에 가까운 수평 확장성과 99.99%의 가용성을 제공하겠다고 선언했습니다.

개발자들은 당장 의아했습니다.

"우리 회사 주문 데이터가 방금 결제한 건이 안 보인다고? 그게 무슨 짓이야?"

그 의문의 실마리가 CAP 이론과 최종 일관성(Eventual Consistency) 에 있었고, 이 이론이 모든 분산 시스템 논의의 출발점이 되었습니다.

2012년, 브루어는 IEEE Computer에 "CAP Twelve Years Later"라는 회고 논문을 기고하며 이렇게 못 박습니다.

"CAP 이론은 '3개 중 2개'를 고르는 이분법이 아니다. 파티션 상황에서 C와 A 사이에서 미세하게 트레이드오프를 조율하는 지침이다."

이 한 문장이 지금도 분산 시스템 설계의 출발점입니다.

---

2. C, A, P의 정의를 다시 쓰다

자, 그럼 C, A, P를 정확히 다시 써보겠습니다. 흔히들 "일관성", "가용성", "분할 허용"이라고 한 줄로 끝내버리는데, 그게 오해의 80%입니다.

C (Consistency, 일관성)

모든 노드가 언제나 동일한 시점에 정확히 같은 데이터를 바라봐야 한다.

하지만 이 정의는 너무 느슨합니다. 학계에서 CAP의 C는 정확히 Linearizability(선형성) 을 의미합니다.

Linearizability란, 모든 읽기/쓰기 연산이 마치 "하나의 시계열로 정렬될 수 있다"는 보장입니다. 쉽게 말해, set(x, 5) 직후 어떤 노드에서 read(x)를 하든 반드시 5가 반환되어야 한다는 거예요. 시점이 어긋나서 옛 값이 나오면 일관성이 깨진 겁니다.

흔히 "결과적 일관성(Eventual Consistency)"이라고 부르는 것은 Linearizability보다 약한 일관성 모델입니다. "언젠가는 같아진다"는 약속이지 "지금 당장 같다"는 약속이 아닙니다. CAP의 C가 아니라는 뜻이죠.

A (Availability, 가용성)

다운되지 않은 정상 노드는 에러 없이 응답을 반환해야 한다.

여기서 중요한 함정이 있습니다. "정상 노드"의 학문적 정의는 메시지를 잃어버리지 않는 노드까지 포함합니다. 즉, 파티션이 발생해 메시지가 일부 유실되는 상황에서도 살아남은 노드는 반드시 정상적인 응답을 줘야 한다는 게 가용성의 진짜 의미입니다.

또 하나, 가용성은 "한 번이라도 응답하면 됨"이 아닙니다. 모든 요청에 대해 응답해야 합니다. 네트워크가 끊겼다는 이유로 빈 응답을 보내거나 무한히 기다리는 것은 가용성을 위배한 겁니다.

P (Partition Tolerance, 분할 용인성)

네트워크 단절이나 통신 지연으로 인해 노드 간 메시지가 유실되거나 전달되지 못하는 상황이 발생해도, 시스템 전체가 멈추지 않고 계속 동작할 수 있다.

이게 오늘 글의 가장 중요한 부분이라 다음 섹션에서 따로 다루겠습니다.

---

3. "P를 보장한다"는 것의 오해와 진실

분산 시스템을 처음 배우는 사람이 CAP을 공부하면 거의 100% 다음과 같이 정리합니다.

"우리 시스템은 트래픽이 폭증해도 잘 돌아가니까 AP 시스템이야."

또는:

"재고 데이터는 무조건 일관돼야 하니까 CP로 가자."

여기서부터 모든 게 무너집니다. 왜냐고요?

P는 선택의 대상이 아닙니다.

네트워크 파티션은 멀리 있는 데이터센터 두 곳 사이의 전용선이 끊기는 일부터, 가용존(AZ) 라우터 한 대가 펌웨어 업데이트로 죽는 일, 단순히 TCP 연결 한 번이 끊기는 일까지 — 분산 시스템에서는 언제든 일어날 수 있는 일입니다. Peter Deutsch의 "Fallacies of Distributed Computing" 1번 항목이 "The network is reliable(네트워크는 믿을 수 있다)"인 것도 같은 맥락입니다.

따라서 분산 시스템 설계자의 진짜 질문은 "P를 고르느냐 마느냐"가 아니라, 단 하나입니다.

"P가 발생했을 때 C와 A 중에 무엇을 더 우선할 것인가?"

그렇다면 왜 CA는 불가능한가?

CA가 성립하는 유일한 상황은 서버가 단 1대일 때입니다. 서버가 1대면 분산이 아니므로 네트워크 단절이 발생할 일이 없습니다. 데이터는 항상 일관되고, 서버만 안 죽으면 항상 응답하니 CA가 가능합니다.

문제는 서버가 2대 이상이 되는 순간 발생합니다. 둘이 통신하려면 케이블이나 무선이 필요한데, 그 순간 네트워크 장애는 운명처럼 따라붙습니다. 파티션이 일어났다는 것 자체를 시스템이 인지하는 순간, C와 A 중 하나를 선택해야 합니다.

다시 정리합니다.

분산 시스템에서 P는 전제(前提)이지 선택지가 아닙니다.
설계자는 오직 "파티션이 났을 때 C를 지킬 것인가, A를 지킬 것인가"만 결정합니다.

---

4. CP와 AP의 갈림길 — 네트워크가 끊기는 순간

자, 실제로 네트워크가 끊기는 시나리오를 그려보겠습니다.

서울 데이터센터에 노드 1·2·5가 있고, 부산 데이터센터에 노드 3·4·6이 있는 결제 시스템을 상상합니다. 평상시에는 두 데이터센터가 100km 떨어진 전용선으로 연결되어 모든 트랜잭션이 동기적으로 복제됩니다.

장애 발생: 부산 방향 전용선 두 개가 동시에 단절됩니다.

서울 노드 1·2·5는 살아 있고, 부산 노드 3·4·6도 살아 있습니다. 그러나 두 데이터센터는 서로 통신할 수 없습니다.

이 순간 시스템은 단 두 가지 중 하나를 선택해야 합니다.

선택지 1 — CP: 정합성을 지킨다

"서로 통신이 안 되니, 데이터 불일치를 막기 위해 일부 요청을 거부하거나 에러를 내자."

서울 노드는 부산 노드에게 데이터를 보낼 수 없으니, 쓰기 요청을 거부합니다. 또는 부산 노드 측의 모든 읽기/쓰기를 fail-fast로 처리해 클라이언트에게 "일시적 장애" 에러를 내려보냅니다.

이때 사용하는 패턴은 다음과 같습니다.

• Fail-Fast (빠른 실패): 파티션을 감지하면 즉시 에러를 반환. 무한 대기보다 클라이언트가 빠르게 다른 처리를 시도할 수 있어 전체 시스템 부하를 줄임.
• Read-Only 모드 전환: 쓰기만 거부하고 읽기는 허용. 캐시된 데이터라도 보여줘서 사용자 경험의 일부를 유지.
• Fencing Token (펜싱 토큰): 옛 Leader가 네트워크 복구 후 잘못된 결정을 내리는 것을 막기 위한 토큰. Split-Brain 방지.
• Bulkhead (벌크헤드, 격벽) 패턴: 문제가 생긴 영역(예: 부산 데이터센터)의 자원을 격리해 서울 데이터센터 자원을 보호.

대표적인 CP 시스템: ZooKeeper, etcd, HBase, 전통적인 RDBMS의 단일 마스터 + Replica 구성.

선택지 2 — AP: 가용성을 지킨다

"서로 통신이 안 돼도 각자 살아남아서 어떻게든 사용자 요청에 응답하자. 데이터는 나중에 맞춘다."

서울 노드는 자신이 가진 데이터로 모든 요청에 응답합니다. 부산 노드도 마찬가지입니다. 같은 사용자가 서울 노드에서 주문한 내역이 부산 노드에는 잠시 안 보일 수 있지만, 둘 다 응답합니다.

이때 사용하는 패턴은 다음과 같습니다.

• Circuit Breaker (서킷 브레이커): 일정 시간 실패가 임계치를 넘으면 자동으로 fallback 응답으로 전환. 시스템 전체가 무한 재시도로 죽는 것을 막음.
• Fallback (폴백): 캐시된 옛 값이라도 반환. "서비스가 죽었다"보다 "오래된 데이터지만 동작"이 나은 UX 제공.
• Eventual Consistency + 비동기 메시지: 네트워크 복구 후 비동기로 데이터를 맞춰 최종적으로 일관성 회복.
• Idempotency (멱등성): 네트워크 복구 후 중복 재시도로 인한 이중 결제 같은 사고 방지.

대표적인 AP 시스템: Cassandra, DynamoDB, Riak, Amazon S3.

트레이드오프 한눈에 보기

	CP (Consistency 우선)	AP (Availability 우선)
파티션 시 동작	쓰기 거부 / 에러 반환	일관성 깨진 채 응답
장점	데이터 무결성 보장	끊겨도 서비스 살아있음
단점	장애 시 일부 사용자 차단	일시적 데이터 불일치
적합한 도메인	결제 정산, 재고, 좌석 예약	장바구니, 상품 조회, SNS 피드
대표 시스템	ZooKeeper, etcd, HBase	Cassandra, DynamoDB, Couchbase

"그럼 우리 회사 시스템은 어떤 거야?"

정답은 둘 다일 수 있다입니다.

현대 시스템은 도메인별로 다른 일관성 요구사항을 가집니다. 결제 도메인은 CP가 맞고, 상품 상세 조회 도메인은 AP여도 무방합니다. 그래서 실무에서는 단일 CAP 라벨을 시스템에 통째로 붙이지 않고, 서비스 단위로 다르게 설계합니다.

[결제 서비스] → CP (강한 일관성)
[상품 카탈로그] → AP (가용성 우선)
[사용자 프로필] → 도메인별로 다른 정책

이게 단순 이분법으로 시스템을 라벨링하다 보면 실무 복잡성을 놓치게 되는 이유입니다.

---

5. 마무리 — CAP을 넘어

CAP은 분산 시스템 설계의 가장 기초적인 출발점이지만, 동시에 한계가 명확한 도구이기도 합니다. Brewer 본인도 2012년 회고에서 인정했듯이, "3개 중 2개"라는 단순 이분법은 실무의 복잡성을 담지 못합니다.

특히 CAP은 파티션이 발생했을 때만 이야기합니다. 평상시에는 어떤 트레이드오프가 있을까요? 일관성과 응답 속도(Latency) 사이의 트레이드오프는 어떻게 표현할까요?

이 질문에 답하기 위해 2012년, Yale 대학의 Daniel Abadi는 PACELC라는 새로운 프레임을 제안합니다. 이 이론은 "파티션 상황(P)뿐 아니라 평상시(E)에도" 시스템이 무엇을 우선하는지를 명시적으로 기술합니다.

그리고 평상시의 일관성을 결정하는 가장 실용적인 도구가 바로 Quorum(R + W > N) 과 합의 알고리즘(Raft) 입니다. 노드 수십 대가 흩어져 있는데 어떻게 데이터가 유실되지 않고 일관성을 유지하는지 — 그 답은 다음 편들에 있습니다.

• 2편: 이커머스 주문 시스템으로 보는 CP vs AP (feat. 블랙프라이데이)
• 3편: CAP을 넘어 PACELC로
• 4편: 분산 시스템은 실제로 어떻게 합의를 이루는가? (Quorum, Raft)

---

참고 자료

• Eric Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, Vol. 45, Issue 2, 2012.
• Seth Gilbert, Nancy Lynch, Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, ACM SIGACT News, Vol. 33, Issue 2, 2002.
• Martin Kleppmann, A Critique of the CAP Theorem, arXiv:1509.05393, 2015.
• Henry Robinson, CAP Confusion: Problems with Partition Tolerance, The Paper Trail, 2010.
• Peter Deutsch, The Eight Fallacies of Distributed Computing, 1994.