CAP

CAP 은 여러 대에 나눠 담은 데이터에서 무엇을 포기할지 정하는 축입니다. 서버 사이의 연결이 끊긴 동안에는 값을 하나로 지키는 쪽과 응답을 계속 돌려주는 쪽이 양 끝입니다. 둘 다 지키는 방법은 없습니다.

쉽고 빠른 이해

CAP 은 서버 사이 연결이 끊긴 동안 무엇을 포기할지 정하는 축입니다. 장바구니는 응답을 계속 돌려주는 쪽으로, 결제 기록은 값을 하나로 지키는 쪽으로 따로 정할 수 있습니다.

「셋 중 둘만 고른다」로 알려져 있지만 그렇게 읽으면 어긋납니다. 연결이 멀쩡한 평소에는 둘 다 가집니다. 게다가 셋 중 하나인 네트워크 끊김은 고르는 것이 아니라 일어나는 일입니다. 끊기지 않기를 고를 수 있는 설계자는 없습니다. 남는 선택은 끊긴 동안의 둘뿐입니다.

끊김은 이렇게 다룹니다.

1. 끊긴 것을 알아챕니다
2. 일부 연산을 막은 채로 돕니다. 값을 지킬지 응답을 계속할지를 여기서 고릅니다
3. 연결이 돌아오면 갈린 값을 합치고 잘못 나간 것을 되돌립니다

대가는 고른 쪽마다 다릅니다. 값을 지키면 끊긴 동안 일부 요청이 응답을 못 받습니다. 응답을 계속하면 합칠 수 없는 충돌이 남습니다. 사람이 손으로 풀어야 할 수 있습니다.

상세

CAP(Consistency, Availability, Partition tolerance)은 일관성·가용성·분할 내성 세 글자를 딴 이름입니다. 일관성은 데이터의 최신 사본을 하나만 두는 것과 같습니다. 가용성은 고장 나지 않은 노드가 받은 요청에 응답이 돌아오는 것입니다. 갱신 요청도 마찬가지입니다. 분할 내성은 네트워크 분할에 대한 내성입니다. Brewer 는 2000년 기조강연 슬라이드에 어떤 공유 데이터 시스템도 이 성질 중 최대 둘까지만 가질 수 있다고 적었습니다. 12년 뒤 같은 저자는 네트워크로 이어진 공유 데이터 시스템이 셋 중 최대 둘만 가질 수 있다고 다시 적습니다.

같은 글에서 Brewer 는 그 「셋 중 둘」이라는 표현이 늘 오해를 낳았다고 적습니다. 성질 사이의 긴장을 지나치게 단순하게 만들었기 때문입니다. CAP 이 실제로 금지하는 것은 설계 공간의 아주 작은 부분뿐입니다. 분할이 있는 동안의 완전한 가용성과 완전한 일관성입니다. 그리고 분할은 드뭅니다. 분할이 없는 동안에는 일관성도 가용성도 내줄 이유가 거의 없습니다. 분할을 다루는 방법과 거기서 회복하는 방법에는 아주 넓은 여지가 있다고 Brewer 는 적습니다.

세 번째 글자는 나머지 둘과 성격이 다릅니다. 분할 내성은 설계자가 고르는 것이 아니라 네트워크에서 일어나는 일입니다. 광역 시스템에서는 설계자가 분할 내성을 내줄 수 없다는 것이 일반적인 통념입니다. 그래서 일관성과 가용성 사이의 어려운 선택이 남는다고 Brewer 는 적습니다.

기제는 노드 두 개로 드러납니다. 분할의 양쪽에 노드가 하나씩 있다고 놓습니다. 한쪽 노드에라도 상태 갱신을 허용하면 두 노드가 어긋나므로 일관성을 내주게 됩니다. 반대로 일관성을 지키기로 하면 분할의 한쪽은 가용하지 않은 것처럼 행동해야 하므로 가용성을 내주게 됩니다. 노드가 서로 통신할 때만 일관성과 가용성을 함께 지킬 수 있습니다. 그때는 분할 내성을 내주는 것입니다. 분할이 나도 두 노드는 각자 요청을 계속 받습니다. 끊긴 것은 노드 사이의 연결뿐입니다. 그래서 무엇을 내줄지를 각 노드가 정해야 합니다.

flowchart TD
    K1["클라이언트"] --> N1["노드"]
    K2["클라이언트"] --> N2["노드"]
    N1 -. 분할 .- N2

Gilbert 와 Lynch 가 2002년에 이 추측을 증명했습니다. 정리 1 은 비동기 네트워크 모형에서 가용성과 원자적 일관성을 함께 보장하는 읽기·쓰기 데이터 객체를 구현하는 것이 불가능하다고 말합니다. 메시지가 유실되는 실행을 포함한 모든 공정한 실행에서 그렇습니다. 두 사람은 2012년에 같은 것을 한 문장으로 다시 적습니다. 통신 실패가 일어나는 네트워크에서는 어떤 웹 서비스도 모든 요청에 응답을 보장하는 원자적 읽기·쓰기 공유 메모리를 구현할 수 없습니다.

증명 스케치는 갈림길을 한 노드의 처지로 보여줍니다. 그 노드는 아무리 오래 기다려도 두 경우를 구분할 수 없습니다. 어느 값을 돌려줘야 하는지 판정하지 못합니다. 남는 선택은 둘입니다. 언젠가 응답을 돌려주되 잘못된 응답을 돌려줄 위험을 지거나, 응답을 영영 돌려주지 않는 것입니다.

분할은 시간으로 나타납니다. 고전적 해석의 CAP 은 지연을 무시하지만 실무에서는 지연과 분할이 깊이 얽혀 있다고 Brewer 는 적습니다. 운영상 CAP 의 본질은 타임아웃 동안 일어납니다. 그 순간 프로그램은 연산을 취소해 가용성을 낮추거나 연산을 진행해 비일관성을 감수해야 합니다. Paxos 나 2단계 커밋으로 통신을 재시도하는 것은 결정을 미룰 뿐입니다. 언젠가는 결정해야 합니다. 무한정 재시도하는 것은 본질적으로 가용성 대신 일관성을 고르는 것입니다. 실용적으로 분할은 통신에 걸린 시간 한계입니다.

분할이 드물기 때문에 Brewer 는 분할을 명시적으로 다루는 전략을 제안합니다. 세 단계입니다. 분할을 감지합니다. 일부 연산을 제한할 수 있는 명시적 분할 모드로 들어갑니다. 일관성을 되돌리고 분할 중에 저지른 잘못을 보상하는 복구 절차를 시작합니다.

stateDiagram-v2
    state "정상" as A
    state "분할 모드" as B
    state "복구" as C
    A --> B: 분할 감지
    B --> C: 통신 회복
    C --> A: 일관성 복원과 보상

양 끝

두 끝은 분할이 난 동안에만 갈립니다. 한쪽은 값을 하나로 지킵니다. 다른 쪽은 응답을 계속 돌려줍니다. Gilbert 와 Lynch 는 이 대립을 안전성과 생존성으로 다시 적습니다. 일관성은 잘못된 일이 결코 일어나지 않는다는 안전성 성질입니다. 클라이언트에 보내는 모든 응답이 옳습니다. 가용성은 언젠가 바라던 일이 일어난다는 생존성 성질입니다. 결국 모든 요청이 응답을 받습니다. CAP 은 신뢰할 수 없는 분산 시스템에서 안전성과 생존성을 함께 달성할 수 없다는 근본 사실의 한 예라고 두 사람은 적습니다.

일관성 쪽

일관된 서비스를 형식화하는 가장 자연스러운 방법이 원자적 데이터 객체라고 Gilbert 와 Lynch 는 적습니다. 원자적 일관성 또는 선형화 가능성이라 부릅니다. 모든 연산에 전체 순서가 존재해서 각 연산이 어느 한 순간에 완료된 것처럼 보여야 합니다. 분산 공유 메모리에 대한 요청이 한 노드에서 한 번에 하나씩 실행되는 것처럼 굴어야 한다는 요구와 같습니다. 쓰기가 완료된 뒤에 시작한 읽기는 그 값이나 이후 쓰기의 결과를 돌려주어야 합니다.

이 끝을 고르면 네트워크가 어떻게 굴든 일관성을 보장하도록 서비스를 설계합니다. 가용성은 그다음에 최선 노력으로 최적화합니다. 현재 네트워크 상태에서 가능한 만큼 응답하는 것입니다. 대가는 분할 동안 드러납니다. 한쪽은 응답을 거절해야 합니다.

가용성 쪽

연속적으로 가용하려면 고장 나지 않은 노드가 받은 모든 요청이 응답으로 이어져야 합니다. 서비스가 쓰는 알고리즘은 언젠가 종료해야 합니다. 저자들은 이것이 어떤 면에서는 약한 정의라고 적습니다. 종료까지 얼마나 걸릴지에 한계를 두지 않기 때문입니다. 무한한 계산도 허용합니다. 다른 한편 분할 내성이라는 요구가 붙으면 강한 정의로 볼 수 있다고 적습니다. 심각한 네트워크 장애가 일어나도 모든 요청이 종료해야 하기 때문입니다.

이 끝을 고르면 언제나 응답을 보장합니다. 되도록 빨리 오는 응답을 보장합니다. 대가는 응답의 내용에서 옵니다. 응답이 늘 옳지는 않습니다. 일관성은 최선 노력으로만 제공됩니다.

고를 수 없는 세 번째 글자

분할 내성은 앞의 두 정의에 붙는 단서입니다. 분할 내성을 모형화하기 위해 네트워크가 한 노드에서 다른 노드로 보낸 메시지를 임의로 많이 잃을 수 있게 허용합니다. 네트워크가 분할되면 한 구성 요소의 노드에서 다른 구성 요소의 노드로 보낸 모든 메시지가 유실됩니다. 어떤 메시지 유실 패턴이든 그 메시지가 유실되는 바로 그 순간 통신 노드를 갈라놓는 일시적 분할로 모형화할 수 있습니다. 이 끝은 설계자가 고르는 것이 아니라 네트워크에서 일어나는 일입니다.

중간에 서는 자리

둘 다 내주는 자리가 있습니다. 어떤 시스템은 일관성과 가용성을 모두 희생하기도 한다고 Gilbert 와 Lynch 는 적습니다. 그렇게 해서 당면 응용에 더 맞는 트레이드오프를 얻기도 합니다.

일관성의 범위라는 자리도 있습니다. 어떤 경계 안에서는 상태가 일관되지만 그 밖에서는 아무것도 보장되지 않는다는 생각입니다. 주 분할 안에서는 완전한 일관성과 가용성을 확보하고 분할 밖에서는 서비스를 제공하지 않을 수 있습니다. Paxos 와 원자적 멀티캐스트 시스템이 대개 이 모양에 들어맞습니다.

정족수를 쓰는 시스템이 한쪽만 여는 분할의 예입니다. 한쪽은 정족수를 갖고 진행할 수 있습니다. 다른 쪽은 진행할 수 없습니다. 경계 안쪽만 열리고 바깥은 닫히는 모양입니다.

flowchart TD
    subgraph S1["주 분할 · 정족수 있음"]
        A["노드 · 진행"]
        B["노드 · 진행"]
    end
    subgraph S2["분할 밖 · 정족수 없음"]
        C["노드 · 진행 못 함"]
    end
    A --- B
    B -. 분할 .- C

ACID 와 BASE 는 일관성과 가용성 스펙트럼의 양 끝에 놓인 두 설계 철학입니다. ACID 는 일관성에 초점을 맞춘 데이터베이스의 전통적 접근입니다. BASE 는 Basically Available, Soft state, Eventually consistent 입니다. 소프트 상태와 최종 일관성은 분할이 있을 때 작동하는 기법입니다. 그래서 가용성을 밀어 올립니다. Brewer 는 2000년 슬라이드에서 이것이 스펙트럼이라고 생각한다고 적었습니다. 실제 인터넷 시스템은 ACID 서브시스템과 BASE 서브시스템을 조심스레 섞은 것이라고도 적었습니다. 자기들은 사용자 프로필과 로깅에 ACID 를 쓴다고 덧붙였습니다.

선택 기준

조건이 먼저입니다. 아래 조건은 세거나 확인할 수 있는 것들만 골랐습니다.

데이터마다 다른 값을 고를 수 있습니다. 온라인 장바구니는 사용자 요청에 즉각 응답하도록 고가용으로 둘 수 있습니다. 그러면서 이따금 비일관될 수 있습니다. 이상한 상황에서 최근 갱신 하나를 잃기도 합니다. 전자상거래 사이트의 상품 정보도 다소 비일관될 수 있습니다. 사용자는 다소 낡은 재고 정보를 견딥니다. 반면 결제와 청구와 배송 기록은 강한 일관성을 지켜야 합니다. 확정된 주문이 의도한 구매를 반영하지 않으면 사용자가 매우 불쾌해하기 때문입니다.

연산마다 다르게 고를 수도 있습니다. 읽기 전용 연산에는 높은 가용성을 보장하고 데이터베이스를 수정하는 연산은 분할 동안 응답하지 않는 시스템을 생각할 수 있습니다. 갱신 종류마다 수준을 달리하기도 합니다. 구매 연산은 일관성을 보장하고 조회 연산은 낡은 데이터를 돌려줄 수 있습니다.

무엇을 제한할지는 주로 시스템이 지켜야 하는 불변식이 정합니다. 불변식 집합이 주어지면 설계자는 그 불변식을 분할 모드 동안 유지할지, 아니면 어길 위험을 지고 복구 때 되돌릴지를 정해야 합니다. 표의 키가 유일하다는 불변식이 예로 나옵니다. 설계자는 대개 그 불변식을 걸고 분할 동안 중복 키를 허용하는 쪽을 고릅니다. 중복 키는 복구 때 찾아내기 쉽습니다. 병합할 수 있다고 가정하면 불변식을 쉽게 되돌릴 수 있습니다. 분할 동안 반드시 지켜야 하는 불변식이라면 그것을 어길 수 있는 연산을 금지하거나 고쳐야 합니다. 신용카드 청구 같은 외부화된 사건이 흔히 이렇게 다뤄집니다. 이때의 전략은 의도를 기록해 두고 복구 뒤에 실행하는 것입니다.

병합이 언제나 되는 것은 아닙니다. 대부분의 시스템은 충돌을 항상 병합하지는 못합니다. CVS 는 이따금 사용자가 손으로 풀어야 하는 충돌을 냅니다. 오프라인 모드가 있는 위키 시스템은 대개 결과 문서에 손으로 고쳐야 하는 충돌을 남깁니다. 반대로 특정 연산만 쓰면 충돌을 항상 병합할 수 있는 시스템도 있습니다. 충돌 해소의 일반 문제는 풀리지 않습니다. 그래도 설계자는 분할 동안 어떤 연산의 사용을 제한해서 복구 때 상태를 자동으로 병합하게 만들 수 있습니다.

일관성을 내주는 쪽에는 숨은 값이 붙습니다. 시스템의 불변식을 알아야 한다는 것입니다. 일관된 시스템에서는 설계자가 불변식이 무엇인지 모르는 채로도 불변식이 유지되는 경향이 있습니다. 그래서 넓은 범위의 웬만한 불변식이 그냥 지켜집니다. 반대로 가용성 쪽을 고르면 분할 뒤에 불변식을 되돌려야 하므로 모든 불변식을 명시해야 합니다. 이 일은 까다롭고 오류가 나기 쉽습니다.

조건이 부딪히면 미리 고르지 못합니다. 그 결정은 타임아웃 순간으로 미뤄집니다. 그 순간 연산을 취소할지 진행할지를 프로그램이 정합니다.

경계

분할이 나지 않은 동안에도 이 축이 무언가를 강제하나. 아닙니다. 분할이 드물기 때문에 시스템이 분할되지 않은 동안에는 일관성도 가용성도 내줄 이유가 거의 없다고 Brewer 는 적습니다. 평상시에 무엇을 고를지는 이 축이 정하지 않습니다.

그렇다고 그런 시스템이 이 축 밖으로 나가는 것은 아닙니다. 분할 내성을 내준다는 것이 정확히 무엇을 뜻하는지가 불분명하다고 Brewer 는 적습니다. 설계자가 분할이 없기를 고를 수는 없습니다. 일관성과 가용성만 고르는 조합을 생각해 봅니다. 그것을 골라 둔 시스템에 분할이 나면 선택은 다시 일관성 또는 가용성으로 되돌아가야 합니다. 그래서 그 조합을 고른다는 말은 확률로 읽어야 합니다. 분할 확률이 재해나 동시다발 장애 같은 다른 계통 장애의 확률보다 훨씬 낮다는 뜻이어야 합니다. 실제로 대부분의 집단은 데이터센터 한 곳 안에는 분할이 없다고 가정합니다. 그리고 단일 사이트 안에서 그 조합을 목표로 설계합니다. 전통적인 데이터베이스를 포함한 그런 설계가 CAP 이전의 기본값입니다.

세 글자를 「셋 중 둘 고르기」로 읽는 축약은 세 자리에서 어긋납니다. 첫째가 방금 적은 자리입니다. 둘째, 일관성과 가용성 사이의 선택은 한 시스템 안에서 아주 잔 단위로 여러 번 일어납니다. 서브시스템마다 다르게 고를 수 있습니다. 연산에 따라, 심지어 관련된 특정 데이터나 사용자에 따라 선택이 달라지기도 합니다. 셋째, 세 성질 모두 이진이 아니라 연속에 가깝습니다. 가용성은 0에서 100퍼센트까지 연속입니다. 일관성에도 여러 수준이 있습니다. 분할에도 미묘한 구석이 있습니다. 분할이 존재하는지를 두고 시스템 안에서 의견이 갈리기도 합니다.

평상시에 이 축이 강제하지 않는다는 판정에는 모형이라는 단서가 붙습니다. Gilbert 와 Lynch 의 따름정리 1.1 은 비동기 네트워크 모형에서 메시지가 유실되지 않는 공정한 실행에서만 원자적 일관성을 보장하는 객체조차 구현할 수 없다고 말합니다. 통신이 비동기이면 메시지가 하나도 유실되지 않은 실행에서도 같은 상황이 생길 수 있습니다. 실제 분할이 없는데도 그렇습니다. 다만 부분 동기 모형에서는 따름정리 1.1 의 유사물이 성립하지 않습니다. 이 따름정리의 증명은 노드가 메시지 유실 시점을 알지 못한다는 데 기대기 때문입니다. 부분 동기 모형에는 모든 메시지가 전달되는 실행에서는 원자적 데이터를 돌려주고 메시지가 유실될 때만 낡고 비일관된 데이터를 돌려주는 알고리즘이 있습니다.

관련 항목

CAP 세 글자를 이루는 성질

일관성 · 가용성 · 네트워크 분할 · 분할 내성

일관성·가용성을 가리키는 다른 이름

원자적 일관성 · 선형화 가능성 · 안전성 · 생존성

정리 증명이 딛고 서는 모형

비동기 네트워크 모형 · 부분 동기 모형 · 공유 메모리

분할 내성을 포기해 일관성과 가용성을 함께 얻는 사례

단일 사이트 데이터베이스 · 클러스터 데이터베이스 · LDAP(Lightweight Directory Access Protocol, 경량 디렉터리 액세스 프로토콜) · xFS · Ninja · 2단계 커밋 · 캐시 검증 프로토콜

일관성 쪽을 구현하는 기법·사례

비관적 락 · 분산 락 · 분산 데이터베이스 · 과반수 프로토콜 · 정족수 · Paxos · 합의 · 원자적 멀티캐스트 · ACID · 일관성의 범위 · 주 분할

가용성 쪽을 구현하는 기법·사례

최종 일관성 · BASE · 소프트 상태 · 리스 · 만료 · 충돌 해소 · 낙관적 방식 · 웹 캐싱 · DNS(Domain Name System, 도메인 이름 시스템) · Coda · 낡은 데이터 · 위키 · CVS(Concurrent Versions System, 동시 버전 시스템)

분할 대응이 밟는 앞뒤 단계

타임아웃 · 지연 · 분할 모드 · 복구 · 보상

분할 동안 지킬지 정하는 불변식과 사례

불변식 · 병합 · 중복 키 · 외부화된 사건