cap theorem

Consistency Tradeoffs in Modern Distributed Database System Design

지난 번에 소개했던 IEEE Computer 2012년 2월호의 CAP Theorem 특집 중 세번째 글입니다. CAP Theorem 특집을 읽게된 계기도 바로 이 글의 저자인 Abadi의 블로그 글이었습니다.

Consistency Tradeoffs in Modern Distributed Database System Design by Daniel J. Abadi

Critique

현대의 DDBS에서 CAP의 consistency/availability tradeoff 보다 consistency/latency tradeoff가 중요한 설계상의 결정임을 주장하고 PACELC라는 모델을 제안하고 있습니다.

CAP 만으로 설명하기 어려웠던 설계 결정들에 대해 의문이 있었다면 PACELC가 완벽하지는 않지만 CAP에 비해서 더 좋은 모델임에 동의할 수 있을 것 같습니다. 주변 분들에게도 PACELC에 대해서 설명해주면 당연하게 받아들이는 눈치였습니다. 한편, 이 글은 매우 간결하면서도 문제로부터 결론을 도출하기 까지 논리의 흐름이 부드럽게 이어지기 때문에 이해가 잘 되고 그리 무겁지 않게 읽을 수 있습니다.

PACELC의 개념이 직관적으로는 이해하기 쉬운 반면, 현재 존재하는 시스템을 분류할 때 저자도 언급하고 있는 애매한 점들이 등장하는 것을 보면 엄밀한 도구라고 보기에는 약간 무리입니다. tradeoff 의 모든 측면을 모델로 표현하는 것은 매우 어렵기 때문에 베이스라인이라는 표현과 이로부터 상대적인 tradeoff의 유무를 기준으로 사용한 것 같습니다.

역시 완벽하지는 않겠지만 현대의 DDBS에서 활용하고 있는 설계 결정들을 모두 정리해서 스펙트럼 또는 이에 상응하는 모델로 정리할 수 있다면 앞으로의 DDBS 프레임워크의 발전에서 중요한 기초가 될 수 있지 않을까 생각합니다.

아래는 이 글의 요약입니다.

CAP is for Failure

CAP에서 consistency와 availability 사이의 tradeoff를 발생시키는 요소는 단지 partition tolerance 만이 아니라, partition tolerance와 network partition의 존재, 두 가지 요소의 조합이기 때문에, network partition이 존재하지 않을 때, CAP 자체는 consistency와 availability를 동시에 만족시키는 시스템을 허용하고 있다.

Consistency/Latency Tradeoff

network partition이 존재하지 않는다고 하더라도 consistency, availability, latency 사이의 tradeoff는 존재한다. 이러한 tradeoff가 존재하는 이유는 high availability 요구사항으로 인해 시스템은 데이터를 복제해야하기 때문이다.

Data Replication

시스템이 데이터를 복제하는 순간부터 consistency와 latency 사이의 tradeoff가 발생한다. 데이터 복제를 구현하는 데에는 아래와 같이 3개의 방법이 존재하지만, 각각은 모두 latency의 요소가 존재한다.

(1) 데이터의 업데이트를 동시에 모든 복제본으로 보내기

선처리 레이어(preprocessing protocol)를 통과하지 않거나 합의 프로토콜 (agreement protocol)이 없다면 오퍼레이션의 적용 순서의 차이로 인해 복제본들 사이의 차이가 발생한다. 선처리 레이어나 합의 프로토콜을 사용한다면 모든 복제본들이 합의된 순서대로 업데이트를 적용하는 것을 보장할 수 있지만, 선처리 레이어를 위한 추가적인 시스템 컴포넌트, 모든 복제본에 대한 업데이트, 합의 프로토콜 자체 등 latency가 발생하는 여러가지 원인들이 된다.

(2) 데이터의 업데이트를 합의된 마스터 노드에 먼저 보내기

마스터 노드는 모든 업데이트 요청을 처리하고 마스터 노드가 처리한 순서는 마스터 노드가 모든 리플리카에 복제하면서 다른 복제본들에도 그대로 적용된다.

마스터로부터 다른 복제본으로의 복제 방법은 아래와 같은 3가지가 존재한다.

a. 동기적인 복제: 복제본들로의 업데이트가 일어날 때까지 마스터 노드는 대기한다. 복제본들이 consistent하지만, 모든 복제본들의 업데이트로 인해 latency가 증가한다.

b. 비동기적인 복제: 복제본들이 업데이트 되었다는 보장이 없으므로, consistency/latency tradeoff는 시스템이 읽기를 어떻게 다루느냐에 달려있다.

i. 시스템이 모든 읽기를 마스터 노드에서 수행한다면 consistency의 감소가 없지만, 마스터 노드가 다른 복제본에 비해서 가까운 곳에 있지 않을 때, 또는 마스터 노드가 과부하 상태이거나 동작 불능 상태일 때는 latency가 발생한다.

ii. 어떤 노드에서도 읽기를 수행하도록 한다면 읽기의 latency는 좋아지지만, 동일한 데이터의 inconsistent한 읽기가 발생한다. update sequence number의 추적을 통해 sequential/timeline consistency 또는 read-your-writes consistency를 구현해 consistency의 감소를 줄일 수 있다.

c. 데이터의 업데이트를 복제본의 일부에 대해서는 동기적으로 복제하고, 나머지는 비동기적으로 복제한다. 이 경우에도 consistency/latency tradeoff는 시스템이 읽기를 다루는 방식에 달려있다.

i. 동기적으로 복제가 된 적어도 1개 이상의 노드로부터 읽기를 수행한다. (R + W > N)

ii. 동기적으로 업데이트 되지 않은 노드들에서 읽기를 수행하도록 허용한다. (R + W <= N)

(3) 데이터의 업데이트를 임의의 노드에 먼저 보내기

하나의 데이터 항목에 대한 두개의 업데이트가 서로 다른 노드로 보내질 수 있다. 동기적인 복제인가, 비동기적인 복제인가에 따라서 (1), (2)에서와 같은 latency 문제나 consistency 문제가 발생한다.

Tradeoff Examples

PNUTS의 경우, 마스터 노드로부터 비동기적으로 데이터를 복제하고, 아무 노드에서나 읽기를 수행하므로 (즉, 2-b-ii의 경우), latency를 위해 consistency를 tradeoff 하고 있다. 반면, CAP의 관점에서는 network partition이 발생했을 때, 소수 (minority) 파티션에 존재하는 마스터 노드는 사용 불가능하므로 consistency를 위해 availability를 trade-off하는 CP 시스템에 해당한다.

PNUTS는 일반적인 상황 (baseline case)에서 consistency를 희생하는 선택은 CAP에서의 consistency/availability tradeoff 라기보다는 consistency/latency tradeoff 때문이라고 할 수 있고, 일반적인 시스템에서 consistency를 희생하는 주된 이유가 CAP이 아니라는 증거를 보여주고 있다.

PACELC

DDBS에서의 consistency tradeoff는 CAP 대신 다음과 같은 PACELC로 좀 더 완전한 설명이 가능하다.

  • if there is a partition (P), how does the system trade off availability and consistency (A and C);
  • else (E), how does the system trade off latency and consistency (L and C)?

예를 들어, partition이 발생했을 때 availability를 위해 consistency를 포기하고, 보통의 상황에서는 낮은 latency를 위해 consistency를 포기하는 Dynamo, Cassandra, Riak과 같은 시스템들은 PA/EL 시스템이다. VoltDB/H-Store, Megastore와 같은 ACID 시스템들, BigTable과 이에 관련된 시스템들 (e.g. HBase) 은 PC/EC 시스템이다. MongoDB는 partition이 발생했을 때 master에서 복제되지 않은 데이터가 있더라도 새로운 master를 선출해서 서비스를 하기 때문에 PA/EC 시스템이다. PNUTS는 위에서 설명한대로 PC/EL 시스템이다. (이 때, PC는 CAP에서의 consistency가 아니라 일반적인 상황에 대비해서 consistency를 희생하지 않는다는 의미이다.)

Consistency Tradeoffs in Modern Distributed Database System Design 더 읽기"

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

지난 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를 복구하고 파티션 모드 동안의 실수를 만회하기 위한 파티션 복구 프로세스를 시작

Managing Partition

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 특집의 글들을 읽고 있습니다만, 이를 요약할 수 있을 정도로 완벽하게 이해하고 정리하는 것은 매우 시간이 걸리는 일이네요. 여력이 된다면 다섯개의 글 모두 정리해보고 싶습니다.

 

 

CAP Twelve Years Later: How the “Rules” Have Changed 더 읽기"