Paxos
Paxos은 분산 합의 알고리즘 분야에서 사용되는 대표적인 알고리즘이다. Proposer, Acceptor, Learner; 과반수 쿼럼을 중심으로 동작하며, 처리 대상은 여러 노드의 제안 값, 메시지·장애 모델이다. 주요 활용에는 분산 상태 머신과 복제 로그이 포함된다.
| 분류 | 분산 합의 알고리즘 |
|---|---|
| 설계 | Leslie Lamport |
| 공개 | 1989년 무렵 개발·1998년 논문 발표 |
| 입력 | 여러 노드의 제안 값, 메시지·장애 모델 |
| 핵심 구조 | Proposer, Acceptor, Learner; 과반수 쿼럼 |
| 성질·전제 | 충돌 제안 간 안전성, 비동기 환경에서 진행 보장에는 추가 조건 필요 |
| 활용 | 분산 상태 머신과 복제 로그 |
| 참고 자료 | 논문·공식 문서 |
Paxos은 분산 합의 알고리즘 분야에서 사용되는 대표적인 알고리즘이다. Proposer, Acceptor, Learner; 과반수 쿼럼을 중심으로 동작하며, 처리 대상은 여러 노드의 제안 값, 메시지·장애 모델이다. 주요 활용에는 분산 상태 머신과 복제 로그이 포함된다.[1]
Paxos는 분산 시스템의 여러 노드가 하나의 값을 일관되게 선택하도록 만드는 합의 알고리즘 계열이다. 제안을 보내는 proposer, 제안을 수락하는 acceptor, 선택 결과를 알아내는 learner의 역할을 구분한다. 노드가 실패하거나 메시지가 지연되어도 서로 다른 두 값이 동시에 선택되지 않도록 과반수 쿼럼의 교집합을 활용한다.
기본 Paxos에서는 proposer가 번호가 큰 제안을 준비하고 다수의 acceptor에게 이전에 수락한 제안 정보를 받는다. 충분한 응답을 모았다면 이전 수락 값이 있는 경우 번호가 가장 높은 제안의 값을 이어받아 accept 요청을 전송한다. 이 규칙은 서로 다른 라운드의 과반수 쿼럼이 겹친다는 성질과 함께 합의의 안전성을 만든다.
기본 Paxos는 단일 값의 선택 문제를 설명하며, 실용적인 복제 상태 머신에서는 Multi-Paxos와 리더·로그 관리 구조로 확장된다. 메시지 지연과 다수 proposer의 경쟁으로 실행이 계속 방해받을 수 있으므로 안전성 보장과 실제로 결론에 이르는 활성 조건을 구별한다. Raft는 더 명시적인 강한 리더와 로그 복제를 중심으로 같은 복제 합의 문제를 설명하는 다른 방식이다.[2]