Brain259. 래프트 (Raft) / 팍소스 (Paxos) 알고리즘
핵심 인사이트 (3줄 요약)
- 본질: 래프트(Raft)와 팍소스(Paxos)는 분산 시스템에서 Consensus(합의)를 달성하기 위한 알고리즘으로, 여러 노드가 하나의 값에 대해 согласие(일치된 결정)에 도달하는 과정을 보장한다.
- 가치: 분산 환경에서 데이터 복제, 리더 선출, 상태 기계 복제 등에 필수적이며, 네트워크 분단이나 노드 장애가 발생해도 시스템이 согласие에 도달할 수 있게 한다.
- 융합: CAP 정리, 2PC, 분산 트랜잭션, NewSQL, ZooKeeper와 밀접하게 연관되며, etcd, Consul, CockroachDB, MongoDB(レプリカ셋 리더 선출) 등에서 활용된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
개념 정의
Consensus(합의) 알고리즘은 분산 시스템에서 여러 노드가 하나의 값에 대해 согласие(일치된 결정)에 도달하는 과정이다. 대표적인 알고리즘으로 Paxos(팍소스)와 Raft(래프트)가 있다. Paxos는 Leslie Lamport가 1989년에 제안한 이론적으로 완벽하지만 복잡한 알고리즘이며, Raft는 Diego Ongaro와 John Ousterhout이 2014에 Paxos를 개선하여 실용성을 높인 알고리즘이다.
필요성
분산 시스템에서는 여러 노드가 동일한 데이터를 복제하여 관리한다. 이때 모든 노드가 동일한 상태를 유지하려면, 값의 변경에 대해 모든 노드가 동일한 순서로 적용해야 한다. Consensus 알고리즘은 이러한 분산 환경에서의 согласие 달성을 가능하게 한다. 특히 네트워크 분단이나 노드 장애가 발생해도 시스템이 계속 작동할 수 있도록 보장한다.
배경
Paxos는 Leslie Lamport가 1989년 제안했으며, 1998년 저널에公开发표되었다. 그러나 그 복잡성으로 인해 실제가 적용하기 어려웠다. Raft는 2014년 Stanford 대학교에서 Ongaro와 Ousterhout이 Paxos의 복잡성을 해결하고 实際に 적용하기 쉽게 설계한 알고리즘이다. 이후 etcd, Consul, CockroachDB, TiKV 등에서 널리 활용되고 있다.
Consensus의 três 핵심 속성
┌─────────────────────────────────────────────────────────────────────────────┐
│ Consensus의 três 핵심 속성 (Paxos/Raft 공통) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. Agreement (일치성) │
│ ───────────────────── │
│ • 모든 정상 노드가 동일한 값에 대해 согласие해야 함 │
│ • 다수결(Majority) 기반으로 일치 달성 │
│ • 예: 5개 노드 중 3개 이상이 동의하면 전체 시스템이 그 값 принять │
│ │
│ 2. Validity (유효성) │
│ ───────────────── │
│ • 노드가 스스로 만든 값이 아니라, 클라이언트가 제안한 값만 принять함 │
│ • 예: 노드가勝手な値を生成して同意することはできない │
│ │
│ 3. Termination (종결성) │
│ ────────────────── │
│ • 시스템이永远에协商하지 않는 상황이 없어야 함 │
│ • 예: 장애가 없는 한 결국 모든 노드가 값에 동의해야 함 │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ FLP 불가능성 정리 (Fischer, Lynch, Paterson, 1985) │ │
│ │ │ │
│ │ "비동기 분산 시스템에서确定性 알고리즘은 │ │
│ │ 장애가 발생할 경우 Consensus를 항상 보장할 수 없다" │ │
│ │ │ │
│ │ 즉, 完全한 비동기 환경에서는 Consensus 보장 불가능! │ │
│ │ → 따라서 실재 시스템은 타임아웃 등 synchrony 가정 하에 동작 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
비유
Consensus 알고리즘은 여러 명이 함께 결정을 내리는 회의와 같다. 예를 들어 여행 일정을 정할 때,多数의同意가 있어야 최종 결정이 된다. 누군가缺席하거나通信が途切れても、残ったメンバーの中で多数결로結論を出す。会议が永遠に続かないように、一定時間応答がない場合は別の結論に切り替えられる.
📢 섹션 요약: Consensus 알고리즘은 분산 시스템에서 Agreement, Validity, Termination의 três 속성을 만족시켜, 여러 노드가 동일한 값에 대해 일치된 결정을 내릴 수 있게 한다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
Raft 알고리즘 구조
┌─────────────────────────────────────────────────────────────────────────────┐
│ Raft 알고리즘 개요 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Raft는 세 가지 하위 문제로 분리하여 설계됨: │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 1. 리더 선출 (Leader Election) │ │
│ │ ──────────────────────────── │ │
│ │ • 세 가지 상태: Leader, Candidate, Follower │ │
│ │ • 임의의 Follower이 타임아웃 후 Candidate가 되어 리더 선출 시도 │ │
│ │ • 과반수(Quorum)로부터vote를 받으면 Leader가 됨 │ │
│ │ • Heartbeat로_follower들의 지지를 유지 │ │
│ │ │ │
│ │ 2. 로그 복제 (Log Replication) │ │
│ │ ──────────────────────────── │ │
│ │ • Client 요청을 Leader가 받아 Log에 기록 │ │
│ │ • 다른 Follower에게도 Log를 복제 │ │
│ │ • 과반수로부터 복제 확인을 받으면 Commit(적용) │ │
│ │ • 모든 노드가 동일한 순서로 Log를 적용 │ │
│ │ │ │
│ │ 3. 안전성 (Safety) │ │
│ │ ───────────────── │ │
│ │ • 하나의 Term에 최대 하나의 Leader만 존재 │ │
│ │ • Leader는 이미 Commit된 Log만 복제 가능 │ │
│ │ • Candidate는 과반수의vote를 받은 경우만 Leader 가능 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] Raft의 핵심은 "Strong Leader" 개념이다. 모든 쓰기는 Leader를 통해서만 이루어지며, Leader는 과반수(Quorum)로부터 ack을 받아야 커밋으로 처리된다. 이는 복제 동작을 단순화하고 일관성을 쉽게 보장할 수 있게 한다. Follower가Leader로부터Heartbeat을 받지 못하면 임의의 시간 후Candidate가 되어 리더 선출을 시도한다.
Raft 리더 선출 과정
┌─────────────────────────────────────────────────────────────────────────────┐
│ Raft 리더 선출 과정 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [상태 전이 다이어그램] │
│ │
│ ┌────────────┐ │
│ │ Follower │◀──────────────────┐ │
│ └─────┬──────┘ │ │
│ │ │ │
│ │ Heartbeat timeout │ │
│ │ (electionTimeout 초과) │ │
│ ▼ │ │
│ ┌────────────┐ │ │
│ │ Candidate │───────────────────┼─────────────────┐ │
│ └─────┬──────┘ │ │ │
│ │ │ │ │
│ │ ┌────────────────────────┘ │ │
│ ▼ │ │
│ ┌────────────┐ ┌────────────┐ │ │
│ │ Leader │ │ Follower │◀────────────┘ │
│ └────────────┘ └────────────┘ (higher term 발견 시) │
│ │
│ [리더 선출 상세 과정] │
│ │
│ 1. Follower A: Heartbeat 미수신 → electionTimeout 초과 │
│ → 상태 전환: Follower → Candidate │
│ → 현재 Term = 1, voteCount = 1 (자신에게 투표) │
│ │
│ 2. Candidate A: 모든 노드에 RequestVote 요청 전송 │
│ │
│ 3. Follower B, C: 요청 수신 │
│ → 아직 투표 안함 + 아직 Leader 없음 │
│ → Candidate A에게 vote授予 │
│ → voteCount = 3 (과반수 달성!) │
│ │
│ 4. Candidate A: 과반수의vote 획득 │
│ → 상태 전환: Candidate → Leader │
│ → 모든 Follower에게 Heartbeat 전송하여 지지 확보 │
│ │
│ [리더 선출 실패 시나리오] │
│ │
│ • Candidate A가 과반수의vote를 받지 못함 (예: B만 응답, C는 동시에 선출 시도) │
│ → 새 Term 시작 → 다시vote 진행 │
│ → electionTimeout 랜덤화하여 충돌 최소화 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] Raft의 리더 선출은 "임의의 타이머"를 사용하여 충돌을 최소화한다. 각 Follower의 electionTimeout이 랜덤하게 설정되어 있어, 동시에 여러 Candidate가 발생하는 경우를 줄인다. 과반수의vote를 받지 못하면 다음 Term에서 다시 시도하며, 이 과정을 반복하다 보면 결국 하나의 Leader가 선출된다.
Paxos 알고리즘 구조
┌─────────────────────────────────────────────────────────────────────────────┐
│ Paxos 알고리즘 구조 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Paxos는 두 단계(Phase)로 구성됨: │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Phase 1: Prepare (준비 단계) │ │
│ │ ────────────────────────────────── │ │
│ │ │ │
│ │ Proposer: 전체Acceptor에게 Prepare(N) 요청 전송 │ │
│ │ (N: 제안 번호, monotonically increasing) │ │
│ │ │ │
│ │ Acceptor: │ │
│ │ • 이미 Promise한 번호보다 큰 N이면 Promise(N) 응답 │ │
│ │ • 이미 Accept한 값이 있다면 함께 반환 │ │
│ │ • 그렇지 않으면 Promise만 반환 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Phase 2: Accept (수락 단계) │ │
│ │ ──────────────────────────── │ │
│ │ │ │
│ │ Proposer: 과반수으로부터 Prepare 응답 수신 │ │
│ │ • 이미 Accept된 값이 있으면: 그 값으로 Accept(N, V) 요청 │ │
│ │ • 없으면: 원하는 값 V로 Accept(N, V) 요청 │ │
│ │ │ │
│ │ Acceptor: │ │
│ │ • Promise한 번호 N과 동일하면 Accept 수락 │ │
│ │ • 그렇지 않으면 거절 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Phase 3: Learn (학습 단계) │ │
│ │ ──────────────────────────── │ │
│ │ │ │
│ │ Accept된 값을 Learner가 받아 전체 노드에 전파 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] Paxos의 핵심은 "거부되지 않는 가장 큰 번호"의 제안을 통과시킨다는 점이다. Phase 1에서Acceptor는 이전에Accept한 값을 반환하므로,たとえ proposer가 달라진 값을 제안해도 이미Accept된 값이 있다면 그 값으로 통일된다. 이는 어떤 값이든 일관되게 결정되도록 보장한다.
Raft vs Paxos 비교
┌─────────────────────────────────────────────────────────────────────────────┐
│ Raft vs Paxos 비교 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────┬────────────────────────┬────────────────────────┐ │
│ │ 항목 │ Raft │ Paxos │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 복잡성 │ 상대적으로 단순 │ 매우 복잡 │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 구조 │ Strong Leader 기반 │ Leaderless (Paxos는 │ │
│ │ │ (리더가 모든 쓰기 조율) │ 별도의 Leader 없음) │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 리더 선출 │ 명시적 리더 선출 로직 │ Proposer가Leader 역할 │ │
│ │ │ (임의 타이머, 과반수) │ (번호가 가장 큰Proposer)│ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 로그 복제 │ Leader 중심, 직관적 │ 메시지 기반으로 간접적 │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 이해 용이성 │ 높음 (학생들이 1학기 │ 낮음 (설계자의 논문만 │ │
│ │ │看懂 가능) │ 이해 가능) │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 실재 활용 │ etcd, Consul, │ Google Chubby, │ │
│ │ │ CockroachDB, TiKV │ Zookeeper (ZAB) │ │
│ ├────────────────┼────────────────────────┼────────────────────────┤ │
│ │ 이론적 완결성 │ Raft보다 후에 제안됨 │ Lamport의 형식적 증명 │ │
│ │ │ │ 있으나 복잡해 실용성 낮음│ │
│ └────────────────┴────────────────────────┴────────────────────────┘ │
│ │
│ 핵심 결론: │
│ Raft는 Paxos의 복잡성을 해결하고 实제에 적용하기 쉽게 만든 것이며, │
│ Paxos는 이론적 기반을 제공하는 가장 원형적인 Consensus 알고리즘이다. │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: Raft는 Paxos를 실용적으로 개선한 알고리즘으로 Strong Leader 구조를 채택하여 이해하기 쉽고 구현이 용이하며, Paxos는 이론적으로 완결된 원형 알고리즘이다.
Ⅲ. 구현 및 실무 응용 (Implementation & Practice)
etcd에서의 Raft 활용
// etcd는 Raft 알고리즘을 사용하여 분산 키-값 저장소를 구현
// etcd의 쓰기 동작 (Raft 기반)
func (s *EtcdServer) Put(ctx context.Context, r *pb.PutRequest) (*PutResponse, error) {
// 1. 클라이언트 요청을 Raft Log에 기록
batch := &Batch{}
batch.Add(newPutRequest(r.Key, r.Value))
// 2. Raft 프로토콜을 통해 과반수에 복제
err := s.raft.Replicate(batch)
// - Leader가 과반수Follower에게 Log 복제 요청
// - Follower들이 Log 기록 후 Ack 반환
// - 과반수 Ack 수신 시 Commit
// 3. Commit된 Log를 상태 머신에 적용
s.apply()
return &PutResponse{}, nil
}
// etcd의 리더 선출 (Raft 기반)
type Raft struct {
id uint64
state StateType // StateLeader, StateCandidate, StateFollower
term uint64 // 현재 Term 번호
voteCount int // 획득한 투표 수
// ...
}
// 하트비트 수신 시
func (r *Raft) HandleHeartbeat(from uint64, m *pb.Message) {
if m.Term > r.term {
// 더 큰 Term 발견 → Follower로 전환
r.becomeFollower(m.Term, from)
}
// ...
}
ZooKeeper의 ZAB (ZooKeeper Atomic Broadcast)
// ZooKeeper는 Paxos를 변형한 ZAB 프로토콜 사용
// 리더 선출
public class Zookeeper {
// ZAB 프로토콜: 두 가지 모드
// 1. Recovery Mode: 새로운 리더 선출 및 동기화
// 2. Broadcast Mode: 클라이언트 요청을 모든 Follower에게 전파
// 리더 선출 과정
// 1. 각 서버가 ZXID (ZooKeeper Transaction ID)를 비교
// 2. 가장 높은 ZXID를 가진 서버가 잠정 리더가 됨
// 3. 과반수의 Follower가 잠정 리더를 인정하면 리더 확립
// 메시지 전파 (Atomic Broadcast)
public void broadcast(ZooKeeperMessage message) {
// Leader가 메시지를 PROPOSE하고, 과반수가 ACK하면 COMMIT
// 모든 서버가 동일한 순서로 메시지를 적용
}
}
Consensus 활용 사례
┌─────────────────────────────────────────────────────────────────────────────┐
│ Consensus 알고리즘 활용 분야 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 분산 키-값 저장소 │
│ ───────────────────── │
│ • etcd: Kubernetes의 서비스 검색 및 설정 관리 │
│ • Consul: 서비스 디스커버리 및 구성 관리 │
│ • ZooKeeper: Hadoop, Kafka 등의 코디네이터 │
│ │
│ 2. 데이터베이스 복제 │
│ ───────────────── │
│ • CockroachDB: Raft 기반 글로벌 분산 SQL │
│ • TiKV: TiDB의 스토어 엔진, Raft 사용 │
│ • MongoDB: 레플리카셋 리더 선출 (Paxos 유사) │
│ │
│ 3. 메시지 시스템 │
│ ───────────────── │
│ • Kafka: 파티션 리더 선출에 Zookeeper/ZooKeeper 사용 │
│ • NATS: JetStream의 메타데이터 관리 │
│ │
│ 4. 분산锁 및 분산 트랜잭션 │
│ ───────────────────────── │
│ • Redis: Redlock (Redisson 등에서 활용) │
│ • Chubby: Google's distributed lock service │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: Consensus 알고리즘은 분산 키-값 저장소, 데이터베이스 복제, 메시지 시스템, 분산锁 등에서 활용되며, 시스템의 일관성과 가용성을 보장하는 데 필수적이다.
Ⅳ. 품질 관리 및 테스트 (Quality & Testing)
Consensus 알고리즘 테스트
┌─────────────────────────────────────────────────────────────────────────────┐
│ Consensus 알고리즘 품질 테스트 항목 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ [리더 선출 테스트] │
│ ───────────────── │
│ □ 리더 장애 시 새 리더 선출 시간 측정 │
│ □ 동시 리더 선출 시도 시 충돌 해결 확인 │
│ □ 네트워크 분단 시 양쪽에서 각각 리더 선출 시 동작 확인 │
│ □ 과반수 미만의 노드가 살아남았을 때 서비스 수준 확인 │
│ │
│ [로그 복제 테스트] │
│ ───────────────── │
│ □ Leader 장애 시 복제되지 않은 로그 손실 여부 확인 │
│ □ 네트워크 지연 시 복제 순서 보장 여부 확인 │
│ □ 분단 복구 후 로그 동기화 확인 │
│ │
│ [안전성 테스트] │
│ ───────────── │
│ □ 단일 Leader 보장 여부 확인 (동시에 두 Leader가 없는지) │
│ □ 이전 Leader의 로그가 새 Leader에 올바르게 복제되는지 확인 │
│ □ Term 번호 증가에 따른 상태 전이 올바른지 확인 │
│ │
│ [종결성 테스트] │
│ ───────────── │
│ □ 정상 상황에서의 Consensus 달성 시간 측정 │
│ □ 노드 장애/복구 반복 시 시스템 정상 동작 확인 │
│ □ 대규모 노드 (7개 이상) 환경에서의 성능 및 안전성 확인 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
📢 섹션 요약: Consensus 테스트는 리더 선출, 로그 복제, 안전성, 종결성을 모두 검증해야 하며, 네트워크 분단 및 노드 장애 시나리오를 반드시 포함해야 한다.
Ⅴ. 최신 트렌드 및 결론 (Trends & Conclusion)
Raft의 진화
Raft는 원래 단일 클러스터용으로 설계되었으나, 최근에는 다중 클러스터 Consensus, 위임된 Consensus 등 확장 연구가 진행되고 있다. 또한 Raft를 기반으로 한 검증된 라이브러리(go-raft, etcd-raft 등)의成熟으로 인해 실무 적용이 더욱 쉬워지고 있다.
Byzantine Consensus
기존 Consensus 알고리즘(Paxos, Raft)는 비잔틴 장애(Byzantine Failure - 악의적이거나 잘못된 메시지를 보내는 상황)에는対応하지 않는다. Byzantine Consensus를 위해서는 PBFT (Practical Byzantine Fault Tolerance)나区块链의 합의 알고리즘(工作量证明, 권한 증명 등)이 필요하다.
결론
Consensus 알고리즘은 분산 시스템의 핵심 기반으로, Paxos와 Raft가 대표적인 알고리즘이다. Raft는 Paxos의 복잡성을 해결하여 실용성을 높였으며, etcd, Consul, CockroachDB 등 다양한 시스템에서 활용되고 있다. 시스템을 설계할 때는 이러한 Consensus 알고리즘의 동작 원리를 이해하고, 적절한 시스템을 선택해야 한다.
📢 섹션 요약: Consensus 알고리즘은 분산 시스템의 핵심 기술로, Raft와 Paxos가 대표적이며, 리더 선출과 로그 복제를 통해 시스템의 일관성을 보장한다.
핵심 인사이트 ASCII 다이어그램 (Concept Map)
┌─────────────────────────────────────────────────────────────────────────────┐
│ Consensus Algorithm Concept Map │
│ │
│ ┌───────────────────────────┐ │
│ │ Consensus Algorithm │ │
│ │ (합의 알고리즘) │ │
│ └─────────────┬─────────────┘ │
│ │ │
│ ┌─────────────┼─────────────┐ │
│ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ Raft │ │ Paxos │ │
│ │ (Strong Leader)│ │ (Leaderless)│ │
│ └───────┬──────┘ └──────┬──────┘ │
│ │ │ │
│ ┌──────┴──────┐ ┌──────┴──────┐ │
│ ▼ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Leader │ │ Log │ │ Phase 1 │ │ Phase 2 │ │
│ │Election │ │Replication│ │Prepare │ │ Accept │ │
│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │
│ │
│ 활용: etcd, Consul, CockroachDB, ZooKeeper, Kafka, TiKV │
│ 한계: 비잔틴 장애 미지원 → PBFT, 블록체인 필요 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
참고
- Consensus 알고리즘은 분산 시스템에서 Agreement, Validity, Termination의 três 속성을 만족시킨다.
- Raft는 Paxos를 실용적으로 개선한 알고리즘으로 Strong Leader 구조를 채택했다.
- Paxos는 이론적으로 완결된 원형 알고리즘이지만 복잡하여 실무 적용이 어렵다.
- Consensus 알고리즘은 네트워크 분단이나 노드 장애가 발생해도 과반수 기반 согласие 달성을 보장한다.
- FLP 불가능성 정리에 의해 完全한 비동기 환경에서는 Consensus 보장 불가능하다.