Paxos와 Raft

Paxos와 Raft는 가장 영향력 있는 실제 합의 프로토콜 두 가지로, 실제 조정 시스템의 기반이 되는 복제된 로그에 대해 충돌-내결함성(crash-fault-tolerant) 합의를 제공합니다.

Definition

Paxos와 Raft는 쿼럼 기반 프로토콜로, 복제본 집합이 충돌 실패에도 불구하고 순서가 지정된 명령 시퀀스(복제된 로그)에 합의할 수 있도록 하며, 대다수의 복제본이 가용성을 유지하는 한 커밋된 항목이 손실되거나 재정렬되지 않도록 보장합니다.

Scope

이 주제는 Paxos 계열—단일 결정 Paxos(single-decree Paxos), 다중 Paxos(Multi-Paxos) 및 그 공학적 개선 사항—과 Raft 프로토콜을 다룹니다. Raft는 이해도를 높이기 위해 명시적인 리더, 로그 복제, 그리고 멤버십 변경을 중심으로 동일한 보장을 재구성합니다. 제안자/수락자(proposers/acceptors) 및 리더/팔로워(leaders/followers)의 역할, 쿼럼 교차(quorum intersection), 리더 선출 및 임기(terms), 로그 매칭(log matching), 그리고 스냅샷 및 재구성의 실제적인 문제들을 다룹니다.

Core questions

• 쿼럼 교차와 제안 번호 지정은 어떻게 라운드와 리더 변경 전반에 걸쳐 Paxos를 안전하게 유지합니까?
• Raft는 합의를 리더 선출, 로그 복제, 그리고 안전성으로 어떻게 분해합니까?
• 이러한 프로토콜을 실제 운영 시스템으로 전환할 때 어떤 공학적 문제들이 발생합니까?

Key theories

단일 결정 Paxos 및 다중 Paxos

Paxos는 단조롭게 증가하는 제안 번호와 다수 쿼럼에 의해 제어되는 준비(prepare) 및 수락(accept) 단계를 통해 하나의 값에 대한 합의에 도달합니다. 다중 Paxos는 안정적인 리더가 이끄는 결정 스트림 전반에 걸쳐 준비 단계를 상각하여 복제된 로그를 구축합니다.

Raft의 분해

Raft는 임기당 단일 리더를 선출하고, 리더가 팔로워가 복제하는 항목을 추가하며, 로그 매칭 속성을 강제함으로써 Paxos와 동일한 안전성을 달성합니다. 이는 최소성(minimality)을 이해도와 구현 용이성과 의도적으로 교환한 것입니다.

명세에서 실행 시스템으로

실제로 Paxos를 배포하려면 디스크 오류, 리더 임대(leader leases), 로그 압축(log compaction), 재구성(reconfiguration) 등을 처리해야 합니다. 이는 원래 알고리즘에서는 종종 간과되었지만 정확성과 성능에 필수적인 세부 사항입니다.

Clinical relevance

Paxos와 Raft는 널리 사용되는 조정 서비스, 분산 데이터베이스 및 구성 저장소 내에서 실행됩니다. 이를 이해하는 것은 실패를 통해 복제본을 강력하게 일관되게 유지해야 하는 모든 시스템을 구축하거나 운영하는 데 필수적입니다.

History

Lamport는 1998년 그의 '파트타임 의회(part-time parliament)' 논문에서 Paxos를 설명했고, 2001년 'Paxos made simple'에서 이를 명확히 했습니다. Chandra와 동료들은 2007년에 대규모 환경에서 이를 구현하는 실제적인 문제들을 보고했으며, Ongaro와 Ousterhout는 2014년에 Raft를 도입하여 동등한 보장을 훨씬 쉽게 가르치고 구현할 수 있도록 했습니다.

Debates

합의 프로토콜에서 이해도 대 최소성

Raft는 Paxos보다 이해하기 쉽도록 명시적으로 설계되었으며, 이는 추가적인 구조(강력한 리더)가 유연성을 희생하는지에 대한 논쟁을 촉발했습니다. 지지자들은 이해도가 구현 버그를 줄인다고 주장하는 반면, 다른 이들은 Paxos 변형이 더 일반적일 수 있다고 지적합니다.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos와 Raft는 근본적으로 다른 알고리즘입니까?

아닙니다. 이들은 동일한 문제에 대해 동일한 다수 쿼럼 핵심과 동등한 안전성 보장으로 해결합니다. Raft는 주로 강력한 리더와 명시적인 로그를 중심으로 Paxos를 재구성하여 프로토콜을 더 쉽게 이해하고 구현할 수 있도록 합니다.