Juicycrunch Carrot Blog | The CAP Theorem

CAP Theorem

A distributed system can deliver on only two of three desired characteristics: Consistency, Availability, and Partition Tolerance.

Eric Brewer — ACM PODC 2000 (Symposium on Principles of Distributed Computing)

CAP 이론은 분산 시스템은 일관성(Consistency), 가용성(Availability), 분할 내성(Partition Tolerance) 이 세가지 특성을 동시에 보장할 수 없다. 라는 이론입니다.

세가지 특성을 동시에 보장할 수 없다라는건 곧 trade-off 를 생각하라는 의미이기도 합니다.

CAP theorem 은 “C, A, P 중 두 개를 고르는 규칙” 으로 이해하면 안됩니다.

Eric Brewer 가 강조한것은 ‘P는 선택 가능한 옵션이 아니다’ 입니다.

더 정확한 의미는 ‘Partition 이 발생한 상황에서는 Consistency 와 Availability 를 동시에 보장할 수 없다.’ 입니다.

다르게 표현하면 ‘Partition 이 발생했을 때 Consistency 와 Availability 사이에서 어떤 보장을 유지할 것인가?’ 입니다.

용어 설명

특성	설명
일관성 (Consistency)	어떤 요청이 성공한 이후에는 모든 노드가 동일한 최신 데이터를 반환해야 합니다.
가용성 (Availability)	모든 요청에 대해 성공 또는 실패 여부와 관계없이 응답을 반환해야 합니다.
분할 내성 (Partition Tolerance)	노드 간 네트워크가 끊기거나 메시지가 유실, 지연되는 네트워크 분할(Partition)이 발생하더라도 시스템이 계속 동작할 수 있어야 합니다.

Eric Brewer

Eric Brewer 는 2000년 웹 서비스 환경을 배경으로 이 정리를 제시하였고 2002년에 MIT의 Seth Gilbert 와 Nancy Lynch 가 이를 수학적 모델로 정의하고 증명하였습니다.

예시

네트워크 분할이 발생했을 때 시스템은 둘 중 하나를 선택해야 합니다.

AP: 틀릴 수도 있지만 일단 답은 하겠다
CP: 틀린 답을 줄 바에야 답하지 않겠다

실무에서 실제 시스템을 CAP 이론에 빗대어 AP or CP 로 딱 잘라 분류하기 어려운 경우가 많습니다. 아래의 예시는 이해를 돕기위한것이라고 생각해주시기 바랍니다.

Read Replica DB 가 여러개일 때

---
config:
  layout: elk
---
flowchart TB
    WRITE["Write"]
    READ["Read"]
    PRIMARY["Primary DB"]
    READ_REPLICA_1["Replica DB"]
    READ_REPLICA_2["Replica DB"]
    READ_REPLICA_3["Replica DB"]

    WRITE .-> PRIMARY
    PRIMARY -- "Partition" --> READ_REPLICA_1
    PRIMARY -- "Partition" --> READ_REPLICA_2
    PRIMARY -- "Partition" --> READ_REPLICA_3
    READ .-> READ_REPLICA_1
    READ .-> READ_REPLICA_2
    READ .-> READ_REPLICA_3

이번에는 하나의 데이터베이스를 여러 개의 Replica DB에 복제하는 상황을 생각해보겠습니다.

쓰기 요청은 Primary DB에서 처리하고, 변경된 데이터는 여러 Replica DB로 복제됩니다.

평상시에는 모든 DB가 동일한 데이터를 가지고 있기 때문에 문제가 없습니다.

하지만 Primary DB와 Replica DB 사이에 네트워크 분할(Partition) 이 발생한다면 상황이 달라집니다.

예를 들어 Primary DB에서 다음과 같이 데이터가 변경되었다고 가정해보겠습니다.

Primary DB
balance = 100 → 50

네트워크 분할 때문에 Replica DB가 이 변경 사항을 전달받지 못했다면 Replica DB에는 여전히 다음과 같은 데이터가 남아 있을 수 있습니다.

Replica DB
balance = 100

이때 Replica DB에 조회 요청이 들어왔다고 생각해봅시다.

AP를 우선하는 방식이라면

최신 데이터인지는 확실하지 않지만, 일단 현재 가지고 있는 데이터를 반환

Replica DB는 100을 반환할 수 있습니다. 다시 말해 오래된 데이터를 반환하더라도 요청에는 계속 응답합니다.

CP를 우선하는 방식이라면

잘못된 데이터를 반환하지 않기 위해 요청을 처리하지 않음

최신 데이터임을 보장할 수 없다면 응답을 포기하여 일관성을 지키는 것입니다.

한계

CAP 정리는 분산 시스템의 중요한 trade-off 를 설명하는 데 유용하지만 실제 시스템의 특성과 설계상의 선택을 모두 설명하기에는 한계가 있습니다.

PACELC

CAP 이론이 주로 네트워크 분할이 발생했을 때의 trade-off 를 설명한다면 정상적인 상황에서도 분산 시스템은 또 다른 문제를 마주하게 됩니다.

Daniel Abadi는 2010년 이러한 문제를 설명하기 위해 PACELC 라는 개념을 제안했습니다. 이후 2012년 IEEE Computer에 발표한 논문에서 이를 학술적으로 정리했습니다.

Partition이 발생하면 → Availability VS Consistency

정상적인 상황에서는 (Else) → Latency VS Consistency

네트워크 분할이 발생했을 때는 CAP에서 이야기한 것처럼 일관성과 가용성 사이의 트레이드오프가 발생합니다.

하지만 네트워크가 정상적인 상황에서도 여러 노드에 데이터를 동기적으로 복제하려면 서로의 상태를 확인하는 과정이 필요하고 이는 Latency 증가로 이어질 수 있습니다.

마치며

CAP 이론의 핵심은 단순히 C, A, P 중 두 가지를 선택하는 것이 아닙니다. 그리고 특정 시스템을 단순히 AP 또는 CP로 분류하기 위한 규칙이라기보다

분산 시스템에서 장애와 네트워크 지연이 발생했을 때 우리는 무엇을 보장하고 무엇을 포기할 것인가?

를 생각하게 해주는 하나의 설계 관점이라고 볼 수 있습니다.