3장: CAP와 PACELC, 그리고 합의 알고리즘

CAP 정리

브루어의 정리(Brewer's Theorem)로도 알려진 CAP 정리는 분산 시스템의 기본 원칙이다. 일관성(Consistency), 가용성(Availability), 파티션 허용성(Partition Tolerance) 세 가지를 동시에 취할 수 없다는 내용이다.

• AP를 선택하면 파티션이 발생해도 시스템을 계속 운영할 수 있지만, 모든 노드가 동일한 데이터를 유지하기 어렵다.
• CP를 선택하면 모든 노드가 항상 같은 데이터를 유지하지만, 일부 노드에서 사용자 요청을 처리하지 못할 수 있다.

PACELC 정리

바로 그 한계를 보완하는 개념이 PACELC다. 이름을 풀면 이렇게 읽힌다.

• Partition이 발생하면(Availability vs Consistency) 중 선택
• Else, 즉 파티션이 없을 때에도 (Latency vs Consistency) 중 선택

CAP가 다루지 못한 지점이 뒤쪽 절이다. 네트워크가 완전히 정상인 평시에도, 강한 일관성을 유지하려면 노드 사이에 합의를 거쳐야 하므로 지연 시간이 늘어난다. PACELC는 이 상시적인 트레이드오프를 명시적으로 드러낸다.

그리고 이 "여러 서버가 동일한 결정을 내리도록" 만드는 장치가 합의 알고리즘이다.

팩소스 알고리즘

1990년 레슬리 램포트가 발표한 합의 알고리즘으로, 현대 분산 시스템의 초석이 됐다. 세 가지 역할로 구성된다.

프로토콜은 제안 단계 → 준비 단계 → 수용 단계로 진행된다.

적용할 때 고려해야 할 것은 세 가지다.

• 장애 허용성 — 일부 노드가 작동하지 않거나 통신이 불가능할 때도 시스템이 원활하게 동작해야 한다
• 확장성 — 노드 개수가 많아지면 조율과 통신 부담으로 성능이 떨어진다
• 복잡성 — 구현이 어렵고, 모든 참여자가 프로토콜을 정확하게 따라야 한다

이 복잡성 때문에 변형이 여러 개 나왔다.

사용 사례로는 분산 데이터베이스의 레플리카 간 일관성 확보, GFS나 HDFS 같은 분산 파일 시스템의 메타데이터 관리, 그리고 상태 기계 복제(State Machine Replication)를 든다.

래프트 알고리즘

2013년 디에고 옹가로와 존 아우스터하우트가 발표한 합의 알고리즘이다. 팩소스와 같은 문제를 풀지만 이해하기 쉽게 설계된 것 자체가 목표였고, 그 덕에 구현 난이도가 낮아 대안으로 널리 쓰인다.

세 가지 노드 상태를 오간다.

프로토콜은 리더 선출 → 로그 복제 → 안정성과 일관성 확보 순으로 진행된다. 고려 사항은 리더 가용성(리더는 항상 활성 상태여야 한다), 확장성(노드가 늘면 통신 오버헤드가 커진다), 장애 허용성(추종자는 리더 이상 시 새 리더 선출에 참여할 수 있어야 한다)이다.

사용 사례는 넓다. 분산 데이터베이스(DynamoDB), 분산 파일 시스템, 클러스터 관리 및 서비스 디스커버리(아파치 주키퍼), 합의 기반 시스템(구글 스패너), 클라우드 인프라 관리 시스템 등이다.

비잔티움 장군 문제

시스템의 일부가 신뢰성을 잃거나 의도치 않게 동작할 때 신뢰할 수 있는 합의를 이루는 것이 어렵다는 사례로 다루는 고전적 문제다. 비잔티움 제국의 여러 장군이 각자 군대를 이끌고 있는데, 그중 배신자가 섞여 거짓 정보를 흘리는 상황에서 충성스러운 장군들만으로 하나의 계획에 합의해야 한다는 비유다.

해결을 위한 요구 조건은 이렇게 정리된다.

• 충성스러운 장군이 과반수를 넘어야 합의에 도달할 수 있다
• 장군 수를 N, 배신자 수를 F라 할 때 F가 (N-1)/2 보다 작으면 합의가 가능하다
• 합의에는 적당한 시간이 필요하다. 즉각적인 합의는 불가능하다

책이 제시하는 해결 방안은 다섯 가지다.

비잔티움 장애 허용성

시스템 내 일부 노드가 신뢰할 수 없는 상태가 되는 것을 비잔티움 장애(Byzantine Fault) 라 하고, 그 상황에서도 합의를 이루는 능력을 비잔티움 장애 허용성(BFT) 이라 한다.

초기 BFT는 고장난 노드가 전체의 3분의 1 미만일 때만 작동했고, 모든 노드가 서로 통신해야 했기 때문에 계산 및 통신 비용이 매우 컸다. 각 노드가 자신의 값을 다른 모든 노드에 투표 형식으로 보내는 방식이었으므로 메시지 수가 노드 수의 제곱으로 늘어난다.

이후 등장한 실용 비잔티움 장애 허용(PBFT, Practical BFT) 은 통신 비용을 줄여 대규모 네트워크에서도 동작할 수 있게 만들었다. 비트코인과 이더리움 같은 블록체인 기술을 포함한 최신 분산 시스템의 운영에서 중요한 위치를 차지한다.

FLP 불가능성 정리

마지막으로 책은 이론적 상한을 짚는다. FLP 불가능성 정리는 하나의 노드에 문제가 생겼을 때 완전 비동기 환경에서 모든 노드가 동일한 결정을 내리도록 하는 것이 불가능하다는 결과다.

전제 조건은 셋이다.

• 비동기성 — 메시지 지연 시간이나 프로세스 속도에 제한이 없다
• 프로세스 장애 — 전체 프로세스가 n개일 때 최대 f개까지 고장날 수 있다 (0 < f < n)
• 유한한 단계 — 각 프로세스는 정해진 유한한 단계만 수행하고 메시지 크기도 제한적이다

여기서 핵심은 "완전 비동기"라는 전제다. 실제 시스템은 이 전제를 깨는 방식으로 한계를 우회한다.

• 메시지 지연 시간에 정해진 시간 범위(타임아웃)를 설정한다
• 높은 확률로 합의에 도달하는 확률 알고리즘을 사용한다
• 무작위 요소나 시간 동기화 방식을 도입한다
• 리더를 선출하거나 조정자 역할을 둔다

래프트가 하트비트 타임아웃으로 리더 실패를 감지하고 리더를 선출하는 것이 바로 이 우회 전략의 실제 사례다. FLP는 "합의가 불가능하다"가 아니라 "타이밍 가정 없이는 불가능하다"는 정리로 읽어야 한다.

정리

3장의 전반부는 이 시리즈에서 가장 이론적인 대목이다. CAP 정리와 PACELC 정리를 통해 분산 시스템 설계에서는 어느 쪽에 우선순위를 둘지 결정하지 않을 수 없다는 점을 확인하고, 팩소스와 래프트로 그 결정을 실제로 실행하는 메커니즘을 본다. 비잔티움 장군 문제는 참여자를 신뢰할 수 없을 때로 문제를 확장하고, FLP 불가능성 정리는 비동기 환경에서 무엇이 원리적으로 불가능한지를 알려 준다.

이 네 개를 연결해서 보면 하나의 이야기가 된다. 파티션은 반드시 일어나고(CAP), 평시에도 일관성에는 비용이 붙고(PACELC), 합의는 가능하지만 복잡하고(팩소스/래프트), 참여자가 악의적이면 더 비싸지고(BFT), 아무 가정도 없으면 애초에 불가능하다(FLP). 개별 정리를 외우는 것보다 이 순서로 기억해 두는 편이 실제 설계 판단에 더 도움이 된다.