1 개요
- Raft, Raft algorithm, Raft consensus algorithm
- 래프트
- Paxos 알고리즘의 대안으로 설계된 합의 알고리즘
- 로직 분리를 통해 Paxos보다 이해하기 쉽게 설계되었고 공식적으로 안전함이 입증되었으며 몇 가지 추가 기능을 제공한다.
- 클러스터에 상태 머신을 배포하는 일반적인 방법을 제공하여 클러스터의 각 노드가 동일한 일련의 상태 전환에 동의하도록 한다.
- 팩소스의 대안으로 설계된 합의 알고리즘
- 래프트는 로직의 분리를 통해 팩소스보다 이해하기 쉽게 설계되었고, 안전성이 입증되었으며 몇 가지 추가 기능을 제공한다.[1]
- 클러스터를 통해 상태 기계를 분배하는 일반화된 방법을 제공하며, 클러스터의 각 노드가 동일한 일련의 상태 전이에 동의하는지 확인한다.
- Go, C++, Java, Scala 등으로 전체 사양이 구현되어 있고 여러 오픈소스 구현체가 있다.[2]
- 래프트(Raft)라는 이름은 "Reliable, Replicated, Redundant, And Fault-Tolerant"에서 유래하였다.
2 기초
래프트는 선출된 리더를 통해 합의를 달성한다. 래프트 클러스터의 서버는 리더(Leader), 추종자(Follower) 중 하나이며, 리더 선출 중엔 후보자(candidate)가 될 수 있다. 리더는 추종자에 대한 로그 복제에 응답 가능해야한다. 리더는 보통 하트비트 메시지를 보내는 것으로 추종자들에게 존재를 알린다. 각 추종자들은 리더의 하트비트에 대해 타임아웃(일반적으로 150 ~ 300 ms)을 가진다. 이 타임아웃은 하트비트 수신에 의해 리셋된다. 시간 안에 하트비트를 받지 못할 경우, 추종자는 후보자로 상태를 바꾸고 리더 선출을 시작한다.[1][3]
2.1 합의 문제에 대한 래프트의 접근법
2.1.1 리더 선출
기존의 리더가 실패하거나 알고리즘이 시작할 때, 새 리더가 선출될 필요가 있다.
이러한 경우 클러스터 내에 새로운 term이 시작된다. term은 새로운 리더 선출이 필요해지는 임의의 주기이다. 각 term은 리더선출과 함께 시작한다. 만약 선출이 성공적으로 끝난다면 term은 리더에 의해 조율된 일반적인 명령과 함께 계속 된다. 선출에 실패한 경우 새 선출과 함께 새로운 term이 시작된다.
리더 선출은 후보자 서버에 의해 시작된다. 서버는 타임아웃 내에 리더로부터 아무런 연락을 받지 못할 경우 작동하는 리더가 없다고 가정하고 후보자가 된다. 후보자는 term 카운터를 중가시켜 새로운 선출을 시작하고 자기 자신을 새로운 리더로 투표하고 다른 서버들에게 투표를 요구하는 메시지를 보낸다. 서버는 선입선출에 기반하여 한 term에 한번만 투표한다. 만약 후보자가 다른 서버들로부터 현재 term 번호보다 더 큰 번호를 가진 메시지를 받을 경우,후보자의 선출은 거절되며 후보자는 후보자는 추종자로 변하고 본격적으로 리더를 인식한다. 만약 후보자가 과반수의 투표를 받으면 후보자는 새 리더가 된다. 두가지 경우가 모두 일어나지 않는다면, 새로운 term이 시작되고 새 선출이 시작된다.
Raft는 분할 투표 문제를 빠르게 해결하기 위해 난수화된 선출 타임아웃을 사용한다. 서버가 동시에 후보가 되지 않기 때문에 분할 투표 확률을 감소시킨다.
하나의 서버가 타임아웃되면 선출되고 리더가 되어 추종자들이 후보자가 되기 전에 다른 서버들에게 하트비트 메시지를 보낸다.
2.1.2 로그 복제
리더는 로그 복제에 대해 응답 가능하다. 리더는 클라이언트의 요청을 수락한다. 각 클라이언트는 명령어 집합이 클러스트 내의 복제된 상태 기계에 의해 실행되는 것을 요청한다. 리더의 로그에 새 엔트리로서 연결된 이후에는, 각 요청은 각 추종자에게 엔트리 확장 메시지로서 전달된다. 추종자를 이용할 수 없는 경우에는, 리더는 로그 엔트리가 모든 추종자에의해 저장될 때까지 엔트리 확장 메시지 전달을 끊임 없이 재시도한다.
리더가 과반수의 추종자에서 엔트리가 복제된 것을 확인하였을 때, 리더는 리더는 자신의 로컬 상태 기계에 엔트리를 반영하고 요청은 'committed'로 간주된다. 이 때는 리더의 로그 안의 모든 이전의 엔트리들 또한 반영한다. 추종자가 커밋된 로그 엔트리를 배우면, 그 엔트리는 추종자의 로컬 상태 기계에 반영된다. 이것은 클러스터의 모든 서버들간의 로그 일관성을 제공하고, 로그 매칭의 안정성 규칙 보장이 존중된다.
리더가 충돌했을 때, 옛 리더로부터의 로그가 클러스터 내에 완벽하게 복제되지 않은 경우 로그는 일관적이지 않을 수 있다. 새 리더는 추종자들에게 자신의 로그를 복제하도록 시켜 비일관성을 해결한다. 이를 위해서 리더는 자신의 로그와 각 추종자들로부터 받은 로그를 비교하고 마지막으로 합의한 엔트리를 찾고 추종자의 로그 속에서 이 엔트리 이후에 발생한 모든 엔트리를 삭제하고 자신의 로그 엔트리들로 교체한다. 이러한 메커니즘은 실패할 수 있는 클러스터 내의 로그 일관성을 복원한다.
2.2 Raft의 안전성 규칙
Raft는 다음과 같은 안정성 규칙을 보장한다.
- 선출 안정성 : 한 term에는 하나의 리더만이 선출될 수 있다.
- 리더 유일 확장 : 리더만이 로그에 새 엔트리를 추가할 수 있다.
- 로그 매칭 : 두 로그의 term과 색인 번호가 같은 엔트리를 가질 경우, 주어진 색인 번호에 대해 모든 엔트리가 같아야한다.
- 리더 완전성 : 로그 엔트리가 주어진 term에 커밋되었을 경우에 그 로그 엔트리는 그 term 내로 리더의 로그에 반영된다.
- 상태 기계 안전성 : 만약 서버가 로그 엔트리의 일부분을 서버의 상태 기계에 반영했다면 같은 로그에 대해 다른 명령을 반영한 다른 서버는 존재하지 않는다.
4가지 규칙은 이전 영역에서 서술된 알고리즘에 의해 보장된다. 상태 머신 안정성은 선출 과정의 제한으로 보장된다.
2.2.1 상태 머신 안전성
이 규칙은 간단한 제한에 의해 보장된다. : 후보자는 후보자의 로그가 모든 커밋된 엔트리를 포함하지 않으면 선출될 수 없다. 선출되기 위해, 후보자는 클러수터의 과반수와 연락하여 커밋될 로그에 대한 규칙을 가져야하며 이것은 모든 커밋된 엔트리는 후보자가 연락한 서버 중 적어도 하나에 존재해야 한다는 것이다.
래프트는 로그 내의 마지막 엔트리의 색인 번호로 두 로그 중 어떤 것이 최신인지 판단한다. 만약 로그의 마지막 엔트리가 term이 다르다면 더 나중의 term을 최신으로 판단한다. 만약 로그가 같은 term으로 끝난다면 더 긴 로그가 최신으로 판단된다.
Raft에선 유권자에 대한 후보자의 요청에는 후보자의 로그에 대한 정보를 포함한다. 만약 유권자가 소유한 로그가 후보자의 로그보다 최신이라면 유권자는 후보자에 대한 투표를 거부한다.이 구현은 상태 기계 안전성 규칙을 보장한다.
2.2.2 추종자 충돌
추종자가 충돌한 경우, 서로 다른 서버에 의해 보내진 엔트리확장과 투표 요청은 실패한다. 이러한 실패는 서버들이 추종자에 대한 접촉을 무기한적으로 재시도하는 것으로 해결된다. 만약 추종자가 다시 시작된다면, 대기 중인 요청은 완료된다. 만약 요청이 실패 전에 수신되었다면, 재시작된 추종자는 그것을 무시할 것이다.
2.2.3 시점과 가용성
래프트에서 시점은 일정 시간동안의 안정적인 리더를 선출하고 유지하기 위해 중요하며, 이를 위해 완벽한 클러스트 가용성을 가질 필요가 있다. 안전성은 알고리즘의 시점 요청 존중에 의해 보장된다.
- 브로드캐스트시간 << 선출 시간 << MTBF
- 브로드캐스트시간은 클러스트 내 모든 서버에 요청을 보내고 응답을 받기까지 걸리는 시간의 평균이다.
- MTBF는 서버 실패간의 평균 시간이다. 또한 이것은 인프라구조와 관련있다.
- 선출 타임아웃은 리더 선출 영역에서 서술한 것과 같다. 이것은 반드시 선택해야 하는 것 중 하나다.
일반적인으로 브로드캐스트 시간에는 0.5 ~ 20ms가 될 수 있으며, 선출타임아웃은 10 ~ 500ms 사이로 선택할 수 있다. 클러스터가 안정적으로 동작하기 위한 값들을 구하는 것은 몇주 또는 몇달이 걸릴 수 있다.
3 같이 보기
4 참고
-
{{comment.page_title}} ―{{comment.name}}