목차
리더가 멈춰도 합의를 이어가는 Meerkat의 QuePaxa (2026-11)
원문 정보
- 원문: Choosing QuePaxa, an unusual consensus algorithm
- 매체 · 게시일: The Cloudflare Blog · 2026-11-11
- 저자: João Pedro Leite, Bob Halley, James Larisch
- 원문 내용을 바탕으로 재구성한 요약입니다.
80배 느려진 Cloudflare 대시보드
2020년, Cloudflare의 코어 네트워크 스위치에 부분 장애가 났습니다. 합의 시스템이 영향을 받으면서 대시보드는 평소보다 80배 느려졌고, 이 상태가 6시간 이어졌습니다. 데이터 손실은 없었지만, 쓰기는 문제를 해결할 때까지 멈춘 상태였습니다.
Cloudflare가 최근 발표한 Meerkat은 이런 멈춤을 피해야 하는 서비스입니다. 내부 전역 제어 평면을 관리하도록 설계한 실험적 분산 합의 서비스로, 복제본들이 순서가 정해진 이벤트 로그에 합의합니다. 로그의 각 항목에 get이나 put을 기록하면 키-값 저장소를 제공하는 방식입니다. 합의 알고리즘이 서로 충돌하는 결정을 막으므로 복제본들은 같은 로그와 같은 상태를 유지합니다.
Consul, etcd, Apache ZooKeeper도 합의를 사용합니다. Meerkat의 까다로운 조건은 배치 범위입니다. 복제본들이 대륙을 가로질러 떨어져 있고, 그 사이 연결은 지연이 크고 변동도 심합니다. 서버가 살아 있어도 네트워크 때문에 멈출 수 있는 환경에서, 데이터를 지킨다는 보장만으로는 충분하지 않았습니다.
복구를 방해하는 리더 선거
Raft, Multi-Paxos, Viewstamped Replication은 리더만 제안하도록 제한합니다. 여러 제안이 경쟁하지 않게 하고, 리더와 네트워크가 정상일 때 한 번의 왕복으로 결정을 끝내는 방식입니다. 리더가 느려지거나 연결을 잃으면 이 장점도 사라집니다. 남은 복제본들이 장애를 감지하고 새 리더를 선출할 때까지 시스템이 멈춥니다.
복구도 순탄하지만은 않습니다. Raft에서는 리더의 장애를 의심한 복제본이 후보가 되어 과반수의 표를 구하는데, 여러 후보가 나서면 서로 과반수를 얻지 못하게 방해할 수 있습니다. 선거가 실패하면 다시 선거를 치르고, 더 많은 복제본이 후보로 나서는 상황입니다.
이렇게 제안자들이 서로의 진행을 막는 현상을 파괴적 간섭이라고 합니다. 예를 들어 2초 동안 네트워크가 끊겨 선거를 시작했다면, 연결이 돌아온 뒤에도 후보들이 서로를 막아 선거가 훨씬 오래 이어질 수 있습니다. 최초 원인이 사라져도 장애가 스스로 지속되는 준안정 장애입니다.
많은 합의 알고리즘의 원조인 Paxos에서도 같은 유형의 간섭을 만납니다. 제안자는 Prepare 단계에서 수락자 과반수에 투표 번호를 보내, 그보다 낮은 번호의 제안은 받지 않겠다는 약속을 얻습니다. 이어지는 Accept 단계에서는 값과 투표 번호를 보내고, 과반수가 여전히 그 번호를 유지하고 있으면 제안을 결정하는 방식입니다.
그 사이 다른 제안자가 더 높은 번호를 보내면 앞선 제안은 막힙니다. 서로 높은 번호를 보내며 반복해서 가로막으면, 서버가 모두 정상이어도 결정을 내리지 못할 수 있습니다. Paxos가 결국 제안을 결정한다는 진행성을 보장하려면, 어느 시점부터 모든 메시지가 제한된 시간 안에 도착한다는 부분 동기성 가정이 필요한 이유입니다. 리더는 평소의 경쟁을 없애지만, 리더를 복구하는 선거에서 경쟁이 되살아날 수 있습니다.
장애 감지에 묶이지 않는 QuePaxa 헤징
선거를 언제 시작할지도 문제입니다. 원격 프로세스가 고장 났는지는 직접 볼 수 없으므로, 복제본은 하트비트나 응답이 예상한 시간 안에 도착하는지로 판단합니다. 메시지 도착 시간의 상한이 없는 비동기 네트워크에서는 서버가 죽었는지, 메시지만 늦는지 구별할 수 없습니다. 대부분의 메시지가 제때 도착하더라도 갑작스러운 지연이나 연결 단절 때문에 이 판단은 틀릴 수 있습니다.
타임아웃을 늘리면 오탐은 줄어들지만 실제 장애를 알아채는 시간도 길어집니다. Raft의 선거 타임아웃을 네트워크 왕복 시간의 5~10배로 잡는 경우가 많은 이유입니다. 지구 반대편까지 왕복하는 데 수백 밀리초가 걸리는 환경이라면, 여러 차례 왕복에 해당하는 시간을 기다리다가 장애 감지에만 약 1초를 쓸 수 있습니다. 정확히 감지하더라도 그동안 시스템은 멈춰 있습니다.
Cloudflare는 이 기다림에 진행 여부를 맡기지 않는 알고리즘을 찾았습니다. 그 선택이 Tennage & Băsescu 등의 연구진이 2023년에 발표한 QuePaxa입니다. QuePaxa에도 리더는 있지만 필수는 아닙니다. 리더만 한 번의 왕복으로 결정하는 빠른 경로를 사용할 수 있고, 리더가 없어도 다른 제안자가 합의를 이어갑니다.
빠른 경로를 우선 쓰되 리더에게만 기대지 않도록 요청을 헤징합니다. 논문에서는 클라이언트가 모든 복제본에 요청을 보내고, 비리더 복제본은 리더가 먼저 제안하고 결정하도록 잠시 기다리는 방식입니다. Cloudflare 구현은 네트워크 메시지를 줄이려고 이 대기를 복제본에서 클라이언트로 옮겼습니다.
헤징 타임아웃은 장애 판정 기준이 아닙니다. 원문이 든 비교 예시에서, 지연이 100밀리초인 네트워크에 5밀리초 타임아웃을 적용하면 Raft는 멈추지만 QuePaxa에서는 활성 제안자 수가 늘어납니다. 리더가 고장 났다는 판단을 기다려야 다른 제안자가 움직이는 방식이 아니기 때문입니다.
물론 헤징에도 비용은 있습니다. 대기를 짧게 잡으면 리더 변화에 빨리 대응하지만, 더 많은 제안자가 제안을 전파하면서 대역폭을 쓰고 한 라운드 안에 결정하지 못할 가능성도 커집니다. 결정 시간이 늘어날 수도 있는 선택입니다. Cloudflare는 장애 감지 속도를 네트워크 지연에 묶어 두는 대신 이 비용을 감수하기로 했습니다.
높은 우선순위로 모이는 제안자
여러 제안자가 활동하는데도 서로를 끝없이 가로막지 않는 이유는 제안을 채택하는 규칙에 있습니다. QuePaxa에는 값을 제출하는 제안자와, 받은 제안을 기록해 다른 활성 제안자에게 전달하는 recorder가 있습니다. 일반 제안에는 무작위 우선순위를 부여하고, 리더는 자신만 쓸 수 있는 최댓값을 사용하는 방식입니다.
제안자는 더 높은 우선순위의 제안을 만나면 그것을 자신의 제안으로 채택해 전파합니다. 자기 값을 고집하지 않습니다. 각자가 알고 있는 가장 높은 우선순위의 제안을 함께 퍼뜨리면서 같은 값으로 수렴합니다. 한 라운드 안에 합의할지는 보장하지 않지만, 충분한 라운드를 거치면 결국 합의에 도달합니다.
각 라운드는 Phase 0부터 Phase 3까지로 나뉩니다. 제안자는 단계마다 현재 채택한 제안을 모든 recorder에 보내고, 과반수의 응답을 받아 다음 단계로 넘어가는 방식입니다.
한 번의 왕복으로 끝나는 첫 라운드
Phase 0에서는 우선순위를 정해 제안을 보내고, 과반수의 응답에서 가장 높은 우선순위의 제안을 채택합니다. 첫 라운드의 리더에게는 특별한 기회가 있습니다. 자신의 제안이 다른 제안보다 먼저 recorder 과반수에 도착했음을 확인하면 여기서 바로 결정합니다.
이 빠른 결정을 안전하게 만드는 성질이 과반수 교집합입니다. 어떤 두 과반수도 적어도 하나의 recorder를 공유하므로, 리더가 과반수에 먼저 도달했다면 다른 제안자도 과반수를 조회하는 과정에서 리더의 제안을 만나게 됩니다. 리더의 우선순위가 가장 높으니 그 제안을 채택해야 하며, 다른 값을 결정할 수 없습니다.
결정을 이어받는 다음 라운드
빠른 경로가 열리지 않는 경우도 있습니다. 원문의 실행 예시는 리더를 포함한 제안자 2개와 recorder 3개로 이루어집니다. 다른 제안자가 두 번째와 세 번째 recorder에 먼저 도착해 리더의 빠른 경로를 막고, 리더 메시지도 지연시켜 제안들이 곧바로 수렴하지 않는 상황입니다.
이때는 Phase 1에서 각자 채택한 제안을 과반수에 전파합니다. recorder는 관찰한 가장 높은 우선순위의 제안을 유지합니다. 어느 과반수를 다음에 조회하더라도 앞선 과반수와 겹치는 recorder가 있으므로, 더 낮은 우선순위의 제안만 보고 결정하는 일을 막는 단계입니다.
Phase 2에서는 과반수에 Phase 1에서 관찰한 최고 우선순위 제안을 묻습니다. 응답 중 가장 높은 제안이 자신이 채택한 제안과 같으면 결정합니다. 이 실행 예시에서 리더는 자신의 제안을 확인하고 결정하지만, 다른 제안자는 상충하는 응답을 받아 아직 결정하지 못한 상태입니다.
남은 제안자는 Phase 3에서 다시 제안을 전파하고, 과반수에서 확인한 가장 좋은 제안을 채택해 다음 라운드로 넘어갑니다. 앞 단계에서 결정이 있었다면 그 제안은 과반수에 남아 있으므로, 이 제안자도 반드시 발견해 채택합니다. 한 라운드에서 결정을 못 했다고 앞서 얻은 정보를 버리지는 않는 방식입니다.
다음 라운드부터는 리더의 빠른 경로가 없습니다. Phase 2에서 수렴해야 결정합니다. 논문이 예측한 라운드별 결정 확률은 50%이며, Cloudflare는 앞선 라운드에서 제안을 채택하며 수렴하기 때문에 실제 확률은 훨씬 높다고 설명합니다.
리더가 멈춘 뒤의 Meerkat
거의 모든 대륙에 서버를 둔 Meerkat 평가에서, 리더가 중단되거나 연결을 잃거나 느려져도 요청 처리는 이어졌습니다. Cloudflare가 이 평가에서 시스템의 완전한 중단을 관찰한 적은 없습니다.
평소에는 빠른 경로가 대부분을 처리했습니다. 결정의 95% 이상을 리더가 첫 단계에서 끝냈으므로 처리율도 대체로 예측 가능한 상태였습니다. 첫 단계에서 결정하지 못한 사례에서는 처리율이 잠시 평소의 3분의 1 수준까지 내려갔습니다. 한 번 대신 세 번의 왕복을 거쳐 결정하면서 느려졌지만, 처리가 멈추지는 않았습니다.
리더 장애를 보여 준 그래프에서는 결정 처리율이 기존의 약 65%로 떨어졌습니다. 장애가 난 지 1분 뒤 리더를 교체하자 100%로 돌아왔으며, 이 구간에서도 전체 중단은 없었습니다.
리더를 고르는 일에도 여유가 생겼습니다. 리더가 결정을 독점하지 않고 제안자들이 협력하므로, 잠시 최적이 아닌 복제본이 리더를 맡더라도 다른 알고리즘만큼 큰 제약이 되지는 않습니다. Cloudflare는 클러스터의 안정성을 크게 우려하지 않으면서 실행 중 리더를 동적으로 조정할 수 있다고 설명합니다.
실전 검증이 더 필요한 QuePaxa
이 선택에는 아직 채워야 할 검증이 남아 있습니다. QuePaxa는 Raft나 Paxos만큼 폭넓게 실전을 거치지 않았고, Cloudflare는 원래의 crash-stop 설계를 장애 후 복구까지 지원하도록 확장하는 중입니다. 그래서 QuePaxa 구현과 Meerkat 전체의 정형 검증을 진행하며, 광범위한 시뮬레이션과 장애 주입 테스트도 수행하고 있습니다.
Meerkat 시리즈의 후속 글에서는 Meerkat과 QuePaxa의 Rust 구현을 검증하는 방법, 실제 운영 환경에서 재현하기 어려운 장애를 테스트하는 방법을 다룰 예정입니다. 벤치마크와 함께 학술 프로토콜을 실제 운영 시스템으로 옮기며 얻은 경험도 소개할 계획입니다.
장애 사례·타임아웃 예시·평가 수치
| 항목 | 값 |
|---|---|
| 기존 시스템의 장애 사례 | 2020년 Cloudflare 코어 스위치 부분 장애로 대시보드가 평소보다 80배 느려진 상태가 6시간 지속됐으며, 데이터 손실 없이 쓰기가 중단됨 |
| 준안정 장애 설명 예시 | 2초의 네트워크 장애가 끝난 뒤에도 리더 선거가 더 오래 지속될 수 있음 |
| Raft의 일반적인 선거 타임아웃 | 네트워크 왕복 시간의 5~10배로 설정하는 경우가 많음 |
| 전역 장애 감지 시간 설명 | 지구 반대편까지의 왕복은 수백 밀리초 수준이며, 여러 차례 왕복에 해당하는 타임아웃이면 장애 감지에 약 1초가 걸릴 수 있음 |
| QuePaxa 발표 | 2023년 |
| 짧은 타임아웃 비교 예시 | 지연 100밀리초인 네트워크에서 타임아웃 5밀리초는 Raft를 멈추게 하지만, QuePaxa의 헤징에서는 활성 제안자 수를 늘림 |
| 알고리즘 실행 예시 구성 | 제안자 2개 중 리더 1개, recorder 3개 |
| 논문의 라운드별 결정 확률 예측 | 50%; 원문은 실제로는 수렴 덕분에 더 높다고 설명 |
| 평가의 첫 단계 결정 비율 | 95% 이상 |
| 리더 장애 그래프 | 결정 처리율이 기존의 약 65%로 하락하고, 장애 1분 뒤 리더 교체 시 100%로 회복; 전체 중단은 없음 |
| 첫 단계에서 결정하지 못한 사례 | 처리율이 잠시 평소의 3분의 1 수준까지 하락; 결정에 1회 대신 3회 왕복이 필요했던 경우 |