Cloudflare, 리더 교체 기다리지 않는 합의 알고리즘을 내부 실험 서비스에 적용

Cloudflare는 2026년 11월 11일 회사 블로그에서 내부 글로벌 제어면을 관리하기 위한 실험 서비스 Meerkat에 합의 알고리즘 QuePaxa를 적용한 이유와 작동 방식을 설명했습니다. 글을 쓴 João Pedro Leite, Bob Halley, James Larisch는 QuePaxa가 네트워크 지연이나 연결 문제 중에도 특정 리더의 복구를 기다리지 않고 합의를 진행하도록 설계됐다고 밝혔습니다.

Meerkat은 여러 지역에 놓인 복제본(replica)이 이벤트를 같은 순서로 기록하는 분산 시스템입니다. 합의 알고리즘은 이 순서를 정해 복제본의 기록이 서로 달라지지 않게 합니다. Meerkat은 확정된 로그를 애플리케이션에 키-값 저장소처럼 제공하며, 로그에는 값을 읽는 get과 쓰는 put 작업이 담깁니다.

Raft와 Multi-Paxos 같은 리더형 알고리즘에서는 한 복제본이 제안을 주도합니다. 리더가 정상이고 네트워크가 원활하면 빠르게 처리할 수 있지만, 리더가 멈추거나 메시지가 늦으면 다른 복제본이 장애를 의심하고 새 리더를 뽑아야 합니다. 원격 서버가 멈췄는지 메시지만 늦는지 네트워크만으로 즉시 구별하기 어렵기 때문입니다. 장애 감지를 서두르면 정상 리더를 잘못 교체할 수 있고, 기다리는 시간을 늘리면 실제 장애에도 합의가 늦어집니다. 새 리더를 뽑는 과정에서 후보들이 동시에 과반의 표를 얻으려다 서로를 방해해 선거가 반복될 수도 있습니다.

Cloudflare는 이런 문제가 실제 운영에 미친 사례로 2020년 핵심 네트워크 스위치의 부분 장애를 들었습니다. 당시 합의 시스템의 성능이 떨어져 대시보드가 평소보다 80배 느린 상태가 6시간 이어졌습니다. 데이터는 유실되지 않았지만, 장애가 해소될 때까지 쓰기가 중단됐다고 밝혔습니다.

QuePaxa에는 제안자(proposer)와 기록자(recorder)라는 두 역할이 있습니다. 제안자는 합의할 값을 내고, 기록자는 받은 제안을 기록해 다른 제안자에게 전달합니다. 일반 제안자는 무작위로 정한 우선순위를 붙이며, 리더는 가장 높은 우선순위를 가집니다. 제안자는 기록자 과반에서 확인한 제안 가운데 우선순위가 가장 높은 제안을 채택해 다시 알립니다. 각자 자기 제안을 밀어붙이는 대신 서로 높은 우선순위의 제안을 이어받아 같은 값으로 모이는 구조입니다.

한 라운드는 네 단계로 진행됩니다. 각 단계에서 제안자는 현재 채택한 제안을 모든 기록자에게 보내고, 기록자 과반의 응답을 받으면 다음 단계로 넘어갑니다. 첫 단계에서는 기록자 과반에서 확인한 제안 가운데 우선순위가 가장 높은 것을 채택합니다. 다만 리더가 첫 라운드에서 자기 제안이 다른 제안보다 먼저 기록자 과반에 도달했다고 확인하면 이 단계에서 바로 결정할 수 있습니다. 다음 단계에서는 제안자들이 채택한 제안을 기록자 과반에 퍼뜨립니다. 세 번째 단계에서 제안자는 기록자 과반에 전 단계에서 가장 높은 우선순위로 기록된 제안을 묻고, 그 제안이 자신의 채택안과 같으면 결정합니다. 결정하지 못한 제안자는 마지막 단계에서 기록자 과반이 본 제안 가운데 가장 높은 우선순위의 것을 채택해 다음 라운드로 가져갑니다. 기록자 과반끼리는 적어도 한 기록자를 공유하므로, 앞 단계에서 과반에 퍼진 제안을 다음 과반 확인에 참여한 기록자가 알고 있습니다. 리더의 빠른 결정 경로는 첫 라운드에만 있습니다. 이후 라운드에는 이 경로가 없으며, 제안자는 세 번째 단계의 과반 확인을 통해 자신의 채택안이 가장 높은 우선순위인지 확인해야 결정할 수 있습니다.

리더는 합의를 독점하지 않습니다. 빠른 결정을 할 우선권을 갖지만, 클라이언트는 다른 제안자에게도 요청을 보낼 수 있습니다. 논문에 제시된 방식에서는 비리더 복제본이 잠시 기다려 리더가 먼저 제안하도록 합니다. Cloudflare 구현은 복제본 대신 클라이언트가 이 대기시간을 두도록 바꿔 네트워크 메시지를 줄였습니다. 이 hedge 대기시간은 리더 장애를 판정하는 시간이 아니라 다른 제안자를 얼마나 빨리 활성화할지 정하는 기준입니다. Cloudflare가 든 예에서 네트워크 지연이 100밀리초인 환경의 Raft에 5밀리초 선거 시간을 두면 진행이 멈추지만, QuePaxa의 5밀리초 hedge 대기시간은 활성 제안자 수를 늘립니다. 대기시간을 짧게 하면 더 많은 제안이 퍼져 대역폭을 쓰고 결정까지 더 오래 걸릴 수 있습니다.

Cloudflare는 거의 모든 대륙에 서버를 둔 Meerkat 평가에서 리더가 중단되거나 연결이 끊기거나 느려져도 요청 처리가 완전히 멈춘 적이 없었다고 밝혔습니다. 결정의 95% 이상은 리더가 첫 단계에서 처리했습니다. 첫 단계에서 결정하지 못한 경우 처리량은 잠시 평소의 최대 3분의 1까지 떨어졌고, 결정까지 한 차례 대신 세 차례의 네트워크 왕복이 필요했다고 설명했습니다. Cloudflare는 실행 중 리더를 바꾸는 일도 다른 리더형 알고리즘보다 시스템 진행을 덜 제한한다고 밝혔습니다.

Cloudflare는 QuePaxa가 Raft나 Paxos처럼 오랫동안 운영 현장에서 시험된 알고리즘은 아니라고 설명했습니다. 또 원 논문이 멈춘 프로세스의 복구를 가정하지 않는 crash-stop 설계를 복구 지원까지 넓히고 있어, QuePaxa 구현과 Meerkat을 대상으로 형식 검증·시뮬레이션·장애 주입 시험을 진행하고 있다고 밝혔습니다.