분산 합의 지연의 세 가지 탈출구

광역 왕복이라는 지연 하한을 피하는 길은 조정 주체를 흩거나, 통신이 하던 일을 시계에 넘기거나, 커밋 경로에서 조정을 빼는 셋뿐입니다. 워크로드의 충돌률과 시계 신뢰도가 그중 어느 쪽이 실제로 이득인지를 정합니다.

광역 왕복이라는 하한

지리적으로 흩어진 복제본이 하나의 순서에 합의하려면 정보가 물리적으로 오가야 합니다. 리전 간 왕복 시간이 수십에서 수백 ms인 환경에서는 커밋 경로에 왕복이 한 번 낄 때마다 그만큼이 지연 하한으로 굳습니다. Raft나 Multi-Paxos처럼 리더 한 대가 순서를 정하는 프로토콜은 리더에서 먼 클라이언트에게 이 비용을 두 번 물립니다. 클라이언트가 리더까지 다녀오는 왕복 위에, 리더가 과반수 확인을 받는 왕복이 겹치기 때문입니다.

여기서 실제로 깎을 수 있는 것을 나열해 보면 선택지는 셋으로 좁혀집니다. 조정을 맡는 주체를 한 곳에서 여러 곳으로 흩거나, 메시지 교환이 하던 일을 동기화된 시계에 넘기거나, 커밋 경로에서 조정을 아예 빼는 것입니다. 이 세 갈래 분류 자체는 제 판단이며, 아래에 인용한 논문들이 스스로 이렇게 나눈 것은 아닙니다. 본문의 수치는 모두 2026-09 기준으로 각 논문 초록과 대조한 값입니다.

리더를 없애는 길

첫째 탈출구는 순서를 정하는 권한을 모든 복제본에 나눠 주는 것입니다. Egalitarian Paxos(EPaxos)는 서로 상태를 침범하지 않는 명령끼리 실행 순서를 강제할 필요가 없다는 점에서 출발합니다. 충돌이 없으면 임의의 복제본이 2메시지 지연만으로 커밋을 끝냅니다. 클라이언트는 가장 가까운 복제본에 요청을 보내면 되므로, 리더까지 다녀오는 왕복 하나가 사라집니다.

그 대가는 정확성 증명의 난도로 돌아왔습니다. EPaxos*를 제안한 2025년 논문은 원본 프로토콜이 복잡하고 모호하게 명세되어 사소하지 않은 버그를 안고 있었다고 지적합니다. 그러면서 더 단순한 장애 복구 알고리즘과 엄밀한 증명을 제시합니다(arXiv:2511.02743, 2025-11 공개). 빠른 경로를 유지할 수 있는 장애 수 e와 내결함성 f를 독립적으로 조정하는 조건은 n ≥ max{2e+f-1, 2f+1}이고, 논문은 이 값이 최적임을 보입니다. 원본이 목표했던 조합은 n = 2f+1, e = ⌈(f+1)/2⌉ 하나뿐이었습니다.

Apache Cassandra의 Accord는 여기서 설계 축을 바꿉니다. 복제본 응답의 의존성 집합이 정확히 일치해야 빠른 경로가 성립하는 조건을 버리고, 하이브리드 논리 시계 기반 타임스탬프로 전체 순서를 정합니다. 리더를 없애는 길의 실전 구현이 결국 시계에 기대고 있다는 점은 뒤에서 다시 짚습니다.

갈림길을 정하는 충돌률

리더리스 설계의 약속은 조건부입니다. 두 클라이언트가 거의 동시에 요청을 보내면 복제본마다 도착 순서가 달라지고, 이때 정상 노드끼리도 로그가 갈라지는 발산이 일어납니다. Aspen 논문은 이 빠른 경로를 극도로 깨지기 쉽다고 표현하며, 발산이 값비싼 복구 절차를 부른다고 적습니다(arXiv:2601.03390, 2026-01 공개).

Aspen이 택한 대응은 발산을 막는 대신 흡수하는 쪽입니다. 복제본을 n = 3f + 2p + 1로 늘려, 최대 p대가 발산해도 나머지가 빠른 경로를 계속 쓰게 합니다. 여기에 느슨하게 동기화된 시계와 네트워크 지연 추정으로 잠정 순서를 미리 매깁니다. 지리 분산 실험에서 중앙값 지연을 기존 비잔틴 장애 허용 프로토콜 대비 1.1배에서 3.8배까지 낮췄습니다. 처리량은 처리량 최적화 설계의 최대 0.75배를 유지했습니다.

주목할 지점은 대가의 방향입니다. 리더를 없애서 얻은 지연 이득을 지키려고 여분 복제본과 시계 기반 사전 정렬을 다시 끌어들였습니다. 즉 첫째 탈출구는 충돌률이 낮은 구간에서만 순수하게 성립하고, 충돌률이 올라가면 둘째 탈출구의 도구를 빌려 오거나 느린 경로로 떨어집니다.

시계를 믿는 길

둘째 탈출구는 메시지 교환이 증명하던 것을 시계가 증명하게 만드는 것입니다. 가장 오래된 형태는 리더 리스로, 리더가 일정 기간 자신이 유일한 리더임을 시간으로 보장해 읽기마다 붙던 과반수 확인을 없앱니다.

LeaseGuard는 별도 리스 자료구조 없이 Raft 선거가 이미 주는 보장만으로 리스를 세웁니다. 그 결과 일관성 읽기의 통신 비용이 왕복 1회에서 0회로 줄었습니다(arXiv:2512.15659, 2025-12 공개). 같은 논문은 읽기와 쓰기 사이 경합이 사라지면서 쓰기 처리량이 초당 약 1,000건에서 약 10,000건으로 올랐다고 보고합니다. 리더 교체 직후 새 리더가 읽기의 99%를 즉시 허용했다는 결과도 함께 실렸습니다. 이 설계의 세부는 Raft 리더 리스와 선형화 가능한 읽기에 정리해 두었습니다.

리스를 누구에게 주느냐를 일반화하면 읽기 지역성이 더 넓어집니다. Bodega는 리더 한 명이나 과반수 고정 집합이 아니라, 임의로 지정한 응답자 집합에 리스를 부여합니다. 이 방식을 로스터 리스라고 부릅니다(arXiv:2509.07158, 2025-09 공개). 실제 광역 클러스터 실험에서 중간 정도의 쓰기 간섭 아래, 평균 읽기 요청을 기존 방식 대비 5.6배에서 13.1배 빠르게 처리했습니다.

시계는 읽기뿐 아니라 커밋 경로 전체를 압축하는 데도 쓰입니다. Tiga는 조율자가 트랜잭션에 미래 타임스탬프를 붙여 보내고, 서버는 그 시각까지 기다렸다 실행합니다. 이렇게 동시성 제어와 합의를 한 라운드에 묶습니다. 대부분의 경우 커밋이 광역 왕복 1회 안에 끝나고, 순서 예측이 어긋나면 1.5에서 2회로 떨어집니다. 논문은 기존 방식 대비 처리량 1.3배에서 7.2배, 지연 1.4배에서 4.6배 개선을 보고합니다(arXiv:2509.05759, 2025-09 공개).

같은 해 K2는 TrueTime 계열 시계로 시간 불확실성 구간을 줄였습니다. 그 결과 지리 분산 트랜잭션 처리량이 한 자릿수 배 높아졌다고 보고합니다(arXiv:2504.01460, 2025-04 공개).

조정 자체를 피하는 길

셋째 탈출구는 커밋 경로에서 조정을 빼는 것입니다. 두 가지 방식이 있는데, 조정을 나중으로 미루는 쪽과 아예 없애는 쪽입니다.

미루는 쪽의 예가 에포크 기반 낙관적 동시성 제어입니다. Minerva는 시간을 고정 길이 에포크로 나눠 각 복제본이 로컬에서 즉시 커밋한 뒤 쓰기 집합을 배치로 전파하고, 뒤늦게 드러난 충돌은 중단 대신 결정론적 재실행으로 해소합니다. 논문은 확장성 실험에서 3배 이상, TPC-C 고지연 시뮬레이션에서 2.8배 높은 처리량을 보고합니다(arXiv:2602.21566, 2026-02 공개). 자세한 동작은 에포크 기반 낙관적 동시성 제어에서 다뤘습니다.

없애는 쪽은 CRDT입니다. 병합 규칙을 자료형 안에 박아 두어, 어떤 순서로 갱신이 도착해도 같은 값으로 수렴하게 만듭니다. 조정 비용은 0에 수렴하지만 사라진 것은 아닙니다.

2026년의 두 논문은 이 병합이 사용자에게 암묵적이고 불투명하다는 점을 문제로 삼습니다. 한 편은 의미론적 의존성 기반의 명시적 병합을 제안합니다(arXiv:2602.19231, 2026-02 공개). 다른 한 편은 Datalog로 실행 가능한 명세를 내놓았습니다(arXiv:2605.31569, 2026-05 공개). 조정을 없앤 대신 애플리케이션이 어떤 편집이 왜 이겼는지를 설명할 책임을 떠안는 셈입니다. CRDT의 대수 구조는 CRDT에 정리해 두었습니다.

세 탈출구가 무너지는 조건

첫째 탈출구는 충돌률이 낮다는 전제 위에 서 있습니다. 충돌이 잦아지면 빠른 경로가 느린 경로로 떨어지고 의존성 그래프 비용이 커지므로, 리더 기반 설계 대비 이득이 사라집니다.

2013년에 발표된 EPaxos의 정확성 결함은 2019년에 지적됐습니다(arXiv:1906.10917). 프로토콜을 고쳐 단순화한 정정판은 2025년 11월에야 나왔습니다(arXiv:2511.02743, 2026-09 기준). 이 간격도 함께 봐야 합니다. 구현 복잡도는 지연 이득과 달리 벤치마크에 잡히지 않습니다.

둘째 탈출구는 시계 오차 상한이 실제로 지켜진다는 가정 위에 서 있습니다. LeaseGuard의 실측 환경은 AWS TimeSync 기반으로 오차가 50µs 미만이었습니다. Tiga의 평가에서는 동기화 방식별 오차가 Ntpd 16.45ms, Chrony 4.54ms, Huygens 0.012ms로 갈렸습니다. 자체 데이터센터의 일반적인 NTP 구성이 ms 단위 오차에 머문다면 리스 기간과 타임스탬프 여유를 그만큼 키워야 하고, 그러면 애초에 줄이려던 지연이 다시 들어옵니다. 더 나쁜 것은 이 가정이 깨질 때 성능이 아니라 정확성이 조용히 무너진다는 점입니다.

셋째 탈출구는 충돌이 드물거나, 충돌을 애플리케이션 의미론으로 정의할 수 있을 때만 성립합니다. 재실행 비용은 충돌률에 따라 늘고, CRDT는 선형성 대신 강한 최종 일관성만 줍니다. 계좌 잔액처럼 읽은 값에 기대어 쓰는 트랜잭션에는 두 방식 모두 맞지 않습니다.

세 갈래 모두에 걸리는 한계도 있습니다. 위 논문들은 각자 하나의 탈출구를 깊게 파고들 뿐, 셋을 한 시스템에 섞었을 때의 상호작용을 다루지 않습니다. Aspen이 리더 제거와 시계를 겹쳐 쓴 사례가 이 글이 확인한 유일한 조합입니다. 또한 비잔틴 장애를 견뎌야 하는 환경은 처리량 상한이 다른 곳에서 정해지므로 별도 축으로 봐야 합니다. 이 부분은 DAG 기반 BFT 합의와 리더 기반 BFT에서 다뤘습니다.

탈출구 선택 기준

선택을 가르는 질문은 셋입니다. 같은 키에 대한 동시 쓰기가 얼마나 자주 일어나는가, 배포 환경의 시계 오차 상한을 숫자로 말할 수 있는가, 애플리케이션이 병합 규칙을 스스로 정의할 수 있는가.

마지막 줄이 중요합니다. 시계 오차 상한을 운영 지표로 관측하지 않고 있고 충돌률도 측정한 적이 없다면, 세 탈출구 중 무엇을 골라도 전제를 확인하지 않은 선택이 됩니다. 그 상태에서는 리더 기반 합의를 유지하고 리더 배치를 클라이언트 분포에 맞추는 편이 낫다고 봅니다. 이는 논문에 적힌 결론이 아니라 제 판단입니다.

정리

지리 분산 합의의 지연 하한은 광역 왕복이고, 이를 피하는 길은 조정 주체를 흩거나, 통신을 시계로 대체하거나, 조정을 커밋 경로에서 빼는 셋뿐입니다. 세 길 모두 지연을 없애는 것이 아니라 비용을 다른 곳으로 옮기며, 옮겨진 곳은 각각 충돌 복구, 시계 오차 가정, 재실행과 의미론적 충돌입니다. 어느 쪽이 실제로 이득인지는 워크로드의 충돌률과 배포 환경의 시계 신뢰도가 정하므로, 두 값을 측정하기 전에는 선택 자체가 성립하지 않습니다. 그 둘을 아직 모른다면 리더 기반 합의를 유지하고 리더 위치부터 조정하는 것이 안전한 출발점입니다.