Paper: Conflict-free Replicated Data Types

Shapiro, Marc, et al. “Conflict-free replicated data types.” Stabilization, Safety, and Security of Distributed Systems. Springer Berlin Heidelberg, 2011. 386-400.

Distributed system에서 replica 사이의 consistency를 유지하는 것은 매우 어려운 문제지만, CRDT라고 불리는 특별한 데이터구조들은 semilattice나 commutativity와 같은 그 자체의 성질을 이용하여 consistency의 문제를 훨씬 단순한 문제로 만들어준다. CRDT에 해당하는 데이터구조나 수학적인 성질들은 오래전부터 알려져있었고 활용되어왔지만, 이 페이퍼의 저자들이 2007년에 처음으로 CRDT라는 이름을 붙였다. 2009년에는 Treedoc이라는 온라인 협업 에디팅을 위한 데이터구조를 제안하면서 역시 CRDT의 한가지 예로서 제시한다. 하지만 이 때까지도 CRDT의 정의는 commutativity를 이용한다 정도로 매우 모호한 상태였지만, 2011년에 출판된 이 페이퍼는 CRDT의 성질을 수학적으로 정의하고 증명한 것에 큰 의미가 있는 것으로 보인다. 이 페이퍼와 같은 해에 출판된 “A comprehensive study of convergent and commutative replicated data types.”란 페이퍼에서는 이 페이퍼의 개념들을 더욱 자세하게 설명할 뿐만 아니라 알려진 CRDT들의 카탈로그를 제시하고 자세하게 설명하고 있다. 이 페이퍼는 오히려 그 페이퍼의 정수만을 간추려놓은 논문으로 보인다.

Strong Eventual Consistency

Eventual consistent 시스템의 경우 필연적으로 conflict resolution이 필요하게 되는데, 이러한 conflict resolution의 부담을 덜어주는 메커니즘으로서 Version vector나 Dotted version vector 등을 사용한다. CRDT는 근본적으로 conflict가 발생하지 않는 데이터 구조이며, 따라서 causality tracking을 필요로 하지 않을 뿐더러 conflict resolution을 위한 coordination 등을 필요로 하지 않는다. 이러한 특성을 Strong Eventual Consistency라고 이야기 하고 있다.

We propose a simple, theoretically-sound approach to eventual consistency. Our system model, Strong Eventual Consistency or SEC, avoids the complexity of conflict resolution and of roll-back. Conflict-freedom ensures safety and liveness despite any number of failures. It leverages simple mathematical properties that ensure absence of conflict, i.e., monotonicity in a semi-lattice and/or commutativity. […] In our conflict-free replicated data types (CRDTs), an update does not require synchronisation, and CRDT replicas provably converge to a correct common state. CRDTs remain responsive, available and scalable despite high network latency, faults, or disconnection.

우선, Eventual Consistency를 어떤 replica의 causal history에 포함된 method는 결국에는 (eventually) 다른 replica의 causal history에 포함되는 것으로 정의하고 있다. 그리고 Convergence의 특성을 추가적으로 실행되는 method가 없어서 서로 다른 replica의 causal history가 동일하게 유지되는 상황에서는 결국에는 두 replica의 상태가 동등해지는 것으로 정의하고 있다. □(Globally)나 ◊(Finally)와 같은 notation은 처음으로 본 것인데 Temporal Logic에서 사용되는 notation인 것 같다.

Definition 2.2 (Eventual Consistency (EC)). Eventual delivery: An update delivered at
some correct replica is eventually delivered to all correct replicas: ∀i, j : fci ⇒ ◊f
cj .
Convergence: Correct replicas that have delivered the same updates eventually reach equivalent
state: ∀i, j : □ci = cj ⇒ ◊□sisj .
Termination: All method executions terminate.

Strong Eventual Consistency는 여기에 더해서 서로 다른 replica의 causal history가 동일하다면 동등한 상태를 가지는 특성으로 정의하고 있다. 이 paper에서는 한 replica의 causal history를 실행된 method들의 집합으로 정의하고 있으므로 – 그 method들에 대한 순서나 인과성 등의 정보는 포함하지 않고 있으므로 causal history라고 부르는 것은 조금 이상한 것 같다 – 정확히는 실행된 method들의 집합이 동일할 경우라고 보면 될 것 같다.

Definition 2.3 (Strong eventual consistency (SEC)). An object is Strongly Eventually Consistent if it is Eventually Consistent and:
Strong Convergence: Correct replicas that have delivered the same updates have equivalent state: ∀i, j : ci = cj ⇒ si ≡ sj .

State-based CRDT (CvRDT) and Operation-based CRDT (CmRDT)

CRDT를 2가지로 분류하고 있다. 첫번째는 상태들을 merge하는 method를 기반으로 정의하는, Replica들의 상태가 converge할 수 있는 형태의 CRDT인 Convergent Replicated Data Type (CvRDT)이고, 두번째는 operation들이 commutative한 성질을 기반으로 정의하는 CRDT인 Commutative Replicated Data Type (CmRDT)이다. Paper에서는 두 가지의 CRDT는 서로를 emulation할 수 있으므로 equivalent하다고 이야기 하고 있다.

우선 CvRDT의 정의를 이해하기 위해서는 lattice와 semilattice라는 수학 개념에 대해서 이해를 해야한다. Lattice란 기본적으로 어떤 ordering에 대해 정의되는 부분순서집합이며, 임의의 두 원소에 대해서 유일한 join과 meet가 그 집합 내에 존재해야한다. 여기서, join과 meet는 least upper bound와 greatest lower bound라고도 불리며, 우리에게 익숙한 개념으로 보자면, 최소공배수와 최소공약수에 해당하는 개념이다. 이 때, 최소공배수와 최소공약수가 각각 join과 meet가 되는 lattice는 배수를 ordering으로하는 정수집합에 해당한다. 정수집합의 모든 두 원소가 서로 배수관계가 있는 것은 아니지만 – 즉 부분순서집합 – 모든 두원소는 최소공배수와 최소공약수를 가진다. Semilattice란 join 또는 meet 중 하나를 가지는 부분순서집합이고, 어느 쪽이냐에 따라서 join-semilattice와 meet-semilattice로 불린다.

CvRDT에서 정의되는 객체는 객체들의 상태 집합에 대한 join-semilattice이고, merge method는 join 즉 least upper bound로 정의된다. 다시 말하면, 서로 다른 두 replica의 어떤 두 상태가 주어지더라도 이 상태를 merge한 상태가 정의되어있다고 할 수 있다. 이러한 객체가 SEC를 만족하는 것에 대한 증명은 어느 한쪽의…

Definition 2.4 (Monotonic semilattice object). A state-based object, equipped with partial order ≤, noted (S,≤, s0, q, u,m), that has the following properties, is called a monotonic semi-lattice: (i) Set S of payload values forms a semilattice ordered by ≤. (ii) Merging states with remote state s′ computes the LUB of the two states, i.e., s •m(s′) = s⊔s′. (iii) State is monotonically non-decreasing across updates, i.e., s ≤ s • u.
Theorem 2.1 (Convergent Replicated Data Type (CvRDT)). Assuming eventual delivery and termination, any state-based object that satisfies the monotonic semilattice property is SEC.

CmRDT는 말그대로 update method의 commutativity에 기초해서 상대적으로 단순하게 정의되고 있는데, 중요한 것은 concurrent update에 대해서만 commutativity 특성을 요구하고 다른 모든 update는 causal하게 전달되는 것을 가정하고 있다. 현실적으로는 어떤 경우에 어떤 update가 commutative하게 일어나고 어떤 경우에는 그렇지 않은 것은 쉽지 않기 때문에 이러한 제약을 주는 이유에 대해서 조금 의문이 들고, 특히 엄밀하게 정의되어있지 않은 CvRDT와 CmRDT의 equivalence에 대해서도 의문이 들게 만드는 부분이다.

Definition 2.6 (Commutativity). Updates (t, u) and (t′, u′) commute, iff for any reachable replica state s where both u and u′ are enabled, u (resp. u′) remains enabled in state s • u′ (resp. s • u), and s • u • u′ ≡ s • u′ • u.
Theorem 2.2 (Commutative Replicated Data Type (CmRDT)). Assuming causal delivery of updates and method termination, any op-based object that satisfies the commutativity property for all concurrent updates, and whose delivery precondition is satisfied by causal delivery, is SEC.

Example CRDTs

먼저 increment-only integer counter (G-Counter)를 위한 CRDT를 제시하고 있는데, 여러 replica는 integer vector의 각 replica에 해당하는 component를 increment하고, 두 vector의 merge operation은 각 component의 max를 취한 vector를 돌려주는 것으로 정의하고 있다. value method는 모든 component의 합에 해당하는 값을 돌려주게 된다.

increment와 decrement 둘다 가능한 integer counter (PN-Counter)를 위해서는 위에서 정의한 increment-only counter 2개를 결합하여, 하나는 increment를 기록하고 다른 하나는 decrement를 기록해서 실제 value method는 둘 사이의 차에 해당하는 값을 돌려주는 CRDT를 제시하고 있다.

여기서 설명한 G-Counter, PN-Counter를 포함해 G-Set, 2P-Set 등으로 이름지어진 여러 CRDT, 그리고 Directed Graph의 operation-based CRDT 구현 등에 대해 간략하게 설명하고 있는데, 위에서 언급한 “A comprehensive study of convergent and commutative replicated data types.”에서 훨씬 자세한 설명을 하고 있으므로 이 글에서는 생략하도록 한다. 이에 대해서 알고자 한다면 다음 페이지를 참고하면 좋을 것이라고 생각한다.

  • https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
  • https://vaughnvernon.co/?p=1012
  • http://blog.plasmaconduit.com/crdts-distributed-semilattices/
  • https://github.com/aphyr/meangirls

Closing

  • CRDT가 distributed system의 여러가지 도구들 – vector clock, log, … – 과 commutativity라는 관점에서 유사성을 공유하고 있는 것을 고려하면, CRDT의 정식화나 실제 CRDT들에 대해서 생각해보는 것은 좋은 도구가 되며 distributed system을 다루기 위한 사고 훈련이 되는 것 같다.
  • CRDT가 모든 문제를 해결해줄 수는 없으나 이미 알려진 CRDT들을 이용해서도 애플리케이션 관점에서 의미있는 이익을 얻을 수 있는 것으로 보인다. Garbage collection과 같은 실제적인 이슈들이 있으나 해결이 불가능한 것은 아니고, Riak 2.0 등에서 CRDT를 도입한 것을 볼 때 실제적인 응용을 시도해 볼 가치가 있다고 생각한다.
  • 이 논문의 저자들의 2007년, 2009년에 출판한 논문들은 CRDT라는 이름만 붙어있을 뿐이지 수학적인 정식화 등은 전혀들어있지 않다. 하지만, 이름을 붙이고 수년동안 연구를 하면서 완벽하지는 않지만 어느 정도의 엄밀함을 가진 모델을 성립시키고 하나의 분야로서 다루어질 수 있게 된 것 같다. 물론 이것만 하더라도 대단한 것이지만, A급 컨퍼런스의 A급 논문들만 보다보면 처음부터 거추장스러운 것은 하나도 없고, 논리적으로 완벽하며 또한 해당 분야에서도 중요한 의미를 지니고 있는 세상에 없을만한 것으로 보이곤 한다. 이 둘을 보면서, 평범한 과학자나 엔지니어들의 현실은 오히려 이러한 A급 논문보다 이들 논문들과 더 가깝지 않을까라는 생각이 조금 들었다.

What consistency does your key-value store actually provide?

What consistency does your key-value store actually provide? by Anderson, Eric, et al

Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace. We run these algorithms on traces of our eventually consistent key value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.

예전에 HP-KVS에 관련해서 자료를 찾다가 발견한 페이퍼인데, 얼마전 한국에 다녀올 때 읽어보게 되었습니다.

1. Perceived consistency rather than worst-case consistency

이 페이퍼는 일반적으로 key-value store들이 보장하는 worst-case consistency가 아니라, 실제로 client에 의해서 관찰되는 consistency의 수준을 측정하는 알고리즘을 제안하고 있다. 우리가 스토리지 기술을 선택할 때는 물론 worst-case consistency가 고려되기는 하지만, 실제로는 ‘실용적인’ 접근을 취하는데, 그것이 의미하는 바는 애플리케이션의 액세스 패턴에 따라 사용자가 느끼는 consistency의 수준이 달라질 수 있음을 고려해서 스토리지 기술을 선택한다는 것이다. 이 페이퍼가 해결하려는 문제 자체가 엄밀하거나 학술적이기 보다는 실용적인 의미를 해석하려는 것이기 때문에 한계는 있겠지만, 어떤 worst-case consistency를 가진 스토리지 – 예를 들어 eventually consistent 스토리지들이 어떤 애플리케이션에 필요한 consistency를 달성하기에 충분한지 충분하지 않은지에 대해서 매우 피상적으로 논의하는 것보다는 체계적인 방법을 제공한다는 점 그리고, 그러한 방법이 존재할 수 있다는 점에서 의미가 있는 것 같다.

2. A eager, eventually consistent protocol often achieves strong consistency

이 알고리즘을 통한 검증을 역시 HP에서 만든 eventually consistent key-value store인 Pahoehoe를 가지고 실험한 결과를 보여주고 있는데, 가장 concurrent한 조건 (128 concurrent processes on 1 key)에서도 consistency violation의 수가 10% 이하로 발생하고 있고, 일반적인 조건 하에서는 1% 수준이다. 그 이유를 우리가 일반적인 웹 애플리케이션에서 예상하고 있는 것과 마찬가지로 concurrent write 하에서의 read가 많지 않기 때문으로 설명하고 있다.

3. Lamport’s consistency assumption on registers: safe, regular, and atomic

이 페이퍼가 검증하려고 하는 consistency 수준의 분류로 Leslie Lamport가 On Interprocess Communication. Part I: Basic Formalism에서 제안한 register의 3가지 consistency semantic을 사용하고 있다. 이는 다음과 같다.

3가지의 consistency 모두 write와 concurrent하지 않은 read는 가장 최근의 write에 의한 값을 return 해야한다. 차이는 write와 concurrent한 read에서 발생한다.

  • safe: write와 concurrent한 read는 임의의 값을 return
  • regular: write와 concurrent한 read는 가장 최근의 write에 의한 값과 concurrent한 write들에 의한 값들 중 하나를 return
  • atomic: write와 concurrent한 read도 가장 최근의 write에 의한 값을 return

worst-case consistency를 가지고 예를 든다면, 최근 유행하는 eventual consistent storage들은 concurrent하지 않은 read에 대해서 가장 최근의 write에 의한 값을 return하는 것을 보장하지 않으므로 가장 느슨한 수준인 safe 조차 만족하지 못한다. 반면에 일반적인 ACID 데이터베이스는 atomic 수준에 해당한다.

4. Methods

이 페이퍼가 제안하고 있는 알고리즘은 대략 다음과 같다.

  1. 어떤 key-value store에 대한 클라이언트의 모든 액세스에 대해 시작 시각과 종료 시각, 그리고 저장하거나 읽어온 값의 로그를 기록한다.
  2. 이 로그를 바탕으로 오퍼레이션이 vertex이고, should-happen-before 관계가 edge인 directed graph를 구성한다. 이 때 이 관계는 검증하려는 consistency 종류에 따라서 달라지는데, 대체로 시간의 관계, 값의 인과 관계를 의미한다고 보면 된다.
  3. 구성된 graph에서 cycle이 발견되지 않으면 consistent, 발견되면 inconsistent하다고 판단한다.

straight-forward하기 때문에 쉽게 이해할 수 있다. 시각의 정확성이나 값의 인과관계를 찾는 부분 등에서 보완이 필요한 것 같긴 하지만 중요한 문제는 아닌 것 같다.

5. Measuring Consistability

여러 eventually consistent 스토리지들은 failure가 발생했을 때 consistency를 희생하게 되어있는데 이 때의 consistency 희생이 어느 정도인지 측정하는 작업이 필요하다.

6. Further Reads

  • J. Misra, Axioms for memory access in asynchronous hardware systems, 1986.
  • L. Lamport, On interprocessing communication, Part I: Basic formalism and Part II: Algorithms, 1986
  • W. Vogels, Eventually consistent, 2009
  • A. Aiyer, et al., On the availability of non -strict quorum systems, 2005
  • E. Anderson, et al., Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive, 2010

Paxos Made Simple

Paxos Made Simple by Leslie Lamport

Paxos Made Simple이라는 글의 저자인 Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다. 그의 주요한 업적 중 하나가 바로 Paxos 알고리즘인데, 최근에는 Chubby나 Zookeeper 등의 제품으로 구현되어 분산 시스템의 중요성이 점점 떠오르고 있는 요즈음 더욱 더 일상적으로 쓰이게 되어가고 있습니다.

The Paxos algorithm, when presented in plain English, is very simple.

Abstract에서 보다시피 이 글은 Paxos 알고리즘을 쉬운 말로 설명하고자 하는 시도인데, 합의 문제로부터 정의되는 조건을 충족하기 위한 자연스러운 해결책이 바로 Paxos 알고리즘임을 보이려 하고  있습니다.

하지만, 논리적인 단계들을 정확하기 이해하기 위해서는 쉬운 말로 쓰여진 용어들을 정확하게 해석해야 하기 때문에, 프로그래머 입장에서 볼 때는, 오히려 의사 코드 수준으로 설명하는 다른 글 (예를 들어, Paxos Made Moderately Complex)들이 훨씬 더 이해하기 쉽다는 생각이 들었습니다.

아래는 요약이라고 하기에는 너무 길고, 그렇다고 번역이라고 할 수도 없지만, 개인적으로 중요하다고 생각한 점들을 기록한 메모라고 보시면 좋을 것 같습니다.

Read More

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를 희생하지 않는다는 의미이다.)