Cloudflare Meerkat과 QuePaxa 분산 합의 아키텍처 해부: 타임아웃 없는 선택적 리더 Fast Path(1 RTT)·협동 제안자(Phase 0~3)·로컬 헤징으로 WAN 정지 극복하기
2026년 11월 Cloudflare가 공개한 전역 제어 평면 합의 서비스 Meerkat과 비동기 랜덤화 합의 알고리즘 QuePaxa의 코어 아키텍처를 분석한다. Raft·Multi-Paxos의 타임아웃 폭정과 메타스테이블 선출 폭주를 우회하는 선택적 리더 Phase 0 Fast Path(1 RTT·실측 95%+), 협동 제안자 Phase 0~3 수렴 메커니즘, 클라이언트 로컬 헤징 트레이드오프, 리더 장애 시 무중단 ~65% 처리량 유지 및 로컬 Python 6대 불변식 검증을 정리한다.
Cloudflare Meerkat의 QuePaxa 분산 합의 아키텍처(선택적 리더 Fast Path와 과반수 교차 코어)를 표현한 추상 아트워크
분산 시스템에서 강한 일관성(Strong Consistency)을 보장하는 상태 머신 복제(SMR) 인프라는 보통 etcd, Consul, Apache ZooKeeper처럼 Raft, Multi-Paxos, Viewstamped Replication 기반의 단일 리더 합의 프로토콜을 사용한다. 단일 데이터센터나 가용 영역(AZ) 내부의 안정적인 저지연 네트워크에서는 이 구조가 매우 잘 동작한다. 그러나 대륙 간 광역 네트워크(WAN)와 공용 인터넷 망을 가로질러 수백 개의 에지 거점이 하나의 전역 제어 평면(Global Control Plane) 상태를 공유해야 하는 환경에서는 이야기가 완전히 달라진다. 인터넷 구간은 물리적 장애 없이도 순간적인 패킷 손실, 라우팅 우회, 지연 급등(Latency Spike)이 일상적으로 발생하며, 단일 리더의 응답이 조금만 늦어져도 전체 클러스터가 쓰기를 멈춘 채 리더 선출 타임아웃을 기다리는 구조적 병목에 갇히기 때문이다.
2026년 11월 11일 Cloudflare 엔지니어링 블로그(Choosing QuePaxa, an unusual consensus algorithm)는 실험적 전역 합의 서비스 Meerkat을 공개(2026년 7월 8일 Introducing Meerkat)한 데 이어, 왜 업계 표준인 Raft나 Multi-Paxos 대신 SOSP 2023 논문에서 제안된 이례적인 합의 알고리즘 QuePaxa를 선택해 Rust로 구현하고 있는지 상세히 해부했다. Cloudflare가 2020년 코어 네트워크 스위치 부분 장애 당시 합의 기반 시스템이 6시간 동안 80배 느려지며 쓰기 불능 상태에 빠졌던 뼈아픈 경험을 되풀이하지 않기 위해 내린 결론은, 리더와 타임아웃 기반 장애 감지기에 대한 의존 자체를 제거하는 것이었다.
핵심 판단 기준을 먼저 요약하면, QuePaxa는 정상 상태에서 '선택적 리더(Optional Leader)'를 통해 Raft/Multi-Paxos와 동일한 단일 왕복(1 RTT) Fast Path 성능을 내면서도, 리더가 느려지거나 다운되면 타임아웃 기반 리더 선출 정지 없이 나머지 제안자(Proposer)들이 즉시 협동해 합의를 계속 진행하는 비동기 랜덤화 합의 알고리즘이다. 각 제안자가 생성하는 랜덤 우선순위(Priority)와 더 높은 우선순위 제안을 발견하면 경쟁 대신 공동 전파로 전환하는 '건설적 간섭(Constructive Interference)' 덕분에 파괴적 경합(Dueling Proposers)이나 메타스테이블 선출 폭주가 발생하지 않는다. 또한 Cloudflare는 Meerkat 구현에서 클라이언트 측 짧은 로컬 헤징(Hedging) 타이머를 적용해 장애 감지기를 완전히 배제했으며, 대륙 간 실측 평가에서 전체 결정의 95% 이상을 Phase 0(1 RTT)에서 처리하고 리더 장애 구간에서도 처리량이 0%로 멈추지 않고 약 65% 수준을 유지했다. 이 글은 Cloudflare 공식 기술 블로그(Choosing QuePaxa, an unusual consensus algorithm, Introducing Meerkat)와 SOSP 2023 원 논문(QuePaxa, ACM DOI, EPFL DEDIS 구현체)을 교차 검증해 정리한 분석이며, 공개된 프로토콜 명세와 로컬 Python 6대 불변식 시뮬레이션 검증을 기준으로 설명한다.
1. 왜 WAN 전역 제어 평면에서 전통적 합의가 멈추는가
Raft와 Paxos 계열 합의 알고리즘이 WAN 환경에서 취약해지는 근본 원인은 파괴적 간섭(Destructive Interference)과 불완전한 장애 감지(Fault Detection) 두 가지가 맞물려 있기 때문이다.
- 리더 경합과 메타스테이블 선출 폭주(Metastable Failure):
- 고전 Paxos에서는 여러 Proposer가 동시에 Prepare 단계의 더 높은 Ballot 번호를 보내 서로의 Accept를 무효화하는 Dueling Proposers 현상이 발생한다. 이를 막기 위해 Multi-Paxos와 Raft는 단일 리더에게 쓰기 권한을 몰아주었다.
- 하지만 Raft에서도 리더가 다운되었다고 판단한 다수의 Replica가 동시에 Candidate로 나서 투표를 요청하면, 서로 과반수 표를 쪼개 먹으며 재선출을 무한 반복하는 현상이 생긴다. 일시적인 2초짜리 네트워크 단절이 끝난 뒤에도 연쇄 선출 충돌이 장시간 시스템 복구를 막는 메타스테이블 장애(Metastable Failure)로 번지기 쉽다.
- 비동기 네트워크에서의 '타임아웃의 폭정(Tyranny of Timeouts)':
- 분산 네트워크에서 프로세스는 원격 서버가 진짜 죽었는지, 아니면 단순히 패킷이 늦게 도착하는지 원천적으로 구별할 수 없다. 따라서 Raft는 오탐(False Positive) 선출을 피하기 위해 Election Timeout을 네트워크 RTT의 5~10배(대륙 간 WAN에서는 약 1초 이상)로 보수적으로 높게 잡는다.
- 반대로 타임아웃을 짧게 잡으면 일시적 지연 스파이크마다 불필요한 리더 선출이 터져 전체 클러스터가 멈춘다. 결국 WAN 환경에서는 "타임아웃을 길게 잡으면 실제 장애 복구가 느리고, 짧게 잡으면 오탐으로 시스템이 수시로 정지한다"는 진퇴양난에 빠진다.
2. 기존 리더 기반 합의 대비 4가지 기술 경계 및 아키텍처 비교
Raft·Multi-Paxos에서 QuePaxa(Meerkat)로 패러다임을 전환할 때 엔지니어가 명확히 구분해야 할 4가지 동작 경계는 다음과 같다:
- 안전성·진행(Liveness)을 위한 리더 필수 여부: Raft와 Multi-Paxos는 리더가 없으면 새로운 엔트리를 커밋할 수 없다. QuePaxa의 리더는 오직 1-RTT Fast Path 최적화를 위한 선택적 가속 장치일 뿐이며, 리더가 완전히 크래시되더라도 다른 모든 Proposer가 클라이언트 요청을 받아 합의를 완수한다.
- 타임아웃의 성격 (장애 감지기 vs 로컬 헤징): Raft에서 100ms WAN 지연을 두고 5ms 타임아웃을 설정하면 매 순간 선출이 터져 클러스터가 영구 마비된다. 반면 QuePaxa의 헤징(Hedging) 타임아웃은 장애 감지기가 아니므로 로컬에서 5ms 수준으로 극단적으로 짧게 설정해도 안전성을 해치거나 클러스터를 멈추지 않는다. 단지 일시적으로 병렬 Proposer 수가 늘어 대역폭 비용과 3-RTT 전환 빈도가 약간 증가할 뿐이다.
- 경합 시 상호작용 모델 (배타적 덮어쓰기 vs 협동 채택): 기존 프로토콜은 더 높은 번호의 리더/Candidate가 기존 작업을 무효화한다. QuePaxa에서는 모든 제안에 랜덤 우선순위 티켓을 부여하고, Recorder로부터 자신보다 높은 우선순위 제안을 전달받은 Proposer는 즉시 자기 제안을 접고 그 최고 우선순위 제안을 공동으로 전파(Adopt)한다.
- 라운드 실패 시 누적 작업 보존 여부: 합의 라운드가 Phase 2에서 결론을 내리지 못하더라도 Phase 3(Carry Forward)를 통해 해당 라운드에서 가장 유력했던 제안을 다음 라운드로 승계하므로, 이전 라운드의 수렴 성과가 버려지지 않고 라운드가 거듭될수록 수렴 확률이 기하급수적으로 높아진다.
| 비교 항목 | 전통적 리더 기반 합의 (Raft / Multi-Paxos) | Cloudflare Meerkat (QuePaxa 알고리즘) |
| 리더의 역할 | 안전성과 진행(Liveness)을 책임지는 필수 단일 코디네이터 | 선택적(Optional) 1-RTT 가속기 — 없어도 합의 진행 가능 |
| 정상 상태 지연 | 리더 경유 단일 왕복 (1 RTT) | Phase 0 Fast Path 기준 동일하게 1 RTT (실측 95%+ 비중) |
| 리더 장애 시 동작 | Election Timeout 만료까지 쓰기 전면 정지 (0% 처리량) | 정지 없이 Phase 1~3으로 즉시 우회 (~65% 처리량 유지) |
| 경합 해결 방식 | 투표 분산 및 Ballot 무효화 (파괴적 간섭 위험) | 랜덤 우선순위 + 최고 우선순위 공동 채택 (건설적 협동) |
| 타임아웃 제약 | WAN RTT의 5~10배 이상 필요 (오탐 시 선출 폭주) | 로컬 헤징 타임아웃 (네트워크 RTT와 무관하게 초단기 설정 가능) |
| 리더 교체 비용 | 리더 변경 시 쓰기 드레인 및 재선출 순간 중단 발생 | 무중단 동적 리더 튜닝 가능 (성능 저하 리스크 최소화) |
3. QuePaxa 4단계 합의 & Meerkat 아키텍처 심층 분석
Cloudflare Meerkat의 QuePaxa 4단계 합의 흐름(Phase 0 Fast Path, Phase 1~3 Fallback, 클라이언트 5ms 로컬 헤징, 전역 Recorders 쿼럼) 아키텍처 다이어그램
3.1 선택적 리더와 Phase 0 단일 RTT Fast Path
QuePaxa의 노드 역할은 Paxos와 유사하게 제안을 제출하는 Proposer와 중간에서 제안을 기록·전파하는 Recorder 두 가지로 나뉜다. 지정된 선택적 리더에게는 다른 어떤 비리더 Proposer도 가질 수 없는 독점적 최고 우선순위(Exclusive Maximum Priority)가 부여된다:
- Phase 0 (Propose & Adopt)에서의 즉각 결정 조건:
- 첫 번째 라운드(Round 0)에서 리더가 자신의 제안을 모든 Recorder에 브로드캐스트하고 과반수(Majority) Recorder로부터 "다른 Proposer보다 내 제안이 먼저 도착했다"는 응답을 받으면, 리더는 Phase 1~3을 거치지 않고 단 1 RTT 만에 값을 즉시 확정(Decide)한다.
- 과반수 교차(Majority Intersection)를 통한 안전성 보장:
- 리더 혼자 1 RTT 만에 결정을 내려도 안전한 이유는 임의의 두 과반수 집합은 반드시 최소 1개 이상의 Recorder를 공유한다는 쿼럼 교차 불변식 때문이다. 리더의 제안이 과반수 Recorder에 먼저 기록되었다면, 뒤늦게 진입한 어떤 Proposer가 다른 과반수 Recorder를 조회하더라도 최소 한 곳에서 리더의 최고 우선순위 제안을 마주치게 되며, 즉시 리더의 제안을 채택(Adopt)하므로 절대로 상충하는 값이 결정될 수 없다.
3.2 협동 제안자(Cooperative Proposers)와 4단계 라운드(Phase 0~3)
리더의 메시지가 지연되거나 다른 Proposer가 먼저 Recorder에 도달해 Fast Path가 막히면, 프로토콜은 별도의 복구 프로시저나 리더 선출 없이 자연스럽게 Phase 0 → 1 → 2 → 3 경로를 밟는다:
- Phase 0 (Propose & Adopt): 비리더 Proposer들은 랜덤 숫자 기반의 우선순위 티켓을 생성해 Recorder에 보내고, 과반수 응답에서 관찰된 가장 높은 우선순위 제안을 자기 제안으로 채택한다. (랜덤화는 FLP 불가능성 정리를 우회해 비동기 환경에서의 확률적 종료를 보장하기 위함이다.)
- Phase 1 (Spread): 각 Proposer가 Phase 0에서 채택한 제안을 다시 과반수 Recorder에 전파한다. Recorder는 이때까지 본 최고 우선순위를 기록해, 이후 단계에서 더 낮은 우선순위의 제안이 실수로 결정되는 것을 원천 차단한다.
- Phase 2 (Check & Decide): Proposer들은 과반수 Recorder에게 "Phase 1에서 관찰된 최고 우선순위 제안"을 질의한다. 반환된 결과가 모두 자신이 채택해 전파한 제안과 일치하면 다른 제안에 추월당하지 않았음이 증명되므로 즉시 결정(Decide, 총 3 RTT)한다.
- Phase 3 (Carry Forward): 만약 Phase 2에서 응답이 엇갈려 결정하지 못한 Proposer가 있다면, 과반수 Recorder로부터 가장 최신의 높은 우선순위 제안을 수집해 다음 라운드(Round + 1)로 승계한다. 직전 Phase 2에서 이미 누군가 값을 결정했다면 그 값이 과반수 Recorder에 남아 있으므로, Phase 3을 거친 모든 잔여 Proposer는 반드시 그 결정된 값을 승계해 다음 라운드에서 100% 합류한다. 이론상 라운드당 결정 확률은 50% 이상으로 예측되지만, 실무에서는 수렴 효과 덕분에 훨씬 빠르게 종료된다.
3.3 장애 감지기 제거와 Cloudflare의 클라이언트 측 헤징 변형
QuePaxa가 타임아웃 기반 장애 감지기를 완전히 제거할 수 있는 비결은 헤징(Hedging)에 있다. 원 논문에서는 클라이언트가 모든 Replica에 요청을 보내고 비리더 Replica들이 짧은 로컬 헤징 타임아웃만큼 대기해 리더에게 Fast Path 우선권을 양보한다. 반면 Cloudflare는 Meerkat을 구현하면서 네트워크 메시지 수를 줄이기 위해 Replica 대신 클라이언트가 헤징 타임아웃을 대기하도록 실용적으로 변형했다:
- 정상 시 클라이언트는 우선 선택적 리더에게만 요청을 보내고 짧은 로컬 헤징 윈도우(예: 5ms)를 기다린다. 리더가 빠르면 단 1개의 제안자 경로로 1 RTT에 종료된다.
- 리더가 다운되거나 패킷이 유실되어 헤징 타이머가 만료되면, 클라이언트는 1초짜리 전역 선출 타임아웃을 기다리지 않고 곧바로 나머지 백업 Proposer들에게도 요청을 팬아웃한다.
- 헤징 타이머를 짧게 잡을수록 장애 복구는 빨라지고 대역폭·경합 비용은 늘어나지만, Raft처럼 클러스터가 통째로 얼어붙는 치명적 정지는 결코 일어나지 않는다.
3.4 Cloudflare Meerkat 실측 지표와 Rust 정형 검증 과제
Cloudflare가 거의 모든 대륙에 걸친 서버로 Meerkat을 평가한 결과는 다음과 같다:
- 정상 구간 95% 이상 Fast Path 달성: 대부분의 합의 결정(95% 이상)이 리더의 Phase 0(1 RTT)에서 완료되어 안정적이고 예측 가능한 처리량을 유지했다.
- Phase 2 우회 시에도 무중단 ~65% 처리량 유지: 리더가 의도적으로 중단된 시뮬레이션에서 처리량은 0%로 멈추지 않고 기존 대비 약 65% 수준으로 완만히 감소했으며, 1분 뒤 리더가 복구되자 즉시 100%로 복귀했다(단일 3-RTT 우회 인스턴스에서는 순간적으로 최대 1/3 속도까지 저하되나 정지는 없음).
- Crash-Recovery 확장 및 정형 검증(Formal Verification): 원 QuePaxa 논문은 노드가 죽으면 영구 이탈하는 Crash-Stop 모델을 가정했으나, Cloudflare는 실서비스용으로 노드가 재시작 후 복구되는 Crash-Recovery 모델을 추가 설계하고 있다. 덜 검증된 최신 프로토콜인 만큼 Rust 구현체와 Meerkat 전체에 대해 정형 검증(Formal Verification)과 대규모 결함 주입(Fault-Injection) 시뮬레이션을 병행하고 있다.
4. 로컬 Python 6대 아키텍처 불변식 검증 스크립트
아래 Python 스크립트는 외부 패키지 없이 표준 라이브러리만으로 QuePaxa 및 Meerkat 아키텍처의 6대 핵심 불변식(① Phase 0 리더 1-RTT Fast Path 및 과반수 교차 안전성, ② 리더 부재 시 5개 동시 제안자의 랜덤 우선순위 협동 수렴, ③ 리더 장애 구간에서의 Raft 타임아웃 전면 정지 vs QuePaxa 무중단 우회 비교, ④ 비대칭 지연·경합 상황의 Phase 1~3 안전성 불변식 검증, ⑤ Meerkat 클라이언트 로컬 헤징 트레이드오프 모델링, ⑥ 다중 슬롯 상태 머신 복제 로그 및 최종 KV 상태 동일성)을 로컬에서 검증한다:
실행 결과:
5. 실무 분산 합의 및 전역 제어 평면 설계 체크리스트
배치 토폴로지 기준(LAN vs WAN) 합의 모델 구분: 단일 데이터센터나 리전 내 안정적인 망에서는 성숙한 etcd/Raft 생태계가 여전히 단순하고 강력하지만, 대륙 간 WAN 위에서 수십~수백 밀리초 지연 변동과 패킷 손실이 일상적인 전역 제어 평면이라면 타임아웃 기반 리더 선출이 유발하는 쓰기 정지 비용을 우선 측정한다.
클라이언트 헤징(Hedging) 타임아웃과 대역폭 트레이드오프 튜닝: 로컬 헤징 타이머를 과도하게 짧게 설정하면 정상 상태의 리더까지 백업 제안자와 불필요하게 경합해 3-RTT 우회 비율이 높아질 수 있으므로, 목표 Fast Path 비율(예: 95% 이상)과 목표 장애 우회 속도 사이의 p95/p99 지연 분포를 측정해 헤징 임계치를 조정한다.
선택적 리더의 지리적 배치 동적 최적화: QuePaxa는 무중단으로 리더를 바꿀 수 있으므로, 주 트래픽이 몰리는 대륙이나 Recorder 쿼럼 중심과의 RTT가 가장 짧은 노드로 선택적 리더를 동적 재배치해 1-RTT 결정 비중을 극대화한다.
Crash-Stop과 Crash-Recovery 영속화 경계 검증: 원 QuePaxa 논문 모델과 달리 프로덕션 환경에서는 노드 재부팅 후 디스크 상태 복구(Crash-Recovery)가 필수이므로, 재시작한 Recorder가 이전 라운드에서 응답한 최고 우선순위 약속을 휘발시키지 않도록 WAL/영속 스토리지 fsync 불변식을 반드시 검증한다.
정형 검증(Formal Verification) 및 결함 주입 테스트 병행: 비전통적 다단계 합의 프로토콜은 패킷 재정렬, 비대칭 파티션, 부분 크래시 조합에서 미세한 엣지 케이스가 발생할 수 있으므로 TLA+/Stateright 기반 모델 체킹과 결정론적 시뮬레이션(Simulation Testing)으로 안전성 불변식을 상시 검증한다.
6. 참고 자료 및 공식 출처 (2026-11-17 확인)
확인 기준일: November 17, 2026