Raft 합의 알고리즘 논문 리뷰: etcd·Consul 클러스터가 안 죽는 이유

2014년 6월, 스탠퍼드 대학의 Diego Ongaro와 John Ousterhout은 USENIX ATC에서 논문 한 편을 발표했어요. 제목부터 도발적입니다. “In Search of an Understandable Consensus Algorithm” — 번역하면 “이해하기 쉬운 합의 알고리즘을 찾아서”인데, 논문 저자들 스스로 “우리도 Paxos를 완전히 이해하는 데 거의 1년이 걸렸다”고 고백할 정도로 기존 Paxos가 난해했다는 게 출발점이었어요. 그 결과물이 지금 etcd, Consul, Kubernetes, CockroachDB 내부에서 조용히 돌아가고 있는 Raft입니다. 그렇다면 Raft는 정확히 어떻게 설계됐길래 “이해하기 쉬운 합의”라는 목표를 달성했다고 평가받을까요?

Raft는 어떤 문제를 풀기 위해 나온 알고리즘인가?

Raft는 여러 대의 서버가 동일한 명령 순서를 가진 로그를 복제해 하나의 신뢰할 수 있는 상태 머신처럼 동작하게 만드는 합의 알고리즘이에요. 논문은 이 문제를 “복제 상태 머신(replicated state machine)” 문제로 정의합니다. 클라이언트가 명령을 보내면 클러스터의 리더가 이를 로그에 기록하고, 다른 서버들에 그 로그를 복제시킨 뒤, 각 서버의 상태 머신이 같은 순서로 같은 명령을 실행해 동일한 결과를 내도록 하는 구조예요. Chubby, ZooKeeper 같은 시스템이 이 방식으로 클러스터 리더 선출과 설정 정보 관리를 수행합니다.

문제는 지난 10년 넘게 이 영역을 사실상 독점해온 Paxos가 지나치게 이해하기 어려웠다는 데 있어요. 논문 저자들은 NSDI 2012 참석자들을 대상으로 비공식 설문을 했는데, 노련한 연구자들 사이에서도 Paxos를 편하게 다루는 사람을 거의 찾지 못했다고 밝힙니다. 이유는 Paxos가 단일 결정(single-decree)을 기본 단위로 잡고 이를 로그 전체로 확장하는 구성 규칙이 따로 붙는 2단계 구조라서, 전체를 직관적으로 이해하기가 어렵기 때문이에요. Raft는 여기서 완전히 다른 접근을 택합니다. 문제를 처음부터 리더 선출(leader election), 로그 복제(log replication), 안전성(safety)이라는 세 개의 비교적 독립적인 하위 문제로 쪼개고, 각각을 따로 이해할 수 있게 설계한 거예요. 이 분해(decomposition)가 이 논문 전체를 관통하는 핵심 설계 철학입니다.

리더 선출은 어떻게 동작하나?

Raft의 리더 선출은 하트비트가 끊기면 팔로워가 스스로 후보로 전환해 표를 모으는 방식으로 동작해요. Raft 클러스터의 모든 서버는 리더(leader), 팔로워(follower), 후보자(candidate) 세 상태 중 하나에 있고, 평상시에는 리더 한 대와 나머지 팔로워로 구성됩니다. 시간은 term이라는 논리적 단위로 나뉘는데, 각 term은 정수로 단조 증가하며 선거로 시작해요. 팔로워가 일정 시간(election timeout) 동안 리더로부터 하트비트(AppendEntries RPC)를 받지 못하면 현재 term을 하나 올리고 스스로에게 투표한 뒤 다른 모든 서버에 RequestVote RPC를 보내 후보로 전환합니다.

여기서 흥미로운 설계 선택이 나와요. 논문 저자들은 처음엔 후보끼리 순위를 매겨 우선순위가 높은 쪽이 이기는 랭킹 시스템을 검토했지만, 낮은 순위 서버가 먼저 타임아웃돼도 더 높은 순위 서버가 죽어 있으면 진행이 막히는 등 가용성 관련 미묘한 문제가 반복해서 나타났다고 해요. 결국 election timeout을 150~300ms 구간에서 무작위로 고르는 단순한 방식으로 정리했는데, 이렇게 하면 대개 한 서버만 먼저 타임아웃돼 표를 독점하고, 설령 표가 갈리는 split vote가 나더라도 다음 라운드에서 금방 해소됩니다. 각 서버는 한 term에 한 표만 행사할 수 있고(first-come-first-served), 클러스터 과반수의 표를 받은 후보만 리더가 될 수 있어요. 이 과반수 규칙 덕분에 한 term에서 리더는 최대 한 명만 나올 수 있다는 “Election Safety” 속성이 자연스럽게 보장됩니다.

로그 복제는 어떻게 일관성을 보장하나?

로그 복제는 리더가 클라이언트 명령을 자신의 로그에 먼저 기록한 뒤 AppendEntries RPC로 팔로워들에게 그대로 전파하는 방식으로 이뤄져요. 리더가 선출되면 클라이언트 요청을 받아 자기 로그에 새 항목으로 추가하고, 이를 병렬로 다른 서버에 복제하도록 AppendEntries RPC를 보냅니다. 항목이 클러스터 과반수에 안전하게 복제되면 그 항목은 “커밋(committed)“된 것으로 간주되고, 리더는 그제서야 상태 머신에 반영한 뒤 클라이언트에 결과를 반환해요. 로그는 리더에서 팔로워로만 한 방향으로 흐르고, 리더는 자기 로그의 기존 항목을 절대 덮어쓰거나 지우지 않아요(Leader Append-Only).

이 과정에서 로그 일관성을 지키는 핵심 장치가 Log Matching Property예요. 서로 다른 로그에서 같은 인덱스, 같은 term을 가진 항목이 있다면 그 항목은 같은 명령을 담고 있고, 나아가 그 인덱스까지의 모든 앞선 항목도 완전히 동일하다는 속성입니다. AppendEntries RPC를 보낼 때 리더는 새 항목 바로 앞 항목의 인덱스와 term을 함께 실어 보내고, 팔로워는 자기 로그에 그 항목이 없으면 거절하는 일관성 검사(consistency check)를 수행해요. 리더가 바뀌어 로그가 서로 어긋나 있어도, 리더는 팔로워마다 nextIndex를 추적하며 거절이 반복될 때마다 하나씩 뒤로 물러나 두 로그가 일치하는 지점을 찾고, 그 지점부터 팔로워 로그를 자기 로그로 덮어써 정합성을 맞춥니다. 이렇게 리더가 별도의 특별한 복구 로직 없이 그냥 평소처럼 AppendEntries를 계속 보내는 것만으로 로그가 자동으로 수렴한다는 점이 Raft를 실제로 구현하기 쉽게 만드는 지점이에요.

안전성은 어떻게 지켜지나?

Raft의 안전성은 커밋된 로그 항목을 갖지 못한 서버가 애초에 리더로 뽑히지 못하도록 선거 과정에 제약을 거는 것으로 지켜져요. 이걸 election restriction이라고 부르는데, RequestVote RPC에 후보의 마지막 로그 항목 인덱스와 term을 함께 실어 보내고, 투표자는 자기 로그가 후보 로그보다 더 최신이면 투표를 거부하도록 구현돼 있습니다. 두 로그 중 어느 쪽이 더 최신인지는 마지막 항목의 term을 먼저 비교하고, term이 같으면 로그 길이가 긴 쪽을 최신으로 판단해요. 이 제약 덕분에 후보가 과반수의 표를 얻으려면 그 과반수 중 최소 한 대는 이미 최신 로그를 갖고 있어야 하고, 결과적으로 당선된 리더는 이전 term에서 커밋된 모든 항목을 이미 갖고 있게 됩니다(Leader Completeness Property).

여기에 더해 Raft는 이전 term에서 복제된 항목이라도 그 자체만으로는 절대 커밋으로 간주하지 않고, 반드시 현재 term에서 새 항목이 과반수에 복제된 뒤에야 그 항목과 그 이전 모든 항목을 한꺼번에 간접적으로 커밋 처리하는 보수적인 규칙을 씁니다. 논문은 이 규칙이 없으면 과반수에 복제된 오래된 항목도 이후 리더가 교체되며 덮어써질 수 있는 시나리오를 구체적인 그림으로 보여주는데, 이를 막기 위한 최소한의 안전장치가 바로 이 커밋 규칙이에요. 결국 Election Safety, Leader Append-Only, Log Matching, Leader Completeness라는 네 가지 속성이 사슬처럼 이어져 최종적으로 State Machine Safety(같은 인덱스에는 모든 서버가 항상 같은 명령을 적용한다)를 증명하는 구조입니다. 논문은 이 증명을 TLA+ 명세로도 완전히 정식화해뒀다고 밝혀요.

과반수만 살아있으면 왜 서비스가 계속될까?

Raft 클러스터는 전체 노드 중 과반수만 서로 통신 가능하면 나머지 노드가 죽거나 응답하지 않아도 정상적으로 클라이언트 요청을 처리해요. 논문은 이를 “일반적으로 5대짜리 클러스터는 임의의 2대 장애를 견딘다”고 명시합니다. 5대 중 3대만 살아있으면 그 3대가 과반수를 이루어 리더 선출도, 로그 커밋도 계속 진행할 수 있다는 뜻이에요. N대 클러스터라면 (N-1)/2대까지 장애를 허용하는 셈이라, 노드 수를 홀수로 맞추는 습관이 여기서 나옵니다.

이 가용성이 실제로 얼마나 빨리 회복되는지는 타이밍 요구사항 하나로 요약돼요. 논문은 broadcastTime ≪ electionTimeout ≪ MTBF라는 부등식을 제시하는데, broadcastTime(서버가 클러스터 전체에 RPC를 병렬로 보내고 응답받는 평균 시간)은 보통 0.520ms, electionTimeout은 그보다 한두 자릿수 위인 10500ms, 그리고 서버 한 대의 평균 무장애 시간(MTBF)은 몇 달 단위로 이 요구사항을 넉넉히 만족한다고 밝힙니다. 실험에서는 election timeout을 150~300ms로 설정했을 때 리더 장애 후 재선출까지 걸리는 시간이 중앙값 287ms, 1000회 시행 기준 최악의 경우도 513ms에 그쳤어요. 이 정도면 과반수 노드만 살아있으면 사람이 체감하기 어려운 시간 안에 서비스가 스스로 복구된다는 뜻이에요.

홈랩에서 이 원리가 그냥 이론이 아닌 이유는, Docker Compose로 여러 서비스를 묶어 운영하다 보면 언젠가 단일 노드가 아니라 etcd나 Consul 같은 분산 키-값 저장소를 클러스터로 구성하게 되는 시점이 오기 때문이에요. 이런 시스템 내부는 전부 Raft로 동작하는데, “왜 3대나 5대로 홀수 구성을 권장하는지”, “노드 하나가 죽었는데 왜 서비스가 안 멎는지”, “노드 두 대가 동시에 죽으면 왜 클러스터 전체가 멈추는지”가 전부 이 과반수 규칙 하나로 설명됩니다. 서버 대수를 늘린다고 무조건 안전해지는 게 아니라 “과반수를 이룰 수 있는가”가 핵심이라는 걸 알면, Gitea/Forgejo 같은 셀프호스팅 서비스의 설정 저장소를 이중화할 때도 노드 구성을 훨씬 합리적으로 설계할 수 있어요.

Raft가 정말 Paxos보다 이해하기 쉬운지 사용자 연구로 확인해보면?

결론부터 말하면 “그렇다”예요. 논문 저자들은 스탠퍼드 대학 고급 운영체제 수업과 UC 버클리 분산 컴퓨팅 수업 수강생 43명을 대상으로 실험을 진행했습니다. 참가자를 절반씩 나눠 한쪽은 Raft 강의 영상을 먼저 보고 퀴즈를 푼 뒤 Paxos 순서로, 다른 쪽은 반대 순서로 진행해 학습 순서 효과를 통제했고, Paxos 강의는 오히려 Raft보다 14% 더 길게 만들고 참가자의 35%(15명)는 이미 Paxos 사전 지식이 있었다는 점까지 Paxos 쪽에 유리하게 설계했어요. 그럼에도 60점 만점 기준 Raft 퀴즈 평균 점수는 25.7점, Paxos 퀴즈 평균은 20.8점으로 4.9점 차이가 났고, 95% 신뢰구간에서 실제 점수 차이가 최소 2.5점 이상이라는 게 쌍체 t-검정으로 확인됐습니다. 43명 중 33명이 Paxos보다 Raft 퀴즈에서 더 높은 점수를 받았어요.

퀴즈를 다 푼 뒤 진행한 설문에서도 결과는 비슷했습니다. “실제 시스템에 구현하기 쉬운 쪽”과 “다른 대학원생에게 설명하기 쉬운 쪽” 두 질문 모두에서 41명 중 33명이 Raft를 골랐어요. 논문은 이 결과를 두고 “이해하기 쉬움을 최우선 설계 목표로 삼는 것이 Raft를 설계하는 방식 자체를 바꿨다”고 정리합니다. 실제로 LogCabin이라는 저자들의 참조 구현체는 테스트나 주석을 빼고도 약 2000줄의 C++ 코드로 완성됐고, 논문 발표 당시 이미 25개가 넘는 독립적인 오픈소스 구현체가 나와 있었다고 밝혀요. 지금은 etcd-io/raft, hashicorp/raft 같은 라이브러리가 etcd, Kubernetes, Consul, CockroachDB, TiDB 등 수많은 시스템의 기반이 되어 있습니다.

결론

Raft가 남긴 진짜 성과는 새로운 이론적 돌파구가 아니라, “리더 선출·로그 복제·안전성을 분리하고 상태 공간을 줄인다”는 단순한 원칙만으로 10년 넘게 난공불락이던 Paxos의 자리를 실제 코드 기반에서 대체해버렸다는 점이에요. 도입부에서 던진 질문으로 돌아가면, Raft가 이해하기 쉬운 합의라는 목표를 달성한 방법은 결국 복잡한 문제 하나를 통째로 풀려 하지 않고 세 개의 독립된 하위 문제로 쪼갠 것, 그뿐이었습니다. 홈랩에서 etcd나 Consul 클러스터를 몇 대로 구성할지 고민하고 있다면, 그 답은 이미 이 논문의 과반수 규칙 안에 들어 있어요. Paxos와 Raft를 항목별로 직접 비교하는 내용은 Paxos vs Raft 비교 글에서 이어집니다.

출처

• Diego Ongaro, John Ousterhout, “In Search of an Understandable Consensus Algorithm (Extended Version)”, USENIX Annual Technical Conference (ATC) 2014 — Stanford 공식 PDF
• Raft Consensus Algorithm 공식 사이트
• USENIX ATC 2014 발표 페이지
• etcd-io/raft GitHub, hashicorp/raft GitHub

관련 글

Raft vs Paxos: etcd·Consul·CockroachDB는 왜 Paxos 대신 Raft를 택했나

콘텐츠 정의 청킹(CDC)이란? LBFS 논문으로 보는 중복제거 원리

CRDT 논문 리뷰: 서버 조율 없이 데이터가 수렴하는 원리