Paxos 알고리즘, 분산 시스템 합의를 위한 핵심 기술

Paxos는 분산 시스템에서 합의(Consensus)를 달성하기 위한 알고리즘으로, Proposer, Acceptor, Learner 세 가지 역할을 통해 작동한다. Proposer는 값을 제안하고, Acceptor는 제안된 값을 수락하며, Learner는 최종적으로 합의된 값을 학습한다. 이 과정은 두 단계로 이루어지며, Proposer는 다수 Acceptor의 승인(Majority Acceptance)을 얻어 리더십을 확보하고 값을 결정한다. 각 단계에서 Acceptor는 안정적인 저장소(Stable Storage)에 상태를 기록하여 장애 발생 시에도 데이터 일관성을 유지한다.

FLP 불가능성(FLP Impossibility) 정리는 비동기 분산 시스템(Asynchronous Distributed System)에서 합의가 불가능함을 증명한다. 하지만 Paxos는 부분 동기 시스템(Partially Synchronous System)을 가정하므로 FLP 정리를 위반하지 않는다. 부분 동기 시스템에서는 프로세스 간의 시간 동기화가 어느 정도 이루어지며, 네트워크 지연 시간에 대한 상한을 설정할 수 있다. Paxos는 이러한 환경에서 안전성을 보장하며, 비동기 환경에서도 안전성(Safety)을 유지한다.

Paxos에서 Proposer는 값을 제안하고 Acceptor로부터 승인을 받아야 한다. 여러 Proposer가 동시에 값을 제안하는 경우, 경쟁 조건(Race Condition)이 발생할 수 있다. 이를 해결하기 위해 Proposer는 고유한 제안 번호(Proposal Number)를 사용하고, 무작위 대기 시간(Random Backoff)을 적용하여 충돌을 방지한다. Proposer는 다수의 Acceptor로부터 승인을 얻어야 하며, 승인되지 않을 경우 제안 번호를 증가시켜 다시 시도한다. 이러한 메커니즘을 통해 시스템의 가용성(Availability)을 높인다.

Acceptor는 Proposer로부터 제안을 받고, 제안 번호를 기반으로 값을 수락한다. Acceptor는 promised_num, accepted_num, accepted_value와 같은 상태 변수를 관리하며, 각 상태 변화는 안정적인 저장소(Stable Storage)에 기록된다. 이러한 상태 관리는 Acceptor의 장애 발생 시에도 데이터의 일관성을 보장하며, 시스템의 내결함성(Fault Tolerance)을 높인다. 특히, fsync()를 통해 디스크에 데이터를 즉시 기록하여 데이터 손실을 방지한다.

단일 값에 대한 합의를 넘어, Paxos는 Multi-Paxos로 확장되어 여러 값의 순서를 결정할 수 있다. Multi-Paxos는 여러 Paxos 인스턴스를 실행하여 순차적인 합의를 달성한다. Raft 알고리즘은 Multi-Paxos의 대안으로, Paxos보다 이해하기 쉽도록 설계되었다고 평가받는다. Raft는 리더 선출(Leader Election), 로그 복제(Log Replication) 등의 메커니즘을 통해 합의를 달성하며, Paxos보다 구현 및 유지보수가 용이하다는 장점이 있다.