Quorum의 Raft 합의 알고리즘

Raft Consensus Algorithm

Raft는 이해하기 쉽게 디자인된 합의 알고리즘이라고 한다. fault-tolerance(내결함성)와 Performance(성능) 면에서 우수하여 다수의 노드를 클러스터링하는데 많이 사용한다. 대표적으로 etcd와 Hyperledger Fabric, ZooKeeper, Haddop, 요즘 내가 관심이 많은 Quorum 체인에서도 사용되고 있다. 

Raft는 합의 알고리즘을 3가지 문제를 나눠서 해결한다. 1) 리더 선출 2) 로그 복제 3) 안정성 보장 이 해결방법이 하나의 컨센서스 모듈로 구현된다고 볼 수 있다.

1) Leader Election

모든 노드는 특정 순간에 하나의 상태를 가지게된다. 모두가 임기 마다 3가지 중에 하나의 역할을 가지는데, 이 임기(Term) 마다 하나의 리더를 선출해야한다.

- 리더(Leader) : 클러스터는 하나의 리더와 N-1개의 팔로워로 구성되며 리더는 모든 요청을 수신받아 로그를 보관하고 모든 팔로워들에게 전달한다.

- 팔로워(Follwer) : 팔로워는 클라이언트로부터 받은 요청을 리더에게 재전송하고, 리더의 요청은 다시 수신하여 처리한다.

- 후보(Candidate) : 다음 임기의 리더 후보다.

리더는 주기적으로 heartbeat 메시지를 노드들에게 전파한다. 이 때 노드가 일정 시간동안 리더로부터 메시지를 수신하지 못하면 1) 리더를 새로 선출하는 선거를 진행하거나 2) 본인이 스스로 후보가 되어 자신에게 투표하고 다른 노드들에게 투표 요청 메시지(RequestVote)를 보낸다. 

여기서 말하는 메시지는 RPC 프로토콜로 함수를 요청하는 것을 말한다. 각 임기는 매번 선거로 시작하고, 스스로 후보가 되어 선거하는 경우는 3가지로 볼 수 있다.

1) 과반수의 투표를 받아 당선

2) 다른 노드가 리더가 되는 경우 (이 경우는 본인이 제출한 임기 번호보다 높은 번호로 당선된 리더가 있을 때, 후보에서 팔로워로 상태 변경후 리더로 등록한다)

3) 승자가 없이 투표가 종료되는 경우(모든 노드가 스스로에게 투표하여 투표가 결렬되는 경우)

2) Log Replication

Raft의 로그는 위치 값과 임기 번호, 상태 변경 명령의 세 가지로 구성된 Entry의 집합이다. 동일한 인덱스와 임기 번호가 같으면 같은 명령을 저장해야한다.

3) Safety

팔로워가 리더가 커밋한 메시지를 수신받지 못하면 본인 스스로 리더가 되어 메시지를 덮어버리는 상황이 발생할 수 있다. 이를 막기 위해 여러 방법이 고안되었다.

선거제약 방법은 리더의 커밋을 보장하는 방법을 통해 안정성을 구현한다. 후보 노드가 당선되기 위해서 클러스터 내 다수의 노드에게 연락해야한다. 연락한 노드들의 다수는 커밋된 로그를 반드시 가지고 있어야하는데, 투표 요청은 후보의 로그가 인자값으로 존재한다. 그래서 투표자는 본인의 임기 번호가 더 높거나 로그 인덱스가 더 큰 경우엔 해당 투표 요청을 거부하게 된다. 이로써 모든 당선된 리더는 반드시 커밋된 로그를 가지고 있음을 보장하게 된다.

커밋 규칙은 현재 임기의 메시지가 복제되어야지만 커밋으로 간주하여 안정성을 달성한다. 이전 임기의 메시지가 단순히 과반수 이상의 노드에 복제되어서 발생할 수 있는 문제를 해결할 수 있는데, 커밋은 상태 머신이 어떤 엔트리를 실행할 지 결정하는 값이기 때문에 중요하다.

https://ssup2.github.io/theory_analysis/Raft_Consensus_Algorithm/

https://medium.com/curg/raft-consensus-이해-가능한-합의-알고리즘을-위한-여정-f7ecb9f450ab