Paxos 알고리즘, 평문으로 설명하면 매우 간단하다 (2021)

The Paxos algorithm, when presented in plain English, is very simple (2021)

📅 2026-03-17 📰 Lobste.rs

요약

분산 시스템의 기본 합의 문제와 가장 유명한 합의 알고리즘인 Paxos를 평문으로 설명하여, 복잡한 것으로 알려진 Paxos가 실제로는 직관적이고 이해하기 쉽다는 것을 보여준다.

핵심 포인트

합의 문제의 Agreement, Integrity, Validity, Termination의 4가지 성질 정의
FLP 불가능 정리는 완전 비동기 모델에서만 적용되며, 실제 부분 동기 분산 시스템에서는 Paxos가 작동
Paxos는 Proposer, Acceptor, Learner 세 역할로 단일 값에 대한 합의 달성

왜 중요한가

분산 시스템 개발 시 데이터 일관성과 리더 선출 등의 합의 문제를 해결하는 기초 알고리즘을 이해할 수 있다.

📄 전문 번역

평문으로 설명한 Paxos 알고리즘은 생각보다 단순합니다

분산 시스템에서 합의(Consensus)는 가장 기본이 되는 문제 중 하나입니다. 이 글에서는 합의가 무엇인지 알아보고, 가장 유명한 합의 알고리즘인 Paxos를 살펴보겠습니다. Paxos가 복잡하다는 평판과는 달리, 특히 단일 값에 대한 합의를 목표로 하는 기본 Paxos는 실제로는 매우 직관적이고 이해하기 쉬운 알고리즘입니다.

합의(Consensus) 문제란?

합의 알고리즘의 목적은 분산 시스템에서 여러 프로세스가 하나의 값에 대해 동의하도록 하는 것입니다. 합의 문제를 정의하면 다음과 같습니다.

참여자들의 그룹이 있고, 이들이 어떤 값에 대해 결정할 때 다음 속성들을 만족해야 합니다:

합의(Agreement): 모든 참여자가 결정한 값은 동일해야 합니다.

무결성(Integrity): 한 번 결정한 후에는 그 결정을 바꿀 수 없습니다.

타당성(Validity): 최종 결정 값은 참여자들이 제시한 값 중 하나여야 합니다.

종료(Termination): 결국에는 값이 결정되어야 합니다.

처음 세 속성은 안전성(Safety) 관련이고, 마지막 속성은 생존성(Liveness) 관련입니다.

합의는 분산 시스템의 많은 문제들의 근본이 됩니다. 예를 들어 리더 선출 문제는 "누가 리더인가"에 대한 합의로 축약할 수 있습니다. 또 다른 예로, 복제된 데이터 저장소에서 클라이언트들이 서로 다른 복제본에 쓰기 작업을 제출한다고 생각해봅시다. 이 경우 각 복제본들은 다음에 어떤 쓰기 작업을 수행할지에 대해 합의해야 합니다. 단계마다 다음 쓰기에 대해 합의함으로써 모든 복제본이 동일한 순서로 쓰기를 적용하도록 보장할 수 있고, 이것이 복제본들 간의 일관성을 유지하는 데 필수적입니다.

FLP 불가능성 정리

혹시 FLP 불가능성(FLP Impossibility)이라는 것을 들어본 적이 있나요? Fisher, Lynch, Paterson이 증명한 이 정리는 분산 시스템에서 합의를 달성하는 것이 불가능하다고 말합니다. 그렇다면 Paxos와 다른 합의 프로토콜들은 어떻게 합의 문제를 해결하는 걸까요?

핵심은 FLP가 매우 엄격한 조건인 완전 비동기 환경에서만 불가능함을 증명한다는 것입니다. 이 비동기 모델에서는 프로세스들이 공유된 시간 개념을 가지지 못하고, 시스템의 모든 단계가 임의로 오래 걸릴 수 있습니다. 따라서 프로세스나 네트워크가 어떤 작업을 하는 데 걸리는 시간의 상한선을 가정할 수 없습니다. 그렇기 때문에 타임아웃을 사용해 장애가 발생했다고 결론 내릴 수 없습니다.

> "우리의 증명에 결정적인 것은 처리가 완전히 비동기라는 점입니다. 즉, 프로세스의 상대적 속도나 메시지 전달 지연에 대해 어떤 가정도 하지 않습니다. 또한 프로세스가 동기화된 시계에 접근할 수 없다고 가정하므로, 타임아웃 기반의 알고리즘은 사용할 수 없습니다."

다행히 실제 시스템에서는 어느 정도의 동기성을 가정할 수 있습니다. 프로세스나 네트워크에서 어떤 작업이 걸리는 시간에 대해 합리적인 상한을 설정할 수 있거든요. 마찬가지로 노드 간에 시계 편차는 있지만, 여전히 프로세스 간에 어느 정도의 시간 개념을 공유할 수 있습니다. 모든 합의 프로토콜은 이런 부분 동기 모델을 가정하고 동작합니다.

따라서 Paxos와 다른 합의 프로토콜들이 FLP를 위반하는 것은 아닙니다. 단지 다른 환경에서 동작할 뿐입니다. FLP는 완전 비동기 분산 시스템에서 참이지만, 합의 프로토콜은 대부분의 경우 동기성 가정이 맞는 부분 동기 분산 시스템에서 동작합니다. 혹시 그 가정이 틀리는 상황이 발생하면, 보통 합의 알고리즘은 종료를 보장하지 못하지만 안전성은 항상 보장합니다. 예를 들어 Paxos에서는 제안자들이 계속 서로를 방해하면서 합의에 영원히 도달하지 못하는 상황이 발생할 수 있습니다. 하지만 실제로는 랜덤 백오프를 사용할 때 이런 상황이 발생할 확률이 극히 낮습니다.

Paxos 알고리즘

Paxos는 가장 유명한 합의 알고리즘입니다. Paxos가 복잡하다는 평판을 들어봤을 수도 있지만, 실제로는 그렇게 어렵지 않습니다. 흥미롭게도 Paxos의 발명자인 Leslie Lamport는 Paxos가 평문으로 설명하면 쉽게 이해할 수 있다는 것을 보여주기 위해 후속 논문을 발표했습니다.

Paxos에서는 제안자(Proposer), 수락자(Acceptor), 학습자(Learner) 세 가지 역할이 있습니다. 이들은 논리적 역할일 뿐 모두 같은 노드에서 실행될 수 있습니다. 실제로는 보통 한 노드가 세 역할을 모두 수행합니다.

기본 Paxos 알고리즘의 실행 과정은...

🔗 원문 보기 👍 유용해요