Distributed Systems Principles & Consensus

1. Overview

분산 시스템 원리 및 합의(Distributed Systems Principles & Consensus, DPC)는 단일 컴퓨터(Node)의 연산과 저장 한계를 극복하기 위해, 네트워크로 연결된 수많은 컴퓨터를 모아 마치 하나의 거대한 슈퍼컴퓨터처럼 동작하게 만드는 흑마법(분산 원리)을 다룹니다.

분산 시스템의 세계에 들어서는 순간, 우리는 빛의 속도로 인한 지연(Latency), 랜선이 끊어지는 네트워크 단절(Partition), 그리고 언제든 서버가 돌연사할 수 있는 실패(Failure)를 상수로 받아들여야 합니다. 학습자는 분산 환경의 절대 법칙인 CAP 정리의 잔혹한 트레이드오프를 수용하고, 물리적 시간이 다르게 흐르는 노드들 사이에서 인과율을 맞추는 램포트 시계(Lamport Clocks)를 배웁니다. 나아가 서로를 완전히 신뢰할 수 없는 환경 속에서도 다수결을 통해 시스템의 상태를 일치시키는 팍소스(Paxos)와 래프트(Raft) 같은 분산 합의 알고리즘의 심연을 정복합니다.

2. Scope & Boundaries

In-Scope

• 분산 시스템의 한계 물리 (Distributed Fallacies): 부분 장애(Partial Failure), 비동기 네트워크 모델, 분산 컴퓨팅의 8가지 오류.
• 일관성과 가용성 모델 (Consistency Models): CAP 정리와 PACELC, 강한 일관성(Linearizability), 최종 일관성(Eventual Consistency).
• 논리 시계와 동기화 (Time & Ordering): NTP 물리 시계의 오차, 램포트 논리 시계(Lamport Logical Clocks), 벡터 시계(Vector Clocks).
• 분산 합의 알고리즘 (Consensus Protocols): 상태 기계 복제(State Machine Replication), 래프트(Raft) 리더 선출, 비잔틴 장애 허용(BFT).

Out-of-Scope

• 특정 분산 데이터베이스의 설치 및 튜닝: Cassandra, MongoDB 등 특정 솔루션의 클러스터 셋업 및 NoSQL 모델링 $\rightarrow$ 06-02. NoSQL & Polyglot 영역으로 위임.
• 분산 트랜잭션의 락(Lock) 메커니즘: 데이터베이스 관점의 2PC(Two-Phase Commit)나 분산 락 구현체 $\rightarrow$ 06-03. Distributed Logic 영역으로 위임.

Boundaries

• DPC vs. Distributed Logic (06-03): 06-03(DL)이 '데이터베이스(스토리지)가 분산되었을 때 데이터를 어떻게 안전하게 복제할 것인가'라는 저장 인프라 쪽에 무게를 둔다면, DPC는 **'상태가 없는(Stateless) 프로세스들조차 네트워크로 떨어져 있을 때 어떻게 순서를 맞추고 리더를 뽑을 것인가'**라는 컴퓨터 과학의 순수 분산 알고리즘 원론에 집중합니다.

3. Counterexample

• 순진한 네트워크 신뢰와 타임아웃 무시 (Network Fallacy): 단일 서버에서 개발하던 버릇 그대로, A 서버가 B 서버로 HTTP API를 호출할 때 타임아웃(Timeout)을 무한대로 걸어두거나, 응답이 없으면 성공했다고 가정해 버리는 행위. 분산 환경에서는 B 서버가 죽었는지, 아니면 가는 도중 랜선이 끊겼는지, 응답이 오는 길에 소실되었는지(Three-way Uncertainty) 알 수 없습니다. 이를 방어하기 위한 **멱등성(Idempotency)**이나 재시도(Retry), 서킷 브레이커 로직을 박아넣지 않은 시스템은 첫 네트워크 지연(Spike)에 전체가 마비(Cascading Failure)됩니다.
• CAP 정리의 맹목적 부정 (Consistency Fallacy): 기획자가 "어떤 장애 상황에서도 서비스는 멈추면 안 되고(A), 사용자가 방금 쓴 글은 무조건 0.1초 내에 다른 사람에게 다 보여야 해요(C)"라고 요구할 때 "알겠습니다"라고 답하는 개발자. 네트워크 단절(P)은 우리가 통제할 수 없는 물리적 현상이므로, 단절이 발생했을 때 시스템은 멈추거나(CP) 과거 데이터를 보여주거나(AP) 둘 중 하나를 수학적으로 반드시 선택해야 합니다. CAP 정리를 무시한 설계는 존재할 수 없는 유니콘을 쫓는 것과 같습니다.

4. Prerequisites

• 컴퓨터 네트워크 (Basic): 네트워크 패킷이 라우터를 거치며 왜 지연(Latency)되거나 유실되는지 물리적 감각이 있어야 분산 오류를 이해할 수 있습니다. (08-01. Network)
• 자료 구조와 알고리즘 (Recommended): 래프트(Raft) 합의를 이해하려면 유한 상태 기계(FSM)와 큐(Queue) 같은 기본적인 상태 전이 개념이 요구됩니다. (04-01. CDS)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 분산 컴퓨팅의 한계와 CAP 정리 (Distributed Challenges)

• Why to Learn: "네트워크는 항상 빠르고 안정적이다"라는 거짓말에서 깨어나, 부분 장애(Partial Failure)를 시스템 아키텍처의 기본 전제로 깔기 위함입니다.
• What to Learn:
  • Concepts: 분산 컴퓨팅의 8가지 오류(Fallacies), 부분 장애(Partial Failure), 비결정성(Non-determinism).
  • Skills: CAP 정리(Consistency, Availability, Partition Tolerance), PACELC 정리(지연시간과의 트레이드오프 연장).
  • Tools: 아키텍처 의사결정 매트릭스.
  • Trade-offs: 돈을 다루는 은행 시스템에서는 네트워크가 끊겼을 때 송금을 중지시켜 일관성(CP)을 지키는 것 vs SNS 피드에서는 과거의 글이 잠시 보이더라도 무조건 화면을 띄워 가용성(AP)을 택하는 비즈니스 도메인의 극단적 갈림길.
• How to Learn:
  • 1단계: 마이크로서비스 A가 B를 호출했는데 3초간 응답이 없는 상황을 가정하고, B가 죽었는지 / A $\rightarrow$ B 요청이 유실됐는지 / B $\rightarrow$ A 응답이 유실됐는지 알 수 없는 분산 환경의 '심연의 불확실성'을 증명합니다.
  • 2단계: 네트워크 단절(P)이 발생했을 때, 두 서버가 각자 쓰기 요청을 받게 내버려 두면 스플릿 브레인(Split-Brain)으로 데이터가 찢어짐(AP)을 인지하고, 이를 막기 위해 한쪽 서버의 응답을 강제로 거부(CP)하는 논리를 설계합니다.
• Implement: 클라이언트가 서버로 송금 요청을 보냈을 때 타임아웃이 발생하면, 백엔드가 이 요청을 이미 처리했는지 검증(Idempotency Key)하지 않고 재시도(Retry)할 때 돈이 두 번 빠져나가는 버그를 재현하는 모의 코드.

Recommended

Core Topic 02: 분산 시계와 이벤트 순서 역학 (Logical Clocks & Ordering)

• Why to Learn: 전 세계에 흩어진 서버들의 물리 시계(시계탑)가 미세하게 다르기 때문에, "내가 쓴 글에 달린 댓글이, 내 글보다 더 과거에 작성된 것으로 표시되는" 타임머신 버그를 막기 위해서입니다.
• What to Learn:
  • Concepts: 물리적 시계 동기화의 한계(NTP 오차, 윤초), 인과 관계(Causality, Happened-before).
  • Skills: 램포트 시계(Lamport Logical Clocks)의 단조 증가(Monotonically increasing) 물리, 벡터 시계(Vector Clocks)를 이용한 병렬 충돌(Conflict) 식별.
  • Tools: 분산 트레이싱 타임스탬프 시퀀스.
  • Trade-offs: NTP를 이용해 무식하게 물리적 타임스탬프(LWW: Last Write Wins)로 덮어씌워버리는 단순함(하지만 오차로 인해 나중에 쓴 데이터가 날아갈 수 있음) vs 벡터 시계 배열을 들고 다니며 시스템이 스스로 충돌을 감지해 애플리케이션에 병합(Merge)을 위임하는 완벽함(하지만 구현이 극도로 복잡함).
• How to Learn:
  • 1단계: 한국 서버(시간 12:00<05>)에서 "사과"라고 쓰고, 미국 서버(시간 12:00<03>)에서 1초 뒤 "바나나"로 수정했는데, 미국 서버 시계가 느려서 "사과"가 최종 데이터로 덮어씌워지는 시간 역전의 공포를 계산합니다.
  • 2단계: 시간(Time) 대신 카운터(Counter)를 도입합니다. 각 노드가 이벤트를 겪을 때마다 카운터를 1씩 증가시키고, 메시지를 받을 때는 내 카운터와 상대방 카운터 중 큰 값에 +1을 하는 '램포트 시계' 알고리즘으로 인과율을 강제로 교정하는 다이어그램을 그립니다.
• Implement: 3개의 독립된 파이썬 프로세스가 서로 무작위로 메시지를 주고받을 때, 각 메시지에 램포트 시계 값을 태워 보내고 최종적으로 수신된 메시지들을 카운터 순서대로 정렬하여 인과율을 복원하는 시뮬레이터.

Practical

Core Topic 03: 상태 기계 복제와 Raft 합의 (State Machine & Raft)

• Why to Learn: 리더 노드가 폭파되어도, 남은 노드들이 순식간에 눈빛을 교환하고 새로운 리더를 추대하여 시스템이 1초도 안 쉬고 굴러가게 만드는 현대 분산 시스템(Kubernetes ETCD, Kafka)의 심장 엔진을 직접 뜯어보기 위함입니다.
• What to Learn:
  • Concepts: 상태 기계 복제(State Machine Replication), 팍소스(Paxos)의 난해함과 래프트(Raft)의 직관성.
  • Skills: Raft의 3가지 상태(Leader, Follower, Candidate), 텀(Term) 에포크 제어, 무작위 타임아웃(Randomized Timeout) 기반 리더 선출, 과반수(Majority Quorum) 득표 물리.
  • Tools: Raft 비주얼라이저(Visualizer), Jepsen 테스트 툴.
  • Trade-offs: 2대의 서버로 구성할 때 1대만 죽어도 과반수(2대 중 2대)를 채우지 못해 전체 시스템이 멈추는 분산의 역설 vs 반드시 홀수(3대, 5대)로 구성해 1~2대가 죽어도 과반수 찬성으로 커밋을 이뤄내는 쿼럼(Quorum)의 인프라 비용.
• How to Learn:
  • 1단계: 5대의 노드로 이루어진 클러스터에서 리더 노드의 랜선을 뽑아버립니다. 팔로워 노드들이 리더의 하트비트(Ping)를 받지 못하자 각자 후보자(Candidate)로 돌변하고, 랜덤한 타이머가 먼저 끝난 노드가 선거를 열어 과반수 표를 획득해 새 리더로 왕위에 오르는 대관식을 추적합니다.
  • 2단계: 원래 리더가 네트워크 복구 후 돌아와 "나 아직 리더다!"라고 명령할 때, 새 리더가 발급한 '새로운 임기 번호(Term 2)'를 확인하고는 깨갱하며 일반 팔로워로 강등(Step-down)되는 시스템 자가 치유(Self-healing) 물리를 분석합니다.
• Implement: 3개의 스레드를 띄우고 서로 하트비트 스레드 통신을 하다가 리더 스레드를 kill 하면 남은 2개의 스레드가 랜덤 타이머를 기반으로 새 리더를 선출하여 로그에 "I am the new leader"를 찍는 모형.

Advanced

Core Topic 04: 비잔틴 장애 허용과 고신뢰 합의 (Byzantine Fault Tolerance)

• Why to Learn: 우주 방사선으로 메모리 값이 바뀌거나, 해커가 노드를 털어 거짓 메시지(사보타주)를 뿌리는 최악의 적대적 환경에서도 시스템 전체가 오염되지 않는 극단적 방어 아키텍처를 설계하기 위해서입니다.
• What to Learn:
  • Concepts: 크래시 장애(Crash-fault, 그냥 죽는 것) vs 비잔틴 장애(Byzantine-fault, 헛소리를 하거나 악의적으로 행동하는 것), 비잔틴 장군 문제(Byzantine Generals Problem).
  • Skills: PBFT (Practical Byzantine Fault Tolerance) 메커니즘, 장부를 위조할 수 없는 암호학적 서명과 블록체인(PoW/PoS) 합의 모델의 기초.
  • Tools: 블록체인 노드 시뮬레이터.
  • Trade-offs: 배신자가 없는 일반 분산 시스템(Raft)은 과반수만 동의하면 즉각 처리되는 가벼움 vs 1명의 배신자를 막기 위해 시스템에 최소 3f+1대의 서버가 필요하고, 모든 서버가 모든 서버와 교차 검증 통신을 해야 하는 BFT의 극단적 네트워크 오버헤드 $\mathcal{O}(N^2)$.
• How to Learn:
  • 1단계: 공격할지 말지 합의하려는 3명의 장군 중 1명이 배신자일 때, 배신자가 A에게는 "공격하자", B에게는 "후퇴하자"라고 거짓말을 보내면 A와 B는 결코 과반수 진실을 도출할 수 없는 수학적 절망(f개의 비잔틴 노드를 이기려면 3f+1 노드가 필요함)을 증명합니다.
  • 2단계: 프라이빗 블록체인이나 우주 항공 시스템에서, 메시지를 보낼 때마다 비대칭 키(RSA)로 서명하여 중간에 배신자가 메시지를 조작할 수 없도록 강제하는 PBFT의 Prepare-Commit-Reply 통신 역학을 도식화합니다.
• Implement: 4개의 노드 중 1개를 악의적 노드(Byzantine Node, 수신자마다 다른 무작위 값을 보냄)로 설정하고, 정상 노드 3개가 서로 교차 검증을 통해 악의적 노드의 거짓말을 무시하고 과반수 참값을 도출해 내는 방어 모듈.

7. Terminology

8. References

Primary References

• [P1] CS2023 - AL/Distributed Algorithms — Theoretical consensus basis.
• [P1] CS2023 - AR/Distributed Systems — System architecture constraints.

Secondary References

• [Distributed Systems: An Algorithmic Approach] Sukumar Ghosh — Formal approach.
• [Reliable Distributed Systems] Kenneth Birman — Focus on high availability.

Industry References

• [Consensus: Bridging Theory and Practice] Diego Ongaro (Raft creator) — Practical implementation guide.
• [Etcd Documentation - Why Raft?] — Real-world usage of consensus for configuration.

9. Final Checklist

Primary Checklist

• 네트워크 단절(Network Partition) 발생 시 가용성을 위해 일관성을 포기한다는 것이 실제 데이터 조회 시 어떤 의미인지 사례를 들어 설명 가능한가? (P1)
• Paxos와 Raft 알고리즘에서 왜 과반수(Quorum) 찬성이 필요한지 물리적 논리를 기술할 수 있는가? (P1)

Secondary Checklist

• 램포트 시계가 이벤트의 '전체 순서(Total order)'가 아닌 '부분 순서(Partial order)'만을 보장하는 이유를 인지하고 있는가?
• 분산 시스템에서 '멱등성(Idempotency)'이 중복 메시지 전송 문제를 어떻게 물리적으로 해결하는지 이해하는가?

Industry Checklist

• Kubernetes의 컨트롤 플레인이나 DB 클러스터에서 리더 선출 실패 시 서비스에 미치는 물리적 영향도를 시뮬레이션 가능한가? (SFIA)
• 전역적으로 분산된 시스템에서 물리적 시계 동기화(NTP 등) 오차 범위를 고려한 타임아웃 설정을 할 수 있는가?