Raft Algorithm

Raft Algorithm은 분산 시스템에서 노드 간의 상태를 공유하는 알고리즘을 뜻함. 대표적으로 Paxos, Zab (Zookeeper)가 있으나 어려워, 이를 이해하기 쉽게 구현하기 위해 설계되었음.

Raft is a protocol for implementing distributed consensus.

동작과정

노드는 크게 3가지 형태를 가진다.

Leader Election

초기 노드는 모두 follower 상태에서 시작한다.

이중 leader로 부터 응답을 받지 못하면 Candidate 상태로 바뀐다.

Candidate 상태로 변한 노드는 vote를 다른 노드에 요청하면, 이에 대한 reply을 받는다.

대다수의 node로 부터 reply를 받은 note가 leader로 선출된다.

Log Replication

이후 시스템의 모든 변화는 leader를 통해 이루어 진다.

Client가 5라는 값을 보내면 먼저 leader에게 전달되며, 변화가 발생하는데 이러한 변화는 node’s log (log entity)에 기록된다.

log entity는 uncommit 한 상태이며, 이는 다른 node의 value가 update 되지 않았다.

commit한 상태로 만들기 위해, 다른 node (follower)의 value를 전달해 update 하며, 이를 leader에게 reply 한다.

이후 leader는 follower들에게 log entity가 commit 됐다고 알려준다.

Leader Election (DEEP)

election을 control 하기 위해 두 종류의 timeout을 setting 할 수 있다.

election timeout

follower가 candidate가 될때 까지 기다리는 시간을 의미한다.

시간은 random으로 선정되며 150ms ~ 300ms사이로 결정된다. 즉, 노드마다 election timeout 값이 다르다.

아래 그림 처럼 맨 위 노드가 random 시간이 가장 짧아 가장 먼저 candidate가 되었다.

가장 먼저 candidate가 된 노드가 다른 노드들에게 Request Vote를 보내며, 이후 vote를 가장 많이 받은 node가 leader로 선출된다.

heartbeat timeout

leader가 된 노드는 follower들에게 heartbeat를 주기적으로 보내는 시간을 의미한다. 만약 시간 내 heartbeat를 받지 못했다면 해당 node들은 candidate 상태가 된다.

만약 leader가 dead가 되어 heartbeat를 더이상 보내지 못한다면, 나머지 follower 중 leader가 다시 선출된다.

Log Replication (DEEP)

Leader는 follower들에게 주기적으로 heartbeat를 보내는데, 만약 Client가 Leader에게 특정 값을 보내면 heartbeat 이후에 수정된 값을 follower들에게 보낸다.

이후 모든 follower들에게 ack 를 받고 난 후 commit이 되며, commit 된 이후에 client에게 response를 보낸다.

Raft는 network partition 의 상태에서도 consistent를 유지할 수 있다.

위 그림처럼 A, B와 C, D, E가 분리가 되었을때 Leader가 두 노드가 되는것을 볼 수 있다.

이후 Clinet가 둘이 각 Network에 value를 보내는데, 아래 Client는 3을 보낸다.

허나 3은 commit이 되지 않는데 이러한 이유는 과반수를 넘지 못했기 때문이다. (빨간색 표시)

위 Client는 8을 보내는데, 8은 commit이 된다. 과반수를 넘었기 때문이다. (검은색 표시)

network partition이 정상적으로 돌아오면, 이미 commit 된 노드의 값을 가지는 8로 update가 되며, Leader는 위 Network의 노드가 그대로 Leader를 유지한다.

http://thesecretlivesofdata.com/raft/

Comments