Consensus Algorithms & Distributed Log

1. Overview

합의 알고리즘과 분산 로그(Consensus Algorithms & Distributed Log)는 서로를 완전히 신뢰할 수 없고 언제든 죽을 수 있는 분산된 컴퓨터들이, 거짓말과 네트워크 단절을 극복하고 **"하나의 완벽한 진실(상태)"**에 도달하게 만드는 마법 같은 수학적 엔진을 해부합니다.

학습자는 누가 대장이 될지(리더 선출) 결정하고 모든 부하 서버에 똑같은 순서로 데이터를 복제시키는 가장 난해한 분산 합의 알고리즘인 Paxos의 학술적 위대함과, 이를 실무 엔지니어의 언어로 풀어내어 현대 인프라(Kubernetes etcd 등)를 지배한 Raft 알고리즘의 뼈대를 뜯어봅니다. 나아가 분산 시스템에서 상태를 동기화하는 가장 완벽한 자료구조인 **Append-only 분산 로그(Distributed Log)**의 물리적 메커니즘을 해부합니다. 마지막으로, 스플릿 브레인(Split Brain)과 비잔틴 장군 문제(Byzantine Generals Problem) 같은 악의적 분산 환경 속에서도 단 하나의 단일 진실 공급원(Single Source of Truth)을 지켜내는 최상위 인프라 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 분산 합의 (Distributed Consensus): 다수의 노드가 장애 속에서도 동일한 값에 합의(Agreement)하는 과정.
• 합의 알고리즘: Paxos (학술적 토대), Raft (이해하기 쉬운 리더 기반 합의), Quorum(과반수 정족수).
• 합의 메커니즘 2단계: Leader Election (리더 선출)과 Log Replication (로그 복제).
• 분산 로그 (Distributed Log): Append-only 로그를 통한 State Machine Replication (상태 기계 복제) 원리.

Out-of-Scope

• 비트코인 등 퍼블릭 블록체인의 PoW/PoS: 신뢰할 수 없는(악의적인) 불특정 다수가 참여하는 합의 $\rightarrow$ 10-04 Web3 & Blockchain Architecture 영역으로 위임 (본 문서는 기업 내부의 프라이빗 신뢰 네트워크를 다룸).
• 카프카(Kafka)의 상세 파티션 튜닝: 분산 로그 활용 큐 $\rightarrow$ 07-04 Event-Driven Systems 영역.

Boundaries

• Crash Fault vs Byzantine Fault: Raft나 Paxos 같은 일반 기업용 인프라 합의 알고리즘은 서버가 정전으로 '죽거나(Crash)' '지연되는' 장애만을 가정합니다. 서버가 살아서 '거짓말을 치고 데이터를 조작하는' 악의적인 오류(비잔틴 오류)는 방어하지 못합니다. 악의적 오류까지 방어하려면 성능이 수백 배 떨어지는 BFT(PBFT, 블록체인 채굴 등) 알고리즘이 필요하며, 엔터프라이즈 사내망(신뢰 네트워크)에서 BFT를 도입하는 것은 끔찍한 오버엔지니어링임을 명확히 경계 짓습니다.

3. Counterexample

• 짝수 노드의 저주와 스플릿 브레인 (Split Brain): 4대의 서버로 클러스터를 구성했습니다. 랜선이 끊겨 2대 vs 2대로 네트워크가 쪼개졌습니다(Partition). 양쪽 진영이 모두 "우리가 과반수니까 우리가 대장이다"라고 선언하며 각자 리더를 뽑고 데이터를 따로 기록하기 시작합니다. 랜선이 복구된 후 DB를 합치려 보니 양쪽 데이터가 정반대로 오염되어 시스템이 붕괴합니다. '과반수(Quorum)'를 절대 만들 수 없는 짝수 설계가 낳은 분산 시스템 최악의 참사입니다. 클러스터는 반드시 홀수(3, 5, 7)로 구성해야 합니다.
• 마스터-슬레이브의 단일 장애점 (SPOF): MySQL 마스터 1대와 슬레이브 2대를 띄웠습니다. 마스터가 죽자, 관리자가 새벽에 일어나 슬레이브 중 하나를 마스터로 수동 승격시킵니다. 그사이 데이터가 유실되었습니다. Raft와 같은 합의 알고리즘이 내부적으로 심어져 있지 않은 단순 복제 환경(Primary-Replica)에서는 '누가 리더인지' 스스로 깨닫고 자동 투표를 진행하는 메커니즘이 없어 장애 복구(Failover)가 사람의 손에 의존하게 되는 후진적 안티 패턴입니다.

4. Prerequisites

• 네트워크 분할 (Basic): 네트워크 단절 시 일어나는 CAP 정리의 트레이드오프. (07-02-01 Theorems)
• 자료구조 (Basic): Append-only Log의 단순성과 불변성. (04-02 Core Data Structures)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 두 장군의 딜레마, 분산 합의의 고통 (The Consensus Problem)

• Why to Learn: 분산 시스템에서 '완벽한 동기화'를 보장한다는 것이 네트워크 패킷의 본질적 불확실성 앞에서 얼마나 불가능에 가까운 수학적 난제인지 직시하기 위함입니다.
• What to Learn:
  • Concepts: The Two Generals' Problem (두 장군 문제), 합의(Consensus), 네트워크 불확실성(Uncertainty).
  • Skills: 상태 불일치 시나리오 식별, 무한 ACK(확인 응답) 지옥 인지.
• How to Learn:
  • 1단계: 두 장군 문제: 적진을 사이에 두고 떨어져 있는 두 장군이 내일 오전 9시에 동시에 공격해야 이깁니다. A 장군이 "내일 9시 공격!" 메시지를 B에게 보냅니다. B가 "확인!"이라고 답장을 보냅니다. 그런데 B는 "내 답장이 A에게 잘 갔을까?" 불안해합니다. A가 "너의 답장 잘 받았어!"라고 다시 보냅니다. A도 불안해집니다. 완벽한 합의를 위해 확인(ACK)을 영원히 주고받아야 하는 무한 루프의 절망을 해부합니다.
  • 2단계: 확률적 타협: 100% 완벽한 합의는 이론상 불가능함(Fischer-Lynch-Paterson impossibility)을 인지하고, 타임아웃과 앙상블(다수결)을 통해 '실용적으로 거의 완벽한' 합의로 타협하는 기조를 뜯어봅니다.
• Implement: 파이썬 무한 루프 통신 스크립트. Node A와 Node B가 소켓으로 메시지를 주고받되 패킷 손실 확률 $20\%$. 서로 메시지 1번을 보내고 상태를 COMMITTED로 바꾸려 하지만, 패킷 로스 의심 때문에 상태를 확정 짓지 못하고 ACK만 계속 주고받는 데드락(Deadlock) 데모 렌더링.

Recommended

Core Topic 02: 갈라진 뇌와 과반수의 철칙 (Quorum & Split Brain)

• Why to Learn: Zookeeper, etcd(Kubernetes), Kafka 등 모든 최상위 분산 클러스터가 왜 무조건 노드를 홀수(3, 5, 7대)로 배포하라고 강요하는지 그 물리적 절대 법칙을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Quorum(정족수, 과반수), Split Brain(분할 뇌), Majority, 홀수(Odd number) 클러스터 룰.
  • Skills: N개의 노드 클러스터에서 장애 허용 수(Fault Tolerance) 수학적 도출.
• How to Learn:
  • 1단계: 스플릿 브레인의 파국: 4대 클러스터(A, B, C, D)가 랜선 고장으로 [A, B]와 [C, D]로 반갈죽 났습니다. 양쪽 다 2표씩 얻어 자신들이 리더라고 주장하며 뇌가 두 개로 갈라집니다. 클라이언트 요청이 양쪽으로 나뉘어 들어가 데이터베이스가 완전히 붕괴하는 현상을 해부합니다.
  • 2단계: 과반수(Quorum)의 방어막: 5대 클러스터입니다. 반갈죽 나면 반드시 [3대] vs [2대]가 됩니다. 오직 [3대] 쪽만이 전체 5대의 과반수($N/2 + 1$)를 만족하므로 유일한 리더로 살아남고, [2대] 쪽은 침묵(정지)하여 무결성을 지켜내는 매직 넘버 홀수 룰을 뜯어봅니다.
• Implement: 클러스터 분할 시뮬레이터 로직. N대의 노드를 입력받아, 두 그룹으로 쪼개는 모든 경우의 수 생성. 양쪽 다 '과반수(N/2+1 이상)'를 달성하는 불가능한 상황(모순)이 오직 홀수 대에서만 원천 차단된다는 수학적 팩트 체크를 콘솔에 증명하는 파이썬 코드.

Practical

Core Topic 03: 천하통일 타임라인, Raft 알고리즘 (Raft: Leader & Log)

• Why to Learn: 수십 쪽짜리 학술 논문인 Paxos를 인간 엔지니어가 구현할 수 있게 실용화하여, 현재 거의 모든 현대 분산 클러스터의 심장(Core)이 된 Raft의 2단계 완벽 타임라인을 분해하기 위함입니다.
• What to Learn:
  • Concepts: Leader Election(리더 선출), Log Replication(로그 복제), Heartbeat(심장박동), Term(임기), Randomized Timeout(무작위 타임아웃).
  • Skills: Raft 시뮬레이션 기반 장애(Leader Down) 복구 추적.
• How to Learn:
  • 1단계: 랜덤 타임아웃의 마술(Election): 리더가 죽으면 모든 부하(Follower)들의 타이머가 돌기 시작합니다. 만약 다 똑같이 150ms 타이머를 돌리면 동시에 깨어나서 표가 분산됩니다. 누구는 150ms, 누구는 200ms로 '타이머를 무작위로' 돌려, 제일 먼저 깨어난 놈이 1표를 가져가 즉각 리더가 되는 우아한 충돌 회피 알고리즘을 해부합니다.
  • 2단계: 로그 복제(Replication): 리더가 정해지면, 클라이언트 요청(쓰기)은 무조건 리더만 받습니다. 리더가 부하들에게 "데이터 쓴다?"(AppendEntries) 쏘고, 과반수 부하가 "준비 완료!"(ACK)를 주면 그제야 "진짜로 써라!"(Commit) 명령을 내리는 완벽한 2PC(Two-Phase) 복제 타임라인을 뜯어봅니다.
• Implement: 3노드 Raft 리더 선출 파이썬 미니 시뮬레이터. A(150ms), B(210ms), C(300ms) 무작위 타이머 설정. 스레드를 띄우고 리더 A가 100ms마다 하트비트(Heartbeat)를 보내 타이머를 리셋함. 강제로 A 스레드를 죽이면(Kill), 150ms 후 B가 깨어나 부하 C에게 투표를 강요(Vote Request)하여 새 리더로 승격되는 터미널 로그 데모.

Advanced

Core Topic 04: 불변의 기록 릴레이, 분산 로그와 상태 기계 (Distributed Log & State Machine)

• Why to Learn: Kafka, 데이터베이스 복제, 블록체인의 기반이 되는 "Append-only Log를 순서대로 재생하면, 어떤 컴퓨터든 똑같은 상태가 된다"는 가장 위대한 분산 아키텍처 패턴을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Distributed Commit Log, State Machine Replication (상태 기계 복제), Append-only, Idempotency(멱등성), Offset(오프셋).
  • Skills: 무상태 노드(Stateless Node)에 이벤트 로그를 주입하여 동기화된 상태 구축.
• How to Learn:
  • 1단계: Append-only 로그: RAM의 딕셔너리 값 x=5를 통째로 복제하는 것은 위험합니다. 대신 [로그1: x=1 설정], [로그2: x에 4 더함]이라는 불변의 로그 스트림을 순서대로 디스크에 박아 넣습니다.
  • 2단계: 복제인간 만들기 (State Machine Replication): 텅 빈 새로운 서버가 클러스터에 합류합니다. 기존 데이터베이스를 복사할 필요 없이, 1번 로그부터 1,000번 로그까지 차례대로 실행(Replay)하기만 하면 완벽하게 동일한 상태(State)의 쌍둥이 서버가 탄생하는 결정론적(Deterministic) 복제 원리를 해부합니다.
• Implement: 파이썬 State Machine Replication 시뮬레이션. 빈 dict() 변수를 가진 Node 1, 2, 3. 거대한 배열 Event_Log (예: ["SET x=10", "ADD x=5", "MUL x=2"]). 세 노드가 배열의 인덱스(Offset) 0번부터 순차적으로 루프를 돌며 정규표현식으로 파싱하여 본인의 dict를 업데이트함. 결국 세 노드가 완벽히 {'x': 30}이라는 동일한 상태에 수렴함을 콘솔로 증명.

7. Terminology

8. References

Primary

• [P1] CS2023 - Parallel and Distributed Computing (PDC) - Distributed Consensus
• [P5] SFIA - Enterprise IT Architecture (ARCH) - Fault Tolerance

Secondary

• [In Search of an Understandable Consensus Algorithm] Diego Ongaro, John Ousterhout - The Raft Paper
• [Designing Data-Intensive Applications] Martin Kleppmann - Consistency and Consensus

Industry

• [etcd Documentation] - Understanding the Raft Consensus Algorithm in Kubernetes
• [Confluent Blog] - Kafka, ZooKeeper, and the Magic of Distributed Logs

9. Final Checklist

Primary

• 물리적으로 떨어진 두 대의 서버가 패킷 손실 확률이 존재하는 네트워크를 통해 100% 완벽한 합의(두 장군 문제)에 도달하는 것이 수학적으로 불가능함을 증명할 수 있는가?
• Zookeeper나 Kubernetes의 etcd 같은 클러스터 노드를 배포할 때, 왜 4대(짝수)가 아닌 3대나 5대(홀수)로 배포해야 스플릿 브레인(Split Brain)을 막을 수 있는지 논증할 수 있는가?

Secondary

• Raft 알고리즘에서 리더(Leader)가 죽었을 때, 남은 Follower 노드들이 무작위 타임아웃(Randomized Timeout)을 돌려 표의 분산을 막고 새로운 리더를 선출하는 역학을 해부할 수 있는가?
• 합의 알고리즘에 기반한 시스템(Raft)과 단순 마스터-슬레이브 복제 시스템(MySQL Async Replication) 사이의 데이터 유실(Data Loss) 허용 범위와 장애 복구 자동화(Auto Failover) 수준을 비교할 수 있는가?

Industry

• 상태 기계 복제(State Machine Replication) 아키텍처에서, 리더가 부하 서버들에게 데이터를 쏠 때(AppendEntries) 즉시 완료하지 않고 과반수(Quorum)의 ACK를 기다린 후 Commit(2-Phase)하는 물리적 방어 기제를 설계할 수 있는가?
• 악의적인 해커가 시스템 내부에 침투해 데이터를 거짓으로 조작하여 응답하는 비잔틴 장군 문제(Byzantine Generals Problem)를, 사내망(Raft)과 퍼블릭 블록체인망(PBFT/PoW)이 각각 어떻게 다르게 타협하는지 저울질할 수 있는가?