분산 시스템 개념 (Distributed Systems Concepts)
분산 시스템 개념 (Distributed Systems Concepts)¶
난이도: ⭐⭐⭐⭐
개요¶
분산 시스템은 네트워크로 연결된 여러 컴퓨터가 협력하여 하나의 시스템처럼 동작하는 것입니다. 이 장에서는 분산 시스템의 근본적인 도전과제, 시간 개념, 그리고 리더 선출 알고리즘에 대해 학습합니다.
목차¶
1. 분산 시스템의 8가지 오류¶
Fallacies of Distributed Computing¶
분산 시스템 초보자들이 흔히 하는 잘못된 가정들입니다.
┌─────────────────────────────────────────────────────────────────────────┐
│ 분산 컴퓨팅의 8가지 오류 (Fallacies) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 네트워크는 신뢰할 수 있다 (The network is reliable) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 패킷 손실 │ │
│ │ - 네트워크 파티션 │ │
│ │ - 스위치/라우터 장애 │ │
│ │ │ │
│ │ Node A ───X───► Node B │ │
│ │ 패킷 손실 │ │
│ │ │ │
│ │ 대응: 재시도, 타임아웃, 멱등성 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 2. 지연 시간은 0이다 (Latency is zero) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 로컬 호출: ~10 ns │ │
│ │ - 같은 DC: 0.5 ms │ │
│ │ - 대륙 간: 100+ ms │ │
│ │ │ │
│ │ Seoul ──────────────────► US West │ │
│ │ ~150ms RTT │ │
│ │ │ │
│ │ 대응: 캐싱, 비동기 처리, 지역 분산 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 3. 대역폭은 무한하다 (Bandwidth is infinite) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 네트워크 혼잡 │ │
│ │ - 대역폭 한계 │ │
│ │ - 비용 │ │
│ │ │ │
│ │ 대응: 압축, 페이징, 데이터 지역성 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 4. 네트워크는 안전하다 (The network is secure) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 중간자 공격 │ │
│ │ - 패킷 스니핑 │ │
│ │ - 악의적 노드 │ │
│ │ │ │
│ │ 대응: TLS, 인증, 암호화 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────┐
│ 분산 컴퓨팅의 8가지 오류 (계속) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 5. 토폴로지는 변하지 않는다 (Topology doesn't change) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 서버 추가/제거 │ │
│ │ - 장애 복구 │ │
│ │ - 스케일링 │ │
│ │ │ │
│ │ 대응: 서비스 디스커버리, 동적 구성 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 6. 관리자는 한 명이다 (There is one administrator) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 여러 팀, 여러 조직 │ │
│ │ - 서로 다른 정책 │ │
│ │ - 클라우드 + 온프레미스 │ │
│ │ │ │
│ │ 대응: 표준화, 자동화, 거버넌스 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 7. 전송 비용은 0이다 (Transport cost is zero) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 클라우드 이그레스 비용 │ │
│ │ - 직렬화/역직렬화 오버헤드 │ │
│ │ - 네트워크 장비 비용 │ │
│ │ │ │
│ │ 대응: 데이터 지역성, 효율적인 프로토콜 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 8. 네트워크는 균질적이다 (The network is homogeneous) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 실제: │ │
│ │ - 다양한 하드웨어 │ │
│ │ - 다양한 프로토콜 │ │
│ │ - 레거시 시스템 │ │
│ │ │ │
│ │ 대응: 표준 프로토콜, 추상화 계층 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2. 시간과 순서¶
물리 시계의 문제¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 물리 시계 (Physical Clocks) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 문제 1: 시계 드리프트 (Clock Drift) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 시간 ─────────────────────────────────────────────────────► │ │
│ │ │ │
│ │ 실제 시간: ═════════════════════════════════════════════════ │ │
│ │ │ │
│ │ Node A: ════════════════════════════════════════════════ │ │
│ │ (약간 빠름) │ │
│ │ │ │
│ │ Node B: ════════════════════════════════════════════════ │ │
│ │ (약간 느림) │ │
│ │ │ │
│ │ 일반적인 드리프트: 초당 10-100 마이크로초 │ │
│ │ → 하루에 수 초 차이 발생! │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 문제 2: NTP 동기화의 한계 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ - 일반적 정확도: 수십 밀리초 │ │
│ │ - 인터넷 환경: 100ms 이상 오차 가능 │ │
│ │ - 시간 점프 발생 가능 (앞/뒤로) │ │
│ │ │ │
│ │ NTP Server ───────────► Node │ │
│ │ 네트워크 지연 │ │
│ │ 으로 인한 오차 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 문제 3: 타임스탬프 기반 순서화의 위험 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Node A (시계 빠름): Write X=1 at T=100 │ │
│ │ Node B (시계 느림): Write X=2 at T=99 │ │
│ │ │ │
│ │ 타임스탬프로 정렬: X=2 (T=99) → X=1 (T=100) │ │
│ │ 실제 발생 순서: X=1 먼저 → X=2 나중 │ │
│ │ │ │
│ │ → 잘못된 순서! 데이터 손실 가능! │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Happens-Before 관계¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Happens-Before 관계 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 정의: a → b (a happens-before b) │
│ │
│ 1. 같은 프로세스에서 a가 b 이전에 발생 │
│ 2. a가 메시지 전송, b가 해당 메시지 수신 │
│ 3. 전이성: a → b ∧ b → c ⟹ a → c │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Process P1: ─────●a─────────────●c──────────────────────► │ │
│ │ │ ▲ │ │
│ │ │ │ │ │
│ │ ▼ (메시지) │ (메시지) │ │
│ │ │ │ │ │
│ │ Process P2: ─────────●b─────────●d──────────────────────► │ │
│ │ │ │
│ │ 관계: │ │
│ │ - a → b (메시지 전송) │ │
│ │ - b → d (같은 프로세스) │ │
│ │ - a → c (같은 프로세스) │ │
│ │ - d → c (메시지 전송) │ │
│ │ - a → d (전이성: a → b → d) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 동시성 (Concurrent): │
│ a → b도 아니고 b → a도 아닌 경우, a와 b는 동시(concurrent) │
│ a ∥ b로 표기 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ P1: ─────●a─────────────────────────────────────────► │ │
│ │ │ │
│ │ P2: ─────────────●b─────────────────────────────────► │ │
│ │ │ │
│ │ a와 b는 인과관계 없음 → 순서 정의 불가 → 동시 (a ∥ b) │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. 논리 시계¶
Lamport Clock¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Lamport Clock │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 규칙: │
│ 1. 각 프로세스는 카운터 C를 유지 │
│ 2. 이벤트 발생 시: C = C + 1 │
│ 3. 메시지 전송 시: 메시지에 현재 C 포함 │
│ 4. 메시지 수신 시: C = max(C, msg.C) + 1 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Process A: ─●───────●───────────────●───────────────► │ │
│ │ (C) 1 2 5 │ │
│ │ │ ▲ │ │
│ │ │ msg(C=2) │ msg(C=4) │ │
│ │ ▼ │ │ │
│ │ Process B: ─────────●───────●───────●───────────────► │ │
│ │ (C) 3 4 5 │ │
│ │ ▲ │ │
│ │ │ │ │
│ │ B receives msg from A: max(2, 2) + 1 = 3 │ │
│ │ B local event: 3 + 1 = 4 │ │
│ │ B sends msg to A: 4 (in message) │ │
│ │ A receives msg from B: max(2, 4) + 1 = 5 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 특성: │
│ ✓ a → b ⟹ C(a) < C(b) (인과관계면 시계도 순서 맞음) │
│ ✗ C(a) < C(b) ⟹ a → b (역은 성립 안함!) │
│ │
│ 한계: │
│ - 동시 이벤트 구분 불가 │
│ - 같은 카운터 값 가능 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Vector Clock¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Vector Clock │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 규칙: │
│ - 각 프로세스 i는 벡터 V[1..N] 유지 (N = 프로세스 수) │
│ - 이벤트 발생 시: V[i] = V[i] + 1 │
│ - 메시지 전송 시: 전체 벡터 V 포함 │
│ - 메시지 수신 시: V[j] = max(V[j], msg.V[j]) for all j, V[i]++ │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Process A: ─●─────────●─────────────────●───────────► │ │
│ │ V [1,0,0] [2,0,0] [3,2,1] │ │
│ │ │ ▲ │ │
│ │ │ │ msg [2,2,1] │ │
│ │ ▼ │ │ │
│ │ Process B: ─────────●─────────●─────────●───────────► │ │
│ │ V [2,1,0] [2,2,0] [2,2,1] │ │
│ │ ▲ │ │ │
│ │ │ │ msg [2,2,0] │ │
│ │ │ ▼ │ │
│ │ Process C: ─────────●─────────●─────────────────────► │ │
│ │ V [0,0,1] [2,2,1] │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 비교 규칙: │
│ - V1 ≤ V2: V1[i] ≤ V2[i] for all i │
│ - V1 < V2: V1 ≤ V2 and V1 ≠ V2 │
│ - V1 ∥ V2: neither V1 < V2 nor V2 < V1 (동시) │
│ │
│ 예시: │
│ [2,0,0] < [2,2,0] ✓ (happens-before) │
│ [2,1,0] ∥ [0,0,1] ✓ (concurrent) │
│ │
│ 장점: 동시 이벤트 감지 가능 │
│ 단점: 벡터 크기 = 프로세스 수 (확장성 문제) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
논리 시계 비교¶
| 특성 | Lamport Clock | Vector Clock |
|---|---|---|
| 크기 | 정수 1개 | N개 정수 |
| 인과관계 감지 | 부분적 | 완전 |
| 동시성 감지 | 불가 | 가능 |
| 확장성 | 우수 | 제한적 |
| 구현 복잡도 | 간단 | 중간 |
실제 사용 예¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Vector Clock 활용 예: DynamoDB │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 충돌 감지 및 해결: │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 초기 상태: X = "A", V = [1,0] │ │
│ │ │ │
│ │ Replica 1: Write X = "B" → V = [2,0] │ │
│ │ Replica 2: Write X = "C" → V = [1,1] │ │
│ │ │ │
│ │ 동기화 시점: │ │
│ │ [2,0] ∥ [1,1] (동시 쓰기!) │ │
│ │ │ │
│ │ 해결 방법: │ │
│ │ 1. Last-Write-Wins (타임스탬프) │ │
│ │ 2. 클라이언트에게 반환하여 해결하게 함 │ │
│ │ 3. 애플리케이션 정의 병합 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 예: 장바구니 병합 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Client reads: [item1], [item2] (두 버전) │ │
│ │ Client merges: [item1, item2] │ │
│ │ Client writes: 병합된 결과 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4. 리더 선출¶
리더 선출이 필요한 이유¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 리더 선출 (Leader Election) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 왜 필요한가? │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 분산 시스템에서 조정자(coordinator) 역할이 필요한 경우: │ │
│ │ │ │
│ │ - 분산 락 관리 │ │
│ │ - 합의 알고리즘에서 제안자 │ │
│ │ - 데이터베이스 Primary 노드 │ │
│ │ - 분산 작업 스케줄링 │ │
│ │ - 메시지 순서 결정 │ │
│ │ │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ Node 1 │ │ Node 2 │ │ Node 3 │ │ │
│ │ │(Leader) │ │(Follower│ │(Follower│ │ │
│ │ │ ★ │ │ │ │ │ │ │
│ │ └────┬────┘ └────┬────┘ └────┬────┘ │ │
│ │ │ │ │ │ │
│ │ └────────────┼────────────┘ │ │
│ │ │ │ │
│ │ 조정/동기화 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 요구사항: │
│ 1. Safety: 동시에 최대 1명의 리더 │
│ 2. Liveness: 결국 리더가 선출됨 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Bully Algorithm¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Bully 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 규칙: 가장 높은 ID를 가진 노드가 리더 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 초기 상태: Node 5가 리더 │ │
│ │ │ │
│ │ Node 1 Node 2 Node 3 Node 4 Node 5 (Leader) │ │
│ │ │ │ │ │ ✗ (장애) │ │
│ │ │ │ │ │ │ │
│ │ │ │
│ │ Step 1: Node 2가 리더 장애 감지 │ │
│ │ ───────────────────────────── │ │
│ │ Node 2 → "ELECTION" → Node 3, 4, 5 │ │
│ │ │ │
│ │ Step 2: 더 높은 ID가 응답 │ │
│ │ ───────────────────────────── │ │
│ │ Node 3 → "OK" → Node 2 (나보다 높은 ID 있음) │ │
│ │ Node 4 → "OK" → Node 2 │ │
│ │ Node 5 → (무응답) │ │
│ │ │ │
│ │ Step 3: Node 3, 4도 선거 시작 │ │
│ │ ───────────────────────────── │ │
│ │ Node 3 → "ELECTION" → Node 4, 5 │ │
│ │ Node 4 → "ELECTION" → Node 5 │ │
│ │ │ │
│ │ Step 4: Node 4가 최종 승자 │ │
│ │ ───────────────────────────── │ │
│ │ Node 4 → "COORDINATOR" → All │ │
│ │ │ │
│ │ Node 1 Node 2 Node 3 Node 4 (Leader) Node 5 │ │
│ │ ★ ✗ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 복잡도: O(n²) 메시지 │
│ │
│ 문제점: │
│ - 네트워크 파티션 시 Split-Brain 가능 │
│ - 높은 ID 노드가 불안정하면 계속 선거 반복 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Ring Algorithm¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Ring 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 구조: 노드가 논리적 링으로 구성 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌───────┐ │ │
│ │ │Node 1 │ │ │
│ │ └───┬───┘ │ │
│ │ ┌────────┘ └────────┐ │ │
│ │ ▼ ▼ │ │
│ │ ┌───────┐ ┌───────┐ │ │
│ │ │Node 5 │◄──────────│Node 2 │ │ │
│ │ └───┬───┘ └───┬───┘ │ │
│ │ │ │ │ │
│ │ ▼ ▼ │ │
│ │ ┌───────┐ ┌───────┐ │ │
│ │ │Node 4 │───────────│Node 3 │ │ │
│ │ └───────┘ └───────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 선거 과정: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 1. 리더 장애 감지 시 선거 메시지 생성: [initiator_id] │ │
│ │ │ │
│ │ 2. 다음 노드로 전달, 자신의 ID 추가: │ │
│ │ Node 2: [3] → Node 3 │ │
│ │ Node 3: [3, 4] → Node 4 │ │
│ │ Node 4: [3, 4, 5] → Node 5 │ │
│ │ Node 5: [3, 4, 5, 1] → Node 1 │ │
│ │ Node 1: [3, 4, 5, 1, 2] → Node 2 │ │
│ │ │ │
│ │ 3. 메시지가 시작점으로 돌아오면: │ │
│ │ - 리스트에서 가장 높은 ID 선택: 5 │ │
│ │ - COORDINATOR 메시지 전파: Node 5가 리더 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 복잡도: O(n) 메시지 │
│ │
│ 장점: 메시지 수 적음 │
│ 단점: 링 유지 필요, 느린 선거 과정 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
현대적 리더 선출¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 현대적 리더 선출 방식 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 합의 기반 (Consensus-based) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ - Raft, Paxos 등 합의 알고리즘 사용 │ │
│ │ - 분산 락 서비스 활용 (ZooKeeper, etcd, Consul) │ │
│ │ - Split-Brain 방지 │ │
│ │ │ │
│ │ 예: Raft 리더 선출 │ │
│ │ - 타임아웃 후 Candidate로 전환 │ │
│ │ - 과반수 투표로 리더 선출 │ │
│ │ - Term 기반 리더십 관리 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 2. 외부 서비스 활용 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌─────────────────────────────────────────────────────────┐ │ │
│ │ │ ZooKeeper / etcd │ │ │
│ │ │ │ │ │
│ │ │ /leader-election/ │ │ │
│ │ │ └─ lock (ephemeral node) │ │ │
│ │ │ owner: node-1 │ │ │
│ │ │ │ │ │
│ │ └─────────────────────────────────────────────────────────┘ │ │
│ │ │ │ │ │ │
│ │ ▼ ▼ ▼ │ │
│ │ ┌────────┐ ┌────────┐ ┌────────┐ │ │
│ │ │Node 1 │ │Node 2 │ │Node 3 │ │ │
│ │ │(Leader)│ │(Watch) │ │(Watch) │ │ │
│ │ └────────┘ └────────┘ └────────┘ │ │
│ │ │ │
│ │ - Ephemeral 노드 생성 시도 │ │
│ │ - 첫 번째 생성자가 리더 │ │
│ │ - 리더 장애 시 노드 자동 삭제 → 재선거 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5. 분산 시스템의 도전 과제¶
네트워크 파티션¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 네트워크 파티션 (Network Partition) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 파티션 발생: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Partition A ✗ Partition B │ │
│ │ ┌─────────────┐ 네트워크 단절 ┌─────────────┐ │ │
│ │ │ │ ═══════════════ │ │ │ │
│ │ │ Node 1 │ │ Node 3 │ │ │
│ │ │ Node 2 │ │ Node 4 │ │ │
│ │ │ │ │ Node 5 │ │ │
│ │ │ │ │ │ │ │
│ │ └─────────────┘ └─────────────┘ │ │
│ │ │ │
│ │ 각 파티션은 서로를 "장애"로 인식 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Split-Brain 문제: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Partition A: Partition B: │ │
│ │ "Node 3,4,5 장애!" "Node 1,2 장애!" │ │
│ │ → Node 1이 리더 → Node 5가 리더 │ │
│ │ │ │
│ │ 두 개의 리더! → 데이터 불일치, 충돌 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 해결책: Quorum (정족수) │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 과반수 (N/2 + 1) 이상 노드와 통신 가능해야 리더 역할 수행 │ │
│ │ │ │
│ │ 5개 노드 중: │ │
│ │ - Partition A (2개): 2 < 3 → 리더 불가 │ │
│ │ - Partition B (3개): 3 ≥ 3 → 리더 가능 │ │
│ │ │ │
│ │ → 오직 하나의 리더만 존재! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
부분 장애¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 부분 장애 (Partial Failure) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 분산 시스템의 고유한 특성: 일부만 실패할 수 있음 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 모호한 상황: │ │
│ │ │ │
│ │ Node A ──Request──► Node B │ │
│ │ ◄───?──── │ │
│ │ 타임아웃! │ │
│ │ │ │
│ │ 가능한 원인: │ │
│ │ 1. 요청이 손실됨 │ │
│ │ 2. Node B가 장애 │ │
│ │ 3. 요청은 처리됐지만 응답이 손실됨 │ │
│ │ 4. Node B가 느림 (나중에 응답 올 수 있음) │ │
│ │ │ │
│ │ → 재시도? 안 하면? 어떤 게 맞는 결정인지 알 수 없음! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 대응 전략: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 1. 멱등성 설계: 재시도해도 안전하게 │ │
│ │ 2. 타임아웃 조정: 너무 짧지도, 길지도 않게 │ │
│ │ 3. 헬스체크: 노드 상태 주기적 확인 │ │
│ │ 4. 서킷 브레이커: 반복적 실패 시 빠른 실패 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Byzantine Failure¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Byzantine Failure │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 일반적인 장애: 노드가 멈추거나 응답 없음 (Crash Failure) │
│ Byzantine 장애: 노드가 잘못된/악의적인 행동 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 정상 노드: Byzantine 노드: │ │
│ │ - 프로토콜 준수 - 거짓말 │ │
│ │ - 정확한 정보 - 다른 메시지를 다른 노드에 │ │
│ │ - 일관된 동작 - 랜덤한 동작 │ │
│ │ │ │
│ │ ┌─────┐ "값은 5" ┌─────┐ │ │
│ │ │ A │───────────────►│ B │ │ │
│ │ │(악)│ └─────┘ │ │
│ │ │ │ "값은 7" ┌─────┐ │ │
│ │ │ │───────────────►│ C │ │ │
│ │ └─────┘ └─────┘ │ │
│ │ │ │
│ │ B와 C는 다른 값을 받음 → 합의 불가! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 대응: │
│ - Byzantine Fault Tolerant (BFT) 알고리즘 │
│ - 3f + 1 노드로 f개 Byzantine 장애 허용 │
│ - 블록체인에서 주로 사용 (PBFT, Tendermint) │
│ │
│ 일반적인 시스템에서는: │
│ - 내부 노드는 신뢰 가정 (Crash Failure 모델) │
│ - 외부 입력만 검증 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
6. 연습 문제¶
연습 1: Lamport Clock 계산¶
다음 이벤트 시퀀스에서 각 이벤트의 Lamport 타임스탬프를 계산하세요:
P1: a ────────────► b ──────────────────► c
│ ▲
▼ │
P2: ─────d ─────────► e ─────────f ────►
연습 2: Vector Clock 분석¶
다음 Vector Clock 값들의 관계(happens-before, concurrent)를 판단하세요: - V1 = [2, 1, 0] - V2 = [1, 2, 0] - V3 = [2, 2, 1] - V4 = [3, 1, 0]
연습 3: 리더 선출 설계¶
5개 노드의 분산 데이터베이스에서 리더 선출 메커니즘을 설계하세요: - 네트워크 파티션 처리 - Split-Brain 방지 - 리더 장애 시 자동 복구
다음 단계¶
16_Consensus_Algorithms.md에서 Paxos, Raft 등 분산 합의 알고리즘을 배워봅시다!
참고 자료¶
- "Distributed Systems" - Maarten van Steen, Andrew Tanenbaum
- "Designing Data-Intensive Applications" - Martin Kleppmann
- "Time, Clocks, and the Ordering of Events in a Distributed System" - Leslie Lamport
- "The Fallacies of Distributed Computing" - L Peter Deutsch
- Raft Consensus Algorithm - raft.github.io