분산 합의 지연을 줄이는 세 가지 접근

광역 왕복 비용을 줄이는 대표적인 세 접근은 조정 주체 분산, 시계 활용, 조정 범위 축소이며 각각 다른 전제와 일관성 비용을 요구합니다.

광역 왕복이라는 하한

지리적으로 흩어진 복제본이 하나의 순서에 합의하려면 정보가 물리적으로 오가야 합니다. 리전 간 왕복 시간이 수십에서 수백 ms인 환경에서는 커밋 경로에 왕복이 추가될 때마다 지연 하한이 그만큼 늘어납니다.

Raft나 Multi-Paxos처럼 리더 한 대가 순서를 정하는 프로토콜은 리더에서 먼 클라이언트에게 이 비용을 두 번 물립니다. 클라이언트가 리더까지 다녀오는 왕복 위에, 리더가 과반수 확인을 받는 왕복이 겹치기 때문입니다.

이 글은 지연을 줄이는 설계를 세 갈래로 묶어 비교합니다. 조정 주체를 여러 곳으로 흩거나, 메시지 교환의 일부를 동기화된 시계로 대체하거나, 동기식 조정이 필요한 연산 범위를 줄이는 방식입니다.

이 분류는 가능한 프로토콜을 모두 포괄하는 하한 정리가 아니라 본문의 분석 틀입니다. 본문의 수치는 2026-09 기준으로 인용한 논문의 평가 범위와 대조했습니다.

flowchart TD
    A["광역 왕복<br/>지연 하한"] --> B["리더를 없앤다<br/>EPaxos*·Accord·Aspen"]
    A --> C["시계를 믿는다<br/>리더 리스·Bodega·Tiga·K2"]
    A --> D["조정 범위를 줄인다<br/>에포크 OCC·CRDT"]
    B --> B1["대가<br/>충돌하면 느린 경로와 복구"]
    C --> C1["대가<br/>시계 오차가 안전성 가정이 됨"]
    D --> D1["대가<br/>재실행 비용 또는 의미론적 충돌"]

리더를 없애는 길

첫째 접근은 순서를 정하는 권한을 모든 복제본에 나눠 주는 것입니다. Egalitarian Paxos(EPaxos)는 서로 상태를 침범하지 않는 명령끼리 실행 순서를 강제할 필요가 없다는 점에서 출발합니다.

충돌이 없으면 임의의 복제본이 2메시지 지연만으로 커밋을 끝냅니다. 클라이언트는 가장 가까운 복제본에 요청을 보내면 되므로, 리더까지 다녀오는 왕복 하나가 사라집니다.

sequenceDiagram
    participant C as 클라이언트
    participant N as 가까운 복제본
    participant Q as 빠른 경로 정족수
    C->>N: 명령 제출
    N->>Q: 명령과 의존성 제안
    Q-->>N: 의존성 응답
    N-->>C: 충돌이 없으면 커밋

이 설계에서는 정확성을 증명하기가 어려웠습니다. 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의 CEP-15로 채택된 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는 각 복제본에서 트랜잭션을 임시 상태로 실행하고 쓰기 집합을 에포크 단위로 모읍니다. Raft가 전역 에포크 경계를 합의한 뒤 충돌을 결정론적으로 재실행하며, 클라이언트는 이 global commit까지 기다립니다.

논문은 확장성 실험에서 3배 이상, TPC-C 고지연 시뮬레이션에서 2.8배 높은 처리량을 보고합니다(arXiv:2602.21566, 2026-02 공개). 자세한 동작은 에포크 기반 낙관적 동시성 제어에서 다뤘습니다.

충돌 없는 복제 자료형(Conflict-free Replicated Data Type, CRDT)은 지원하는 연산에서 조정을 없앱니다. 병합 규칙을 자료형 안에 두어 갱신 순서가 달라도 같은 값으로 수렴하게 만듭니다. 로컬 갱신 경로에서는 동기식 조정을 빼지만, 복제와 병합 비용은 남습니다.

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 단위 오차에 머문다면 리스 기간과 타임스탬프 여유를 그만큼 키워야 합니다. 그러면 애초에 줄이려던 지연이 다시 늘어납니다. 시계 오차 가정이 깨지면 성능 저하를 넘어, 감지되지 않는 정확성 오류가 발생합니다.

셋째 접근의 이득도 충돌과 일관성 요구에 달려 있습니다. Minerva는 요청별 WAN 조정을 에포크 합의로 묶지만 global commit 대기는 남고, 재실행 비용은 충돌률에 따라 늘어납니다. CRDT는 자료형이 보장하는 수렴 의미론 안에서만 동기식 조정을 피할 수 있습니다.

세 갈래를 조합할 때는 전제가 서로 독립적이지 않다는 한계도 있습니다. 예를 들어 Aspen은 리더 제거와 시계 기반 사전 정렬을 함께 쓰므로, 리더가 없다는 사실만으로 시계 가정까지 사라지지는 않습니다.

또한 비잔틴 장애를 견뎌야 하는 환경은 처리량 상한이 다른 곳에서 정해지므로 별도 축으로 봐야 합니다. 이 부분은 DAG 기반 BFT 합의와 리더 기반 BFT에서 다뤘습니다.

선택 기준

선택하려면 세 가지를 확인해야 합니다. 같은 키에 대한 동시 쓰기 빈도와 배포 환경의 시계 오차 상한을 측정해야 합니다. 애플리케이션이 병합 규칙을 스스로 정의할 수 있는지도 확인해야 합니다.

마지막 줄이 중요합니다. 시계 오차 상한을 운영 지표로 관측하지 않고 충돌률도 측정한 적이 없다면, 세 접근 중 무엇을 골라도 전제를 확인하지 않은 선택이 됩니다.

그 상태에서는 리더 기반 합의를 유지하고 리더 배치를 클라이언트 분포에 맞추는 선택이 보수적입니다. 이는 특정 논문의 결론이 아니라 앞의 전제를 적용한 운영 판단입니다.

정리

지리 분산 합의에는 광역 통신 지연이 들어가며, 이 글은 이를 줄이는 설계를 세 접근으로 비교했습니다. 조정 주체 분산과 시계 활용은 비용을 각각 충돌 복구와 오차 상한 가정으로 옮기며, 조정 범위 축소는 재실행이나 의미론적 충돌을 남깁니다.

CRDT는 합의를 더 빠르게 수행하는 프로토콜이 아니라 일부 연산의 동기식 합의를 피하도록 일관성 모델을 바꾸는 선택입니다. 어느 접근이 이득인지는 충돌률, 시계 오차 상한, 필요한 일관성 수준을 함께 확인해야 판단할 수 있습니다. 이 조건을 모른다면 리더 위치와 왕복 경로부터 측정해야 합니다.