Paxos 알고리즘의 이해와 구현

반응형

Paxos 알고리즘은 분산 시스템에서 하나의 값에 대해 여러 노드 간의 합의를 이끌어내기 위해 고안된 대표적인 합의(consensus) 프로토콜입니다. 네트워크 지연, 메시지 손실, 노드 장애와 같은 분산 환경의 불확실성 속에서도 시스템의 일관성을 보장하려는 목적을 가지고 있으며, 제안자(Proposer), 승인자(Acceptor), 학습자(Learner)라는 세 가지 역할이 핵심적으로 작용합니다. 아래에서는 Paxos 알고리즘의 기본 원리, 특징, 그리고 유사 알고리즘(Raft, Multi-Paxos 등)과의 비교를 통해 심도 있는 분석을 진행합니다.

1. Paxos 알고리즘의 기본 원리

Paxos는 합의 형성을 위해 두 개의 주요 단계로 동작합니다.

• Prepare 단계:
  제안자는 고유한 제안 번호를 생성한 후, 모든 승인자에게 prepare 메시지를 전송합니다. 승인자들은 이미 약속한(프로미스) 제안 번호보다 작은 번호의 요청만 수락할 수 있으며, 이전에 수락한 값이 있다면 그 정보를 제안자에게 회신합니다. 이를 통해 최신의 제안 정보를 공유받아 일관성 있는 선택이 가능해집니다.
• Accept 단계:
  준비 단계의 결과를 바탕으로 제안자는 최종적으로 합의할 값을 결정하여 승인자에게 accept 메시지를 보냅니다. 승인자들은 자신이 약속한 조건과 부합하는지 확인한 후 값을 수락합니다. 다수의 승인자(보통 전체의 과반수)로부터 수락을 받으면 합의가 확정되며, 학습자에게 최종 값이 전달됩니다.

2. Paxos의 주요 특징

• 장애 허용성 및 내결함성:
  Paxos는 네트워크 지연, 노드 실패와 같은 장애 상황에서도 일부 노드만 참여해도 합의를 이끌어낼 수 있어 높은 내결함성을 제공합니다.
• 동시성 제어:
  여러 제안자가 동시에 제안을 시도할 수 있으나, 고유한 제안 번호 체계와 prepare 단계의 조율을 통해 충돌을 최소화합니다.
• 안정성 보장:
  한 번 합의된 값은 변경되지 않으며, 추후 새로운 제안에도 기존 합의 값이 반영되는 특성이 있습니다.
• 복잡성:
  Paxos의 이론은 매우 견고하지만, 실제 구현에서는 네트워크 통신, 메시지 순서 보장, 타임아웃 등의 세부 사항을 처리해야 하므로 구현 난이도가 높습니다.

3. 유사 알고리즘과의 비교 및 대조

• Multi-Paxos:
  Paxos를 다수의 값에 적용하기 위한 확장 버전입니다. 최초의 합의 후 리더를 선출하여 후속 합의 과정을 단순화하고 효율성을 높입니다. Multi-Paxos는 반복적인 합의 프로세스에서 발생하는 오버헤드를 줄여 실제 분산 시스템에 적용하기 적합합니다.
• Raft 알고리즘:
  Raft는 Paxos의 복잡성을 개선하기 위해 고안된 합의 알고리즘입니다. Raft는 리더 선출 과정을 명확하게 정의하고 로그 복제를 통해 합의를 이끌어내며, 이해와 구현이 상대적으로 쉽다는 장점이 있습니다. 반면, Paxos는 이론적으로 더 견고하지만 복잡성이 높아 실무에서 직접 구현하기에 도전적입니다.
• Viewstamped Replication:
  이 알고리즘 역시 합의를 위해 리더 선출과 복제 과정을 활용하는 방식으로, Paxos와 Raft와 유사한 목적을 가지고 있으나, 구현 방식과 실패 복구 메커니즘에서 차이가 있습니다.

4. 코드 예제: Java와 Python을 통한 Paxos 시뮬레이션

아래의 코드는 Paxos 알고리즘의 핵심 동작을 단순화한 예제로, 개념 증명을 위한 목적으로 prepare와 accept 단계를 구현하였습니다.

Java 코드 예제

import java.util.ArrayList;
import java.util.List;

class Acceptor {
    private int promisedProposalId = -1;
    private int acceptedProposalId = -1;
    private String acceptedValue = null;

    // Prepare 요청에 응답
    public boolean prepare(int proposalId) {
        if (proposalId > promisedProposalId) {
            promisedProposalId = proposalId;
            return true;
        }
        return false;
    }

    // Accept 요청에 응답
    public boolean accept(int proposalId, String value) {
        if (proposalId >= promisedProposalId) {
            acceptedProposalId = proposalId;
            acceptedValue = value;
            return true;
        }
        return false;
    }

    public String getAcceptedValue() {
        return acceptedValue;
    }
}

class Proposer {
    private int proposalId;
    private String proposalValue;
    private List<Acceptor> acceptors;

    public Proposer(int proposalId, String proposalValue, List<Acceptor> acceptors) {
        this.proposalId = proposalId;
        this.proposalValue = proposalValue;
        this.acceptors = acceptors;
    }

    public boolean runPaxos() {
        int prepareCount = 0;
        // Prepare 단계: 다수의 승인자로부터 prepare 응답 확인
        for (Acceptor acc : acceptors) {
            if (acc.prepare(proposalId)) {
                prepareCount++;
            }
        }
        // 과반수 이상의 승인을 확인해야 합의 진행
        if (prepareCount <= acceptors.size() / 2) {
            System.out.println("Prepare 단계 실패: 과반수 승인 불가");
            return false;
        }
        int acceptCount = 0;
        // Accept 단계: 제안 값을 승인자에게 전송
        for (Acceptor acc : acceptors) {
            if (acc.accept(proposalId, proposalValue)) {
                acceptCount++;
            }
        }
        if (acceptCount > acceptors.size() / 2) {
            System.out.println("Paxos 합의 완료. 최종 값: " + proposalValue);
            return true;
        }
        System.out.println("Accept 단계 실패: 과반수 미달");
        return false;
    }
}

public class PaxosSimulation {
    public static void main(String[] args) {
        List<Acceptor> acceptors = new ArrayList<>();
        // 5명의 승인자 생성
        for (int i = 0; i < 5; i++) {
            acceptors.add(new Acceptor());
        }
        // 제안자 생성 및 합의 실행
        Proposer proposer = new Proposer(100, "ConsensusValue", acceptors);
        boolean result = proposer.runPaxos();
        System.out.println("합의 결과: " + (result ? "성공" : "실패"));
    }
}

Python 코드 예제

class Acceptor:
    def __init__(self):
        self.promised_proposal_id = -1
        self.accepted_proposal_id = -1
        self.accepted_value = None

    def prepare(self, proposal_id):
        if proposal_id > self.promised_proposal_id:
            self.promised_proposal_id = proposal_id
            return True
        return False

    def accept(self, proposal_id, value):
        if proposal_id >= self.promised_proposal_id:
            self.accepted_proposal_id = proposal_id
            self.accepted_value = value
            return True
        return False

class Proposer:
    def __init__(self, proposal_id, proposal_value, acceptors):
        self.proposal_id = proposal_id
        self.proposal_value = proposal_value
        self.acceptors = acceptors

    def run_paxos(self):
        prepare_count = 0
        for acc in self.acceptors:
            if acc.prepare(self.proposal_id):
                prepare_count += 1
        if prepare_count <= len(self.acceptors) // 2:
            print("Prepare 단계 실패: 과반수 승인 불가")
            return False
        accept_count = 0
        for acc in self.acceptors:
            if acc.accept(self.proposal_id, self.proposal_value):
                accept_count += 1
        if accept_count > len(self.acceptors) // 2:
            print("Paxos 합의 완료. 최종 값:", self.proposal_value)
            return True
        print("Accept 단계 실패: 과반수 미달")
        return False

# 테스트 코드 예제
if __name__ == "__main__":
    acceptors = [Acceptor() for _ in range(5)]
    proposer = Proposer(100, "ConsensusValue", acceptors)
    result = proposer.run_paxos()
    print("합의 결과:", "성공" if result else "실패")

5. 결론

Paxos 알고리즘은 분산 환경에서 데이터 일관성과 신뢰성을 보장하기 위한 핵심 메커니즘으로, 복잡한 실패 시나리오에서도 안정적인 합의를 도출할 수 있도록 설계되었습니다. 그 복잡성으로 인해 실제 구현에서는 Multi-Paxos나 Raft와 같이 단순화된 변형이 널리 사용되기도 하지만, Paxos의 이론적 기반은 여전히 분산 시스템 연구와 실무에 큰 영향을 미치고 있습니다. 각 알고리즘은 상황에 따라 장단점이 존재하므로, 시스템 설계 시 요구되는 확장성, 장애 복구, 이해도 등을 고려하여 적절한 합의 알고리즘을 선택하는 것이 중요합니다.

위의 예제 코드는 Paxos의 핵심 개념을 이해하고 시뮬레이션할 수 있도록 도와주며, 실제 분산 시스템에서는 추가적인 네트워크 통신, 동기화, 타임아웃 관리 등의 요소를 고려해야 합니다. 이를 통해 Paxos의 복잡성을 완화하고, 시스템 전체의 안정성과 확장성을 보장할 수 있는 기반을 마련할 수 있습니다.