타이머가 모두 같으면 아무도 이기지 못한다

한 줄 요약

합의는 '누가 옳은가' 를 정하는 일이 아니라 '누가 말할 차례인가' 를 정하는 일이고, Raft 는
그것을 임기(term)와 과반 투표라는 두 장치로만 해결한다. 그리고 그 선거가 끝나려면
타이머가 서로 달라야 한다.

왜 이게 필요했나

서버 세 대에 같은 값을 저장한다고 해 보자. 클라이언트가 세 대에 각각 쓰기를 보내면
네트워크 지연 때문에 도착 순서가 달라지고, 세 대의 기록이 어긋난다. 그래서 실무의
답은 언제나 같다 — 쓰기를 받는 곳을 하나로 정하고, 나머지는 그 하나를 따라간다.
문제는 '그 하나' 가 죽었을 때다. 누가 다음 차례인지 아무도 정해 주지 않는 상태에서
남은 서버들끼리 그것을 정해야 한다.

사람이 개입하면 되지 않느냐는 물음이 자연스럽게 나온다. 실제로 오랫동안 그렇게 했고,
지금도 많은 데이터베이스 복제가 승격(promotion)을 사람 손에 맡긴다. 그런데 사람이
개입하는 데는 분 단위가 걸리고, 그 사이에 서비스는 쓰기를 받지 못한다. 더 나쁜 것은
사람도 틀린다는 것이다 — 원래 리더가 사실은 살아 있었는데 네트워크만 끊겨 있었다면,
승격한 순간 쓰기를 받는 곳이 둘이 된다.

Raft 논문(Diego Ongaro, John Ousterhout)은 이 문제를 이해할 수 있게 푸는 것을
목표로 삼았다. 공식 사이트는 Raft 를 "이해하기 쉽도록 설계된 합의 알고리즘이며
내결함성과 성능에서 Paxos 와 동등하다" 고 소개한다
([raft.github.io](https://raft.github.io/)). 논문의 짧은 판은
2014년 USENIX ATC 에서 최우수 논문상을 받았다.

어떻게 동작하나

Raft 의 시간은 임기로 흐른다. 임기는 1씩 올라가기만 하는 정수이고, 임기 하나에
리더는 최대 하나다. 리더가 없으면 임기가 하나 오르고 새 선거가 열린다. 모든 메시지에
보낸 쪽의 임기가 실려 있어서, 두 노드가 만나면 규칙은 단순해진다 — 더 큰 임기를 본
쪽이 자기 임기를 그 값으로 올리고 팔로워로 물러난다. 더 작은 임기의 요청은 거절하되,
내 임기를 그쪽으로 내리지는 않는다.

선거는 세 줄로 끝난다.

1. 리더 소식이 타임아웃만큼 끊기면 → 임기 +1, 후보가 되어 자기에게 한 표2. 나머지에게 투표를 요청 → 받는 쪽은 '한 임기에 한 표' 만 준다3. 과반을 받으면 리더. 과반은 절반 이상이 아니라 절반 초과다

과반이라는 조건이 하는 일은 하나다 — 두 개의 과반은 반드시 겹친다. 5대 중 3대의
집합 두 개를 어떻게 고르든 적어도 한 대는 양쪽에 들어간다. 그 한 대가 한 임기에 한 표만
주므로, 같은 임기에 리더가 둘이 되는 일은 일어날 수 없다. raft.github.io 는 이 성질을
"서버의 어떤 과반이든 살아 있으면 진행한다 — 예를 들어 5대 클러스터는 2대가 죽어도
계속 동작한다" 고 적는다.

남은 것은 타이머다. 세 노드의 타임아웃이 똑같으면 셋이 같은 순간에 후보가 되고,
각자 자기에게 한 표씩 주고 서로에게는 주지 않는다. 아무도 과반에 닿지 못한 채 임기만
올라간다. 그래서 Raft 는 타임아웃을 일정 구간 안에서 무작위로 뽑는다. 먼저 깨어난
하나가 나머지가 깨어나기 전에 표를 모으면 선거가 한 번에 끝난다.

여기서 한 가지를 분명히 해 두는 것이 좋다. 선거는 '누가 더 좋은 노드인가' 를 고르는
일이 아니다. 성능도, 자원도, 최근 부하도 보지 않는다. 보는 것은 두 가지뿐이다 —
먼저 깨어났는가, 그리고 (로그가 생긴 뒤로는) 로그가 뒤처지지 않았는가. 이 단순함이
알고리즘을 이해할 수 있게 만들고, 동시에 '왜 하필 저 노드가 리더가 됐나' 라는 질문에
대한 답을 허무하게 만든다. 답은 대개 '타이머가 먼저 울려서' 다.

리더가 하는 일도 생각보다 적다. 값을 받고, 나머지에게 전달하고, 살아 있다는 신호를
계속 보낸다. 그 신호가 심장박동(heartbeat)이고, 할 말이 없어도 계속 보낸다 — 침묵과
죽음을 구별할 방법이 그것뿐이기 때문이다. 팔로워는 심장박동이 올 때마다 타이머를
처음으로 되돌린다. 그래서 선거가 다시 열리는 조건은 '리더가 죽었을 때' 가 아니라
'심장박동이 타임아웃 안에 닿지 않았을 때' 이고, 이 둘의 차이가 운영의 사고 대부분을
설명한다.

현장에서 만나는 모습

운영에서 이 이야기는 대개 "임기가 계속 오른다" 는 경고로 나타난다. etcd 문서는
리더가 살아 있는데도 심장박동이 제때 닿지 않으면 "쓸데없는 선거(spurious election)"가
일어난다고 적고, 지연이 큰 환경에서는 heartbeat-interval 과 election-timeout 을
조정하라고 안내한다([etcd FAQ](https://etcd.io/docs/v3.5/faq/)). 디스크가 느려져
쓰기가 밀리거나 GC 가 길게 멈추면, 노드는 멀쩡한데 심장박동만 늦어져 선거가 반복된다.
그동안 클러스터는 쓰기를 받지 못한다.

반대 방향의 사고도 있다. 타임아웃을 지나치게 길게 잡으면 진짜로 리더가 죽었을 때
그만큼 오래 멈춰 있는다. 선거 타임아웃은 '얼마나 빨리 알아차릴 것인가' 와 '얼마나
자주 헛되이 놀랄 것인가' 사이의 손잡이이고, 두 방향 모두 장애로 보인다.

다음 실습에서 할 것

포트만 다른 프로세스 세 개를 띄워 선거를 직접 구현한다. HTTP 서버와 타이머 같은
배선은 드리고, 임기 비교·투표·과반 판정 같은 판단하는 함수만 쓴다. 마지막 단계에서는
세 노드의 타임아웃을 똑같이 맞춰 놓고 9초를 지켜본다. 리더는 뽑히지 않고 임기만
올라가는 것을 직접 보게 된다.