[강의 정리] Distributed System 6.2: Raft consensus algorithm (..ing..)

# 강의 영상

---

정리

지금까지 정리해왔던 분산 시스템의 논리적 시간, broadcast 등을 살펴 보며 이제, 이러한 개념들을 정리해서 Raft 알고리즘에 대해서 살펴볼 것입니다. 그리고 이 알고리즘은 분산 환경에서 합의를 이루는 과정에 대한 알고리즘 이므로, 꽤 복잡하므로 하나씩 슈도코드를 통해 살펴 보면서 이해해보도록 하겠습니다. 실제로 이 Raft 알고리즘을 항상 기억하고 있어야할 필요는 없지만, 이 알고리즘을 한번쯤 깊게 이해해 보는것도 가치가 있는 일입니다. 이 Raft 알고리즘에 대해서 시각적으로 살펴보기 위한 웹 사이트도 참고해보세요. (http://thesecretlivesofdata.com/raft/) (https://raft.github.io/)

 

이 알고리즘을 이해하기 위해서는 아래 그림을 잘 숙지하고 있어야 합니다. 즉, 하나의 노드는 leader, candidate, follower 중 하나의 상태를 가질 수 있고, 처음 클러스터가 시작하거나 한번 장애가 있는 후 복구된 상태라면 "follower" 상태로 시작합니다. 만약 특정 시간 이상으로 리더에게서 메시지를 받지 못하면, follower 는 leader에게 문제가 생겼다고 판단하고 candidate 로 상태가 변하게 됩니다. 그리고, term 정보를 증가 시키고, 새로운 leader 를 선출하기 위한 "leader election"을 진행합니다. 

 

이제, 슈도코드를 하나씩 살펴보도록 하겠습니다.

처음에 관련 변수들을 초기화 하는 작업이 있는데, 이 때 currentTerm, votedFor, log, commitLength 는 별도의 저장소에서 보관을 하고 있어야 합니다. 이 변수들은 crash 난 이후에도 초기화 되면 안되는 값들 입니다. 그리고 log 변수는 배열로 msg, term 정보를 가지고 있고, 이는 해당 msg 가 해당 term 에 들어왔다 라는 것을 나타냅니다. 그리고 여기서 log 는 zero-based 이기 때문에 첫번째 인덱스의 값이 가장 첫번째값이고, 마지막 인덱스의 값이 가장 마지막에 들어온 값이 됩니다. 그리고 결과적으로 이 로그들을 분산 노드들에 전파 하게 됩니다. 그리고 노드가 리더가 죽었다는 판단을 하게 되면 leader election 단계에 들어가게 됩니다. 이때 currentTerm 을 하나 올리고, currentRole 지금 노드의 상태를 candidate 로 바꾸게 됩니다. 그리고 vote에 대한 정보에 자기 자신의 nodeId 를 설정해 자기 자신에게 투표를 합니다. 그러고, msg 에 VoteRequest 정보와 현재 내 nodeId, currentTerm 정보를 넣고 메시지를 노드들에게 보내게 됩니다. 

 그리고 아래 그림에서는 follower 상태의 노드가 candidate 노드로 부터 VoteRequest 요청을 받았을때 행동하는 알고리즘을 나타냅니다. 가장 먼저 term 을 확인을 합니다. 자신이 받은 (candidate 노드로부터) term 이 내가 지금 현재의 term 보다 높다면 나 자신을 follower 로 설정 후, 현재 term 도 받은 값으로 설정해 둡니다. 이는 이전의 데이터를 가지고 있는 리더로 부터 영향을 받지 않기 위함 입니다. 그리고 내가 가지고 있는 로그의 마지막 term 과 전달 받은 로그의 마지막 term 을 비교하는 과정을 거칩니다. 여기서, candidate 의 데이터가 최신이 아니라는 판단이 된다면 VoteResponse 를 통해 false 응답을 주게 되고, 그렇지 않다면 true 응답으로 하게 됩니다. 

이제 다시 candidate 입장으로 돌아와서 follower 들에게 VoteResponse 를 받았을때의 로직을 살펴봅니다. 우선, 현재 term 보다 낮은 term 으로 들어온 응답은 모두 무시하게 됩니다. (네트워크 지연 등으로 늦을 수 있기 때문에..?) 그리고 반대로 현재 term 보다 높은 term 이 응답으로 들어온다면 이 candidate 는 동작하고 있는 리더 선출 과정을 그만 두고, 본인을 follower 단계로 내립니다. 하지만, term 도 현재와 동일하고 응답도 true 로 왔다면, votesReceived 리스트에 전달받은 node id 를 추가하게 됩니다.  여기서 투표 받은 갯수가 quorum 보다 많아 지면 leader 로 승격됩니다. 그리고, leader 가 됨과 동시에 하는 일은 sentLength와 ackedLength 를 업데이트 해주고, ReplicateLog 함수를 호출하는 일입니다. 이는 follower 들에게 새로운 leader 가 선출되었음을 알리는 역할이기도 합니다. 

 

(...)