Paxos
1. Paxos
- 팩소스(Paxos)는 신뢰할 수 없는 프로세서들의 네트워크에서 합의 문제를 해결하기 위한 알고리즘입니다.
- 팩소스 알고리즘의 핵심은 분산 시스템에서 여러 문제가 발생하더라도 하나의 값을 도출할 수 있도록 합의하는 것입니다.
- 여기서 하나의 값은 시스템 내 모든 노드가 동의해야 하는 특정 데이터나 결정을 의미합니다.
- 팩소스 알고리즘은 여러 단계의 통신을 거쳐 각 노드가 하나의 값으로 일치할 수 있도록 합의하는 프로토콜을 사용하여 궁극적으로 분산 시스템이 안전적으로 동작할 수 있도록 합니다.
2. 구성요소
Paxos 프로토콜은 프로세서의 행동을 5가지 역할(클라이언트, 제안자, 수락자, 학습자, 리더)에 따라 정의합니다.
역할의 결합
일반적인 구현에서 단일 프로세서는 하나 이상의 역할을 동시에 수행할 수 있습니다. 이는 프로토콜의 정확성에 영향을 미치지 않으며, 일반적으로 메시지 지연이나 횟수를 최적화하기 위해 역할을 결합합니다.
예를 들어, 하나의 서버가 제안자와 수락자 역할을 동시에 수행할 수 있습니다.
2.1 Client (클라이언트)
- 클라이언트는 분산 시스템에 요청을 게시하고 응답을 기다리는 역할을 합니다.
- 분산 시스템 외부에서 요청을 시작하는 주체
- 요청이 처리될 때까지 대기
- 최종적으로 학습자로부터 응답을 받음
- 예시:
- 분산 파일 서버에서 파일 쓰기 요청
- 분산 데이터베이스에서 트랜잭션 요청
- 분산 락 시스템에서 락 획득 요청
2.2 Proposer (제안자)
- 제안자는 클라이언트를 대변하여 합의 프로세스를 주도하는 역할을 합니다.
- 클라이언트 대변: 클라이언트의 요청을 받아 수락자에게 전달
- 제안 생성: 합의해야 할 값을 제안하고 시스템 내 다른 노드에 전파
- 설득 시도: 수락자들이 제안을 수용하도록 설득
- 중재자 역할: 충돌이 발생할 경우 프로토콜을 진전시키기 위해 중재
제안자의 중요성
제안자는 단순히 제안만 하는 것이 아니라, 여러 제안자 간 충돌이 발생했을 때 이를 조정하고 프로토콜이 계속 진행되도록 하는 핵심 역할을 수행합니다.
2.3 Acceptor (수락자/유권자)
- 수락자는 프로토콜의 **장애 허용 "메모리"**로 동작하며, 제안을 수락하거나 거부하는 역할을 합니다.
- 제안 검토: 제안자로부터 받은 제안을 검토하고 수락 여부 결정
- 상태 저장: 수락한 제안을 영구적으로 저장 (장애 허용을 위해)
- 응답 전송: 제안에 대한 수락/거부 응답을 제안자와 학습자에게 전송
쿼럼 (Quorum)
- 수락자들의 집합을 **쿼럼(Quorum)**이라고 부릅니다. Paxos 프로토콜의 핵심 원칙:
- 제안자가 보낸 메시지는 반드시 수락자들의 쿼럼에 보내져야 함
- 쿼럼의 수락자로부터 받은 응답만 유효함
- 쿼럼 외 수락자로부터 받은 메시지는 무시됨
예시: 5개의 수락자가 있는 경우
- 쿼럼 크기: 최소 3개 (과반수)
- 제안이 합의되려면: 최소 3개 수락자의 동의 필요
- 장애 허용: 최대 2개 수락자 장애 발생 시에도 동작 가능
왜 쿼럼인가?
쿼럼을 사용하면:
- 일부 수락자가 장애 상태여도 시스템이 계속 동작
- 과반수 이상의 동의를 통해 일관성 보장
- 네트워크 파티션 상황에서도 안전성 유지
2.4 Learner (학습자)
- 학습자는 프로토콜의 응답 요소로 행동하며, 합의된 값을 최종적으로 실행하는 역할을 합니다.
- 합의 감지: 제안이 수락자들에 의해 합의되었는지 확인
- 값 실행: 합의된 요청을 실제로 실행
- 응답 전송: 클라이언트에게 실행 결과를 응답
- 가용성 향상: 추가적인 학습자를 배치하여 처리 가용성 증대 가능
동작 흐름:
1. 클라이언트 요청이 수락자 쿼럼에 의해 합의됨
2. 학습자가 합의 사실을 감지
3. 학습자가 요청을 실행 (예: 파일 쓰기, DB 업데이트)
4. 학습자가 클라이언트에게 응답 전송
학습자 복제
학습자는 여러 개 배치할 수 있습니다:
- 학습자 A가 장애 발생 → 학습자 B가 계속 서비스
- 읽기 부하 분산 가능
- 합의 프로세스 자체에는 참여하지 않으므로 자유롭게 추가 가능
2.5 Leader (리더)
- 리더는 식별 가능한 제안자로, Paxos의 진행을 보장하는 역할을 합니다.
- 프로토콜 진행 보장: Paxos는 리더가 선택되어야만 진행이 보장됨
- 제안 조정: 모든 제안을 리더를 통해 조정하여 충돌 최소화
- 성능 최적화: 단일 리더가 있으면 제안 충돌이 없어 빠르게 합의 가능
리더의 필요성
- 리더가 하나일 때: 프로토콜이 효율적으로 진행됨
- 리더가 여럿일 때: 여러 프 로세스가 자신이 리더라고 믿으면 지속적으로 충돌하는 업데이트를 제안하여 프로토콜이 지연될 수 있음
리더 충돌 시에도 안전성 유지
여러 프로세스가 동시에 리더라고 믿더라도:
- 안전성(Safety)은 유지됨: 잘못된 합의는 발생하지 않음
- 활성(Liveness)은 저하됨: 합의 도달이 지연될 수 있음
즉, 시스템의 정확성은 보장되지만 성능이 저하됩니다.
2.6 역할 간 관계
클라이언트
↓ (요청)
제안자 ←--→ 리더 (제안 조정)
↓ (제안)
수락자(쿼럼) ←→ 수락자(쿼럼)
↓ (합의 통보)
학습자
↓ (응답)
클라이언트
전체 흐름:
- 클라이언트가 요청을 제안자에게 전달
- **리더(제안자)**가 제안을 생성하여 수락자 쿼럼에 전송
- 수락자들이 제안을 검토하고 수락/거부 결정
- 쿼럼이 제안을 수락하면 합의 완료
- 학습자가 합의를 감지하고 요청 실행
- 학습자가 클라이언트에게 응답 전송