📦 분산 환경 알고리즘 정리 | Notion

요약 정리

합의 알고리즘: Paxos, Raft, Multi-Paxos, Zab
트랜잭션 처리: 2PC, 3PC
리더 선출: Bully, Ring
데이터 복제/동기화: Gossip, Viewstamped Replication
시간/순서 정렬: Lamport Clock, Vector Clock
분산 키-값 위치 찾기: Chord, DHT

분산 합의 알고리즘 (Consensus Algorithms)

분산 시스템에서 여러 노드가 하나의 값을 합의(Consensus) 하는 것이 목적입니다.

알고리즘	특징	장점	단점
Paxos	Leslie Lamport 제안
최초의 이론적 합의 알고리즘	이론적으로 안전성 보장	구현 복잡
이해 어렵고 디버깅 힘듦
Multi-Paxos	Paxos의 최적화 버전
리더 기반 연속 합의	Paxos보다 실용적	여전히 구현 난이도 높음
Raft	Paxos 대안으로 개발
리더 선출, 로그 복제 명확히 분리	이해 쉽고 구현 용이
교육용으로도 적합	Paxos보다 이론적으로 덜 정형화
Viewstamped Replication	Paxos와 유사
리더 기반으로 복제 수행	안정성, 견고함	상대적으로 알려지지 않음
Zab (Zookeeper Atomic Broadcast)	Zookeeper에서 사용
리더 기반 브로드캐스트 프로토콜	실용성 높음, Zookeeper에 최적화	범용 합의 알고리즘으로는 한계

분산 트랜잭션 알고리즘

원자성을 보장하는 트랜잭션 처리를 위한 알고리즘입니다.

알고리즘	특징
2PC (Two-Phase Commit)	Coordinator가 Prepare → Commit 단계로 나눠 합의
네트워크 장애 시 block 가능
3PC (Three-Phase Commit)	2PC에 타임아웃과 중간 상태 추가
non-blocking, 하지만 더 복잡