분산시스템(Distributed System) - 5(Consensus)

앞선 포스트에서 분산시스템에서 메시지의 순서를 보장하기 위해 FIFO-total-order-broadcast를 이용하였다. 위의 알고리즘을 이용하게 되면 리더에서 순서를 정하고 메시지를 분배해줄 리더의 존재가 필요했고 SPOF의 문제가 생기게 되었다. 이 문제를 해결한다면 Fault-tolerant total order broadcast가 되고 state machine replication에 적용하여 fault-tolerance한 분산시스템을 만들 수 있게 된다. 

 

간단하게 생각하면 replication에서 처럼 리더도 여러개를 두고 하나가 죽는다면 다른 리더를 세우는 방식을 하면 된다. 

그럼 이 리더들의 싱크를 어떻게 맞추고 이중에 어떤 노드를 리더로 세울까?

리더를 선출하는 것을 Consensus라하는데 대표적인 알고리즘 Paxos와 Raft가 있다 Paxos는 교수님들이 모여야 제대로 설명하고 이해를 할 수 있을 정도로 어렵다고 한다. (사실인지는 모름) 이 강의에서도 Raft만 다루기 때문에 이것에 대해서만 정리를 해보자.

 

리더는 일정간격으로 다른 노드들에게 메시지를 보내는데 그 메시지가 오지 않으면(timeout) 다른 노드들 중 하나가 candidate가 되고 다른 노드들에게 메시지를 보낸다.

이 메시지에 대하여 quorum의 노드 (과반 수의 노드)가 그 candidate를 지지한다면 그 노드는 새로운 리더가된다. 이때  여러 리더가 생성된다면 slpit brain이라는 사태가 일어난다 파가 나뉘는 것이다. 그래서 raft는 at any one time이라는 개념을 사용하는데 여기서의 time은 이 알고리즘에서 사용되는 term의 한 주기이다. term은 매번 리더 선출을 시작할 때 증가하는 정수이다. 알고리즘은 term과 majority quorum을 이용하여 한 번의 term에는 하나의 리더만을 가지도록 한다. 리더가 동시에 존재한다면 term이 가장 높은 노드가 진정한 리더이고 나머지 리더는 follower가 된다. 이러한 방식을 가지고 계속 리더를 유지한다.

그리고 리더가 되면 로그를 갱신하고 클라이언트에게 데이터를 받고 follower들에게 메시지를 보내고 quorum노드 만큼답을 받으면 데이터를 commit 한다. 

 

 

이과정을 하나씩 보자. 

 

이 강의에서 다룬 알고리즘의 버전은 시스템에 노드가 추가 또는 제거되는부분에 대해서는 다루지 않는다.

 

http://thesecretlivesofdata.com/raft/ (raft 보기 쉽게 이해할수있다.)

1. 노드는 세 가지 상태가 있다. leader, candidate, follower 모든 노드는 처음에는 follower로 시작을 한다. 각 노드는 timeout 시간을 랜덤 하게 가지고 그 시간이 지나는동안 leader또는 candidate에게 메시지를 받지 못하면 candidate가 되고 term을 증가시킨다. 그리고 리더선출(leader election)을 시작한다. (timeout시간을 랜덤하게 가지는 이유는 candidate가 동시에 여럿이 생성되지 않게 하기 위해서 이다.) 이때 다른 leader나 candidate에게 더 높은 term의 메시지를 받게 되면 follower로 돌아간다.

 

1. candidate가 된 노드가 다른 노드의 동의를 얻기 위해 메시지를 보낸다. 메시지에는 term과 log정보를 포함해서 보낸다. 받은 follower노드는 자신이 가진 log정보과 term을 비교하여 candidate가 더 최신이고 해당 term에 다른 노드에 투표를 하지 않았다면 OK를 보낸다. 로그정보 확인으로 최신의 정보를 가지지 않은 노드가 리더가 되는 것을 방지할 수 있다.

 

1. quorum의 노드에게 OK를 받으면 candidate는 leader가 되고 새로운 leader의 정보를 follower들에게 보낸다. 그리고 follower노드들의 로그 상태를 업데이트하고 follower들에게 받은 ackedLength를 0으로 초기화한다. 그리고 주기적으로 heartbeat를 follower들에게 보낸다. 이것은 리더가 살아있다는 것을 주기적으로 알리는 동시에 메시지가 누락되어 최신 로그를 가지지 못하는 follower들의 로그를 최신화해준다.
2. 리더가 선정이 되고 새로운 메시지가 오면 리더에서 처리 후 follwer들에게 보내준다. 이것을 AppendEntries라 한다. 위의 heartbeat도 AppendEntries에 빈 entry를 보내는 것이다. 리더가 메시지를 받아 state를 변경하게 되면 우선 로그에 반영을 한다. 그리고 follower들에게 보내고 응답을 기다리는데 이때 quorum의 노드에게 성공적인 응답을 받으면 commit을 하고 메시지를 보낸 클라이언트에 응답을 보낸다.

1. 각 follower들은 다른 로그 상태를 가진다. 이를 리더에서 저장을 하고 있다가 AppendEntries 할 때 싱크를 맞추어주는데 리더가 가진 상태와 follower가 가 진상태가 다를 수도 있다. AppendEntries에는 commit 한 수 로그 등의 정보가 들어있고 이것들을 매칭 하여 비교 후 해당 값들을 적용할 수 있다면 적용을 한다. 그렇지 않다면 follower의 로그를 AppendEntries의 로그 index이후 삭제한 후에 리더에 거절 메시지를 보낸다.

 

1. 리더는 follower가 보낸 응답을 받는다. 가장 먼저 term을 확인한다. 리더의 역할을 수행하는 건 하나지만 동시에 다수가 될 수도 있다. 이때 term을 확인하여 노드 자신이 현재 시스템의 진짜 리더인지 확인을 하고 자신이 가진 term보다 높다면 follower로 상태를 변경한다. 그리고 term이 현재보다 낮다면 해당 메시지는 무시한다. term이 자신의 값과 같고 ok응답이 왔다면 리더가 관리하고 있는 ackedLength와 follower의 로그 상태를 업데이트한다. false라면 follower의 최신 로그의 index를 낮추고 다시 AppendEntries를 보낸다. 계속하다 보면 언젠가는 둘의 싱크가 맞을 것이다.

 

이런 과정을 통하여 fault-tolerant한 리더를 세울 수 있다.

 

 

 

포스트의 모든 이미지는

https://www.youtube.com/channel/UClB4KPy5LkJj1t3SgYVtMOQ/videos 와 Introduction to Reliable and Secure Distributed Second Edition에 있다.