CAP 이론: 분산 시스템의 불가능한 삼위일체 (PACELC 포함)

1. 프롤로그 - "네트워크가 끊기면 어떻게 되지?"

분산 시스템을 공부하다 보면 어느 순간 이런 질문을 마주하게 된다.

"서울 서버와 뉴욕 서버가 실시간으로 동기화되어야 하는 시스템에서, 네트워크가 끊기면 어떻게 되지?"

처음엔 막연한 질문 같았다. 그런데 파고들수록 이 질문이 분산 시스템 설계의 핵심을 건드리고 있다는 걸 알게 됐다. 실제로 2008년 이후 상어에 의한 해저 케이블 손상은 구글이 공식적으로 인정한 문제다. 네트워크 단절은 SF가 아니라 현실이다.

그 상황에서 시스템은 둘 중 하나를 선택해야 한다.

옵션 1: 시스템을 멈춘다 서울과 뉴욕의 잔액 데이터가 다르면 이중 인출 사고가 날 수 있다. 그러니 네트워크가 복구될 때까지 모든 입출금을 중단한다. 고객들은 ATM 앞에서 "시스템 점검 중"이라는 메시지를 본다.

옵션 2: 일단 진행한다 각 지점이 알고 있는 잔액 정보로 입출금을 처리한다. 뉴욕에서 출금한 내역이 서울에 반영 안 될 수 있지만, 일단 서비스는 돌아간다. 나중에 네트워크 복구되면 데이터를 맞춘다.

은행 시스템이라면? 대부분 옵션 1을 선택한다. SNS라면? 옵션 2를 선택한다.

이게 바로 CAP 이론이다. 그리고 공부하면서 받아들이게 된 가장 뼈아픈 진실은 이것이었다: 완벽한 분산 시스템은 물리적으로 불가능하다.

---

2. 좌절의 순간 - "왜 세 개 다 안 돼요?"

CAP 이론을 처음 접했을 때 솔직히 납득이 안 됐다.

"데이터는 항상 정확해야 하고(Consistency), 서비스는 절대 다운되면 안 되고(Availability), 네트워크는 당연히 끊길 수 있으니 그것도 대비해야 하는데(Partition Tolerance)... 이게 왜 다 안 되지? 서버 더 사면 되는 거 아닌가?"

설명을 읽어봐도 뭔가 추상적이었다. 그런데 '네트워크가 끊겼을 때 어떤 일이 일어나는지'를 구체적으로 그려보니 이해가 됐다. 네트워크가 끊기는 순간, 시스템은 일관성을 포기하거나 가용성을 포기해야 했다. 둘 다 지킬 방법은 없었다.

---

3. 깨달음의 순간 - CAP의 진짜 의미

2000년, UC 버클리의 에릭 브루어(Eric Brewer) 교수가 CAP 이론을 발표했다. 2002년 MIT의 길버트와 린치가 수학적으로 증명했다. 결국 이거였다:

분산 시스템은 Consistency, Availability, Partition Tolerance 중 최대 2개만 보장할 수 있다.

Consistency (일관성)

"모든 노드가 같은 시간에 같은 데이터를 본다."

마치 쌍둥이 형제가 같은 기억을 공유하는 것과 같다. 서울에서 내가 방금 계좌에 100만 원을 입금했으면, 0.001초 뒤 뉴욕에서 조회해도 정확히 100만 원이 증가한 잔액이 보여야 한다.

만약 한 노드라도 업데이트가 안 됐다면? 에러를 뱉어야 한다. 틀린 정보를 주느니 차라리 "지금 확인 불가"라고 말하는 게 낫다.

// Strong Consistency 예시
async function withdraw(accountId, amount) {
  // 모든 복제본(replica)에 동기적으로 쓰기
  const results = await Promise.all([
    db.primary.update(accountId, -amount),
    db.replica1.update(accountId, -amount),
    db.replica2.update(accountId, -amount)
  ]);

  // 하나라도 실패하면 전체 롤백
  if (results.some(r => !r.success)) {
    await rollback(accountId, amount);
    throw new Error("Consistency violation - aborting");
  }

  return { success: true, balance: results[0].newBalance };
}

Availability (가용성)

"살아있는 노드는 무조건 응답한다."

식당 비유를 들어보자. 주방장이 아프다고 해서 식당 문을 닫는 게 아니라, 보조 주방장이라도 투입해서 일단 요리를 내놓는 것이다. 맛이 좀 다를 수 있지만, 손님은 굶지 않는다.

분산 시스템에서는 특정 노드가 죽거나 네트워크가 끊겨도, 살아있는 노드는 반드시 클라이언트 요청에 응답해야 한다. 그 응답이 최신 데이터가 아닐 수도 있다. "내가 아는 건 이거야. 정확한지는 장담 못 해"라는 식이다.

// High Availability 예시
async function getLikeCount(postId) {
  try {
    // Primary DB 시도
    return await db.primary.query(postId);
  } catch (primaryError) {
    console.warn("Primary down, using replica");

    try {
      // Replica 1 시도
      return await db.replica1.query(postId);
    } catch (replica1Error) {
      // Replica 2 시도 (데이터가 오래될 수 있음)
      return await db.replica2.query(postId);
    }
  }

  // 모든 노드 실패 시에만 에러
  // → 하지만 이러면 Availability 깨짐
}

Partition Tolerance (분할 내성)

"네트워크가 쪼개져도 시스템은 계속 돌아간다."

서울-뉴욕 간 네트워크가 끊겼다. 하지만 서울 사용자는 서울 DB를, 뉴욕 사용자는 뉴욕 DB를 쓸 수 있어야 한다. 각자 고립된 섬처럼 동작하다가, 나중에 다리가 복구되면 합치는 것이다.

중요한 것은: 분산 시스템에서 Partition은 "발생할 수 있다"가 아니라 "반드시 발생한다"는 점이다. 해저 케이블 끊김, 라우터 장애, 심지어 GC(Garbage Collection)로 인한 수백 ms 멈춤도 다른 노드 입장에선 네트워크 파티션이다.

그래서 정리해본다:

P는 선택사항이 아니다. 무조건 받아들여야 한다.

즉, 분산 시스템의 진짜 선택지는 CP vs AP 둘 중 하나다.

---

4. 깊이 파고들기 - CP vs AP 시스템의 실제

4.1 CP 시스템 - "틀린 정보를 주느니 차라리 죽겠다"

대표 사례: 은행 시스템

은행 ATM에서 돈을 뽑는다고 상상해보자. 잔액이 10만 원인데, 네트워크 지연 때문에 한 ATM은 10만 원이라고 알고 있고 다른 ATM은 5만 원(방금 출금 후)이라고 알고 있다. 이때 일관성이 깨진 ATM에서 10만 원을 출금하면? 잔액이 마이너스가 된다.

이런 상황을 막기 위해 CP 시스템은 가용성을 희생한다. 데이터 동기화가 확실하지 않으면 아예 서비스를 중단한다.

# CP 시스템 예시 (MongoDB 같은 동작)
def write_to_distributed_db(key, value):
    # Primary node에 쓰기 시도
    primary_success = primary_node.write(key, value)

    if not primary_success:
        raise Exception("Primary unreachable - refusing write")

    # Majority (과반수) 복제 성공해야 ACK
    replicas_ack = 0
    for replica in replica_nodes:
        if replica.is_reachable():
            if replica.write(key, value):
                replicas_ack += 1

    # 과반수 못 받으면 롤백하고 실패 처리
    if replicas_ack < len(replica_nodes) // 2:
        primary_node.rollback(key)
        raise Exception("Cannot guarantee consistency - aborting")

    return "Write successful with strong consistency"

CP 시스템 예시:

• MongoDB: Primary가 죽으면 새 Primary 선출될 때까지 쓰기 불가
• HBase: Region Server 장애 시 해당 region은 응답 중단
• ZooKeeper: 과반수 노드가 살아있어야만 동작
• Redis Cluster: Master-Slave sync 끊기면 쓰기 거부 옵션 제공

4.2 AP 시스템 - "좀 틀려도 괜찮으니 서비스는 살려라"

대표 사례: SNS 좋아요 카운터

인스타그램에서 내 게시물 좋아요가 서울 서버에는 1,000개로 보이고 뉴욕 서버에는 995개로 보인다면? 별 문제 없다. 30초 후에 맞춰지면 된다. 하지만 "서비스 점검 중"이라고 뜨면? 사용자는 이탈한다.

AP 시스템은 일관성을 희생한다. 각 노드가 독자적으로 쓰기를 받고, 나중에 데이터를 합친다.

# AP 시스템 예시 (Cassandra 같은 동작)
def write_to_ap_db(key, value):
    # 쓰기를 여러 노드에 "비동기적으로" 날림
    futures = []
    for node in all_nodes:
        # 응답 안 기다림 (fire and forget 아님, 하지만 실패해도 계속)
        future = node.async_write(key, value)
        futures.append(future)

    # 단 하나라도 성공하면 OK (실제로는 quorum 설정 가능)
    success_count = 0
    for future in futures:
        try:
            if future.get(timeout=0.1):  # 100ms만 대기
                success_count += 1
        except TimeoutError:
            pass  # 느린 노드는 스킵

    if success_count > 0:
        return "Write accepted (eventual consistency)"
    else:
        raise Exception("All nodes unreachable")

AP 시스템 예시:

• Cassandra: 노드 절반이 죽어도 나머지로 서비스 계속
• DynamoDB: Multi-region 설정 시 지역별 독립 쓰기 가능
• DNS: Name server 동기화 느려도 각자 응답
• CouchDB: Conflict를 허용하고 나중에 Merge

4.3 실제 시스템 선택 기준

내가 이해했던 가장 중요한 기준은 이것이다:

"데이터 불일치가 돈 손실/법적 문제를 일으키나?"

• Yes → CP (은행, 재고 관리, 예약 시스템)
• No → AP (SNS, 로그 수집, 조회수 카운터)

---

5. PACELC: CAP 이론의 현실적 확장

CAP는 하나의 문제가 있었다. 네트워크 장애(Partition) 상황만 가정한다는 것.

하지만 우리 시스템은 99.9%의 시간 동안은 네트워크가 정상이다. 그 평화로운 시간에도 trade-off는 존재한다. 이걸 보완한 게 PACELC 이론이다.

IF Partition 발생 → Availability vs Consistency 선택 ELSE (정상 상태) → Latency vs Consistency 선택

정상 상태의 딜레마

서울, 뉴욕, 런던 3개 서버가 완벽히 연결돼 있다고 치자. 사용자가 서울에서 데이터를 쓴다.

옵션 1: Synchronous Replication (동기 복제)

서울 쓰기 → 뉴욕 복제 대기 → 런던 복제 대기 → 모두 완료 → 사용자에게 OK

• 장점: 완벽한 Consistency
• 단점: 대기 시간(Latency)이 길다 (수백 ms)

옵션 2: Asynchronous Replication (비동기 복제)

서울 쓰기 → 즉시 사용자에게 OK → (백그라운드로 뉴욕/런던 복제)

• 장점: 빠른 응답(Low Latency)
• 단점: 복제 전에 조회하면 옛날 데이터 보임

결국 평화로운 상태에서도 "속도 vs 정확성" 사이에서 고민해야 한다. 이게 PACELC의 ELC 부분이다.

PACELC 시스템 분류

시스템	Partition 시	Normal 시	특징
MongoDB	CP	Latency 희생 (PC/EL)	Primary에 동기 쓰기 대기
Cassandra	AP	Latency 최소화 (PA/EL)	비동기 복제, 빠른 응답
DynamoDB	AP	튜닝 가능 (PA/E?)	Read/Write Consistency 옵션 제공
Google Spanner	CP	Latency 희생 (PC/EL)	하지만 7ms 동기화로 Latency 최소화

---

6. 실제 Lab - Quorum을 이용한 일관성 조율

AP 시스템도 최소한의 일관성을 챙기고 싶을 때가 있다. 이때 쓰는 게 Quorum(정족수) 개념이다.

수학적 원리: W + R > N

• N: 총 복제본 개수
• W: 쓰기 시 몇 개 노드에 성공해야 하나
• R: 읽기 시 몇 개 노드를 확인하나

핵심: W + R > N 이면, 읽기와 쓰기가 무조건 겹친다.

예를 들어 N=3, W=2, R=2라면:

• 쓰기 시 3개 중 2개 노드에 기록
• 읽기 시 3개 중 2개 노드를 확인
• 비둘기집 원리상, 읽은 2개 중 최소 1개는 최신 데이터를 가진 노드임

# Cassandra 스타일 Quorum 읽기/쓰기
def quorum_write(key, value, N=3, W=2):
    """
    3개 노드 중 2개에 쓰기 성공해야 OK
    """
    nodes = get_replica_nodes(key)  # [node1, node2, node3]
    success_count = 0

    for node in nodes:
        try:
            if node.write(key, value, timeout=0.5):
                success_count += 1
                if success_count >= W:
                    return True  # W개 성공하면 즉시 리턴
        except TimeoutError:
            continue

    return False  # W개 못 채우면 실패

def quorum_read(key, N=3, R=2):
    """
    3개 노드 중 2개 읽어서 최신값 선택
    """
    nodes = get_replica_nodes(key)
    responses = []

    for node in nodes:
        try:
            data = node.read(key, timeout=0.5)
            responses.append(data)
            if len(responses) >= R:
                break  # R개 모이면 충분
        except TimeoutError:
            continue

    # 타임스탬프 기준 최신값 선택
    return max(responses, key=lambda x: x.timestamp)

Quorum 튜닝 전략

W	R	특성	사용 사례
1	N	쓰기 빠름, 읽기 느림	로그 수집
N	1	쓰기 느림, 읽기 빠름	조회 많은 캐시
N/2+1	N/2+1	균형 잡힘	일반 서비스

DynamoDB는 이걸 ConsistencyLevel=QUORUM 같은 옵션으로 제공한다. Cassandra도 CONSISTENCY QUORUM 설정이 있다.

---

7. CAP를 뛰어넘으려는 시도들

7.1 Google Spanner: "우리는 CA를 만들었다?"

2012년, 구글이 Spanner 논문을 발표하면서 "사실상 CA 시스템"이라고 주장했다. 어떻게?

핵심: TrueTime API

CAP에서 일관성이 깨지는 근본 원인은 "각 서버의 시계가 다르기 때문"이다. 서울 서버는 10:00:00.100이라고 생각하고 뉴욕 서버는 10:00:00.050이라고 생각하면, 누가 먼저인지 알 수 없다.

구글의 해법:

1. 모든 데이터센터에 GPS 수신기와 원자 시계(Atomic Clock) 설치
2. 시간 오차를 7ms 이내로 줄임
3. TrueTime API는 [earliest, latest] 구간을 반환
4. 트랜잭션은 latest 시간까지 대기하여 순서 보장

# Spanner TrueTime 개념 예시 (의사코드)
def spanner_transaction(key, value):
    # TrueTime은 구간을 반환
    tt_now = TrueTime.now()
    # tt_now = [10:00:00.100, 10:00:00.107]  # 7ms 불확실성

    # 안전하게 latest까지 대기
    wait_until(tt_now.latest)

    # 이제 이 트랜잭션의 타임스탬프는 확실히 과거 모든 트랜잭션보다 뒤
    commit_with_timestamp(key, value, tt_now.latest)

하지만 엄밀히 말하면 Spanner도 CP다. 네트워크 파티션 시 과반수 못 받으면 쓰기 실패한다. 단지 99.999% 가용성으로 CA처럼 보일 뿐이다.

7.2 Eventual Consistency 패턴들

AP 시스템에서 쓰이는 "나중에 맞추기" 기법들:

1. Last-Write-Wins (LWW)

• 가장 최근 타임스탬프가 이긴다
• 문제: 시계 동기화 안 되면 데이터 유실 가능

2. Vector Clocks

• 각 노드의 버전을 벡터로 관리
• 예: {서울: 3, 뉴욕: 2, 런던: 1}
• Conflict 발생 시 애플리케이션이 해결

3. CRDTs (Conflict-free Replicated Data Types)

• 수학적으로 충돌이 불가능한 자료구조
• 예: 카운터(증가만), Set(합집합만)

// CRDT 카운터 예시
class GCounter {
  constructor(nodeId) {
    this.nodeId = nodeId;
    this.counts = {};  // {node1: 5, node2: 3}
  }

  increment() {
    this.counts[this.nodeId] = (this.counts[this.nodeId] || 0) + 1;
  }

  // 다른 노드 카운터와 병합
  merge(other) {
    for (let node in other.counts) {
      this.counts[node] = Math.max(
        this.counts[node] || 0,
        other.counts[node]
      );
    }
  }

  value() {
    return Object.values(this.counts).reduce((a, b) => a + b, 0);
  }
}

7.3 분산 합의 알고리즘

CP 시스템이 "어느 노드의 데이터가 진짜인가"를 결정하는 방법:

Raft 알고리즘 (간단한 버전)

1. Leader 선출 (과반수 투표)
2. Leader만 쓰기 허용
3. Follower들에게 복제
4. 과반수 ACK 받으면 커밋

Paxos 알고리즘 (어려운 버전)

• 같은 목적, 더 복잡하고 증명 완벽
• Raft는 Paxos를 "이해 가능하게" 만든 버전

---

8. 현실 세계의 적용 - 시스템 선택 가이드

8.1 Use Case별 추천

금융/결제

• 선택: CP
• 시스템: PostgreSQL (synchronous replication), MongoDB, Spanner
• 이유: 돈 문제는 틀리면 안 됨

SNS/컨텐츠

• 선택: AP
• 시스템: Cassandra, DynamoDB
• 이유: 일시적 불일치는 괜찮음, 다운은 안 됨

전자상거래 재고

• 선택: CP (재고), AP (조회수)
• 하이브리드: 재고는 정확해야 하지만, 상품 설명은 eventual OK

IoT 센서 데이터

• 선택: AP
• 시스템: InfluxDB, TimescaleDB
• 이유: 센서 데이터 하나 누락 vs 전체 서비스 다운

8.2 CAP 흔한 오해

오해 1: "CA 시스템을 만들 수 있다"

• 진실: 단일 서버 아니면 불가능. 네트워크 쓰는 순간 P는 필수.

오해 2: "무조건 둘만 선택"

• 진실: Quorum 같은 기법으로 중간 지점 찾기 가능. 100% C는 못 주지만 99% C는 줄 수 있다.

오해 3: "AP 시스템은 일관성이 없다"

• 진실: Eventual Consistency는 있다. "영원히 안 맞음"이 아니라 "나중에 맞음".

---

9. Jepsen Test: 거짓말쟁이를 잡아내는 도구

"우리 DB는 완벽한 일관성을 보장합니다!" - 많은 NoSQL 벤더들의 마케팅 문구였다.

2013년, 카일 킹스버리(Kyle Kingsbury)가 Jepsen이라는 테스트 프레임워크를 만들어서 이런 주장들을 검증하기 시작했다.

Jepsen이 하는 것

; Jepsen 테스트 의사코드
(deftest partition-test
  ; 1. 네트워크를 랜덤하게 쪼갬
  (partition-network [node1 node2] [node3])

  ; 2. 양쪽에서 동시에 쓰기
  (parallel
    (write! node1 :x 1)
    (write! node3 :x 2))

  ; 3. 네트워크 복구
  (heal-network)

  ; 4. 일관성 검증
  (assert (= (read! node1 :x) (read! node3 :x))))

Jepsen에 걸린 유명 DB들

• MongoDB 2.4: "Replica Set은 안전하다" → 데이터 유실 발견
• Redis: "AOF는 내구성 보장" → 특정 설정에서 유실
• Elasticsearch: "분산 검색 일관성" → Split-brain 발생
• Kafka: "메시지 손실 없음" → 특정 시나리오에서 손실

교훈: "신뢰하되 검증하라". 프로덕션에 쓰기 전에 Jepsen 리포트를 확인하는 게 전문가의 자세다.

---

10. 마무리 - 내가 정리해본 CAP의 본질

CAP 이론을 처음 접했을 때는 "제약"으로 느껴졌다. 하지만 지금은 이해했다. 이건 제약이 아니라 현실이다.

빛의 속도는 유한하다. 네트워크는 반드시 끊긴다. 시계는 동기화가 안 된다. 이런 물리 법칙 앞에서 우리는 선택해야 한다:

"내 시스템에서 더 중요한 게 뭐지? 정확성? 가용성?"

금융 시스템이라면 CP를 선택한다. 잘못된 잔액으로 돈이 사라지는 것보다, 잠시 서비스가 멈추는 게 낫다.

SNS 플랫폼이라면 AP를 선택한다. 좋아요 숫자가 1초 늦게 업데이트되는 것보다, 서비스가 다운되는 게 더 치명적이다.

결국 이거였다: CAP 이론은 "선택을 강요하는 이론"이 아니라 "선택을 돕는 도구"다.

내 시스템의 본질을 이해하고, 올바른 trade-off를 선택하는 것. 그게 이 이론이 가르쳐주는 핵심이라고 받아들였다.

---

11. 용어 사전 (Glossary)

1. CAP Theorem: 분산 시스템의 Consistency, Availability, Partition Tolerance 중 최대 2개만 보장 가능하다는 정리.
2. Partition (네트워크 분할): 노드 간 통신이 물리적으로 끊긴 상태. 해저 케이블 손상, 라우터 장애 등.
3. Eventual Consistency (최종 일관성): 쓰기가 멈추면 언젠가는 모든 노드가 같은 값을 보게 된다는 약한 보장.
4. Strong Consistency (강한 일관성): 쓰기 직후 모든 읽기가 최신값을 반환. Linearizability라고도 함.
5. Quorum: 정족수. N개 노드 중 과반수(N/2+1) 이상의 합의를 받는 방식.
6. PACELC: CAP 확장판. Partition 시 A vs C, Else(정상) 시 L vs C 선택.
7. Vector Clock: 분산 이벤트 순서를 추적하는 자료구조. Conflict 감지 가능.
8. CRDT: 자동으로 충돌 해결되는 데이터 타입. 수학적으로 교환/결합 법칙 만족.
9. Split-brain: 네트워크 파티션으로 두 그룹이 각각 독립적으로 동작하는 상태.
10. TrueTime: Google Spanner의 시간 API. GPS+원자시계로 7ms 이내 오차.

---

12. FAQ & Common Questions

Q1: RDBMS는 무조건 CA인가요?

A: 단일 서버면 CA지만, 복제(Replication)하는 순간 CAP 지배를 받는다.

• MySQL Async Replication → AP (약한 일관성)
• PostgreSQL Sync Replication → CP (가용성 희생)

Q2: Redis는 CP인가요 AP인가요?

A: 설정에 따라 다르다.

• min-replicas-to-write 2 설정 → CP (복제 안 되면 쓰기 거부)
• 기본 설정 → AP (Master만 살아있으면 쓰기 허용)

Q3: 블록체인은 뭔가요?

A: 전형적인 AP 시스템. Fork(분기)를 허용하고 나중에 가장 긴 체인 선택(Eventual Consistency). 하지만 Bitcoin은 10분 기다리면 사실상 Finality(CP적 특성)를 가진다고 볼 수 있다.

Q4: DynamoDB는 CP인가요 AP인가요?

A: 기본은 AP. 하지만 ConsistentRead=true 옵션 주면 CP처럼 동작. "Tunable Consistency"라고 한다.

Q5: CAP를 완전히 극복한 시스템은 없나요?

A: 없다. Spanner도 엄밀히는 CP다. 단지 99.999% 가용성으로 CA처럼 보일 뿐. 물리 법칙은 못 깬다.

Q6: Microservice 아키텍처에서는 어떻게 적용하나요?

A: 각 서비스마다 다르게 적용.

• 주문 서비스 → CP (결제 일관성)
• 추천 서비스 → AP (조금 오래된 추천도 OK)
• 검색 서비스 → AP (색인 지연 허용)

---