[그림 1] Raft Consensus Algorithm Operation
Cloud/Infra 분야에서 필연적으로 알아야 할 알고리즘인 Raft Consensus Algorithm에 대해 알아보자.
이 알고리즘은 매우 중요하다. 다수의 노드를 클러스터링 하는 데에 대부분 이 알고리즘이 쓰인다는 점에서이다.
Container Orchestration하는 Docker Swarm과 kubernetes에서도 이 알고리즘을 이용하여 노드를 관리한다.
Raft Consensus Algorithm은 2개의 Phase로 이루어져 있고, Leader(Master) node의 상태에 따라 Leader Election부터 다시 시작한다.
1. Leader Election (리더 선출)
2. Log Replication (로그 복제 / 나머지 노드에 데이터 반영)
첫 번째 Phase인 Leader Election을 설명하기 전에 반드시 알아야 할 내용에 대해 설명한다.
Clustering을 위해서는 마스터 노드와 마스터 노드에 의해 컨트롤되는 슬레이브 노드가 있어야 한다.
직접 정해주기도 하지만 마스터 노드에 문제가 발생하는 경우, 슬레이브 노드가 마스터 노드가 되어 서비스 요청을 정상적으로 처리해야 한다.
이 때, 필요한 것이 Distributed Consensus이다.
Distributed Consensus (분산 합의)
여러 노드 가운데에서 Leader(Master) 노드를 선출하는 합의 방식이다.
어디에서 활용되는가?
굉장히 많은 분야에서 활용된다.
대표적으로 블록체인이 있고, Hadoop / Message Queue / ZooKeeper / Kafka / Redis 등 다수 노드의 운영이 요구되는 환경에서 쓰인다.
왜 쓰는가?
쉽게 설명하자면, 모든 노드가 하나의 목적을 달성하기 위해 Consensus를 하는 것이라고 생각하면 된다.
(이 사이에 예시를 들어보았으나 부적절해 보여서 일단 지웠다.)
여러 노드가 존재하는 Distributed environment은 아래와 같은 특징을 지닌다.
Concurrency of processes: 모든 작업이 동시성을 띤다; 노드들은 서로의 일을 동시에 진행할 수 있다.
Lack of a global clock: 모든 노드들을 위한 하나의 Clock이 없다; 노드들은 서로 간 스스로 동기화되지 않는다.
Faulty processes: 작업의 오류가 발생할 수 있다; 모든 노드는 오류(고장, 데이터 손실 등)가 발생하지 않을 확률이 0%이다.
Message passing: 메시지를 전달한다; 노드들은 서로 HTTP, RPC 등을 통해 Sync/Async 로 통신한다.
이 4개의 특징을 고려해 최종적으로 노드들이 하나의 input에 대해 모두 동일한 output을 갖도록 하는 것이 Distributed Consensus의 존재 의의이다.
설명이 부족하지만...ㅜㅜ
Distributed Consensus에 대해 이 정도의 이해만 하고, Raft Consensus Algorithm에 대해 이어서 설명한다.
Phase 1: Leader Election
Leader Election은 Elect, Vote, Decide 형태로 진행된다.
[그림 2] Waiting an Election Timeout - Three nodes have a different timeouts to become a candidate of Leader
세 노드가 있다고 가정을 해보자.
이 세 노드는 150ms ~ 300ms 정도의 서로 다른 Timeout을 가지고 있다.
이 Timeout이 끝나는 노드는 자신이 Leader가 되겠음을 투표받기 위해 나머지 노드에게 알리게 된다.
[그림 3] Elect - Node C asks for a vote to the other nodes
Node C가 제일 먼저 Timeout 됐으므로, 아직 Timeout이 끝나지 않은 Node A와 B에게 Vote할 것을 Request한다.
[그림 4] Vote - Node C is waiting for being voted
Node A와 B는 Vote request를 받고 Election timeout을 리셋한다.
그리고 Node C가 Leader node가 되도록 Node A와 B는, Node C에게 Vote를 응답한다.
[그림 5] Decide - Node C has became a leader node
정상 노드의 수 - 1 만큼 Vote response를 받거나 과반수 이상의 Vote Response를 받은 노드 즉, Node C는 Leader node가 된다.
여기까지가 Leader Election 과정이다.
만약, 노드의 개수가 짝수개일 경우 발생 가능한 문제점이 존재한다.
Election timeout이 만료된 2개의 노드(Candidate)가 서로 동일하게 또 다른 2개의 노드로부터 Vote를 요청하는 경우이다.
이 경우 Candidate들은 동일한 Vote 수를 받게 되며, 이를 해결하기 위해 backoff를 가지고 다시 Vote를 요청하게 된다.
네트워크의 상태에 따라 길어야 몇 초 안에 이루어지는 Leader Election 이지만, real-time service의 경우에는 치명적일 수 있다.
이것을 Majority(대부분성; 다수결의 원칙)를 유지하기 위함이라고 이야기한다.
그렇기에, 짝수 개의 노드가 허용되더라도 인프라에 종사하는 사람들은 항상 노드를 홀수 개로 유지할 것을 권장한다.
Phase 2: Log Replication
[그림 6] Completed Log Replication process of Raft Consensus Algorithm
Election 이후 Leader node는 각 node에게 heartbeat를 통해 Append entries를 보내며, 다른 노드가 candidate될 때 까지 계속 heartbeat를 보낸다.
이 heartbeat에는 Client의 요청으로 인해 변경되는 데이터 또한 함께 담겨있어,
다른 node들이 Leader node와 동일한 상태로 동기화되어서 클러스터의 데이터 일관성(Consistency)을 유지하도록 한다.
동기화가 완료되면, Client에게 Response를 한다.
Node C가 아닌 다른 노드가 candidate 되는 조건은 Node C에 fault가 있어서 heartbeat를 보내지 못하거나,
네트워크 문제로 인해 Node A와 B가 heartbeat를 받지 못하는 경우가 있다.
만일 Node A와 B의 Heartbeat timeout이 만료될 때 까지 heartbeat를 받지 못하면, Leader election 과정의 처음부터 다시 시작된다.
제약사항
Raft Consensus Algorithm이 동작하려면, 3개 이상의 node가 필요하다. (Majority의 최소 조건이기 때문)
References
https://www.preethikasireddy.com/post/lets-take-a-crack-at-understanding-distributed-consensus
http://thesecretlivesofdata.com/raft/
https://raft.github.io/raft.pdf