합의 알고리즘(Consensus Algorithm)은 분산 시스템에서 여러 노드가 동일한 데이터를 일관되게 유지하도록 보장하는 알고리즘입니다.
노드 간에 장애, 네트워크 지연, 메시지 유실이 발생하더라도 **시스템 전체의 정합성(consistency)**을 유지하는 것이 핵심 목적입니다.
기술사 관점에서 합의 알고리즘은 CAP 이론, FLP 이론, 분산 트랜잭션의 정합성 유지와 밀접히 연결되어 있으며, 다음과 같은 핵심 요소를 고려해야 합니다:
🔷 1. 합의 알고리즘이 필요한 이유
- 분산 시스템의 특성: 노드가 서로 다른 위치에 있고, 독립적으로 실행됨
- 장애 상황 존재: 일부 노드의 장애, 네트워크 분할, 메시지 손실 등
- 중앙 집중 노드가 없거나 신뢰할 수 없을 때 데이터의 정합성을 보장해야 함
🔷 2. 주요 합의 알고리즘
📌 1. Paxos
-
개발자: Leslie Lamport (1998)
-
특징:
- 이론적으로 가장 정확하게 증명된 합의 알고리즘
- 노드 간 다수결(Quorum) 기반
- 역할: Proposer, Acceptor, Learner
-
단점:
- 설계가 복잡하고 구현이 어려움
- 실제 시스템 적용 시 성능 이슈
📌 활용: Google Chubby, Microsoft Azure
📌 2. Raft
-
개발자: Diego Ongaro, John Ousterhout (2014)
-
Paxos를 대체하기 위해 탄생 – 더 쉽게 이해하고 구현할 수 있도록 설계
-
역할: Leader, Follower, Candidate
-
과정:
- Leader 선출 (Election)
- 로그 복제 (Log Replication)
- 커밋 동기화 (Commit)
-
장점:
- Paxos보다 구조가 명확하고 구현이 쉬움
- Leader 기반으로 성능 우수
📌 활용: etcd (Kubernetes 내부 키-값 저장소), Consul, TiDB 등
📌 3. Viewstamped Replication (VSR)
- Paxos와 유사하지만, Primary-Backup 구조를 채택
- Fault Tolerance를 위해 View라는 개념을 사용하여 Primary를 교체
- Raft와 개념적으로 유사
📌 4. Byzantine Fault Tolerant Algorithms (BFT 계열)
-
비잔틴 장애: 노드가 악의적으로 잘못된 정보를 보내는 상황까지 고려
-
PBFT (Practical Byzantine Fault Tolerance):
- 전체 노드의 ⅓ 이하가 악의적이어도 합의 가능
- 고성능, 하지만 노드 수가 많아질수록 통신량 급증
📌 활용: Hyperledger Fabric, Tendermint (Cosmos), 일부 블록체인
🔷 3. 비교 요약
| 알고리즘 | 장애 허용 | 특징 | 주요 사용 사례 |
|---|---|---|---|
| Paxos | Crash fault | 이론적으로 강력, 구현 복잡 | Chubby, Azure |
| Raft | Crash fault | 직관적 설계, 리더 기반 | etcd, Consul |
| PBFT | Byzantine fault | 악의적 노드 대응, 느림 | 블록체인, Hyperledger |
| Gossip (간접적 합의) | Eventually consistent | 빠르고 확장성 높음, 강한 일관성은 없음 | Cassandra, DynamoDB |
🔷 4. 관련 이론
📌 CAP Theorem
- Consistency, Availability, Partition tolerance
- 합의 알고리즘은 일반적으로 C + P 조합을 목표로 함
📌 FLP Impossibility Theorem
- 비동기 네트워크에서는 1개 노드라도 실패할 경우, 결정적인 합의 보장은 불가능
- ⇒ 실제 시스템은 시간 제한, 타임아웃, 리더 선출 등을 통해 우회
🔷 5. 기술사적 시사점
-
합의 알고리즘은 분산 시스템 설계의 핵심 요소로, 시스템의 신뢰성, 가용성, 확장성에 직접적인 영향을 미침
-
선택 시 고려 요소:
- 장애 유형: Crash vs Byzantine
- 시스템 구조: 리더 중심(Raft), 리더리스(PBFT)
- 요구 정합성 수준: Strong vs Eventual
- 성능 및 확장성 요구
-
합의 알고리즘은 단순한 데이터 저장을 넘어 마이크로서비스 간 상태 동기화, 블록체인, 멀티 데이터센터 동기화 등 광범위한 분야에 적용됨
