← 목록으로
컴퓨팅·임베디드
#리더 선출#분산 합의#Raft#스플릿 브레인#펜싱 토큰
최종 업데이트 · 2026-11-18

리더 선출(Leader Election)과 분산 시스템의 단일 조정자 확보

1. 개요

가. 정의

리더 선출(Leader Election)이란 동등한 권한을 가진 여러 노드로 구성된 분산 시스템에서, 특정 역할(쓰기 조정, 로그 복제, 작업 할당 등)을 수행할 단 하나의 리더 노드를 노드들이 스스로 합의하여 선택하고, 그 리더가 사라졌을 때 다시 새 리더를 뽑는 분산 조정(coordination) 메커니즘이다.

분산 시스템은 단일 서버의 성능·가용성 한계를 넘기 위해 여러 노드로 동일한 역할을 수행하게 한다. 그런데 "모든 노드가 대등하다"는 성질은 확장성과 가용성을 주는 동시에, 같은 자원을 동시에 변경하거나 같은 작업을 중복 수행하는 충돌을 낳는다. 리더 선출은 이 충돌을 구조적으로 막기 위해, 특정 순간에 쓰기·조정 권한을 한 노드에만 집중시키고 나머지는 추종자(follower)로 두는 방식이다. 리더가 사라지면 남은 노드들이 새 리더를 뽑아 서비스를 이어가므로, 단일 조정자의 단순함과 다중 노드의 가용성을 동시에 얻는다.

리더 선출은 그 자체로 하나의 합의 문제이기도 하다. "누가 리더인가"에 대해 노드들이 서로 다른 답을 가지면, 두 노드가 동시에 리더처럼 행동하는 스플릿 브레인(split-brain)이 발생해 데이터가 손상된다. 따라서 기술사 관점에서 리더 선출은 단순한 "대표 뽑기"가 아니라, 안전성(최대 한 명의 리더)과 활동성(언젠가 반드시 리더가 존재)이라는 분산 합의의 두 속성을 만족시켜야 하는 문제로 이해해야 한다.

나. 등장 배경과 필요성

초기의 고가용 구성은 액티브-스탠바이(active-standby) 이중화로, 사람이 장애를 감지하고 수동으로 예비 서버를 승격시켰다. 이 방식은 감지와 전환에 분(minute) 단위 시간이 걸리고, 운영자가 실수로 두 서버를 동시에 액티브로 만들면 곧바로 데이터 충돌로 이어졌다. 노드 수가 수십·수백으로 늘고 클라우드에서 노드가 수시로 생성·소멸하는 환경에서는, 사람이 리더를 지정하는 방식 자체가 병목이자 단일 장애점이 된다.

또한 현대 분산 데이터베이스·메시지 브로커·오케스트레이터는 "정확히 한 번(exactly-once)" 혹은 "선형화 가능(linearizable)" 수준의 일관성을 요구한다. 예컨대 분산 데이터베이스가 복제 로그를 여러 노드에 순서대로 적용하려면, 로그의 순서를 결정할 단일 직렬화 지점이 필요하다. 스케줄러가 크론 작업을 정확히 한 번만 실행하려면, 여러 스케줄러 인스턴스 중 하나만 실제 실행 권한을 가져야 한다. 이처럼 "여럿이지만 결정은 하나가" 내려야 하는 요구가 보편화되면서, 장애를 자동 감지하고 수초 내에 새 리더로 전환하는 자동화된 리더 선출이 필수 기반 기술로 자리 잡았다.

구체적으로 Apache Kafka는 각 파티션에 리더 복제본 하나를 두어 모든 읽기·쓰기를 처리하게 하고, 리더 브로커가 죽으면 ISR(In-Sync Replica) 중에서 새 리더를 선출한다. Kafka 3.x 이후의 KRaft 모드는 과거 ZooKeeper에 의존하던 컨트롤러 선출까지 Raft 기반 내장 합의로 대체하여, 외부 코디네이터 없이 메타데이터 리더를 선출한다. 이는 리더 선출이 특정 제품의 부가 기능이 아니라 분산 시스템의 핵심 골격임을 보여주는 사례다.

다. 핵심 특성과 만족해야 할 속성

리더 선출 알고리즘은 다음 속성을 만족해야 한다. 첫째, 안전성(safety)으로 "어느 순간에도 유효 리더는 최대 한 명"이어야 한다. 동시에 두 리더가 쓰기를 수행하면 데이터가 갈라진다. 둘째, 활동성(liveness)으로 "장애나 분할이 수습되면 언젠가는 반드시 리더가 선출"되어야 한다. 아무도 리더가 되지 못해 영원히 멈추면 가용성이 0이 된다.

FLP 불가능성 정리는 완전 비동기 네트워크에서 한 노드라도 장애가 있으면 안전성과 활동성을 동시에 항상 보장하는 결정적 합의는 불가능함을 증명한다. 현실 시스템은 타임아웃과 무작위화를 도입해 활동성을 "실용적 확률"로 확보하고 안전성은 절대 포기하지 않는 설계를 택한다. 즉 네트워크가 심하게 불안정하면 잠시 리더가 없을 수는 있어도, 두 리더가 동시에 존재하는 일만큼은 막는다. 셋째, 리더 선출은 장애 감지(failure detection)와 밀접하다. 리더가 "정말 죽었는지, 단지 느린지"를 구분하는 것이 선출의 출발점이며, 이 판단이 틀리면 불필요한 재선출이나 스플릿 브레인이 생긴다.

2. 전체 구조와 동작 원리

가. 전체 구조

리더 선출 기반 시스템은 일반적으로 노드 집합, 장애 감지 계층, 선출 알고리즘, 그리고 리더 임기를 식별하는 토큰(term·epoch·fencing token)으로 구성된다. 아래 구조도는 추종자들이 리더를 추종하다가, 리더 장애를 감지하면 선출 과정을 거쳐 새 리더를 세우고, 외부 클라이언트는 항상 현재 리더로 요청이 라우팅되는 흐름을 보여준다.

flowchart TB
  C["클라이언트 / 외부 요청"] --> R{"현재 리더 라우팅"}
  R --> L["리더 노드: 쓰기·조정·로그 순서 결정"]
  L -->|상태·로그 복제| F1["추종자 1"]
  L -->|상태·로그 복제| F2["추종자 2"]
  L -->|하트비트| F3["추종자 3"]
  F1 -. 하트비트 감시 .-> D["장애 감지 계층"]
  F2 -. 하트비트 감시 .-> D
  F3 -. 하트비트 감시 .-> D
  D -->|리더 타임아웃| E["선출 절차 개시"]
  E -->|새 임기 번호 부여| NL["신규 리더 확정"]
  NL -->|펜싱 토큰 갱신| R

이 구조의 핵심은 임기 번호(term/epoch)다. 리더가 바뀔 때마다 단조 증가하는 번호를 부여하고, 추종자와 공유 자원은 "더 큰 임기 번호를 제시하는 리더만 인정"한다. 이렇게 하면 네트워크에서 뒤늦게 깨어난 과거 리더가 낡은 임기 번호로 명령을 내려도, 자원이 이를 거부하여 스플릿 브레인을 차단한다.

나. 대표 알고리즘별 동작

리더 선출 알고리즘은 크게 네 가지 계열로 나눌 수 있으며, 각각 전제와 복잡도가 다르다.

(A) 불리 알고리즘(Bully Algorithm). Garcia-Molina가 1982년 제안한 고전 알고리즘으로, 각 노드에 고유한 우선순위 번호를 부여하고 "살아 있는 노드 중 번호가 가장 큰 노드"가 리더가 된다. 리더 부재를 감지한 노드는 자신보다 번호가 큰 모든 노드에게 선출 메시지를 보내고, 응답이 없으면 스스로 리더를 선언하며, 응답이 있으면 더 높은 번호 노드에게 선출을 양보한다. 구현이 직관적이지만 리더 교체 시 메시지가 $O(N^2)$까지 증가하고, 느린 노드를 죽은 것으로 오인하면 "왕따 교체"가 반복되는 약점이 있다.

(B) 링 알고리즘(Ring Algorithm). 노드를 논리적 링으로 배열하고, 선출 메시지가 링을 한 바퀴 돌면서 만난 노드들의 식별자를 수집한 뒤, 가장 큰 식별자를 리더로 확정한다. 메시지 복잡도가 $O(N)$으로 불리보다 낮지만, 링 중간 노드가 죽으면 링 복구 로직이 필요하고 수렴이 느리다.

(C) 합의 기반 선출(Consensus-based, Raft/Paxos 계열). 오늘날 실무의 표준이다. Raft는 노드를 추종자·후보자·리더의 세 상태로 두고, 무작위 선거 타임아웃(randomized election timeout)을 사용한다. 추종자가 일정 시간(통상 150~300ms) 동안 리더 하트비트를 못 받으면 임기 번호를 1 올리고 후보자가 되어 자기 자신에게 투표한 뒤 다른 노드에 투표를 요청한다. 과반수(quorum, N/2+1)의 표를 먼저 모은 후보자가 리더가 되며, 각 노드는 한 임기에 한 표만 주므로 한 임기에 두 리더가 생기지 않는다. 무작위 타임아웃은 여러 후보가 동시에 출마해 표가 갈리는 스플릿 보트(split vote)를 확률적으로 빠르게 해소한다.

(D) 임차권 기반 선출(Lease-based, 코디네이션 서비스 활용). ZooKeeper·etcd 같은 외부 코디네이션 서비스에 선출을 위임하는 방식이다. 각 노드가 공유 저장소에 임시(ephemeral) 키나 임차권(lease)을 획득하려 경쟁하고, 먼저 획득한 노드가 리더가 되며, 세션이 끊기거나 임차 기간이 만료되면 키가 사라져 다음 노드가 리더가 된다. 애플리케이션은 복잡한 합의를 직접 구현하지 않고도 안정적 선출을 얻는다. Kubernetes 컨트롤러·스케줄러의 HA 구성이 대표적으로 이 Lease 객체 기반 선출을 사용한다.

아래 상태도는 Raft 계열 노드가 추종자에서 후보자를 거쳐 리더가 되고, 더 높은 임기 번호를 발견하면 다시 추종자로 내려오는 과정을 나타낸다.

stateDiagram-v2
  [*] --> Follower
  Follower --> Candidate: 선거 타임아웃 경과
  Candidate --> Candidate: 스플릿 보트 발생, 임기 증가 후 재투표
  Candidate --> Leader: 과반수 득표 획득
  Candidate --> Follower: 더 높은 임기의 리더 발견
  Leader --> Follower: 더 높은 임기 번호 수신
  Leader --> Leader: 주기적 하트비트 전송

다. 펜싱 토큰과 스플릿 브레인 방지 절차

리더 선출에서 가장 위험한 실패는 "리더라고 믿는 두 노드가 동시에 쓰기를 하는" 스플릿 브레인이다. 네트워크 분할, GC로 인한 장시간 일시정지, 느린 디스크 등으로 기존 리더가 자신이 교체된 사실을 모른 채 깨어나 과거의 권한으로 쓰기를 시도할 수 있다. 이를 막는 표준 기법이 펜싱 토큰(fencing token)이다. 리더가 바뀔 때마다 단조 증가하는 번호를 발급하고, 보호 대상 자원(스토리지·DB)이 이제까지 본 가장 큰 토큰보다 작은 토큰의 요청을 스스로 거부한다.

Martin Kleppmann이 지적했듯, 락이나 임차권을 "획득했다"는 사실만으로는 안전하지 않다. 임차권을 잃은 노드가 잠시 멈춰 있다가 깨어나 뒤늦게 쓰기를 보낼 수 있기 때문이며, 결국 자원 스스로가 토큰을 검사해 과거 리더의 쓰기를 차단해야 안전성이 보장된다. 아래 시퀀스는 과거 리더의 지연된 쓰기가 더 큰 토큰을 가진 신규 리더 때문에 거부되는 과정을 보여준다.

sequenceDiagram
  participant L1 as 과거 리더 토큰 33
  participant S as 공유 스토리지
  participant L2 as 신규 리더 토큰 34
  L2->>S: 쓰기 요청 토큰 34
  S-->>L2: 수락 및 최대 토큰 34 기록
  L1->>S: 지연된 쓰기 요청 토큰 33
  S-->>L1: 거부, 토큰 33 은 34 보다 작음

3. 알고리즘 비교와 적용 사례

알고리즘 선택은 노드 수, 네트워크 가정, 요구 일관성 수준에 따라 달라진다. 아래 표는 대표 계열을 비교한 것이나, 핵심은 "실무에서는 안전성을 위해 과반수 합의 또는 외부 코디네이션에 기반한 선출이 사실상 표준"이라는 점이다. 불리·링은 교육적 가치가 크지만, 느린 노드를 죽음으로 오인했을 때 스플릿 브레인을 구조적으로 막지 못해 강한 일관성이 필요한 현대 시스템에는 단독으로 쓰지 않는다.

구분 불리 링 Raft/Paxos 임차권 기반
리더 결정 기준 최대 식별자 링 순회 최대 식별자 과반수 득표 공유 키 선점
메시지 복잡도 $O(N^2)$ $O(N)$ $O(N)$ 수준 서비스에 위임
스플릿 브레인 방어 약함 약함 임기+과반수 임차+펜싱
네트워크 가정 동기적 동기적 부분 동기 세션/타임아웃
대표 사용처 교육·소규모 교육 etcd·Consul·Kafka KRaft ZooKeeper·K8s Lease

실무 사례를 보면 차이가 더 분명해진다. ZooKeeper는 ZAB 프로토콜과 epoch 번호, 그리고 순차 임시 노드(sequential ephemeral znode)를 이용한 "가장 작은 시퀀스 노드가 리더" 방식의 선출 레시피를 제공하며, HBase·Kafka(구버전)·Solr 등이 이를 활용했다. etcd는 Raft를 핵심으로 삼아 리더를 선출하고, 임차권(lease)과 리비전 번호로 분산 락·리더 선출 API를 제공한다. Kubernetes의 모든 상태가 etcd에 저장되는 만큼, etcd의 리더 선출 안정성은 클러스터 전체의 가용성과 직결된다. Kubernetes 컨트롤러 매니저·스케줄러는 Lease 객체를 주기적으로 갱신(renew)하는 방식으로 리더를 유지하며, 갱신이 끊기면 다른 인스턴스가 Lease를 획득해 수초 내 승계한다. 이는 코디네이션 서비스 패턴이 플랫폼 레벨 HA의 사실상 표준임을 보여준다.

예컨대 3노드 etcd 클러스터에서 리더가 죽으면, 남은 2노드가 과반수(2/3)를 이루므로 수백 밀리초 내에 새 리더를 뽑아 쓰기를 재개한다. 반대로 5노드 클러스터가 2+3으로 분할되면, 2노드 쪽은 과반수를 못 이루어 스스로 쓰기를 멈춘다. 이 "소수파는 멈춘다(fail-stop)"는 설계가 바로 스플릿 브레인을 막는 핵심 원리다.

4. 심화: 장애 감지 민감도와 실무 튜닝

리더 선출의 실무 난제는 알고리즘 자체보다 장애 감지의 정확도와 민감도 조정에 있다. 하트비트 타임아웃을 너무 짧게 잡으면, 일시적 네트워크 지연이나 GC 멈춤을 리더 사망으로 오인해 멀쩡한 리더를 교체하는 불필요한 리더 교체(leadership churn)가 반복된다. 리더가 바뀔 때마다 캐시 워밍, 로그 재정렬, 클라이언트 재연결 비용이 발생하므로 churn은 곧 성능·가용성 저하로 이어진다. 반대로 타임아웃을 너무 길게 잡으면 진짜 장애에서 전환이 늦어져 가용성이 떨어진다. 이 트레이드오프는 네트워크 지연 분포(p99)와 서비스의 RTO 목표를 함께 고려해 결정해야 한다.

실무에서는 몇 가지 보강 기법이 쓰인다. 첫째, 프리보트(pre-vote)로, 후보자가 되기 전에 "내가 출마하면 당선 가능한가"를 먼저 타진해, 네트워크에서 격리되었다가 돌아온 노드가 임기 번호만 올려 클러스터를 교란하는 현상을 막는다. 둘째, 리더 스티키니스(leader stickiness)와 우선순위로, 특정 노드를 선호 리더로 지정해 불필요한 교체를 줄이고 지역성을 확보한다. 셋째, 지터(jitter)를 준 무작위 타임아웃으로 스플릿 보트를 줄인다. 넷째, 리더 선출과 별도로 실제 쓰기 경로에 펜싱 토큰 검증을 두어, 선출이 잠깐 흔들려도 데이터 정합성만큼은 지키도록 이중 방어를 구성한다.

또한 최근에는 Kafka의 KRaft처럼 외부 코디네이터(ZooKeeper) 의존을 제거하고 자체 내장 합의로 선출을 통합하는 흐름이 뚜렷하다. 운영 구성요소를 줄여 장애 지점과 운영 복잡도를 낮추려는 것이며, 이는 분산 시스템이 "선출을 외부에 위임"하던 단계에서 "선출을 코어에 내재화"하는 단계로 성숙하고 있음을 보여준다. 클라우드 네이티브 환경에서는 노드가 수시로 교체되므로, 리더 선출은 멤버십 변경(reconfiguration) 중에도 안전해야 하며, Raft의 조인트 합의(joint consensus)처럼 멤버십을 안전하게 바꾸는 절차와 함께 설계해야 한다.

5. 고려사항 및 시사점

기술사 관점에서 리더 선출을 설계·도입할 때는 다음을 종합적으로 고려해야 한다.

  • 안전성 우선 원칙과 소수파 정지: 가용성보다 데이터 정합성이 중요한 시스템에서는 "과반수를 얻지 못하면 쓰기를 멈춘다"는 보수적 설계가 원칙이다. 과반수 확보를 위해 노드 수는 3·5·7처럼 홀수로 구성하고, 두 데이터센터 분할 시 동점을 피하도록 세 번째 가용영역에 투표 노드(또는 witness/arbiter)를 배치하는 쿼럼 설계를 병행한다.
  • 펜싱과 멱등성으로 다중 방어: 선출 로직만 믿지 말고, 쓰기 경로에 펜싱 토큰 검증과 요청 멱등성을 함께 두어, 지연된 과거 리더나 중복 메시지가 데이터를 손상시키지 못하게 한다. 선출은 "틀릴 수 있다"는 전제로 자원 측 방어를 설계하는 것이 핵심이다.
  • 장애 감지 튜닝과 관측성: 하트비트 주기·타임아웃·프리보트를 네트워크 p99 지연과 RTO에 맞춰 조정하고, 리더 교체 횟수·임기 번호 증가 속도·선출 소요 시간을 지표로 수집해 churn을 조기에 탐지한다. 선출 관련 로그·메트릭이 없으면 간헐적 장애의 원인 분석이 사실상 불가능하다.
  • 빌드 대 구매(build vs. buy) 전략: 자체 Raft 구현은 미묘한 버그로 데이터 손실을 유발하기 쉬우므로, 특별한 이유가 없다면 etcd·ZooKeeper·Consul 같은 검증된 코디네이션 서비스나 라이브러리를 재사용하는 것이 타당하다. 선출을 코어에 내장하는 KRaft 흐름과, 외부에 위임하는 Lease 방식의 트레이드오프(운영 단순성 대 결합도)를 조직 역량에 맞춰 선택한다.
  • 멤버십 변경과 확장 전망: 오토스케일링으로 노드가 수시로 바뀌는 환경에서는 안전한 재구성 절차(조인트 합의, 한 번에 한 노드 추가/제거)를 함께 갖춰야 한다. 향후 지리적으로 분산된 멀티리전 시스템에서는 리더의 위치가 지연·규제(데이터 주권)에 영향을 주므로, 리더 선호·지역 고정과 선출을 연계한 설계가 중요해진다.

참고자료


한 줄 요약: 리더 선출은 대등한 노드들 사이에서 쓰기·조정 권한을 가진 단일 리더를 자동으로 뽑고 장애 시 승계하는 메커니즘으로, 과반수 합의(Raft)나 임차권 기반(ZooKeeper·K8s Lease) 선출에 임기 번호와 펜싱 토큰을 결합해 스플릿 브레인을 막는 것이 안전성의 핵심이다.