리더 선출

리더 선출은 여러 서버 가운데 한 대를 대표로 정하는 일입니다. 나머지 서버는 대표가 정한 것을 따릅니다. 대표가 죽으면 남은 서버들이 새 대표를 뽑습니다. 어떤 순간에도 대표가 둘이 되지 않게 하는 것이 이 일의 핵심입니다.

쉽고 빠른 이해

리더 선출은 서버 여러 대 가운데 「지금 결정은 이 서버가 한다」를 정하는 일입니다. 예를 들어 같은 주문 데이터를 세 서버가 똑같이 한 벌씩 나눠 가진다면, 쓰기 순서는 대표 한 대가 정하고 나머지는 받아 적습니다.

이게 없으면 서버마다 제각각 결정합니다. 같은 예약 작업이 두 번 돕니다. 같은 데이터를 두 서버가 서로 다르게 고치기도 합니다.

어떻게 도나:

1. 대표는 살아 있다는 신호를 주기적으로 보냅니다
2. 신호가 한동안 끊기면 다른 서버가 「내가 대표를 하겠다」고 나섭니다
3. 절반이 넘는 서버가 찬성하면 새 대표가 됩니다

대가가 있습니다. 새 대표가 서기 전까지 쓰기가 잠깐 멈춥니다. 대표 한 대가 모든 결정을 맡으니 그 서버가 바빠집니다. 죽은 줄 알았던 옛 대표가 살아 돌아와 자기가 아직 대표라고 믿는 일도 막아야 합니다. 그래서 잠깐의 멈춤도 못 견디는 시스템은 대표를 두지 않습니다.

상세

이 절은 먼저 대표가 왜 필요한지, 선출이 무엇을 지켜야 하는지를 봅니다. 그다음 대표가 죽었음을 알아채는 법과 대표를 뽑는 방식 둘을 봅니다. 끝으로 네트워크가 갈라질 때 대표가 둘이 되는 사고와 그것을 막는 장치를 짚습니다.

「리더」라는 말은 분산 시스템에서 대표 역할을 맡은 서버를 가리킵니다. 따르는 쪽 서버는 흔히 팔로워라고 부릅니다. 이 편에서는 서버 한 대를 노드라고 부르겠습니다.

비유로 보는 리더 선출

반장이 있는 교실을 떠올려 봅시다. 선생님 전달 사항은 반장 한 명이 받아 반 전체에 알립니다. 반장이 전학을 가면 반은 새 반장을 뽑습니다.

곤란한 것은 반장이 둘인 경우입니다. 한 반장은 「내일 체육복」, 다른 반장은 「내일 교복」이라고 전하면 반이 둘로 갈립니다.

대표를 두는 까닭

여러 노드가 같은 데이터를 나눠 가지면 「어떤 순서로 바꿀까」를 정해야 합니다. 노드마다 따로 정하면 순서가 엇갈립니다. 한 노드가 순서를 정하고 나머지가 따르면 이 문제가 단순해집니다.

작업을 한 번만 돌려야 할 때도 대표가 필요합니다. 매일 자정에 정산을 도는 서버가 세 대 떠 있다고 해 봅시다. 대표 한 대만 정산을 돌리게 하면 같은 정산이 세 번 도는 일이 없습니다.

그런데 대표를 한 대로 고정하면 그 서버가 죽을 때 전체가 멈춥니다. 한 대가 죽으면 전체가 멈추는 부품을 단일 장애점이라고 부릅니다. 리더 선출은 대표를 두면서도 이 약점을 피하려고 대표를 그때그때 다시 뽑습니다.

입력과 출력

리더 선출을 계산 문제로 보면 입력은 노드들과 각 노드를 가리키는 서로 다른 번호입니다. 출력은 노드마다 내리는 판단 하나입니다. 「내가 대표다」 또는 「대표는 저 노드다」입니다.

선출이 올바르려면 두 조건을 지켜야 합니다.

첫 조건은 「나쁜 일이 절대 일어나지 않는다」는 약속이라 안전성이라고 부릅니다. 뒤에서 보듯 실무 방식은 네트워크가 아무리 느려도 이 약속을 늘 지킵니다.

둘째 조건은 「좋은 일이 언젠가 일어난다」는 약속이라 활성이라고 합니다. 실무 방식은 이 약속을 조건부로 지킵니다. 메시지가 늦더라도 그 늦음이 일정 한도 안으로 들어오는 동안에만 대표가 섭니다.

대표가 죽었음을 알아채는 법

선출은 대표가 없다는 것을 알아야 시작됩니다. 대표는 살아 있다는 짧은 신호를 일정한 간격으로 보냅니다. 이 신호를 하트비트라고 부릅니다.

다른 노드는 하트비트가 정해 둔 시간 동안 안 오면 대표가 죽었다고 봅니다. 이 기다리는 시간이 타임아웃입니다. 타임아웃이 끝나면 그 노드가 선출을 시작합니다.

이 판단은 틀릴 수 있습니다. 대표가 살아 있어도 네트워크가 느리거나 대표가 잠깐 멈추면 하트비트가 늦습니다. 타임아웃을 짧게 잡으면 멀쩡한 대표를 자주 갈아치웁니다. 길게 잡으면 진짜로 죽었을 때 새 대표가 늦게 섭니다.

번호가 큰 노드가 이기는 방식

오래된 교과서 방식은 번호를 비교합니다. 살아 있는 노드 가운데 번호가 가장 큰 노드를 대표로 정합니다.

그 가운데 불리(bully) 방식은 이렇게 돕니다. 대표가 죽었다고 본 노드는 자기보다 번호가 큰 노드들에게 선거를 알립니다. 아무도 답하지 않으면 스스로 대표라고 선언합니다. 누군가 답하면 그 노드에게 선출을 넘기고 물러섭니다.

링(ring) 방식은 노드를 원 모양으로 잇고 번호를 한 방향으로 돌립니다. 각 노드는 받은 번호와 자기 번호 가운데 큰 쪽을 다음 노드로 넘깁니다. 자기 번호가 한 바퀴 돌아 돌아오면 그 노드가 가장 큰 번호이므로 대표가 됩니다.

두 방식은 「답이 없는 노드는 죽었다」를 믿고 섭니다. 그래서 네트워크가 갈라져 서로 답을 못 받으면 양쪽에서 각자 가장 큰 번호가 대표가 됩니다. 이 약점 때문에 요즘 데이터를 다루는 시스템은 아래의 과반 투표 방식을 씁니다.

과반 투표로 뽑는 방식

과반 투표 방식은 노드 과반의 표를 얻은 노드만 대표로 인정합니다. 노드가 다섯이면 셋의 표가 있어야 대표가 됩니다.

결정에 필요한 최소 노드 수를 정족수라고 합니다. 이 방식은 과반을 정족수로 씁니다. 정족수를 정해 두면 몇 표가 모여야 결정이 서는지를 노드마다 똑같이 셀 수 있습니다.

과반이 안전성을 지키는 까닭은 과반 두 무리가 반드시 한 노드 이상 겹치기 때문입니다. 한 노드는 한 번의 선거에서 한 표만 던집니다. 겹친 노드는 두 후보 모두에게 표를 줄 수 없습니다. 그래서 같은 선거에서 대표가 둘 나오지 않습니다.

선거를 구별하려고 선거마다 번호를 하나씩 올립니다. 과반 투표 방식을 쓰는 대표적인 알고리즘인 Raft 는 이 번호를 텀이라고 합니다. 노드는 자기가 아는 것보다 큰 텀 번호를 보면 그 번호로 따라 올라갑니다. 작은 텀 번호를 단 메시지는 무시합니다.

한 노드는 셋 가운데 한 상태에 있습니다. 대표를 따르는 팔로워, 표를 모으는 후보, 그리고 대표입니다.

stateDiagram-v2
    팔로워 --> 후보: 하트비트가 타임아웃 동안 안 온다
    후보 --> 리더: 과반의 표를 얻는다
    후보 --> 팔로워: 더 큰 텀의 리더를 만난다
    후보 --> 후보: 표가 갈려 새 텀으로 다시 선거한다
    리더 --> 팔로워: 더 큰 텀 번호를 본다

그림의 흐름을 말로 옮기면 이렇습니다. 팔로워는 하트비트가 끊기면 텀 번호를 하나 올리고 후보가 됩니다. 후보는 과반의 표를 얻으면 리더가 됩니다. 더 큰 텀의 리더를 만나면 팔로워로 돌아갑니다. 두 후보가 표를 나눠 가져 아무도 과반을 못 얻으면, 후보는 텀을 올려 다시 선거합니다(아래 절에서 다시 봅니다).

한 번의 선거가 도는 순서

노드 셋에서 선거 한 번을 따라가 봅니다. 노드 A 가 먼저 타임아웃이 끝나 후보가 됐다고 해 봅시다.

sequenceDiagram
    participant A as 노드 A
    participant B as 노드 B
    participant C as 노드 C
    Note over A: 텀을 올리고 자기에게 한 표
    A->>B: 이 텀에서 나를 뽑아 달라
    A->>C: 이 텀에서 나를 뽑아 달라
    B-->>A: 찬성한다
    Note over A,B: A 자신과 B 로 과반 둘이 모였다
    A->>B: 하트비트
    A->>C: 하트비트

A 는 자기 표와 B 의 표로 과반을 채워 리더가 됩니다. C 의 답은 기다리지 않습니다. 곧바로 하트비트를 보내 다른 노드가 후보로 나서지 않게 합니다.

두 노드가 동시에 후보가 되면 표가 갈려 아무도 과반을 못 얻을 수 있습니다. 그러면 새 텀으로 다시 선거합니다. 같은 일이 되풀이되지 않게 노드마다 타임아웃 길이를 무작위로 조금씩 다르게 잡습니다. 한 노드가 먼저 깨어나 표를 모을 확률이 커집니다.

실무에서 선출은 흔히 합의 알고리즘의 한 부분으로 들어갑니다. 합의는 여러 노드가 한 값에 동의하는 일입니다. Raft 도 선출과 함께 쓰기 순서에 대한 합의를 맡는 알고리즘입니다.

이때 노드마다 받은 쓰기를 순서대로 쌓은 기록이 있습니다. 대표가 보낸 쓰기를 과반의 노드가 받아 적으면 그 쓰기는 확정되어 되돌리지 않습니다. 분단이나 장애로 쓰기를 몇 개 못 받은 노드는 기록이 뒤처집니다.

그래서 합의 알고리즘은 투표에 조건을 하나 더 겁니다. 후보의 기록이 자기 기록보다 뒤처져 있으면 표를 주지 않습니다. 확정된 쓰기를 모르는 노드가 대표가 되어 그 쓰기를 지워 버리는 일을 막으려는 것입니다.

드는 메시지 수

선출 방식은 메시지를 몇 개 주고받는지로 견줍니다. 노드 수를 n 이라고 하겠습니다.

과반 투표 방식의 선거 횟수에 상한이 없는 것은 우연이 아닙니다. 메시지가 얼마나 늦을지 한계를 모르고 노드가 죽을 수도 있는 네트워크를 생각해 봅시다. 여기서는 무작위를 쓰지 않고 정해진 규칙만 따르는 절차가 어떤 경우에도 반드시 끝난다고 보장할 수 없습니다.

그래서 무작위 타임아웃으로 「대개 금방 끝난다」를 노립니다.

대표가 둘이 되는 사고

네트워크 장애로 노드들이 서로 연락이 안 되는 두 무리로 쪼개지는 일을 분단이라고 부릅니다. 노드 다섯 가운데 대표를 포함한 둘이 나머지 셋과 끊겼다고 해 봅시다.

셋인 쪽은 과반을 모을 수 있으니 새 대표를 뽑습니다. 둘인 쪽은 과반을 못 모으니 새 대표를 못 뽑습니다. 여기까지는 대표가 하나입니다.

문제는 옛 대표입니다. 옛 대표는 끊긴 줄 모르고 여전히 자기가 대표라고 믿을 수 있습니다. 이렇게 대표 둘이 동시에 결정하는 상태를 스플릿 브레인이라고 부릅니다.

flowchart TD
    P["네트워크가 셋과 둘로 갈라진다"] --> Q{"옛 대표가 어느 쪽에 있나"}
    Q -->|셋인 쪽| S["대표가 그대로 이어진다"]
    Q -->|둘인 쪽| T["셋인 쪽이 새 대표를 뽑는다"]
    T --> U{"옛 대표가 물러났나<br/>(다음 절의 리스 · 펜싱 토큰)"}
    U -->|아니오| V["대표 둘이 따로 결정한다"]
    U -->|예| W["대표는 하나로 남는다"]

옛 대표가 셋인 쪽에 남았다면 과반을 그대로 모을 수 있으니 대표가 바뀌지 않습니다. 사고는 옛 대표가 둘인 쪽에 갇혔을 때 납니다.

과반 투표 방식은 옛 대표의 쓰기가 과반에게 받아들여지지 않게 해서 데이터를 지킵니다. 옛 대표가 쓰기를 확정하려면 과반의 확인이 필요합니다. 둘인 쪽에서는 그 확인을 못 받습니다.

다만 이것만으로 막히지 않는 일이 둘 있습니다. 옛 대표는 과반에게 묻지 않고 자기 데이터로 읽기에 답할 수 있어서, 셋인 쪽에서 확정된 새 쓰기를 모른 채 오래된 값을 돌려줍니다. 앞에서 든 자정 정산처럼 노드 바깥에 일을 시키는 작업도 과반 확인을 거치지 않아 두 번 돌 수 있습니다. 그래서 아래 두 장치를 더합니다.

옛 대표를 막는 두 장치

첫째는 리스입니다. 리스는 만료 시각이 붙은 권한입니다. 대표는 과반에게서 받은 리스가 살아 있는 동안만 대표로 행동합니다.

리스를 갱신하지 못한 대표는 만료 시각에 스스로 물러납니다. 새 대표는 옛 리스가 만료될 때까지 기다린 뒤에 일을 시작합니다. 그래서 두 대표가 일하는 시간이 겹치지 않습니다.

리스는 노드들의 시계가 거의 같은 빠르기로 간다고 가정합니다. 옛 대표의 시계가 느리게 가면 리스가 끝났는데도 아직 남았다고 믿습니다. 그래서 만료 시각에 여유를 두고 잡습니다.

둘째는 펜싱 토큰입니다. 대표가 바뀔 때마다 커지는 번호를 대표에게 줍니다. 텀 번호를 그대로 쓰기도 합니다. 대표는 데이터를 쓰러 가는 바깥 저장소(데이터베이스 · 파일 저장소 등)에 요청할 때 이 번호를 붙입니다.

저장소는 지금까지 본 가장 큰 번호를 기억합니다. 그보다 작은 번호를 단 요청은 거절합니다. 옛 대표가 뒤늦게 깨어나 요청을 보내도 번호가 작아서 막힙니다. 시계에 기대지 않는다는 점이 리스와 다릅니다.

직접 짜지 않고 빌려 쓴다

선출 절차를 애플리케이션이 직접 짜는 일은 드뭅니다. 틀리기 쉬운 부분이 많기 때문입니다. 대개 합의를 이미 구현한 저장소에 선출을 맡깁니다. 앞 절의 바깥 저장소와는 다른 것으로, 대표를 정하는 일만 맡아 주는 저장소입니다.

흔한 방식은 「이 키가 비어 있으면 내 이름을 쓴다」입니다. 여러 노드가 동시에 시도해도 저장소가 한 노드만 성공시킵니다. 그 키를 리스에 묶으면 대표가 죽을 때 키가 사라지고 다른 노드가 이어받습니다.

etcd 와 ZooKeeper 가 이런 저장소입니다. Kubernetes 는 여러 벌 띄운 제어 컴포넌트 가운데 한 벌만 일하게 할 때 이 방식을 씁니다.

쓰지 않는 경우

대표를 두면 모든 결정이 한 노드를 지나 그 노드가 바빠집니다. 선출이 도는 동안 쓰기도 멈춥니다. 쓰기가 한 곳에 몰리면 안 되거나 멈춤을 견딜 수 없는 시스템은 대표를 두지 않습니다.

그런 시스템은 어느 노드든 쓰기를 받게 합니다. 엇갈린 값은 나중에 맞춥니다. 이 방식을 리더리스 복제라고 부릅니다. 대신 잠깐씩 노드마다 다른 값을 보여 줄 수 있습니다. 이 어긋남을 최종 일관성으로 받아들입니다.

관련 항목

리더 선출을 푸는 알고리즘

Raft · Paxos · Zab · Viewstamped Replication · 불리 알고리즘 · 링 알고리즘 · Chang-Roberts 알고리즘 · HS 알고리즘

리더 선출에 관여하는 역할

리더 · 팔로워 · 후보 · 노드 · 코디네이터 · 레플리카

리더 선출이 기대는 부품과 규칙

정족수 · 과반수 프로토콜 · 텀 · 에포크 · 하트비트 · 타임아웃 · 장애 감지 · 무작위 타임아웃

리더 선출이 지키는 성질

안전성 · 활성 · 합의 · 선형화 가능성 · FLP 불가능성

대표가 둘이 되는 사고와 그 원인

분단 · 스플릿 브레인 · 좀비 리더 · 클럭 드리프트 · GC 멈춤 · 정족수 상실

옛 대표를 막는 장치

리스 · 펜싱 토큰 · 시퀀서 · STONITH · 분산 락

리더 선출을 채택한 저장소와 플랫폼

etcd · ZooKeeper · Consul · Kubernetes · Kafka KRaft · MongoDB · Redis Sentinel

리더를 두는 방식과 두지 않는 방식

싱글 리더 복제 · 멀티 리더 복제 · 리더리스 복제 · 최종 일관성 · 페일오버 · 단일 장애점 · 복제