2PC의 한계, 합의 알고리즘의 등장
분산 시스템에서 여러 노드가 동일한 결정을 내려야 하는 상황을 흔히 볼 수 있다. 하지만 네트워크 지연, 메시지 유실, 노드 장애 등으로 인해 모든 노드가 동일한 상태를 보장하는 것은 쉽지 않다. 이를 처음 해결하고자 등장한 방식이 Two-phase commit (2PC) 이다. 코디네이터 노드(Coordinator)가 트랜잭션 참여자(Participant)들에게 사전 승인 요청을 보내고, 모두가 동의하면 커밋을 진행한다.
그러나 2PC는 구조적인 결함이 있다. Coordinator가 커밋 직전에 장애를 겪는다면, 참여자 노드는 어떻게 해야 할지 모른 채 블로킹된다. 시스템은 멈추고, 사람의 개입 없이는 복구가 어렵다. 이러한 단일 실패점(SPoF)과 비가용성 문제는 분산 시스템의 요구사항과 맞지 않는다. [2PC 참고]
이러한 문제를 해결하기 위해 다양한 대안이 논의되었고, 일부 시스템에서는 Coordinator를 이중화하거나 타임아웃 후 롤백을 강제하는 등의 방식을 도입했다. 하지만 이러한 초기 해결 방안도 여전히 완전한 복구와 정합성을 보장하지 못했다.
결국 이 한계를 구조적으로 극복하기 위한 대안으로 등장한 것이 바로 합의(Consensus) 알고리즘 이다.
합의 (Consensus)
합의란 여러 노드들이 동일한 결정에 동의해야 한다는 것이다.
누가 리더가 될지, 어떤 값이 최종 결과인지, 어떤 요청이 처리되었는지 등을 모든 정상 노드가 동의해야 한다.
합의는 단순히 투표로 끝나는 것이 아니라, 네트워크 장애와 노드 장애 상황에서도 일관성을 유지해야 하기 때문에 매우 복잡하다.
Raft, Paxos, Zab, Viewstamped Replication 등은 이러한 환경에서 안전하게 합의를 보장하기 위한 알고리즘이다.
이들은 정족수(quorum) 기반의 투표, 로그 복제, 리더 선출, 에포크 기반의 버전 관리 등을 통해 일부 노드가 장애를 겪어도 시스템 전체가 하나의 일관된 상태를 유지하게 한다.
Raft 알고리즘의 동작 과정
합의 알고리즘의 속성
합의 과정은 보통 하나 또는 그 이상의 노드들이 값을 제안할 수 있고, 합의 알고리즘이 그 값들 중 하나를 결정하는 방식으로 진행된다.
이러한 형식에서 합의 알고리즘은 다음 4가지 속성을 만족해야 한다.
균일한 동의 (Agreement)
어떤 두 노드도 서로 다른 결정을 내리지 않는다.
균일한 동의는 모든 노드가 동일한 최종 결정에 도달해야 한다는 속성이다. 만약 한 노드가 특정 값을 결정했다면, 다른 모든 정상 노드 역시 반드시 동일한 값을 결정해야 한다.
이는 분산된 환경에서 데이터 불일치나 충돌이 발생하는 것을 방지하며, 시스템 전반의 일관성을 유지하는 데 필수적이다.
무결성 (Integrity)
어떤 노드도 2번 결정하지 않는다.
무결성은 어떤 노드도 한 번 결정한 값을 번복하거나 두 번 이상 결정해서는 안 된다는 속성이다. 즉, 한 번 합의된 값은 영구적으로 유지되어야 하며, 재시도나 장애 복구 과정에서도 동일한 트랜잭션이 중복으로 커밋되거나 기존 결정이 변경되는 문제가 발생해서는 안 된다.
이는 시스템의 신뢰성을 보장하고 데이터의 정확성을 유지하는 데 중요한 역할을 한다.
유효성 (Validity)
한 노드가 값 v를 결정한다면, v는 어떤 노드에서 제안된 것이다.
유효성은 합의된 값이 반드시 제안된 값들 중 하나여야 한다는 속성이다. 어떤 노드도 제안하지 않은 임의의 값에 대해 합의가 이루어져서는 안 된다.
이는 외부의 노이즈, 악의적인 공격, 또는 네트워크 오류 등으로 인해 잘못된 값이 합의되는 것을 방지하여, 합의 과정의 정당성을 확보하고 비정상적인 값의 도입을 막는 역할을 한다.
종료 (Termination)
죽지 않은 모든 노드는 결국 어떤 값을 결정한다.
종료는 정상적인 모든 노드가 결국에는 어떤 값으로든 결정을 내려야 한다는 속성이다. 아무리 오랜 시간이 지나더라도 시스템이 무기한 응답 불능 상태에 빠지지 않고, 최종적으로 합의를 완료해야 한다.
이는 네트워크 지연이나 일부 노드의 장애 상황에서도 시스템이 멈추지 않고 계속해서 작동하며, 최종적으로 결정 도달을 보장하는 속성이다.
균일한 동의, 무결성, 유효성은 시스템이 잘못된 결정을 내리지 않도록 보장하는 안정성(Safety)을 제공한다.
반면, 종료 속성은 시스템이 멈추지 않고 결국 결정을 내릴 수 있도록 보장하는 활동성(Liveness)을 제공한다.
이 속성들은 동시에 만족하기 어렵다.
특히, 동기적 환경이 아닌 비동기 네트워크 환경에서는 안정성과 활동성 사이에 충돌이 생긴다.
안정성과 활동성의 Trade-off
분산 시스템에서 합의 알고리즘은 안정성(Safety)과 활동성(Liveness)이라는 두 가지 중요한 속성 사이에서 균형을 잡아야 한다.
하지만, 비동기 네트워크 환경에서는 두가지 속성을 동시에 보장하기 어려워진다.
비동기 네트워크의 특징
1. 메시지 전송 시간의 불확실성
메시지가 언제 도착할지, 심지어 도착할지 안 할지 예측할 수 없다.2. 메시지 순서의 불확실성
메시지가 전송된 순서대로 도착한다는 보장이 없다.3. 노드 실패 감지의 어려움
메시지 지연과 노드 실패를 구분하기 매우 어렵다.
특정 노드가 응답하지 않을 때, 그 노드가 단순히 느린 것인지, 네트워크가 메시지를 유실한 것인지, 아니면 노드 자체가 죽은 것인지 확신할 수 없다.
안정성을 우선할 경우
안정성을 우선시한다는 것은 시스템이 절대로 잘못된 상태에 도달하지 않도록 보장하는 것을 의미한다. 비동기 네트워크 환경에서 이를 위해 시스템은 다음과 같은 선택을 하게 된다.
불확실한 상황에서는 대기
메시지 지연이나 노드 응답 없음을 즉각적인 실패로 간주하지 않고, 충분히 기다리거나 추가적인 확인 절차를 거친다.
이는 잘못된 판단으로 인해 데이터 불일치가 발생하는 것을 막아야 하기 때문이다.엄격한 합의 프로세스
모든 노드가 올바른 상태를 공유하고 있음을 정족수(Quorum) 기반의 투표나 여러 단계의 커밋 프로토콜을 통해 확인한다. 메시지 손실이나 순서 뒤바뀜이 발생해도 안정적인 결과를 도출할 수 있도록 재전송, 메시지 식별자 등을 활용한다.
하지만 이러한 안정성 우선 전략은 필연적으로 활동성을 저해한다.
노드 응답을 무한정 기다리거나, 복잡한 합의 단계를 거치면 시스템의 응답 시간이 길어지고, 심지어 일부 노드의 장애나 네트워크 분할 시 시스템 전체가 멈추거나 동작 불능 상태에 빠질 수 있다.
활동성을 우선할 경우
활동성을 우선시한다는 것은 시스템이 항상 응답할 수 있고, 궁극적으로 작업을 완료할 수 있도록 보장하는 것을 의미한다. 비동기 네트워크 환경에서 이를 위해 시스템은 다음과 같은 선택을 하게 된다.
불확실한 상황에서도 진행
특정 노드의 응답이 없거나 네트워크 지연이 발생해도 일정 타임아웃 후 해당 노드를 무시하고 계속 진행하거나, 비동기적으로 데이터를 전파하여 빠르게 응답한다.느슨한 일관성 허용
모든 노드가 즉시 동일한 최신 데이터를 가지는 것을 강제하기보다, 최종 일관성(Eventual Consistency)과 같이 시간이 지나면 모든 노드가 일치하게 되는 모델을 채택한다.
이 경우, 일시적인 데이터 불일치가 허용된다.
이러한 활동성 우선 전략은 시스템의 응답성과 가용성을 높이지만, 안정성을 희생할 수 있다.
응답이 없는 노드를 배제하고 진행했을 때 실제로는 그 노드가 중요한 최신 정보를 가지고 있었을 경우 데이터 불일치가 발생할 수 있고, 느슨한 일관성 모델에서는 사용자가 오래된 데이터를 보게 되는 문제가 발생할 수 있다.
Paxos와 Raft의 안정성 우선 전략
Paxos나 Raft는 안정성을 절대적으로 보장하고, 활동성은 네트워크 상황에 따라 양보한다.
실제 운영 환경에서는 이 Trade-off가 뚜렷하게 드러난다. 예를 들어, 장애 복구 중 클러스터가 split-brain 상태에 빠져 두 리더가 동시에 커밋을 진행한다면, 동일한 로그 슬롯에 서로 다른 값이 기록되는 심각한 오염이 발생할 수 있다.
이러한 상황에서는 활동성을 포기하고서라도 안정성을 지키는 것이 더 중요하다. 데이터 무결성을 잃은 시스템은 더 이상 신뢰할 수 없기 때문이다.
현실적인 활동성 보장 방안
Paxos는 이론적으로 활동성(종료, Termination)을 보장하지 않는 것으로 알려져 있다. 그러나 실제 구현에서는 이러한 문제를 해결하기 위해 다양한 휴리스틱(Heuristics)을 사용한다. 예를 들어, 리더를 강제로 선출하거나, 타임아웃 기반의 재시도를 통해 합의 프로세스가 더 빠르게 종료될 가능성을 높인다.
Raft는 Paxos보다 구현이 쉬우면서도 활동성 속성을 보다 명확히 보장하도록 설계되었다. Raft는 일정 시간 동안 리더로부터 메시지를 받지 못하면 새로운 리더 선출 프로세스를 시작하여 합의 프로세스를 재개한다. 이는 시스템이 특정 상황에서 무한히 기다리지 않고 능동적으로 복구를 시도하도록 돕는다.
현실적인 분산 시스템에서는 이론적인 활동성을 완벽하게 보장하는 것보다, 합의가 지연되거나 중단되었을 때 이를 빠르게 감지하고 복구할 수 있는 메커니즘을 설계하는 것이 중요하다.
예를 들어, K8s의 핵심 분산 저장소인 etcd는 Raft 알고리즘을 기반으로 하며, 리더 장애 발생 시 빠르게 새로운 리더를 선출하여 시스템 중단 시간을 최소화한다.
Reference
Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly Media, 2017.
