Paxos로 명령 로그를 계속 기록하려고 합니다. Multi-Paxos는 반복 비용을 어떻게 줄이며 리더가 바뀌면 무엇을 이어받나요?

단일 Paxos는 한 슬롯의 값을 선택하는 절차이고 로그는 슬롯마다 합의를 반복합니다. Multi-Paxos는 안정 리더가 높은 ballot에 대해 한 번 prepare 약속을 얻고 그동안 여러 슬롯의 accept를 진행해 매 슬롯 prepare 비용을 줄입니다. 각 슬롯에는 여전히 하나의 값만 선택됩니다.

리더 교체

새 리더는 acceptor 응답에서 이미 chosen이거나 높은 ballot으로 수락된 값을 보존해야 합니다. 빈 슬롯을 임의 명령으로 덮지 않고 필요하면 no-op으로 채워 상태 머신이 순서를 유지하게 합니다. 12가 10보다 먼저 선택돼도 적용은 10·11·12 순서여야 합니다.

안정 리더는 진행을 돕지만 Paxos 규칙을 대신하지 않습니다. client 재전송은 논리 ID·sequence로 멱등 처리하고 외부 효과는 별도 경계로 둡니다. pipeline·경쟁 proposer·지연 accept·leader 교체·learner 단절을 주입해 안전성과 진행성을 따로 검사합니다.

prepare를 재사용하는 전제

리더는 자신이 사용할 ballot에 대해 필요한 슬롯 범위의 약속과 기존 수락 정보를 얻어야 합니다. 다른 proposer가 더 높은 ballot으로 약속을 받아 가면 옛 리더의 accept는 거절됩니다. 안정 리더라는 운영 기대만으로 prepare를 생략하는 것이 아니라 acceptor의 지속된 약속이 그 ballot을 지지한다는 조건을 재사용합니다. 각 슬롯은 독립적으로 하나의 값을 선택하지만 여러 슬롯을 pipeline으로 제안할 수 있습니다.

리더 변경 시 새 리더는 응답한 쿼럼의 수락 기록에서 슬롯별 가장 높은 ballot의 값을 이어받습니다. 이미 chosen인지 알 수 없는 수락값도 임의로 지우지 않습니다. 과반에서 이전 선택을 모를 수 있는 것이 아니라, 새 리더가 그 선택 여부를 완전히 알지 못해도 안전하도록 이 규칙이 필요합니다. 어떤 수락도 없는 슬롯에는 새 명령이나 no-op을 제안할 수 있습니다.

선택 순서와 적용 순서

슬롯 12가 먼저 chosen이 되고 슬롯 11이 아직 비어 있을 수 있습니다. 상태 머신은 10까지 적용한 뒤 12를 먼저 실행하지 않고 11을 복구하거나 안전한 no-op으로 채운 뒤 순서대로 진행합니다. chosen은 과반이 수락한 사실, learned는 그 사실을 관찰자가 안 상태, applied는 명령이 상태에 반영된 상태입니다. 클라이언트에 어떤 단계에서 어떤 성공을 반환하는지 계약으로 명시해야 합니다.

클라이언트가 응답을 잃고 같은 요청을 다시 보내면 다른 슬롯에 재요청이 들어갈 수 있습니다. 요청 ID와 결과를 상태 머신에 함께 보관해 중복 효과를 막고, 스냅샷에도 이 정보를 포함합니다. 외부 결제·메일은 상태 머신의 결정적 계산과 분리해 멱등 키·outbox로 다루겠습니다.

경쟁 proposer가 계속 높은 ballot을 내면 안전성은 유지해도 진행이 지연될 수 있습니다. 안정 리더·선거 지연·백오프는 진행성을 돕는 장치입니다. 테스트는 옛 리더의 늦은 accept, 새 리더 준비 중 중단, 빈 슬롯, learner 재접속에서 슬롯별 단일 선택과 순차 적용을 검사하겠습니다.