Paxos와 Raft로 설계하는 분산 합의와 리더 선출

여러 노드가 같은 상태에 도달해야 할 때

분산 합의는 비동기 네트워크와 부분 장애가 있는 환경에서 여러 노드가 하나의 값, 순서, 로그에 같은 결론을 내리게 하는 알고리즘군이다. 여기서 지켜야 할 축은 둘이다. 이미 합의한 값이 바뀌지 않고 정합성을 유지하는 Safety, 그리고 언젠가는 결정을 내리는 Liveness다.

일반적인 모델은 Crash-stop 또는 Crash-recovery 장애와 과반수 쿼럼을 전제로 한다. 비잔틴 장애는 포함하지 않는다. 비잔틴 환경이나 공개망 합의가 필요하다면 PBFT, Tendermint 등 다른 범주의 알고리즘을 검토해야 한다.

Paxos는 Proposer, Acceptor, Learner 역할을 두고 Prepare와 Accept의 2단계 절차로 단일 명령 합의에서 출발한다. 실무에서는 이를 로그 합의로 확장한 Multi-Paxos가 사용된다. Raft는 이해와 운영의 단순성을 우선한 설계로, Leader·Candidate·Follower 상태, Term, 과반수 복제, Leader Completeness와 Log Matching 규칙을 명확히 규정한다.

쿼럼이 보장하는 합의의 연속성

과반수(>N/2) 쿼럼은 서로 반드시 겹친다. 이 교집합이 리더가 교체된 뒤에도 이미 합의된 값이 유지되는 기반이 된다.

Safety를 지키려면 증가하는 라운드나 임기를 관리하고, 이전 합의에 관한 정보를 다음 라운드로 전달해야 한다. 네트워크가 분할됐을 때 소수 파티션이 쓰기를 받지 않는 것도 같은 이유다. 쓰기를 거부해 Split-brain을 막고, 과반수를 확보한 쪽만 상태를 전진시킨다.

로그를 복제하고 커밋하는 방식

리더는 요청을 선형화된 순서로 로그에 Append한 뒤, 팔로워에 복제한다. 과반수 ACK를 받으면 커밋 인덱스를 진행시키고 상태 머신에 적용한다.

Log Matching은 인덱스와 임기 쌍이 맞는지 확인하는 규칙이다. 불일치가 발견되면 뒤쪽 로그를 삭제하고 다시 동기화한다. 로그가 계속 자라는 문제는 스냅샷과 압축으로 다루며, 늦은 노드가 따라잡는 비용도 줄일 수 있다.

선출과 장애 복구가 이어지는 흐름

Election Timeout이 끝난 팔로워는 Candidate가 되어 투표를 요청한다. 과반 득표에 성공하면 리더가 되고, 실패하면 랜덤화된 타임아웃 뒤 다시 선출을 시도한다. 랜덤 타임아웃과 Pre-Vote는 동시 선출 충돌과 불필요한 다운타임을 줄이는 데 쓰인다. 리더는 Heartbeat를 보내 팔로워 상태를 유지하고 타임아웃을 리셋한다.

⤢✕

Write-Ahead Log(WAL)를 fsync하면 크래시 뒤 재시작해도 상태를 재현할 수 있다. 분할된 파티션에서는 리더가 없으면 선출을 시도하지만, 과반수를 얻지 못하면 읽기 전용 또는 차단 모드에 머문다. 리더가 바뀌어도 Leader Completeness가 이미 커밋된 항목을 유지한다.

멤버십을 바꿀 때는 Joint Consensus나 두 단계 변경으로 쿼럼 교집합을 보존한다. 스냅샷, 로그 압축, 리더 전가(transfer)는 운영 중단을 줄이고 성능을 안정화하는 수단이다. ReadIndex나 Lease Read 같은 선형화 읽기는 읽기 일관성과 지연 사이의 균형을 조절한다.

Paxos와 Raft의 설계상 차이

항목	Paxos	Raft
성능	Multi-Paxos에서 안정기 리더 중심 1RTT 커밋이 가능하나 구현 복잡도가 높다.	리더 중심 1~2RTT 커밋이며 배치·파이프라이닝이 쉽고 구현이 표준화돼 있다.
확장성	알고리즘 개념 일반화에는 강점이 있지만 멤버십 변경·스냅샷은 구현별 차이가 있다.	Joint Consensus와 스냅샷 절차가 명확해 운영 확장이 수월하다.
일관성	형식적 안전성은 강력하지만 이해 난이도가 운영 오류 리스크가 될 수 있다.	이해하기 쉬워 구현·운영 버그를 줄일 수 있고 선형화 읽기 지원도 용이하다.
안정성	리더 교체와 로그 충돌 처리에 설계 자유도가 커 구현 편차가 있다.	Heartbeat, Pre-Vote, 임기 규칙이 표준화돼 선출이 안정적이다.
운영 편의	디버깅과 문서화 난도가 높고 학습 비용이 크다.	etcd, Consul, TiKV, CockroachDB, Kafka KRaft 생태계와 관측성 측면의 이점이 있다.

합의 알고리즘이 쓰이는 자리

Raft 기반 시스템에는 구성 관리와 서비스 디스커버리의 etcd·Consul, 분산 트랜잭션 저장소인 TiKV·CockroachDB, 메타데이터 합의를 맡는 Kafka KRaft가 있다. Paxos 기반 사례로는 Google Spanner의 Per-Range Paxos, Chubby의 록 서비스, 일부 RDBMS의 그룹 커밋 레플리케이션이 있다. ZooKeeper/ZAB는 Paxos 계열 변형으로 순서 보장과 브로드캐스트 최적화를 적용한다.

분산 리더십은 etcd, Consul, ZooKeeper를 이용해 분산 락·세션·펜싱 토큰을 발급하고 단일 액티브 인스턴스를 보장하는 데 활용된다. 작업 스케줄러에서는 리더가 워크 큐를 분배하고 장애가 나면 다음 리더가 빠르게 승계한다. 스토리지에서는 샤드별 리더가 쓰기 경로를 맡고, 팔로워는 읽기와 캐치업을 담당한다.

운영 설계에서 확인할 조건

홀수 노드 구성(3·5·7)을 사용하고, 노드는 독립 장애 영역인 AZ나 랙에 분산 배치한다. Election Timeout은 예를 들어 150~300ms 범위에서 랜덤화할 수 있으며, Pre-Vote와 리더 전가(transfer)는 계획된 장애의 영향을 줄인다. WAL fsync 보장, 디스크 지연 모니터링, 스냅샷·압축 주기 최적화와 로그 길이 제한도 함께 다뤄야 한다.

CAP 관점에서 네트워크 분할은 가용성 저하를 감수하고 강한 일관성을 선택하는 상황이다. 쓰기 처리량은 과반수 ACK 때문에 상한이 형성되며, 지연 편차(p99)가 커질 수 있다. Lease Read는 시계와 네트워크 가정에 의존하므로 강건성을 별도로 검토해야 한다.

사전 설계 단계에서는 쿼럼 크기, 지연 예산, RPO/RTO를 정하고 Crash-recovery 장애 모델을 명시한다. 이후 Election·Heartbeat 타임아웃, 배치 크기, 동시 Append 파이프라인 깊이를 설정한다. 운영 중에는 프로메테우스 지표로 추가 지연, 리더 변경률, 로그 지연을 관찰하고 혼잡 제어와 백프레셔를 적용한다.

강한 일관성을 선택했을 때의 운영 효과

안정 상태의 커밋 지연은 12 RTT 범위이며, 지역망(DC 내부)에서는 210ms 수준을 달성할 수 있는 환경이 다수다. 선출 시간은 p99 500ms 이하로 구성할 수 있고, 리더 장애에 따른 중단 시간은 <1s를 목표로 설정할 수 있다.

Crash-recovery 가정에서는 RPO=0을 유지하며, 다중 장애에 대비한 스냅샷과 원격 복제는 RTO 개선에 활용된다. Raft의 명시적 규칙은 디버깅을 쉽게 하고 장애 시나리오의 예측 가능성을 높인다. 선형화 보장은 트랜잭션, 잠금, 순서 의존 업무에서 논리적 오류를 줄인다.

Raft는 이해하기 쉬운 규칙과 운영 생태계 때문에 강한 일관성이 필요한 시스템의 기본 선택지가 될 수 있다. 반면 고도의 커스터마이징이나 이론적 최적화가 필요한 워크로드라면 Multi-Paxos 체계도 고려할 가치가 있다. 어느 쪽이든 업무 특성, 지연 예산, 장애 모델을 정량화한 뒤 쿼럼·타임아웃·로그 관리 정책을 설계하고 검증해야 한다.