요즘 개발자를 위한 시스템 설계 수업 - 3장 분산 시스템의 이론과 데이터 구조 1

3장 분산 시스템의 이론과 데이터 구조

3.1 CAP 정리

분산 환경에서 네트워크 분할(Partition)은 피할 수 없는 물리적 현실

Partition Tolerance(P)는 선택 옵션이 아니라 전제 조건입니다. 따라서 실질적인 선택은 CP(일관성 중심) vs AP(가용성 중심)의 양자택일 문제

 

일관성을 유지하는 것

모든 노드가 동일한 데이터 상태를 유지하지만 일부 노드는 요청을 처리하지 못할 수 있음

가용성을 유지하는 것

모든 노드가 독립적으로 요청을 처리할 수 있지만 서로 다른 데이터 상태를 가질 수 있음

3.2 PACELC 정리

장애 상황(Partition)에서는 가용성(A)과 일관성(C)을 저울질하고, 평상시(Else)에는 지연 시간(L)과 일관성(C)을 저울질한다

PAC (The Failure Mode - 장애 상황 - 기존 CAP)

Partition이 발생하면 (네트워크 단절 시) Availability (가용성)와 Consistency (일관성) 중 하나를 선택해야 한다.

ELC (The Normal Mode - 정상 상황 - 신규 상황)

Else (만약 네트워크가 정상이라면) Latency (지연 시간)와 Consistency (일관성) 중 하나를 선택해야 한다.

 

전략 유형	설명	대표 기술	적합한 사례
PA / EL	무조건 살리고 본다, 무조건 빠르다	DynamoDB, Cassandra, Riak	SNS 피드, 장바구니, 로그 수집 사용자는 사소한 데이터 틀어짐보다 느린 것을 더 못참는다.
PC / EC	죽을지언정 거짓말은 안 한다,  느려도 정확하다	HBase, BigTable, Voltdb, CockroachDB	금융 거래, 재고 관리, 결제 원장 결제 정보는 일관성이 조금이라도 틀어질 경우 법적 책임까지 간다.
PA /EC	장애 시엔 살리지만, 평소엔 정확하게	MongoDB (Tunable)	특이 케이스로 적합한 사례가 없
PC /EL	장애 시엔 멈추지만, 평소엔 빠르다	Redis (Standalone)	단순 캐싱 데이터가 사라져도 문제 없는 고속 캐시 용도

정상 상태(Else)에서 Latency(L)와 Consistency(C) 사이의 물리적 트레이드오프가 복제(Replication) 아키텍처에서 어떻게 발현되는지

합의

분산 시스템에서 서로 다른 서버들이 동일한 상태나 결정을 유지하도록 하는 과정

시스템의 안정성과 신뢰성에 영향

3.2.1 팩소스 알고리즘(paxos)

분산 환경에서 여러 노드가 '동일한 데이터'를 가지게 하려면 단순한 복제로는 부족, 두 클라이언트가 동시에 다른 노드에 쓰기를 요청했을 때, 누가 먼저인가를 결정하는 '합의(Consensus)'가 필요

팩소스는 Proposer(제안자), Acceptor(수용자), Learner(학습자)라는 역할을 분리하여 과반수(Quorum)의 동의를 얻어내는 완벽한 수학적 증명

팩소스 알고리즘의 핵심 포인트

• 제안자(proposer)
  합의 프로세스 시작 역할 노드
  합의 값 제안, 제안 다른 노드 전파
• 수용자(acceptor)
  제안 받고, 제안 수용 여부를 다른 노드에 전파
• 학습자(learner)
  합의된 값을 최종적으로 받는 노드
  이 값 기반으로 후속 작업 수행

 

팩소스 알고리즘의 프로토콜 과정(2 Phase)

• Phase 1: Prepare (제안 권한 획득)
• Phase 2: Accept (값의 합의)

 

 

 

팩소스 고려 사항

• 장애 허용성
  일부 노드 작동하지 않는 경우 원활하게 동작할 것
• 확장성
  성능은 포함된 노드 개수에 영향을 받음, 많으면 노드 간 조율 비용 증가로 성능 하락
• 복잡성
  정교한 만큼 복잡하다, 즉, 구현 난이도가 높다

팩소스 알고리즘이 발전한 방향과 최적화 기법

• 멀티 팩소스
  리더 기반 동작, 제안 과정을 생략
• 패스트 팩소스
  낙관적인 상황을 가정하고, 리더가 있지만 누구나 제안을 한다, 충돌 시 리더가 중재
• 심플 팩소스
  학술적 목적의 개념 최적화에 가까움
  보통 Basic Paxos(단일 값 합의)를 지칭하며, Multi/Fast Paxos의 기초가 되는 원형을 의미합니다. 엔지니어들이 구현할 때 가장 먼저 참고해야 하는 레퍼런스 모델

프로토콜	리더(Leader) 의존도	최적 조건 시 지연 (Message Delay)	정족수 (Quorum Size, 노드 N=2f+1 가정)	핵심 메커니즘 (Mechanics) 및 한계
Simple / Basic	없음 (모두 Proposer)	4 Delays (2 RTT)	f+1 (과반수)	매번 Phase 1, 2 반복. Livelock 위험 높음. 학술용.
Multi-Paxos	필수 (강한 의존)	3 Delays (1 RTT)	f+1 (과반수)	Phase 1 생략. 현대 SMR의 표준. 리더 장애 시 일시적 가용성 저하.
Fast Paxos	약함 (충돌 해소용)	2 Delays	≈3f/2+1 (더 큼)	클라이언트가 직접 Acceptor에 전송. 동시 요청 시 충돌 복구 비용 막대함.

팩소스 알고리즘을 사용한 사례

• 분산 데이터베이스
• 분산 파일 시스템
• 상태 기계 복제

3.2.2 래프트 알고리즘

"인간이 이해할 수 없는 코드는 유지보수할 수 없고, 유지보수할 수 없는 분산 시스템은 결국 붕괴한다. 알고리즘의 최우선 가치는 성능이 아니라 '이해 가능성(Understandability)'이다." 

John Ousterhout (Raft 창시자)

 

합의 알고리즘

간단하고 직관적인 방법으로 구현 낮이도가 팩소스에 비해 상대적으로 낮음

 

비교 관점	Multi-Paxos	Raft	물리적 차이점 및 한계
디자인 철학	수학적 완벽성과 성능	이해 가능성(Understandability)	래프트는 구현의 파편화를 막기 위해 명세가 매우 구체적임.
리더십 (Leadership)	선택적 (최적화를 위한 도구)	필수적 (Strong Leader)	래프트는 리더 없이 아무것도 할 수 없음. 클라이언트 요청은 무조건 리더로 라우팅됨.
로그 구조 (Log Structure)	비순차적 커밋 허용 (Holes 발생)	엄격한 순차적 추가 (Append-Only)	래프트는 이전 로그가 일치하지 않으면 새 로그를 거부함(Log Matching Property).
리더 선출 방식	명확한 표준 없음	무작위 타이머 (Randomized Timers)	래프트는 스플릿 보트(Split Vote)를 피하기 위해 150~300ms의 무작위 타임아웃을 사용함.
주요 프로덕션 구현체	Google Spanner, Cassandra LWT	etcd (K8s), Consul, KRaft (Kafka)	팩소스는 사내 커스텀 엔진 중심, 래프트는 오픈소스 표준으로 자리잡음.

래프트 알고리즘의 핵심 포인트

• 리더(leader)
• 추종자(follower)
• 후보자(candidate)

 

팩소스는 '누구나 제안자(Proposer)가 될 수 있다'는 철학 때문에 두 노드가 동시에 다른 로그 인덱스에 데이터를 쓰는 아웃오브오더(Out-of-order) 커밋이 발생할 수 있음

래프트는 '오직 리더만이 로그를 추가(Append-only)할 수 있으며, 리더의 로그는 절대 덮어씌워지지 않는다'는 명백한 규칙으로 동작

래프트 알고리즘의 프로토콜 과정

• 리더 선출
• 로그 복제
• 안정성과 일관성

래프트 알고리즘에서 고려할 사항

• 리더 가용성
• 확장성
• 장애 허용성

래프트 알고리즘을 사용한 사례

• 분산 데이터베이스
• 분산 파일 시스템
• 클러스터 관리 및 서비스 디스커버리
• 합의 기반 알고리즘
• 클라우드 인프라 관리 시스템

 

래프트 알고리즘은 노드가 잘못 작동하거나 악의적으로 행동하는 등 복잡한 오류 상황까지는 다루지 못한다.