분산 시스템 핵심 개념 완전 정리: CAP 정리부터 합의 알고리즘, 일관성 모델까지

단일 서버                    분산 시스템
+-----------+               +-----+  +-----+  +-----+
|  App +DB  |    vs         | N1  |--| N2  |--| N3  |
+-----------+               +-----+  +-----+  +-----+
                                  \    |    /
                               네트워크(불안정)

네트워크 분할 발생!

  [Node A]  ----X----  [Node B]
  data=1                data=1

  Client가 Node A에 write(data=2) 요청

  선택지 1 (CP): Node B와 동기화 불가 → 요청 거부 (가용성 포기)
  선택지 2 (AP): 일단 Node A만 업데이트 → 불일치 허용 (일관성 포기)

if (Partition) then
    Availability vs Consistency
else
    Latency vs Consistency

엄격한 일관성 (Strict)
    ↓
선형화 가능성 (Linearizability)
    ↓
순차 일관성 (Sequential)
    ↓
인과 일관성 (Causal)
    ↓
최종 일관성 (Eventual)

시간 →
Client A:  write(x=1) ------>
Client B:              read(x) → 반드시 1 반환

실제 시간:  A:write(x=1)  B:write(x=2)
순차 일관성: B:write(x=2), A:write(x=1) 도 허용
            (모든 노드가 이 순서에 동의하면)

A가 글 작성 → B가 댓글 작성 (인과 관계 있음)
  → 모든 노드에서 글이 댓글보다 먼저 보임

C가 글 작성 / D가 별도 글 작성 (인과 관계 없음)
  → 노드마다 순서가 다를 수 있음

시간 →
Node A:  x=1 ......... x=1 (변경 전파) → x=1
Node B:  x=0 ......... x=0 → x=1 (약간의 지연 후)
Node C:  x=0 ......... x=0 → x=1

           쓰기
Client → [Leader] → 복제 → [Follower 1]
                         → [Follower 2]
                         → [Follower 3]
           읽기
Client → [Follower 1, 2, 3 중 아무나]

# 반동기 복제 의사코드
def write(data):
    leader.write(data)
    ack_count = 1  # 리더 자신
    for follower in followers:
        if follower.replicate(data):
            ack_count += 1
            if ack_count >= 2:  # 최소 1개 팔로워 확인
                return SUCCESS
    return FAILURE

[Leader A] ←→ [Leader B] ←→ [Leader C]
    ↓              ↓              ↓
[Follower]    [Follower]    [Follower]

         write(x=1)
Client → [Node A] ✓
       → [Node B] ✓
       → [Node C] ✗ (장애)

W=2 성공 → 쓰기 성공!

         read(x)
Client → [Node A] x=1
       → [Node B] x=1
       → [Node C] x=0 (오래된 값)

R=2 → 최신 값(x=1) 반환

hash(key) mod N = partition_number

key="user_123" → hash → 7 → 7 mod 3 = 1 → Partition 1
key="user_456" → hash → 2 → 2 mod 3 = 2 → Partition 2

Partition 0: A-F
Partition 1: G-M
Partition 2: N-S
Partition 3: T-Z

        0
       / \
     330   30
     /       \
   300        60
   |    Ring    |
   270        90
     \       /
     240   120
       \ /
       180

Node A: 0-90
Node B: 90-180
Node C: 180-270
Node D: 270-360

Node E 추가(135 위치) → Node B의 90-135만 Node E로 이동

Phase 1: Prepare
  Proposer → Acceptor: "제안 번호 n을 준비해주세요"
  Acceptor → Proposer: "OK" (이전에 수락한 값이 있으면 함께 전달)

Phase 2: Accept
  Proposer → Acceptor: "제안 번호 n, 값 v를 수락해주세요"
  Acceptor → Proposer: "수락" (과반수가 수락하면 합의 완료)

시간 →
           Term 1          Term 2
Follower: [Heartbeat]... [Timeout!] → Candidate
Candidate: 자신에게 투표 + 다른 노드에 RequestVote
           과반수 득표 → Leader 당선!

Leader:   [Heartbeat]→[Heartbeat]→[Heartbeat]→...

# Raft 리더 선출 의사코드
class RaftNode:
    def __init__(self):
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.election_timeout = random(150, 300)  # ms

    def on_timeout(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.id
        votes = 1  # 자기 자신

        for peer in self.peers:
            if peer.request_vote(self.current_term, self.log):
                votes += 1

        if votes > len(self.peers) // 2:
            self.state = "leader"
            self.send_heartbeats()

Client → Leader: write(x=5)

Leader Log: [Term1:x=3] [Term1:y=7] [Term2:x=5]
                                        ↓ AppendEntries
Follower1: [Term1:x=3] [Term1:y=7] [Term2:x=5] ✓
Follower2: [Term1:x=3] [Term1:y=7] [Term2:x=5] ✓
Follower3: [Term1:x=3] [Term1:y=7] (네트워크 지연)

과반수(3/5) 복제 완료 → 커밋! → 클라이언트에 응답

Phase 1: Prepare (투표)
  Coordinator → Participant A: "커밋 가능?"
  Coordinator → Participant B: "커밋 가능?"
  A → Coordinator: "Yes"
  B → Coordinator: "Yes"

Phase 2: Commit (실행)
  Coordinator → A: "커밋!"
  Coordinator → B: "커밋!"

Phase 1: CanCommit
Phase 2: PreCommit (타임아웃 설정)
Phase 3: DoCommit

주문 생성 Saga:

T1: 주문 생성 → T2: 결제 처리 → T3: 재고 차감 → T4: 배송 시작
                      ↓ 실패!
C2: 결제 취소 ← C1: 주문 취소

# Saga Orchestrator 의사코드
class OrderSaga:
    steps = [
        ("create_order", "cancel_order"),
        ("process_payment", "refund_payment"),
        ("update_inventory", "restore_inventory"),
        ("arrange_shipping", "cancel_shipping"),
    ]

    def execute(self):
        completed = []
        for action, compensation in self.steps:
            try:
                getattr(self, action)()
                completed.append(compensation)
            except Exception:
                # 보상 트랜잭션 역순 실행
                for comp in reversed(completed):
                    getattr(self, comp)()
                raise SagaFailed()

규칙:
1. 이벤트 발생 시 카운터 증가
2. 메시지 전송 시 자신의 카운터를 포함
3. 메시지 수신 시 max(자신 카운터, 받은 카운터) + 1

Process A:  (1)→ (2)→ (3)────→ (6)
                       send     recv
Process B:       (1)→ (2)→ (4)→ (5)
                       recv     send

3개 노드 A, B, C

A: [1,0,0] → [2,0,0] → [2,0,0] send to B
B: [0,0,0] → [0,1,0] → [2,2,0] recv from A → [2,3,0] send to C
C: [0,0,0] → [0,0,1] → [2,3,2] recv from B

def compare_vector_clocks(vc1, vc2):
    """벡터 시계 비교"""
    less = False
    greater = False
    for a, b in zip(vc1, vc2):
        if a < b:
            less = True
        elif a > b:
            greater = True

    if less and not greater:
        return "BEFORE"      # vc1 < vc2
    elif greater and not less:
        return "AFTER"       # vc1 > vc2
    elif not less and not greater:
        return "EQUAL"
    else:
        return "CONCURRENT"  # 동시 이벤트!

HLC = (물리적 시간, 논리적 카운터)

물리적 시간이 같을 때 논리적 카운터로 순서 결정
→ NTP 오차 범위 내에서 인과 관계 보장

Node A → "살아있어?" → Node B
Node A ← "응!" ← Node B

... 시간 초과 ...

Node A → "살아있어?" → Node B
Node A ← (무응답) ← Node B
→ Node B 장애로 판단

Phi(φ) 값:
  φ = 1  → 10% 확률로 장애
  φ = 2  → 1% 확률로 장애
  φ = 3  → 0.1% 확률로 장애

임계값(예: φ > 8)을 넘으면 장애로 판단

1. Node A가 Node B에 ping
2. 응답 없으면 → Node C, D에 "B에 indirect ping 해줘" 요청
3. C, D가 B에 ping → 응답 없으면 B를 의심(suspect)
4. 일정 시간 후 여전히 응답 없으면 B를 제거
5. 가십(gossip)으로 멤버십 변경을 전파

아키텍처:
  - Leaderless, Consistent Hashing
  - Quorum 읽기/쓰기 (W + R > N)
  - 가십 프로토콜로 멤버십 관리
  - Last-Write-Wins 충돌 해결
  - SSTable + Memtable 저장 구조

PACELC: PA/EL
  - 분할 시: 가용성 우선
  - 정상 시: 낮은 지연 우선

아키텍처:
  - 전 세계 분산, 강한 일관성
  - TrueTime API: GPS + 원자시계로 시간 불확실성 구간 제공
  - Paxos 기반 복제
  - 외부 일관성(External Consistency) 보장

TrueTime:
  TT.now() → [earliest, latest]
  불확실성 구간이 보통 1-7ms

  트랜잭션 커밋 시:
  1. 타임스탬프 s 할당
  2. commit-wait: TT.after(s)가 true가 될 때까지 대기
  3. 불확실성 구간만큼 대기하여 순서 보장

아키텍처:
  - Consistent Hashing + 가상 노드
  - Sloppy Quorum: 장애 시 다른 노드가 대신 응답
  - Hinted Handoff: 복구 후 원래 노드에 데이터 전달
  - Vector Clock으로 버전 관리
  - Merkle Tree로 안티 엔트로피