[분산 시스템] Day 1: 합의 - 여러 노드가 하나의 진실에 동의하는 법 (Raft)
이 글은 AI(Claude)의 도움을 받아 작성하고, 작성자가 검토·편집했습니다.
서론: 신뢰할 수 없는 부품으로 신뢰할 수 있는 시스템 만들기
분산 시스템의 근본 문제는 하나다. 여러 노드가, 일부가 죽거나 메시지가 지연되는 와중에도, 하나의 값에 동의할 수 있는가? 이것이 합의(consensus)다. 분산 데이터베이스의 리더 선출, 설정 공유, 분산 락이 전부 합의 위에 선다. 이 시리즈는 합의부터 장애 대응까지 5일에 걸쳐 다룬다.
1. 왜 합의가 어려운가
1
2
3
4
5
6
7
순진한 발상: "그냥 과반이 투표하면 되잖아?"
현실의 장애물:
- 메시지가 지연되거나 순서가 바뀜
- 노드가 응답 도중 죽음 (보냈는지 안 보냈는지 모름)
- 네트워크가 둘로 쪼개짐 (split-brain)
- 죽은 줄 알았던 노드가 되살아남
FLP 정리는 “완전 비동기 환경에서 한 노드라도 죽으면 합의를 보장할 수 없다”고 증명했다. 그래서 실용 알고리즘은 타임아웃(부분 동기)을 가정한다. Raft가 대표적이다.
2. Raft의 세 가지 상태
Raft는 Paxos보다 이해하기 쉽도록 설계됐다. 모든 노드는 세 상태 중 하나다.
1
2
3
4
5
6
7
[Follower] 평소 상태. 리더의 메시지를 따름
│ 일정 시간 리더 소식 없음 (election timeout)
▼
[Candidate] 스스로 출마해 투표 요청
│ 과반 득표
▼
[Leader] 모든 쓰기를 받고 팔로워에 복제. 주기적 하트비트 발송
핵심 개념은 임기(term)다. 단조 증가하는 번호로, 각 임기에 리더는 최대 한 명. 더 높은 임기를 본 노드는 즉시 팔로워로 물러난다. 이것이 split-brain 시 오래된 리더를 무력화한다.
3. 리더 선출
1
2
3
4
5
1. Follower가 election timeout(보통 150~300ms 랜덤) 동안 리더 소식이 없으면
2. term을 +1 하고 Candidate가 되어 자신에게 투표, 다른 노드에 RequestVote 발송
3. 각 노드는 term당 한 번만 투표 (선착순)
4. 과반 득표 → Leader. 즉시 하트비트로 자신의 권위를 알림
5. 동시에 여러 후보가 나와 표가 갈리면 → 타임아웃 후 재선거
타임아웃을 랜덤화하는 것이 핵심이다. 모두 동시에 출마해 표가 갈리는 상황(split vote)을 확률적으로 줄인다.
4. 로그 복제
리더가 정해지면 모든 쓰기는 리더를 거친다.
1
2
3
4
5
6
클라이언트 → Leader: "x=5 써줘"
1. Leader가 로그에 [term=2, x=5] 추가 (아직 미확정)
2. AppendEntries로 모든 Follower에 복제
3. 과반(자신 포함)이 로그에 기록하면 → "커밋(committed)" 확정
4. Leader가 상태 머신에 적용하고 클라이언트에 성공 응답
5. 다음 하트비트에 커밋 지점을 실어 Follower도 적용
1
2
3
4
5
로그 인덱스: 1 2 3 4
Leader: [x=1] [y=2] [x=5] [z=9]
Follower1: [x=1] [y=2] [x=5] ← 인덱스 3까지 복제됨
Follower2: [x=1] [y=2] [x=5] [z=9]
↑ 과반(3/3 중 자신+F2)이 가진 인덱스 3까지 커밋 가능
과반(quorum)이 기록해야 커밋이다. 그래서 노드 1대가 죽어도 나머지 과반으로 진행된다.
5. 안전성: 커밋된 것은 사라지지 않는다
Raft가 보장하는 핵심 불변식은 “한 번 커밋된 로그 항목은 이후 모든 리더의 로그에 반드시 존재한다“이다.
1
2
3
4
이를 위한 투표 제약:
Candidate의 로그가 투표자보다 최신이 아니면 표를 주지 않는다
→ 최신 로그를 가진 노드만 리더가 될 수 있음
→ 커밋된(과반이 가진) 항목은 반드시 차기 리더에 포함됨
이 제약이 “리더가 바뀌어도 확정된 데이터는 유실되지 않는다”를 보장한다. 분산 DB가 Raft 위에서 강한 일관성을 제공하는 근거다.
6. 노드 수와 장애 허용
1
2
3
4
5
6
7
8
정족수(quorum) = ⌊N/2⌋ + 1
N=3: quorum=2, 1대까지 장애 허용
N=5: quorum=3, 2대까지 장애 허용
N=7: quorum=4, 3대까지 장애 허용
짝수는 비효율: N=4도 quorum=3이라 1대만 허용 (N=3과 동일한데 비용↑)
→ 홀수(보통 3 또는 5)를 쓴다
노드를 늘리면 장애 내성은 오르지만 모든 쓰기가 더 많은 노드의 동의를 받아야 해 지연이 는다. 대개 5대가 균형점이다.
7. Day 1 체크리스트
- 합의가 “장애·지연 속에서도 하나의 값에 동의하기” 문제임을 이해했다.
- Raft의 세 상태(Follower/Candidate/Leader)와 임기(term) 개념을 파악했다.
- 랜덤 타임아웃이 split vote를 줄이는 이유를 안다.
- 과반 복제가 커밋의 조건이며 1대 장애를 견디게 함을 이해했다.
- 정족수 계산과 홀수 노드 선택의 이유를 설명할 수 있다.
다음 편 예고
합의는 강하지만 비싸다. 모든 데이터를 합의로 처리할 순 없다. Day 2에서는 복제 전략(동기 vs 비동기, 리더-팔로워 vs 다중 리더)과 각 방식의 일관성·가용성 트레이드오프를 다룬다.