Consensus Algorithms & Distributed Log

1. Overview

분산 합의 알고리즘 및 로그 역학(Consensus Algorithms & Distributed Log, CAD)은 네트워크 지연과 노드 장애가 빈번한 환경에서도 "어떤 값이 최종 진실인가"에 대해 모든 장치가 하나의 목소리를 내게 만드는 분산 시스템의 신뢰 공학입니다.

학습자는 분산 합의의 근간인 Paxos 알고리즘의 복잡한 수리 구조와, 이를 이해하기 쉽게 재해석한 Raft 알고리즘의 리더 선출 물리를 배웁니다. 특히, 결정론적 연산 결과(State)를 순차적으로 기록하여 모든 노드에 똑같이 복제하는 **상태 머신 복제(State Machine Replication, SMR)**와 **공유 로그(Shared Log)**의 물리 저장 기작을 익칩니다. 이를 통해 서비스 장애 시에도 데이터 유실이나 중복 없이 정합성을 유지하는 하이엔드 코디네이션(Coordination) 인프라 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Consensus Foundations: 불확실성 속에서의 단일 값 합의 수리 모델
• Paxos Family: Basic Paxos, Multi-Paxos의 제안(Propose)과 수락(Accept) 물리 흐름
• Raft Mechanics: Leader Election, Log Replication, Safety 규약의 하드웨어 정착
• Replicated Log Physiology: 로그의 순차적 추가(Append-only)와 인덱싱 물리학
• Quorum Physics: 다수결 법칙을 이용한 시스템 가용성 유지 수리 모델

Out-of-Scope

• 비잔틴 장애(악의적 공격)를 다루는 블록체인 합위 (10-04-XX 영역으로 위임)
• 단순한 데이터베이스 비동기 복제 상세 (06-03-04 영역에서 분담)

Boundaries

• CAD vs. Consistency Dynamics: 일관성 역학(07-02-01)이 '어떤 수준의 정합성을 가질지 정책'에 집중한다면, CAD는 '그 정합성을 실제로 하드웨어적으로 어떻게 달성할지 알고리즘'에 집중하여 구분합니다.

3. Counterexample

• 단순히 "Raft 라이브러리 쓰는 법"이라 설명하는 것은 CAD 학습이 아닙니다. 왜 네트워크 파티션(Split-brain) 발생 시 리더가 두 명이 되지 않도록 '쿼럼(Quorum)'이 물리적으로 강제되어야 하는지 수리 증명할 수 있어야 하며, 로그 압축(Log Compaction/Snapshot) 작업이 왜 분산 시스템의 저장 공간 한계를 극복하는 유일한 물리적 해방구인지 논증하지 못한다면 CAD의 실전적 난제를 이해하지 못한 것입니다.

4. Prerequisites

• Network Layers & Protocols (Basic): UDP/TCP 패킷 유실 이해가 필수입니다. (08-01-02 기반 역량)
• Theorems & Consistency Dynamics (Recommended): CAP 정리와 일관성 모델 이해가 권장됩니다. (07-02-01 TCD)

5. Learning Map

1. The Trust Crisis: 믿을 수 없는 네트워크 위에서 '하나의 진실'을 정하기 위한 수리적 규약을 설계합니다.
2. Leader Selection: 혼란을 수습하고 명령을 내릴 하드웨어 리더를 물리적으로 선출합니다.
3. The Holy Log: 리더의 명령을 모든 노드의 로컬 저장소에 일관되게 기록(Replication)합니다.
4. Infinite History: 쌓여가는 로그를 압축하고, 죽었던 노드가 깨어났을 때 가장 빨리 물리적으로 동기화되는 공학을 완성합니다.

6. Learning Topics

Basic

Core: 합의의 개념과 쿼럼 물리학 (Consensus Basics)

• Why to Learn: 전체 노드 중 과반수가 살아있다면 시스템을 계속 가동할 수 있는 물리적 근거를 얻기 위해서입니다.
• What to Learn:
  • Definition of Consensus: Agreement, Validity, Termination 조건
  • Quorum Logic: $N/2 + 1$ 법칙이 보장하는 물리적 교집합의 성질
  • Minority Failure: 장애 허용(Fault Tolerance) 범위 산출 ($f$대의 장애를 견디기 위해 $2f+1$대의 노드 필요)
• How to Learn:
  • 3대, 5대, 7대의 노드가 있을 때 각각 몇 대까지 죽어도 서비스가 가능한지 수리 계산 실습
  • 쿼럼 없이 각자 판단했을 때 발생하는 데이터 불일치 시나리오 재현
• Implement: $N$개의 노드 중 과반수 이상의 찬성(Vote)을 얻어야 성공하는 기초 QuorumSelector

Recommended

Core: Raft 알고리즘의 리더십 (Raft Leadership)

• Why to Learn: 분산 환경에서 명령의 선후 관계를 정리해 줄 '지휘관'을 안전하게 세우기 위함입니다.
• What to Learn:
  • Election Timeout: 리더 부재를 감지하는 물리적 시간 변수($Randomized$)
  • Term Index: 시간의 흐름을 논리적 번호로 매기는 수리 장치
  • Log Matching Property: 리더와 추종자의 로그가 일치함을 증명하는 물리 기작
• How to Learn:
  • Raft 시각화 도구를 이용해 리더가 죽었을 때 새로운 리더가 선출되는 물리적 전이 과정 분석 실습
  • '네트워크 구멍(Hole)'이 생겼을 때 이전 리더의 명령이 왜 거부되는지 수리 분석
• Implement: 무작위 타이머를 통해 먼저 타임아웃된 노드가 표를 요청하는 리더 선출 프로토타입

Practical

Core: 복제 로그와 상태 기계 (Log Replication)

• Why to Learn: 모든 노드의 하드웨어 상태를 동일하게 만들어 하나의 거대 가상 서버처럼 작동시키기 위해서입니다.
• What to Learn:
  • Append-only Log: 수정 불가능한 순차 쓰기 하드웨어 워크로드
  • Commit Index: 모든 노드에 성공적으로 구워진(Persisted) 로그의 물리 지점
  • Log Inconsistency resolution: 충돌하는 로그를 리더의 것으로 덮어쓰는 동기화 물리학
• How to Learn:
  • 데이터 변경 명령이 로그를 타고 전파되어 각 노드의 로컬 DB에 반영되는 전 과정을 수치로 측정하는 실습
  • 지연이 심한 노드가 전체 시스템의 '커밋 속도'를 어떻게 물리적으로 늦추는지 관찰
• Implement: 로그들을 안전하게 저장하고 특정 인덱스까지 확정(Commit)하는 ReplicatedLog 시스템

Advanced

Core: 로그 압축과 장애 복구 (Log Compaction)

• Why to Learn: 수조 개의 로그가 하드웨어 디스크를 가득 채우기 전에 물리적 상태를 요약하기 위해서입니다.
• What to Learn:
  • Snapshotting: 현재 메모리 상태를 통째로 덤프하고 이전 로그를 지우는 물리 기법
  • InstallSnapshot: 너무 뒤처진 노드에게 로그 대신 스냅샷 통째로 전송하는 하이브리드 복구
  • Log Pruning: 수리적 안정성이 확보된 구간의 로그 제거 정책
• How to Learn:
  • 스냅샷 생성 시 발생하는 CPU/Disk 부하가 합의 알고리즘 지연 시간에 미치는 영향 산출 실습
  • 죽어있던 노드가 복귀했을 때 'Snapshot + Log' 결합 방식으로 최신 상태를 찾는 복구 시간 예측
• Implement: 정해진 크기마다 로그를 스냅샷으로 변환하고 오래된 로그 파일을 삭제하는 Snapshotter

7. Terminology

8. References

Primary

• [P1] CS2023 - SF/Systems Fundamentals (Systems Coordination and Consensus) — Core requirements.
• [P1] CS2023 - PD/Parallel and Distributed Computing (Distributed algorithms) — Detailed context.

Secondary

• [In Search of an Understandable Consensus Algorithm (Raft Paper)] Diego Ongaro et al. — The definitive Raft reference.
• [Paxos Made Simple] Leslie Lamport — The fundamental Paxos explanation.

Industry

• [HashiCorp Consul: Raft Protocol Internals] — Real-world coordination case.
• [Etcd: Distributed key-value store based on Raft] — Industry standard implementation.

9. Final Checklist

Primary

• '합의 알고리즘'이 왜 '네트워크 지연'과 '노드 장애' 상황에서도 시스템의 안정성(Safety)을 물리적으로 보장하는지 설명 가능한가? (P1)
• '쿼럼'의 크기가 전체 노드 수($N$)에 따라 결정될 때, 시스템이 견딜 수 있는 물리적 손실 노드 수를 수리 산출할 수 있는 가? (P1)

Secondary

• 'Raft' 알고리즘에서 '임기(Term)' 개념이 왜 물리적 리더 중복(Split-brain)을 방지하는 수리적 장치가 되는지 소통 가능한가?
• **상태 머신 복제(SMR)**가 비결정론적 작업(예: 현재 시간 기록)을 처리할 때 왜 물리적 일관성이 깨질 위험이 있는지 논증 가능한가?

Industry

• 분산 DB 운영 시, '로그 복제' 작업의 동기(Synchronous) 옵션과 성능($Throughput$) 사이의 물리적 트레이드-오프를 제안할 수 있는 가? (SFIA)
• 'Etcd'나 'Consul' 같은 코디네이션 도구에서 리더 선출 주기가 하드웨어 네트워크 지터(Jitter)에 반응하는 방식을 물리적으로 설명할 수 있는 가?