분산 시스템의 시간과 장애: 8가지 착각부터 논리 시계까지

분산 시스템이 어려운 이유

분산 시스템은 네트워크로 연결된 여러 컴퓨터가 하나의 시스템처럼 동작하는 것이다. 어려움은 두 가지 물리적 현실이 겹치는 데서 나온다.

단일 프로세스 안에서는 함수 호출이 실패하면 즉시 알 수 있다. 원격 호출은 요청이 안 갔는지, 처리됐는데 응답만 잃었는지, 아직 처리 중인지 모른다. 그래서 재시도·멱등성·타임아웃이 분산 설계의 기본 부품이 된다.

분산 컴퓨팅의 8가지 착각

1994년 Peter Deutsch가 Sun에서 일곱 가지를 정리했고, 1997년 James Gosling이 여덟 번째를 더했다. 처음 분산 애플리케이션을 만드는 사람이 거의 반드시 하는 가정이며, 모두 틀린다.

장애는 일상이다

규모가 커지면 드문 장애도 매일 일어난다. MTBF(평균 고장 간격)가 30년인 아주 튼튼한 서버도 1만 대를 모으면 하루에 한 대꼴로 죽는다. 그래서 대규모 시스템은 장애 허용 소프트웨어를 피할 수 없다.

Google이 2009년에 공개한 「새 클러스터의 전형적인 첫해」는 이 규모 감각을 보여 준다.

장애는 독립적이지 않고 상관된다(랙·전원·스위치 단위로 같이 죽는다). 그래서 복제본은 같은 랙·같은 전원에 두지 않는다. 대응 원칙은 이렇다.

• 카나리 요청, 다른 복제본·데이터센터로 페일오버, 이상한 백엔드를 감지해 실요청에서 빼기.
• 일부가 고장 나도 에러 페이지보다 제한된 기능을 보여 준다(우아한 성능 저하).
• 모든 서버가 상태 페이지, 메트릭, 요청 샘플, 온라인 프로파일링을 내보내 「느리면 왜 느린지」 알 수 있게 한다.
• 평균뿐 아니라 p99 꼬리 지연을 본다. 중복 요청이나 타임아웃으로 꼬리를 줄인다.

장애 감지(하트비트, 타임아웃)와 이중화 구성은 고가용성 이중화 구조와 장애 감지에 있다.

전역 「지금」은 없다

정보는 빛보다 빨리 움직이지 못하므로 두 컴퓨터가 같은 순간을 동시에 알 수 없다. 1나노초에 전기가 가는 거리는 약 30cm다.

NTP·GPS·원자시계로 시계를 맞출 수는 있지만 오차를 없애지는 못한다. 시계 자체가 온도·부하·전력에 따라 빨라지고 느려지며, 같은 랙의 위아래 서버끼리도 다르게 흐른다. 가장 공들인 사례인 Google Spanner도 GPS와 원자시계를 써서 시계 오차를 1~7ms 수준으로 묶을 뿐이다. 그래서 Spanner의 TrueTime API는 현재 시각을 한 점이 아니라 [가장 이른, 가장 늦은] 구간으로 돌려준다. 불확실성을 숨기지 않고 드러내는 설계다.

여기에 장애가 더해지면 원리적인 한계가 생긴다.

불가능성 결과는 특정 시스템 모델 안에서의 결론이다. 「이 제품은 분할 중에도 일관되고 늘 가용하다」 같은 주장을 걸러 내는 잣대로 쓰되, 모델의 가정을 함께 알아야 한다. 실제 합의 프로토콜(Paxos, Raft)은 메시지 손실·노드 중단이 있는 세계에서도 안전성(서로 다른 결정을 내리지 않음)은 지키고, 진행(결국 결정함)은 네트워크가 안정된 동안에만 보장하는 식으로 이 한계를 비켜 간다.

사건의 순서: happened-before와 논리 시계

물리 시계를 믿을 수 없다면 「무엇이 먼저였나」를 어떻게 정할까. Lamport는 시간을 인과 관계로 다시 정의했다.

happened-before (→)

a → b도 b → a도 아니면 두 사건은 동시적(concurrent) 이다. 동시적이라는 말은 같은 시각이라는 뜻이 아니라 서로 영향을 줄 수 없었다는 뜻이다. 이 순서는 전체가 아닌 부분 순서(partial order)다. 특수 상대성 이론에서 관찰자마다 사건의 선후가 달라도 인과 순서만은 모두 같은 것과 같은 구조다.

Lamport 논리 시계

각 프로세스가 정수 카운터 하나를 들고 다음 두 규칙을 지킨다.

1. 사건이 일어날 때마다 C = C + 1
2. 메시지를 보낼 때 C를 함께 보낸다(T).
   받은 쪽은 C = max(C, T) + 1

그러면 a → b이면 C(a) < C(b) 가 보장된다. 시간이 같으면 프로세스 ID로 순서를 깨서 모든 사건의 전체 순서(total order)를 만든다.

• 역은 성립하지 않는다. C(a) < C(b)라고 a → b인 것은 아니다. 동시적인 사건도 숫자는 어느 한쪽이 작다.
• 인과 관계를 정확히 판별하려면 프로세스마다 카운터 배열을 들고 다니는 벡터 시계(vector clock)를 쓴다. 두 벡터를 비교해 「앞」, 「뒤」, 「동시」를 가린다. 버전 벡터는 같은 아이디어를 복제본 충돌 감지에 쓴 것이다.
• 물리 시계와 논리 시계를 섞은 하이브리드 논리 시계(HLC)는 실제 시각에 가까운 값을 유지하면서 인과 순서도 지킨다. CockroachDB 같은 분산 DB가 쓴다.
• 시스템 밖의 사건(사람이 전화로 알려 준 순서 등)은 논리 시계가 모른다. 외부 사건까지 맞추려면 동기화된 물리 시계가 필요하다.

전체 순서 = 어떤 분산 시스템이든 구현하는 법

모든 노드가 같은 순서로 같은 명령을 처리하면 같은 상태에 도달한다. 이것이 상태 기계 복제(state machine replication)다. 논문은 이를 분산 상호 배제(누가 먼저 자원을 쓰나) 예로 보였고, 오늘날 Raft·Paxos 기반 시스템(etcd, ZooKeeper, Kafka KRaft)이 같은 원리로 로그 순서를 합의한다.

일관성 모델

일관성 모델(consistency model) 은 복제된 데이터를 여러 클라이언트가 읽고 쓸 때 「어떤 결과가 보일 수 있나」를 정한 약속이다. 강할수록 프로그래밍이 쉽고, 약할수록 조율이 적어 빠르고 가용하다.

세션 보장은 최종 일관성 시스템에서 사용자가 가장 자주 겪는 이상을 막는 실용적인 중간 단계다.

AP 시스템(분할 중에도 응답하는 시스템)이 줄 수 있는 것은 최종 일관성과 그 위의 세션·인과 보장까지다. 선형화 가능성이 필요하면 분할 중 일부 요청을 거절하는 CP 쪽을 고른다. CAP과 PACELC는 데이터베이스 모델, 복제 지연 때문에 생기는 문제는 데이터베이스 확장과 성능 최적화에 있다.

합의 문제

합의(consensus) 는 여러 노드가 일부 고장이 나도 하나의 값(또는 하나의 순서)에 모두 동의하게 하는 문제다. 리더 선출, 분산 락, 원자적 커밋, 클러스터 멤버십, 그리고 무엇보다 복제 로그의 순서가 모두 합의로 풀린다. 앞 절의 상태 기계 복제가 합의 위에 서 있다.

어떤 장애를 가정하나

비잔티움 장군 문제

비잔티움 장군 문제(Byzantine Generals Problem) 는 Lamport·Shostak·Pease가 1982년에 정리한 문제다. 도시를 포위한 장군들이 전령으로만 연락하며 「모두 공격」이나 「모두 후퇴」 중 하나에 합의해야 하는데, 일부 장군이 배신자라 장군마다 다른 명령을 전한다. 충성스러운 장군들은 배신자가 있어도 같은 결정을 내려야 한다.

결론은 서명 없는 메시지(구두 메시지)로는 배신자가 전체의 3분의 1 이상이면 풀 수 없다는 것이다. 장군 셋 중 하나가 배신하면, 나머지 둘은 서로 다른 말을 들었을 때 누가 거짓말쟁이인지 가릴 수 없다. 그래서 f명의 배신자를 견디려면 3f+1명이 필요하다. 메시지에 위조할 수 없는 서명을 붙이면 조건이 완화된다.

이 문제가 중요한 것은 고장 난 노드가 멈추지 않고 틀린 말을 하는 경우를 가정하기 때문이다. 메모리·디스크 손상, 소프트웨어 버그, 해킹당한 노드, 그리고 서로를 믿지 않는 참여자가 그렇다.

• 한 조직이 운영하는 데이터센터 안에서는 노드가 거짓말을 하지 않는다고 보고 중단 장애 모델을 쓴다. 손상은 체크섬으로 따로 잡는다. etcd, ZooKeeper, Kafka KRaft가 그렇다.
• 누구나 참여하고 서로 믿지 않는 블록체인은 비잔티움 장애를 가정해야 한다. 비트코인은 작업 증명(PoW)으로 가장 많은 연산이 쌓인 체인을 따르게 해 확률적으로 합의한다(나카모토 합의). 참여자가 정해진 체인과 많은 지분 증명 체인은 PBFT 계열 BFT 알고리즘(Tendermint·CometBFT, HotStuff 등)으로 블록을 확정한다.

BFT 알고리즘과 Raft·Paxos

비잔티움 장애 허용(BFT, Byzantine Fault Tolerance) 은 일부 노드가 임의로 행동해도 시스템이 올바르게 동작하는 성질이다. 대표 알고리즘 PBFT(Practical BFT, 1999) 는 리더(primary)가 순서를 제안하면(pre-prepare) 노드끼리 서로 확인 메시지를 돌리고(prepare), 다시 확정 메시지를 돌려(commit) 2f+1개의 일치하는 응답이 모이면 실행한다.

근본 차이는 노드를 믿느냐다. CFT는 「살아 있는 노드는 프로토콜대로 행동한다」를 믿어 과반만으로 충분하고, BFT는 그 믿음 없이 서로 교차 검증하느라 노드도 메시지도 더 든다.

Paxos

Paxos 는 노드가 멈추거나 메시지를 잃어도 값 하나에 합의하게 하는 고전 알고리즘이다. 역할은 셋이다. 값을 제안하는 제안자(proposer), 제안을 받아들이는 수락자(acceptor), 결정된 값을 알게 되는 학습자(learner). 한 노드가 여러 역할을 겸한다. 안전성 조건은 「제안된 값만 선택되고, 값은 하나만 선택되며, 선택되지 않은 값을 선택됐다고 알지 않는다」이다.

1단계 (prepare / promise)
  제안자: 새 번호 n을 골라 수락자 과반에 prepare(n)
  수락자: 이미 응답한 어떤 prepare보다 n이 크면
          「n보다 작은 제안은 앞으로 받지 않겠다」고 약속하고,
          지금까지 수락한 제안 중 번호가 가장 큰 것(있으면)을 돌려준다
2단계 (accept / accepted)
  제안자: 과반의 약속을 받으면 accept(n, v)를 보낸다.
          v는 응답에 실려 온 제안 중 번호가 가장 큰 것의 값, 없으면 자기 값
  수락자: 그사이 더 큰 번호에 약속하지 않았다면 수락한다
과반이 (n, v)를 수락하면 v가 선택된다

• 과반 정족수가 핵심이다. 어떤 두 과반도 최소 한 노드를 공유하므로, 이미 선택됐을 수 있는 값은 다음 제안자의 1단계 응답에 반드시 실려 온다. 그래서 새 제안자는 그 값을 이어받을 수밖에 없다.
• 학습자는 수락자들이 수락 사실을 알려 와서 과반 수락을 확인한다. 메시지를 줄이려면 수락자가 대표 학습자 한 명에게만 알리고 그가 나머지에게 퍼뜨린다.
• 안전성은 늘 지키지만 진행은 보장하지 않는다. 두 제안자가 번갈아 더 큰 번호로 1단계를 시작하면 서로의 2단계를 무효로 만들며 끝없이 경쟁할 수 있다. 그래서 대표 제안자(리더) 하나만 제안하게 한다. 리더 선출에는 타임아웃 같은 시간 가정이 필요하며, 이는 비동기 네트워크에서 결정적 합의가 항상 끝나는 알고리즘은 없다는 FLP 불가능성과 맞닿아 있다.
• 상태 기계 복제는 Paxos를 여러 번 돌려 만든다(Multi-Paxos). 로그의 칸마다 Paxos 인스턴스 하나를 두고, 안정된 리더는 앞으로의 모든 칸에 대해 1단계를 한 번에 끝내 둔 뒤 칸마다 2단계만 보낸다. 새 리더가 빈칸을 발견하면 아무 효과 없는 no-op 명령으로 채워 순서를 이어 간다.

Raft는 이 구조(리더, 과반 복제, 로그)를 같은 보장으로 다시 짜서 각 부분을 명시적으로 정의한 알고리즘이다.

복제 방식별로 얻는 것과 내주는 것

데이터센터를 여러 곳에 두고 쓰기까지 받으려면(multihoming) 어떤 복제 방식을 쓰냐에 따라 얻는 것이 갈린다. 같은 DC 안 왕복은 1ms 안팎이지만 DC 사이는 수십~150ms라서, 동기 합의는 그만큼 쓰기 지연을 치른다.

2PC는 코디네이터 하나가 투표를 모으는 동기 프로토콜이라 무겁고, 코디네이터나 참여자 하나만 멈춰도 막힌다. Paxos는 과반만 응답하면 진행해 같은 강한 일관성을 더 나은 가용성으로 준다. Google Spanner, CockroachDB 같은 분산 SQL이 Paxos·Raft 위에서 DC를 넘는 트랜잭션을 제공하는 이유다. 2PC 자체와 사가 같은 대안은 분산 트랜잭션에 있다.

Raft

Raft 는 이해하기 쉬운 것을 목표로 2014년에 나온 합의 알고리즘이다. Paxos와 같은 보장을 주면서 문제를 리더 선출, 로그 복제, 안전성으로 나눴다. 시간은 임기(term) 라는 단조 증가 번호로 나뉘고, 임기마다 리더는 많아야 하나다.

리더 선출

stateDiagram-v2
  state "팔로워" as F
  state "후보" as C
  state "리더" as L
  F --> C: 선거 타임아웃(무작위, 논문 예시 150~300ms) 동안 하트비트를 못 받음 → 임기 +1, 자기에게 투표, 모두에게 RequestVote
  C --> L: 과반 득표 → 즉시 하트비트(빈 AppendEntries)로 선거를 끝낸다
  C --> F: 더 높거나 같은 임기의 리더 하트비트를 받음
  C --> C: 표가 갈려 아무도 과반을 못 얻음 → 타임아웃 뒤 임기를 올려 다시 선거
  note right of F
    각 노드: 한 임기에 한 표만, 먼저 온 후보에게 준다
    단, 후보의 로그가 자기 로그보다 최신이 아니면 거절한다
    (마지막 항목의 임기 → 인덱스 순으로 비교)
  end note

• 타임아웃을 무작위로 잡기 때문에 대개 한 노드가 먼저 깨어나 표가 갈리는 일이 드물다.
• 「로그가 더 최신인 후보에게만 투표」라는 제한 덕분에, 커밋된 항목을 모두 가진 노드만 리더가 된다(리더 완전성).
• 과반이 있어야 리더가 서므로 네트워크가 갈라져도 소수 쪽은 리더를 뽑지 못한다. 옛 리더가 소수 쪽에 남아도 과반 확인을 못 받아 아무것도 커밋하지 못하고, 높은 임기를 보는 순간 물러난다. 이것이 스플릿 브레인을 막는 원리다(고가용성 이중화 구조와 장애 감지).

로그 복제

sequenceDiagram
  participant c as 클라이언트
  participant l as 리더
  participant f as 팔로워들
  c->>l: 명령
  Note over l: 로그에 (임기, 인덱스, 명령) 추가
  l->>f: AppendEntries(새 항목들, 직전 항목의 인덱스·임기, 리더의 커밋 인덱스)
  alt 직전 항목이 내 로그와 맞음
    f-->>l: 덧붙이고 성공 응답
  else 안 맞음
    f-->>l: 거절
    Note over l,f: 리더가 한 칸씩 앞으로 물러나 다시 보내고,<br/>맞는 지점 뒤의 어긋난 항목은 리더 것으로 덮어쓴다
  end
  Note over l: 과반이 저장한 항목을 커밋 → 상태 기계에 적용
  l-->>c: 응답
  l->>f: 다음 AppendEntries(커밋 인덱스)
  Note over f: 커밋 인덱스를 보고 자기 상태 기계에 적용

읽기도 그냥 리더가 답하면 자기가 이미 물러난 줄 모르는 옛 리더가 옛 값을 줄 수 있다. 그래서 선형화 가능한 읽기는 읽기 전에 과반과 하트비트를 주고받아 아직 리더인지 확인하거나(read index), 시계에 기댄 리스(lease)를 쓴다.

조율의 비용과 피하는 법

합의 프로토콜(Paxos, Viewstamped Replication, Zab, Raft)은 논리적인 「지금」을 만들어 주지만 계속 통신해야 한다. 모든 사건의 순서를 조율하면 응답 지연은 최소 시스템 안 왕복 한 번(메시지 두 번)보다 짧아질 수 없고, 장애 중에는 진행이 멈출 수도 있다. 그래서 성능이 중요한 시스템은 「얼마나 적은 조율로 놀랍지 않은 동작을 줄 수 있나」를 찾는다.

• 클러스터 관리(리더 선출, 멤버십)를 직접 만든 조율 코드로 풀지 않는다. 검증된 합의 구현(etcd, ZooKeeper)을 쓴다.
• 실제 데이터베이스가 분할 상황에서 약속한 일관성을 지키는지는 Jepsen처럼 네트워크를 일부러 끊고 이력을 검증하는 테스트로 확인한다. 이런 분석(aphyr.com의 Jepsen 글 모음)에서 여러 DB가 문서에 적힌 보장을 어긴 사례가 드러났다.

정리

• 분산 시스템의 본질적 어려움은 비동기와 부분 장애다. 원격 호출은 실패 이유를 알 수 없다.
• 8가지 착각(신뢰성, 지연 0, 무한 대역폭, 보안, 고정 토폴로지, 단일 관리자, 전송 비용 0, 균질성)은 모두 틀린다. 재시도·멱등성·큰 메시지·표준 형식으로 대응한다.
• 규모가 커지면 장애는 매일 일어나고 서로 상관된다. 장애를 정상 경로로 설계한다.
• 전역 「지금」은 없다. 최선의 시계도 ms 단위 오차가 있으므로 순서는 논리 시계(Lamport, 벡터, HLC)나 합의로 정한다.
• 일관성 모델은 선형화 가능성에서 최종 일관성까지 이어지고, 그 사이의 인과·세션 보장(자기 쓰기 읽기, 단조 읽기)이 실용적인 타협점이다.
• 합의는 과반(2f+1)으로 중단 장애를, 3f+1과 교차 검증으로 비잔티움 장애를 견딘다. Raft는 무작위 타임아웃 선거와 과반 복제로 로그 순서를 맞춘다.
• 조율은 비싸다. 꼭 필요한 곳에만 합의를 쓰고, 나머지는 CRDT·멱등 연산처럼 순서가 필요 없는 설계로 뺀다.

관련 노트: 데이터베이스 모델: RDB, NoSQL, NewSQL, 고가용성 이중화 구조와 장애 감지, 분산 시스템의 통신·데이터 흐름 패턴, 데이터 관리 패턴: CDC, 이벤트 소싱, CQRS, 최종 일관성, 달력과 시간에 대한 개발자의 착각, 백엔드 지연 시간 줄이기: 숫자 감각과 기법, 고전 분산 시스템 설계