Raft 합의 알고리즘
Raft 논문을 선택한 이유
작년에 참여한 카프카 소모임에서 zookeeper 가 사라지고 kraft 가 그 자리를 대신할 것이라는 말을 들은적이 있다. 카프카도 kraft도 모르던 시절이라 kraft 가 뭐길래 이를 대체할 수 있는지 막연한 궁금증만 가졌다. 시간이 좀 더 흘러 분산 시스템을 공부하면서 raft 를 알게 됐고, 어렴풋이 기억하던 kraft 의 근간이 되는 이론이란 것도 알게 됐다. 뿐만 아니라 쿠버네티스 클러스터 구축에 필요한 etcd 의 근간 역시 raft 라는 걸 알게 돼면서, raft 를 제대로 배워보고자 논문을 선택하게 됐다.
Raft 가 떠오를 수 밖에 없던 배경
Raft 는 단순히 말하면 복제된 로그를 관리하기 위한 알고리즘이다. 복제된 로그는 분산시스템에서 각각의 개별 노드에 저장되는데, 이 때 로그를 안전하고 일관성 있는 방향으로 복제하기 위한 절차를 합의 알고리즘이라 부른다. 즉 Raft 는 합의 알고리즘을 구현하기 위한 개념 정도로 이해할 수 있다.
Raft 를 소개하는 논문은 제목부터 이해할 수 있는(Understandable) 합의 알고리즘에 포커스를 둔다. 이전의 합의 알고리즘은 어땠길래 Understandable 이란 워딩까지 사용하며 Raft 를 소개하는 걸까? Raft 이전의 널리 알려진 합의 알고리즘은 Lesile Lamport(83) 가 고안한 Paxos Protocol 으로, 논문에선 당시 스탠포드 대학의 학생들도 이를 이해하는데 1년이 넘는 시간이 걸렸다고 소개한다.
이러한 배경 때문에 Raft 는 처음부터 "이해 가능한" 이란 측면에서 중점을 두고 발전됐다. Paxos 만큼 효율적인 알고리즘이지만, Paxos 보다는 더 이해하기 쉬운 알고리즘이기도 한 셈이다.
Replicated State Machine, 복제 상태 머신이란?
합의 알고리즘은 복제 상태 머신 개념에서 출발한다.
복제 상태 머신이란 무엇일까? 복제 상태 머신(Replicated State Machine)은 분산 시스템에서 여러 노드가 동일한 상태를 유지하기 위해 사용 되는 개념으로, 분산된 노드들이 같은 명령을 순서대로 실행하여 동일한 상태를 보장한다. 여기서 언급된 머신은 클러스터의 노드 중 하나, 즉 서버를 의미하며 `같은 명령을 순서대로 실행`한다는 것은 특정 노드의 상태를 변경(x <- 5)하는 명령이 입력될 때, 나머지 다른 노드에서도 명령이 동일하게 실행되는 것을 의미힌다.
이렇게 분산된 노드에서 상태를 동일하게 복제하면 클러스터의 가용성(availability)이 보장된다. 즉 복제 상태 머신은 분산 시스템에서의 다양한 내결함성 문제를 해결하기 위해 사용될 수 있다.
그럼 복제 상태 머신은 분산 시스템의 모든 서버 상태를 어떻게 동일하게 할 수 있을까?
바로 복제 로그를 구성해서 복제 상태 머신을 구현할 수 있다. 복제 로그의 목표는 클러스터에 연결된 모든 노드에 사용자의 명령어를 동일한 순서로 저장하는 것이다. 일관된 로그를 복제하면 각 노드의 상태 머신이 로그의 명령(command)을 순차적으로 실행하여 동일한 상태를 만들 수 있다. 각 상태머신은 결정론적(deterministic) 이므로 같은 상태를 계산하고, 같은 순서의 결과들을 반환한다.
📌 결정론적 (Deterministic) : 결정론적 알고리즘이란 특정 입력(input) 에 대해 특정 결과(output)를 반환하는 의미로, 여러 복제된 상태 머신들이 동일한 복제 로그를 토대로 명령을 실행하면, 분산 노드들은 결국 같은 결과를 반환할 수 있다.
복제 상태 머신은 다음의 속성을 만족해야 한다.
- 안정성 : 네트워크 딜레이, 패킷 손실, 중복 전송 같은 Non-Byzantine 조건에서 결함이 없어야 한다. (Non-Byzantine 조건이란?)
Non-Byzantine 조건이란 장애가 발생할 수 있지만 시스템 구성 요소가 악의적이거나 임의의 행동을 하지 않는 환경을 의미한다. Non-Byzantine 환경의 복제 상태 머신 프로토콜에서는 다음을 가정한다.
1. 충돌 회피 : 노드들은 서로 다른 결정이나 결과를 만들어내지 않는다. 장애가 발생하더라도 임의의 오류없이 동기화된 상태를 유지한다.
2. 일관된 메시지 전달 : 네트워크 통신이 손실되거나 지연될 순 있지만, 메시지가 임의로 변조되진 않는다.
3. 안정성과 라이브니스 보장 : 시스템의 모든 정당한 요청은 응답을 받으며, 시간이 지나면 각 노드가 동일한 상태를 복제한다.
- 가용성 : 클러스터의 서버 중 과반수 이상이 동작할 수 있고 서로 통신이 가능한 상태라면, 몇몇 서버에 대한 장애 허용성을 가진다. 다운된 서버는 일시적인 중단으로 여기며 나중에 복구된다. 예를 들어 클러스터의 5대 서버 중 2대 서버의 장애까지는 견뎌 낼 수 있다.
- 일반적으로 클러스터의 과반수가 단일 RPC 호출에 응답하면 command 를 완료할 수 있다. (여기서 RPC 는 추후에 다루도록)
- 로그 일관성을 유지하기 위해 타이밍에 의존하지 않는다. 타이밍에 의존하면 왜 안될까? 분산 시스템에서 타임 스탬프를 이용해 최신 데이터를 판단하는 경우를 가정해보자.
문제상황
1. 고장난 클럭 케이스 : 노드 A 의 시간이 고장나서 1시간 뒤로 설정되면, 과거의 데이터라고 판단하여 최신성을 보장받지 못할 수 있다.
2. 네트워크 지연 케이스 : 노드 A 의 변경사항이 네트워크 지연으로 인해 나중에 다른 노드에 도착하면, 다른 노드에선 A 의 과거 타임스탬프를 가진 데이터를 무시하거나 충돌 처리에 문제가 발생할 수 있다.
위 같은 이유로 타이밍에 의존하면 정확한 로그 일관성을 유지하기 어려워, 최신 데이터를 식별하기 어렵게 된다.
이해하기 쉬운 합의 알고리즘을 구성하는 요소
Raft 설계의 목표 중 한가지는 기존에 이해하기 어려웠던 Paxos 를 대체하는, 이해하기 쉬운 합의 알고리즘을 만드는 것이었다. 많은 개발자들이 알고리즘을 쉽게 이해함과 동시에 시스템을 구축 시 알고리즘에 대한 직관을 얻을 수 있어야 했다. Raft 설계자들은 2가지 접근으로 알고리즘을 설계했다.
1. Problem Decomposition : Raft 는 '합의'라는 복잡한 문제를 해결하기 위해 그보다 작은 문제로 쪼개서 해결하는 분할/정복을 이용한다. Raft 는 크게 1. 리더 선출 2. 로그 복제 3. 안정성 보장 이라는 3개의 독립적인 문제로 나누어 하나의 합의 알고리즘을 만들기로 한다.
2. Simplify the State Space (상태 공간 단순화) : 시스템이 가질 수 있는 가능한 상태의 수를 줄여 시스템을 더 일관성 있게 만들고 비결정성을 가능한한 제거한다.
Raft 는 합의 라는 복잡한 문제를 해결하기 위해 더 작은 3개의 독립적인 하위 문제로 분리(분할) 할 수 있다.
- 리더 선출 :기존 리더 노드에 장애가 발생하거나 실패할 때 새로운 리더를 선출한다.
- 로그 복제 : 오직 리더만 클라이언트가 요청하는 로그 생성을 허용하여 전체 클러스터에 걸쳐 로그를 복제할 수 있다.
- 안정성 : Raft 의 핵심적인 안정성은 상태 머신으로, 만약 어떤 서버가 특정 로그 항목을 자신의 상태 머신에 적용(commit)했다면 다른 서버는 동일한 로그 인덱스에 다른 명령(command)을 적용할 수 없다.
각각의 노드는 RPC(원격 프로시저 호출)로 서로 통신하며, 합의 알고리즘에서는 2종류의 RPC, RequestVote RPC 와 AppendEntries RPC 를 필요로 한다. RequestVote RPC 는 리더 선출 기간 중 후보자가 호출하는 RPC로 다른 팔로워 노드들에게 자신에게 투표하라는 메시지를 담아 보낸다. AppendEntries RPC 는 리더들이 로그를 다른 노드에 복제하거나, 하트비트 통신을 위해 사용된다.
Raft 에는 총 3가지의 상태 (Leader, Follower, Candidate) 가 존재하며, 각 노드는 한 순간에 하나의 상태만 가질 수 있다. 노드는 내부적으로 임기(term) 를 가지고 있어, 각 임기마다 하나의 리더를 선출하여 해당 임기의 대표성을 가진다. 임기는 매 임기마다 1씩 증가하는(auto-increment) 형태로 구분할 수 있다.
각 임기마다 노드가 가질 수 있는 상태는 아래와 같다.
- 리더, Leader : 클러스터는 하나의 리더와 나머지 팔로워로 구성된다. 오직 리더만이 클라이언트의 모든 요청을 수신하며 자신의 로컬에 로그를 적재한 후 팔로워에게 요청을 전달한다.
- 팔로워, Follower : 팔로워는 클라이언트로부터 받은 요청을 리더에게 리다이렉트 하거나, 리더에게 전달받은 요청만 수신하여 처리하는 역할을 수행한다.
- 후보자, Candidate : 새로운 리더를 선출하기 위해 후보가 된 상태이다. 리더 선출과정에서 여러 후보가 생길 수 있다.
리더 선출
Raft 는 리더 선출을 위해 Heartbeat 메커니즘을 사용한다. 리더는 주기적으로 하트비트를 팔로워 노드에 보내 각 노드간 상태를 유지한다. (하트비트는 로그항목을 포함하지 않은 AppendEntries RPC 로 보낸다.)
클러스터의 노드들은 최초로 부팅될 때 팔로워 상태로 시작한다. 이 때 각 노드마다 랜덤한 타임아웃(election timeout)이 설정돼 있는데, 이 타임아웃 내에 하트비트를 받지 못하면 살아있는 리더가 없다고 판단하여 새로운 리더를 선출하기 위한 선거를 시작한다.
타임아웃을 먼저 초과한 노드(팔로워)는 선거를 시작하기 위해 자신의 현재 임기 상태를 증가시키고 후보자(Candidate) 상태로 전환한다. 해당 후보자는 스스로에게 투표한 후, 클러스터 내 노드들에 병렬적으로 RequestVote RPC를 호출하여 자신을 리더로 투표해달라는 사인을 보낸다.
선거에서 승리하면 (정족수 이상 투표) 해당 후보자는 리더로 전환된다. 하지만 실패하는 경우도 발생하는데, a) 다른 후보자가 먼저 과반수 투표를 받아 리더가 되는 경우나, 리더 선출에서 b) 아무도 승리하지 못한 채 특정 시간이 지난 경우엔 다시 팔로워 상태로 전환한다.
모든 서버들은 동일 임기 내에 선착순으로 오직 하나의 투표에게만 투표한다. (1 노드 1 투표) 그리고 정족수 이상 득표한 후보자만이 리더로 선출되는 규칙은 적어도 하나의 후보자만 특정 임기 내에서 승리할 수 있음을 보장한다.
랜덤 타임아웃
Raft에선 여러 후보자가 발생한 후 투표가 동률로 끝나는 상황을 Split Vote 라 한다. 이 경우 투표는 결렬되고 재투표를 진행해야한다. 이런 케이스 발생을 줄이기 위해 각 서버는 랜덤으로 타임아웃 시간이 설정된다. 특정 후보자가 과반수 표를 얻지 못해 선거가 실패하면, 일정 시간 후 다시 (랜덤한) 타임아웃이 발생하고 새로운 선거가 시작된다. 랜덤 타임아웃 덕분에 선거가 여러 번 반복될수록 동시에 후보가 출마할 확률이 줄어, 결국 한 후보자가 과반수 표를 얻어 리더로 선출될 가능성이 높아진다.
로그 복제
Raft 의 로그는 index(위치 값), 임기 번호, 상태 변경 명령(command) 3가지로 구성된 엔트리의 집합체를 의미한다.
Raft 는 어떻게 로그 일관성을 유지하여 복제 상태 머신을 구성할까?
먼저 클라이언트가 새로운 요청을 리더에게 전송하면, 리더는 이 요청(command)을 자신의 로그에 추가(append)한다. 이후 리더는 AppendEntries RPC 를 모든 노드에 병렬적으로 요청해 해당 항목을 복제하도록 한다. 그 후 과반수 합의 과정을 거치는데, 리더는 클러스터 과반수(정족수)에서 로그가 복제된 것을 확인하면, 자산의 로그 엔트리를 커밋하고 팔로워에게도 변경 사항이 커밋됐음을 보낸다. 그 후 팔로워도 자신의 로그 엔트리를 커밋한다(그전까진 복제만 해둠)
1. 먼저 클라이언트가 새로운 요청을 리더에게 전송하면, 리더는 이 요청(command)을 자신의 로그에 추가(append)한다.
2. 이후 리더는 AppendEntries RPC 를 모든 노드에 병렬적으로 요청해 해당 항목을 복제한다.
3. 그 후 과반수 합의 과정을 거치는데, 리더는 클러스터 과반수(정족수)에서 로그가 복제된 것을 확인하면, 자산의 로그 엔트리를 커밋하고 팔로워에게도 변경 사항이 커밋됐음을 보낸다. 아래 이미지에서 정족수는 2 (= n/2 + 1)이므로 Node2 혹은 Node3 중 하나에만 복제가 성공하면 해당 로그를 커밋할 수 있다.
리더가 전송하는 AppendEntries RPC 는 아래 요소들로 이뤄져있다.
term: 현재 leader의 임기
leaderId : leader id
prevLogIndex : 바로 이전의 log index
prevLogTerm : 바로 이전의 log index에 기록된 임기(term)
entries[] : 저장할 로그 엔트리 (비어있으면 heartbeat용)
leaderCommit : 현재 leader의 commitIndex
AppendEntries 상세 동작 순서를 살펴보면,
1. Follower 의 현재 임기(currentTerm) 보다 리더로 부터 전달받은 term 이 낮으면 (term < currentTerm) return false
2. 전달받은 prevLogIndex 에 해당하는 엔트리가 없으면 return false
ex) 리더의 index 는 100 인데 복사하려는 follower 의 index 가 98인, prevLogIndex(=99)에 해당하는 entry 가 없는 경우
3. 이미 존재하는 엔트리가 새로운 엔트리와 충돌이 발생한 경우(=같은 index 지만 다른 term 일 경우) -> 기존 엔트리 삭제 후 새로운 엔트리 추가
4. 새로 추가된 엔트리의 index 와 리더의 commitIndex 중 더 작은 값을 follwer 의 commitIndex 에 set
글이 생각보다 길어져 2편에서 이어지도록 하겠습니다. 2편에서는 로그의 일관성을 지키기 위해 Raft 프로토콜에서 어떤 식으로 복제가 진행되는지 원리를 자세히 다뤄보겠습니다.