Raft 알고리즘 요약

오늘 글 에서는 합의(consensus) 알고리즘 중 하나인 Raft 알고리즘(이하 Raft)에 대해서 설명한다. Raft에 대해서 조사를 하게 된 이유는 Kafka에서 Zookeeper을 제외하는 대신 Controller의 역할 수행을 위해 Raft의 일부 개념을 가져와서 구현했기 때문이다. Kafka에서 사용하는 Raft는 정확히 같은 동작방식을 사용하는 것은 아니다. 크게 차이가 나는 부분은 로그 복제 부분이다. 대표적으로 Raft는 push 방식으로 controller가 데이터를 각 follower에 보내지만 Kafka에서는 pull 방식으로 follower들이 데이터를 가지고 온다. 이 글에서는 그 차이점에 대해 설명하기 보다 Raft 논문^[각주:1]에서 설명하는 leader 선정 과정 및 로그 복제 방법에 대해서 간략히 소개한다.

Raft의 개발 목적은 기존의 알고리즘 대비 이해햐기 쉬운 합의 알고리즘을 만드는데 있다고 한다. 이해하기 쉽다는 것은 개발자가 실제로 엔지니어링을 할 때, 구현이 어렵지 않다는 것을 의미한다. Raft는 몇 가지 요소로 구분하여 기능을 설명한다. 이 글에서는 2개의 기능에 대해서 나누어서 설명한다.

 

1. Leader 선정

Leader 선정 과정에 대해 알기 전에 알아두어야 하는 기본 개념에 대해 먼저 설명한다.

 

서버의 상태는 3가지로 나뉜다.

• leader
• follower
• candidate

leader는 하나만 존재하며 모든 클라이언트로부터의 요청을 받는 역할을 한다. 처음 시스템이 시작되었을 때, 모든 서버들은 follower 상태로 시작한다. 반복적인 선정 과정을 통해 leader를 정하게 되고 leader로 계속 확인 받는 과정을 통해 leader로서 역할을 계속 수행할 수 있다. 아래 그림1로 각 상태의 변화 과정을 한 눈에 볼 수 있다.

그림 1. 상태 변환 과정

앞서 leader 선정을 반복적인 선정 과정이 있다고 했다. 반복적인 단계의 구분은 term으로 이루어진다. Raft는 연속적으로 증가하는 integer를 포함하는 임기(term)로 나누어진다. 각 서버들은 현재 term (current term)를 보관하고 있다. 서버가 다른 서버들과 통신하면서 current term을 주고 받는데, 받은 term이 서버가 가진 current term 보다 큰 값이면 교체한다. 큰 값이 더 최신의 상태를 의미하기 때문이다. 그리고 서버의 현재 상태를 follow로 전환한다.

그림 2. term 설명

 

상태, term 등의 기본 개념을 알아봤다면 이젠 Leader 선정 과정에 한걸음 더 들여다보자.

 

Leader는 주기적으로 heartbeat를 보낸다. follow 서버들은 leader로 부터 election timeout 시간이 되기 전에 heartbeat를 받지 못한다면 leader가 없다고 간주하고 새로운 leader 선정 과정으로 들어간다. Leader 선정에 들어가면 follower는 candidate로 상태를 바꾸고 current term을 증가한다. 그리고 본인에게 한표를 주고 다른 서버들에게도 투표 요청(RequestVote RPCs)을 한다. 투표는 3개의 결과 중 하나로 이어진다.

• leader로 선정
• 다른 서버가 leader로 선정
• leader로 설정된 서버가 없음 (과반의 투표를 받지 못함)

3번의 결과로 이어지면 다시 leader 선정 과정을 반복한다. 그런데 계속해서 3번의 결과로 이어지지 않는 이유가 있다. candidate 마다 랜덤한 timeout 시간(150~300ms)으로 투표를 요청하기 때문에 가장 빠르게 투표를 받는 서버가 나오게 되며, 해당 서버가 leader로 선출된다. Leader로 선정될 때는 과반수 이상의 follower로부터 투표를 받아야 한다.

 

다음 사이트^[각주:2]에서는 leader 선정과정을 애니메이션으로 잘 보여주고 있다. 애니메이션을 보면 leader 선정과정에서 서버로 표현된 원에 시계방향 선이 보이는데, 각 candidate 서버 마다 다른 속도로 흘러가는 것을 볼 수 있다. 앞서 설명한 timeout 시간이 랜덤하게 가진다고 보여지며 그래서 먼저 leader로 선정되는 서버가 나올 수 있다.

 

참고로 leader 선정 과정에서 candidate가 또 다른 candidate에게 투표 요청을 받았다고 가정하자. 그럼 current term과 다른 서버가 보낸 term을 비교하여 본인의 term이 작다면 상태를 follow로 전환한다.

 

Leader 선정에 대해 추가로 읽어보면 좋은 블로그^[각주:3]

 

2. Log Replication

클라이언트의 모든 요청은 leader가 받는다. 그리고 leader는 클라이언트의 요청이 포함된 entry를 follow에 복제한다.  복제는 leader가 follower에 보내는 heartbeat에 포함된 AppendEntries RPCs를 통해 이루어진다. 그리고 과반 수 이상 복제가 완료된 entry를 committed 되었다고 하며 committed된 entry는 실행 상태가 보장되었음을 의미한다. 즉, 모든 로그의 복제는 leader에 의해서만 전달되는 push 방식이다.

로그 안에는 일정하게 증가하는 index와 term 번호를 포함한다. 2개의 값으로 leader와 follower 각 서버의 상태가 동일함을 증명한다. 아래 그림 3과 같이 로그 index는 순차적으로 증가하며 term 별로 다른 색으로 구분된 것을 볼 수 있다.

그림 3.

Raft가 관리하는 상태는 다음 2가지 규칙을 따른다.

• 동일한 index, term 번호를 가지는 로그가 각 서버에 동일하게 존재하면 해당 로그는 동일한 client 요청이다.
• 동일한 index, term 번호를 가지는 로그가 각 서버에 동일하게 존재하면 해당 로그 이전의 값이 모두 동일하다.

그런데 leader와 follower의 충돌로 인해서 각 서버의 로그가 불일치하는 경우가 발생할 수 있다. 이 때, 각 서버 로그의 일관성을 유지하기 위해서 leader와 follower의 로그가 일치하는 지점 이후부터 leader의 로그 값으로 덮어 씌운다. 즉, 불일치가 일어난 부분은 leader의 로그로 일치시키는 것이다. 위와 같은 로직으로 일관성을 유지하기 위해 leader는 로그 복제 시 다음 로그의 인덱스 번호를 같이 포함하여 전송한다.

 

Log Replication에 대해 더 읽어보면 좋은 블로그^[각주:4]

 

3. 정리

이번 글에서는 논문에서 리더 선출과 로그 복제에 대한 부분을 읽고 아주 간략하게 필자가 이해한 부분을 정리했다. 그래서 잘못된 내용이 포함될 수 있으니 보다 자세한 사항은 논문을 직접 참고하시길 추천한다. 그리고 다른 블로그 글에서도 그림과 함께 자세히 설명한 내용도 있으니 참고하면 좋다.

 

 

 

 

1. In Search of an Understandable Consensus Algorithm [본문으로]
2. http://thesecretlivesofdata.com/raft/ [본문으로]
3. Raft Algorithm, Explained (Leader Election) [본문으로]
4. Raft Algorithm Explained 2 (Log Replication) [본문으로]