[Distributed System] Consensus Algorithm

🧩 State Machine Replication

분산 시스템에서 여러 대의 서버가 하나의 거대한 컴퓨터처럼 동작하게 만드는 마법은 상태 머신 복제(State Machine Replication, SMR)라는 개념에서 시작됩니다. 수백 개의 노드가 흩어져 있는 환경에서도 사용자가 마치 단일 서버와 통신하는 것과 같은 환상을 유지하려면, 모든 노드가 동일한 상태를 공유하고 동일한 순서로 이벤트를 처리해야 합니다.

SMR의 핵심 철학은 “결정론(Determinism)”에 있습니다. 동일한 초기 상태에서 시작한 복제본(Replica)들이 동일한 입력 시퀀스를 동일한 순서로 수신하여 실행한다면, 그 결과로 도출되는 최종 상태 역시 반드시 동일해야 한다는 원칙입니다. 여기서 ‘입력’은 시스템의 상태를 변화시키는 명령(Command)을 의미하며, 이 명령들이 쌓인 기록 보관소를 우리는 로그(Log)라고 부릅니다.

Append-only Log

로그는 단순한 데이터의 나열이 아니라, 분산 시스템 내에서 발생하는 모든 사건의 선형적 시간축 역할을 수행합니다. 각 노드는 자신만의 로컬 로그를 관리하며, 합의 알고리즘의 주된 임무는 모든 노드의 로그가 정확히 같은 위치에 같은 명령을 갖도록 보장하는 것입니다.

이 구조에서 각 노드는 세 가지 핵심 컴포넌트로 구성됩니다.

• Consensus Module: 다른 노드들과 통신하며 로그의 내용과 순서에 대해 합의를 이끌어내는 지능형 레이어입니다.
• Log: 합의가 완료된(Committed) 명령들이 영구적으로 저장되는 저장소입니다.
• State Machine: 로그에 기록된 명령을 실제로 실행하여 애플리케이션의 상태(예: 데이터베이스의 키-값 쌍)를 변경하는 실행 엔진입니다.

비결정론적 요소의 위험성 (Non-determinism)

SMR 아키텍처에서 상태 머신이 수행하는 작업에 get_current_time()이나 random() 같은 비결정론적 함수가 포함되면 시스템은 즉시 붕괴합니다. 동일한 로그를 실행하더라도 노드마다 결과가 달라져 일관성(Consistency)이 깨지기 때문입니다. 모든 명령은 오직 입력 값과 이전 상태에만 의존해야 합니다.

커밋의 의미

단순히 로그에 명령을 쓴다고 해서 상태가 바로 변하는 것은 아닙니다. 합의 알고리즘은 특정 로그 엔트리가 ‘안전하게 복제되었음’을 확인하는 단계를 거치며, 이를 커밋(Commit)이라고 합니다. 일단 커밋된 로그는 어떤 장애 상황에서도 사라지지 않으며(Durability), 상태 머신은 오직 커밋된 로그만을 읽어 서비스에 반영합니다. 이 엄격한 파이프라인 덕분에 네트워크 지연이나 일부 노드의 다운 속에서도 전체 시스템은 단일한 진실을 유지할 수 있습니다.

🧩 Consensus

분산 시스템에서 합의(Consensus)는 단순히 투표를 통해 다수결을 따르는 민주적인 절차가 아닙니다. 이는 지연(Latency), 패킷 손실(Packet Loss), 그리고 노드 장애(Crash)가 일상적으로 발생하는 비신뢰 네트워크(Unreliable Network) 위에서, 모든 정상적인 노드가 ‘단 하나의 진실’을 선택하도록 강제하는 엄격한 프로토콜입니다.

합의의 본질적인 어려움은 “누가 죽었는지, 아니면 그저 느린 것인지”를 구별할 수 없다는 불확실성에서 기인합니다. 메시지를 보냈는데 응답이 없다면, 상대방의 서버가 전원 불량으로 멈춘 것일까요? 아니면 네트워크 스위치가 혼잡하여 응답이 10초 뒤에 도착하는 것일까요? 이 사소한 구분의 불가능성이 합의 알고리즘의 설계를 지옥으로 만듭니다.

FLP 불가능성

1985년, Fischer, Lynch, Paterson은 분산 컴퓨팅 역사상 가장 충격적인 논문을 발표합니다. 소위 FLP Impossibility라 불리는 이 이론은 “완전한 비동기 네트워크 환경에서는 단 하나의 노드만 결함이 생겨도, 결정론적(Deterministic)으로 합의를 마칠 수 있는 알고리즘은 존재하지 않는다”는 것을 증명했습니다.

비동기 시스템에서는 메시지 전달 시간에 상한선이 없으므로, 시스템이 무한히 ‘결정되지 않은 상태’에 머물 수 있는 시나리오가 반드시 존재한다는 뜻입니다. 우리가 사용하는 Raft나 Paxos 같은 알고리즘들은 이 이론을 무시하는 것이 아니라, 무작위성(Randomness)이나 타임아웃(Timeout)이라는 현실적인 타협안을 도입하여 이 논리적 교착 상태를 깨뜨립니다.

합의를 구성하는 3가지 절대 조건

모든 합의 알고리즘은 다음 세 가지 수학적 속성을 만족해야만 유효하다고 간주됩니다.

1. Agreement (합의): 모든 정상적인 노드는 동일한 값에 도달해야 한다.
2. Validity (유효성): 합의된 값은 반드시 누군가 제안한 값이어야 한다. (엉뚱한 값이 튀어나와선 안 된다.)
3. Termination (종료): 모든 정상적인 노드는 결국 어떤 값으로든 결정을 내려야 한다.

Safety와 Liveness의 줄타기

합의 알고리즘의 설계는 결국 Safety(안전성)와 Liveness(생존성) 사이의 균형을 맞추는 일입니다.

• Safety는 “나쁜 일(잘못된 합의)이 절대 일어나지 않음”을 보장합니다. 노드들이 서로 다른 값을 합의해 버리는 정합성 오류가 이에 해당합니다.
• Liveness는 “좋은 일(결국 합의됨)이 언젠가는 일어남”을 보장합니다. 시스템이 멈추지 않고 계속해서 요청을 처리해 나가는 가용성이 이에 해당합니다.

현실의 분산 시스템은 대개 Safety를 절대적으로 우선시합니다. 일시적으로 시스템이 응답하지 않을지언정(Liveness 포기), 데이터가 꼬여서 노드마다 다른 값을 가지고 있는 상황(Safety 포기)은 용납할 수 없기 때문입니다. 우리가 배우는 대부분의 합의 프로토콜은 네트워크 파티션 상황에서 가용성을 포기함으로써 데이터의 무결성을 수호합니다.

비잔틴 장애와의 경계

우리가 다루는 일반적인 합의 알고리즘(Paxos, Raft)은 노드가 단순히 멈추는 Fail-stop 장애를 가정합니다. 하지만 노드가 악의적으로 거짓 메시지를 보내거나 프로토콜을 변조하는 비잔틴 장애(Byzantine Fault) 상황은 이보다 훨씬 복잡한 합의 과정을 요구합니다. 일반적인 엔지니어링 환경에서는 노드가 아군(Trusted)이라는 가정하에 성능 최적화를 꾀하지만, 블록체인과 같이 누구도 믿을 수 없는 환경에서는 이 신뢰의 경계를 허무는 것에서부터 다시 합의를 시작해야 합니다.

🧩 Quorum

분산 시스템에서 정합성을 유지하는 가장 강력한 무기는 역설적이게도 ‘모든 노드의 동의를 구하지 않는 것’에 있습니다. 모든 노드가 응답할 때까지 기다리는 시스템은 단 하나의 노드만 고장 나도 전체가 마비되기 때문입니다. 여기서 등장하는 개념이 바로 쿼럼(Quorum), 즉 의사결정에 필요한 최소한의 정족수입니다. 쿼럼은 시스템의 가용성(Availability)과 일관성(Consistency) 사이에서 절묘한 균형을 잡는 수학적 장치입니다.

쿼럼의 핵심 원리는 ‘교집합의 보장’에 있습니다. 전체 노드 수가 $N$일 때, 어떤 결정에 참여한 노드들의 집합이 반드시 이전 결정에 참여했던 노드들의 집합과 적어도 하나 이상의 노드를 공유하도록 강제하는 것입니다. 이 중첩된 노드가 바로 과거의 기억(상태)을 현재로 전달하는 ‘진실의 전달자’ 역할을 수행합니다.

$N/2 + 1$

가장 흔히 사용되는 방식은 과반수 쿼럼입니다. 전체 노드가 5대라면 3대($5/2 + 1$)의 동의가 필요합니다. 왜 하필 과반수일까요? 수학적으로 $N$개의 원소를 가진 집합에서 과반수 크기의 두 부분집합을 추출하면, 이 두 집합은 반드시 최소한 하나의 공통 원소를 가질 수밖에 없기 때문입니다.

이 원리는 네트워크 파티션(Network Partition) 상황에서 빛을 발합니다. 네트워크가 물리적으로 두 그룹으로 쪼개졌을 때, 과반수를 확보한 그룹은 오직 한쪽뿐입니다. 나머지 그룹은 정족수 미달로 인해 어떤 결정도 내릴 수 없게 되어, 시스템 전체에서 서로 다른 두 개의 진실이 발생하는 ‘스플릿 브레인(Split-brain)’ 현상을 원천 차단합니다.

Read/Write 쿼럼의 상호작용

쿼럼은 단순히 과반수 모델에만 국한되지 않습니다. 읽기 쿼럼($R$)과 쓰기 쿼럼($W$)을 조정하여 시스템의 성능 특성을 바꿀 수 있습니다. 이때 반드시 지켜야 할 철칙은 다음과 같습니다.

쿼럼의 대원칙: $R + W > N$

읽기 정족수와 쓰기 정족수의 합이 전체 노드 수($N$)보다 커야 합니다. 이 조건이 만족되어야만 읽기 요청 시 최소한 한 대 이상의 노드는 반드시 가장 최신의 쓰기 데이터를 가진 노드임을 보장받을 수 있습니다.

• Write-Heavy 시스템: 쓰기 성능이 중요하다면 $W$를 낮추고 $R$을 높입니다. 하지만 최신 데이터를 찾기 위해 더 많은 노드를 뒤져야 하므로 읽기 지연 시간이 늘어납니다.
• Read-Heavy 시스템: 읽기 성능이 중요하다면 $W$를 높이고(모든 노드에 복제) $R=1$로 설정합니다. 어느 노드에서 읽어도 최신 데이터임을 보장받지만, 쓰기 시 단 한 대의 노드만 장애가 나도 전체 쓰기가 실패할 위험이 커집니다.

장애 허용 범위

쿼럼 시스템에서 우리가 감내해야 할 비용은 명확합니다. 전체 노드가 $N$대일 때, 시스템이 정상 작동하기 위해 견딜 수 있는 최대 장애 노드 수는 $F = (N-1)/2$입니다. 예를 들어:

• 3대 중 1대 장애까지 허용 (쿼럼 2대)
• 5대 중 2대 장애까지 허용 (쿼럼 3대)

여기서 흥미로운 점은 노드를 1대 추가한다고 해서 항상 장애 허용 능력이 선형적으로 늘어나지 않는다는 것입니다. 노드가 3대일 때와 4대일 때 모두 장애 허용치는 1대로 동일합니다(4대의 과반수는 3대이므로). 따라서 분산 시스템 아키텍처를 설계할 때는 효율적인 쿼럼 구성을 위해 노드 수를 주로 홀수로 유지하는 전략을 취합니다.

🧩 Leader & Follower

분산 시스템에서 합의에 도달하는 가장 빠른 방법은 무엇일까요? 아이러니하게도 의사결정권을 단 한 명에게 몰아주는 것입니다. 모든 노드가 서로 제안을 주고받으며 싸우는 대신, 모두가 인정하는 단 한 명의 리더(Leader)가 명령의 순서를 정하고, 나머지 팔로워(Follower)들은 그 결정을 묵묵히 따르는 방식입니다. 이 계층적 구조는 복잡한 합의 문제를 단순한 ‘복제’ 문제로 치환합니다.

리더는 시스템의 입구이자 사령탑입니다. 클라이언트의 모든 요청은 리더에게 집중되며, 리더는 이 요청들에 일련번호를 부여하여 로그에 기록합니다. 팔로워들은 리더가 보내주는 로그 조각들을 자신의 장부에 옮겨 적기만 하면 됩니다. 덕분에 네트워크 메시지 교환 횟수는 획기적으로 줄어들고, 시스템의 처리량(Throughput)은 비약적으로 상승합니다.

임기와 하트비트

절대 권력은 반드시 부패하거나, 더 흔한 경우로는 ‘죽습니다’. 리더 노드에 장애가 발생하면 전체 시스템이 마비되기 때문입니다. 이를 방지하기 위해 합의 알고리즘은 임기(Term 또는 Epoch)라는 논리적 시간 개념을 도입합니다.

리더는 자신이 살아있음을 증명하기 위해 팔로워들에게 주기적으로 하트비트(Heartbeat) 메시지를 보냅니다. “나는 아직 건재하니 새로운 선거를 열지 마라”는 신호입니다. 만약 정해진 시간(Election Timeout) 동안 하트비트가 도착하지 않으면, 팔로워들은 리더의 유명을 달리한 것으로 간주하고 즉시 다음 임기를 시작하며 새로운 리더 선출 프로세스에 돌입합니다.

리더십의 정당성 확인

새로운 리더가 나타났을 때, 팔로워들은 그가 들고 있는 ‘임기 번호’를 확인합니다. 만약 자신의 기록보다 낮은 번호를 들고 있는 리더가 명령을 내린다면, 팔로워는 그를 ‘과거의 유령’으로 취급하고 명령을 거부합니다. 이는 네트워크 지연으로 인해 뒤늦게 도착한 옛 리더의 메시지가 시스템을 교란하는 것을 막는 핵심 안전 장치입니다.

수동적 복제와 감시

팔로워는 결코 무능한 존재가 아닙니다. 그들은 리더의 명령을 복제하는 동시에, 리더가 쿼럼(Quorum)을 유지하고 있는지 확인하는 투표권자들입니다. 리더가 보낸 로그가 과반수 이상의 팔로워에게 안전하게 전달되었을 때만 그 명령은 ‘확정(Commit)’됩니다. 즉, 리더는 제안하고 팔로워는 검증합니다.

또한 팔로워는 리더가 된 노드가 정말로 자격이 있는지(가장 최신의 로그를 가졌는지)를 선거 과정에서 엄격히 심사합니다. 리더와 팔로워의 관계는 단순한 상하관계가 아니라, 합의라는 공동의 목표를 위해 서로를 견제하고 보완하는 유기적인 협력 관계에 가깝습니다.

병목 현상과 장애 조치

모든 요청이 리더를 거쳐야 한다는 점은 곧 리더가 시스템의 병목 지점(Bottleneck)이 될 수 있음을 의미합니다. 또한 리더가 교체되는 짧은 찰나의 순간 동안 시스템은 어떠한 요청도 처리할 수 없는 ‘가용성 공백’ 상태에 빠집니다. 합의 알고리즘 설계자들은 이 공백을 밀리초(ms) 단위로 줄이기 위해 선거 알고리즘을 최적화하고, 하트비트 간격을 정교하게 튜닝하는 데 수많은 밤을 지새웁니다.

🧩 Safety & Liveness

모든 분산 알고리즘의 명세서 가장 깊은 곳에는 두 가지 약속이 새겨져 있습니다. 하나는 “결코 틀리지 않겠다”는 약속이고, 다른 하나는 “결국 해내겠다”는 약속입니다. 우리는 이를 각각 Safety와 Liveness라고 부릅니다. 이 두 속성은 분산 시스템의 정당성을 평가하는 가장 근본적인 잣대이며, 동시에 서로를 밀어내는 긴장 관계에 놓여 있습니다.

Safety

Safety는 시스템의 정합성(Consistency)을 담보하는 장치입니다. 분산 합의에서 Safety가 지켜진다는 것은, 서로 다른 두 노드가 동일한 로그 인덱스에 대해 서로 다른 값을 커밋하는 비극이 발생하지 않음을 의미합니다. 일단 어떤 값이 ‘합의’되었다고 선언되면, 그 사실은 영원히 변하지 않아야 합니다(Immutability).

만약 Safety가 깨진다면, 사용자 A는 자신의 잔고가 100원이라고 믿는데 사용자 B의 화면에는 0원이라고 표시되는 데이터 오염이 발생합니다. 분산 시스템 엔지니어들에게 Safety는 타협 불가능한 성역입니다. 시스템이 잠시 멈출지언정(Liveness 포기), 잘못된 정보를 진짜라고 우기는 상황은 절대로 용납되지 않습니다.

Safety의 불변성

합의 알고리즘에서 Safety를 증명하기 위해 흔히 ‘단조 증가(Monotonicity)’ 성질을 이용합니다. 로그 인덱스는 뒤로 갈 수 없으며, 한 번 결정된 리더의 과거 이력은 덮어씌워질 수 없다는 규칙들이 모여 시스템 전체의 Safety를 형성합니다.

Liveness

반면 Liveness는 시스템의 전진(Progress)과 관련이 있습니다. 아무리 완벽하게 안전한 시스템이라도, 클라이언트의 요청에 영원히 응답하지 않는다면 그것은 죽은 시스템과 다름없습니다. Liveness는 “시스템에 참여한 정상적인 노드들이 충분하다면, 결국에는 합의에 도달하고 요청을 처리한다”는 것을 보장합니다.

현실 세계에서 Liveness를 위협하는 가장 큰 적은 무한 루프나 교착 상태(Deadlock)가 아니라, 네트워크 파티션과 리더 선출의 무한 반복입니다. 예를 들어, 두 노드가 정확히 동시에 리더 선거를 시작하고 똑같이 한 표씩 나눠 갖는 상황이 무한히 반복된다면 시스템의 Liveness는 소멸합니다. Raft는 이 문제를 해결하기 위해 ‘무작위 선거 타임아웃’이라는 지극히 현실적이고 우아한 해결책을 도입했습니다.

부분 동기화 모델

앞서 언급한 FLP 불가능성 원리에 따르면, 순수하게 비동기적인 환경에서는 Safety와 Liveness를 동시에 100% 만족시키는 결정론적 알고리즘을 만들 수 없습니다. 따라서 현대의 합의 알고리즘들은 Partial Synchrony(부분 동기화) 모델을 채택합니다.

이 모델에서 시스템은 평소에는 Safety와 Liveness를 모두 만족하며 기민하게 움직입니다. 하지만 극심한 네트워크 장애가 발생하면, 알고리즘은 즉시 Safety 모드로 전환합니다. “정확히 알 수 없다면 응답하지 않는다”는 전략을 취하는 것입니다. 장애가 해소되고 네트워크 지연이 일정 범위 안으로 들어오면, 시스템은 다시 Liveness를 회복하고 멈췄던 합의를 재개합니다.

분산 시스템의 트레이드오프

결국 엔지니어링은 선택의 문제입니다.

• Safety 우선: 금융 시스템, 데이터베이스 관리 시스템. 데이터의 정확성이 생명이며, 장애 시 서비스 중단을 감수하더라도 정합성을 지킵니다.
• Liveness 중심: 실시간 스트리밍, 단순 캐시 시스템. 최신 데이터가 아니더라도 일단 화면에 무언가 나오는 것이 중요할 때 선택합니다. (물론 이 경우 엄격한 의미의 ‘합의 알고리즘’보다는 최종 일관성 모델을 사용합니다.)

Raft Election Restriction

합의 알고리즘의 세계에서 가장 끔찍한 시나리오는 ‘과거를 모르는 리더’가 선출되는 것입니다. 만약 어떤 노드가 이미 과반수의 동의를 얻어 확정(Commit)된 로그를 가지고 있지 않은 채 리더가 된다면, 그는 자신의 비어있는 로그를 기준으로 다른 팔로워들의 소중한 데이터를 덮어씌워 버릴 것입니다. Raft는 이를 방지하기 위해 선출 제약 조건(Election Restriction)이라는 매우 단순하면서도 강력한 안전장치를 도입했습니다.

데이터의 최신성

Raft의 리더 선출 과정은 민주적이지만, 동시에 철저하게 실력(데이터의 최신성) 위주로 돌아갑니다. 어떤 후보자가 투표를 요청(RequestVote)하더라도, 투표를 하는 팔로워는 후보자의 로그가 최소한 자신의 로그보다 ‘최신(At least as up-to-date)’인지를 먼저 검사합니다. 만약 후보자의 로그가 자신보다 뒤처져 있다면, 팔로워는 가차 없이 투표를 거부합니다.

여기서 ‘최신성’을 판단하는 기준은 다음 두 가지 규칙을 엄격히 따릅니다.

1. Term(임기) 비교: 마지막 로그 엔트리의 임기 번호가 더 큰 쪽이 더 최신이다.
2. Index(인덱스) 비교: 만약 임기 번호가 같다면, 로그의 길이가 더 긴(마지막 인덱스가 더 큰) 쪽이 더 최신이다.

/**
 * Raft Election Restriction
 * * Raft의 Safety를 보장하는 핵심 로직인 '로그 최신성 비교'를 다룹니다.
 * 후보자가 과반수의 동의를 얻기 위해서는 반드시 투표자의 로그보다 최신이어야 합니다.
 */
public class RaftNode {
    private int currentTerm;
    private String votedFor;
    private List<LogEntry> log;
    private NodeState state;

    // ... 기타 필드 및 생성자 생략 ...

    /**
     * 후보자로부터 수신한 RequestVote RPC를 처리합니다.
     */
    public synchronized VoteResponse handleRequestVote(VoteRequest args) {
        // 1. 임기 비교: 후보자의 임기가 현재 나의 임기보다 낮으면 거절
        if (args.getTerm() < this.currentTerm) {
            return new VoteResponse(this.currentTerm, false);
        }

        // 2. 새로운 임기 발견: 임기 업데이트 및 상태 전환
        if (args.getTerm() > this.currentTerm) {
            this.currentTerm = args.getTerm();
            this.votedFor = null;
            this.state = NodeState.FOLLOWER;
        }

        // 3. 투표권 행사 가능 여부 확인 (votedFor 체크)
        if (this.votedFor == null || this.votedFor.equals(args.getCandidateId())) {
            
            // 내 로컬 로그의 마지막 상태 추출
            int myLastLogIndex = this.log.size() - 1;
            int myLastLogTerm = (myLastLogIndex >= 0) ? this.log.get(myLastLogIndex).getTerm() : 0;

            /**
             * [핵심 Logic] Raft Paper Section 5.4.1: Up-to-Date Restriction
             * * 1. 마지막 로그의 임기(Term)가 다르면, 더 높은 임기를 가진 로그가 최신이다.
             * 2. 마지막 로그의 임기가 같다면, 로그의 길이(Index)가 더 긴 쪽이 최신이다.
             */
            boolean isUpToDate = (args.getLastLogTerm() > myLastLogTerm) ||
                                 (args.getLastLogTerm() == myLastLogTerm && 
                                  args.getLastLogIndex() >= myLastLogIndex);

            if (isUpToDate) {
                this.votedFor = args.getCandidateId();
                resetElectionTimer(); // 투표 승인 시 선거 타이머 초기화
                return new VoteResponse(this.currentTerm, true);
            }
        }

        // 로그가 최신이 아니거나 이미 다른 후보에게 투표한 경우
        return new VoteResponse(this.currentTerm, false);
    }
}

/**
 * 로그 엔트리를 나타내는 불변 객체
 */
class LogEntry {
    private final int term;
    private final String command;

    public LogEntry(int term, String command) {
        this.term = term;
        this.command = command;
    }

    public int getTerm() { return term; }
}

투표 거부의 논리

이 제약 조건이 왜 중요한지 이해하려면 쿼럼(Quorum)의 원리를 다시 떠올려야 합니다.

어떤 로그가 커밋되었다는 것은 이미 과반수(Quorum)의 노드에 해당 로그가 복제되었음을 의미합니다. 그리고 새로운 리더가 선출되기 위해서도 역시 과반수의 투표가 필요합니다. 이 두 과반수 집합은 반드시 최소한 하나의 노드를 공유하게 됩니다.

이 공유된 노드는 반드시 커밋된 최신 로그를 가지고 있을 것이며, 선출 제약 조건에 의해 자신보다 뒤처진 로그를 가진 후보자에게는 절대 투표하지 않습니다. 결과적으로, 커밋된 모든 로그를 보유한 노드만이 리더로 당선될 수 있는 수학적 필연성이 완성됩니다. Paxos가 복잡한 로그 복구 과정을 거치는 것과 달리, Raft는 선출 단계에서 아예 자격 없는 리더를 걸러냄으로써 문제를 획기적으로 단순화했습니다.

로그 매칭 속성

Raft의 선출 제약 조건은 “리더가 된 노드의 로그는 무조건 옳다”는 전제를 만듭니다. 따라서 리더는 팔로워의 로그를 절대 삭제하거나 덮어쓰지 않으며, 오직 자신의 로그를 팔로워에게 강제로 복제하기만 하면 됩니다. 이는 복제 로직을 단방향으로 단순화하여 구현의 복잡성을 낮추는 결정적인 요인이 됩니다.

최신성 체크의 한계와 트레이드오프

하지만 이 우아한 설계에도 엔지니어링적인 비용은 존재합니다.

• 선거 지연 (Election Delay): 네트워크 파티션이나 특정 노드의 잦은 재시작으로 인해 로그가 파편화된 경우, 서로가 서로의 최신성을 인정하지 않아 투표가 무산되고 재선거가 반복되는 ‘Liveness 저하’ 현상이 발생할 수 있습니다.
• 복구 비용: 가장 최신 로그를 가진 노드가 하드웨어 장애로 영구히 격리된다면, 시스템은 차선의 로그를 가진 노드를 리더로 세우기 위해 복잡한 수동 개입이나 특수한 합의 무시 전략을 써야 할 수도 있습니다.

결국 Raft의 선출 제약 조건은 “조금 늦더라도(Liveness), 과거의 진실을 잃어버리는 일(Safety)은 절대 없어야 한다”는 분산 시스템의 철학적 선택이 구현된 결과물입니다.

Summary

합의 알고리즘은 신뢰할 수 없는 분산 환경에서 단일한 진실을 유지하기 위한 논리적 투쟁의 산물입니다. 복제 상태 머신(SMR)을 통해 모든 노드가 동일한 실행 경로를 걷게 하며, 쿼럼(Quorum)이라는 수학적 경계를 설정하여 물리적인 네트워크 단절 속에서도 데이터의 무결성을 수호합니다. Raft와 같은 현대적 프로토콜은 효율적인 리더십 모델과 엄격한 선출 제약을 결합하여 시스템의 복잡성을 인간이 이해 가능한 수준으로 제어하면서도 안전성(Safety)을 완벽히 증명해냅니다. 결국 합의란 불완전한 물리 세계 위에 완벽한 논리 체계를 구축하려는 엔지니어들의 정교한 타협이자 예술입니다.

References

• [Stanford] In Search of an Understandable Consensus Algorithm (Raft)
• [Microsoft] Paxos Made Simple (Leslie Lamport)
• [Cornell] Implementing Fault-Tolerant Services Using the State Machine Replication Approach
• [The Paper Trail] A Brief Tour of FLP Impossibility