CAP 정리와 한계 PACELC 정리

이번 포스팅에서는 Brewer (브루어)의 CAP정리에 대해서 알아보도록 하겠습니다. CAP정리가 20년도 더 된 정리이기 때문에 그걸 보완한 PACELC 정리에 대해서도 알아보겠습니다. 

 

CAP에 대해서 구글링을 해보면 많은 분들이 CAP이론이라고 하시는데 이론과 정리는 엄연히 다릅니다. 이론은 증명되지 않은 생각? 주장? 에 가깝고 (e.g 일반 상대성 이론) 정리는 증명이 완료된 이론을 정리라고 합니다 (페르마의 마지막 정리). 정확히 말하면 CAP는 이론이었다가 증명이 완료된 후 정리가 된것입니다. 정식 영문 명칭도 theory가 아닌 theorem으로 되어있습니다. 

 

p.s 저도 CAP이론이라고 말하는게 더 멋있어서 이론이라고 부르고 싶은데... 이론이 아닌걸 이론이라고 부르면 아무래도 잘못된 정보를 전달하는 것이 되니 참 안타깝습니다...

 

서론이 좀 길었네요 이제 CAP 정리와 PACELC 정리에 대해서 알아보도록 하겠습니다. 

 

 

CAP 정리

CAP정리는 Brewer의 정리라고도 불립니다. CAP정리는 분산시스템에서 Consistency, Availability, Partition tolerance 이 세가지 속성 중 세가지를 모두 만족하는 시스템은 없다라는 정리입니다. 최대 2개만 만족할 수 있다는 것이죠. 

 

분산시스템이란 같은 시간대에 물리적 혹은 가상의 기기로 하나의 노드보다 더 많은 노드에 데이터를 저장하는 네트워크를 말합니다. 아래의 그림은 분산시스템을 설명하는 좋은 예시입니다. 

 

모든 분산시스템에서 클라우드 애플리케이션을 설계할 때 CAP정리를 아는 것은 필수입니다. 

 

우선 CAP에 대해서 알아보죠. CAP는 각각 Consistency, Availability, Partition Tolerance의 앞글자를 따서 만든 단어입니다. 각각에 대해서 설명해보겠습니다. 

 

Consistency

ACID의 C와 같은 단어를 쓰지만 느낌이 좀 다릅니다. ACID의 Consistency는 일관성 즉 트랜잭션 진행중 데이터베이스가 중간에 바뀌더라도 진행하고있던 데이터베이스로 일관성있게 진행해야 한다는 것입니다. 

 

CAP의 Consistency는 정합성입니다. 흔히 데이터 정합성을 말할 때 그 정합성이 맞습니다. Consistency는 모든 클라이언트가 같은 시간에 같은 데이터를 본다는 의미입니다.

 

데이터가 하나의 노드에 쓰여지면, 쓰기 작업이 성공하기 전에 모든 시스템안에 모든 다른 노드에 즉각적으로 복제되어야합니다. 

 

 

Availability

Availability를 파파고에 돌려보면 유용성, 유효성이라고 나오는데 사실 한글인데 무슨 뜻인지 잘 안와닿습니다. 그래서 저는 Availability를 가용성 혹은 사용가능성이라고 해석합니다. 

 

Availability는 어떤 클라이언트가 요청을 할 때 하나 혹은 더 많은 노드가 죽어버려도 응답을 할 수 있어야 한다는 의미입니다. 분산환경에서 모든 노드들은 요청에 대해 적절한 응답을 보여줘야 한다는 것입니다. 

 

요청, 응답 이런 단어들이 헷갈리니 예시를 들자면 요청 = 쿼리, 응답 = 데이터 라고 생각하셔도 무방합니다. 

 

 

Partition tolerance

Partition tolerance는 직역하면 분할 용인입니다. 정말 영어는 이래서 어려운 것 같습니다. 개발자들은 이 Partition이라는 단어를 장애 또는 오류 라고 해석하더라고요... 그렇게 해석하면 장애 용인 혹은 장애 허용 정도로 해석할 수 있는데 이래도 잘 이해가 안되시죠

 

Partition tolerance는 쉽게 풀어서 설명하면 금방 이해할 수 있습니다. Partition tolerance는 장애가 생기는 환경을 가정한 시스템 partition을 의미합니다. 

 

CAP정리에 대한 IBM의 공식문서에서 Partition tolerance를 이렇게 설명하고 있습니다. Partition은 분산 시스템에서 연결 오류(장애)입니다. 즉, 두개의 노드 사이에 연결이 끊어지거나 일시적인 연결 지연을 의미하죠. Partition tolerance는 클러스터가 시스템안의 노드 사이에 수많은 연결 오류(장애)에도 불구하고 계속해서 동작해야한다는 것입니다. 

 

Partition을 장애로 해석해야한다니 참 답답합니다. 이걸 진짜 나눈 것 이라는 파티션이라고 해석해야 하는지 장애라고 해석해야 하는지 해석하다보면 답답해질 때가 있습니다.

 

놀랍게도 사실입니다.

 

CAP에서는 세개를 모두 만족하는 시스템이 없다는 정리라고 말씀드렸죠? 그럼 CAP는 총 세개의 타입이 나옵니다. 바로 CP, AP, CA이렇게 세가지입니다. 각각의 타입에 대해서도 한번 알아보죠

 

 

CAP 정리에서 NoSQL의 타입

이 섹션에 들어가기 전에 그림을 가지고 설명할텐데 그 그림을 위한 사전 지식이 있어야합니다. 

 

이렇게 여섯가지를 알고 계시면 됩니다. 네번째인 Network Partition은 앞서 설명했듯이 네트워크 장애라고 보시면 됩니다.

 

CP database

CP는 Consistency와 Partition tolerance 이렇게 두가지 속성을 가진 데이터베이스입니다. 그렇다는 얘기는 Availability는 만족하지 않다는 얘기이죠. 

 

CP인 경우 시스템의 노드들이 나눠졌음에도 요청을 받는 것을 유지하기 때문에 파티션을 허용합니다. 이 데이터베이스 모델은 일관적입니다. 왜냐하면 오직 결과를 생성하는 노드들이 모든 쓰기 요청을 처리하는 마스터 노드와의  연결을 유지하기 때문입니다. 

 

Availability는 왜 만족하지 못할까요? CP와 AP는 서로가 서로 물리고 물린다고 생각하시면 편합니다. CP는 정합성 때문에, AP는 가용성 때문에 맞은편에 있는 속성을 유지하기 힘들죠. 

 

CP의 경우 Consistency 즉 정합성을 유지해야 하는데 위의 상황에서 Availability를 만족하려면 각각의 노드가 요청과 응답을 해야하는데 그럼 각각의 노드에 쓰기 작업이 가능해진다는 의미입니다. 그럼 A노드 B노드에 모두 쓰기가 가능해지면 둘의 데이터가 달라지는건 피할 수 없겠죠?

 

위의 그림을 설명하자면 맨 처음 마스터 노드와 일반적인 노드가 있는 상황에서는 쿼리가 들어오면 정상적으로 응답이 나가죠. 하지만 장애상황이 되면 마스터 노드가 죽어버리면서 쿼리만 들어오고 정상적으로 응답을 하지 못하는 모습을 보여줍니다. 

 

 

AP database

AP는 Availability와 Partition tolerance를 만족하는 데이터베이스 모델입니다. 

 

각각의 노드들이 어떻게 Availability를 가질 수 있을까요? 이 데이터베이스 모델의 경우 마스터 노드에 도달할지 안할지와 관계없이 요청을 응답하는 slave를 가지기 때문에, 그리고 다른 파티션에 있는 slave node가 새로운 마스터 노드를 선출하기 때문에, 그리고 우리는 마스터노드가 없는 클러스터를 가지고 있기 때문에 Availability를 만족합니다. 

 

위의 그림을 1, 2, 3 이렇게 세부분으로 나눠서 보겠습니다.

 

첫번째는 마스터 노드에 도달할지 안할지와 관계없이 응답하는 slave 노드를 가지기 때문에 마스터노드가 죽어버렸음에도 요청에의한 응답이 가능합니다.

 

두번째는 장애 상황에서 마스터노드가 죽어버리고 다른 파티션에 있는 slave 노드가 새로운 마스터 노드를 선출한 경우입니다. 

 

세번째는 마스터 노드가 없는 상황인데, 실제로 NoSQL 데이터베이스 중 Cassandra였나..? 자세히 기억이 안나는데 마스터 노드가 존재하지 않는 데이터베이스가 있습니다. RDBMS라면 상상도 못할 일이지만 NoSQL에서는 가능한가봅니다. 

 

아무튼 세번째 상황에서도 당연히 가용성을 보장하기 때문에 가능합니다. 

 

그럼 Consistency는 어째서 만족할 수 없을까요? 앞서 설명드렸다시피 Availability를 만족해야 하기 때문에 Consistency를 만족할 수 없습니다. 

 

이건 앞선 이유와 같은 이유가 되겠네요. 각각의 노드가 쓰기 작업이 가능해야 할텐데 쓰기작업을 진행하는 순간 정합성이 깨져버리겠죠? 

 

 

CA database

이제 마지막으로 CA인데 이건 할 얘기가 좀 많습니다. 

 

CAP 정리에서 정의를 살펴보면 마치 C, A, P 각각이 동등한 선상에 있는 것처럼 느껴집니다. 이러한 연유로 C, A, P가 분산 시스템의 특정에 대한 것으로 여겨지지만 실상은 그렇지 않습니다. 

 

왜냐하면 앞서 설명했듯이 P는 Partition tolerance, 장애를 허용하는 파티션을 만드는 작업인데 이 P를 허용하지 않는 순간
"우리 시스템은 죽었다 깨어나도 장애가 발생하지 않습니다" 라고 선언하는 것과 다르지 않습니다. 

 

따라서 P를 만족하지않는 데이터베이스는 이 세상에 있을 수 없습니다. 

 

그래서 마치 P를 포기하고 CA를 선택해도 되는 것처럼 느껴집니다. 하지만 앞서 말했듯이 그런 시스템은 존재하지 않고 그럼 C나 A 중에서 선택해야 한다는 의미입니다. 

 

그렇다고 C나 A를 마냥 둘 중 선택하듯이 선택해도 되냐? 의 문제도 또 있습니다. 이 C나 A도 동일선상에 있지 않습니다. AP를 선택한 Cassandra의 경우 네트워크 장애 상황이던 정상 상황이던 C를 포기하도록 되어있습니다. HBase의 경우 장애상황일 때만 A를 포기하고 정상일때는 A를 만족합니다. 

 

즉, CAP 정리는 장애 상황일때만 대칭성이 있고 정상일 때는 그렇지 않습니다. 그러므로 CAP정리의 내포된 의미는 분산시스템에서 네트워크 장애 상황일 때 정합성과 가용성 중 많아도 하나만 선택할 수 있다는 것입니다. 

 

하지만 이런 식의 해석은 정상 상황일 때의 분산시스템 동작을 서술해주지 못합니다. 이에 대해 PACELC라는 기가막힌 표현에 대해서 알아봅시다. 

 

 

PACELC

앞서 설명했듯이 CAP는 장애상황과 정상상황을 모두 설명할 수 없습니다. PACELC의 핵심은 장애상황과 정상상황을 모두 설명할 수 있다는 점에서 CAP의 업그레이드 버전이라고 볼 수 있습니다. 

 

Partition은 제가 설명드렸듯이 "장애" 혹은 "오류" 라고 해석하시면 됩니다. 

 

위의 그림에서 알 수 있듯이 장애상황에서는 A와 C를 선택하고 그밖에 상황(정상 상황)에서는 L과 C를 선택한다는 것입니다. L은 Latency이고 C는 앞선 Consistency입니다. 

 

이 개념을 NoSQL에 적용해보면 다음과 같습니다. 

 

• HBase는 PC/EC입니다. 장애 상황일 때 C를 위해서 A를 희생합니다. 그렇지 않은 경우에는 C를 위해 L을 희생합니다. 
• Cassandra는 PA/EL이 가능하도록 설계되었습니다. 설정에 따라 Eventual Consistency의 특성을 가지게 되었는데, 이 경우 PA/EL이 됩니다. 장애 상황인 경우에는 가능한 노드에만 데이터를 반영하고 정상으로 복구되면 필요한 노드에 데이터를 모두 반영합니다. 정상 상황일때도 Latency를 위해 모든 노드에 데이터를 반영하지 않습니다. 
• Brewer가 정의한 가상의 분산시스템은 PA/EC입니다. 정상적인 경우에는 모든 노드에서 같은 메시지를 볼 수 있도록 쓰기 연산이 일어나는데 P 상황인 경우 이를 판단하여 일단 접근 가능한 만큼만 데이터를 반영합니다. 결과적ㅇ느로 시스템은 다운되지 않지만 절단된 노드들끼리는 데이터를 주고 받지 못하게 됩니다. 장애상황이 복구되면 이를 감지하여 전달하지 못한 데이터를 반영합니다. 장애 상황일때만 C를 포기하고 보통의 상황에서는 강력한 C를 가져가는 것입니다. 

 

참고)

RDBMS에도 CAP을 적용하여 CA로 분류하기도 합니다. Brewer가 처음 발표할 때에도 이렇게 표현하기도 했고, 하나의 인스턴스로 운영되는 RDBMS의 특징상 네트워크로 연결되어 있기 않으므로 네트워크 단절을 재제할 수 있다는 점에서 이렇게 분류하는게 어느정도 납득은 됩니다. 

 

하지만 CAP는 분산시스템이 전제이고 따라서 RDBMS에 CAP를 적용하는 것은 맞지 않습니다. 

 

라고 써있는 글을 참조하긴 했지만...

http://eincs.com/2013/07/misleading-and-truth-of-cap-theorem/

CAP Theorem, 오해와 진실

 

이 말은 RDBMS는 분산시스템이 아니라는 의미가 됩니다. RDBMS가 분산시스템이 왜 아닌지에 대해서 찾아봤습니다. 

 

 

위의 그림은 RDBMS의 경우를 나타낸 그림입니다. 일반적인 마스터-슬레이브 관계인 경우 마스터 노드가 죽어버리면 남아있던 슬레이브 노드가 마스터가 되면서 다시 정상적인 운영을 합니다. 

 

클러스터링을 구현한다면 active 노드 개수가 적으면 전체 클러스터가 종료될 수 있습니다. 하지만 이러한 상황은 클러스터링에서 언제든지 발생할 수 있습니다. 클러스터링이 가진 단점 중 하나이죠. 

 

이러한 단점을 해결하기 위한 아키텍처가 바로 레플리케이션입니다. 클러스터링과 레플리케이션 그리고 나오진 않았지만 샤딩에 대해서 자세히 알고싶으신 분은 아래의 링크를 참고해주세요!

 

https://coding-review.tistory.com/309

데이터베이스 튜닝 방법 (Clustering, Replication, Sharding)

 

위의 구조를 가지고 있기 때문에 RDBMS는 분산시스템을 사용할 일이 없죠. 애초에 분산시스템이 필요한 도메인에서 RDBMS를 사용하지 않습니다. 

 

 

자 여기까지 CAP정리 그리고 그 업그레이드 버전인 PACELC에 대해서 알아봤습니다. 이번건 정말 어려웠습니다. 특히 CP와 AP를 보면서 왜 CP가 A를 만족하지 않지? 왜 AP가 C를 만족하지 않지? 에 대해서 정말 머리굴려가며 열심히 공부했던 것 같습니다.

 

NoSQL을 공부하다보니 별에별거까지 다 공부하고 있네요. CAP정리에 대해서는 면접에 충분히 나올 수 있는 내용입니다. PACELC까지 깊은 내용은 아니더라도 CAP정리에 대한 기본적인 내용은 충분히 나올만한 질문이라고 생각합니다. 잘 정리하셔서 면접에서 꼭 활용하시길 바라겠습니다. 

 

여기까지 글 마쳐보도록 하겠습니다. 긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 되세요~~

 

 

출처

https://www.ibm.com/topics/cap-theorem

What is the CAP Theorem? | IBM

=>  CAP 정리에 대한 IBM 공식문서

 

https://www.geeksforgeeks.org/what-is-a-distributed-system/

What is a Distributed System? - GeeksforGeeks

=> 분산시스템에 대한 정의

 

https://stackoverflow.com/questions/36404765/why-isnt-rdbms-partition-tolerant-in-cap-theorem-and-why-is-it-available

Why isn't RDBMS Partition Tolerant in CAP Theorem and why is it Available?

=> 스택 오버플로우 질문

 

http://eincs.com/2013/07/misleading-and-truth-of-cap-theorem/

CAP Theorem, 오해와 진실

=> CAP 정리의 오해와 진실 : 이재성님

 

http://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf

=> CAP 정리 증명논문

논문 제목 : Perspectives on the CAP theorem

논문 저자 : Seth Gilbert, Nancy A. Lynch

수여 기관 : National University of Singapore, Massachusetts Institute of Technology