개요

래프트는 그냥 뗏목을 뜻한다ㅋㅋ
아무튼 래프트 알고리즘은 분산 시스템에서 구성원 간 리더를 선출하고 상태를 동기화하기 위해 고안된 합의 알고리즘이다.
2014년 처음 논문으로 발표됐는데, 제작자 왈 먼저 로그(통나무)를 통해 기존에 사용되던 알고리즘으로부터 탈출하는 개념을 떠올렸고, 이에 뗏목을 뜻하는 Raft라고 명명했다고 한다.^[1]
위키에서는 (Reliable, Replicated, Redundant) And Fault-Tolerant라는 거창한 표현의 약자로 나오는데, 처음 명명될 당시에는 아주 단순한 발상에서 비롯됐다는 거..

기능

분산 환경에서 동기화가 돼야 하는 노드끼리 효율적으로, 장애가 발생해도 서비스가 유지 가능하도록 하는 알고리즘이다.
기본적으로 하나의 리더 노드가 존재하고, 팔로워 노드들은 이 리더로부터 데이터를 받아서 동기화하는 역할만 수행한다.
실제로 모든 요청 처리, 쓰기 작업 등을 담당하는 것은 리더 노드로, 외부 입장에서는 하나의 노드에만 접근이 되니 기본적으로 정합성 이슈가 덜하다.
래프트 알고리즘은 이러한 구조 아래 다음의 기능들을 하기 위한 알고리즘이다.

• 리더를 어떻게 선출할지
• 리더가 죽으면 다음 리더를 어떻게 뽑을지
• 어떻게 리더가 하나임을 보장할지

여기에서 유의할 점이 있는 게, 래프트는 리더를 항상 기반으로 동작한다는 것이다.
외부의 요청을 수행하는 노드는 반드시 하나이며, 이 리더 노드가 다운되는 상황이 있을 때 이것을 유기적으로 복원하기 위한 알고리즘이다.
그러므로 래프트는 고가용성 클러스터를 구성하기 위한 알고리즘이지 다량의 트래픽을 감당하기 위해 로드 밸런싱이나, 요청 분할을 하지 않는다.
오히려 클러스터의 정합성을 유지하기 위해 발생하는 로직으로 인해 전체 성능이 떨어지면 떨어지지, 노드가 늘어난다고 처리 속도가 향상되는 것이 아니란 말이다.

속성

본격적으로 알아보기 이전에, 래프트 알고리즘이 보장하는 속성들이 무엇인지만 정리하겠다.

구체적으로 래프트는 위의 속성들을 항상 만족한다.
잘 모르는 용어는 글을 읽다보면 구체화될 것이다.

• Election Safety - 무조건 한 임기에는 한 리더만이 존재한다.
• Leader Append-Only - 리더는 로그를 추가하기만 하고 지우지 않는다.
• Log Matching - 같은 임기와 같은 인덱스를 가진 로그는 무조건 동일하다.
• Leader Completeness - 무슨 일이 있어도 리더는 커밋 처리된 로그를 전부 가지고 있다.
• State Machine Safety - 저장 장치에는 덮어씌워지는 일이 절대 없다.

기본 개념

본격적으로 동작 흐름을 살펴보기 이전에, 알아야 하는 개념들을 먼저 정리하겠다.

리더 관리

• 하트비트(heartbeat)
  • 리더가 모든 노드에 주기적으로 보내는 메시지로 두 가지 기능을 한다.
  • 리더의 상태에 맞춰 팔로워들을 동기화
  • 현재 클러스터에 리더가 있음을 알림
• 임기(term)
  • 한 세대를 나타내는 번호값
  • 한 리더가 리더로서 기능하고 있는 동안 이 값은 변하지 않는다.
    • 리더가 바뀌게 되면 이 값은 1씩 증가한다.
  • 이 값은 클러스터 내의 모든 통신에 항상 붙어있어 모든 노드는 현재 임기가 몇 세대인지 알 수 있다.
• 선거 타임아웃(election timeout)
  • 팔로워가 후보자가 되기 위해 대기하는 기간
    • 후보자란 리더가 없는 상태에서만 생기는 노드로 리더가 되기 위해 시도하는 노드를 말한다.
  • 모든 노드는 임의의 타임아웃 기간을 가지고 있고, 각자 기간이 지나면 노드는 자신이 리더가 되겠답시고 후보자로 태세 전환을 한다!
  • 팔로워들은 하트비트를 받게 되면 자신의 타임아웃을 다시 초기화한다.

이 정도만 보더라도 어떻게 하나의 노드만 리더가 될 수 있는지 감이 올 것이다.
리더는 주기적으로 하트비트를 보내고, 각 팔로워들은 이것을 받을 때마다 타임아웃을 초기화하기에, 리더가 있는 동안은 누구도 리더가 되려는 시도를 하지 않는다.

로그 커밋

미리 말해두지만, 리더는 팔로워들이 어디까지 로그를 받아갔는지 개별적으로 추적한다.
팔로워 a,b가 있는데 모종의 이유로 a는 최신 정보까지 다 받았지만 b는 못 받아갔을 수도 있다.
이런 것을 반영하도록 설계돼있다는 말이다.

정족수(Quorom)

래프트는 아주 민주적인? 알고리즘으로 리더를 선출할 때, 리더의 로그를 커밋할 때 항상 과반수가 지지하는지를 중시한다.
이때 과반수는 노드 개수 N개일 때 (N+1)/2로 계산되며, 이 값을 정족수라고 부른다.
간단하게 노드 개수가 3개면 정족수는 2, 4개여도 2 이런 식이다.
이 정족수의 응답을 기반으로 동기화하기에 래프트가 합의(Consensus) 알고리즘이라는 것이다.

추가적으로 이것 때문에 래프트 알고리즘을 사용하는 클러스터는 노드의 개수를 홀수로 맞출 것을 권장한다.
이유는 아래에서 다루겠다.

동작 원리

로그 복제(log replication)

기본적으로 래프트가 구성된 환경에서 동기화가 어떤 식으로 이뤄지는지 알아보자.
위에서 말했듯이 래프트는 전체 클러스터의 동기화를 통한 안정성 확보를 중시하기에 무작정 클라의 요청을 수행했다고 이를 커밋하지 않는다.

기본 상황

클라이언트가 클러스터에 어떤 요청을 보냈다고 가정해보자.

• 리더가 요청을 수행한다.
  • 리더는 요청이나 작업 사항을 로그 형태로 지속적으로 저장한다.
  • 이 상태의 로그는 uncommited 상태로, 후보 로그라고도 부른다.
• 하트비트 타이밍에 리더는 모든 팔로워에게 자신의 로그를 보낸다.
• 팔로워는 리더의 로그를 받고 해당 사항들을 후보 상태로 자신에게 저장한 뒤에 ok로 응답한다.
• 정족수 이상의 팔로워로부터 ok를 받은 리더는 비로소 언커밋 로그를 커밋하고 클라에게 처리 응답을 보낸다.
  • 클라는 이때가 돼서야 응답을 받을 수 있다..
• 다음 하트비트 타이밍에 리더는 확정 로그들의 인덱스를 모든 팔로워에게 보낸다.
• 팔로워는 이 인덱스를 받고 이전에 받은 언커밋 로그 중 해당 인덱스의 로그까지 커밋한다.

보다시피 커밋 상태의 로그는 클러스터의 모든 노드가 유지하는 것이 보장된다.

팔로워 응답이 정족수를 못 넘기면?

그러면 팔로워의 응답이 정족수를 넘기지 못한다면?
팔로워 노드가 다운이 되거나, 모종의 이유로 클러스터 내부에서 통신을 못하는 상황이 나올 수 있다.

• 하트비트 타이밍마다 리더는 언커밋된 로그를 계속 전체에 보낸다.
  • 중복된 로그는 자연히 덮어쓰기 되는데, 각 로그가 인덱스를 가지고 있기에 가능하다.
• 다음 하트비트 타이밍에도 정족수를 못 넘겼다.. 그래도 리더는 포기하지 않고 같은 말을 반복한다!
• 이러다 시간이 너무 오래 지나면 클라에게 에러를 반환하기도 하고, 리더의 메모리가 꽉차면 더 이상 로그를 생성하지 않는다던가 하는 대응을 한다.

한참 지나 돌아온 노드가 있다면?

그럼 어쩌다 네트워크가 끊겨서 로그를 못 받다가 겨우 다시 연결된 노드는 어떻게 동기화될까?
가령 로그 인덱스가 10까지 커밋된 상태에서 노드 a가 클러스터에서 나가리됐다 쳐보자.
a 하나 없어진다고 해도 정족수는 만족해서 이후에 로그 인덱스는 15까지 커밋이 됐다.
이때 다시 a가 클러스터에 합류한다면(리더의 트래픽을 받을 수 있게 된다면), a는 15의 인덱스를 받았을 때 실패를 반환한다.
그럼 리더는 a가 15번 로그를 처리할 수 없다는 것을 알고 인덱스를 조금씩 줄여가며 로그를 쭉 보내준다.
10번 인덱스를 받았을 때, 비로소 a 노드는 ok 응답을 보낼 것이고 리더는 그 인덱스 이후의 로그들을 전부 보내준다.
(이를 위해 리더 노드는 팔로워마다 nextIndex, matchIndex를 관리한다.)
이런 식으로 클러스터에 노드가 없어졌다 추가돼도 제대로 동기화되는 것이 보장되는 것이다.

리더 선출(leader election)

정상적인 상황에서 동기화되는 원리는 보았다.
그럼 이 리더를 선출하는 상황은 어떻게 흘러갈까?
원래 리더는 주기적으로 하트비트를 보낸다.
그리고 각 팔로워는 하트비트를 받을 때마다 자신의 선거 타임아웃을 초기화한다.
이를 통해 리더는 항상 하나인 상태로 유지될 수 있다.
그런데 리더가 갑자기 사라진다면?

일반적인 리더 선출

임기 3세대의 리더가 사라졌다.

• 리더의 하트비트가 오지 않고, 팔로워들의 선거 타임아웃은 점차 흘러간다.
• 타임아웃은 노드마다 임의의 값이라 a 팔로워는 먼저 타임아웃이 완료된다.
• a는 팔로워가 아닌, 후보자로서 동작하기 시작한다.
  • 먼저 임기 번호를 1 증가시켜 값을 4로 설정한다.
  • 자신이 리더가 되겠다면서 클러스터 전체에 투표 요청 메시지(이건 로그 아님)를 날린다.
  • 참고로 후보자 노드는 무조건 자신에게 투표한다.
• 투표 요청을 받은 노드는 투표 응답을 보낸다.
  • 이때 이미 후보자가 있기에 자신의 선거 타임아웃을 초기화해 자신이 후보자가 되지 않도록 한다.
  • 여러 투표 요청을 받을 수도 있을 텐데 무조건 첫번째 투표 요청에만 응답한다(1노 1투표 ㅗㅜㅑ).
• 정족수의 투표를 받은 노드는 자신이 리더가 되었음을 선포하기 위해 하트비트를 날리기 시작한다.
• 하트비트를 받으면 리더가 있다는 것이니 모든 노드는 그대로 팔로워로 유지되고, 클러스터가 제 기능을 한다.

이제 임기 4세대의 클러스터로서 클러스터는 기능한다.
추가적으로, 후보자로 동작하는 노드는 자신의 선거 타임아웃 값을 완전히 재설정한다.
나중에 혹시라도 다시 리더를 가리는 상황이 됐을 때 이전과 똑같이 시작하지 않도록 보장하는 것이다.

복수의 후보자가 나온 상황

선거 타임아웃 기간이 제각각 다르고 트래픽이 전달되는 시간도 다르니 동일한 타이밍에 여러 노드가 후보자가 되는 것이 가능하다.
이렇게 후보 경합 상황이 됐다고 해도, 각 노드는 무조건 투표권을 한번만 행사한다.

• 각 후보자는 클러스터에 투표 요청을 뿌린다.
• 다른 후보자의 투표를 받은 후보자는 이미 자신에게 투표했으니 거절한다.
• 후보자가 아닌 노드는 자신에게 가장 먼저 도착한 투표 요청에만 투표를 한다.

이렇게 했을 때 모든 후보자들이 과반수를 넘기지 못한 상황이 나올 수 있다.

• 리더 선출에도 일정 제한 기간이 있으며, 이 제한을 넘긴 것을 인식한 후보자는 다시금 임기 번호를 1 증가키셔 새로운 투표 요청을 보낸다.
• 투표 요청을 날릴 때마다 각 후보자는 자신의 선거 타임아웃 값 자체를 재설정하기에 항상 같은 상황이 나오지 않도록 최선을 다한다.
• 근데도 이 상황이 계속 지속되면 split brain 상태라고 하는데 그냥 클러스터 박살난 거임;

사라졌던 리더가 복귀한다면?

이전에 리더였던 노드가 다시 돌아오는 상황은 어떨까?
여기에도 다양한 케이스가 있긴 한데, 결론적으로 이놈은 다시 리더가 되기 힘들다.

• 기껏 돌아왔는데 하트비트를 받음
  • 임기 세대가 자신보다 높은 걸 확인하고 다른 노드가 리더가 됐구나.. 인지한다.
  • 무말랭이 팔로워 시절로 돌아간다..
• 기껏 돌아왔는데 투표 요청 받음
  • 아무튼 임기 세대는 올라갔구나..
  • 무말랭이 팔로워 시절로 돌아간다..
• 기껏 돌아왔는데 투표 요청이 한 차례 날아가고 아직 새 리더가 선출되지 않음
  • 아직 자신이 리더인냥 하트비트를 보내긴 한다.
  • 그러나 이미 투표를 하고 있는 상황에서 다른 노드들은 임기가 낮은 하트비트를 무시한다.

그럼에도 리더가 다시 복각하는 케이스가 발생할 수는 있다.
클러스터 상황에 따라서는 어쩌다 리더가 복수로 존재하는 케이스가 있을 수 있다.(다른 임기 세대를 가짐)
이럴 때 후보자가 자신의 임기 세대보다 높은 임기를 가진 하트비트를 받는 경우가 생길 수 있는데, 이럴 때는 후보자 노드가 사퇴한다.
결국 현재 높은 임기 세대가 중요한 것이다!

각 대상이 변화할 수 있는 과정들을 담은 그림이다.
보다시피 리더라고 스스로 인지하는 노드더라도 자신보다 높은 임기 세대를 가진 노드를 발견하게 되면 알아서 팔로워가 된다..

이 방식 자체는 다른 노드들이 사라졌다 등장한 상황이라도 비슷하다.
임기 값이 세팅돼있기에, 한번이라도 높은 임기 값을 받은 노드들은 이전 임기의 값을 무시하도록 돼있다.
아무튼 이런 특성 덕분에, 언커밋된 로그를 가지고 있는 리더이더라도 다시 리더가 되는 것은 불가능하며, 이에 따라 언커밋 로그는 손실된다.

데이터 정합성

클러스터 환경에 따라 여러 복잡한 상황이 발생할 수 있다.
맨 위 노드가 8세대 리더라고 치고, 여러 노드가 끊겼다 추가됐다 하는 상황에서 a부터 f까지, 다양한 팔로워 노드 상태를 가질 수 있다..
(참고로 언커밋된 로그가 이렇게 될 수 있다는 것이다.)
f 노드만 따져볼까?
2세대 리더로서 언커밋된 로드를 전파하기도 전에 죽고 금새 되살아나서 3세대 리더로 재등장해 똑같이 언커밋한 로그를 쌓다가 그 이후로 오래 죽어있던 노드는 f 같은 상태가 될 수 있다.
그 동안 클러스터에서는 지지고 볶고 하며 8세대까지 온 상황..
이런 복잡한 상황에서도 최종적으로는 모든 노드가 동기화를 할 수 있도록 최선을 다하고자 하는 게 래프트이다...
현 상황에서 시간이 지나면 점차 리더의 로그에 맞춰 모든 노드가 상태가 업데이트될 것이다.

4번 속성 증명(Leader Completeness)

논문에서 재밌게 보였던 것 하나만 언급하고 글을 마칠까 한다.
리더는 무조건 모든 커밋된 로그를 가지고 있다는 것은 어떻게 증명되는가?
이 속성이 완벽해야 결국 커밋된 로그들을 제대로 동기화하여 모든 노드가 데이터 정합성을 확보한다는 것이 보장된다.

논문에서는 이를 증명하기 위해 귀류법을 사용한다.

T 세대에 리더인 S1이 로그를 커밋했고, 이후에 등장한 U 세대의 리더인 S5가 그 로그를 가지고 있지 않다고 가정해보자.

• S5는 S1이 커밋한 로그가 없는 상태로 과반수의 투표를 받아 리더가 됐다.
• S1이 커밋을 했으니 과반수가 S1의 로그를 복제했다.
• 다시 말해, 최소한 S1의 커밋을 받았으면서 S5에 투표를 한 노드(S3)가 있다는 말이 된다.
• 이런 S3가 있기 위해서는 최소한 U 세대 투표 이전에 T 세대 커밋을 받았어야만 한다.
• 그리고 S3가 투표를 했다는 것은 S5는 최소한 S3보다 더 최신의 로그를 가지고 있다는 것인데, 여기에서 모순이 발생한다.
• S3와 S5의 마지막 로그가 같은 임기 세대라면
  • S5의 로그 인덱스는 S3보다 크거나 같다.
  • 그러나 S3는 S5가 받지 못한 T 세대의 커밋 로그를 가지고 있으니 모순.
• S3와 S5의 마지막 로그가 다른 임기 세대라면
  • S5는 최소한 T세대 이상의 임기 세대여야만 S3로부터 투표를 받을 수 있다.
  • 이것은 S5에 마지막 로그를 넣은 임의의 리더는 T 세대의 커밋을 가지고 있었다는 말이 된다.
  • 3번 속성(같은 세대의 같은 인덱스는 무조건 같은 값)에 의해, S5가는 해당 리더의 커밋을 그대로 가지고 있어야 한다.
  • 이는 처음 가정에 모순이다.

가정이 모순됐기에, 귀류법으로 T 세대 이상의 리더는 반드시 T 세대의 커밋된 로그를 가지고 있음이 증명된다.

이런 식으로 모든 속성이 증명되는데, 꽤나 재밌으니 직접 논문을 읽어보는 것도 괜찮은 것 같다.^[2]

변형 래프트

기본 래프트 알고리즘 이상으로, 실제 소프트웨어들은 여기에 더 발전된 기능과 플로우를 추가하여 구현하곤 한다.
조만간 이쪽 문서로 옮길 듯한데, 일단 Etcd#심화 raft 참고.

관련 문서

참고