Raft - leader election

Raft에서는 모든 결정을 leader가 한다. 클라이언트의 모든 요청은 리더를 통해서만 가능하고, 새로운 로그를 추가하는 것도 새로운 노드가 추가되거나 기존의 노드를 지우는 것도 리더를 통해서 결정된다. leader의 명령을 따르는 노드들은 follower라고 하는데 follower들은 leader의 명령을 그대로 따른다. Follower는 leader가 보낸 명령에 따라 자신의 상태를 변경하고, 새로운 클라이언트가 접속하면, 클라이언트에게 어떤 노드가 리더인지 알려준다. Raft에서는 의도적으로 follower가 할 수 있는 일이 별로 없도록 만들었고 덕분에 프로토콜을 단순하게 만들 수 있었다.

Leader인 노드는 일정 주기로 follower들에 heartbeat을 보낸다. follower들은 leader의 heartbeat을 듣고 있다가 일정 시간 동안 heartbeat을 듣지 못하면 leader가 죽었다고 생각하고 자신을 후보로 추천하며 다른 노드들에 자신을 leader로 뽑아달라고 RequestVote 요청을 보낸다. 이렇게 자신을 RequestVote 요청을 받은 노드를 candidate이라고 부른다. RequestVote를 받은 노드는 현재 자신의 상태를 보고 candidate이 더 최신 상태라면 새 leader를 지지하는 응답을 보내고, 그렇지 않으면 거절하는 응답을 보낸다. 반 이상의 노드가 자신을 지지한다고 응답하면 이 candidate은 leader가 된다. RequestVote를 보내고 일정 시간 동안 leader가 되지 못한 candidate은 다시 한번 모든 노드에게 RequestVote를 보낸다. 이때 얼마 만에 다시 RequestVote를 보낼지는 특정 범위 내에서 랜덤하게 결정된다. 랜덤한 timeout을 사용한다는 것은 Raft를 효율적으로 동작하게 하는데 매우 중요하다. 만약 고정된 시간을 사용한다면 모든 후보가 자기 자신에게 투표하라고 주장하며 선거가 끝나지 않을 수 있다. Candidate이 더 최신인지 아닌지는 term과 lastLogIndex를 보고 결정한다.

Term은 leader의 재임 기간이다. Leader가 바뀌면 term이 바뀐다. 하지만 모든 term에 leader가 존재하지는 않는다. Term은 단조 증가하는 숫자로 서버별로 자신의 term을 저장하고 있다. Raft에서 메시지를 보낼 때는 언제나 자신이 생각하는 term을 함께 보내고, 메시지를 받은 노드는 메시지에 들어있는 term과 자신의 term 중 더 큰 값을 자신의 term으로 만든다. 혹은 RequestVote를 보낼 때도 term을 증가시키고 보낸다.

Message에 들어있는 term이 자신의 term보다 크다는 것은 candidate이 자신보다 더 최신의 상태라는 것이다. 따라서 자신의 상태를 바로 follower로 바꾸고 candidate을 지지한다는 응답을 보낸다. 이것은 자신이 leader였을 때도 마찬가지다. 이런 경우 네트워크 등의 문제로 다른 노드가 자신의 heartbeat을 듣지 못했다는 것이고, 이 경우 다른 노드들이 이미 state를 진행했을 수 있기 때문에 새 leader의 상태를 따른다. 반대로 요청의 term이 자신의 term보다 낮다면, 이 요청은 그냥 무시하면 된다.

자신과 같은 term의 RequestVote 메시지가 메시지에 있는 lastLogIndex를 본다. lastLogIndex가 자신의 log index보다 작다면 이 candidate은 지지하지 않는다. 이는 partition 상황에서도 consistency를 유지하기 위함이다. 이는 다음에 log replication을 설명하며 자세히 설명하도록 하겠다.