합의 알고리즘 (Consensus Algorithms)
합의 알고리즘 (Consensus Algorithms)¶
난이도: ⭐⭐⭐⭐
개요¶
분산 시스템에서 합의(Consensus)는 여러 노드가 하나의 값에 동의하는 것입니다. 이 장에서는 합의 문제의 정의, Paxos와 Raft 알고리즘, Byzantine Fault Tolerance, 그리고 ZooKeeper와 etcd의 활용을 학습합니다.
목차¶
1. 합의 문제 정의¶
합의란?¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 합의 문제 (Consensus Problem) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 목표: N개의 노드가 하나의 값에 동의하기 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Node 1: "A" │ │
│ │ Node 2: "B" ───► 모든 노드: "A" (또는 "B") │ │
│ │ Node 3: "A" │ │
│ │ Node 4: "C" │ │
│ │ Node 5: (장애) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 사용 사례: │
│ - 리더 선출: 누가 리더인가? │
│ - 분산 락: 누가 락을 획득했는가? │
│ - 분산 DB: 어떤 트랜잭션 순서로 커밋하는가? │
│ - 상태 머신 복제: 어떤 명령을 실행하는가? │
│ │
└─────────────────────────────────────────────────────────────────────────┘
합의의 속성¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 합의 알고리즘의 필수 속성 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. Safety (안전성) - 잘못된 것이 발생하지 않음 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Agreement (합의): │ │
│ │ - 모든 정상 노드는 같은 값에 합의 │ │
│ │ - 두 노드가 다른 값을 결정하면 안됨 │ │
│ │ │ │
│ │ Validity (유효성): │ │
│ │ - 결정된 값은 어떤 노드가 제안한 값이어야 함 │ │
│ │ - 아무도 제안하지 않은 값은 선택 불가 │ │
│ │ │ │
│ │ Integrity (무결성): │ │
│ │ - 각 노드는 최대 한 번만 결정 │ │
│ │ - 한번 결정하면 변경 불가 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 2. Liveness (활성) - 좋은 것이 결국 발생함 │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Termination (종료): │ │
│ │ - 모든 정상 노드는 결국 값을 결정 │ │
│ │ - 영원히 대기하지 않음 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ FLP Impossibility (1985): │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 비동기 시스템에서 단 하나의 노드 장애도 허용하면서 │ │
│ │ Safety와 Liveness를 동시에 보장하는 것은 불가능하다. │ │
│ │ │ │
│ │ 실제 시스템의 대응: │ │
│ │ - Liveness를 약간 희생 (타임아웃 후 재시도) │ │
│ │ - 동기 가정 추가 (부분 동기) │ │
│ │ - Safety는 항상 보장 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
장애 모델¶
| 모델 | 설명 | 필요 노드 수 |
|---|---|---|
| Crash Failure | 노드가 멈춤, 복구 가능 | 2f + 1 |
| Omission Failure | 메시지 손실 가능 | 2f + 1 |
| Byzantine Failure | 악의적/임의의 행동 | 3f + 1 |
2. Paxos 알고리즘¶
Paxos 개요¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Paxos 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Leslie Lamport이 1989년에 발명 (1998년 발표) │
│ 분산 합의의 기초가 되는 알고리즘 │
│ │
│ 역할: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Proposer (제안자) │ │
│ │ - 값을 제안 │ │
│ │ - 클라이언트 요청 처리 │ │
│ │ │ │
│ │ Acceptor (수락자) │ │
│ │ - 제안을 투표 │ │
│ │ - 과반수가 수락하면 결정 │ │
│ │ - 상태 저장 │ │
│ │ │ │
│ │ Learner (학습자) │ │
│ │ - 결정된 값을 학습 │ │
│ │ - 읽기 전용 복제본 │ │
│ │ │ │
│ │ (실제로는 한 노드가 여러 역할 수행 가능) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Basic Paxos: 두 단계¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Basic Paxos: Phase 1 - Prepare │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Proposer Acceptors (과반수 필요) │
│ │ A1 A2 A3 │
│ │ │ │ │ │
│ │───Prepare(n=1)────►│ │ │ │
│ │───Prepare(n=1)────────────►│ │ │
│ │───Prepare(n=1)────────────────────►│ │
│ │ │ │ │ │
│ │ │ │ │ │
│ │◄──Promise(n=1)────│ │ │ │
│ │◄──Promise(n=1)────────────│ │ │
│ │◄──Promise(n=1)────────────────────│ │
│ │ │ │ │ │
│ │
│ Prepare(n): "제안 번호 n으로 제안하려 합니다" │
│ Promise(n): "n보다 작은 제안은 무시하겠습니다" │
│ + 이전에 수락한 값이 있으면 함께 반환 │
│ │
│ Acceptor 규칙: │
│ - 받은 n > 기존 promised_n 이면 Promise │
│ - 그렇지 않으면 무시/거부 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────┐
│ Basic Paxos: Phase 2 - Accept │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 과반수 Promise 받은 후: │
│ │
│ Proposer Acceptors │
│ │ A1 A2 A3 │
│ │ │ │ │ │
│ │──Accept(n=1,v="X")─►│ │ │ │
│ │──Accept(n=1,v="X")─────────►│ │ │
│ │──Accept(n=1,v="X")─────────────────►│ │
│ │ │ │ │ │
│ │◄──Accepted(n=1)────│ │ │ │
│ │◄──Accepted(n=1)────────────│ │ │
│ │◄──Accepted(n=1)────────────────────│ │
│ │ │ │ │ │
│ ▼ │
│ 과반수 Accepted → 값 "X" 결정! │
│ │
│ Accept(n, v): "제안 번호 n으로 값 v를 수락해주세요" │
│ Accepted(n): "수락했습니다" │
│ │
│ v 선택 규칙: │
│ - Promise에서 받은 이전 값이 있으면 그 중 가장 높은 n의 값 사용 │
│ - 없으면 자신이 원하는 값 제안 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Paxos 충돌 해결¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Paxos: 동시 제안 처리 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 시나리오: 두 Proposer가 동시에 제안 │
│ │
│ Proposer1 Proposer2 Acceptors │
│ │ │ A1 A2 A3 │
│ │ │ │ │ │ │
│ │─Prepare(1)─►│ │ │ │ │
│ │ │─Prepare(2)─►│ │ │ │
│ │ │ │ │ │ │
│ │◄─Promise(1)─┼─────────────│ │ │ A1: n=1 │
│ │ │◄─Promise(2)─────────│ │ A2: n=2 │
│ │ │◄─Promise(2)─────────────────│ A3: n=2 │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
│ │─Accept(1,X)►│ │ │ │ │
│ │ │ X NACK! (n=1 < promised n=2) │
│ │ │ │ │ │ │
│ │ │─Accept(2,Y)►│ │ │ │
│ │ │◄─Accepted───────────│ │ │
│ │ │◄─Accepted───────────────────│ │
│ │ │ │ │ │ │
│ │ ▼ │ │ │ │
│ │ 값 "Y" 결정 │ │ │ │
│ │ │ │ │ │ │
│ │ │ │ │ │ │
│ Proposer1은 더 높은 n으로 재시도 필요 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Multi-Paxos¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Multi-Paxos │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Basic Paxos의 문제: 매번 Prepare 필요 (2 RTT) │
│ │
│ Multi-Paxos 최적화: │
│ - 안정적인 리더 선출 │
│ - 리더가 연속적인 값들을 결정 │
│ - Prepare 단계 생략 (1 RTT) │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Leader Acceptors │ │
│ │ │ A1 A2 A3 │ │
│ │ │ │ │ │ │ │
│ │ │──Prepare(n=1)────►│ │ (최초 1회만) │ │
│ │ │◄─Promise(n=1)─────│ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │
│ │ │──Accept(1,v1)────►│ │ Log Entry 1 │ │
│ │ │◄─Accepted─────────│ │ │ │
│ │ │ │ │ │ │ │
│ │ │──Accept(1,v2)────►│ │ Log Entry 2 │ │
│ │ │◄─Accepted─────────│ │ │ │
│ │ │ │ │ │ │ │
│ │ │──Accept(1,v3)────►│ │ Log Entry 3 │ │
│ │ │◄─Accepted─────────│ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │
│ │ 리더가 안정적인 동안 Accept만 반복 (1 RTT) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. Raft 알고리즘¶
Raft 개요¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ "In Search of an Understandable Consensus Algorithm" (2014) │
│ Diego Ongaro, John Ousterhout │
│ │
│ 설계 목표: 이해하기 쉬운 합의 알고리즘 │
│ - Paxos와 동등한 성능/안전성 │
│ - 훨씬 이해하기 쉬움 │
│ │
│ 주요 개념 분리: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 1. Leader Election (리더 선출) │ │
│ │ 2. Log Replication (로그 복제) │ │
│ │ 3. Safety (안전성) │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 노드 상태: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 타임아웃 과반수 획득 │ │
│ │ ┌────────┐ ───────► ┌────────────┐ ──────► ┌────────┐ │ │
│ │ │Follower│ │ Candidate │ │ Leader │ │ │
│ │ └────────┘ ◄─────── └────────────┘ ◄────── └────────┘ │ │
│ │ 더 높은 Term 타임아웃 더 높은 Term │ │
│ │ (재선거) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Term (임기)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft: Term (임기) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Term: 논리적 시간 단위 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Term 1 │ Term 2 │ Term 3 │ Term 4 │ │ │
│ │ ┌───────┐ │ ┌───────┐ │ ┌───┐ │ ┌─────────┐ │ │ │
│ │ │선거 │ │ │선거 │ │ │선거│ │ │선거 │ │ │ │
│ │ │ │ │ │ │ │ │실패│ │ │ │ │ │ │
│ │ │Node 1 │ │ │Node 3 │ │ │ │ │ │ Node 2 │ │ │ │
│ │ │Leader │ │ │Leader │ │ │ │ │ │ Leader │ │ │ │
│ │ └───────┘ │ └───────┘ │ └───┘ │ └─────────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ ───────────┼─────────────┼──────────┼──────────────┼───► │ │
│ │ 시간 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Term 규칙: │
│ - 각 Term에는 최대 한 명의 리더 │
│ - Term 시작: 새 선거 시작 │
│ - 더 높은 Term을 발견하면 즉시 Follower로 전환 │
│ - 오래된 Term의 메시지는 무시 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Leader Election¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft: Leader Election │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Step 1: Election Timeout │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Node A (Follower) │ │
│ │ │ │ │
│ │ │─────────────────────────────────────────────► │ │
│ │ │ heartbeat 없음 (150-300ms) │ │ │
│ │ │ ▼ │ │
│ │ │ 타임아웃! │ │
│ │ │ → Candidate로 전환 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ Step 2: Request Vote │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Node A (Candidate) Node B Node C │ │
│ │ term: 2 term: 1 term: 1 │ │
│ │ │ │ │ │ │
│ │ │── RequestVote(term=2) ────►│ │ │ │
│ │ │── RequestVote(term=2) ──────────────────►│ │ │
│ │ │ │ │ │ │
│ │ │◄── VoteGranted ────────────│ │ │ │
│ │ │◄── VoteGranted ──────────────────────────│ │ │
│ │ │ │ │ │ │
│ │ ▼ │ │
│ │ 과반수 (2/3) 획득 → Leader 선출! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 투표 규칙: │
│ - 각 Term에서 최대 1표만 행사 │
│ - 요청자의 로그가 자신보다 최신이어야 투표 │
│ - 투표 후 타이머 리셋 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Log Replication¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft: Log Replication │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Leader의 로그: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ Index: 1 2 3 4 5 6 │ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┐ │ │
│ │ Term: │ 1 │ 1 │ 2 │ 2 │ 2 │ 3 │ │ │
│ │ ├─────┼─────┼─────┼─────┼─────┼─────┤ │ │
│ │ Cmd: │ x=1 │ y=2 │ x=3 │ z=1 │ y=4 │ x=5 │ │ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┘ │ │
│ │ ▲ │ │
│ │ commitIndex │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 복제 과정: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Leader Follower 1 Follower 2 │ │
│ │ │ │ │ │ │
│ │ │ AppendEntries │ │ │ │
│ │ │ (term, prevLogIdx, │ │ │ │
│ │ │ prevLogTerm, │ │ │ │
│ │ │ entries[]) │ │ │ │
│ │ │────────────────────►│ │ │ │
│ │ │────────────────────────────────────► │ │ │
│ │ │ │ │ │ │
│ │ │◄── Success ─────────│ │ │ │
│ │ │◄── Success ───────────────────────── │ │ │
│ │ │ │ │ │ │
│ │ │ 과반수 복제 완료 │ │ │
│ │ │ → commitIndex 증가 │ │ │
│ │ │ → 상태 머신에 적용 │ │ │
│ │ │ │ │ │ │
│ │ │ 다음 AppendEntries에 commitIndex 포함 │ │
│ │ │ → Follower도 커밋 │ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Log Consistency¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Raft: Log Consistency │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ Log Matching Property: │
│ - 같은 index, 같은 term → 같은 command │
│ - 같은 index, 같은 term → 이전 모든 entry도 동일 │
│ │
│ 불일치 발생 시: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Leader: [1,1] [1,2] [2,3] [3,4] [3,5] [3,6] │ │
│ │ Follower: [1,1] [1,2] [2,3] [2,4] [2,5] │ │
│ │ ▲ │ │
│ │ 불일치 지점 │ │
│ │ │ │
│ │ 해결: Leader가 Follower 로그를 자신과 일치하도록 덮어씀 │ │
│ │ │ │
│ │ 1. AppendEntries(prevLogIdx=3, prevLogTerm=2) 실패 │ │
│ │ 2. nextIndex 감소하며 재시도 │ │
│ │ 3. 일치점 발견 (index=3) │ │
│ │ 4. index 4부터 Leader 로그로 덮어씀 │ │
│ │ │ │
│ │ 결과: │ │
│ │ Follower: [1,1] [1,2] [2,3] [3,4] [3,5] [3,6] │ │
│ │ (Leader와 동일) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Raft vs Paxos¶
| 특성 | Raft | Paxos |
|---|---|---|
| 이해 용이성 | 높음 | 낮음 |
| 리더 역할 | 명확 (강한 리더) | 유연 |
| 로그 순서 | 연속적 | 구멍 가능 |
| 구현 복잡도 | 낮음 | 높음 |
| 논문 명확성 | 상세 | 추상적 |
| 활용 사례 | etcd, CockroachDB | Chubby, Spanner |
4. Byzantine Fault Tolerance¶
Byzantine Generals Problem¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Byzantine Generals Problem │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 상황: N명의 장군이 공격/후퇴를 결정해야 함 │
│ 일부 장군이 배신자일 수 있음 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ ┌──────────┐ │ │
│ │ │ General 1│ │ │
│ │ │ (배신자) │ │ │
│ │ └────┬─────┘ │ │
│ │ │ │ │
│ │ "공격" │ "후퇴" │ │
│ │ ▼ ▼ │ │
│ │ ┌──────────┐ ┌──────────┐ │ │
│ │ │ General 2│ │ General 3│ │ │
│ │ │ (충성) │ │ (충성) │ │ │
│ │ └──────────┘ └──────────┘ │ │
│ │ │ │
│ │ Gen 2: "1번이 공격이래" / Gen 3: "1번이 후퇴래" │ │
│ │ → 충성스러운 장군들도 다른 결정을 내릴 수 있음! │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 해결 조건: 3f + 1 장군이 있으면 f명의 배신자 허용 │
│ 예: 4명의 장군 → 1명의 배신자 허용 │
│ 7명의 장군 → 2명의 배신자 허용 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
PBFT (Practical Byzantine Fault Tolerance)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ PBFT 알고리즘 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 3단계 프로토콜: Pre-Prepare → Prepare → Commit │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Client Primary Replica 1 Replica 2 Replica 3 │ │
│ │ │ │ │ │ │ │ │
│ │ │──Request──►│ │ │ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │─Pre-Prepare─►│ │ │ │ │
│ │ │ │─Pre-Prepare──────────────►│ │ │ │
│ │ │ │─Pre-Prepare──────────────────────────►│ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │◄──Prepare──│ │ │ │ │
│ │ │ │────Prepare─►│◄─Prepare──│ │ │ │
│ │ │ │ │────Prepare──►◄─Prepare──│ │ │
│ │ │ │ │ │────Prepare─►│ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │◄───Commit──│ │ │ │ │
│ │ │ │────Commit──►│◄──Commit──│ │ │ │
│ │ │ │ │────Commit───►◄──Commit──│ │ │
│ │ │ │ │ │────Commit──►│ │ │
│ │ │ │ │ │ │ │ │
│ │ │◄──Reply───│ │ │ │ │ │
│ │ │◄──Reply───────────────│ │ │ │ │
│ │ │◄──Reply──────────────────────────── │ │ │ │
│ │ │◄──Reply──────────────────────────────────────── │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │
│ │ f+1 동일한 Reply 받으면 클라이언트가 결과 수락 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 복잡도: O(n²) 메시지 │
│ 한계: 확장성 낮음 (보통 ~20 노드) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
BFT 활용¶
| 분야 | 예시 |
|---|---|
| 블록체인 | Tendermint, Hyperledger Fabric |
| 항공/우주 | 비행 제어 시스템 |
| 금융 | 고가용성 트레이딩 시스템 |
5. 실전 활용¶
ZooKeeper (ZAB)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ ZooKeeper / ZAB │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ZAB (ZooKeeper Atomic Broadcast): │
│ - Paxos 변형 │
│ - 리더 기반 │
│ - 순서 보장 │
│ │
│ 데이터 모델: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ / (루트) │ │
│ │ ├── /config 설정 데이터 │ │
│ │ │ └── /config/db {"host": "localhost"} │ │
│ │ ├── /locks 분산 락 │ │
│ │ │ └── /locks/job1 (ephemeral) │ │
│ │ └── /leader 리더 선출 │ │
│ │ └── /leader/node-1 (ephemeral + sequential) │ │
│ │ │ │
│ │ 노드 타입: │ │
│ │ - Persistent: 명시적 삭제 전까지 유지 │ │
│ │ - Ephemeral: 세션 종료 시 자동 삭제 │ │
│ │ - Sequential: 자동 증가 번호 부여 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 활용: │
│ - Kafka: 브로커 조정, 토픽 메타데이터 │
│ - HBase: 마스터 선출, 리전 할당 │
│ - Hadoop: HA NameNode │
│ │
└─────────────────────────────────────────────────────────────────────────┘
etcd (Raft)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ etcd │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 특징: │
│ - Raft 합의 알고리즘 │
│ - 키-값 저장소 │
│ - gRPC API │
│ - Watch 기능 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Kubernetes Control Plane │ │
│ │ │ │
│ │ ┌─────────────┐ ┌─────────────────────────┐ │ │
│ │ │ API Server │────────►│ etcd Cluster │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ │ ┌─────┐ ┌─────┐ ┌─────┐│ │ │
│ │ │ - Pods │ │ │etcd1│ │etcd2│ │etcd3││ │ │
│ │ │ - Services │ │ │Raft │ │Raft │ │Raft ││ │ │
│ │ │ - ConfigMaps│ │ └─────┘ └─────┘ └─────┘│ │ │
│ │ └─────────────┘ └─────────────────────────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 사용 예시: │
│ ``` │
│ # 키 저장 │
│ etcdctl put /config/db/host "localhost" │
│ │
│ # 키 조회 │
│ etcdctl get /config/db/host │
│ │
│ # Watch (변경 감지) │
│ etcdctl watch /config/db/ │
│ │
│ # 리더 확인 │
│ etcdctl endpoint status │
│ ``` │
│ │
│ 활용: │
│ - Kubernetes: 클러스터 상태 저장 │
│ - Service Discovery: Consul 대안 │
│ - Feature Flags: 동적 설정 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
Consul¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Consul │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 특징: │
│ - Raft 합의 알고리즘 │
│ - 서비스 디스커버리 │
│ - 헬스 체크 │
│ - KV 저장소 │
│ - 다중 데이터센터 │
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ DC1 (Primary) DC2 (Secondary) │ │
│ │ ┌─────────────────┐ ┌─────────────────┐ │ │
│ │ │ Consul Servers │◄──WAN────►│ Consul Servers │ │ │
│ │ │ (3 nodes, Raft)│ Gossip │ (3 nodes, Raft)│ │ │
│ │ └────────┬────────┘ └────────┬────────┘ │ │
│ │ │ │ │ │
│ │ ┌──────┴──────┐ ┌──────┴──────┐ │ │
│ │ │ │ │ │ │ │
│ │ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ │ │
│ │ │Agent│ │Agent│ │Agent│ │Agent│ │ │
│ │ │Svc A│ │Svc B│ │Svc A│ │Svc C│ │ │
│ │ └─────┘ └─────┘ └─────┘ └─────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 주요 기능: │
│ - DNS 기반 서비스 디스커버리: service.consul │
│ - 분산 락: Consul Sessions │
│ - 리더 선출: consul lock │
│ - 설정 관리: Consul KV + Template │
│ │
└─────────────────────────────────────────────────────────────────────────┘
도구 비교¶
| 특성 | ZooKeeper | etcd | Consul |
|---|---|---|---|
| 합의 알고리즘 | ZAB (Paxos 변형) | Raft | Raft |
| 데이터 모델 | 계층형 (파일시스템) | 플랫 KV | 플랫 KV |
| Watch | O | O | O |
| 서비스 디스커버리 | 수동 구현 | 수동 구현 | 내장 |
| 헬스 체크 | X | X | 내장 |
| 다중 DC | X | X | O |
| 언어 | Java | Go | Go |
| 주요 사용처 | Hadoop, Kafka | Kubernetes | HashiCorp 생태계 |
6. 연습 문제¶
연습 1: Paxos 시나리오¶
5개의 Acceptor가 있는 Paxos 시스템에서 다음 시나리오를 분석하세요: - Proposer 1이 n=1로 "A" 제안 - Proposer 2가 n=2로 "B" 제안 - 네트워크 지연으로 메시지 순서가 뒤섞임 - 최종적으로 어떤 값이 선택되는가?
연습 2: Raft 로그 복구¶
다음 상황에서 Raft의 로그 일관성 복구 과정을 설명하세요:
Leader: [1,1] [2,2] [2,3] [3,4] [3,5]
Follower: [1,1] [2,2] [2,3] [2,4]
연습 3: 합의 시스템 설계¶
다음 요구사항의 분산 설정 관리 시스템을 설계하세요: - 3개 데이터센터에 배포 - 하나의 DC 장애에도 서비스 지속 - 설정 변경은 밀리초 내 전파 - 읽기 성능 최적화
다음 단계¶
17_Design_Example_1.md에서 URL 단축기, 페이스트빈, Rate Limiter 설계를 실습해봅시다!
참고 자료¶
- "Paxos Made Simple" - Leslie Lamport
- "In Search of an Understandable Consensus Algorithm (Raft)" - Diego Ongaro
- "Practical Byzantine Fault Tolerance" - Castro, Liskov
- etcd Documentation: etcd.io
- ZooKeeper Documentation: zookeeper.apache.org
- Consul Documentation: consul.io
- Raft Visualization: raft.github.io