Raft consensus
분산시스템, Raft Algorithm
Raft Algorithm
Raft 알고리즘은 여러 분산 시스템에서 내결함성을 위해 고안된 알고리즘이다.
내결함성이란, 특정 노드에 장애가 발생해도 시스템은 정상적으로 동작하며 이를 복구할 수 있는 능력을 말한다.
Raft 알고리즘, 뗏목 합의 알고리즘이라고도 불리는 이 알고리즘은 어떻게 내결함성을 보장할 수 있을까?
Raft 알고리즘에 대해서 알아보자.
Definition
뗏목 합의 알고리즘(Raft Consensus Algorithm)은 분산 시스템 환경에서 모든 노드가 동일한 상태를 유지하도록 하고,
일부 노드에 결함이 생기더라도 전체 시스템이 문제 없이 동작하도록 만들기 위해 고안된 합의 알고리즘의 일종이다.
이름을 뗏목으로 지은 이유를 찾아보면 뭔가 여러가지 얘기가 있는것 같다.
"로그를 이어서 만든 뗏목" 이라는 설명이 제일 와닿았다.
Principle
Raft 알고리즘이 적용된 분산 시스템에서 모든 노드는 아래의 세 가지 중 하나의 상태를 가진다.
Leader: 클러스터를 대표하는 하나의 노드. 리더는 클라이언트가 클러스터로 보낸 모든 명령의 수신 및 전파, 그리고 응답을 전담한다. 또한 리더는 Heartbeat 을 주기적으로 전파한다 .(ping)
Follwer: 리더를 제외한 나머지 노드는 팔로워이다. 리더로부터 전파된 명령을 처리하는 역할만 담당한다.
Candidate: 리더가 없는 상황(heartbeat 가 끊김)에서 새 리더가 되기 위해 출마한 팔로워의 상태를 의미한다.
일반적으로 하나의 리더와 나머지 팔로워들로 구성되며, 후보자는 오직 리더가 없거나 무응답 상태인 경우에만 일시적으로 존재한다.
Zookeeper, MongoDB Cluster 등 많은 분산 시스템에서 Raft 알고리즘을 사용한다.
Raft 알고리즘에 대해서 깊게 이해한다면 다양한 분산 시스템이 왜 그렇게 디자인 됐는지 이해할 수 있을 것이다.
그림을 보면 flow 가 잘 이해가 될 것이다.
리더는 수신된 명령에 대한 로그를 생성해서 디스크에 저장. 모든 팔로워에게 복제하여 전달한다.
각 팔로워는 전달받은 로그에 대한 응답을 보낸다.
리더가 수신한 응답수가 과반수에 이르면, 리더는 로그를 통해 전파된 명령을 클러스터의 모든 노드가 동일하게 수행하도록 한다음, 클라이언트에게 명령 수행 결과를 리턴한다.
해당 로그를 클러스터 전체 노드가 똑같이 보유할 때까지 로그를 재전송한다.
장애로 제때 명령을 처리하지 못한 팔로워가 있더라도, 해당 팔로워는 정상 상태로 복구된 뒤 그동안의 로그들을 다시 전달받아 순차적으로 수행한다.
당연한 얘기지만, 그동안의 로그들을 다시 전달받는다는 것은 해당 노드가 어떤 로그까지 실행했는지를 알 수 있다는 것을 의미하고, 해당 로그부터 미래의 로그들을 순차적으로 수행한다는 것은 로그에 Sequence 가 있다는 뜻이다.
Leader Election
분산 시스템에서 이 리더는 보통 홀수 개로 선출한다. 경우에 따라 리더가 한 개만 있는 경우도 있고, 아닌 경우도 있다.
Raft 알고리즘에서 리더의 역할은 절대적이다. 이 리더는 어떻게 정해질까? 위에서 합의 알고리즘의 일종이라고 말했는데, 당연히 투표를 통해서 이루어진다.
리더 선출(Leader Election)의 과정을 이해하려면 우선 아래 용어들을 알아야 한다.
임기 (Term): 새로운 선거가 시작된 시점부터 선출된 리더가 활동할 시간
선거 타임아웃(Election Timeout): 팔로워 상태의 노드가 후보자가 되기까지 대기하는 시간이다. 타임아웃은 모든 팔로워 및 후보자 노드에게 각기 다른 임의의 값으로 주어진다.
하트비트(Heartbeat): 위에서 잠깐 나왔듯이 리더가 일정 시간 주기로 팔로워들에게 ping 을 날린다.
리더의 선출 과정은 다음과 같다. 일단 리더의 임기가 끝난 상황을 가정해보자.
모든 노드가 팔로워 상태를 유지하며 선거 타임아웃이 올 때 까지 대기한다.
타임아웃이 가장 먼저 끝난 노드가 후보(Candidate)로 전환되고, 새로운 임기(Term)가 시작된다.
후보자 노드는 즉시 자신에게 투표하고 다른 노드들에게 투표 요청을 한다.
다른 팔로워 노드는 해당 요청을 수신한 시점에 투표한 적이 없다면 후보자 노드에게 투표한다.
또한 자신의 타임아웃을 초기화해서 이미 나온 후보자 노드외에 추가로 계속해서 후보자가 나오지 않도록 한다.
과반의 투표를 얻은 노드는 새로운 리더로 선정된다.
노드마다 타임아웃이 다른 것은 동시에 여러 후보자가 발생하지 않게 하기 위함이다.
자 다음으로 리더 노드에 장애가 발생한 상황을 가정해보자. 임기가 끝나서 리더를 선출해야 하는 경우도 있지만, 장애가 발생했을때도 리더는 선출되어야 한다.
팔로워중 타임아웃에 도달할 때까지 Heartbeat 를 받지 못한 팔로워는 "즉시 후보자로 전환된다".
이 때 클러스터의 임기 번호 (Term) 이 1 증가하게 되고, 곧 바로 새로운 리더 선출을 시작한다.(3-4번)
Reference
Visualization of Raft protocol
Last updated
