본문으로 건너뛰기
02 QuePaxa와 Raft의 차이 — 선택적 리더와 hedging

02 · QuePaxa와 Raft의 차이 — 선택적 리더와 hedging

QuePaxa 논문(Tennage·Băsescu 외, SOSP 2023)과 Cloudflare 블로그 Choosing QuePaxa, an unusual consensus algorithm(2026-11-11)을 바탕으로 썼습니다. GeekNews의 소개 글에서 출발했습니다. 자료 확인 시점은 2026-11-22이며, 직접 실행한 결과는 없습니다. Raft의 동작은 1편 Raft의 리더 중심 합의에 있습니다.

선거 타임아웃에 묶인 Raft의 진행

Raft의 리더가 멈추면 선거 타임아웃이 지나고 새 리더가 선출될 때까지 쓰기가 중단됩니다. 복제본은 리더가 죽었는지 메시지만 늦었는지 구별할 수 없습니다. 타임아웃을 줄이면 정상 리더를 의심해 선거를 반복할 수 있고, 늘리면 실제 장애 뒤에도 더 오래 기다립니다.

QuePaxa 논문은 이런 의존을 “타임아웃의 폭정(tyranny of timeouts)“이라고 부릅니다. 주류 리더 기반 프로토콜이 진행을 보장하려면 메시지가 결국 일정 시간 안에 도착한다는 부분 동기 가정이 필요합니다. 동시 리더의 상호 방해와 비싼 교체 비용을 피하려고 타임아웃을 보수적으로 잡지만, 환경에 맞는 값은 사람이 정해야 합니다. 잘못 정하면 성능이 나빠지거나 진행이 멈춘다는 지적입니다. 논문은 Raft가 느리지만 타임아웃을 일으킬 만큼 느리지는 않은 리더에 계속 묶일 수 있다고도 적습니다.

Cloudflare는 지구 반대편까지의 왕복이 수백 ms이면, 선거 타임아웃을 왕복 몇 번으로 잡을 때 장애 감지에만 1초가량 걸릴 수 있다고 계산합니다. 같은 글은 Raft 같은 알고리즘이 더 작고 지역적인 네트워크에서는 대체로 잘 동작한다고도 적습니다.

선택적 리더와 우선순위에 따른 제안 채택

QuePaxa의 복제본은 제안자(proposer)와 기록자(recorder) 역할을 함께 맡습니다. 제안자는 값을 내고 결정을 주도하며, 기록자는 요청에 응답하면서 합의 상태를 보관합니다. 통신은 제안자가 기록자에게 보내는 요청과 그 응답뿐입니다. 제안자끼리는 직접 통신하지 않습니다.

Paxos에서는 동시에 나선 제안자들이 더 큰 번호를 보내 서로의 제안을 막는 파괴적 간섭이 생길 수 있습니다. QuePaxa의 제안자는 기록자의 응답에서 우선순위가 더 높은 제안을 얻으면 그것을 자기 채택안으로 삼아 전파합니다. 여러 제안자가 같은 제안의 전파를 돕는 방식이며, Cloudflare는 이를 건설적 간섭이라고 부릅니다.

우선순위는 보통 무작위 수지만, 지정 리더만 예약된 최댓값을 씁니다. 리더는 논문의 표현으로 “first among equals”, 즉 왕복 한 번에 결정하는 빠른 경로(fast path)의 특권을 가진 제안자입니다. 리더가 멈춰도 다른 제안자가 계속 진행하므로, 합의를 재개하기 위해 Raft처럼 새 리더를 먼저 뽑을 필요가 없습니다.

라운드의 네 phase와 결정 조건

로그의 자리 하나인 슬롯마다 합의 시도인 라운드를 반복합니다. 라운드는 네 단계(phase)로 구성되며, 제안자는 각 단계에서 기록자에게 요청을 보내고 과반 응답을 기다립니다.

단계제안자가 하는 일결정 가능 여부
phase 0우선순위를 붙여 제안을 보내고, 과반 응답의 첫 값 중 최고 우선순위 제안을 채택첫 라운드의 리더만. 과반이 처음 받은 제안이 모두 리더 것일 때
phase 1채택한 제안을 과반에 전파. 기록자는 해당 단계에서 본 최고 우선순위를 유지불가
phase 2과반 응답에서 phase 1의 최고 우선순위 제안을 확인응답들 중 최고 우선순위 제안이 자기 채택안과 같으면 누구든 결정
phase 3과반에서 찾은 최선의 제안을 채택불가. 다음 라운드로 넘어감

결정 지점과 다음 라운드로 이어지는 경로입니다.

QuePaxa의 한 라운드는 네 단계이며, 리더는 첫 라운드의 phase 0에서, 그 밖의 제안자는 phase 2에서 결정할 수 있습니다. phase 3까지 결정하지 못하면 채택한 제안을 들고 다음 라운드로 갑니다.
도식 텍스트
  • phase 0 — 제안하고 채택
  • phase 1 — 채택안 전파
  • phase 2 — 최고 우선순위 확인
  • phase 3 — 다음 라운드 준비
  • 결정 — 왕복 한 번
  • 결정 — 왕복 세 번
  • 과반
  • 과반
  • 불일치
  • 리더 빠른 경로
  • 채택안과 일치

phase 0의 fast path와 과반 교차

왕복 한 번의 결정은 과반 교차에 기댑니다. 어떤 두 과반도 기록자를 적어도 하나 공유하므로, 리더의 제안이 과반의 첫 값이었다면 다른 제안자가 어느 과반에 물어도 그 제안을 만나게 됩니다. 이 제안은 최고 우선순위라서 다른 제안자도 이를 채택하며, 다른 값이 결정될 수 없습니다.

리더의 제안이 과반에 먼저 도착한 fast path입니다.

리더의 제안이 기록자 과반에 가장 먼저 닿았다는 응답을 받으면, 리더는 왕복 한 번에 결정합니다.
도식 텍스트
  • 리더 제안자
  • 기록자 1
  • 기록자 2
  • 기록자 3
  1. 1. 제안(우선순위 최댓값)
  2. 1. 제안
  3. 1. 제안
  4. 2. 처음 받은 제안은 리더 것
  5. 2. 처음 받은 제안은 리더 것
  6. 과반 응답이 모두 리더 제안 · 결정
  7. 늦은 응답은 · 기다리지 않음

phase 2의 결정과 리더 없는 라운드

fast path를 놓쳐도 같은 라운드의 phase 2에서 결정할 수 있습니다. phase 0·1·2의 왕복을 세면 세 번입니다. phase 3에서 제안을 채택하는 절차는 앞선 결정을 보존합니다. 누군가 이미 결정했다면 그 제안이 기록자 과반에 남아, 나머지 제안자가 반드시 이를 채택하기 때문입니다.

두 번째 라운드부터는 리더의 fast path가 없고 모두 무작위 우선순위를 씁니다. 무작위성이 필요한 이유는 Fischer·Lynch·Paterson의 1985년 FLP 정리에 있습니다. 메시지 지연에 아무 가정이 없는 비동기 네트워크에서는 서버 하나만 멈춰도 결정적 알고리즘이 안전성과 종료를 함께 보장할 수 없다는 내용입니다. Paxos와 Raft는 진행을 위해 타이밍 가정을 두고, QuePaxa는 무작위성으로 확률 1의 종료를 얻습니다.

논문은 리더 없는 각 라운드가 적어도 1/2 확률로 성공하며 기대 라운드 수가 2보다 작음을 증명합니다. 전제는 과반이 살아 있고 정상 복제본 사이의 메시지가 결국 전달되며, 네트워크를 조작하는 적대자가 메시지 내용과 우선순위를 보지 못한다는 것입니다. 논문은 복제본 사이의 TLS 암호화로 메시지 내용을 가리는 조건을 충족할 수 있다고 보며, 사이드 채널은 범위 밖에 둡니다.

장애 판정 없이 제안자를 늘리는 hedging

QuePaxa도 평소에는 리더가 fast path를 쓰는 편이 효율적입니다. 리더만 기다리지 않도록 쓰는 hedging은 같은 작업을 다른 노드에서도 시작해 예상 밖의 지연에 대비하는 기법입니다.

논문에서는 클라이언트가 모든 복제본에 요청을 보냅니다. 리더는 바로 나서고, 다른 제안자는 자기 순번의 지연만큼 기다린 뒤 현재 단계를 다른 제안자가 끝냈다는 증거가 없을 때만 동작합니다. Cloudflare는 메시지 수를 줄이려고 이 기다림을 복제본 대신 클라이언트가 맡도록 구현했다고 밝혔습니다.

리더 장애 때 다른 제안자가 진행을 이어가는 흐름입니다.

Cloudflare 구현에서는 클라이언트가 hedging 지연만 기다린 뒤 다른 제안자에게도 요청을 보내고, 그 제안자가 리더의 장애 여부를 확인하지 않은 채 합의를 진행합니다.
도식 텍스트
  • 클라이언트
  • 리더 (응답 없음)
  • 다른 제안자
  • 기록자 과반
  1. 1. 요청
  2. hedging 지연 경과 · 장애 판정은 하지 않음
  3. 2. 같은 요청
  4. 3. 제안(무작위 우선순위)
  5. 4. 과반 응답
  6. phase 1과 2를 거쳐 결정 · 왕복 세 번
  7. 5. 결과

선거 타임아웃은 장애를 의심해 복구 절차를 시작하는 기준이고, hedging 지연은 다른 제안자가 합류할 시점입니다. 논문은 타임아웃 0은 끝없는 장애·복구를 부르지만 hedging 지연 0은 유효하다고 설명합니다. Cloudflare도 지연이 100ms인 네트워크에서 Raft의 타임아웃을 5ms로 두면 시스템이 멈추지만, 같은 값의 hedging 지연은 활성 제안자 수를 늘릴 뿐이라고 적습니다.

짧은 지연은 더 많은 제안자를 깨우므로 메시지가 늘고 fast path의 성공 확률이 낮아집니다. 메시지 수는 평소 복제본 수에 비례하지만, 지연이 너무 작거나 네트워크가 비동기적으로 움직이면 최악의 경우 제곱에 비례합니다. 논문이 둔 가정 아래에서는 지연을 잘못 정해도 진행 보장이 유지됩니다.

리더도 성능을 보고 바꿀 수 있습니다. 논문은 고정 길이의 슬롯 묶음인 epoch마다 리더를 고정하고, 복제본을 돌아가며 시험한 뒤 평균 epoch 완료 시간을 기준으로 리더를 선택합니다. 리더 선택이 나빠도 진행 보장은 유지되므로 운영 중에 바꾸는 부담이 작습니다.

Raft와 QuePaxa의 차이

항목RaftQuePaxa
리더의 지위필수. 리더가 새 로그 엔트리를 만들고 복제선택. fast path 특권을 가진 제안자
정상 경로리더에서 과반까지 왕복 한 번리더의 fast path로 왕복 한 번
리더 장애 시선거 타임아웃 동안 쓰기 중단, 새 리더 선출 뒤 재개다른 제안자가 hedging 지연 뒤 제안. 선거 없음. 결정까지 왕복이 늘어남
동시 제안한 term(논리적 시간 구간)에 리더 최대 하나. 후보가 겹치면 표가 분산되어 재선거높은 우선순위 제안을 채택하며 같은 값으로 수렴
타임아웃의 역할장애 감지와 선거 시작의 기준. 진행이 여기에 달림hedging 지연은 성능 조절값. 진행 보장 여부와 무관
값을 잘못 잡으면너무 짧으면 선거 반복으로 중단, 너무 길면 장애 뒤 중단이 길어짐너무 짧으면 메시지 증가, 길면 리더 장애 대응이 늦어짐
진행을 보장하는 가정부분 동기와 타이밍 조건. 부분 분할에는 PreVote(사전 투표)와 CheckQuorum(과반 확인) 필요정상 복제본 간 메시지는 결국 전달. 메시지 내용을 못 보는 적대자 아래 비동기에서도 확률 1로 종료
안전성타이밍과 무관타이밍과 무관
장애 모델멈췄다가 디스크의 상태로 복구해 재합류논문은 멈춘 복제본이 돌아오지 않는 crash-stop
멤버십 변경·로그 압축논문에 정의, 구현 다수논문 프로토타입은 미구현
구현과 운영 경험etcd, Consul, CockroachDB, TiKV, Kafka 등연구용 Go 프로토타입, Cloudflare의 Rust 구현(실험 단계)

부분 분할 행은 Howard·Abraham이 링크 단절 모델에서 내린 결론에 따른 것입니다. 그 진행 보장은 타이밍 가정이 성립하는 구간의 보장으로 해석합니다.

논문과 Cloudflare가 보고한 수치

논문이 비교한 Raft는 etcd 같은 운영 구현이 아닌 저자들의 연구용 구현입니다.

측정자·시점조건결과
QuePaxa 논문 §7.4 (2023)AWS 5개 리전, 5대. 소수 복제본의 송신 지연을 5초마다 바꿔 최대 500ms까지 늘림QuePaxa는 초당 7.5만 명령 이상 유지. Multi-Paxos와 Raft는 초당 2,500 명령에서 포화
논문 §7.55대, 평균 왕복 180ms, 초당 2.5만 명령 부하에서 리더를 멈춤시험한 모든 hedging 지연에서 QuePaxa의 복구 시간은 303~473ms. Multi-Paxos와 Raft는 타임아웃이 왕복 시간의 약 1.8배보다 작으면 처리량과 진행을 잃음
논문 §7.6성능이 다른 인스턴스 5대, 가장 느린 것을 초기 리더로Multi-Paxos와 Raft는 느린 리더를 유지(지연 5.2ms). QuePaxa는 4초 만에 리더를 바꿔 3.8ms
논문 §7.2단일 리전, 정상 상태QuePaxa 초당 58.4만 명령, Multi-Paxos 40만
Cloudflare Meerkat (2026-11)거의 모든 대륙에 서버 배치결정의 95% 이상을 리더가 phase 0에서 처리. 제시한 리더 장애 구간에는 결정 속도가 평소의 약 65%로 내려갔다가 리더 교체 뒤 회복. 평가 중 완전히 멈춘 적은 없었다고 보고

단일 리전의 처리량 차이에는 명령 배치를 먼저 퍼뜨리고 그 식별자만 합의하는 최적화가 영향을 줬다는 것이 논문 저자들의 설명입니다. Cloudflare의 수치는 자체 평가이며, 벤치마크는 후속 글에서 공개하겠다고 밝혔습니다.

구현 범위와 검증의 한계

  • crash-stop을 가정한 논문에서 상태 영속화와 재시작 뒤 재합류 지원 여부는 확인되지 않았다. Cloudflare는 장애 뒤 복구를 지원하도록 확장하는 중이라고 밝혔다.
  • 논문에 따르면 네트워크를 강하게 조작할 수 있는 적대자는 리더가 있는 첫 라운드를 항상 실패시킬 수 있다. 리더 없는 라운드로 진행하지만 fast path의 이점은 사라진다.
  • Cloudflare는 Raft의 선거 반복을 준안정 장애(metastable failure)라고 부른다. Bronson 등의 2021년 논문은 원인이 사라지면 풀리는 livelock(진행 없는 반복)을 이 정의에서 제외한다. 선거 반복만으로 준안정 장애라고 부르면 원래 정의보다 범위가 넓어진다.
  • Raft만큼 운영에서 검증되지 않았다는 점은 Cloudflare도 인정한다. Cloudflare는 자신의 QuePaxa 구현과 Meerkat 전체를 정형 검증하고, 시뮬레이션과 장애 주입 테스트를 함께 진행 중이라고 밝혔다.

참고 자료

마지막 수정 일자