CAP Theorem은 분산시스템에서 일관성(Consistency), 가용성(Availability), 분할 용인(Partition tolerance)이라는 세 가지 조건을 모두 만족할 수 없다는 정리로, 세 가지 중 두 가지를 택하라는 것으로 많이 알려졌다. 특히 NoSQL이 인기를 끌면서 널리 퍼졌지만, 정리 자체가 제대로 이해하기 어렵게 정의되어 있어서 이해하기가 쉽지 않다. 그 때문인지 VoltDB 개발자 스스로 VoltDB를 CA로 말하기도 했고, Couchbase가 위키피디아에 CA로 등재되었다가 나중에 CP로 수정되는 사태가 발생할 정도이니 말 다했다. 그동안 이 문제에 대해 많은 논의가 이루어졌는데, 이 글에서는 이에 대해 다뤄보려고 한다.

Diagram of CAP Theorem
CAP Theorem을 소개할 때 널리 사용되는 다이어그램이지만, 그림 자체가 틀렸을 뿐만 아니라 이 정리를 잘못 이해하기 쉽게 만든다. 이에 대해서는 글에서 차차 설명될 것이다.

CAP Theorem, 무엇이 오해이고 무엇이 진실인가?

CAP는 분산시스템 설계에서 기술적인 선택을 돕는다. 분산시스템이 모든 것 특성을 만족시킬 수 없음을 인지하게 하고 선택지를 제공해주는 것이다. 하지만 CAP를 명확하게 이해하기 위해서는 다음과 같은 문제들이 해결되어야 한다.

  • CAP Theorem을 다루는 글에서 나타나는 Partition tolerance의 정의가 일관성이 없다. 2000년에 Brewer가 이 정리를 발표할 때 P에 대한 정의는 다음과 같았다.
The system continues to operate despite arbitrary message loss or failure of part of the system

하지만 2002년에 이에 대해 Gilbert와 Lynch가 이 정리에 대해 증명에 사용된 P에 대한 새로운 정의는 다음과 같다.

The network will be allowed to lose arbitrarily many messages sent from one node to another

두 정의는 큰 차이가 있지만, 아직도 Brewer가 처음 내세운 정의가 많은 곳에서 사용되며 심지어 한국 위키피디아에도 이 버전으로 번역되어 있다. 하지만 정확한 정의는 후자가 맞으며 그래야 이 정리가 성립한다. 따라서 분할 내성 보다는 분할 용인이라고 번역하는 것이 더 올바를 것이다.

  • CAP Theorem의 정의를 살펴보면 마치 C,A,P가 동등한 선상에 있는 것처럼 느껴진다. 이런 연유로 C,A,P가 모두 분산시스템의 특성에 대한 것으로 여겨지지만, 실상은 그렇지 않다. 앞에서 언급한 정의를 생각해본다면, C와 A는 분산시스템의 특성이지만, P는 그 분산시스템이 돌아가는 네트워크에 대한 특성이다. 이 정리가 처음 발표될 때의 P에 대한 정의는 P가 정말로 분산시스템의 특성인 양 서술해 놓았다. 네트워크가 분산시스템의 일부라고 해도 엄밀히 따지면 대상이 다르다고 봐야 한다.

  • CAP Theorem의 정의가 이해하기 어렵게 되어 있다. 세 가지 특성 중 두 개까지 고를 수 있다는 것으로도 많이 알려졌는데 마치 P를 포기하고 CA를 선택할 수도 있는 것 같은 기분을 들게 한다. 하지만 실상은 그렇지 않다. P의 정의는 네트워크가 임의의 메시지 손실을 할 수 있다는 것을 허용하느냐이다. 다시 말해 네트워크가 가끔 장애가 날 수 있다는 것을 인정하느냐는 것이다. P의 선택을 배제하려면, 절대로 장애가 나지 않는 네트워크를 구성해야 하지만 그런 것은 이 세상에 존재하지 않는다. 따라서 원하든 원하지 않든 P는 선택되어야 하며 결국 선택권은 C나 A중 하나밖에 없다.

  • 또 하나의 중요한 문제는 C와 A가 비대칭적이라는 것이다. AP를 선택한 것으로 많이 알려진 Cassandra를 생각해보자. 이 시스템은 네트워크 장애 상황이든 정상 상황이든 C를 포기하도록 되어있다. HBase의 경우에는 장애상황일 때만 A를 포기하고 정상일 때는 A를 만족한다. CAP Theorem은 네트워크가 장애 상황일 때만 대칭성이 있고 정상일 때에는 그렇지 않다.

이 모든 문제와 모순을 해결하려면 CAP가 서술하는 상황을 장애상황으로 국한지어야 한다. 애초에 P는 네트워크 장애가 있을 수 있다는 것을 인정하느냐의 문제이고 이는 인정 할 수밖에 없는 문제이므로 처음부터 선택되어있는 것이다. 결국, CAP Theorem이 내포하고 있는 의미는 분산시스템에서 네트워크 장애상황일 때 일관성과 가용성 중 많아도 하나만 선택할 수 있다는 것이다. 하지만 이런 식의 해석은 정상 상황일 때의 분산시스템 동작을 서술해주지 못한다. 이에 대해 Daniel Abadi가 PACELC라는 아주 우아한 표기법을 제시하였다.

CAP보다는 PACELC를 쓰자

CAP는 분산시스템 디자이너의 선택에 도움을 주는 정리다. CAP가 장애 상황일 때의 선택에 대해 서술하는 것으로 생각하면, 정상 상황일 때의 선택에 대해 서술하지 못하게 된다. 그래서 정상상황일 때와 장애상황을 때를 나누어 설명하자는 것이 PACELC의 핵심이다. PACELC의 의미를 인용하자면 아래와 같다.

if there is a partition (P) how does the system tradeoff between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system tradeoff between latency (L) and consistency (C)?

PACELC Diagram

다시 말해 파티션(네트워크 장애)상황일 때에는 A와 C는 상충하며 둘 중 하나를 선택해야 한다는 것이다. 당연한 얘기다. 변경된 값을 모든 노드에서 바라볼 수 있도록 하려면 신뢰성 있는 프로토콜을 이용하여 데이터에 관여하는 모든 노드에 데이터가 반영되어야 한다. 하지만 네트워크 단절이 일어나 몇 개의 노드에 접근할 수 없을 때 C를 위해 데이터 반영이 아예 실패하던지 C를 포기하고 일단 접근 가능한 노드들이게 만 데이터를 반영하던지 둘 중의 하나만 골라야 한다. 또한, 정상상황일 때에는 L과 C는 상충하며 둘 중 하나를 선택해야 한다. 모든 노드들에 새로운 데이터를 반영하는 것은 상대적으로 긴 응답시간이 필요하기 때문이다. 이를 몇 가지 NoSQL 시스템에 적용하면 다음과 같다.

  • HBase는 PC/EC이다. 장애 상황일때 C를 위해 A를 희생한다. 그렇지 않은 경우에도 C를 위해 L을 희생한다.
  • Cassandra는 PA/EL이 가능하도록 디자인 되었다. 설정에 따라 Eventual Consistency의 특성을 가지게 되는데, 이 경우 PA/EL이 된다. 장애 상황인 경우에는 가능한 노드에만 데이터를 반영하고 정상으로 복구되면 필요한 노드에 데이터를 모두 반영한다. 정상상황일때도 Latency를 위해 모든 노드에 데이터를 반영하지 않는다.
  • Brewer가 제시한 가상의 분산시스템은 PA/EC이다. 정상적인 경우에는 모든 노드에서 같은 메세지를 볼 수 있도록 쓰기 연산이 일어나는데 P 상황인 경우, 이를 판단하여 일단 접근 가능한 만큼만 데이터를 반영한다 결과적으로 시스템은 디운되지 않지만 절단된 노드들 끼리는 데이터를 주고 받지 못하게 된다. 장애상황이 복구되면 이를 감지하여 전달하지 못한 데이터를 반영한다. 장애상황일때에만 C를 포기하고 보통의 상황에서는 강력한 C를 가져가는 것이다. Brewers NoSQL Proposal
  • PNUTS는 PC/EL이다. 장애상황일 때는 C를 위해 A를 희생하지만, 평소에는 L을 위해 C를 희생한다. 시스템이 정상일 때에도 C를 충족시키지 못하는데 네트워크 장애일 때 C를 위해 A를 포기한다니 말이 안 되는 것 같지만, 여기서 PC의 의미는 평소만큼의 C를 보장하기 위해 A를 희생시킨다는 의미로 받아들이면 된다. PNUTS의 Consistency Level은 Timeline Consistency이다. 일반적으로 생각하는 Consistency보다는 약하지만, 장애상황일 때에도 정상상황일 때와 같은 Consistency Level을 보장하기 위해 요청 자체를 실패시킨다.

위에서 소개한 사례 중 마지막 두 개를 CAP Theorem으로 표현하려고 해보려고 하려면 어떻게 표현해야 할지 잘되지 않는다. 이처럼 CAP로 표현하는 것보다 PACELC로 표현하는 것이 훨씬 명확하다. 앞서 살펴본 CAP의 문제점도 전혀 없다.

못다 한 이야기

RDBMS에 CAP를 적용하여 CA로 분류하는 것을 자주 보았다. Brewer가 처음 발표할때에도 이렇게 표현을 하기도 했고, 하나의 인스턴스로 운영되는 RDBMS의 경우 네트워크로 연결되어 있지 않으므로 네트워크 단절을 배제할 수 있다는 점에서 이렇게 분류하는게 어느 정도 납득은 간다. 하지만 CAP는 분산시스템이 전제조건이고 따라서 RDBMS에 CAP를 적용하는 것은 맞지 않다. 굳이 적용하기 위해 CAP정리를 다음과 같은 명제식으로 바꾸어 본다고 하자.

p: 시스템이 분산시스템이다.
q: C,A,P 모두 만족 시킬 수 없다.
p->q

여기서 RDBMS의 경우 분산시스템이 아니므로 p는 거짓이이며, q의 참, 거짓 여부와 상관없이 명제 전체가 수학적으로 참이 되므로 이 명제가 맞다고 주장할 수 있다. 하지만 이것은 석궁사건으로도 유명한 1995년 성균관대학교 본고사 문제에서 성균관 대학교가 주장한 사기 풀이법과 같은 논리이다. 따라서 RBMS에 CAP를 적용하려는 시도는 맞지 않다. CAP를 적용하려는 시스템이 분산시스템이 아니라면 CAP자체가 동작하지 않는 것이다. 석궁 사건과 같은 봉변을 당하고 싶지 않다면 CAP를 제대로 이해하자.

결론

애초에 CAP Theorem이 의도했던바는 명확하다. 절대로 장애가 없는 네트워크는 존재하지 않으며, 따라서 분산시스템에서 P는 무조건 인정하고 들어가야 한다는 것이다. 따라서 네트워크가 단절되었을 때 시스템이 어떻게 동작할지 결정해야 하며, 이 때 C와 A를 모두 만족시키는건 불가능하므로 둘 중에 하나를 골라야 한다. 하지만 어려가지 문제로 CAP는 분산시스템에 대한 명확한 표현이 힘들다. PACELC를 이용하면 문제를 명확하게 이해할 수 있으며 시스템에 대해서도 깔끔하게 표현할 수 있다. 좀 더 자세한 내용에 대해 알고 싶다면 다음 글들을 참고하면 된다.