Algorithm Technical

[Algorithm] Raft Algorithm 소개

시작하며…

“합의”란 무엇일까?

하나의 데이터베이스 서버와 이 서버를 이용하는 하나의 클라이언트로 구성된 시스템이 있다고 가정합시다.

이때, 클라이언트에서 서버로 데이터 업데이트를 요청하면, 단일 데이터베이스 서버 노드이기 때문에 데이터 “합의”가 쉽습니다.
여기서 “합의”란 클라이언트와 서버가 동일한 데이터를 공유하는 상태가 되는 것을 의미합니다.

그렇다면 여러 노드들로 구성된 시스템 내에서 합의는 어떻게 이룰 수 있을까요?
가령 블록체인이나 도커스웜 등의 분산 시스템에서 말이죠.

분산시스템 내에서 합의 도중 발생할 수 있는 문제를 “The Problem of Distributed Consensus”라 합니다.
그리고 오늘 소개 할 Raft 알고리즘은 이러한 Distributed Consensus를 구현하기 위해 존재하는 다양한 “합의 알고리즘” 중 하나입니다.

Raft Algorithm이란?

우선 “Raft”는 우리말로 “뗏목”이라는 뜻입니다.

뗏목은 통나무를 떼로 가지런히 엮은 후 물에 띄워 사람이나 물건을 운반 할 수 있도록 만든 것입니다. 여러 개의 나무가 지탱하고 있기 때문에 일부 나무가 손상되어도 뗏목은 앞으로 나아갈 수 있습니다.

즉, Raft Algorithm은 뗏목처럼 운용 중인 여러 서버들 중 일부에 장애가 발생하더라도 제 기능을 유지하도록 하는 “합의 알고리즘” (혹은 “합의 프로토콜”) 입니다. Raft와 같은 합의 알고리즘이 적용된 시스템은 특정 서버에 장애가 발생하더라도 전체 서비스를 중단하지 않고 서버를 복구 할 수 있습니다.

Consensus Algorithm으로는 가장 유명한 Paxos가 있고, Zookeeper에서 사용하는 Zab이 있습니다. 그리고 Raft는 이해하기 어려운 기존의 알고리즘과 달리 쉽고 구현이 용이하도록 설계되어 있습니다.

지금부터 우리는 Raft Algorithm에 대하여 자세히 알아봅시다.

Leader Election(리더 선출)

기본적으로 Raft 알고리즘이 적용된 시스템의 노드는
“Follower(팔로워), Candidate(후보자), Leader(리더)”
라는 세가지 상태를 가질 수 있습니다.

Raft 알고리즘 기반의 시스템 내 모든 노드는 기본적으로 “팔로워” 상태로 생성됩니다.

즉, 최초엔 리더도 후보자도 없는 상태인 시스템입니다.
시스템엔 합의를 주도할 리더가 필요합니다. 따라서 리더를 뽑습니다. 모든 팔로워 노드들은 리더가 될 수 있습니다. 단 먼저 후보자 노드가 되어야 리더로 선출될 수 있는 자격이 주어집니다. 팔로워가 후보자 상태로 전환이 되면 해당 후보자 노드는 시스템 내 다른 노드들에게 자신을 리더로 뽑아달라는 투표를 요청(Request)하게 됩니다. 그리고 투표를 요청받은 노드들은 반드시 투표 요청을 보낸 후보자에게 투표(Response)을 해야만 합니다.

위 예시 그림을 보실까요?

노드a는 후보자입니다.
후보자가 된 노드 a는 다른 노드들에게 자신을 리더로 뽑아달라는 투표 요청을 합니다.
투표 요청을 받은 노드b와 노드c는 즉각 노드a에게 투표를 합니다. 투표 요청에 대한 응답을 보내는 거죠. 이때, 과반수 이상의 응답(투표)을 받게 되면 해당 후보자는 리더로 선출이 됩니다.

이러한 리더 선출 프로세스를 Leader Election이라고 합니다. 위 예시에서 노드a는 과반수 이상의 투표를 받아 리더가 되었습니다. 이제 이 시스템에서 발생되는 모든 변경사항은 “리더”를 통해서만 합의 할 수 있습니다.

Log Replication (로그 복제)

그렇다면 리더를 통해 어떻게 합의를 진행하는 걸까요? 예시를 바로 보시겠습니다.

어떤 클라이언트(그린노드)가 우리 시스템에 “5”라는 값을 업데이트하라는 요청을 보내왔습니다.

클라이언트의 요청은 리더에게 먼저 수신됩니다.
업데이트 요청을 받은 리더(노드 a)는 우선 자신의 로그 엔트리(Log Entries)에 해당 값을 기록합니다. 로그에 기록된 변경사항은 즉시 커밋되진 않습니다. 변경된 사항을 전체 시스템에 커밋하기 위해 먼저 리더는 자신의 로그를 팔로워들의 노드에 복제합니다. 그리고 리더는 과반수 이상의 팔로워 노드들이 각자의 로그 엔트리에 변경사항을 기록 할 때까지 기다립니다.

과반수 이상의 노드들로부터 각자의 로그 엔트리가 기록이 완료되었다는 응답을 받으면, 리더는 자신의 로그를 커밋하고 값을 “5”로 업데이트 합니다. 그리고 팔로워들에게도 변경 사항이 커밋되었음을 알립니다. 리더의 알림을 받은 팔로워들의 상태값은 모두 “5”로 변경됩니다.

자, 이제 모든 노드가 “5”라는 값으로 업데이트 되었네요.
Raft Algorithm에서의 합의는 이렇듯 Log Replication에 의해 이루어집니다.

Raft Algorithm의 문제점은 없는가?

Raft Algorithm의 합의 프로세스는 사실 이게 전부입니다.

  1. Leader Election : 합의를 리딩 할 리더를 선출한다.
  2. Log Replication : 변경사항 발생 시 리더가 로그 복제를 통해 합의를 진행한다.

참 쉽죠…?
그런데 말입니다. 살짝 궁금증이 생깁니다.

최초에 모든 노드는 팔로워 상태로 시작하는데 후보자 노드가 되는 기준이 뭘까요?
또한, 동시에 여러 후보자가 노드가 등장하여 다른 팔로워 노드들에게 동시에 투표요청을 한다면? 둘 이상의 후보자에게 투표요청을 받은 팔로워는… 어느 후보자에게 투표를 해야할까요…?

이러한 이슈를 해결하고자 Raft는 두 가지 타임아웃 설정을 가지고 있습니다.

The Election Timeout

첫번째로 “The Election Timeout”입니다.
Election timeout은 팔로워가 후보자로 전환되기까지 걸리는 시간을 의미합니다.

무슨말인 즉슨, 기본적으로 팔로워 노드들은 150ms 와 300ms 사이의 랜덤한 수치의 Election Timeout이 설정되어 있습니다. 그리고 팔로워 노드는 자신의 Election timeout이 끝나면, 후보자 상태로 전환됩니다.
시스템 내에 후보자 노드가 등장하면 새로운 선거기간(Election Term)이 시작됩니다. 새 리더를 선출하는 새로운 선거 기간이 된거죠. (Election Term에 대해서는 뒤에서 자세히 다루겠습니다.)
후보자 된 노드는 먼저 Election Term의 값을 +1 증가시킵니다. 그리고 자기 자신에게 투표 후 곧바로 다른 노드들에게 투표 요청 메시지(Request Vote Message)를 보냅니다.

예시와 함께 한번 더 이해해봅시다.

위 그림에서 노드C는 Election Timeout이 먼저 종료되어 후보자가 된 상태입니다.
후보자가 된 노드 C는 Election Term을 1로 업데이트한 후, 자기 자신에게 먼저 투표(Vote Count : 1)를 합니다. 이후 즉시 다른 팔로워들에게 투표 요청 메시지(Request Vote Message)를 보냅니다.

만약, 투표 요청 메시지를 수신받은 팔로워 노드가 현재 선거 기간 내에 투표 한 적이 없다면 곧바로 투표 요청을 한 후보자에게 응답(Vote)을 보냅니다.
위 그림에서 노드A와 B는 현재 선거기간 동안엔 다른 후보자에게 투표한적이 없었기에 노드C에게 투표를 합니다.
그리고 투표를 마친 노드 A와 B는 자신의 Election timeout를 초기화합니다. 팔로워 노드들의 Election Timeout이 다시 시작되죠. (Election Timeout을 초기화 한 이유 역시 뒤에서 이야기할 예정입니다.)
이후 과반수 이상의 투표를 받은 후보자는 리더로 선출됩니다.
노드 C가 리더가 되었습니다~!

Election Term (선거 기간)

여기서 잠깐!! Election Term은 왜 기록하고 업데이트하는 걸까요?
(저만 궁금했을까요…?)
Election Term에 대하여 좀 더 자세히 알아볼 필요가 있습니다.

Election Term : 1 = “제 1대 리더선출 선거”

Election Term은 말 그대로 “선거기간”으로, 현재 진행 중인 리더선출(Leader Election)이 몇번 째 횟차 인지를 나타냅니다. Raft에서 모든 노드는 동일 선거기간 내에 단 한번의 투표만 할 수 있습니다. 모든 노드들은 각자 Election Term을 카운팅하여 기록하고 있으며, 이러한 프로세스를 통해 동일한 Term 내에서의 중복 투표를 막을 수 있습니다.
Election Term이 어떻게 중복투표를 방지하는 것인지는 예제를 통해 차근차근 이해해봅시다.

현재 위 그림에서 노드A와 C는 동시에 후보자 노드가 되었습니다.
따라서, 노드A와 C는 리더가 되기위한 경합을 치뤄야합니다.
이번 리더선출은 4번째 횟차네요. 노드 A와C는 자신이 참여한 선거 기간이 Term이 4번째 Election Term임을 기록한 후, 자기 자신에게 투표를 합니다.
그리고 다른 노드들에게 4번째 리더선출이 시작되었음을 알리며 투표 요청 메시지(Request Vote Message)를 보냅니다.
노드 B와 D는 각각 노드 A와 C의 투표 요청 메시지를 받은 후 자신이 몇번째 선거까지 참여했는지를 확인합니다. 4번째 선거에는 후보자로써로도 팔로워로써도 투표를 행사한 적이 없음을 확인한 두 노드 B와 D는 각각 단 하나의 후보자 노드에게만 응답(Vote)을 보냅니다. 노드 B는 노드 C에게, 노드 D는 노드 A에게 투표를 했네요.
아까의 예제와 마찬가지로 투표를 마친 노드 B와 D는 자신들의 Election Timeout을 초기화 합니다. (알듯말듯한 그 이유… 뒤에서 다뤄질 예정입니다.)
최종 투표 결과는 동률입니다.
4번째 Election Term에서는 과반수 이상의 투표를 획득한 노드가 없네요.
그렇다면….? 5번째 Election Term을 시작하겠네요.
(리더가 뽑힐 때 까지 To be Continued….☆)

The Heartbeat Timeout

자, 이렇게 Raft의 첫번째 타임아웃 설정인 Election Timeout에 대해 알아보았습니다.
그.러.나. 또 다른 의문점이 생겼습니다. (의심과 궁금증이 많은 편 ㅎ)
리더를 선출했는데 왜 팔로워들의 Election Timeout은 초기화 된 걸까요…?

리더 선출 직후, 리더를 제외한 나머지 팔로워들의 Election Timeout은 다시 시작됩니다. 그리고 이들 중 Election Timeout이 끝난 팔로워는 후보자가 될 것이고, 곧바로 새로운 Leader Election 시작되겠죠…

…이렇게 자주 리더를 갈아치워도 되는걸까요…? (동공지진…)

우리에겐 아직 소개 되지 않은 두번째 타임아웃 설정이 있습니다.
리더 선출 이후 팔로워들의 Election Timeout을 제어하면서 동시에 여러가지 이슈들을 해결할 수 있는 “The Heartbeat Timeout” 에 대하여 예시를 통해 알아봅시다.

리더가 된 노드C에겐 더이상 Election Timeout설정이 적용되지 않습니다.
대신 리더에게는 Heartbeat Timeout설정이 적용됩니다. (레퍼런스 글에는 안나와있지만 Heartbeat Timeout이 Election Timeout보다 현저히 짧은 시간입니다.)

리더 노드는 자신의 Heartbeat Timeout에 따라 주기적으로 Append Entries 메시지를 팔로워들에게 전송합니다. 그리고 리더의 Append Entries 메시지를 수신받을 때 마다 팔로워들은 리더에게 수신받았다는 응답을 보내야합니다.
그리고 Append Entries를 수신 받은 팔로워의 Election Timeout은 초기화가 됩니다. (오!?)

Heartbeat Timeout은 심장이 수축과 이완을 반복하며 생명을 연명하듯이…
리더 노드가 본인의 생존(?)을 팔로워 노드들에게 알리고 동시에 팔로워 노드들에게 응답을 받음으로써 각자 잘 살아있는지 서로의 생사를 확인 방법입니다.
합의를 이끌 리더노드의 상태가 정상일 경우 불필요하게 새로운 리더를 선출할 필요가 없습니다. 따라서 팔로워 노드들이 후보자가 되지 못하도록 Election Timeout을 다시 초기화 시키는 것이라고 보시면 됩니다.

마무리

지금까지 Raft Algorithm에 대하여 알아보았습니다.
Leader Election을 통해 선출한 리더를 중심으로 서버에 변경 사항이 발생하였을 때 Log Replication 모든 합의가 이루어집니다. 또한 Heartbeat Timeout설정에 의해 리더와 팔로워 노드들이 주기적으로 Append Entries를 주고 받음으로써 분산된 각 노드들의 장애여부를 지속적으로 탐지할수 있습니다.
이때 리더 노드에 문제 발생 시, Election Timeout에 의하여 재빠르게 새로운 리더선출을 진행하여 시스템을 중단 시키지 않고 계속 운영할 수 있게 합니다.

그럼 Raft Algorithm은 실제 어디에서 어떻게 사용되고 있을까요?
앞에서도 계속 언급해왔지만 분산 시스템 으로 불리우는 다양한 플랫폼에서 활용되고 있습니다.

  1. Docker Swarm
    도커에서는 도커 스웜의 매니저 노드가 스웜의 일관된 상태를 유지하기 위해 Raft Algorithm을 사용합니다.

    $ docker swarm init

    도커 스웜 초기화 명령어 수행 시, 매니저노드 및 Raft DB가생성되고 보안 연결이 자동으로 생성됩니다.

  2. Block Chain
    블록 체인은 대표적인 분산 처리 시스템으로 네트워크에 참여하는 모든 사용자가 모든 거래내역 등의 데이터를 분산하여 저장합니다. 이렇게 저장된 데이터를 블록이라 칭하며 여러 블록들을 시간의 순서대로 묶는 형태를 가져 블록체인이라 불리게 됩니다.(블록체인에 대한 자세한 설명은 구글링으로~)
    따라서, 체인 내 생성되는 모든 블록이 동일한 데이터를 유지하기 위해서 합의 알고리즘이 필요합니다.
    특히 Raft Algorithm은 엔터프라이즈 블록체인의 합의 알고리즘으로 주로 사용되며 대표적으로 “하이퍼레저 패브릭 v2.0”, “AERGO”등 있습니다.

심화 학습

자, 보너스 라운드입니다.
어느날 우리가 Raft Algorithm을 적용하여 분산 시스템 구축을 해야한다고 가정합시다.
이때 분산 시스템 내 노드짝수 개로 구성해야 할까요?
아니면 홀수 개로 구성해야할까요?
예제를 본 뒤, 스스로 해답을 찾아봅시다.

위 예제에서는 노드 B가 리더인 5개의 노드로 구성된 시스템이 운영되고 있습니다.
이때 노드 A와 B, 그리고 노드 C,D,E 사이에 파티션 생겼습니다. 파티션으로 분리가 되었기에 노드 C,D,E는 더이상 리더 노드 B와 Append Entries를 주고 받을 수 없게 되었습니다. Election Timeout이 초기화 되고, 새로운 Election Term이 시작됩니다. 그리고 노드 C가 해당 구역에서 리더가 됩니다.

클라이언트로부터 값 “3”으로 업데이트 요청왔습니다. 각 리더들에게 요청이 전달됩니다.이때, 노드 B가 리더로 있는 군집은 과반수 이상의 동의를 얻지 못했기 때문에 로그를 커밋하지 못합니다. 반면에 노드 C가 리더로 있는 군집은 과반수 이상의 동의를 얻었기 때문에 “3”를 업데이트하고 커밋합니다.
이 후 새로운 클라이언트가 등장하여 추가로 값 “5”를 업데이트 요청합니다. 노드 B는 여전히 3을 커밋하지 못하였기 때문에 로그 복제를 하지 못합니다. 하지만 노드 C는 문제없이 로그 복제를 진행하여 최종적으로 값 “8”로 상태를 커밋합니다.

이후 파티션이 사라집니다.
리더인 노드 B와 노드 C는 Append Entries 각 노드들에게 전송합니다. 이때 노드 B는 자신의 선거기간 이후에 선출된 노드 C의 존재를 노드 C가 보낸 Append Entries를 통해 확인합니다. 그리고, 곧바로 자신의 로그를 롤백 한 후 노드 C의 로그를 복제, 커밋합니다.
이후 노드 C가 최종 리더가 됩니다.

운용 중인 시스템 내 두개 이상의 노드에 이상이 발생한 경우, 클러스터링을 통해 정상 노드들만을 가지고 시스템을 지속적으로 운용할 수 있을 것입니다.
또한 장애가 발생한 노드는 정상 복구된 이후에도 Raft Algorithm의 합의 프로세스를 통해 운용중이던 노드들과 동일한 상태를 가질 수 있게 됩니다.
자, 다시 한번 질문을 떠올려봅시다.
분산 시스템을 구축할 때, 홀수 개의 노드를 생성해야 할까요 아니면 짝수개의 노드를 생성해야 할까요?

답은 이미 위 예제에 나와 있습니다.

Reference

https://raft.github.io/

http://thesecretlivesofdata.com/raft/

https://swalloow.github.io/raft-consensus

https://kin3303.tistory.com/72?category=886709

https://www.blocko.io/blockchain/raft-aergo-private-environment%EB%A5%BC-%EC%9C%84%ED%95%9C-%ED%95%A9%EC%9D%98consensus/?fbclid=IwAR1A3jXD8nX3BTMs_8agyUSUuRi3k2rC69f0Ts5m0CAjl-hsemjMKBMkRuw

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.

%d 블로거가 이것을 좋아합니다: