[분산 시스템] 컨센서스(Consensus) 정리

 

1. 컨센서스란?

 

컨센서스(Consensus)는 합의라는 뜻으로, 분산 시스템에서 여러 노드들이 공통된 상태 정보에 동의하는 과정이다. 어그리먼트(Agreement)와 같은 말이며, 모든 노드가 동일한 값을 인식하도록 맞추는 것이 핵심이다.

 

 

2. 분산 시스템이 Unreliable한 이유

 

분산 시스템의 노드들은 네트워크를 통해 메시지를 교환하는데, 네트워크 자체가 불안정하다.

문제 설명

패킷 손실	메시지가 중간에 유실될 수 있음
딜레이	스위치 트래픽 과부하로 지연 발생
순서 역전	패킷 순서가 뒤바뀔 수 있음
중복 메시지	스퓨리어스 타임아웃으로 중복 전송
노드 크래시	경고 없이 갑자기 장애 발생
네트워크 파티션	클러스터가 고립된 그룹으로 분리

 

TCP 같은 프로토콜이 Reliability를 높여주려 하지만, 근본적으로 분산 시스템은 Unreliable하다.

 

 

3. 글로벌 클락(Global Clock) 문제

 

• 모든 컴퓨터는 독립적인 시계를 가지며, 완전히 동일한 시간을 공유하지 않는다.
• NTP로 주기적으로 동기화하지만 완벽하지 않다.
  • 쿼츠 시계 기준 하루 최대 8.6초 오차 발생
  • LAN 환경에서도 1ms ~ 10ms 오차 발생
• 따라서 물리적 타임스탬프로 이벤트 순서를 결정하는 것은 신뢰할 수 없다.
• 분산 시스템에서 관심 있는 건 실제 시간이 아니라 이벤트의 순서이므로, 로지컬 클락을 사용해야 한다.

 

 

4. 로지컬 클락(Logical Clock)

 

물리적 시간 대신 카운터(시퀀스 넘버)로 이벤트의 순서를 표현하는 방식.

 

4-1. 램포트 로지컬 클락 (Lamport Logical Clock)

 

각 프로세스가 로컬 카운터를 가지고 다음 규칙에 따라 동작한다.

 

로컬 이벤트 발생	자신의 카운터 +1
메시지 전송	현재 카운터 값을 메시지에 첨부해서 전송
메시지 수신	max(로컬값, 수신값) + 1

 

P1 카운터: 1 → 이벤트 → 2 → 메시지 전송(값: 2)
P2 카운터: 1 → 메시지 수신 → max(1, 2) + 1 = 3

 

한계: 토탈 오더(전체 순서)만 제공하므로, 동시에 발생한 이벤트를 구분하지 못한다.

 

4-2. 벡터 클락 (Vector Clock)

 

램포트 클락의 한계를 보완한 방식. 노드 수만큼의 배열(벡터) 형태로 클락을 관리한다.

상황 동작

로컬 이벤트 발생	자신의 인덱스 값만 +1
메시지 전송	현재 벡터 전체를 메시지에 첨부
메시지 수신	각 인덱스별 max 취한 후 자신의 인덱스 +1

 

초기 상태
P1: [1,0,0]  P2: [0,1,0]  P3: [0,0,1]

P1 로컬 이벤트 → P1: [2,0,0]
P1 → P2 메시지 전송 (값: [2,0,0])
P2 수신: max([0,1,0], [2,0,0]) + P2 인덱스 +1 → [2,2,0]

장점: 개별 머신의 이벤트를 독립적으로 트래킹하므로 동시 발생 이벤트(Concurrent Event)도 추적 가능.

 

 

5. 컨센서스의 3가지 핵심 속성 

 

Validity (유효성)	결정된 값은 반드시 누군가가 제안한 값이어야 함	짜장·짬뽕·탕수육 중에서 골라야지, 갑자기 유산슬은 안 됨
Termination (종료성)	모든 correct 노드는 반드시 최종 결정을 내려야 함	"나는 싫어, 안 먹어!" 하며 때 쓰는 거 불가
Integrity (무결성)	각 노드는 한 번만 결정하며, 번복 불가	투표 후 "다른 사람 찍고 싶어"는 불가

 

 

6. FLP Impossibility

 

비동기 시스템에서 단 하나의 프로세스가 크래시해도, 컨센서스를 보장하는 것은 불가능하다.

• 이유: 비동기 시스템에서는 메시지 딜레이와 크래시를 구분할 수 없음
• 실제 해결책: 타임아웃(Bounded Delay)을 사용해 우회

 

 

7. Paxos

 

레슬리 램포트가 1990년 제안한 컨센서스 프로토콜. (쉬운 버전 논문은 1998년 출판)

구성 요소

Proposer	값을 제안
Acceptor	제안에 투표
Learner	결정된 값을 학습

 

Phase 1 — Prepare & Promise

Proposer → (고유 번호 N 브로드캐스트) → Acceptors

Acceptors → N이 자신이 본 번호 중 가장 크면:
  - "N보다 낮은 제안은 앞으로 수락 안 하겠다" Promise
  - 이전에 수락했던 값(VA)도 함께 Proposer에게 반환

 

 

Phase 2 — Accept & Accepted

과반수 Promise 획득 시:
Proposer → Accept 메시지 전송
  - 이전 수락 값이 있으면 → 가장 높은 번호의 값 사용 (자신의 원래 제안값 X)
  - 없으면 → 자신의 제안값 사용

Acceptors 과반수 수락 시 → 값 확정 → Learner에게 통보

 

Fault Tolerance	f개 장애 허용 시 최소 2f+1개 Acceptor 필요 (과반수 유지)
Safety	하나의 값만 선택됨
Liveness	보장 안 됨 → Dueling Proposers 문제 발생 가능

 

 

Dueling Proposers: Proposer가 여러 개일 때 서로 상대 제안을 무효화해서 영원히 컨센서스가 안 될 수 있음.

 

 

8. Multi-Paxos & Raft

 

Multi-Paxos (Stable Leader Optimization)

 

기본 Paxos는 메시지 딜레이가 4단계 (Prepare → Promise → Accept → Accepted). 리더를 미리 선출해서

Phase 1을 생략 → Phase 2만 반복하면 효율적.

리더(Proposer) → "이렇게 해" → 팔로어들 → "네 알겠습니다"

 

 

Raft (2014)

 

Paxos를 최대한 단순화한 프로토콜. 스탠포드 수업에서 학생들이 잘 이해했을 만큼 직관적이다.

• 리더-팔로어 구조 + 하트비트 기반 리더 선출
• Multi-Paxos의 Stable Leader Optimization 적용
• 실무에서 가장 널리 사용

 

 

9. 쿼럼(Quorum) 시스템

 

과반수 동의를 기반으로 한 시스템. =

R + W > N

 

 

R	읽기 정족수
W	쓰기 정족수
N	전체 레플리카 수

 

 

이 조건을 만족하면 읽기와 쓰기 사이에 반드시 겹치는 노드가 최소 1개 존재 → 항상 최신 데이터를 읽을 수 있음.

 

R=3, W=3	읽기/쓰기 균형
R=2, W=4	Write-heavy (쓰기 우선)
R=4, W=2	Read-heavy (읽기 우선)

 

10. 실제 사용 현황

 

Apache Kafka	ZooKeeper → Raft
etcd	Raft
CockroachDB	Raft
Google Spanner	Paxos
Consul	Raft
ZooKeeper	ZAB (리더 베이스)

 

 

실제 프로덕션에서는 Raft를 가장 많이 사용한다. 이유는 Paxos의 심플한 버전이기도 하고, 결국 사람들이 심플한 걸 선호하기 때문이다.

 

⭐핵심 요약

 

컨센서스	모든 노드가 동일한 값에 합의하는 과정
글로벌 클락	존재하지 않음 → 로지컬 클락 사용
램포트 클락	카운터 기반, 토탈 오더 제공
벡터 클락	벡터 기반, 동시 이벤트도 추적 가능
FLP	비동기 시스템에서 컨센서스 완벽 보장 불가
Paxos	과반수 투표 기반 컨센서스 프로토콜
Raft	Paxos를 단순화한 리더 베이스 프로토콜
Quorum	R + W > N 조건으로 최신 데이터 보장