Paxos 합의 알고리즘

들어가며

 Paxos는 Leslie Lamport가 1989년에 제안한 합의 알고리즘으로, 이런 환경에서도 단 하나의 값만 안전하게 결정되도록 보장한다.

Raft, Kafka(KRaft), etcd 등 현대 분산 시스템의 합의 메커니즘을 이해하려면, 그 원조인 Paxos를 먼저 이해하는 것이 중요하다.

---

해결하려는 문제

 분산 환경에서 노드들이 "이 값을 X로 하자"라고 제안할 때, 일부 노드가 다운되거나 메시지가 지연되더라도 단 하나의 값만 최종 결정되어야 한다. 두 노드가 동시에 다른 값을 제안하더라도, 시스템 전체는 반드시 하나만 선택해야 한다.

---

세 가지 역할

Paxos에는 세 가지 역할이 있으며, 하나의 노드가 여러 역할을 동시에 수행할 수 있다.

Client → Proposer → Acceptor(A, B, C) → Learner
         (값 제안)     (투표/수락)         (결과 학습)

Proposer는 클라이언트의 요청을 받아 "이 값을 합의하자"고 제안을 시작하는 역할이다.

Acceptor는 제안을 수락하거나 거부하는 투표자 역할이다. 과반수(majority)의 Acceptor가 수락해야 값이 결정된다.

Learner는 최종 결정된 값을 전달받아 학습하는 역할이다.

---

두 단계 프로토콜

Paxos는 Prepare-Promise와 Accept-Accepted 두 단계로 동작한다.

1단계: Prepare → Promise

Proposer가 고유한 제안 번호(proposal number) N을 선택하고, 모든 Acceptor에게 Prepare(N) 메시지를 보낸다. 이것은 "나 N번 제안을 하려고 하는데, 받아줄 수 있어?"라는 요청이다.

Acceptor는 N이 자신이 지금까지 본 제안 번호 중 가장 크면, 두 가지를 약속한다.

1. N보다 작은 번호의 제안은 앞으로 수락하지 않겠다.
2. 이전에 수락했던 제안이 있으면 그 정보(제안 번호와 값)를 Proposer에게 돌려준다.

이 응답이 Promise이다. 만약 N이 이미 본 번호보다 작으면, Acceptor는 무시하거나 거부한다.

Proposer                    Acceptor A, B, C
   |                              |
   |--- Prepare(N=1) ----------->|
   |                              | N=1 > 0 이므로 OK
   |<-- Promise(N=1) ------------|
   |   (이전 수락 값 없음)          |
   |   과반수 Promise 수신!        |

2단계: Accept → Accepted

Proposer가 과반수의 Acceptor로부터 Promise를 받으면, 다음 단계로 진행한다. 이때 제안할 값을 결정하는 규칙이 핵심이다.

• Promise 응답 중에 이전에 수락된 값이 있으면, 가장 높은 제안 번호에 연결된 값을 자신의 제안 값으로 사용해야 한다.
• 이전에 수락된 값이 하나도 없으면, 자신이 원래 제안하려던 값을 사용한다.

Proposer가 Accept(N, value) 메시지를 Acceptor들에게 보내고, Acceptor는 그 사이에 N보다 큰 번호의 Prepare를 받지 않았다면 이 제안을 수락한다.

과반수의 Acceptor가 수락하면, 해당 값이 **최종 결정(chosen)**된다.

Proposer                    Acceptor A, B, C
   |                              |
   |--- Accept(N=1, V="X") ----->|
   |                              | N=1이 아직 유효하므로 수락
   |<-- Accepted(N=1) -----------|
   |   과반수 Accepted!           |
   |   "X"가 최종 결정됨            |

---

충돌 시나리오: 두 Proposer가 동시에 제안할 때

정상적인 경우는 단순하지만, 핵심은 충돌이 발생했을 때 어떻게 안전성을 보장하는가이다.

시나리오: P1이 "X"를, P2가 "Y"를 제안

Step 1. P1이 Prepare(N=1)을 A, B에게 보내고 과반수 Promise를 확보한다.

Step 2. P1이 Accept(1, "X")를 보내기 전에, P2가 Prepare(N=2)를 B, C에게 보내서 과반수 Promise를 확보한다. B는 이제 N=2에 Promise했으므로 N=1 이하의 제안을 수락하지 않겠다고 약속한 상태다.

Step 3. P1이 Accept(1, "X")를 보내면, A는 수락하지만 B는 거부한다 (이미 N=2에 Promise했으므로). P1은 과반수 수락에 실패한다.

Step 4. P2가 Accept(2, "Y")를 B, C에게 보내면, 둘 다 수락한다. 과반수 달성으로 "Y"가 최종 결정된다.

시간 →

P1: Prepare(1) → A,B Promise   Accept(1,"X") → A 수락, B 거부! → 실패
P2:              Prepare(2) → B,C Promise     Accept(2,"Y") → B,C 수락 → "Y" 결정!

핵심: 제안 번호가 더 큰 쪽이 이긴다.

---

안전성의 핵심: 이전에 수락된 값 이어받기

이미 값이 결정된 후 새로운 Proposer가 나타나면 어떻게 될까?

시나리오: "Y"가 결정된 후 P3가 "Z"를 제안하려는 경우

B와 C가 Accept(2, "Y")를 수락하여 "Y"가 결정된 상태에서, P3가 Prepare(N=3)을 모든 Acceptor에게 보낸다.

각 Acceptor는 Promise와 함께 이전에 수락했던 값을 돌려준다.

• A: Promise(3) + 이전 수락 정보 (1, "X")
• B: Promise(3) + 이전 수락 정보 (2, "Y")
• C: Promise(3) + 이전 수락 정보 (2, "Y")

P3는 이 중에서 가장 높은 제안 번호(2)에 연결된 값 "Y"를 자신의 제안 값으로 사용해야 한다. 원래 "Z"를 제안하고 싶었지만, Accept(3, "Y")를 보내야 한다.

P3가 받은 Promise 응답:
  A → (1, "X")
  B → (2, "Y")
  C → (2, "Y")

규칙: max(proposal number)에 연결된 값 선택
  max = 2 → 값 = "Y"

∴ P3는 Accept(3, "Y")를 전송 → "Y"가 다시 확인됨

이 규칙이 Paxos 안전성의 핵심이다. 과반수끼리는 반드시 최소 하나의 Acceptor가 겹치기 때문에, 새로운 Proposer는 항상 이전에 결정된 값을 발견하게 된다. 한번 결정된 값은 절대 바뀌지 않는다.

---

Paxos 알고리즘의 한계

1. Livelock - Safety는 보장하지만, Liveness는 보장하지 못한다

Basic Paxos를 그대로 사용하면 트래픽이 큰 시스템에서 심각한 성능 문제가 발생한다. Proposer 간 충돌이 반복되면서 라이브락(livelock)이 발생할 수 있기 때문이다.

예를 들어 P1이 Prepare(1)로 과반수 Promise를 받고 Accept를 보내려는 순간, P2가 Prepare(2)를 보내서 Acceptor들의 약속을 덮어쓴다. P1이 실패하고 다시 Prepare(3)을 보내면, 이번엔 P2의 Accept가 거부된다. 이렇게 서로 끊임없이 상대방을 무효화하면서 아무도 값을 결정하지 못하는 상태가 반복될 수 있다.

Proposer A: prepare(n=1) → 과반 Promise 획득
Proposer B: prepare(n=2) → 과반 Promise 획득 (A의 n=1 무효화)
Proposer A: accept(n=1)  → 거절됨 → prepare(n=3) 재시도
Proposer B: accept(n=2)  → 거절됨 → prepare(n=4) 재시도
...

 

2. 성능 한계

2라운드 메시지 교환

 Basic Paxos에서 하나의 값에 합의하려면 최소 2라운드의 메시지 교환이 필요하다.

Round 1: Proposer → Acceptor  (Prepare)
         Acceptor → Proposer  (Promise)

Round 2: Proposer → Acceptor  (Accept)
         Acceptor → Proposer  (Accepted)

 각 라운드는 네트워크 왕복(RTT) 1회와 Acceptor 측의 디스크 fsync를 수반한다. 합의 한 건당 2 RTT + 2 fsync가 최소 비용이다.

Multi-Paxos에서 안정적인 Leader가 확보되면 Prepare 단계를 생략하여 1라운드로 줄일 수 있다. 하지만 Leader가 교체되면 다시 2라운드로 돌아가며, Leader 교체가 잦은 불안정한 환경에서는 이 최적화의 효과가 반감된다.

 

Proposer 충돌에 의한 Throughput 저하

 Paxos의 기본 구조에서는 모든 노드가 Proposer가 될 수 있다. 이론적으로는 유연하지만, 실제로 여러 Proposer가 동시에 활동하면 충돌이 잦아지고 재시도가 늘어나면서 throughput이 급격히 떨어진다.

 

지리적 분산 환경에서의 Latency

 Quorum 기반 알고리즘의 특성상, 과반수 응답을 기다려야 한다. 노드가 서울, 도쿄, 버지니아에 분산되어 있다면, 가장 느린 quorum 멤버의 RTT가 전체 합의 latency를 결정한다. 이 문제는 Paxos에만 국한되지 않지만, 2라운드 구조가 latency를 더 증폭시킨다.

---

해결책: Multi-Paxos과 Raft

 이 문제를 해결하기 위한 아이디어는 리더를 하나 선출하고, 리더만 Proposer 역할을 하도록 제한하는 것이다. 이 아이디어를 Paxos에 적용한 것이 Multi-Paxos이다.

 리더가 안정적으로 유지되는 동안에는 Prepare 단계를 매번 반복할 필요가 없다. 리더가 한 번 Prepare로 과반수의 Promise를 확보하면, 이후의 요청들은 Accept 단계만으로 처리할 수 있다. 2단계 프로토콜이 사실상 1단계로 줄어드는 것이다.

[Basic Paxos]
  매 요청마다: Prepare → Promise → Accept → Accepted  (2 RTT)

[Multi-Paxos (리더 안정 시)]
  최초 1회: Prepare → Promise
  이후:     Accept → Accepted  (1 RTT)

 이 구조에서는 충돌이 원천적으로 발생하지 않는다. 클라이언트 요청이 모두 리더를 통해 직렬화되기 때문이다. 리더가 다운되었을 때만 새 리더를 선출하고, 그 과정에서 잠깐의 충돌이 있을 수 있지만 정상 운영 중에는 충돌 없이 높은 처리량을 유지한다.

 

 Raft는 Multi-Paxos의 리더 중심 구조를 프로토콜 자체에 내장하면서, 리더 선출, 로그 복제, 안전성을 하나의 통합된 프로토콜로 명확하게 정의했다. "이해하기 쉬운 합의 알고리즘"을 목표로 설계되었다.

 현재 대부분의 분산 시스템은 Raft를 선택한다. etcd, Consul, CockroachDB, TiKV, Kafka(KRaft) 등이 모두 Raft 기반이다.

 

---

핵심 정리

1. Paxos는 두 단계 프로토콜이다. Prepare-Promise로 제안 권한을 확보하고, Accept-Accepted로 값을 결정한다.
2. 제안 번호가 안전성의 기반이다. 더 큰 번호의 Prepare가 오면 이전 약속이 무효화되어, 항상 최신 제안이 우선한다.
3. 이전에 수락된 값을 이어받는 규칙이 핵심이다. Promise 응답에서 가장 높은 제안 번호의 값을 사용해야 하므로, 한번 결정된 값은 절대 바뀌지 않는다.
4. 과반수의 교집합이 안전성을 보장한다. 어떤 두 과반수든 최소 하나의 Acceptor가 겹치므로, 결정된 값은 반드시 새로운 Proposer에게 전달된다.
5. Basic Paxos는 실무에서 그대로 쓰기 어렵다. 라이브락 문제 때문에 Multi-Paxos(리더 선출)로 확장하여 사용하며, Raft는 이 구조를 처음부터 프로토콜에 내장한 것이다.