[RAFT] RAFT consensus algorithm specification

 중간고사가 끝난 이후부터는 RAFT 알고리즘을 maude를 사용해 formal modeling을 진행할 것입니다. 그에 앞서 어떠한 specification을 모델링할지 결정해야 합니다.

 따라서, 이 글에서는 RAFT consensus algorithm에 대해 간단히 소개하고 modeling하고자 하는 specification을 작성하고자 합니다.

 

RAFT consensus algorithm

 RAFT consensus algorithm은 모든 node가 동일한 상태를 유지하며, tolerance를 보장하기 위해 고안된 알고리즘이다. 때문에 일부 node에 문제가 생겨도 전체 system이 잘 동작해야만 한다.

 

 

 

구성

state의 변화. 출처 : In Search of an Understandable Consensus Algorithm

 모든 node는 아래 3가지 상태 중 한 가지를 가진다.

cluster란 여러 subsystem이 연결되어 하나의 system처럼 동작하는 것을 말한다.

• leader : cluster를 대표하는 상태로, client가 cluster로 보낸 모든 메시지의 수신, 전송, 응답을 모두 맡는다. 주기적으로 모든 follower에게 heartbeat를 보낸다.
• follower : leader가 존재할 경우, 모든 node는 이 상태를 가진다. Leader로부터 받은 메시지를 처리한다.
• candidate : leader가 존재하지 않는 경우, 새 leader가 되기 전 상태이다. heartbeat를 받지 못한 follower가 candidate가 된다.

 RAFT consensus algorithm은 cluster의 모든 node가 최신 상태로 동기화하는 방식으로 replicated state machine을 구현한다.

 

 

 

Flow

 아래와 같은 과정을 통해 cluster 전체가 최신 상태로 동기화된다.

1. client가 leader에게 특정 명령을 보낸다.
   • 좀 더 구체적으로는 client가 leader가 아닌 상태라면, 해당 요청을 leader로 redirect한다.
2. leader가 모든 메시지에 대한 log를 생성해 local에 저장한 후, 모든 follower에게 복제해 전달한다. 해당 메시지를 수신한 follower는 leader에게 응답을 보낸다.
3. leader가 수신한 `정상 응답 수`가 전체 노드 개수 중 과반수 이상이라면, log를 통해 cluster의 모든 node가 해당 명령을 수행할 때까지 log를 재전송하며 동시에 client에게 명령 수행 결과를 리턴한다.
   • 때문에 cluster의 모든 node가 같은 명령이 수행되었음을 보장할 수 있다.
4. 문제가 발생해 명령을 처리하지 못한 follower들은 복구된 후 cluster와 연결되었을 때 leader로부터 그간의 log를 모두 받아 다시 수행한다.

 

 

Leader Election Flow

 leader는 다수결을 통해 선출된다. flow는 아래와 같다.

1. 각 node의 election timeout 내에 heartbeat가 도착하지 않았다면 아래 단계를 진행한다.
   • leader는 heartbeat를 모든 node에게 전송한다. 만약 election timeout 내에 leader로부터 heartbeat가 오지 않은 경우 leader에 문제가 생겼다고 간주하고, candidate로 상태를 바꾼다.
2. election timeout이 끝난 follower node들은 candidate로 바뀌고, 새로운 term `newTerm`이 시작된다. 해당 node는 자신에게 한 표를 행사한 후 다른 node들에게 `투표 요청 메시지`를 보낸다.
3. 이 메시지를 받은 node가 `newTerm`에서 투표한 적이 없다면 해당 `투표 요청 메시지`를 보낸 candidate node에게 `투표 응답 메시지`를 보낸 후 자신의 election timeout을 초기화한다.
   • 때문에 현재 투표 중인 candidate 이외에 다른 candidate의 생성을 막을 수 있다.
4. 전체 node 중 과반수에 해당하는 `투표 응답 메시지`를 받은 node는 `newTerm`의 새로운 leader가 된다. 다른 candidate들은 follwer가 된다.

 

 여기서 사용된 용어는 아래와 같은 의미를 가지고 있다.

• term : 새로운 election이 시작된 시점부터 끝날 때 까지의 시간을 식별하는 값이다.
• election timeout : follower node가 candidate node로 될 때까지 기다리는 시간이다. 이 값은 모든 node별로 다른 값이 주어진다. 또한 매 term마다 모든 node들의 election timeout은 무작위로 재조정된다.
• heartbeat : leader가 모든 follower에게 주기적으로 보내는 메시지이다. leader의 상태 확인을 위해서만 사용한다.

 

Leader에 문제가 생긴 경우

 위 flow에 따르면, heartbeat를 수신하지 못한 채 election timeout이 끝난 node들은 candidate가 된다. 이후 `투표 요청 메시지`를 모든 node에게 보낸다고 했다.

 만약 leader가 해당 메시지를 수신한 경우, `투표 요청 메시지` 내에 있는 `term 번호`를 확인하고, 자신이 가지고 있는 것 보다 크다면 follower로 전환한다.

 

과반을 얻지 못한 경우 - 동점자가 만들어진 경우

 과반을 얻지 못한 경우, 해당 term을 즉시 종료하고 새로운 term을 시작함과 동시에 재선거를 시작한다. 동점자가 나타나는 현상을 막기 위해 모든 term에서 모든 node들의 election timeout은 다르게 재조정된다.

 

과반을 얻지 못한 경우 - 과반을 얻을 수 없는 경우

 문제가 발생한 node가 너무 많다면 어떠한 경우에도 과반수 이상의 표를 얻을 수 없다. RAFT consensus algorithm의 경우 client의 모든 명령이 leader를 통해 수신되는데, leader가 만들어질 수 없는 이 경우 cluster 전체가 마비된다.

 

Quorum

 투표에서 leader를 선출하기 위해 과반수를, 즉 n이 cluster의 node 개수일 때 $\frac{n+1}{2}$ 개의 표를 얻어야만 한다. 이 개념은 cluster가 제대로 동작하기 위해 필요하다.

 바로 앞에서 살펴 본 [과반을 얻을 수 없는 경우]가 발생하지 않기 위해서는 최대 $\frac{n-1}{2}$개의 node가 투표를 하지 않아도 된다. 만약 문제가 발생한 node가 $\frac{n-1}{2}$보다 많다면 과반수의 득표를 얻을 수 없기 때문에 cluster의 기능이 멈춘다.

 

 

 

Specification

RAFT의 safety rule

• election safety : 한 term에서 최대 하나의 leader가 선출된다.
• log matching : 두 log의 index와 term이 동일한 경우 해당 index까지의 모든 log entry는 동일하다.
• leader completness : 모든 leader는 commit된 log를 가진다.
• state machine safety : 과반수 이하의 node가 offline이더라도 잘 동작해야 한다.
• join consensus : 새로운 node가 추가되더라도 오직 단 하나의 leader만 존재할 수 있다.

 

 

Log

• log matching을 비교할 수 있어야 한다.
• index, term, 변경 명령 3가지를 가지고 있다.

 

 

각 Node

• state를 가진다. state는 크게 4가지, follower, leader, candidate, offline이 있다.
• 모든 node는 현재 term과 각자의 log를 가지고 있다.
• 모든 node는 현재의 leader node와 다른 모든 node들을 알고 있다.
• 모든 node는 offline으로 변할 수 있다.
• state의 변화는 아래 diagram을 따른다.

state의 변화. 출처 : In Search of an Understandable Consensus Algorithm

Follower

• leader node를 알고 있어야 한다.
• RequestVote를 받은 경우 본인의 log index와 term을 바탕으로 true로 응답한다.
• leader로부터 heartbeat를 받지 못한 경우 candidate로 변화한다.

 

Leader

• 다른 모든 node에게 multicast를 보낼 수 있다.
• 주기적으로 heartbeat 메시지를 multicast한다.

 

Candidate

• 다른 모든 node로 RequestVote 메시지를 multicast할 수 있다.
• leader로부터 AppendEntry 메시지를 받은 경우 follower로 변화한다.
• 다른 node로부터 ResponseVote 메시지를 받을 수 있다.
  • 과반수 이상의 투표를 받은 경우 leader로 변화한다. leader가 된 경우 모든 follower에게 AppendEntry 메시지를 보내며 이를 통해 log matching을 보장한다.
  • 과반수 미만의 투표를 받은 경우 follower로 변화한다.

 

 

Offline

• state가 offline인 node는 그 어떤 message도 보낼 수 없고, 받을 수 없다.
• offline에서 online으로 바뀔 수 있다.

 

 

 

Message

• type이 있다. logUpdaterequest, appendEntryRequest, appendEntryResponse,commit, voteRequest, voteResponse가 있다.
• logUpdateRequest : leader node가 log update를 요청하는 메시지이다.
• appendEntryRequest : follower node에게 보내는 메시지이다.
• appendEntryResponse : follower node가 응답하는 메시지이다.
• commit : log commit message
• voteRequest : 투표를 요청하는 메시지
• voteResponse : 투표 응답 메시지