TT Lab

한국어 English 日本語

시작하기
블로그

블로그

분산 시스템의 본질적 어려움 — CAP, PACELC, Raft/Paxos, Vector Clock, Saga, Event Sourcing 완벽 정리 (2025)

2026-04-15 · 29 분 읽기 · #distributed-systems#cap-theorem#pacelc#raft#paxos#vector-clock#lamport-clock#saga-pattern#event-sourcing#spanner#cockroachdb#consensus

왜 지금 분산 시스템인가 — 2025년, 더는 피할 수 없다

2015년까지만 해도 "분산 시스템은 Netflix나 Google이 하는 것"이었다. 2026년, 스타트업 3명도 분산 시스템을 다룬다.

결론: 분산 시스템은 더 이상 '선택'이 아니라 '조건'이다. 그런데 업계에서 가장 많이 오해되는 주제이기도 하다. "우린 CP를 택했어요"라는 말이 얼마나 공허한지, 이 글을 다 읽으면 알게 된다.

Part 1 — 왜 분산은 본질적으로 어려운가

8가지 분산의 거짓말 (The Fallacies of Distributed Computing)

1994년 Peter Deutsch(당시 Sun)가 정리한 목록. 30년이 지난 지금도 유효하다.

  1. 네트워크는 신뢰할 수 있다 — 패킷은 사라진다.
  2. 지연시간은 0이다 — 빛의 속도는 유한하다(뉴욕-시드니 RTT 약 200ms).
  3. 대역폭은 무한하다 — 모든 데이터를 다 보낼 수는 없다.
  4. 네트워크는 안전하다 — MITM, DNS 하이재킹, BGP 하이재킹이 실제로 일어난다.
  5. 토폴로지는 변하지 않는다 — 노드는 죽고, 이동하고, 생성된다.
  6. 관리자는 한 명이다 — 여러 조직이 시스템을 공유한다.
  7. 전송 비용은 0이다 — 클라우드 egress 비용이 증명한다.
  8. 네트워크는 균질적이다 — TCP/IP라는 공통 껍질 아래 이더넷, WiFi, 위성, 5G가 뒤섞인다.

분산 시스템 논문의 99%는 "이 8가지가 거짓이라서" 생긴 문제를 다룬다.

두 프로세스가 '동시'를 합의할 수 없다

단일 머신에서 now()는 명확하다. 두 머신에서? 근본적으로 불확실하다.

이 때문에 분산 시스템에서 '사건의 순서'는 절대시간이 아닌 논리시간으로 결정된다. Lamport(1978)의 통찰이었다.

Part 2 — CAP 정리를 다시 읽기

원래 정의 (Brewer, 2000 / Gilbert & Lynch, 2002)

"네트워크 파티션(P) 상황에서, 시스템은 Consistency(C)와 Availability(A) 중 하나만 보장할 수 있다."

핵심 오해 3가지:

오해 1: "CP냐 AP냐 택한다"

틀렸다. 파티션이 없는 평시에는 C와 A 모두 만족 가능하다. CAP는 오로지 "파티션 발생 시 트레이드오프"를 말한다. Eric Brewer 본인이 2012년 "CAP Twelve Years Later" 에서 해명했다.

"The 'two of three' formulation was always misleading. In reality, the 'choice' is only relevant during partitions."

오해 2: "Consistency = ACID의 C"

틀렸다. CAP의 C는 Linearizability(단일 객체, 단일 연산 기준으로 '한 번에 일어난 것처럼' 보이는 것)다. ACID의 C는 '제약조건 위반 없음'이라는 전혀 다른 개념이다.

오해 3: "Availability = 서비스가 안 죽는 것"

틀렸다. CAP의 A는 '모든 요청이 에러가 아닌 응답을 받는다'는 매우 엄격한 정의다. 99.99% 가용성과는 다르다.

PACELC — CAP가 놓친 것

2010년 Daniel Abadi가 제안. "Partition 시 A vs C, Else(평상시) Latency vs Consistency."

시스템파티션 시평상시
DynamoDB (기본)PAEL (짧은 지연, 약한 일관성)
CassandraPAEL
MongoDBPA/PC (설정)EC
HBasePCEC
PostgreSQL (단일)해당 없음EC
SpannerPCEC (TrueTime으로 L도 상쇄)

PACELC가 중요한 이유: 평상시 시스템이 어떻게 동작하는지가 사용자 경험의 99.9%를 차지한다. CAP만 보고 "우린 CP"라고 답하는 건 하루 중 99.99%를 설명 못 한다.

Consistency Models 스펙트럼

강한 순서:

  1. Linearizable (Strong) — 외부 관찰자 입장에서 단일 머신처럼 보임. 비용 최고.
  2. Sequential — 모든 프로세스가 같은 순서로 본다, 단 실시간 순서는 보장 X.
  3. Causal — 인과관계 있는 이벤트만 순서 보장. (Vector Clock 기반)
  4. Read-Your-Writes — 내가 쓴 건 내가 즉시 읽을 수 있다.
  5. Monotonic Reads — 한 번 본 값보다 '과거' 값은 다시 안 본다.
  6. Eventual — 충분히 기다리면 수렴한다.

2025년 현실: 대부분의 앱은 Linearizable까지 필요 없고, Causal + Read-Your-Writes 조합이면 충분하다. 그런데도 "Strong Consistency" 마케팅에 속아 Linearizable을 요구했다가 비용을 못 감당하는 사례가 많다.

Part 3 — 시간과 순서 — Lamport부터 HLC까지

Lamport Clock (1978)

Leslie Lamport의 "Time, Clocks, and the Ordering of Events in a Distributed System." 분산 컴퓨팅 역사에서 가장 중요한 논문.

1. 각 노드는 단조 증가하는 로컬 카운터 L을 유지한다.
2. 로컬 이벤트: L = L + 1
3. 메시지 송신: L = L + 1, 메시지에 L 첨부
4. 메시지 수신: L = max(L_local, L_message) + 1

한계: Happens-Before 관계를 부분적으로만 포착. a < b여도 실제 인과관계가 없을 수 있다(Total Order는 주지만 Causal Order는 X).

Vector Clock (Fidge, Mattern 1988)

각 노드가 모든 노드의 카운터를 벡터로 유지.

노드 A: [A=3, B=1, C=0]
노드 B: [A=2, B=4, C=0]

A에서 B로 메시지 송신 시 A의 벡터 첨부.
B는 수신 후 max(자기, 메시지)로 업데이트.

두 벡터 V1, V2 비교:
- V1 ≤ V2 (모든 원소): V1 happens-before V2
- 둘 다 아니면: concurrent(동시)

DynamoDB 초창기, Riak, Cassandra의 conflict detection에 사용. 단점: 노드 수 증가 시 벡터 크기 비례 증가.

HLC — Hybrid Logical Clock (2014)

물리시간 + 논리시간 하이브리드. CockroachDB, MongoDB 4.0+, YugabyteDB 내부 시계.

(wall_time, logical_counter)

- wall_time: 물리 시계 값
- logical_counter: 동일 wall_time 내 순서

장점: NTP 드리프트에도 안전 + 인간이 읽을 수 있는 타임스탬프 + Causal Order.

TrueTime — Google Spanner의 비밀 병기 (2012)

원자시계 + GPS를 데이터센터마다 배치. API는 이렇게 생겼다.

TT.now() → { earliest: t1, latest: t2 }  # 불확실 구간 반환
TT.after(t) → t가 이미 과거인가?
TT.before(t) → t가 아직 미래인가?

Spanner가 커밋할 때:

1. 커밋 타임스탬프 s 선택 (TT.now().latest 이후 값)
2. s가 '확실히 과거'가 될 때까지 대기(commit wait) — 보통 7ms 이하
3. 응답 반환

이 "commit wait" 덕분에 전 세계 데이터센터에 걸친 외부 일관성(External Consistency)을 달성한다. 하드웨어(원자시계)에 의존하는 유일한 프로덕션 분산 DB.

2017년 Amazon Time Sync + 2022년 PTP(Precision Time Protocol) 보급으로 TrueTime급 정밀도가 클라우드에서 가능해졌다. AWS는 2023년 μs 정밀도 TimeSync를 공개.

Part 4 — 합의(Consensus) — Paxos와 Raft

FLP Impossibility (1985)

Fischer, Lynch, Paterson: 비동기 네트워크 + 한 프로세스라도 죽을 수 있음 → 결정적(deterministic) 합의 알고리즘 불가능.

분산 시스템 이론의 가장 유명한 불가능성 정리. "그럼 어떻게 Paxos/Raft가 동작하는가?" 답: 타임아웃(무기한 진행 포기) + 랜덤화로 우회. 100% 결정적이진 않지만, 실용적으로 수렴한다.

Paxos (Lamport, 1989년 제출, 1998년 출판)

Leslie Lamport의 "The Part-Time Parliament." 그리스 섬의 의회 비유로 썼다가 리뷰어들에게 욕먹고 9년 출판 지연. 1998년 출판 후에도 "이해 불가"라는 악명.

핵심 역할:

2-phase:

Phase 1 (Prepare):
  Proposer → 모든 Acceptor: "제안번호 n을 받을래?"
  Acceptor → Proposer: "n이 이전 어떤 것보다 크면 수락. 이전 수락값 반환."

Phase 2 (Accept):
  Proposer → Acceptor: "값 v로 제안번호 n을 수락해줘"
  (v는 Phase 1에서 본 가장 최근 수락값 또는 제안자 선택)
  Acceptor → Proposer: "수락/거부"

과반수 수락 시 값 확정.

악명의 원인:

  1. Multi-Paxos, Fast Paxos, Generalized Paxos 등 변종 과다.
  2. 논문의 설명 스타일이 공학자 친화적이지 않음.
  3. 구현 시 발생하는 엣지 케이스가 논문에 명시 X.

Google Chubby, Apache ZooKeeper의 초기 버전, Megastore, Spanner 등에서 사용.

Raft (Ongaro & Ousterhout, 2014)

스탠퍼드 박사과정 Diego Ongaro가 "Paxos가 너무 어려워서" 만든 합의 알고리즘. 논문 제목이 "In Search of an Understandable Consensus Algorithm"이다.

3개의 서브 문제로 분해:

1. Leader Election (리더 선출)

2. Log Replication (로그 복제)

3. Safety (안전성)

Raft를 쓰는 시스템:

Paxos는 "검증된 이론", Raft는 "실전 엔지니어링." 2020년대 신규 시스템의 90%가 Raft.

EPaxos, Multi-Paxos, Flexible Paxos

Part 5 — 트랜잭션 — 2PC, 3PC, Saga

2PC (Two-Phase Commit)

가장 단순하고 가장 위험한 트랜잭션 프로토콜.

Phase 1 (Prepare):
  Coordinator → Participants: "커밋 가능?"
  Participants → Coordinator: "Yes / No"

Phase 2 (Commit):
  모두 Yes → Coordinator: "Commit!"
  하나라도 No → Coordinator: "Abort!"

치명적 단점: Coordinator가 Phase 2 직전에 죽으면 참가자들이 블로킹된다. 수동 개입 없이는 복구 불가. 실무에서 2PC를 프로덕션에 쓰는 곳은 XA 트랜잭션 기반 레거시(DB2, Oracle RAC) 정도.

3PC (Three-Phase Commit)

Phase를 추가해 블로킹 회피 시도. 그러나 네트워크 파티션에서는 여전히 불일치 가능. 실무에서 거의 안 쓴다.

Saga Pattern (Garcia-Molina & Salem, 1987)

긴 트랜잭션을 여러 로컬 트랜잭션 + 각각의 보상 트랜잭션으로 분해.

주문 → 결제 → 재고 차감 → 배송

실패 시 역순 보상:
배송 실패 → 재고 복구 → 결제 환불 → 주문 취소

두 종류:

2020년대 주류:

Saga의 한계: Isolation이 없다. 중간 상태가 외부에 노출된다. "의미적 잠금(semantic lock)"으로 보완하지만 완벽하지 않다.

TCC (Try-Confirm-Cancel)

중국 Alibaba가 마이크로서비스 트랜잭션에 사용. Saga와 비슷하지만 리소스 예약(Try) + 확정(Confirm) / 취소(Cancel) 3단계.

Part 6 — Event Sourcing + CQRS

Event Sourcing

"상태가 아니라 이벤트의 연속을 저장한다."

[현재 상태: 잔고 $100]  ← 전통 방식

[이벤트: +$50, -$20, +$70]  ← Event Sourcing
→ 재생하면 $100

장점:

단점:

CQRS (Command Query Responsibility Segregation)

쓰기 모델과 읽기 모델을 물리적으로 분리.

Command → Write Model (Event Store) → Event 발행
                  ↓
                  → Read Model (Materialized View)
                  → Read Model (ElasticSearch)
                  → Read Model (Redis)

Query → Read Model들

강력하지만 복잡도 폭발. 간단한 CRUD에 CQRS를 도입하면 유지보수 비용이 폭증한다.

2024년 주류 구현:

Outbox Pattern — Exactly-Once의 비밀

"DB 커밋 + 메시지 발행"을 원자적으로 하려면?

순진한 방법(틀림):

1. DB 커밋
2. Kafka 발행

2번 실패 시 상태 불일치. 반대로 해도 마찬가지.

Outbox Pattern (정답):

BEGIN;
  INSERT INTO orders (...);
  INSERT INTO outbox (event_type, payload) VALUES (...);
COMMIT;

-- 별도 프로세스가 outbox 테이블을 폴링해서 Kafka에 발행
-- 발행 성공 시 outbox 행 삭제 or 플래그 업데이트

Debezium (Kafka Connect CDC)이 이를 자동화한다. PostgreSQL WAL → Kafka로 실시간 스트리밍.

Part 7 — Exactly-Once Semantics — 존재하는가

"정확히 한 번"의 3가지 의미

  1. 메시지 전송 ExO: 네트워크상 절대 불가(Two Generals Problem).
  2. 메시지 처리 ExO: 중복 감지 + 멱등성으로 가능.
  3. 최종 효과 ExO: 소비자 쪽 멱등성이 관건.

At-Least-Once + Idempotency = 실질적 Exactly-Once

Kafka 공식 가이드라인. 프로듀서가 중복 보낼 수 있다고 가정하고, 컨슈머를 멱등하게 설계하면 효과는 Exactly-Once.

멱등성 구현:

-- Upsert 방식
INSERT INTO processed_events (event_id, result)
VALUES ('evt-123', ...)
ON CONFLICT (event_id) DO NOTHING;

Kafka의 Transactional Producer (2017+)

producer.initTransactions();
producer.beginTransaction();
producer.send(record1);
producer.send(record2);
producer.commitTransaction();  // 모두 or 아무도

파티션·오프셋 원자적 커밋 + Consumer의 isolation.level=read_committed 설정 시 Exactly-Once. 단, 프로듀서·컨슈머·Kafka 브로커 모두에서 설정이 일치해야 한다.

Part 8 — 실전 분산 DB — Spanner, CockroachDB, TiDB, YugabyteDB

Google Spanner

CockroachDB (2015)

"Spanner를 오픈소스로." 전 Google 엔지니어들이 창업.

2022년 라이선스를 BSL로 변경해 커뮤니티 일부 반발. 2024년 Series F $278M 이후 프로덕션 채택 급증.

TiDB (PingCAP, 2016)

중국 PingCAP 창업.

2024년 PingCAP 매출 $100M 돌파. 아시아권에서 매우 강력한 채택률.

YugabyteDB (2016)

전 Facebook/Nutanix 출신.

Part 9 — 스트리밍의 분산 — Kafka, Pulsar, Redpanda

Kafka

Pulsar (Apache, Yahoo 2016 기증)

Redpanda (2019)

Part 10 — 실제 장애 사례

1. Roblox 73시간 장애 (2021년 10월)

원인: Consul의 BoltDB가 writeback contention으로 쓰기 지연 → 리더 선출 불가능 → 전체 장애. 교훈: 키-밸류 스토어의 백그라운드 compaction이 합의에 영향을 미친다.

2. GitLab 데이터 손실 (2017년 1월)

원인: 엔지니어가 실수로 primary에서 rm -rf 실행. 5개 백업 모두 작동 안 함(설정 오류/크기 0/오래됨). 교훈: "백업이 있다"가 아니라 "복구가 검증됐다"가 중요.

3. Knight Capital 45분 $440M 손실 (2012)

원인: 배포 중 8개 서버 중 1개에만 새 코드 적용. 다른 코드가 실행되면서 무한 매수 주문. 교훈: 배포의 원자성 부재 = 분산 불일치 = 경제적 재앙.

4. Cloudflare 2022 Regex 장애

원인: 정규식 하나가 CPU 100% 점유 → 전 엣지 다운. 교훈: 분산 시스템의 가용성은 최약한 링크의 원자적 영향 반경이 결정한다.

5. AWS us-east-1 DynamoDB 2015 장애

원인: 메타데이터 서비스 과부하 → 테이블 리스트 조회 실패 → 종속 서비스 연쇄 실패. 교훈: "모든 것을 서비스로"는 단일 장애점의 분산된 버전이 되기 쉽다.

Part 11 — 실무 체크리스트 (12항목)

  1. CAP가 아니라 PACELC로 말하라 — 평상시 동작이 99.99%다.
  2. Exactly-Once는 신화다 — At-Least-Once + Idempotency를 설계하라.
  3. 시계를 믿지 마라 — HLC 또는 TrueTime 기반 DB를 쓰거나, 직접 Lamport Clock을 고려.
  4. 2PC를 새로 도입하지 마라 — Saga 또는 Outbox Pattern.
  5. 합의가 필요하면 Raft — 직접 구현하지 말고 etcd/Consul/검증된 라이브러리.
  6. 리더 선출에 의존하는 시스템은 "리더가 없는 동안"을 설계해야 한다.
  7. 쿼럼 크기를 이해하라 — N=3 클러스터는 1대만 고장 허용.
  8. 재시도에는 반드시 지수 백오프 + Jitter. 재시도 폭주가 장애를 키운다.
  9. 분산 캐시 무효화를 설계 단계에서 해결하라. 나중에 붙이면 지옥.
  10. 모니터링 없이 분산 X — 분산 추적, 메트릭, 로그 3종 세트 필수.
  11. Chaos Engineering을 도입하라 — 네트워크 파티션을 일부러 만들어 동작 검증.
  12. 데이터 복구를 정기 훈련하라 — GitLab 사례는 매년 일어날 수 있다.

Part 12 — 10대 안티패턴

  1. "CP를 택했어요"라고 말하기 — CAP를 오해한 증거.
  2. 단일 조정자(Coordinator)에 의존 — SPOF 보장.
  3. 분산 락으로 비즈니스 로직 보호 — 대부분 멱등성으로 해결 가능.
  4. 로컬 시계로 순서 결정 — NTP 드리프트가 버그의 원인.
  5. 트랜잭션을 마이크로서비스 경계 넘기기 — Saga나 Outbox로 재설계.
  6. 재시도에 타임아웃 없음 — 재시도 폭발로 장애 확장.
  7. 분산 모놀리스 — 서비스는 많지만 모두가 얽혀 함께 배포.
  8. 로컬에서만 테스트하고 프로덕션에 기대 — 분산 버그는 지연시간에서 나온다.
  9. Single Leader 데이터베이스를 수평 확장이라고 부르기 — Read Replica는 확장이 아닌 분산 읽기.
  10. "어차피 eventual consistency니까"로 모든 불일치 합리화 — 사용자는 "eventual"을 이해하지 못한다.

Part 13 — 학습 리소스

마치며 — 분산 시스템은 '철학'이다

Lamport의 유명한 정의:

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

분산 시스템은 "완벽히 통제되지 않는 세계에서, 충분히 신뢰할 수 있는 결과를 만들어내는 기술"이다. 완벽은 없다. 오직 타협만 있다. 그러나 그 타협을 명시적·의식적으로 한다면, 우리는 무한에 가까운 규모를 다룰 수 있다.

2025년의 엔지니어에게 분산 시스템 지식은 더 이상 선택이 아니다. 당신이 작성하는 모든 코드는 이미 분산 환경에 있다. 단, 대부분은 그 사실을 깨닫지 못할 뿐이다.

다음 글 예고 — "데이터베이스 내부 구조 완전 해부" — B-Tree, LSM, WAL, MVCC, Vacuum, Replication, Index 성능의 비밀

이 시리즈는 분산 '위'의 이야기였다. 다음은 분산 '아래' — 단일 DB의 심장부다.

"왜 DB는 느려지는가?"에 대한 완전한 답이다. — 다음 글에서.

로그인하면 좋아요를 누를 수 있습니다

댓글

아직 댓글이 없습니다.

로그인하면 댓글을 쓸 수 있습니다