CS for DEV

Theme

10.2 복제와 일관성 — 무엇을, 언제 보이게 할 것인가 ​

복제본이 두 개 이상이면 "지금 이 값은 무엇인가"라는 질문에 하나의 답만 있을 수 없다. 이 문서는 단일 리더·복수 리더·리더 없는 복제 전략을 안전성의 원천과 가용성 특성으로 비교하고, linearizability부터 eventual consistency까지 일관성 모델의 스펙트럼을 세운다. 마지막으로 네트워크 분단을 전제로 CAP 정리의 정확한 조건과 흔한 오독을 구분한다.

학습 목표 ​

  • 단일 리더·복수 리더·리더 없는(quorum) 복제 전략을 안전성의 원천과 가용성 특성으로 비교한다.
  • linearizability, sequential consistency, causal consistency, eventual consistency를 보장 강도와 허용하는 이상 현상으로 구분한다.
  • quorum read/write(N, W, R)의 수학적 관계와 그 관계가 실제로 보장하는 것·보장하지 않는 것을 구분한다.
  • 네트워크 분단을 정확히 정의하고, CAP 정리를 오독 없이 서술하며 실제 시스템 설계 판단에 적용한다.

배경: 복제는 사본이 아니라 지연 있는 전파다 ​

복제는 가용성(한 노드가 죽어도 서비스 지속), 내구성(데이터 손실 방지), 지역성(가까운 복제본에서 읽어 지연 단축)을 얻기 위한 수단이다. 그런데 복제본을 "원본의 사본"으로 생각하면 첫 단추부터 잘못 끼운다. 사본은 원본과 동시에 존재하지만, 복제본은 항상 전파에 걸리는 시간만큼 과거의 어느 시점을 반영한다.

text
쓰기가 노드 A에 도달한 순간           t0
                                       │  네트워크 전파 지연
노드 B가 그 쓰기를 받는 순간           t0 + δ

δ가 0에 가까울수록 "복제본은 최신이다"라는 직관이 맞아떨어지지만, δ를 0으로 만들려면 모든 쓰기가 모든 복제본의 확인을 기다려야 하고, 그 순간 10.1에서 본 부분 실패와 진행(liveness)의 트레이드오프가 그대로 돌아온다. 일관성 모델이란 이 δ 동안 무엇을 보여줄지, 그리고 그 대가로 무엇을 지불할지를 명시적으로 정하는 계약이다.

핵심 개념 ​

복제 전략 세 가지 ​

단일 리더(leader-based) ​

모든 쓰기가 한 리더를 거치고, 리더가 정한 순서를 followers가 그대로 적용한다. 안전성의 원천은 "누가 유일한 순서 결정자인가"에 달려 있다. 10.1의 Raft·Paxos로 리더를 세우면, 리더가 하나뿐이라는 보장 자체가 과반 교차라는 수학적 사실에서 나온다. 반면 단순 primary-backup 구성(합의 없이 수동 또는 휴리스틱으로 리더를 지정)에서는 그 보장을 별도의 fencing으로 직접 만들어야 한다 — 챕터 11.6이 다룬 epoch·lease·storage fence가 정확히 이 공백을 메우는 장치다.

가용성 특성은 리더 선출 방식에 정확히 대응한다. 합의 기반 리더는 소수 파티션에서 쓰기를 거부해 안전성을 지키는 대신 가용성을 낮춘다(10.1의 분단 시나리오가 이 동작을 그대로 보여줬다).

복수 리더(multi-leader) ​

둘 이상의 노드가 각자 쓰기를 받고 나중에 서로 전파한다. 흔히 지역별로 리더를 두어(서울 리전, 프랑크푸르트 리전) 각 리전이 로컬 쓰기를 즉시 받아들이게 하는 구성이다. 단일한 순서 결정자가 없으므로 같은 키에 대한 동시 쓰기가 서로 다른 리더에서 동시에 성공할 수 있다 — 이것이 충돌이며, 사후에 해결해야 한다(다음 절 참고). 대가로 얻는 것은 각 리전이 다른 리전과 단절돼도 로컬 쓰기를 계속 받을 수 있다는 가용성이다.

리더 없는(leaderless, quorum 기반) ​

모든 노드가 대등하게 읽기·쓰기를 받고, 클라이언트(또는 코디네이터)가 여러 노드에 동시에 요청을 보내 일정 수 이상의 응답을 모아 완료로 간주한다. Amazon Dynamo가 이 모델을 대중화했고 Cassandra·Riak이 계승했다. 일부 노드가 응답하지 않아도 진행할 수 있어 가용성이 가장 높지만, 안전성은 정족수(quorum)의 수학적 성질에 의존하며 — 이는 다음다음 절에서 살펴볼 것처럼 합의 수준의 보장이 아니다.

전략안전성의 원천충돌 처리가용성 특성대표 사례
단일 리더(합의 기반)과반 교차(10.1)발생하지 않음(단일 순서)소수 파티션에서 쓰기 불가Raft/Paxos 기반 스토어
단일 리더(비합의)별도 fencing 필요발생하지 않음(정상 시)fencing 구현에 의존, split-brain 위험전통적 primary-backup RDBMS
복수 리더없음(사후 병합)필요(LWW, CRDT, 앱 병합)리전 간 단절에도 로컬 쓰기 가능다중 리전 앱, 오프라인 동기화
리더 없음(quorum)정족수 중첩(부분적)필요(vector clock, read repair)개별 노드 실패에 가장 강함Dynamo, Cassandra, Riak

이 문서는 세 전략의 일반 이론을 다룬다. 구체적인 로그 위치 추적, bootstrap, failover 절차는 챕터 11.6 데이터베이스 복제가, 데이터를 노드에 배치하는 결정(파티셔닝/샤딩 — 다음 절에서 이 용어를 네트워크 분단과 구분한다)은 챕터 11.7이 구체화한다.

일관성 모델의 스펙트럼 ​

무엇을 "일관성 있다"고 부를지는 하나가 아니다. 강한 순서에서 약한 순서로 네 지점을 세운다.

linearizability — 복제본이 하나인 것처럼 ​

linearizability(Herlihy & Wing, 1990)는 가장 강한 보장이다. 모든 연산이 호출 시점과 응답 시점 사이의 어느 한 순간에 원자적으로 일어난 것처럼 보이고, 그 순간들의 순서가 실제 시계(wall-clock) 순서와 모순되지 않는다. "복제본이 여러 개라는 사실을 클라이언트가 전혀 알아챌 수 없다"는 말로 요약된다. 대가는 크다 — 모든 읽기·쓰기가 사실상 전역적으로 조정돼야 하므로 10.1이 세운 합의 수준의 조율이 필요하고, 파티션 중에는 지킬 수 없다(뒤의 CAP 절에서 증명한다).

sequential consistency — 순서는 있지만 시계와 무관 ​

sequential consistency는 챕터 8a의 메모리 모델에서 이미 만난 용어다 — 거기서는 한 프로세스 안의 메모리 접근 순서 보장으로 등장했다면, 여기서는 여러 복제본에 걸친 연산 순서 보장으로 같은 이름이 다른 규모에 적용된다. 모든 프로세스가 하나의 전역 순서에 동의하고, 그 순서는 각 프로세스 자신의 프로그램 순서와 일치해야 한다. 그러나 그 전역 순서가 실제 시계 순서와 일치할 필요는 없다 — 실시간으로는 A가 B보다 먼저 끝났어도, 전역 순서에서는 B가 A보다 앞에 놓일 수 있다. linearizability보다 조율 비용이 낮은 이유가 여기에 있다.

causal consistency — 인과관계만 지킨다 ​

causal consistency는 10.1의 happens-before로 정의된 인과관계가 있는 연산만 순서를 지키도록 요구하고, 동시(concurrent) 연산은 노드마다 다른 순서로 봐도 무방하다. "댓글이 원 게시물보다 먼저 보이는" 것은 인과관계 위반이라 causal consistency가 막지만, "서로 무관한 두 사용자의 좋아요 순서가 노드마다 다르게 보이는" 것은 애초에 인과관계가 없으므로 허용된다. 여러 연구가 causal consistency를 **"항상 가용해야 하는 시스템이 달성할 수 있는 가장 강한 일관성 모델"**로 규명했다(Mahajan, Alvisi, Dahlin, 2011) — 더 강한 모델(linearizability, sequential consistency)은 파티션 중 가용성을 희생해야만 지킬 수 있기 때문이다. 이 경계선이 다음 CAP 절의 핵심과 정확히 맞닿는다.

eventual consistency — 최소한의 약속 ​

eventual consistency는 "새 쓰기가 멈추면 언젠가는 모든 복제본이 같은 값으로 수렴한다"는 것만 약속한다. 수렴 전에 무엇을 읽을 수 있는지에 대해서는 아무 말도 하지 않는다 — 오래된 값, 순서가 뒤바뀐 값, 심지어 (다중 리더의 충돌이 해결되지 않았다면) 서로 다른 값이 노드마다 보일 수 있다.

모델순서 보장실시간 순서와의 관계파티션 중 가용성
linearizability모든 연산에 전역 순서반드시 일치불가(뒤에서 증명)
sequential consistency모든 연산에 전역 순서무관사실상 불가(전역 조율 필요)
causal consistency인과관계 있는 연산만 순서무관가능
eventual consistency없음(수렴만 약속)무관가능

클라이언트 중심 보장 — 세션 위에 얹는 안전장치 ​

약한 모델을 그대로 쓰면 같은 사용자에게도 "방금 쓴 글이 사라졌다가 다시 나타나는" 경험을 줄 수 있다. Terry 외(1994)가 정리한 세션 보장은 이 문제를 사용자 세션 단위로 좁혀서 해결한다.

  • read-your-writes: 자신이 쓴 값 이후의 상태만 읽는다.
  • monotonic reads: 한 세션의 연속된 읽기가 과거로 되돌아가지 않는다.
  • monotonic writes: 한 세션의 쓰기가 그 세션이 이전에 낸 쓰기보다 먼저 적용되지 않는다.
  • writes-follow-reads: 어떤 값을 읽은 뒤의 쓰기는, 그 값을 만든 쓰기보다 논리적으로 뒤에 온다(댓글이 원글보다 먼저 보이지 않는 것과 같은 요구를 쓰기 순서 쪽에서 보장).

챕터 11.6이 read replica 라우팅에서 구현한 read-your-writes·monotonic read가 바로 이 일반 이론의 DB 적용 사례다.

quorum 수학 — N, W, R ​

리더 없는 복제에서 "충분히 많은 노드가 응답했다"를 정량화하는 것이 정족수다. 전체 복제본 수를 N, 쓰기 성공에 필요한 응답 수를 W, 읽기에 조회하는 노드 수를 R이라 하면, 다음 조건일 때 모든 읽기 정족수와 모든 쓰기 정족수가 적어도 한 노드에서 겹친다.

text
W + R > N

N=3인 예로 확인하자. 쓰기가 노드 {1, 2}에 성공했다(W=2, 노드 3은 응답 없음). 읽기가 노드 {2, 3}을 조회하면(R=2) 노드 2에서 최신 값을 발견한다. 읽기가 {1, 3}을 조회해도 노드 1에서 발견한다. W=2, R=2, N=3이면 어떤 2곳을 골라도 서로 겹칠 수밖에 없다 — 비둘기집 원리다.

여기서 흔한 오해를 바로잡아야 한다. W + R > N은 정상 상황에서 오래된 값을 읽을 확률을 낮추는 조건이지, linearizability를 보장하는 조건이 아니다. 다음 경우들이 겹침만으로는 막히지 않는다.

  • 동시 쓰기: 두 클라이언트가 같은 키에 거의 동시에 쓰면 "어느 것이 최신인가"가 애초에 정의되지 않는다. 물리 시계로 승자를 정하는 LWW(last-write-wins)는 10.1에서 본 시계 어긋남 때문에 실제로는 늦게 쓴 값이 조용히 버려질 수 있다.
  • 쓰기와 동시에 일어나는 읽기: 쓰기가 진행 중일 때 읽으면 정족수 겹침이 성립해도 읽기가 새 값과 헌 값 중 어느 쪽을 볼지는 타이밍에 달려 있다.
  • sloppy quorum: 지정된 N개 노드 중 일부가 응답하지 않으면 임시로 다른 노드가 대신 쓰기를 받아들이고(hinted handoff), 나중에 원래 노드로 전달한다. 이 창 동안에는 "쓰기를 받은 노드 집합"과 "지정된 N개"가 겹치지 않을 수 있어 기하학적 보장 자체가 깨진다.

결론은 이렇다. quorum 겹침은 확률적으로 오래된 읽기를 줄이는 실용적 장치이지, 합의 수준의 안전성 증명이 아니다. 진짜 linearizability가 필요하다면 10.1의 합의에 기반한 단일 리더 구조가 필요하고, quorum 기반 시스템은 대개 causal consistency나 그보다 약한 보장을 목표로 설계된다.

네트워크 파티션 — 정의부터 정확히 ​

다음 절의 CAP를 다루기 전에 "파티션"이 무엇을 뜻하는지 정의해야 한다. 네트워크 파티션은 노드 집합이 둘 이상의 그룹으로 나뉘어 그룹 사이의 메시지가 전달되지 않거나 임의로 지연되는 상태다. 완전히 끊길 수도, 일부 쌍만 영향을 받을 수도 있다. 10.1의 언어로 옮기면, 파티션은 부분 동기성 가정이 그 지속 시간 동안 깨지는 구간이다 — 메시지가 얼마나 지연될지 상한을 잃는다는 점에서 완전 비동기 모델과 같아진다.

이 개념을 데이터를 여러 노드에 나눠 배치하는 **데이터 파티셔닝(샤딩)**과 혼동하지 않아야 한다. 이름은 같지만 하나는 장애(네트워크가 갈라지는 사건), 하나는 설계 결정(데이터를 어떻게 나눠 저장할지)이다. 데이터를 여러 shard로 나누는 결정은 챕터 11.7이 다루며, 이 문서에서 "파티션"은 항상 네트워크 장애를 가리킨다.

CAP 정리의 정확한 의미 ​

Brewer(2000)가 처음 제시하고 Gilbert & Lynch(2002)가 형식화한 CAP 정리는 다음을 증명한다.

네트워크 파티션이 존재하는 동안, 분산 데이터 저장소는 Consistency(여기서는 정확히 linearizability를 뜻한다)와 Availability(장애가 없는 모든 노드는 모든 요청에 응답해야 한다)를 동시에 만족할 수 없다.

증명은 직관적이다. 노드 집합이 G1, G2로 갈라졌다고 하자. 클라이언트가 G1의 한 노드에 값 v를 쓴다. 곧이어 다른 클라이언트가 G2의 한 노드에서 같은 키를 읽는다.

text
G1 ─── v 쓰기 성공 ───▶ (G2와 통신 불가)
G2 ─── 같은 키 읽기 요청

G2의 노드가 선택할 수 있는 것은 둘뿐이다.
(a) 응답한다 → v를 모르므로 오래된 값을 반환 → linearizability 위반(Consistency 상실)
(b) v를 알 때까지 응답을 미룬다 → 요청한 클라이언트는 응답을 못 받음 → Availability 상실

G2가 G1과 통신할 수 없는 한 이 선택을 피할 수 없다. 파티션이 일어나는 동안에는 C 또는 A 중 하나를 반드시 포기해야 한다는 것이 정리의 전부다.

"3개 중 2개를 고른다"는 표현이 오해인 이유 ​

CAP를 "Consistency, Availability, Partition tolerance 중 2개를 고르라"는 3지선다로 설명하는 자료가 많지만, 이 표현은 원 저자 스스로 문제로 지적했다(Brewer, "CAP Twelve Years Later", 2012). 파티션은 설계자가 "포기"할 수 있는 선택지가 아니다 — 네트워크는 물리적으로 파티션이 일어나며, 이를 견디지 않는 시스템은 파티션이 실제로 일어나는 순간 완전히 멈춘다. 진짜 선택은 "파티션이 일어났을 때 C를 지킬 것인가, A를 지킬 것인가"이며, 파티션이 없는 평상시에는 C와 A를 동시에 가질 수 있다.

그래서 시스템을 "CP" 또는 "AP"로 분류하는 것은 파티션 중의 동작을 가리키는 것이지 상시 동작을 가리키는 게 아니다.

  • CP: 파티션 중 소수 그룹은 요청을 거부하거나 응답을 미룬다. 10.1의 Raft가 소수 파티션에서 쓰기를 확정하지 못하는 동작이 정확히 이것이다.
  • AP: 파티션 중에도 모든 그룹이 응답하되, 값이 서로 갈라질 수 있다(eventual consistency로 사후 수렴). 앞서 본 leaderless quorum 시스템의 sloppy quorum이 이 선택이다.

CAP의 "C"는 ACID의 "C"가 아니다 ​

용어 충돌에 주의해야 한다. CAP의 Consistency는 linearizability라는 구체적이고 좁은 정의다. ACID의 Consistency는 애플리케이션이 정의한 불변식(제약 조건)이 트랜잭션 전후에 유지된다는, 전혀 다른 개념이다. "이 시스템은 AP라서 ACID를 지원하지 않는다" 같은 문장은 두 C를 섞은 오류다 — AP 시스템도 각 노드 로컬에서는 자신의 불변식을 지킬 수 있고, CP 시스템도 애플리케이션 불변식을 스스로 어길 수 있다.

PACELC — 파티션이 없을 때의 진짜 트레이드오프 ​

Abadi(2012)는 CAP가 파티션이라는 예외 상황만 다룬다는 점을 지적하며 이를 확장했다. PACELC: 파티션(P)이 있으면 Availability와 Consistency 중 선택해야 하고, 그렇지 않은 평상시(Else, E)에도 Latency와 Consistency 사이의 트레이드오프가 상존한다. 강한 일관성을 지키려면 쓰기가 여러 노드의 확인을 기다려야 하고, 그 대기 시간이 지연으로 나타난다. 파티션은 드물게 일어나지만 지연-일관성 트레이드오프는 매 요청마다 발생하므로, 실무 설계에서 더 자주 마주치는 축은 사실 CAP의 P가 아니라 PACELC의 E다.

실무 관점 ​

"AP 시스템은 일관성이 없다"는 오해 ​

AP는 linearizability를 포기한다는 뜻이지 아무 보장도 없다는 뜻이 아니다. eventual consistency 위에 세션 보장(read-your-writes 등)이나 causal consistency를 얹어 대부분의 사용자 경험 문제를 해결하는 것이 일반적인 설계다. "결국은 맞아진다"와 "아무 순서도 없다"를 같은 것으로 취급하지 않는다.

"CP를 선택하면 항상 안전하다"는 오해 ​

CP 시스템도 10.1이 짚은 것처럼 소수 파티션에서 스스로 멈출 뿐, fencing이 빠진 구현이라면 옛 리더가 여전히 응답하는 사고가 날 수 있다. "CP라고 표시된 제품"과 "실제로 과반 기반 안전성을 올바르게 구현한 제품"은 다른 이야기이며, 검증은 여전히 필요하다.

마케팅 문구가 아니라 파티션 중 동작을 묻는다 ​

벤더 문서의 "강한 일관성 지원"이라는 문구는 평상시 동작을 말하는 경우가 많다. 판단에 필요한 질문은 하나다 — "네트워크가 갈라지면 이 시스템은 무엇을 포기하는가?" 이 질문에 구체적으로 답하지 못하는 설명은 CAP를 실제로 검증하지 않은 것이다.

정리 ​

  • 복제는 지연 있는 전파 과정이며, 일관성 모델은 그 지연 동안 무엇을 보여줄지 정하는 계약이다.
  • 단일 리더·복수 리더·리더 없는 복제는 안전성의 원천(합의, 사후 병합, 정족수 중첩)과 가용성 특성이 서로 다르다.
  • linearizability부터 eventual consistency까지는 순서 보장의 강도가 다르며, causal consistency는 항상 가용한 시스템이 달성할 수 있는 가장 강한 모델이다.
  • W + R > N은 오래된 읽기를 줄이는 실용적 장치이지 linearizability의 증명이 아니다. 동시 쓰기, 동시 읽기, sloppy quorum이 겹침의 보장을 무너뜨릴 수 있다.
  • CAP 정리는 파티션 중 C와 A 중 하나를 포기해야 한다는 뜻이며, 평상시에는 둘 다 가질 수 있다. "3개 중 2개 선택"이라는 통념은 파티션이 선택 사항이 아니라는 점에서 오독이다. PACELC가 파티션이 없을 때의 지연-일관성 트레이드오프를 마저 채운다.

확인 문제 ​

1. N=5, W=3, R=2로 설정된 quorum 시스템이 있다. 이 설정이 항상 linearizable 읽기를 보장하는지 판정하고, 근거를 제시하라.

정답과 해설

W + R = 5 = N이므로 항상 겹친다는 보장(W+R > N)이 성립하지 않는다 — 쓰기 정족수 3곳과 읽기 정족수 2곳을 겹치지 않게 고를 수 있다(5개 중 3개와 나머지 2개). 설령 W+R > N으로 바꾸더라도 linearizability는 보장되지 않는다. 동시 쓰기의 순서 정의, 쓰기와 동시에 일어나는 읽기, sloppy quorum 사용 여부를 추가로 확인해야 한다.

2. 어떤 팀이 "우리 시스템은 CAP에서 C와 A를 모두 만족하므로 CAP 정리의 예외"라고 주장한다. 이 주장을 평가하라.

정답과 해설

평상시(파티션이 없는 동안)에는 C와 A를 동시에 만족하는 것이 당연하며 CAP 정리와 모순되지 않는다 — CAP는 파티션이 일어나는 동안의 선택을 다룬다. 진짜 확인할 질문은 "이 시스템이 파티션 중에 무엇을 하는가"이다. 파티션 중에도 두 속성을 모두 유지한다고 주장한다면, 정리의 증명(겹치지 않는 두 그룹에 대한 쓰기·읽기 요청 시나리오)에 구체적으로 어떻게 대응하는지 제시해야 하며, 그렇지 못하면 파티션을 경험한 적이 없어 검증되지 않았을 가능성이 크다.

3. 다중 리전 서비스가 서울과 프랑크푸르트 리전에 각각 로컬 리더를 두고 비동기로 서로 전파한다. 같은 사용자 프로필의 "자기소개" 필드를 두 리전에서 거의 동시에 수정했다. LWW로 충돌을 해결하는 설계의 위험을 10.1의 개념과 연결해 설명하라.

정답과 해설

LWW는 각 쓰기에 물리 타임스탬프를 붙이고 더 큰 값을 승자로 선택한다. 그런데 10.1에서 본 것처럼 리전 간 물리 시계는 정확히 맞지 않는다. 실제로는 나중에 발생한 수정이 시계 오차 때문에 더 이른 타임스탬프를 받으면 조용히 버려질 수 있다 — 사용자에게 어떤 오류도 보이지 않은 채 데이터가 소실된다. 논리 시계나 vector clock으로 인과관계를 확인하거나(이 경우 두 쓰기는 인과관계 없는 동시 쓰기이므로 자동 병합이 불가능함을 인지), 최소한 두 값을 모두 보존해 애플리케이션이나 사용자가 병합을 선택하게 하는 설계가 더 안전하다.

4. "causal consistency는 eventual consistency보다 강하지만 linearizability만큼 비용이 크지는 않다"는 문장의 근거를 이 문서의 개념으로 설명하라.

정답과 해설

causal consistency는 인과관계(happens-before)가 있는 연산의 순서만 지키면 되고 동시 연산은 노드마다 다른 순서로 봐도 무방하다. 반면 linearizability는 모든 연산(동시 연산 포함)에 대해 실시간 순서와 일치하는 전역 순서를 요구하므로 사실상 매 연산마다 전역 조율이 필요하다. causal consistency는 인과관계 있는 연산에 대해서만 좁혀서 조율하면 되므로 비용이 낮고, 파티션 중에도 가용성을 유지할 수 있는 가장 강한 모델로 알려져 있다. eventual consistency보다는 강한 이유는 최소한 인과관계는 지킨다는 보장이 추가되기 때문이다.

참고 자료 ​