CAP Theorem 과 PACELC Theorem 1편 CAP Theorem 의 등장

CAP Theorem 과 PACELC Theorem 에 대해 알아 볼 일이 생겨서 공부 하면서 정리 해 보고 있다. 여러가지 자료를 찾아 보면서 보고 있지만 보면 볼 수록 점점 헷깔린다. 왜냐하면 CAP 이론이 2000년에 처음 발표 되고 시간이 흐르면서 기존의 CAP 이론은 공격을 받기 시작한다. 그러다가 CAP 이론을 만든 사람도 기존 CAP 이론의 부족함을 인정하고 업데이트 버전을 만들게 된다. 한편 CAP 이론의 부족함에 대해 지적한 일부는 PACELC 이론으로 돌아서게 된다. 그러다 보니 웹상에 공개된 자료들도 올라온 시기에 따라 달라진다. 그래서 일단 CAP 이론과 관련 히스토리 위주로 정리 해 보았다. 한번에 다 정리하기에는 내용이 길어져서 내용을 좀 나누어 작성해 보았다.

1998년 CAP 처음 등장

2012년에 작성한 CAP Twelve Years Later: How the "Rules" Have Changed 에서 CAP Theorem 은 1998년 가을에 처음 등장하였고 1999년에 발행되었다고 한다. 1998년과 관련된 자료는 아직 찾지 못하였다.

1999년 논문에 CAP Principle 게재

Brewer 와 Fox 가 함께 쓴 논문(Harvest, Yield, and Scalable Tolerant Systems)에 CAP Principle 이 등장한다.

---

---

해당 논문 내용에서 몇가지를 추려내어 보았다.

우선 CAP 각각에 대해서 설명는 부분이 있는데, Strong consistency 는 singlecopy ACID consistency 를 의미하고, High availability 는 가용성, Partition-resilience 은 파티션이 나눠진 상황에서도 시스템이 살아 있음을 의미한다. 여기서도 CAP 중 최대 2개를 고를 수 있다고 나온다.

• CA without P: 분산 트랜잭션 데이터베이스는 네트워크 파티션이 없는 경우 수행 할 수 있다.
• CP without A: 파티션 상황에서 파티션이 복구되기 전까지는 ACID 데이터베이스의 트랜잭션은 중단된다. 병합충돌을 피하기 위해서이다. 일관성을 피하기 위함이다.
• AP without C: HTTP Web caching 은 문서 복제를 통해 클라이언트-서버 파티션 복원을 제공한다. 그러나 클라이언트-서버 파티션은 만료된 복제에 대해 최신데이터인지 검증을 못하게 한다. 일반적으로 분산 데이터베이스 문제는 만료 기반의 캐시를 사용해서 AP 를 실현하거나 복제본과 다수결을 통해 PC를 얻는다. 소수는 안된다. (PC를 얻는게 아니고 CP를 얻는다 일까?)

Bayou 분산 데이터베이스, Coda disconnected file system 를 예로 들며 이야기도 나오고 Strong CAP Principle 이니 Weak CAP Principle 과 같은 이야기가 나오는데 일단 생략 하겠다. 추후 기회가 되면 좀 더 자세히 풀어 봐야 겠다.

논문 제목에서 Harvest 와 Yield 라는 단어가 나오는데 둘 다 국어사전에는 "수확"의 의미를 가지고 있다. 차이점은 yield 는 수익률에서도 사용된다. 차이점에 대해 알고 싶으면 Difference Between Harvest and Yield 라는 글을 읽어 보기 바란다. 여기 나온 예제로 "My pumpkin farm yields over 1000 pounds of pumpkins every year, but we can only harvest about 800 pounds of them.", "The yield on this investment is currently 3%" 가 있다. yield 는 농사를 넘어서 경제용어로도 쓰이는 단어이다. 어렴풋이 알듯 하면서도 좀 애매하다.

2000년 7월 Eric Brewer 가 PODC 에서 CAP Theorem 발표

2000년 7월 19일 PODC (Sysposium on Principles of Distrubuted Computing) 행사에서 컴퓨터과학자 에릭 브루어(Eric Brewer)가 CAP 이론을 발표하게 된다. Towards Robust Distributed Systems - 강력한 분산 시스템으로의 지향 - Dr. Eric A. Brewer Professor, UC Berkeley 프레젠테이션으로 된 자료라 설명이 자세히 나와 있지는 않다.

그 때 발표한 자료에서 CAP 이론의 일부 내용을 발췌하였다. Consistency vs Availability (ACID vs BASE) 이야기가 나오다가 CAP 이론으로 이어진다. ACID 와 BASE 에 대해 간단하게 짚어 보고 넘어가자면, ACID 는 Atomicity, Consistency, Isolation, Durability 의 약자로 고립되어 있어서 강력한 일관성을 가진다. ACID 데이터베이스는 데이터베이스 트랜잭션이 안전하게 수행된다는 것을 보장하기 위한 성질을 가리킨다. BASE 는 Basically Available, Soft state, Eventual consistency (최종 일관성)의 약자로 분산 컴퓨팅에서 고가용성을 위해 일관된 최근 데이터를 얻지 못하는 것을 감안하며, 최종적으로는 일관성을 가지긴 한다는 의미이다.

CAP Theorem 으로 돌아와서, 공유 데이터시스템에서 CAP 일관성(Consistency), 가용성(Availability), 네트워크 파티션 허용 (Tolerance to network Partition)중 최대 두개의 속성을 가질 수 있다는 이야기가 나온다. 1999년의 자료의 P 는 Partition-resilience 라고 나왔었는데 여기서는 Tolerance to network Partitions 으로 나온다. Resilience(탄력, 회복력)과 Tolerance(허용, 내성, 포용력)은 비슷한듯 하면서 좀 다른 느낌이다.

Theorem: You can have at most two of these properties for any shared-data system

Forfeit Partitions1999년 자료에는 with out 을 썼는데 여기서는 Forfeit (상실, 몰수) 라는 표현을 쓴다. CA without P 은 CA 강조하는 느낌인데 여기서는 P의 Forfeit (상실, 몰수)를 더 강조하고 있다. 뒤에 가면 Sacrifice P 처럼 P를 희생한다는 방식으로 표현하기도 한다. 비슷한 말이지만 늬앙스가 조금씩 다르다.

후에 인터넷에 떠도는 그림의 예제로는 RDBMS 가 많이 언급 된다. 하지만 여기서는 RDBMS 는 언급되지 않고 Single-site databases, Cluster databases, LDAP, xFS file system 를 예로 들고 있다. CA는 뒤에 언급되겠지만 CA 공격을 많이 받게 되고 결국 현실적으로 불가능하다는 결론에 이르게 된다.

Forfeit Availability

가용성을 몰수하고 CP를 선택 하는 경우에 대한 내용이다. 예제로 분산데이터베이스, 분산락킹, 대다수의 프로토콜이 나온다. 특성으로는 비관적인 락킹과 소수 파티션을 사용할 수 없게 만든다는 점이 있다. 비관적인 락킹은 무슨 의미로 쓴건지 잘 이해가 안간다. 소수 파티션을 사용할 수 없다는 건 또 무슨 말일까?

Forfeit Consistency

일관성을 몰수하고 AP를 선택하는 경우에 대한 내용이다. 예제로 Coda, Web caching, DNS 가 나온다. 특성으로는 만기/임대, 충돌 해결, 낙관이 있다.

그 다음장에 나오는 내용은 다음과 같다.

These Tradeoffs are Real

• The whole space is useful
• Real internet systems are a careful mixture of ACID and BASE subsystems
  • We use ACID for user profiles and loggin (for revenue)
• But there is almost no work in this area
• Symptom of a deeper problem: systems and database communities are separate but overlapping (with distinct vocabulary)

번역해 보자면, 실제 인터넷 시스템은 ACID와 BASE 서브시스템을 혼합한 것이다. ACID 는 사용자 정보와 로그인에 사용한다. 하지만 이 분야(분산 시스템?) 에서는 거의 그럴 일 없다. 더 심한 문제의 증상으로 시스템과 데이터베이스의 커뮤니티는 분리되어 있지만 겹쳐져 있다. ... 뭔 이야기인지 잘 모르겠다.

CAP Take Homes

• Can have consistency & availability within a cluster (foundation of Ninja), but it is still hard in practice
• OS/Networking good at BASE/Availability, but terrible at consistency
• Databases better at C than Avaiability
• Wide-area databases can't have both
• Disconnected clients can't have both
• All systems are probabilistic...

일관성과 가용성은 하나의 클러스에서는 가질 수 있다. 그러나 실제로는 어렵다. (CA 의 어려움을 인정하긴 한다.) OS/Networking 은 가용성에 좋지만 일관성이는 끔찍하다. (왜지?) 데이터베이스는 가용성보다는 일관성에 더 좋다. 넓은 범위에서 데이터베이스는 둘 다 가질 수는 없다. 연결되지 않은 클라이언트는 둘다 가질 수 없다. 모든 시스템은 확률적(?)이다.

프레젠테이션 자료만 봐서는 확실히 이해하기에는 부족한 부분이 많다. 아무튼 일단 여기서 줄인다. 좀 더 이해가 되면 내용을 좀 더 업데이트 해 보겠다.

2002년 Seth Gilber 와 Nancy Lynch 의 CAP 이론 증명

CAP 이론에 힘이 실리기 시작하는 해 이다. 세스 길버트(Seth Gilbert) 와 낸시 린치 (Nancy Lynch) 가 CAP 이론을 증명하였다. Brewer's Conjecture(추측) and the Feasibility(타당성) of Consistent, Available, Partition-Tolerant Web Service 논문에서 확인 해 볼 수 있다.

초록 (Abstract)

분산 웹 서비스 (Distributed web services)를 디자인 할 때 흔히 요구되는 항목으로 일관성 (Consistency), 가용성 (availability), 분할 용인 (Partition tolerance)가 있다. 세가지 모두를 만족하기는 불가능하다. 여기서 우리는 비동기 네트워크 모델에서의 추측을 증명하고 부분적인 동기 모델에서의 딜레마의 해결책에 대해 논의 해 본다.

PODC 2000 에서 Brewer 는 웹서비스에서 일관성, 가용성, 분할 용인 모두를 보장할 수는 없다고 했다. 세 속성은 실제세계의 웹서비스에서는 탐나고 기대된다. ... 이하 생략

결론

이 글에서 네트워크 파티션 상황에서 일관된 데이터가 불가능함을 보였다. 그러나 셋 (일관성, 가용성, 분할용인) 중 둘을 이루는것은 실현 가능하다. 비동기모델에서 시계를 사용할 수 없는 경우 불가능한 결과가 발생한다. 일관된 데이터를 제공하는 것은 불가능 하며 심지어 메시지를 잃어 버린 경우 부실 데이터가 반환 될 수도 있다. 그러나 부분적으로 동기 모델에서는 일관성과 가용성 사이에서 실제적인 절충안을 달성 할 수 있다. 특히 오늘날 대부분의 실제 시스템은 "대부분의 데이터를 대부분의 시간"으로 되돌려 주도록 강요 받고 있다. 이 아이디어를 공식화하고 이를 달성하기 위한 알고리즘을 연구하는 것은 향후 이론 연구에서 흥미로운 주제이다.

중간 내용은 짬이 나면 좀 더 읽어 보고 정리 해 봐야 겠다.

다음편은

이후로 2010년 전 까지는 CAP 이론은 순항 해 간다. 그러다가 2010년에 공격을 받기 시작 한다. 이후로 작성할 글에서는 그러한 이야기들에 대해서 다뤄 보도록 하겠다.

지금 이 글도 아직 모든 내용을 이해하고 쓴 내용은 아니라 부족 할 수 있다. 추후 좀 더 이해가 되면 좀 더 내용을 보강 해 보겠다. 어쩌면 글이 더 나눠 질지도 모르겠다.