Paxos는 Leslie Lamport가 1989년 제안한 분산 합의 알고리즘으로, 네트워크 실패와 노드 장애 환경에서 여러 서버가 단일 값에 합의할 수 있음을 수학적으로 증명했다. 이론적 토대로서 BigTable, Chubby, Zookeeper 등의 기반이 됐다.
3가지 역할
Proposer: 값을 제안하는 역할
Acceptor: 제안을 수락/거부하는 역할 (합의 정족수 구성)
Learner: 합의된 값을 학습하는 역할
실제로는 한 노드가 여러 역할을 동시에 수행
2단계 프로토콜
Phase 1 - Prepare/Promise
Proposer → Acceptors: Prepare(n) [n = 제안 번호]
Acceptor 처리:
if n > 이전에 응답한 최대 번호:
Promise(n, 이미 수락한 값이 있으면 반환)
else:
무시 또는 거부
Proposer: 과반수 Promise 수신 시 Phase 2 진행
Phase 2 - Accept/Accepted
Proposer → Acceptors: Accept(n, v)
[v = Phase 1에서 반환된 값 중 가장 높은 번호의 값, 없으면 자신의 값]
Acceptor 처리:
if n >= 이전에 응답한 최대 번호:
Accepted(n, v) 응답, 값 저장
else:
거부
Proposer: 과반수 Accepted → 합의 완료
Learner: 과반수 Accepted 확인 후 값 학습
Paxos가 어려운 이유
- 1.다수의 Proposer: 여러 제안자가 동시에 경쟁 가능 (Livelock)
- 2.로그 연속성: 각 슬롯마다 독립적 합의 → Multi-Paxos로 해결
- 3.멤버십 변경: 노드 추가/제거 처리 복잡
- 4.실제 구현 복잡성: 논문과 실제 구현 간 많은 간격
Multi-Paxos
Basic Paxos: 단일 값 합의
Multi-Paxos: 로그 항목 시퀀스에 Paxos 반복 적용
최적화:
- 안정적 리더 선출 → Phase 1을 한 번만 수행
- 이후 Phase 2만 반복 → Raft와 유사해짐
Paxos 변형
| 변형 | 특징 |
|---|
| Multi-Paxos | 로그 시퀀스 합의 |
| Fast Paxos | 2단계 → 1단계 (특정 조건) |
| Byzantine Paxos | 악의적 노드 허용 |
| Cheap Paxos | 최소 구성원으로 동작 |
관련 개념
