cap theorem

지난 2012년 2월, IEEE Computer에 CAP Theorem에 대한 특집이 실렸습니다. 특집의 첫번째 아티클을 쓴 저자는 지난 2000년 PODC (Symposium on Principles of Distributed Computing)에서 CAP Theorem을 conjecture의 형태로 발표했던 바로 Eric Brewer입니다.

CAP Twelve Years Later: How the “Rules” Have Changed by Eric Brewer

1. CAP Theorem

소위 NoSQL 운동에 대해서 조금이나마 관심이 있었던 분들은 CAP Theorem에 대해 들은 바가 있을 것입니다.

CAP Theorem은 네트워크를 통해 데이터를 공유하는 시스템은 아래의 3가지 특성 중 2개만을 가질 수 있다고 얘기하고 있습니다.

• Consistency (C)
• High Availability (A)
• Tolerance to Network Partitions (P)

네트워크로 연결된 2개의 노드로 구성된 시스템이 있다고 가정해봅시다. 그리고 네트워크 파티션에 의해 2개의 노드는 통신할 수 없는 상황이 벌어졌다고 생각해봅시다.

Availability를 위해 하나 이상의 노드가 상태를 업데이트할 수 있도록 한다면 2개의 노드가 가지고 있는 데이터는 inconsistent해지므로 Consistency를 포기하는 것이 됩니다. Consistency를 보존하려고 한다면, 2개의 노드 중 한 쪽은 unavailable한 것처럼 행동해야 하므로, Availability를 포기하는 것이 됩니다. 노드들이 서로 통신할 때만, Consistency와 Availability를 동시에 보존할 수 있으므로 이는 Partition Tolerance를 포기하는 것이 됩니다.

2. Why 2 of 3 is misleading

“Partition Tolerence를 포기할 수 없으므로, Consistency와 Availability 중 하나를 선택해야 하고, Availability를 희생할 수 없으므로, Consistency를 희생해야한다” 정도가 NoSQL 운동의 초기에 등장했던 AP 시스템들의 공통된 주장이었습니다.

그러나, Eric Brewer는 이런 식으로 3개의 특성 중 2개만을 선택해야 한다는 관점이 많은 오해를 불러왔다고 얘기하고 있습니다.

그 이유는 다음과 같이 설명하고 있습니다.

• 파티션은 흔히 일어나지 않으므로, 파티션이 일어난 상황이 아닐 때에도 Consistency나 Availability를 포기할 타당성은 적다.
• Consistency-Availability 사이의 선택은 하나의 시스템에서 단 한번 이루어지는 것이 아니라, 세부적인 단위로에서 여러번 일어날 수 있다.
• 3개의 특성들은 연속적이다. Availability는 0% – 100%, 여러 레벨의 Consistency, Partition에 대한 시스템 내의 Disagreement 등이 이를 나타낸다.

3. Cap-Latency connection

또한 Eric Brewer는, 전통적인 관점에서 네트워크의 파티션은 커뮤니케이션의 단절을 의미하는 것이지만, 제한된 시간 내에 커뮤니케이션을 하지 못하는 것을 네트워크 파티션으로 보는 관점을 제시하고 있습니다. 즉, 어떤 오퍼레이션의 타임아웃이 발생한 시점에 시스템이 해당 오퍼레이션의 재시도를 시도한다면 Consistency를 선택하는 것이고, 그렇지 않는다면 Availability를 위해서 파티션을 허용하는 것입니다.

이러한 관점에서 시스템의 설계자가 목표로 하는 response time에 따라 타임아웃을 설정하면, 타임아웃이 발생하는 것을 파티션으로 감지하고, 파티션 모드로 진입할 수 있게 됩니다.

한편, 지연 (Latency)을 피하기 위해 강한 Consistency를 포기하는 시스템의 예로 Yahoo의 PNUTS를 들고 있고, 업데이트와 업데이트 이후 일정 시간동안의 읽기에 대해서는 지연을 허용하는 Facebook의 시스템을 그 반대의 사례로 들고 있습니다.

4. Managing partitions

Eric Brewer는 파티션을 다루는 전략을 다음과 같이 제안하고 있습니다.

우선 파티션은 흔하지 않기 때문에, CAP은 대부분의 시간 동안 완벽한 C와 A를 허용해야합니다. 하지만, 파티션이 발생했을 경우에는, 파티션을 매우 명시적으로 관리해야한다고 언급하고 있습니다. 이를 아래의 3단계와 그림으로 표현하고 있습니다.

1. 파티션의 시작을 감지
2. 특정 오퍼레이션을 제한할 수 있는 명시적인 파티션 모드에 진입
3. 커뮤니케이션이 회복된 후, Consistency를 복구하고 파티션 모드 동안의 실수를 만회하기 위한 파티션 복구 프로세스를 시작

4.1. Which operations should proceed?

기본적으로 어떤 오퍼레이션을 제한할지는 시스템이 유지해야하는 불변조건 (invariants)에 달려있습니다. 파티션 동안 유지되지 않아도 되고, 파티션 복구 시 쉽게 복구할 수 있는 경우 (예를 들어, 중복된 키들의 병합)에는 오퍼레이션을 허용할 수 있고, 파티션 동안 유지되어야만 하는 불변조건에 해당하는 경우에는 오퍼레이션을 금지하거나 지연하거나 수정해야 한다고 얘기하고 있습니다.

실제로 오퍼레이션에 대해 어떤 조치를 취할지는 시스템에 대한 모든 원자적인 (atomic) 오퍼레이션과 불변조건들의 테이블을 만들고 각각의 항목별로 오퍼레이션이 불변조건을 위반할 수 있는지 여부를 검토해야 합니다.

중요한 것은 실제로 시스템을 사용하는 사용자에게는 이러한 조치가 보이지 않는 것입니다. 신용카드 결제의 경우 통신이 불가능한 상황에서 의도를 기록한 후 나중에 실행하는 것이나, Bayou의 캘린더 애플리케이션에서 잠재적으로 inconsistent한 항목들을 다른 색상으로 표시하는 등 흔히 오프라인 모드라고 불리는 사용자 인터페이스에서의 처리를 언급하고 있습니다. 본질적으로 이러한 오프라인 모드는 장시간 동안의 파티션과 다름없다는 것입니다.

파티션이 끝난 후 복구를 위해 파티션의 양단에서 일어난 오퍼레이션의 이력을 추적하는 가장 좋은 방법으로 오퍼레이션들 사이의 인과적인 의존성을 보존하는 버전 벡터 (version vector)를 사용하는 것이라고 얘기하고 있고, 이러한 시스템의 좋은 예로 Dynamo를 들고 있습니다.

4.2. Partition recovery

파티션 복구 동안, 파티션 양단의 상태를 일관되게 (consistent) 만들고, 잘못된 응답이나 시스템 외부로의 영향 등 파티션 모드 동안에 이루어진 실수를 만회하는 두가지 문제를 해결해야 합니다.

우선 일관성의 문제는 파티션 상태로부터 시작해서 양단의 오퍼레이션들을 재실행 (roll-forward) 하면서 계속 일관된 상태를 유지하는 방식을 가장 쉬운 방식으로 언급하고 있습니다.

한편, 양단의 오퍼레이션을 병합할 때 발생하는 충돌에 대해서는, 일반적인 충돌 해결의 문제는 해결 불가능하지만, 현실적으로는 설계자는 파티션 동안의 오퍼레이션 제한을 통해 복구 동안의 자동 병합에서 문제가 생기지 않도록 합니다. (예를 들어, Google Docs는 텍스트의 추가, 삭제, 스타일의 적용으로 오퍼레이션을 제한)

상태의 자동적인 수렴을 위한 일반적인 프레임워크 중 하나는 상호적인 (commutative) 오퍼레이션입니다. 하지만, 실제로는 상호적인 오퍼레이션만 사용하는 것은 매우 어렵기 때문에, CRDT (Commutative Replicated Data Type)이란 개념을 소개하고 있습니다. CRDT는

• 파티션 동안 모든 오퍼레이션들은 상호적임을 보장하거나,
• 상태를 기록한 후, 파티션 동안에 일어나는 모든 오퍼레이션은 그 상태에 대해 단조적임을 보장합니다.

예를 들어, 집합에 대한 추가와 삭제 오퍼레이션에 대한 CRDT 구현은, 추가된 항목들과 삭제된 항목들에 대한 집합을 각각 유지하는 것입니다. 파티션 복구 시점에서 시스템은 양단의 집합으로부터 정리 작업을 수행할 수 있습니다. 정리 작업은 파티션 동안에는 불가능하기 때문에 파티션 이후로 지연시켜야 하는 오퍼레이션이지만, 인지되는 가용성을 제약하지 않습니다. 따라서, CRDT를 통해 상태를 구현할 수 있다면, 설계자는 Availability를 선택하더라도 파티션 이후에 자동적으로 상태가 수렴될 수 있도록 보장할 수 있습니다.

4.3. Compensating for mistakes

시스템 외부에 가해진 실수를 복구하는 것은 시스템 외부로의 영향에 대한 이력을 필요로 합니다. 어떤 사람이 전날 밤 술에 취해 전화를 걸었다면, 그 전화들은 외부로의 영향에 해당하고, 그 사람이 다음 날 아침 정상 상태가 되었을 때, 잘못 건 전화들에 대해 만회를 하기 위해서는 어젯밤 걸었던 전화들에 대한 기록을 필요로 합니다.

다른 예로, 파티션 동안에 시스템이 동일한 주문을 두 번 수행했다고 가정해봅시다. 시스템이 주문의 이력으로부터 중복된 주문을 식별할 수 있다면, 중복된 주문 중 하나를 취소하고 고객에게 적절하게 사과하는 메일을 보낼 수 있지만, 그러한 이력이 없다면, 그러한 실수를 파악하는 것은 고객의 부담이 됩니다.

Brewer는 여기서 보상 트랜잭션 (Compensating Transaction)의 개념을 소개하고 있습니다. 예를 들어, 하나의 트랜잭션으로 모든 직원들의 레코드들을 업데이트 하려고 한다면 모든 레코드를 lock하게 됩니다. 보상 트랜잭션은 커다란 트랜잭션을 다수의 작은 트랜잭션으로 쪼개어 각각 따로 commit하는 방식을 취합니다. 따라서, 원래의 커다란 트랜잭션을 취소하려고 할 때 이미 commit된 작은 트랜잭션의 영향을 수정하는 새로운 트랜잭션 -보상 트랜잭션을 실시합니다. 보상 트랜잭션의 접근은 전통적인 데이터베이스의 접근과 같이 직렬성 (Serializability)이나 격리성 (Isolation)에 의존하기 보다는 트랜잭션의 전체적인 영향에 의존합니다. 그리고 외부에 미친 영향까지도 고려가 되어야 합니다. 예를 들어, 중복된 지불을 환불하는 것은 애초에 고객에게 청구하지 않는 것과 같다고는 할 수 없지만, 거의 동등하다는 것이고, 이러한 생각 – 실수를 인정하고 보상을 통해 동등한 결과를 얻는 방식이 파티션 복구에서도 성립한다고 얘기하고 있습니다.

5. Closing

Eric Brewer가 마지막에서 강조하고 있는 것은 시스템 설계자는 파티션이 존재할 때, 무턱대고 consistency나 availability를 희생하려고 해서는 안되고, 이 글에서 언급하고 있는 방식을 통해 양쪽 모두를 최적화하려고 해야한다는 것입니다. 이를 위한 버전 벡터 (version vector)나 CRDT 등의 기술들이 프레임워크화되고 좀 더 보편화될 것이라고 얘기하고 있습니다.

제가 이 글을 읽고 느낀 점들은 아래와 같습니다.

• CAP Theorem에 대해서 이 글을 읽기 전까지만 해도 단순화된 관점 – 2 of 3을 가지고 있었으나, 이 글을 읽고나서 CAP Theorem에 대한 이해도가 좀 더 높아졌고, 단순한 AP 또는 CP 시스템 이외의 시스템 설계의 많은 가능성에 대해서 생각해보게 되었습니다.
• 상태의 수렴을 위한 데이터와 오퍼레이션의 재설계가 필요하다는 것은 깨닫고 있었지만, CRDT와 같은 좋은 사고 도구가 될 수 있는 정식화 (formalization)가 있는지는 몰랐습니다.
• 결국 현재로서는 분산 저장 시스템은 매우 복잡한 설계가 필요할 뿐만 아니라, 전통적인 DB와는 다르게 보편화된 프레임워크가 있기 보다는 개별 시스템 별로 따로 설계를 해야하는 수준이기 때문에, 아직 더 많은 연구와 개발이 필요한 분야인 반면, 그만큼 비용이 많이 들어가는 부문인 것 같습니다.
• CAP Theorem 특집의 글들을 읽고 있습니다만, 이를 요약할 수 있을 정도로 완벽하게 이해하고 정리하는 것은 매우 시간이 걸리는 일이네요. 여력이 된다면 다섯개의 글 모두 정리해보고 싶습니다.