[KRaft 파헤치기] Raft 알고리즘 톺아보기

들어가며

KIP-500을 통해 제안된 카프카의 주키퍼 독립 선언(?)에는 카프카의 메타데이터가 앞으로 Raft 알고리즘을 통해 관리될 것으로 나와있습니다. Raft 알고리즘은 쿠버네티스의 etcd에서 사용되는, 분산 합의 알고리즘인데요. 이번 글은 Raft 알고리즘이 어떤 방식으로 분산 환경에서 합의를 만드는지 살펴봅니다.

Raft 알고리즘 톺아보기

분산 합의?

분산 시스템은 2개 이상의 컴퓨팅 노드에서 동일한 목적을 위해 구성된 시스템을 말합니다. 그렇기 때문에 분산 시스템의 모든 노드는 동일한 상태(State)를 가져야 합니다. 그리고 이렇게 동일한 상태를 가지는 것을 합의(Consensus;컨센서스)라고 합니다. 예를 들어, 카프카도  컨트롤러가 몇 번 브로커인지 혹은 어떤 토픽의 몇 번 파티션이 어떤 브로커에 위치하는지를, 주키퍼를 통해 합의되어 관리됩니다. 만약 주키퍼 클러스터의 이상이 생겨 이러한 합의가 깨진다면, 클러스터에 예상하지 못한 다양한 이슈가 발생할 수 있습니다(참고로 주키퍼는 Raft 알고리즘 대신 ZAB을 사용합니다). 이처럼 분산 시스템에서 합의를 구성하는 것은 매우 중요합니다.

Raft 알고리즘

Raft(Reliable, Replicated, Redundant And Fault-Tolerant) 알고리즘은 클라이언트를 통해 받은 변경사항을 로그 복제를 통해 클러스터의 모든 노드가 동일하게 가질 수 있도록 하는 분산 합의 방법입니다. Raft 알고리즘은 3가지 역할의 노드들로 구성됩니다.

• 리더(Leader) :
  • 클라이언트와 통신하며, 변경사항을 요청받습니다.
  • 주기적으로 팔로워로 변경사항과 함께 하트비트 요청을 보냅니다.(AppendEntry)
• 팔로워(Follower) :
  • 리더가 요청한 변경사항을 저장합니다. 
  • 리더 선출 기간(Term)을 가지고 있습니다.
  • 선출 대기 시간(Election Timeout) 동안 리더의 요청을 대기하며, 시간 초과 시 후보자가 됩니다.
• 후보자(Candidate) :
  • 스스로와 다른 팔로워에 리더 선출 투표(RequestVote)를 요청합니다.
  • 클러스터의 과반 이상의 노드의 투표 응답을 받으면 리더가 됩니다.
  • 리더로부터 요청을 받으면, 리더 정보를 갱신하고 팔로워가 됩니다.

역할들을 살펴보았을 때, Raft 알고리즘의 2가지 중요한 실행 절차를 알 수 있습니다. 바로 투표를 통한 리더 선출(Leader Election)과 로그 복제(Log Replication) 입니다. 

참고로 설명을 위한 그림 자료는 http://thesecretlivesofdata.com/raft 를 참고했습니다. 그림에서는 아래와 같이 나타냅니다.

• 노드
  • 아무 선이 없는 푸른 동그라미는 팔로워를 나타냅니다.
  • 점선 테두리의 푸른 동그라미는 후보자를 나타냅니다.
  • 실선 테두리의 푸른 동그라미는 리더를 나타냅니다.
  • 팔로워와 후보자 노드의 시계 방향으로 채워지는 흰 선은 선출 대기 시간이 지나고 있음을 나타냅니다.
• 요청-응답
  • 색이 칠해진 동그라미는 요청을 나타냅니다.
  • 비어있는 동그라미는 응답을 나타냅니다.

리더 선출(Leader Election)

리더 선출 과정은 팔로워의 선출 대기 시간을 초과하면서 시작합니다. 선출 대기 시간은 각 팔로워마다 일정 범위의 랜덤 한 값을 가지며, 리더로부터 요청을 받으면 초기화됩니다. 만약 리더로부터 더 이상 요청을 받지 못하여 선출 대기 시간이 초과되면 팔로워는 후보자가 됩니다. 후보자는 먼저 스스로 투표한 뒤, 다른 팔로워들에게 투표 요청을 보냅니다. 투표 요청을 받은 팔로워는 자신의 선출 대기 시간을 초기화하고 투표 응답을 후보자에게 보냅니다. 대기하고 있던 후보자가 클러스터의 과반수의 투표 응답을 받으면 리더가 되며 리더 선출이 끝납니다. 

노드 C가 처음으로 선출 대기 시간을 초과하여 후보자가 되고, 다른 노드들에게 투표 요청-응답을 통해 리더가 되는 모습. 후보자가 스스로 투표 후에도 선출 대기 시간이 지나고 있음을 알 수 있다.

위 설명에서 중요한 점은 다음과 같습니다.

1. 선출 대기 시간은 일정 범위에서 랜덤한 값을 가지기 때문에, 서로 다른 팔로워가 동시에 리더 선출을 시작하는 경우가 적습니다. 
2. 후보자는 응답 수가 과반이 되기까지 대기합니다. 이 시간에도 팔로워와 후보자의 선출 대기 시간을 계속 지나갑니다.

그렇다면 만약! 아주 극히 드문 확률로 4대의 노드로 구성된 클러스터에서 두 노드가 동시에 후보자가 되고, 또 투표가 동률이 발생하면 어떻게 될까요? 위에서 살펴본 것처럼 후보자는 과반의 투표 응답을 받아야 리더가 되기 때문에, 두 노드는 후보자 상태로 대기하게 됩니다. 그리고 클러스터에는 리더 노드가 없기 때문에, 모든 팔로워 노드와 후보자 노드는 아무런 요청을 받지 못해 선출 대기 시간이 초과할 때까지 대기합니다. 결국 선출 대기 시간이 초과한 임의의 노드로 인해 다시 리더 선출이 진행됩니다. 

4번 선출 기간에 A와 C 노드가 후보자가 되어 투표 결과가 동률이 되지만, 과반의 응답을 받지 못해 리더가 되지 못하고 대기한다. 대기 중에 B 노드가 선출 대기 시간이 지나 후보자가 되고, 5번 선출 기간의 리더로 선출된다. 

로그 복제(Log Replication)

Raft 알고리즘으로 구성된 클러스터에선 클라이언트의 요청을 모두 리더가 받아서 처리합니다. 그리고 리더는 로그 형태로 클라이언트의 요청을 지속적으로 추가하여 저장합니다. 마지막으로 리더가 자신의 로그를 팔로워에게 복제하도록 함으로써 클러스터가 동기화됩니다.

리더는 클라이언트의 요청을 계속해서 이어붙이는 로그의 형태로 저장합니다. 리더는 자신의 로그를 팔로워가 복제할 수 있도록 합니다. 출처 : https://towardsdatascience.com/raft-algorithm-explained-2-30db4790cdef

리더는 팔로워에게 일정한 주기마다 AppendEntry 요청을 보내 클라이언트가 요청한 변경사항을 반영할 수 있도록 합니다. 나아가 팔로워는 리더의 AppendEntry 요청을 일종의 하트비트 신호로 인식하여 요청을 받게 되면 자신의 선출 대기 시간을 초기화합니다. 즉, 리더는 팔로워에게 주기적으로 하트비트 요청을 보내는데, 이 하트비트 요청에 그동안의 변경사항이 함께 전달됩니다.

리더인 노드 A가 AppendEntry 요청을 팔로워 노드에게 보냅니다. 요청을 받은 팔로워 노드 B, C는 자신의 선출 대기시간을 초기화하고 응답을 보냅니다.

Raft 알고리즘에선 클라이언트의 변경사항을 로그의 형태로 저장합니다. 그리고 리더는 클라이언트의 요청이 클러스터에 정상적으로 반영되었는지를 보장하기 위해 아래와 같이 일련의 과정을 통해 검증하고 응답을 보냅니다. 

리더가 클라이언트의 요청을 팔로워에게 전파하는 모습. 붉은색 텍스트는 Uncommit 로그를, 검은색 텍스트는 Commit 로그를 나타냅니다. (중간중간 멈추는 것은 녹화 문제입니다) 출처 : http://thesecretlivesofdata.com/raft/#replication

1. 클라이언트가 리더에게 변경사항을 담아 요청을 보냅니다.
2. 요청 받은 리더는 자신의 로그에 변경사항을 후보(Entry)로 저장합니다. (Uncommited)
3. 다음 하트비트 시점에 팔로워 노드들에게 변경사항을 담아 AppendEntry 요청을 보냅니다.
4. 리더의 요청을 받은 팔로워는 변경사항을 후보로 저장합니다. (Uncommmited)
5. 클러스터의 과반의 팔로워가 응답을 보내면, 리더는 후보 상태의 변경사항을 커밋합니다. (Commit)
6. 커밋이 되면 클라이언트에게 요청에 대한 응답을 보냅니다. 
7. 다음 하트비트에 리더는 커밋된 로그의 인덱스 정보를 같이 담아서 팔로워에게 AppendEntry 요청을 보냅니다.
8. 팔로워는 요청 내에 있는 리더의 커밋한 로그 인덱스까지 커밋합니다. (Commit)

참고로 AppendEntry 요청 메시지의 구조를 golang으로 표현하면 다음과 같습니다. (출처 : https://towardsdatascience.com/raft-algorithm-explained-2-30db4790cdef)

type AppendEntryArgs struct {
// 리더 정보
	Term			int		// current term of the leader, very IMPORTANT
	LeaderId 		int		// id of the leader, 0 to N-1 where N = total servers
// 최신 변경사항들
	Entries			[]Entry // new data to sync
// 이전 로그 정보
	PrevLogIndex	int		// important metadata for log correctness
	PrevLogTerm		int		// important metadata for log correctness
// 커밋된 로그 정보
	LeaderCommit	int 	// what index have been received by the majority
}

type AppendEntryReply struct {
	Term 			int 	// current term of the receiving node
	Success			bool	// AppendEntry declined or accepted
	ConflictIndex	int		// if declined, specifying the conflicting index
	ConflictTerm	int		// if declined, specifying the conflicting term
}

 

마무리

이번 글을 통해 Raft 알고리즘에서 리더를 선출하는 과정과 클라이언트를 클러스터에 동기화하는 과정에 대해 살펴봤습니다. 

만약 잘못된 부분과 수정이 필요한 부분이 있다면 언제든지 코멘트 부탁드립니다. 

참고 및 출처

Raft

Raft Consensus Algorithm

Raft Algorithm Explained 2

 

분산 컴퓨팅 - 위키백과, 우리 모두의 백과사전