Raft Consensus Algorithm

개요

Raft Consensus Algorithm은 분산 시스템 환경에서 모든 노드가 동일한 상태를 유지하도록 하고, 일부 노드에 결함이 생기더라도 전체 시스템이 문제없이 동작하도록 만들기 위해 고안된 합의 알고리즘(Consensus Algorithm)의 일종이다.

2014년에 Diego Ongaro와 John Ousterhout가 "In Search of an Understandable Consensus Algorithm"이라는 논문을 통해 최초로 발표했으며, 당시 Paxos 등의 같은 목적을 수행하는 다른 알고리즘보다 더 쉽게 이해할 수 있고 구현하기에도 용이한 구조를 목표하여 만들어졌다. 이후 현재는 쿠버네티스(Kubernetes)의 etcd 클러스터, MongoDB의 레플리카 셋(replica set) 등 다양한 영역에 접목되어 활용되고 있다.

동작 원리

Raft Consensus Algorithm이 적용된 분산 시스템에서 모든 노드는 아래의 세 가지 중 하나의 상태를 가진다. 일반적으로 하나의 리더와 나머지 팔로워들로 구성되며, 후보자는 오직 리더가 없거나 무응답 상태일 경우에만 일시적으로 존재한다.

• 리더(Leader) : 클러스터를 대표하는 하나의 노드다. 리더는 클라이언트가 클러스터로 보낸 모든 명령의 수신 및 전파, 그리고 응답을 전담한다. 또한 리더는 자신의 상태 메시지(heartbeat)를 주기적으로 모든 팔로워에게 전파한다.
• 팔로워(Follower) : 리더가 존재하는 한 나머지 노드는 이 상태를 유지한다. 리더로부터 전파된 명령을 처리하는 역할만 담당한다.
• 후보자(Candidate) : 리더가 없는 상황에서 새 리더를 정하기 위해 전환된 팔로워의 상태를 의미한다. 리더로부터 일정 시간 이상 상태 메시지(heartbeat)를 받지 못한 팔로워는 후보자로 전환된다.

Raft Consensus Algorithm은 클러스터 전체에 대한 명령이 오직 리더로부터 팔로워에게 일방향으로 전파되도록 동작한다. 이 동작 원리의 짜임새를 간결하게 축약하면 다음과 같다.

1. 리더는 수신된 명령에 대한 로그(log)를 생성하여 로컬에 저장한 뒤 모든 팔로워에게 복제하여 전달한다. 각 팔로워는 전달받은 로그에 대한 응답을 다시 리더에게 보낸다.
2. 리더가 수신한 정상 응답 수가 클러스터 전체 노드의 과반수에 이르면, 리더는 로그를 통해 전파된 명령을 클러스터의 모든 노드가 동일하게 수행하도록 한 뒤 클라이언트에게 명령 수행 결과를 리턴한다. 한편 리더는 해당 로그를 클러스터 전체 노드가 똑같이 보유할 때까지 로그 재전송을 주기적으로 반복한다.
3. 시스템 문제나 네트워크 이슈로 제때 명령을 처리하지 못한 팔로워가 있더라도, 그 팔로워는 정상 상태로 복구된 뒤 클러스터와의 연결이 재개되면 리더로부터 그동안의 명령 처리 기록이 포함된 로그들을 다시 전달받아 순차적으로 수행한다. 클러스터 전체의 최신화 및 동기화는 이렇게 하여 유지된다.

리더 선출(Leader Election)

Raft Consensus Algorithm에서 리더의 역할은 절대적이다. 이 알고리즘은 과반수의 승인이 필요한 다수결의 원칙을 이용한다. 이를 리더 선출(Leader Election) 작업이라고 한다.

리더 선출(Leader Election)의 과정을 이해하려면 우선 아래 용어들을 알아야 한다.

• 임기(Term) : 정치 선거제에서의 "제1대", "제2대"와 같은 성격의 번호값이다. 이 번호값은 새로운 선거가 시작된 시점부터 그 선거로 선출된 리더가 리더로서 기능하는 동안까지의 시간을 대표한다.
• 선거 타임아웃(Election Timeout) : 팔로워 상태의 노드가 후보자로 변환되기까지 대기하는 시간으로, 일종의 타이머와 같이 기능한다. 이 타임아웃은 모든 팔로워 및 후보자 노드에게 150~300ms 사이의 각기 다른 임의의 값으로 주어진다.
• 하트비트(Heartbeat) : 리더가 다른 모든 팔로워에게 일정 시간 간격으로 반복 전달하는 메시지다. 이 메시지에는 클라이언트의 명령 전파를 위한 로그(log)가 포함되지 않으며, 오직 리더가 자신의 상태를 유지하는 수단으로만 기능한다.

리더 선출(Leader Election)의 과정

1. 클러스터에 리더가 없는 상태에선 모든 노드가 팔로워 상태를 유지하며 각자에게 주어진 선거 타임아웃(Election Timeout)이 될 때까지 대기한다.
2. 선거 타임아웃(Election Timeout)이 가장 먼저 끝난 노드가 후보자로 전환되고, 새로운 선거 임기(Term)가 시작된다. 후보자 노드는 즉시 자신에게 한 표를 준 뒤 다른 노드들에게 투표 요청 메시지를 전송한다.
3. 만약 이 요청 메시지를 수신한 노드가 해당 임기 중에 아직 투표한 적이 없다면, 그 메시지의 발신처인 후보자에게 투표 메시지를 보낸 후 자신의 선거 타임아웃(Election Timeout)을 초기화한다. 이는 현재 투표 과정에 있는 후보자 노드(들) 외에 또 다른 후보자가 출현하지 않도록 하는 장치다.
4. 전체 노드 수의 과반에 해당하는 응답을 얻은 노드는 해당 임기(Term)에 대한 새로운 리더로 선정된다.
5. 이렇게 새로 선출된 리더는 나머지 노드들에게 하트비트(Heartbeat)를 주기적으로 전송한다. 팔로워는 리더로부터 하트비트(Heartbeat)를 수신할 때마다 자신의 선거 타임아웃(Election Timeout)을 다시 초기화하며 팔로워 상태를 유지한다. 리더가 정상적으로 동작하는 한, 하나의 리더와 나머지의 팔로워로 이루어진 클러스터 구성은 계속 유지된다.

만약 리더 노드에 문제가 생긴다면?

자신에게 주어진 선거 타임아웃(Election Timeout) 이내에 리더로부터 어떠한 메시지도 받지 못한 팔로워 노드는 즉시 후보자로 전환된다. 이때 클러스터의 임기(Term) 번호가 1 증가하게 되며, 곧바로 새로운 리더 선출이 시작된다. 이후에 진행되는 과정은 위의 2~5번과 동일하다.

클러스터의 각 노드는 현재의 임기(Term) 번호를 저장해두고, 서로 메시지를 주고받을 때마다 이 번호를 함께 포함시킨다. 문제가 생겼던 이전의 리더 노드가 복구되어 클러스터와 다시 연결되면, 이 노드는 클러스터가 공유하는 임기(Term) 번호를 자신의 번호와 비교하게 된다. 현재 클러스터의 임기(Term) 번호보다 자신의 번호가 낮은 것을 확인한 이전의 리더 노드는 팔로워로 전환된다.

만약 누구도 과반을 얻지 못했다면?

자주 있는 일은 아니지만, 경우에 따라 재선거를 치러야 할 때도 있다. 예를 들어 4개 노드의 클러스터에서 우연히 2개의 후보자가 동시에 나타나서 각 2표씩 얻은 경우를 상상해 볼 수 있다.

이러한 분할 투표(split votes) 현상으로 인해 누구도 과반을 얻지 못한 경우에는 그대로 해당 임기를 종료하고 새 임기와 함께 재선거를 시작한다. 이때 이전 선거처럼 동점자가 다시 나타나지 않도록, Raft Consensus Algorithm은 매 선거가 시작될 때마다 후보자 노드들의 선거 타임아웃(Election Timeout) 값을 랜덤 하게 재조정한다. 이후의 진행 과정은 위의 2~5번과 동일하다.

그러나 만약 클러스터 안에 죽은 노드가 너무 많아서 어떤 노드도 과반의 득표를 얻을 수 없는 상황이라면 리더 선출이 불가능해진다. 클러스터로 들어오는 명령이 오직 리더로부터 팔로워에게 일방향으로 전파되는 알고리즘의 특성상,

리더의 부재는 클러스터 관리 기능 전체를 멈추게 만든다.

참고 문헌

1번 링크를 통해 시각화를 통한 알고리즘의 원리를 익혀가는 것을 추천한다.

1. Raft : Understandable Distributed Consensus
2. The Raft Consensus Algorithm

Paxos보다 쉬운 Raft Consensus. 이해 가능한 합의 알고리즘을 위한 여정 | by scalalang2 | RATE Labs