리더 선출(Leader Election)은 분산 시스템에서 여러 노드 중 하나를 리더로 선정하여 조율 역할을 맡기는 알고리즘이다. 리더는 쓰기 처리, 스케줄링, 잠금 등을 중앙에서 관리하여 시스템 일관성을 보장한다.
리더 선출이 필요한 이유
분산 시스템의 문제:
노드 A, B, C가 동시에 같은 작업 수행 → 데이터 충돌
리더 선출 해결:
노드 A가 리더 → 모든 쓰기 A를 통과 → 일관성 보장
A 장애 → B 또는 C가 새 리더로 선출
Bully 알고리즘
가정: 각 노드는 고유한 ID를 가짐
1. 노드 P가 리더 없음을 감지
2. P → 자신보다 높은 ID의 모든 노드: Election 메시지
3. 응답 없으면 P가 리더 선언
4. 더 높은 ID의 노드 Q가 응답하면:
Q → P: "OK" (내가 처리할게)
Q가 다시 Election 시작
5. 어떤 노드도 응답 안 하면 선언한 노드가 리더
문제: O(n²) 메시지, 네트워크 분할 시 다중 리더 가능
Raft 기반 리더 선출
가장 현대적이고 널리 사용되는 방식이다. 임기(Term) 번호를 이용하여 안전한 리더 선출을 보장한다. (자세한 내용은 Raft 합의 알고리즘 참조)
ZooKeeper 기반 리더 선출
python
from kazoo.client import KazooClient
zk = KazooClient(hosts='localhost:2181')
zk.start()
# Ephemeral Sequential 노드 생성
path = zk.create('/election/node', ephemeral=True, sequence=True)
# 예: /election/node0000000003 생성
# 가장 작은 번호 노드가 리더
children = sorted(zk.get_children('/election'))
if path.endswith(children[0]):
print("나는 리더!")
else:
# 바로 앞 노드를 Watch → 장애 시 재선출
prev = children[children.index(path[-10:]) - 1]
zk.exists(f'/election/{prev}', watch=lambda e: elect_leader())
뇌 분열(Split-Brain) 문제
네트워크 파티션으로 두 그룹이 각자 리더를 선출하는 상황이다.
해결책:
1. 과반수 쿼럼: 과반수 그룹만 리더 유지 (Raft 방식)
2. 펜싱 토큰: 리더 변경 시 토큰 번호 증가, 구 리더 요청 거부
3. STONITH: 구 리더 강제 종료 (Shoot The Other Node In The Head)
관련 개념
