CAP 정리와 PACELC 정리
CAP 정리란?
CAP 정리(브루어의 정리)는 아래 세 가지 조건을 모두 만족하는 분산 컴퓨터 시스템이 존재하지 않음을 증명한 정리이다.
- 일관성 (Consistency)
- 가용성 (Availability)
- 분할 내성 (Partition tolerance)
각 조건의 상세한 내용은 다음과 같다.
일관성 (Consistency)
- 모든 노드가 같은 순간에 같은 데이터를 볼 수 있어야 한다.
가용성 (Availability)
- 하나 이상의 노드가 작동 중지된 경우에도 데이터를 요청하는 클라이언트가 응답을 받을 수 있어야 한다.
분할 내성 (Partition tolerance)
- 메시지 전달이 실패하는 시스템 일부가 망가져도 시스템이 계속 동작해야한다.
- 노드 간의 통신 장애가 발생하더라도 동작해야한다.
= 두 개의 노드 중 하나의 노드로 쿼리를 했을 때, 다른 노드의 상태를 알지 못하더라도 해당 노드 자체만으로 동작
가용성과 분할 내성이 결국 같은 이야기를 하는 것이 아닌지 의문이 들 수 있다.
이 둘을 비교하자면 가용성은 특정 노드에 장애가 발생한 상황에 대한 것이고, 분할 내성은 노드의 상태는 정상이나 네트워크 등의 문제로 서로간의 통신이 불가능한 상황에 대한 것이다. 이해를 돕기 위해 아래와 같은 예시를 들었다.
먼저, 위 그림은 여러 개의 노드를 통해 데이터를 제공하고 있는 모델이다.
이 모델에서는 Client A가 Node 1에 데이터를 업데이트하면, 즉시 Node 2, 3에도 데이터가 업데이트되어 Client B에서도 같은 데이터를 볼 수 있게끔해준다.(일관성)
이 때, Node 1이 장애로 인해 DOWN 될 경우 Node 2, 3을 통해 Client A, B에게 데이터를 응답해줄 수 있다.(가용성)
그런데 이번에는 노드에 장애가 발생한 것이 아니라 노드 간의 네트워크에 문제가 있다고 가정해보자. 이 경우에는 모든 노드가 동작하고 있으나 노드간 통신이 원활하지 않아 Node 1에 업데이트한 데이터를 Node 3에도 반영할 수 없게 되었다.
이 상황에서 Client A → Node 1, Client B → Node 3 방향의 쿼리는 일관성은 유지되지 않더라도 데이터를 응답해줄 것이다.(분할 내성)
이 때, 일관성 유지를 위해 네트워크가 복귀될때까지 기다리게 된다면 가용성을 보장 다고 할 수 없게된다.
CA, CP, AP 시스템
CP (Consistency + Partition tolerance)
- 분할(두 노드간의 통신 장애)이 발생할 때, 이를 해결하기 전까지 일관성을 유지하지 못하는 노드를 종료해야한다.
- MongoDB, Redis, Hbase, BigTable, MemcacheDB ...
AP (Availability + Partition tolerance)
- 분할이 발생할 때, 모든 노드는 가용 상태를 유지하나 파티션의 마지막 노드에서는 다른 노드보다 이전 버전의 데이터를 반환할 수도 있다.
- 분할이 해결되면 보통 동기화를 통해 노드간의 데이터 불일치를 해결한다.
- Dynamo, Cassandra, CouchDB ...
CA (Consistency + Availability)
- 모든 노드에서 일관성과 가용성을 제공
- RDBMS(MySQL, Postgres ...), ElasticSearch
MySQL은 CA일까?
앞서 RDBMS는 일관성과 가용성을 보장하는 CA 시스템이라고 분류했었다. 대부분의 RDBMS가 트랜잭션 ACID를 통해 일관성을 보장하고, 많은 경우 Active-Active 혹은 Active-Stanby 구조로 HA를 제공하기 때문이다.
그런데 MySQL은 Cluster를 지원한다.
MySQL InnoDB Cluster는 3개 이상의 MySQL 서버 인스턴스로 구성되어, 모든 인스턴스가 Primary인 multi-primary 방식과 하나의 Primary와 여러 개의 Secondary 인스턴스를 두는 single-primary 방식으로 구성할 수 있다.
이렇게 설정을 통해 MySQL InnoDB Cluster를 구성할 경우, MySQL은 CA 시스템이라고 보기 어려우며, CP 시스템이라고 볼 수 있다.
그 이유는 노드 간 분할이 발생했을 때, 나머지 노드들은 다음과 같이 동작하기 때문이다.
- 저장된 모든 데이터를 처리할 수 있는 활성 노드가 충분하지 않은 경우 - 종료
- 저장된 모든 데이터를 처리할 수 없을 정도의 장애나 도달할 수 없는 노드가 없는 경우 계속 서비스를 제공
- 저장된 모든 데이터를 처리할 수 없을 정도의 장애나 도달할 수 없는 노드가 있는 경우 중재
다른 노드의 하위 집합이 사용 가능한 클러스터로 다시 그룹화될 수 있음
CAP 정리의 문제점
CAP 정리에는 각 요건에 대한 정리가 명확하지 않아 이해하기 쉽지 않고 모호하다는 문제가 있다. 그 중에서도 Partition tolerance의 정의가 가장 모호하다. 앞서 정리한 내용을 읽고 Partition tolerance를 이해하는 사람은 얼마나 될까? 이 포스트가 아니고 Brewer가 발표한 내용을 보더라도 그가 정의한 바를 이해하는 사람이 얼마나 될지는 미지수다.
관련해서 2013년도에 작성된 포스팅을 찾았는데, 내용이 너무 좋아 첨부한다.
CAP Theorem, 오해와 진실
CAP Theorem은 분산시스템에서 일관성(Consistency), 가용성(Availability), 분할 용인(Partition tolerance)이라는 세 가지 조건을 모두 만족할 수 없다는 정리로, 세 가지 중 두 가지를 택하라는 것으로 많이 알
eincs.com
주요 내용을 요약하자면,
- Consistency와 Availability는 분산 시스템의 특성이지만, Partition tolerance는 분산 시스템이 돌아가는 네트워크에 대한 특성이다.
- CAP 정리에서 조건을 3개로 두어 Partition tolerance를 포기하고 CA를 선택할 수 있게끔 느끼게하나, P를 포기하면 절대로 장애가 나지 않는 네트워크를 구성해야 함을 의미하며, 절대 존재할 수 없다.
- C와 A가 비대칭적인데, HBase의 경우 장애 상황일 때만 A를 포기하고 정상일 때는 A를 만족한다. 그러므로 CAP 정리는 네트워크가 장애 상황일 경우에만 대칭성이 있고 그렇지 않을 때는 비대칭적이다.
PACELC 정리
CAP 정리의 문제점을 보완하기 위해 PACELC 정리가 나왔다.
PACELC 정리는 CAP 정리의 Consistency, Availability를 한 축으로 두고, 정상 상황이냐 장애 상황이냐를 한 축으로 두어 설명한다.
Partition(장애 상황)일 때는 Availability와 Consistency 중 하나를 선택해야하며, 정상 상황일 때는 Latency와 Consistency 중 하나를 선택해야한다.
다시 말해, Partition이 발생해 몇 개의 노드와 통신이 불가능할 때, 일관성 유지(C)를 위해 데이터 반영을 포기하던지 가용성(A)을 위해 통신 가능한 노드에만 데이터를 반영하던지 선택해야한다. 정상 상황일 경우에는 낮은 지연 시간(L)을 위해 일부 노드에만 데이터를 반영하던지, 일관성 유지(C)를 위해 모든 노드에 데이터를 반영하고 상대적으로 긴 응답시간을 가져갈지 선택해야한다.
DDBS (Distributed DataBase System)별 분류는 아래와 같다.
| DDBS | P + A | P + C | E + L | E + C |
| Bigtable / HBase | O | O | ||
| Cassandra | O | O | ||
| Couchbase | O | O | O | |
| Dynamo | O | O | ||
| DynamoDB | O | O | O | |
| MongoDB | O | O | ||
| MySQL Cluster | O | O | ||
| PostgreSQL | O | O | ||
| VoltDB | O | O |
References
- 위키백과 - CAP 정리 (https://ko.wikipedia.org/wiki/CAP_%EC%A0%95%EB%A6%AC)
- IBM - CAP Theorem (https://www.ibm.com/topics/cap-theorem)
- MySQL - MySQL InnoDB Cluster (https://dev.mysql.com/doc/refman/8.0/en/mysql-innodb-cluster-introduction.html)
- The CAP theorem and MySQL Cluster (https://planet.mysql.com/entry/?id=32245)
- CAP Theorem, 오해와 진실 (http://eincs.com/2013/07/misleading-and-truth-of-cap-theorem/)
- 위키백과 - PACELC 정리 (https://en.wikipedia.org/wiki/PACELC_theorem)