DISTRIBUTED SYSTEMS

브루어의 삼각형 너머: CAP 정리가 드러낸 분산 시스템의 원죄와 타협의 미학

일관성, 가용성, 분할 내성 — 왜 우리는 셋 중 둘만을 가질 수 있는가, 그리고 PACELC가 던진 새로운 질문

Distributed Systems Theory · 16 min read

2000년 7월, UC 버클리의 Eric Brewer 교수는 PODC(Principles of Distributed Computing) 학회 기조연설에서 훗날 “CAP 정리”로 불리게 될 추측을 제시했다. 분산 시스템은 일관성(Consistency), 가용성(Availability), 분할 내성(Partition tolerance) 중 단 두 가지만을 동시에 보장할 수 있다는 주장이었다. 단순해 보이는 이 문장이 이후 20여 년간 데이터베이스 산업 전체의 설계 사상을 재편했다. 이 글은 우리가 과거 포르투갈어권 호스팅 인프라를 운영하며 부딪혔던 실제 장애 경험을 바탕으로, CAP 정리가 왜 필연인지, 그리고 그것이 실무에서 어떻게 해석되고 있는지를 정리한다.

1. 정리의 정식 서술: Gilbert와 Lynch의 증명

Brewer가 2000년에 제시한 것은 엄밀히 말해 “추측”이었다. 이를 수학적으로 증명한 것은 2002년 MIT의 Seth Gilbert와 Nancy Lynch였다. 그들의 논문 “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services”는 CAP을 다음과 같이 정식화한다.

Gilbert-Lynch의 증명은 간결하다. 두 노드 G1, G2가 있고 두 노드 사이의 네트워크가 단절되었다고 가정하자(P). 클라이언트가 G1에 쓰기를 수행하고, 거의 동시에 G2에 읽기를 수행한다. G2는 네트워크 단절로 G1의 쓰기를 알 수 없다. 이때:

• G2가 “오래된 값”을 반환하면 일관성(C)이 깨진다.
• G2가 “모르겠다”며 응답을 거부하면 가용성(A)이 깨진다.
• G2가 G1과 통신을 시도하다 무한정 기다리면 분할 내성(P)을 포기한 것이다.

즉, 분할이 발생한 순간 C와 A 중 하나는 포기할 수밖에 없다. 이것이 CAP 정리의 본질이다.

2. 흔한 오해: “셋 중 둘을 고른다”는 잘못된 구호

CAP이 대중화되면서 “CA 시스템, CP 시스템, AP 시스템”이라는 분류가 유행했다. 그러나 이 도식적 분류는 Brewer 자신이 2012년 IEEE Computer 기고문 “CAP Twelve Years Later”에서 직접 반박한 것이다.

핵심은 이것이다. 네트워크 분할은 선택 사항이 아니다. 현실의 분산 시스템에서 네트워크 단절, 지연, 메시지 유실은 반드시 발생한다. 따라서 P는 포기할 수 있는 대상이 아니라 감내해야 할 전제 조건이다. 그렇다면 의미 있는 선택지는 오직 하나다. 분할이 발생했을 때 C를 택할 것인가, A를 택할 것인가?

2.1. “CA 시스템”이라 불리는 것들의 정체

전통적 관계형 데이터베이스인 MySQL, PostgreSQL의 단일 인스턴스는 흔히 “CA”로 분류된다. 그러나 단일 노드 시스템에 대해 CAP을 논하는 것은 애초에 범주 착오다. 분할이 없는 시스템에 분할 내성을 논할 이유가 없기 때문이다.

만약 이들을 프라이머리-리플리카 복제 구성으로 확장한다면, 네트워크 분할 시 반드시 선택의 기로에 서게 된다. MySQL의 반동기 복제(semi-sync), PostgreSQL의 synchronous_commit 설정은 이런 선택의 스펙트럼을 제어하는 도구들이다.

3. CP 시스템의 세계: 일관성을 선택한 자들

3.1. HBase와 Bigtable 계열

HBase는 Google Bigtable의 오픈소스 구현으로, 리전 서버(Region Server)가 담당 리전의 데이터를 독점적으로 소유하는 구조다. 특정 리전 서버가 네트워크 분할로 격리되면, 그 리전의 데이터에 대한 접근은 중단된다. 다른 노드가 자동으로 그 리전을 넘겨받기까지(ZooKeeper 세션 타임아웃 + 재할당 과정) 수 초에서 수십 초가 소요된다. 이 공백 기간 동안 가용성은 희생되지만, 데이터 일관성은 절대적으로 보장된다.

3.2. etcd, ZooKeeper, Consul

쿠버네티스의 메타데이터 저장소인 etcd, 하둡 에코시스템의 조정자인 ZooKeeper, 서비스 디스커버리 도구인 Consul은 모두 Raft 또는 ZAB 같은 합의 프로토콜 위에 세워진 CP 시스템이다. 이들의 공통점은 쿼럼(quorum)을 유지하지 못하면 쓰기를 거부한다는 것이다.

5노드 etcd 클러스터를 예로 들면, 최소 3노드가 서로 통신 가능해야 쓰기가 성공한다. 네트워크 분할로 2-3 분할이 발생하면 2노드 쪽은 쓰기를 거부하고, 3노드 쪽만 서비스를 계속한다. 이 설계 철학은 명확하다. 잘못된 값을 반환하느니 아무것도 반환하지 않는 편이 낫다.

3.3. Spanner의 반전: TrueTime이라는 하드웨어적 해법

Google Spanner는 CAP의 난제를 하드웨어 수준에서 재정의한 흥미로운 시스템이다. 각 데이터 센터에 GPS 수신기와 원자 시계를 배치하고, 이를 기반으로 TrueTime API를 구현했다. 시간에 명시적인 불확실성 구간(ε)을 도입하고, 이 구간만큼 대기함으로써 지리적으로 분산된 노드들 사이의 트랜잭션 순서를 물리적 시간으로 보장한다.

Spanner의 논문 저자들은 자신들의 시스템을 “실질적으로 CA”라고 표현했다. 분할이 발생하지 않는 한 C와 A를 모두 제공하며, 분할이 발생하면 C를 택한다. 이것이 이론적으로 불가능하다는 의미가 아니라, Google이 자사의 전용 광 네트워크에서 분할 발생 자체를 극도로 드물게 만들었다는 엔지니어링의 승리를 의미한다.

4. AP 시스템의 세계: 가용성을 택한 자들

4.1. Dynamo 계열: Cassandra, Riak, DynamoDB

Amazon이 2007년 SOSP에서 발표한 Dynamo 논문은 AP 설계의 이정표다. 이들은 “고객이 장바구니에 물건을 넣을 수 없는 쇼핑몰”을 가장 큰 악몽으로 규정하고, 어떤 상황에서도 쓰기를 받아들이는 쪽을 택했다. 대신 일관성은 최종적 일관성(eventual consistency)이라는 약한 보장으로 완화했다.

Dynamo 계열의 핵심 메커니즘은 다음과 같다.

• 벡터 시계(Vector Clock): 각 노드의 쓰기 버전을 벡터로 관리하여, 동일 키에 대한 동시 쓰기의 인과 관계를 추적한다.
• 튜너블 일관성(Tunable Consistency): R + W > N 조건을 만족하면 읽기-쓰기 간 일관성이 보장된다. N은 복제본 수, R은 읽기 쿼럼, W는 쓰기 쿼럼이다.
• 힌트 핸드오프(Hinted Handoff): 목적 노드가 접근 불가능할 때 다른 노드가 임시로 받아두었다가 복구 시 전달한다.
• 리드 리페어(Read Repair): 읽기 시 여러 복제본을 비교하여 오래된 값을 즉시 업데이트한다.

4.2. CRDT와 병합 가능한 충돌 해결

최종적 일관성의 철학적 질문은 이것이다. 같은 데이터에 대해 두 노드가 독립적으로 쓴 뒤 재결합할 때, 어떤 값을 유지해야 하는가? 단순한 “Last Write Wins” 전략은 사용자가 추가한 장바구니 아이템을 잃게 만들 수 있다.

CRDT(Conflict-free Replicated Data Types)는 이 문제에 우아한 해법을 제시한다. 연산의 순서와 무관하게 항상 같은 결과로 수렴하는 데이터 구조를 정의하는 것이다. G-Counter, PN-Counter, OR-Set, LWW-Register 등이 대표적이다. Redis의 일부 기능, Riak, Redis Labs의 CRDB 등이 CRDT를 활용한다.

“분산 시스템은 일관성을 약속하지 않는다. 다만
어떤 순간에 어떤 일관성을 약속할지를 설계자가 선택할 뿐이다.”

5. PACELC: Daniel Abadi의 확장

CAP은 분할이 발생했을 때의 선택을 다룬다. 그러나 분할이 없는 평상시에도 분산 시스템은 또 다른 트레이드오프에 직면한다는 것을 예일 대학의 Daniel Abadi가 2010년 지적했다. 그의 PACELC 정리는 다음과 같이 확장된다.

평상시에도 강한 일관성을 보장하려면 쓰기는 반드시 여러 노드의 확인을 받아야 하고, 이는 지연을 늘린다. 반대로 지연을 줄이려면 일부 노드의 확인을 건너뛰어야 하고, 이는 일시적 비일관을 감수한다는 뜻이다. PACELC 축으로 기존 시스템들을 분류하면 다음과 같다.

시스템	분할 시 (PAC)	평상시 (ELC)
MongoDB (기본 설정)	PC (일관성 우선)	EC (일관성 우선)
Cassandra	PA (가용성 우선)	EL (지연 우선)
DynamoDB	PA	EL
Spanner	PC	EC
etcd / ZooKeeper	PC	EC

PACELC의 통찰은 분산 시스템 선택이 단순히 “장애 시 어떻게 되느냐”의 문제가 아니라, 평상시에도 지속적으로 작동하는 설계 철학의 문제라는 점이다.

6. 실무에서의 전략: 일관성의 스펙트럼

이론적으로 일관성은 이분법이 아니다. Jepsen 프로젝트로 유명한 Kyle Kingsbury가 정리한 일관성 모델의 계층은 다음과 같다.

• Strict Serializable: 가장 강한 보장. 모든 연산이 실시간 순서를 존중하는 직렬 실행과 동등.
• Linearizable (선형화 가능성): 각 객체에 대한 연산이 순간적으로 일어난 것처럼 보임.
• Sequential Consistency: 모든 프로세스가 동일한 연산 순서를 관찰.
• Causal Consistency: 인과 관계가 있는 연산의 순서만 보장.
• Eventual Consistency: 새 쓰기가 없으면 결국 모든 복제본이 수렴.

실무의 과제는 각 유스케이스가 요구하는 일관성 수준을 정확히 파악하는 일이다. 사용자 프로필처럼 자주 변경되지 않고 구 버전을 잠시 보여도 되는 데이터에는 최종적 일관성으로 충분하다. 반면 금융 거래, 재고 관리, 좌석 예약처럼 이중 판매(double-booking)가 절대 허용되지 않는 영역에는 선형화 가능성 또는 그 이상이 필요하다.

하나의 서비스 안에서도 데이터의 성격에 따라 서로 다른 일관성 모델을 적용하는 것이 현대 분산 시스템 설계의 정석이 되었다. 장바구니는 Cassandra에, 결제 기록은 Spanner 또는 CockroachDB에, 세션은 Redis에 나눠 담는 구성이 그런 예다.

7. 결론: 이론의 엄격함과 실무의 유연함 사이에서

CAP 정리는 분산 시스템의 불완전성에 대한 경고가 아니라, 설계자에게 부과된 강제된 선택의 언어다. 네트워크는 반드시 실패하고, 그 실패의 순간에 시스템은 반드시 답해야 한다. “아직 확실하지 않아요”라고 말할 것인가, “아마 이 값이에요”라고 말할 것인가.

우리가 과거 포르투갈어권 무상 호스팅 인프라를 운영하며 가장 뼈아프게 배운 것은, 일관성과 가용성 어느 한쪽을 포기한다는 결정은 사용자에 대한 약속의 성격을 바꾸는 일이라는 사실이었다. AP 시스템을 택했다면, 사용자에게 “가끔 방금 쓴 값이 안 보일 수 있어요”를 암묵적으로 동의받는 것이다. CP를 택했다면, “가끔 몇 초간 아무 것도 못 볼 수 있어요”를 받아들인 것이다. 어느 쪽도 공짜가 아니다.

CAP은 20년이 지난 오늘날에도 여전히 유효하다. 새로운 합의 알고리즘(Raft, Paxos, PBFT), 새로운 복제 전략, 새로운 하드웨어(원자 시계, RDMA, NVDIMM)가 등장해도, 빛의 속도와 실패의 확률은 변하지 않기 때문이다. 분산 시스템 설계자의 역할은 이 물리적 제약 안에서 사용자에게 가장 유용한 약속을 선택하는 것, 그리고 그 약속을 정직하게 지키는 것이다.