What is Raft?
Raft는 이해하기 쉽도록 설계된 합의 알고리즘이다. 내결함성 및 성능 면에서 Paxos와 동일하다. 차이점은 비교적 독립적인 하위 문제로 분해되어 있으며, 실제 시스템에 필요한 모든 주요 부분을 깔끔하게 해결한다는 것이다.
Hold on - what is consensus?
합의는 내결함성 분산 시스템의 근본적인 문제이다. 합의는 여러 서버가 그 가치에 동의하는 내용을 포함한다. 한 서버가 값에 대한 결정에 도달하면 그 결정이 최종 결정이 된다. 일반적인 합의 알고리즘은 과반수의 서버를 사용할 수 있을 때 진행된다. 예를 들어 5대의 노드로 구성된 클러스터의 경우 2대의 노드 실패까지 내결함성을 지닌다. 더 많은 노드의 실패가 발생하면 중단되지만 잘못된 결과를 반환하지는 않는다.
합의는 일반적으로 내결함성 시스템을 구축하기 위한 일반적인 접근 방식인 복제된 상태 머신의 맥락에서 발생한다. 각 서버에는 상태 머신과 로그가 있다. 상태 머신은 해시 테이블과 같이 동작하며 내결함성을 갖추기 위한 구성요소다. 클라이언트는 클러스터의 일부 서버에 장애가 발생하더라도 신뢰할 수 있는 단일 상태 머신과 상호 작용하고 있는 것 처럼 보인다. 각 상태 머신은 로그에서 명령을 입력으로 받는다. 해시 테이블에는 set x to 3과 같이 값을 설정하는 등의 명령이 포함된다. 합의 알고리즘은 서버 로그의 명령에 동의하는데 사용된다. 합의 알고리즘은 어떤 상태 머신이 n번째 명령으로 set x to 3을 적용할 경우 다른 상태 머신이 다른 n번째 명령을 반영하지 않도록 보장해야 한다. 결과적으로 각 상태 머신은 동일한 일련의 명령을 처리하므로 동일한 일련의 결과를 생성하고 동일한 일련의 상태에 도달하게 된다.
What is Distributed Consensus in Raft?
단일 노드가 시스템에 존재한다고 가정하자. 이 가정에서는 노드를 단일 값을 저장하는 데이터베이스 서버로 생각할 수 있다. 또한 서버로 값을 전송할 수 있는 클라이언트도 있다. 단일 노드에서 하나의 명령에 대한 합의는 쉽게 진행할 수 있다. 하지만 여러 노드가 존재하는 상태에서는 어떻게 합의에 도달할 수 있을까? 이것이 바로 분산 합의의 문제다. Raft는 분산 합의를 구현하기 위한 프로토콜이다. 동작 방식에 대한 간략한 개요부터 살펴보자.
Overview
단일 노드는 3가지의 상태를 가질 수 있다.
- Follower state
- Candidate state
- Leader state
Leader election
모든 노드는 follower state로 시작한다. 만약 팔로워가 리더로부터 연락(heart beat)를 받지 못하면 후보가 될 수 있다. 그런 다음 후보자가 다른 노드에 투표를 요청한다. 노드들은 그들의 투표로 응답을 보낸다. 후보가 과반수의 노드로부터 표를 얻으면 리더가 된다. 이 프로세스를 리더 선출(Leader Election)이라 한다.
Log replication
이제 시스템에 대한 모든 변경 사항은 리더를 통해 이루어진다. 각 변경 사항은 노드의 로그에 추가된다. 이 로그 항목은 현재 커밋되지 않은 상태라 노드 값을 업데이트 하지 않는다. 항목을 커밋하기 위해 노드는 먼저 팔로워 노드에 해당 항목을 복제한다. 그런 다음 리더는 대다수의 노드가 엔트리에 해당 값을 작성할 때 까지 기다린다. 응답은 받은 리더는 값을 커밋하고 팔로워들에게 값이 커밋됨을 통지한다. 이런 방식으로 클러스터는 시스템 상태에 대한 합의에 도달하게 된다. 이 프로세스를 로그 복제(Log Replication)이라 한다.
Low level design
Leader election
Raft에서는 선거를 제어하기 위해 두 가지 타임아웃이 존재한다. 첫번째는 election timeout이다. Election timeout은 팔로워가 후보자가 될 때 까지 기다리는 시간이다. 이 시간은 150ms에서 300ms까지 무작위로 지정된다. Election timeout이 지나면 팔로워는 후보자가 되어 새로운 election term을 시작하고 스스로에게 투표한다. 그런 다음 다른 노드들에게 투표 요청 메세지를 보낸다. 수신 노드가 이번 term에 아직 투표하지 않은 경우 후보자에게 투표한다. 그리고 수신 노드 스스로 election timeout을 재설정한다. 과반수의 표를 얻은 후보는 리더로 승격한다.
이제 리더는 팔로워들에게 append entries 메세지를 보내기 시작한다. 이 메세지는 heartbeat timeout으로 지정된 간격을 가지는 주기로 전송된다. 그런 다음 팔로워가 각 append entries 메세지에 응답한다. 이 term은 팔로워가 heartbeat 수신을 중단하고 후보자가 될 때 까지 지속된다.
리더가 중지되고 재선거는 어떤 방식으로 진행되는지 살펴보자. 하트비트를 받지 못한 노드는 timeout이 발생하고 후보자가 된다. 후보자는 위에서 언급한 내용과 동일하게 election term을 시작하고 클러스터에 투표를 진행하게 된다. 리더가 되기 위해선 과반의 득표가 필요하기 때문에 term당 한 명의 리더만 선출되게 된다.
두 개 이상의 노드가 동시에 후보가 되면 분할 투표가 발생할 수 있다. 분할 투표 시나리오를 살펴보자. 클러스터에는 4개의 노드가 존재하고, 그 중 2개의 두 노드(A, B)가 동시에 후보자가 되어 같은 term에 선거를 시작한다. 그리고 후보자 각각의 투표 요청은 각각의 노드에 도착하게 된다. C는 A에게, D는 B에게 투표하여 각 후보자에게는 2표씩 득표했기 때문에 이번 term에는 더 이상 표를 받을 수 없게 된다. 노드는 새로운 선거를 기다렸다가 다시 시도한다. 이 과정을 통해 최종적으로 하나의 노드만 리더로 선출된다.
Log replication
리더가 선출되면 시스템에 대한 모든 변경 사항을 모든 노드에 복제해야 한다. 이 과정은 하트비트에 사용되는 것과 동일한 append entries 메세지를 통해 이루어진다. 이 프로세스를 살펴보자. 먼저 클라이언트가 리더에게 변경 사항을 전송한다. 이 변경사항은 리더의 로그에 추가되고 다음 하트비트 메세지에 팔로워들에게 변경 사항을 실어 전송한다. 과반의 팔로워가 승인하면 항목이 커밋되고 응답이 클라이언트로 전송된다.
Raft는 네트워크 파티션에 있어서도 일관성을 유지할 수 있다. 클러스터에 5개의 노드가 있고 {A,B}, {C,D,E}로 파티션이 분리되었다고 가정하자. 파티션이 분리된 C D E(파티션 2)에서는 새로운 리더를 선출하게 되고, 네트워크 파티션으로 인해 서로 다른 term을 가지는 두 명의 리더를 가지게 된다. 이제 서로 다른 클라이언트가 두 리더를 업데이트 한다고 가정하자. 클라이언트는 파티션 1로 요청을 보냈지만, 파티션 1의 리더 A는 과반의 노드가 동의하지 않아 로그 항목이 커밋되지 않은 상태로 유지된다. 다른 클라이언트는 파티션 2의 리더 C에 요청을 보낸다. 리더 C는 과반의 노드가 복제에 동의했기 때문에 명령이 성공적으로 수행된다. 이제 네트워크 파티션이 복구되었다 가정하자. 노드 A는 노드 C가 가지는 더 높은 term을 보고 물러나게 된다. 노드 A와 B는 모두 커밋되지 않은 항목을 롤백하고 C의 로그와 일치 시킨다. 이 과정을 통해서 클러스터 전체에 로그의 일관성을 유지하게 된다.