해당 내용은 2025년 02월 5일 'Ceph Code Walkthruogh 2.0' 에서 '이*규'님께서 발표한 '[6차] paxos 알고리즘' 에 대한 내용을 정리한 내용입니다. ceph에 관련된 내용을 공부하고 싶다면 연락부탁드립니다.

Paxos 의 어원

래슬리 램포트(Leslie Lamport)가 1989년에 이 알고리즘을 제안하면서, 논문 제목을 "The Part-Time Parliament"(시간제 의회)라고 지었는데, 여기서 Paxos 섬의 의회(Parliament) 가 등장합니다.

어원의 배경

• 램포트는 Paxos 알고리즘을 설명하기 위해 그리스 Paxos 섬에서 운영되던 의회(Parliament)를 기반으로 한 이야기를 만들었습니다.
• 이 의회의 의원들이 일정하지 않은 시간에 참여(Part-Time) 하는 상황에서도 의사 결정을 내릴 수 있어야 했습니다. 지각한 의원이 가져온 의제가 이미 결정됬거나 아예 참석하지 않는 의원들이 존재할 수 있는 상황이 발생합니다.
• 그래서 누구든 해당 안건에 대한 임시 의장(Proposer)이 되어 참석한 의원들에게 의사결정을 묻고 참석인원이 모두 동의했다면, 의제를 완료시키고 임시의장에서 물러닙니다.
• 이와 비슷하게 Paxos 알고리즘도 분산 시스템에서 노드들을 제안자, 수락자 또는 학습자로 부분적으로 참여시켜 일관된 합의를 이끌어내는 특징을 가집니다.

하지만 이 가상의 배경 이야기가 너무 복잡해서 연구자들이 이해하는 데 어려움을 겪었고, 이후 램포트는 1998년에 "Paxos Made Simple" 논문을 발표하며 더 직관적으로 설명했습니다.

즉, Paxos 알고리즘의 어원은 그리스 Paxos 섬에서 유래되었으며, "부분적으로 참여하는 의회"라는 개념에서 출발한 것입니다.

Paxos 알고리즘

분산 시스템에서 합의(Consensus) 를 이루기 위한 알고리즘으로, 충돌 없이 하나의 값이 선택되도록 보장하는 것이 핵심입니다.

1. 역할(Role) 정의

• Proposer(제안자): 합의할 값을 제안하는 역할
• Acceptor(수락자): Proposer의 제안을 수락하고 합의할 값을 결정하는 역할
• Learner(학습자): 최종 결정된 값을 학습하는 역할

Paxos 알고리즘 과정

1단계: Prepare Phase (제안 준비 단계)

1. Proposer는 제안 번호(N)와 함께 Prepare 요청을 Acceptor에게 보낸다.
2. Acceptor는 다음을 수행한다.
   • 이전에 응답한 제안이 없다면, 해당 제안(N)을 기억하고 응답한다.
   • 이전에 더 큰 제안을 수락한 적이 있다면, 기존 값과 함께 거절한다.

2단계: Accept Phase (제안 수락 단계)

1. Proposer는 다수의 Acceptor로부터 Prepare 응답을 받으면, 가장 높은 제안 번호(N)로 Accept 요청을 보낸다.
2. Acceptor는 다음을 수행한다.
   • 제안 번호(N)가 자신이 응답한 최대 번호보다 크거나 같다면 제안을 수락하고 다른 Acceptor에게 전달한다.
   • 그렇지 않다면 거절한다.

3단계: Learn Phase (학습 단계)

1. 다수의 Acceptor가 동일한 값을 Accept하면 합의가 완료된다.
2. Learner는 다수의 Acceptor로부터 값을 받아 최종적으로 결정된 값을 학습한다.

Paxos 알고리즘을 다룬 이유

1. 합의 알고리즘의 근본적인 개념을 다룸
2. 다음 포스팅인 ceph에서 사용하는 Multi-Paxos를 위해
3. 다다음 포스팅인 raft를 위해....
4. ceph code walkthrough를 알리기 위해
5. 스터디한 기억날때 정리하기 위해