분산 시스템 기초 완전 가이드 2025: 합의 알고리즘, 복제, 일관성 모델, 장애 허용

분산 시스템의 핵심 도전 과제
┌─────────────────────────────────────────────┐
│                                             │
│  네트워크는 신뢰할 수 없다                    │
│  ├── 패킷 손실                              │
│  ├── 지연 변동                              │
│  └── 네트워크 파티션                         │
│                                             │
│  노드는 실패할 수 있다                       │
│  ├── 크래시                                 │
│  ├── 슬로우다운                             │
│  └── 비잔틴 장애 (악의적 동작)               │
│                                             │
│  글로벌 시간이 존재하지 않는다                │
│  ├── 클럭 드리프트                           │
│  ├── NTP 오차                               │
│  └── 이벤트 순서 결정의 어려움               │
│                                             │
└─────────────────────────────────────────────┘

CAP 정리
┌─────────────────────────────────────────────┐
│                                             │
│            Consistency (C)                  │
│               /\                            │
│              /  \                           │
│             /    \                          │
│            / CP   \  CA                     │
│           /  시스템 \ 시스템                  │
│          /          \                       │
│         /____________\                      │
│  Availability (A) ─── Partition             │
│                       Tolerance (P)         │
│                                             │
│  CP: HBase, MongoDB, etcd, ZooKeeper       │
│  AP: Cassandra, DynamoDB, CouchDB          │
│  CA: 단일 노드 RDBMS (이론적)               │
│                                             │
│  네트워크 파티션 시 C 또는 A 중 선택 필수    │
└─────────────────────────────────────────────┘

PACELC 정리
if (Partition) then
    Availability vs Consistency
else
    Latency vs Consistency

┌─────────────────────────────────────────────┐
│ 시스템         │ P 발생 시 │ 정상 시 (E)    │
│───────────────│──────────│───────────────│
│ DynamoDB      │ PA       │ EL (낮은 지연) │
│ Cassandra     │ PA       │ EL             │
│ MongoDB       │ PC       │ EC (강한 일관성)│
│ Google Spanner│ PC       │ EC             │
│ CockroachDB   │ PC       │ EL (읽기 최적화)│
│ PNUTS (Yahoo) │ PC       │ EL             │
└─────────────────────────────────────────────┘

강한 일관성 ◄─────────────────────────────► 약한 일관성
(Strong)                                    (Weak)

선형화 가능성  순차적    인과적    최종적
(Linearizable) (Sequential) (Causal) (Eventual)

│ 성능 낮음    │          │         │ 성능 높음  │
│ 구현 복잡    │          │         │ 구현 단순  │
│ 높은 보장    │          │         │ 낮은 보장  │

선형화 가능성 (Linearizable)
Client A: ──write(x=1)──────────────────────
Client B: ────────────read(x)→1─────────────
Client C: ──────────────────read(x)→1───────

모든 클라이언트가 쓰기 완료 후 항상 최신 값을 읽음

비선형화 (Not Linearizable)
Client A: ──write(x=1)──────────────────────
Client B: ────────────read(x)→1─────────────
Client C: ──────────────────read(x)→0───────  ← 오래된 값!

# Eventual Consistency를 가정한 읽기 패턴
class EventuallyConsistentStore:
    def __init__(self, replicas: list):
        self.replicas = replicas

    def write(self, key: str, value: str, timestamp: float):
        """모든 복제본에 비동기 쓰기"""
        for replica in self.replicas:
            replica.async_put(key, value, timestamp)

    def read(self, key: str) -> str:
        """읽기 - 어떤 복제본에서든 읽을 수 있음"""
        # 최신 타임스탬프 값 선택 (read-repair)
        values = [r.get(key) for r in self.replicas]
        return max(values, key=lambda v: v.timestamp).value

    def read_your_writes(self, key: str, session_token: str) -> str:
        """자신의 쓰기를 읽을 수 있도록 보장"""
        # 세션 토큰으로 마지막 쓰기 위치 확인
        last_write_replica = self.get_replica_for_session(session_token)
        return last_write_replica.get(key).value

인과적 일관성 예시:
A: write(x=1)    ← B가 x=1을 읽은 후 y=2를 쓴 경우
B: read(x)→1, write(y=2)
C: read(y)→2, read(x)→?

인과적 일관성이 보장되면:
  C가 y=2를 볼 수 있다면, x=1도 반드시 볼 수 있어야 합니다.
  (y=2의 인과 원인인 x=1이 먼저 보여야 함)

Read-Your-Writes
Client A: write(x=1) ───→ read(x)→1  (항상 보장)
                           ↑
                    자신의 쓰기를 읽음

Session Consistency: 동일 세션 내에서 보장
Monotonic Reads: 한 번 새 값을 보면 이전 값으로 돌아가지 않음

Basic Paxos (단일 값 합의)
┌─────────────────────────────────────────────┐
│                                             │
│  Phase 1a: Prepare                          │
│  Proposer → Acceptor: prepare(n)            │
│  "제안 번호 n으로 준비해주세요"              │
│                                             │
│  Phase 1b: Promise                          │
│  Acceptor → Proposer: promise(n, prev_val)  │
│  "n 미만은 거부하겠습니다. 이전 수락값 전달" │
│                                             │
│  Phase 2a: Accept                           │
│  Proposer → Acceptor: accept(n, value)      │
│  "이 값을 수락해주세요"                      │
│                                             │
│  Phase 2b: Accepted                         │
│  Acceptor → Learner: accepted(n, value)     │
│  "과반수가 수락하면 합의 완료"               │
│                                             │
└─────────────────────────────────────────────┘

Raft 상태 전이
┌────────────────────────────────────────────────┐
│                                                │
│  ┌──────────┐  타임아웃   ┌──────────┐         │
│  │ Follower │──────────→│ Candidate│         │
│  │          │←──────────│          │         │
│  └──────────┘  실패/발견  └────┬─────┘         │
│       ↑                      │               │
│       │    과반수 투표 획득    │               │
│       │                      ↓               │
│       │              ┌──────────┐            │
│       └──────────────│  Leader  │            │
│         새 리더 발견   │          │            │
│                      └──────────┘            │
│                                                │
│  Term (임기):                                  │
│  ┌───┬───┬───┬───┬───┐                        │
│  │ 1 │ 2 │ 3 │ 4 │ 5 │ ...                   │
│  └───┴───┴───┴───┴───┘                        │
│  각 Term마다 최대 하나의 Leader                 │
└────────────────────────────────────────────────┘

Leader Election 과정
┌────────────────────────────────────────────────┐
│ 1. Follower가 heartbeat 타임아웃              │
│ 2. Term 증가, 자신에게 투표                    │
│ 3. RequestVote RPC를 다른 노드에 전송          │
│ 4. 과반수 투표를 받으면 Leader 됨              │
│                                                │
│ [Node A: Follower]  [Node B: Follower]         │
│ [Node C: Follower]  [Node D: Follower]         │
│ [Node E: Follower]                             │
│                                                │
│ Node A 타임아웃 → Candidate (Term 2)           │
│ A→B: RequestVote(Term 2) → B: Grant            │
│ A→C: RequestVote(Term 2) → C: Grant            │
│ A→D: RequestVote(Term 2) → D: Grant            │
│                                                │
│ A가 과반수(3/5) 획득 → Leader!                 │
│ A→all: AppendEntries(heartbeat)                │
└────────────────────────────────────────────────┘

Log Replication
┌────────────────────────────────────────────────┐
│                                                │
│  Client → Leader: write(x=5)                   │
│                                                │
│  Leader Log:  [1:x=3] [2:y=7] [3:x=5]         │
│  Follower A:  [1:x=3] [2:y=7]                 │
│  Follower B:  [1:x=3] [2:y=7]                 │
│  Follower C:  [1:x=3]                         │
│  Follower D:  [1:x=3] [2:y=7]                 │
│                                                │
│  1. Leader가 로그에 엔트리 추가                 │
│  2. AppendEntries RPC로 복제                   │
│  3. 과반수 복제 확인 시 커밋                    │
│  4. 클라이언트에 응답                          │
│  5. 다음 heartbeat에서 커밋 알림               │
│                                                │
│  안전성: Leader는 커밋된 모든 엔트리를 포함     │
│  (Election Restriction)                        │
└────────────────────────────────────────────────┘

from enum import Enum
from dataclasses import dataclass, field
from typing import Optional
import random
import time

class NodeState(Enum):
    FOLLOWER = "follower"
    CANDIDATE = "candidate"
    LEADER = "leader"

@dataclass
class LogEntry:
    term: int
    index: int
    command: str

@dataclass
class RaftNode:
    node_id: str
    state: NodeState = NodeState.FOLLOWER
    current_term: int = 0
    voted_for: Optional[str] = None
    log: list = field(default_factory=list)
    commit_index: int = 0
    last_applied: int = 0

    # Leader 전용
    next_index: dict = field(default_factory=dict)
    match_index: dict = field(default_factory=dict)

    def on_election_timeout(self):
        """선거 타임아웃: Candidate로 전환"""
        self.state = NodeState.CANDIDATE
        self.current_term += 1
        self.voted_for = self.node_id
        votes_received = 1  # 자신에게 투표

        # 모든 노드에 RequestVote 전송
        for peer in self.peers:
            response = self.send_request_vote(peer)
            if response and response.vote_granted:
                votes_received += 1

        if votes_received > len(self.peers) // 2:
            self.become_leader()

    def become_leader(self):
        """Leader로 전환"""
        self.state = NodeState.LEADER
        # next_index 초기화
        for peer in self.peers:
            self.next_index[peer] = len(self.log)
            self.match_index[peer] = 0
        self.send_heartbeats()

    def on_append_entries(self, term, leader_id, entries, leader_commit):
        """AppendEntries RPC 처리"""
        if term < self.current_term:
            return False

        self.state = NodeState.FOLLOWER
        self.current_term = term
        self.reset_election_timer()

        # 로그 일관성 확인 및 엔트리 추가
        self.log.extend(entries)

        if leader_commit > self.commit_index:
            self.commit_index = min(leader_commit, len(self.log) - 1)
            self.apply_committed_entries()

        return True

    def replicate_log(self, command: str):
        """클라이언트 명령 처리 (Leader만)"""
        if self.state != NodeState.LEADER:
            return False

        entry = LogEntry(
            term=self.current_term,
            index=len(self.log),
            command=command
        )
        self.log.append(entry)

        # 모든 Follower에 복제
        ack_count = 1  # 자신
        for peer in self.peers:
            success = self.send_append_entries(peer, [entry])
            if success:
                ack_count += 1

        # 과반수 확인
        if ack_count > len(self.peers) // 2:
            self.commit_index = entry.index
            self.apply_committed_entries()
            return True
        return False

리더-팔로워 복제
┌─────────────────────────────────────────────┐
│                                             │
│  Client ──write──→ ┌────────┐               │
│                    │ Leader │               │
│  Client ──read──→  │ (R/W)  │               │
│                    └───┬────┘               │
│                   복제  │  복제              │
│              ┌─────────┼─────────┐          │
│              ↓         ↓         ↓          │
│         ┌────────┐┌────────┐┌────────┐      │
│         │Follower││Follower││Follower│      │
│         │ (Read) ││ (Read) ││ (Read) │      │
│         └────────┘└────────┘└────────┘      │
│                                             │
│  동기 복제: 느리지만 데이터 손실 없음        │
│  비동기 복제: 빠르지만 데이터 손실 가능       │
│  반동기 복제: 하나 이상의 팔로워에 동기 복제  │
└─────────────────────────────────────────────┘

멀티리더 복제
┌─────────────────────────────────────────────┐
│                                             │
│  DC-US             DC-EU            DC-Asia │
│  ┌────────┐       ┌────────┐      ┌────────┐│
│  │Leader 1│◄─────►│Leader 2│◄────►│Leader 3││
│  │ (R/W)  │       │ (R/W)  │      │ (R/W)  ││
│  └───┬────┘       └───┬────┘      └───┬────┘│
│      │                │               │     │
│  ┌───┴───┐        ┌───┴───┐      ┌───┴───┐ │
│  │Follower│        │Follower│      │Follower│ │
│  └───────┘        └───────┘      └───────┘ │
│                                             │
│  장점: 쓰기 지연 감소, 오프라인 동작 가능    │
│  단점: 충돌 해결 필요 (LWW, CRDT 등)        │
└─────────────────────────────────────────────┘

# Last-Writer-Wins (LWW) - 가장 단순
def lww_resolve(conflict_a, conflict_b):
    """타임스탬프가 더 큰 값이 승리"""
    if conflict_a.timestamp > conflict_b.timestamp:
        return conflict_a
    return conflict_b

# Custom merge function
def custom_merge(conflict_a, conflict_b):
    """도메인 특화 머지 로직"""
    if conflict_a.type == "counter":
        return Value(conflict_a.value + conflict_b.value)
    elif conflict_a.type == "set":
        return Value(conflict_a.value.union(conflict_b.value))
    else:
        return lww_resolve(conflict_a, conflict_b)

무리더 복제 (Dynamo 스타일)
┌─────────────────────────────────────────────┐
│                                             │
│  N=3 (총 복제본), W=2 (쓰기 쿼럼),          │
│  R=2 (읽기 쿼럼)                             │
│                                             │
│  Write: Client → Node1 (ack)                │
│                → Node2 (ack)    ← W=2 충족  │
│                → Node3 (timeout)             │
│                                             │
│  Read:  Client → Node1 (v=5, ts=100)        │
│                → Node2 (v=5, ts=100)  ← 최신│
│                → Node3 (v=3, ts=90)   ← 오래│
│                                             │
│  읽기 복구: 오래된 Node3에 최신값 전송       │
│                                             │
│  쿼럼 조건: W + R > N → 최소 하나의          │
│  교집합이 존재하여 최신값 읽기 보장           │
│                                             │
│  Sloppy Quorum: 장애 시 다른 노드로 대체    │
│  (Hinted Handoff)                           │
└─────────────────────────────────────────────┘

체인 복제
┌─────────────────────────────────────────────┐
│                                             │
│  Write → [Head] → [Middle] → [Tail] → Read │
│                                             │
│  장점:                                      │
│  - 강한 일관성 보장                          │
│  - 읽기와 쓰기의 부하 분산                   │
│  - 구현이 비교적 단순                        │
│                                             │
│  단점:                                      │
│  - 쓰기 지연이 체인 길이에 비례               │
│  - Head나 Tail 장애 시 재구성 필요           │
│                                             │
│  사용 예: Azure Storage, HDFS               │
└─────────────────────────────────────────────┘

물리적 시계의 문제
┌─────────────────────────────────────────────┐
│                                             │
│  Node A 시계: 10:00:00.000                  │
│  Node B 시계: 10:00:00.150  (150ms 차이)    │
│  Node C 시계: 09:59:59.800  (200ms 차이)    │
│                                             │
│  NTP 동기화 정확도: 보통 수십ms              │
│  Google Spanner TrueTime: 약 7ms 오차       │
│                                             │
│  문제: 이벤트 A가 B보다 먼저 발생했는지      │
│  물리적 시계만으로는 판단 불가                │
└─────────────────────────────────────────────┘

Lamport Timestamp
규칙:
1. 이벤트 발생 시 로컬 카운터 증가
2. 메시지 전송 시 카운터 포함
3. 메시지 수신 시 max(local, received) + 1

Node A:  [1] ──msg──→ [2] ────→ [3]
                        ↓
Node B:  [1] ────→ [3] (max(1,2)+1) → [4]
                                        ↓
Node C:  [1] ──→ [2] ───────────→ [5] (max(2,4)+1)

한계: a와 b의 Lamport 시간만으로
      인과 관계를 구별할 수 없음
      (L(a) < L(b)라도 a가 b의 원인이 아닐 수 있음)

class LamportClock:
    def __init__(self):
        self.time = 0

    def tick(self) -> int:
        """로컬 이벤트 발생"""
        self.time += 1
        return self.time

    def send(self) -> int:
        """메시지 전송"""
        self.time += 1
        return self.time

    def receive(self, sender_time: int) -> int:
        """메시지 수신"""
        self.time = max(self.time, sender_time) + 1
        return self.time

벡터 클럭
각 노드가 모든 노드의 카운터를 벡터로 유지

Node A: [A:1, B:0, C:0]
        ──msg──→
Node B: [A:0, B:1, C:0] → 수신 후 [A:1, B:2, C:0]
        ──msg──→
Node C: [A:0, B:0, C:1] → 수신 후 [A:1, B:2, C:2]

인과 관계 판단:
V1 < V2  ⟺  모든 i에 대해 V1[i] <= V2[i] 이고
              적어도 하나의 j에 대해 V1[j] < V2[j]

V1 || V2  (동시 발생) ⟺  V1 < V2도 V2 < V1도 아님

class VectorClock:
    def __init__(self, node_id: str, nodes: list):
        self.node_id = node_id
        self.clock = {n: 0 for n in nodes}

    def tick(self):
        """로컬 이벤트"""
        self.clock[self.node_id] += 1

    def send(self) -> dict:
        """메시지 전송"""
        self.clock[self.node_id] += 1
        return self.clock.copy()

    def receive(self, sender_clock: dict):
        """메시지 수신"""
        for node in self.clock:
            self.clock[node] = max(self.clock[node], sender_clock.get(node, 0))
        self.clock[self.node_id] += 1

    def is_before(self, other_clock: dict) -> bool:
        """self가 other보다 먼저 발생했는지"""
        all_leq = all(self.clock[n] <= other_clock.get(n, 0) for n in self.clock)
        any_lt = any(self.clock[n] < other_clock.get(n, 0) for n in self.clock)
        return all_leq and any_lt

    def is_concurrent(self, other_clock: dict) -> bool:
        """동시 발생 여부"""
        return not self.is_before(other_clock) and not self._is_after(other_clock)

HLC (Hybrid Logical Clock)
= 물리적 시계 + 논리적 시계의 장점 결합

구성: (physical_time, logical_counter)

장점:
- 물리적 시간에 가까운 값 (사람이 이해 가능)
- 인과 관계 추적 가능
- NTP 오차를 보정

사용 예: CockroachDB, YugabyteDB

장애 모델 스펙트럼 (허용 난이도 순)
┌─────────────────────────────────────────────┐
│                                             │
│  Crash-Stop (가장 단순)                      │
│  ├── 노드가 멈추고 복구되지 않음             │
│  ├── 감지가 비교적 쉬움                      │
│  └── 대부분의 합의 알고리즘이 가정            │
│                                             │
│  Crash-Recovery                              │
│  ├── 노드가 멈추고 나중에 복구               │
│  ├── 영구 저장소에서 상태 복원               │
│  └── WAL(Write-Ahead Log) 필요              │
│                                             │
│  Omission                                    │
│  ├── 메시지를 보내거나 받지 못함             │
│  ├── 네트워크 파티션 포함                    │
│  └── 타임아웃으로 감지                       │
│                                             │
│  Byzantine (가장 복잡)                       │
│  ├── 노드가 임의의/악의적 동작              │
│  ├── 잘못된 데이터 전송 가능                 │
│  ├── 합의에 3f+1 노드 필요 (f: 장애 수)     │
│  └── 블록체인에서 주로 사용                   │
│                                             │
└─────────────────────────────────────────────┘

class PhiAccrualFailureDetector:
    """Phi Accrual 장애 감지기 (Akka에서 사용)"""

    def __init__(self, threshold: float = 8.0):
        self.threshold = threshold
        self.heartbeat_intervals = []
        self.last_heartbeat = None

    def heartbeat(self, timestamp: float):
        """하트비트 수신"""
        if self.last_heartbeat:
            interval = timestamp - self.last_heartbeat
            self.heartbeat_intervals.append(interval)
        self.last_heartbeat = timestamp

    def phi(self, current_time: float) -> float:
        """phi 값 계산 - 장애 의심 수준"""
        if not self.heartbeat_intervals:
            return 0.0

        time_since_last = current_time - self.last_heartbeat
        mean = sum(self.heartbeat_intervals) / len(self.heartbeat_intervals)
        variance = sum((x - mean) ** 2 for x in self.heartbeat_intervals) / len(self.heartbeat_intervals)
        std_dev = variance ** 0.5

        if std_dev == 0:
            return float('inf') if time_since_last > mean else 0.0

        # 정규 분포 기반 phi 계산
        y = (time_since_last - mean) / std_dev
        # phi = -log10(1 - CDF(y))
        return max(0.0, y * 1.5)  # 단순화된 근사

    def is_alive(self, current_time: float) -> bool:
        """노드가 살아있는지 판단"""
        return self.phi(current_time) < self.threshold

2PC (Two-Phase Commit)
┌────────────────────────────────────────────────┐
│                                                │
│  Phase 1: Prepare (투표)                       │
│  Coordinator → Participant A: prepare?         │
│  Coordinator → Participant B: prepare?         │
│  Coordinator → Participant C: prepare?         │
│                                                │
│  A → Coordinator: YES (준비 완료)              │
│  B → Coordinator: YES                          │
│  C → Coordinator: YES                          │
│                                                │
│  Phase 2: Commit (실행)                        │
│  Coordinator → A: commit                       │
│  Coordinator → B: commit                       │
│  Coordinator → C: commit                       │
│                                                │
│  문제점:                                       │
│  - 코디네이터 장애 시 참가자 블로킹            │
│  - 단일 장애점 (SPOF)                          │
│  - 동기적이라 성능 저하                        │
│                                                │
│  하나라도 NO → Abort                           │
│  코디네이터 장애 → 불확실 상태 (in-doubt)      │
└────────────────────────────────────────────────┘

3PC: 2PC의 블로킹 문제 해결 시도
Phase 1: CanCommit (투표)
Phase 2: PreCommit (사전 커밋)
Phase 3: DoCommit (최종 커밋)

추가된 PreCommit 단계로:
- 타임아웃 기반 복구 가능
- 하지만 네트워크 파티션에서는 여전히 문제

실무에서는 3PC보다 Saga 패턴을 더 많이 사용

Saga 패턴: 보상 트랜잭션 기반
┌────────────────────────────────────────────────┐
│                                                │
│  정상 흐름:                                    │
│  T1 → T2 → T3 → T4 → 완료                     │
│  (주문) (결제) (재고) (배송)                    │
│                                                │
│  T3 실패 시 보상:                              │
│  T1 → T2 → T3(실패) → C2 → C1                 │
│  (주문) (결제) (재고실패) (결제취소) (주문취소)  │
│                                                │
│  Choreography (이벤트 기반):                   │
│  각 서비스가 이벤트를 발행하고 구독              │
│                                                │
│  Orchestration (중앙 조정):                    │
│  Saga Orchestrator가 각 단계를 조정             │
│                                                │
└────────────────────────────────────────────────┘

# Saga Orchestrator 예시
from dataclasses import dataclass
from typing import Callable
from enum import Enum

class SagaStatus(Enum):
    PENDING = "pending"
    RUNNING = "running"
    COMPLETED = "completed"
    COMPENSATING = "compensating"
    FAILED = "failed"

@dataclass
class SagaStep:
    name: str
    action: Callable
    compensation: Callable

class SagaOrchestrator:
    def __init__(self, steps: list):
        self.steps = steps
        self.completed_steps = []
        self.status = SagaStatus.PENDING

    async def execute(self):
        """Saga 실행"""
        self.status = SagaStatus.RUNNING

        for step in self.steps:
            try:
                await step.action()
                self.completed_steps.append(step)
            except Exception as e:
                print(f"Step '{step.name}' failed: {e}")
                await self.compensate()
                return False

        self.status = SagaStatus.COMPLETED
        return True

    async def compensate(self):
        """보상 트랜잭션 실행 (역순)"""
        self.status = SagaStatus.COMPENSATING

        for step in reversed(self.completed_steps):
            try:
                await step.compensation()
                print(f"Compensated: {step.name}")
            except Exception as e:
                print(f"Compensation failed for '{step.name}': {e}")
                self.status = SagaStatus.FAILED
                return

        self.status = SagaStatus.FAILED

# 사용 예
saga = SagaOrchestrator([
    SagaStep("create_order", create_order, cancel_order),
    SagaStep("process_payment", charge_payment, refund_payment),
    SagaStep("reserve_inventory", reserve_stock, release_stock),
    SagaStep("arrange_shipping", book_delivery, cancel_delivery),
])

범위 파티셔닝 (Range Partitioning)
┌─────────────────────────────────────────────┐
│ Key: A-F → Shard 1                          │
│ Key: G-N → Shard 2                          │
│ Key: O-Z → Shard 3                          │
│                                             │
│ 장점: 범위 쿼리 효율적                       │
│ 단점: 핫스팟 발생 가능 (특정 범위에 쏠림)    │
└─────────────────────────────────────────────┘

해시 파티셔닝 (Hash Partitioning)
┌─────────────────────────────────────────────┐
│ hash(key) % 3 == 0 → Shard 1               │
│ hash(key) % 3 == 1 → Shard 2               │
│ hash(key) % 3 == 2 → Shard 3               │
│                                             │
│ 장점: 균등 분배                              │
│ 단점: 범위 쿼리 불가, 리샤딩 비용 높음       │
└─────────────────────────────────────────────┘

일관성 해싱
┌─────────────────────────────────────────────┐
│                                             │
│           Node A (0)                        │
│          ╱        ╲                         │
│        ╱            ╲                       │
│   Node D              Node B                │
│   (270)                (90)                 │
│        ╲            ╱                       │
│          ╲        ╱                         │
│           Node C (180)                      │
│                                             │
│  key의 해시 → 링 위의 위치                   │
│  시계 방향으로 가장 가까운 노드에 할당        │
│                                             │
│  노드 추가/제거 시:                          │
│  - 전체 리밸런싱이 아닌 인접 노드만 영향     │
│  - 평균 K/N 키만 이동 (K: 총 키, N: 노드)   │
│                                             │
│  가상 노드 (Virtual Node):                   │
│  - 각 물리 노드가 링 위에 여러 위치 차지     │
│  - 부하 균등 분배                            │
│                                             │
└─────────────────────────────────────────────┘

import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    def __init__(self, virtual_nodes: int = 150):
        self.virtual_nodes = virtual_nodes
        self.ring = {}         # hash -> node
        self.sorted_keys = []  # sorted hash values
        self.nodes = set()

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str):
        """노드 추가"""
        self.nodes.add(node)
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:vn{i}"
            h = self._hash(virtual_key)
            self.ring[h] = node
            self.sorted_keys.append(h)
        self.sorted_keys.sort()

    def remove_node(self, node: str):
        """노드 제거"""
        self.nodes.discard(node)
        for i in range(self.virtual_nodes):
            virtual_key = f"{node}:vn{i}"
            h = self._hash(virtual_key)
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        """키에 대한 노드 조회"""
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h)
        if idx >= len(self.sorted_keys):
            idx = 0
        return self.ring[self.sorted_keys[idx]]

# 사용
ring = ConsistentHashRing(virtual_nodes=150)
ring.add_node("node-1")
ring.add_node("node-2")
ring.add_node("node-3")

print(ring.get_node("user:123"))  # → node-2
print(ring.get_node("order:456"))  # → node-1

Gossip (Epidemic) 프로토콜
┌─────────────────────────────────────────────┐
│                                             │
│  주기적으로 랜덤 노드에 상태 정보 전파       │
│                                             │
│  Round 1: A → B (A의 정보)                  │
│  Round 2: A → C, B → D (A,B의 정보)        │
│  Round 3: C → E, D → F (확산 계속)          │
│  ...                                        │
│  O(log N) 라운드 후 전체 전파                │
│                                             │
│  Push: 자신의 정보를 보냄                    │
│  Pull: 상대의 정보를 요청                    │
│  Push-Pull: 양방향 교환 (가장 효율적)        │
│                                             │
│  사용 예:                                    │
│  - 멤버십 관리 (노드 추가/제거 감지)         │
│  - 장애 감지                                │
│  - 분산 집계 (카운터, 평균 등)               │
│  - Amazon DynamoDB, Apache Cassandra        │
│                                             │
└─────────────────────────────────────────────┘

SWIM (Scalable Weakly-consistent Infection-style Membership)
┌────────────────────────────────────────────────┐
│                                                │
│  1. Ping: 랜덤 노드에 직접 핑                  │
│     A ──ping──→ B                              │
│                                                │
│  2. Ack: 응답                                  │
│     A ←──ack── B                               │
│                                                │
│  3. 무응답 시: 간접 핑 (Ping-Req)              │
│     A ──ping-req──→ C ──ping──→ B              │
│     A ←──ack────── C ←──ack── B               │
│                                                │
│  4. 여전히 무응답: B를 의심(Suspect)            │
│  5. 일정 시간 후: B를 죽은 것으로 판단          │
│                                                │
│  사용: HashiCorp Serf, Consul                  │
└────────────────────────────────────────────────┘

Google Spanner 핵심 기술
┌─────────────────────────────────────────────┐
│                                             │
│  TrueTime API                               │
│  ├── GPS + 원자 시계 기반                    │
│  ├── 시간 불확실성 구간 반환: [earliest, latest]│
│  ├── 오차: 약 7ms 이내                       │
│  └── 외부 일관성 (External Consistency) 보장  │
│                                             │
│  Paxos 기반 복제                             │
│  ├── 각 스패너 서버 그룹이 Paxos 실행         │
│  ├── 동기 복제로 강한 일관성                  │
│  └── 전 세계 분산 가능                       │
│                                             │
│  읽기-쓰기 트랜잭션                           │
│  ├── 2PL (Two-Phase Locking) + 2PC           │
│  ├── TrueTime으로 커밋 타임스탬프 할당        │
│  └── 읽기 전용 트랜잭션: 잠금 없이 스냅샷 읽기│
│                                             │
└─────────────────────────────────────────────┘

DynamoDB 핵심 설계
┌─────────────────────────────────────────────┐
│                                             │
│  일관성 해싱 + 가상 노드                     │
│  ├── 파티션 키 기반 데이터 분배              │
│  └── 자동 리밸런싱                           │
│                                             │
│  Sloppy Quorum + Hinted Handoff             │
│  ├── N=3, W=2, R=2                          │
│  ├── 장애 시 다른 노드가 대신 저장           │
│  └── 복구 후 원래 노드로 전달                │
│                                             │
│  Vector Clock으로 충돌 감지                   │
│  ├── 인과 관계 추적                          │
│  └── 동시 쓰기 감지 시 클라이언트가 해결      │
│                                             │
│  Anti-Entropy (Merkle Tree)                  │
│  ├── 복제본 간 불일치 탐지                   │
│  └── 효율적인 동기화                         │
│                                             │
│  Gossip 기반 멤버십                           │
│  └── 노드 추가/제거 감지                     │
│                                             │
└─────────────────────────────────────────────┘

Kafka 복제 모델
┌─────────────────────────────────────────────┐
│                                             │
│  Topic: orders (Partition 3, RF=3)          │
│                                             │
│  Partition 0:                               │
│    Leader: Broker 1                         │
│    ISR: [Broker 1, Broker 2, Broker 3]     │
│                                             │
│  Partition 1:                               │
│    Leader: Broker 2                         │
│    ISR: [Broker 2, Broker 3, Broker 1]     │
│                                             │
│  Partition 2:                               │
│    Leader: Broker 3                         │
│    ISR: [Broker 3, Broker 1, Broker 2]     │
│                                             │
│  ISR (In-Sync Replicas):                    │
│  ├── Leader의 로그를 따라잡은 복제본         │
│  ├── 뒤처지면 ISR에서 제거                   │
│  └── acks=all → ISR 전체가 복제 확인         │
│                                             │
│  Controller:                                │
│  ├── ZooKeeper/KRaft로 선출                  │
│  ├── 파티션 리더 할당                        │
│  └── 브로커 장애 시 리더 재선출              │
│                                             │
└─────────────────────────────────────────────┘

import time
from enum import Enum
from threading import Lock

class CircuitState(Enum):
    CLOSED = "closed"       # 정상
    OPEN = "open"           # 차단
    HALF_OPEN = "half_open" # 시험

class CircuitBreaker:
    def __init__(self, failure_threshold: int = 5,
                 recovery_timeout: float = 30.0,
                 half_open_max: int = 3):
        self.failure_threshold = failure_threshold
        self.recovery_timeout = recovery_timeout
        self.half_open_max = half_open_max

        self.state = CircuitState.CLOSED
        self.failure_count = 0
        self.last_failure_time = 0
        self.half_open_count = 0
        self.lock = Lock()

    def call(self, func, *args, **kwargs):
        """보호된 함수 호출"""
        with self.lock:
            if self.state == CircuitState.OPEN:
                if time.time() - self.last_failure_time > self.recovery_timeout:
                    self.state = CircuitState.HALF_OPEN
                    self.half_open_count = 0
                else:
                    raise CircuitBreakerOpenError("Circuit breaker is OPEN")

        try:
            result = func(*args, **kwargs)
            self._on_success()
            return result
        except Exception as e:
            self._on_failure()
            raise e

    def _on_success(self):
        with self.lock:
            if self.state == CircuitState.HALF_OPEN:
                self.half_open_count += 1
                if self.half_open_count >= self.half_open_max:
                    self.state = CircuitState.CLOSED
                    self.failure_count = 0
            elif self.state == CircuitState.CLOSED:
                self.failure_count = 0

    def _on_failure(self):
        with self.lock:
            self.failure_count += 1
            self.last_failure_time = time.time()
            if self.state == CircuitState.HALF_OPEN:
                self.state = CircuitState.OPEN
            elif self.failure_count >= self.failure_threshold:
                self.state = CircuitState.OPEN

Bulkhead 패턴 (격벽)
┌─────────────────────────────────────────────┐
│                                             │
│  서비스 A용 스레드 풀: [████░░░░░░]          │
│  서비스 B용 스레드 풀: [██████░░░░]          │
│  서비스 C용 스레드 풀: [███░░░░░░░]          │
│                                             │
│  서비스 B가 느려져도 A, C에 영향 없음        │
│  각 서비스의 장애가 격리됨                   │
│                                             │
└─────────────────────────────────────────────┘

import random
import time
from functools import wraps

def retry_with_backoff(max_retries: int = 3,
                       base_delay: float = 1.0,
                       max_delay: float = 60.0,
                       jitter: bool = True):
    """지수 백오프와 지터를 적용한 재시도"""
    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            for attempt in range(max_retries + 1):
                try:
                    return func(*args, **kwargs)
                except Exception as e:
                    if attempt == max_retries:
                        raise e

                    delay = min(base_delay * (2 ** attempt), max_delay)
                    if jitter:
                        delay = delay * random.uniform(0.5, 1.5)

                    print(f"Attempt {attempt + 1} failed, "
                          f"retrying in {delay:.1f}s...")
                    time.sleep(delay)
        return wrapper
    return decorator

@retry_with_backoff(max_retries=5, base_delay=0.5)
def call_remote_service():
    """원격 서비스 호출"""
    pass