2017-12-08

Raft - log replication

 Raft가 가장 중요하게 생각하는 요소는 이해할 수 있는 알고리즘을 만드는 것이다. 이해할 수 있고 구현하기 쉬운 알고리즘이 Raft의 가장 중요한 요소이기 때문에 Raft는 로그를 누적시킬 수는 있지만 지울 수는 없는 append only 정책을 사용한다. Append only 정책을 사용하기 때문에 Raft의 state를 바꾸는 명령은 AppendEntries 밖에 존재하지 않는다. 사실 Raft가 정의하는 필수 RPC(Remote procedure call)은 지난번 글에서 설명한 RequestVote와 이번에 설명할 AppendEntries 뿐이다. leader가 보내는 heartbeat은 빈 entry를 추가하는 AppendEntries 메시지이다.

 Client가 state를 변경하자고 leader에게 요청하면, leader는 새로운 로그를 만든다. 하지만 이 로그는 아직 state를 변경시킨 것은 아니다. Leader는 새 entry를 커밋하라고 follower들에게 AppendEntries 메시지를 보낸다. follower는 AppendEntries 메시지를 받으면 각자의 스토리지에 받은 로그를 커밋하고 leader에게 답변을 보낸다. Leader는 과반의 follower가 로그를 커밋했다는 메시지를 받으면, 자신도 로그를 커밋한다. 이렇게 leader에 log가 커밋된 뒤에야 state가 성공적으로 변경된 것이고, 클라이언트에게 요청이 처리됐다고 응답을 보낸다.

 AppendEntries 메시지는 follower가 가져야 할 로그들을 담고 있다. follower는 각자 저장하고 있는 로그의 상태가 다르기 때문에 follower들에게 보내야 할 로그의 양도 전부 다르다. 이는 leader가 nextIndex라는 이름으로 각 follower에 어떤 로그를 보낼지 저장하고 있다가 메시지를 보낼 때 사용된다. Follower가 할 일은 leader가 보낸 로그를 저장할 수 있는지 보고 leader에게 응답을 보내준다.

 Follower는 AppendEntries에는 새로 추가할 log 이외에도 이미 follower가 저장했을 거라고 생각하는 prevLogIndex와 prevLogTerm을 같이 보낸다. Follower는 해당하는 index의 로그가 prevLogTerm일 경우 이 로그는 저장할 수 있는 로그다. 만약 prevLogIndex에 해당하는 log가 존재하지 않거나, prevLogTerm에 생성된 로그가 아니면 이 로그는 현재 leader가 가지고 있는 로그가 아니므로 유효하지 않다. 이 경우 prevLogIndex를 포함한 그 이후 모든 로그를 지우고 leader에게 저장할 수 없었다고 알린다. 그러면 leader는 전에 보냈던 index보다 작은 index의 로그를 포함하는 새 AppendEntries를 보낸다.

 Log를 저장할 수 있는 경우. 즉, prevLogIndex에 해당하는 로그를 가지고 있고, 이 로그가 prevLogTerm에 생성된 경우. follower는 leader가 보낸 로그를 저장하고 저장했다는 사실을 leader에게 알린다. 이때 follower가 이미 prevLogIndex 이후의 로그를 가지고 있었다면, 이 로그를 전부 지우고 leader가 보낸 로그로 덮어쓴다. 모든 state 관리를 leader에게 맡기고, leader의 state를 그대로 따르기 위해서다.
 Raft의 log replication은 leader가 commit 한 로그는 다음 term이 되어도 롤백 되지 않는 것을 보장한다. Term의 변경은 네트워크에 문제가 생겼을 때 발생하므로, 쉽게 말해 Raft는 CAP theorem에서 말하는 CP category에 분류된다. 이에 관해서는 다음 글에서 자세히 설명하도록 하겠다.

댓글 없음:

댓글 쓰기