Cloudflare Meerkat: QuePaxa를 통한 전 세계적 분산 합의

Cloudflare Meerkat은 리더 기반 프로토콜에서 발견되는 ""타임아웃의 폭정""을 제거함으로써 고가용성 글로벌 합의를 제공합니다.

Cloudflare는 330개 이상의 글로벌 데이터 센터 전반에 걸쳐 중요한 컨트롤 플레인 상태를 관리하기 위해 설계된 실험적인 분산 합의 서비스인 Meerkat을 도입했습니다. 단일 권위 있는 리더에 의존하는 전통적인 합의 시스템과 달리, Meerkat은 QuePaxa 알고리즘을 활용하여 어떤 복제본(replica)이라도 합의를 주도할 수 있게 합니다. 이러한 아키텍처는 현재 리더가 실패하거나 네트워크 지연 시간이 급격히 변동하더라도 시스템이 읽기 및 쓰기 작업을 위해 가용성을 유지하도록 보장하며, Cloudflare가 이전에 Raft 기반 시스템에서 경험했던 서비스 중단을 방지합니다.

글로벌 컨트롤 플레인 데이터 요구 사항

리소스 배치 정보나 데이터베이스 리더십 상태와 같은 컨트롤 플레인 데이터는 광역 네트워크(WAN) 전반에서 안정적으로 작동하기 위해 강력한 일관성과 높은 결함 허용 능력이 결합되어야 합니다.

선형성 (강력한 일관성)

Meerkat은 가장 강력한 일관성 모델인 **선형성(linearizability)**을 목표로 합니다. 선형 시스템에서는 모든 작업이 실제 시간 흐름에 따라 정확하게 순서화됩니다. 이는 클라이언트가 어떤 글로벌 복제본에 접속하더라도, 쓰기 작업 이후에 수행된 모든 읽기 작업이 해당 쓰기 내용을 반드시 볼 수 있도록 보장합니다. 이 모델은 프로그래머가 분산 상태를 마치 단일 스레드 머신의 로컬 메모리처럼 다룰 수 있게 함으로써 개발을 단순화합니다.

결함 허용 및 정확성

Meerkat은 다음과 같은 조건 하에서 정확성과 가용성을 유지하도록 설계되었습니다:

• 과반수 가용성: 시스템은 과반수의 머신(2f+1 시스템에서 f+1)이 살아 있고 통신 중인 한 읽기 및 쓰기 작업을 위해 가용성을 유지합니다.
• 클라이언트 액세스: 클라이언트는 살아 있는 머신의 과반수와 연결된 모든 머신과 상호작용할 수 있습니다.
• 비-Byzantine 결함: 시스템은 어떤 행위자가 능동적으로 악의적이지 않은 한 정확성을 유지하며, 머신 충돌, 재시작 및 네트워크 성능 저하를 처리합니다.

아키텍처: Meerkat 로그 및 QuePaxa

Meerkat은 트랜잭션 키-값(KV) 저장소나 리싱(leasing) 시스템과 같은 애플리케이션이 구축되는 기반으로 작동합니다.

분산 로그

Meerkat의 핵심은 ""slots""의 시퀀스를 유지하는 것입니다. 각 슬롯은 비어 있거나 결정된 이벤트가 포함될 수 있습니다.

• 슬롯을 통한 일관성: 두 복제본이 특정 슬롯에 대해 값을 결정하면, 그 값들은 반드시 동일해야 합니다.
• 선형적 읽기: 선형성을 보장하기 위해, get 요청조차 로그 이벤트를 생성합니다. 만약 복제본이 비어 있다고 믿는 슬롯에서 읽기를 시도하지만, 과반수가 이미 해당 슬롯에 대해 값을 결정했다면, 복제본은 읽기를 완료하기 전에 과반수와 동기화하도록 강제되어, 이전 쓰기 작업 이후에 효과적으로 읽기를 선형화합니다.

왜 Raft 대신 QuePaxa인가?

Cloudflare는 광역 네트워크(WAN)에서 발생하는 특정 가용성 문제를 해결하기 위해 Raft에서 QuePaxa로 전환했습니다:

1. 리더 병목 현상 제거: Raft에서는 모든 쓰기가 단일 리더를 거쳐야 합니다. 리더가 실패하거나 느려지면 전체 시스템이 차단됩니다. QuePaxa에서는 어떤 복제본이라도 최신 슬롯에 대한 합의를 주도할 수 있습니다.
2. 타임아웃 문제 방지: Raft는 새로운 리더 선출을 트리거하기 위해 타임아웃에 의존합니다. 예측 불가능한 WAN에서는 타임아웃이 너무 짧으면 불필요한 선출이 계속 발생하고, 타임아웃이 너무 길면 다운타임이 증가합니다. QuePaxa는 타임아웃으로 인해 진행이 중단되지 않습니다.
3. 건설적 간섭: Raft의 리더십 캠페인은 서로 간섭하여 쓰기를 차단할 수 있지만, QuePaxa는 여러 복제본이 동시에 값을 제안할 수 있게 합니다. 이러한 제안들은 파괴적인 간섭이 아닌, 값을 결정하기 위해 함께 작동합니다.

성능 트레이드오프 및 최적화

합의 알고리즘은 여러 번의 네트워크 왕복이 필요하기 때문에, Meerkat은 범용 데이터베이스가 아닌 빈번하지 않은 쓰기가 발생하는 컨트롤 플레인 데이터용으로 설계되었습니다.

지연 시간 제약 사항

결정 지연 시간은 과반수 복제본 간의 네트워크 지연 시간에 비례합니다. 제안(proposal)은 리더에 의해 주도될 경우 일반적으로 한 번의 왕복(round trip)이 소요되며, 리더가 아닌 경우 세 번 이상의 왕복이 소요됩니다.

성능 완화 전략

처리량을 개선하고 체감 지연 시간을 줄이기 위해 Meerkat은 여러 전략을 사용합니다:

• 배칭(Batching): 복제본들은 여러 쓰기 작업을 하나의 제안으로 그룹화할 수 있습니다.
• 복제본 배치: 개발자는 전체 글로벌 분산이 필요하지 않은 서비스의 경우 복제본을 더 가깝게 배치하여 왕복 시간을 줄일 수 있습니다.
• 오래된 읽기(Stale Reads): 엄격한 선형성이 필요하지 않은 애플리케이션의 경우, 합의 라운드를 트리거하지 않고 복제본의 로컬 데이터로부터 읽기 서비스를 제공할 수 있습니다.
• 묶음 작업(Bundled Operations): KV 저장소는 단일 합의 라운드 내에서 일반 트랜잭션 및 compare-and-swap (CAS) 쓰기를 지원합니다.

현재 상태

Meerkat은 현재 내부 실험적 서비스입니다. 최대 50개의 글로벌 복제본을 사용하는 개념 증명(Proof-of-concept) 배포를 통해, 리더가 지속적으로 실패하더라도 클러스터가 에러율 증가 없이 계속 작동함을 입증했습니다.