쿠...sal: [컴][알고리즘] Raft 알고리즘

Raft 알고리즘에 대한 설명은 ref. 2 를 먼저보자. 간결하게 그림을 이용해서 설명해 주기 때문에 이해하기가 더 쉽다. 아래 자료를 이해하는데에도 ref. 2 를 한 번 보고 보면 이해가 잘 될 것이다.

여기의 내용은 필자가 이해하려고 정리한 내용이라 내용이 부실할 수 있다. 그러니 되도록 Reference 에 적어놓은 원본을 확인하자.

State machine replication

분산에서 사용되는 Replication models(복제모델) 이 몇개 있는데(참고) , 이중에 State machine replication 이 있다. 이 모델이 distributed consensus 를 이용해서 만들어 졌다. 이 모델도 transactional replication model 처럼 많이 쓰인다.

이 모델은 replicated process 가 deterministic finite automation 이고 모든 event 에 대해 atomic broadcast 가 가능하다 는 것을 가정한다.

가정

replicated process 가 deterministic finite automation
모든 event 에 대해 atomic broadcast 가 가능하다

이 state machine replication 은 어떤 node(state machine) 가 동일한 순서로 input 을 처리한다면 동일한 순서의 output 이 나오게 된다. 그렇기 때문에 동일한 순서의 input 을 결정해서 그것을 모든 node 에 뿌려주는 작업을 해야 한다.

Distributed Consensus 는 뭔가?[ref. 1, 2]

이 동의(consensus)에 대한 이야기는 ref. 2 의 slide 를 보는 것이 효과적인 듯 하다.

consensus 동작을 설명하기 위해 "분산으로 구성된 database "를 보자. 이 db 는 각 node 가 같은 data 를 가지고 있어야 한다고 가정하자.

이 때 client 가 한 node 랑 통신을 할 것인데, 이 때 db 에 "x 라는 값을 5로 변경하라" 고 query 를 날렸다고 하자. 그러면 x 가 5으로 바뀌면 명령은 완료된다. 그런데 문제는 distributed system 이다. 여러개의 node 가 가지고 있는 x 라는 값이 다 똑같이 5로 바뀌어야 한다.

이렇게 여러개의 node 가 같은 명령(command) 을 수행해서 같은 동작을 하도록 하기 위해 필요한 것이 consensus(동의) 이다.

이 부분에 대해서는 여기서도 설명을 하겠지만 ref. 2 를 보는 것이 이해하기 좋다.

여하튼 모든 node 들이 같은 행동을 하기 위해서

일단 한 node (node A 라고 하자.)가 command 를 받으면
그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
그리고 다른 node 들에게 그 command 를 날려준다.
그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
log 를 적었다고 node A 에게 응답을 준다.
그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
그리고 client 에게 응답을 준다.

이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.

아래는 ref. 1 에서 이야기하는 Consensus 에 대한 설명이다.

----------------------------------------------------------------

동의(Consensus) 는 fault-tolerant distributed system(문제가 발생해도 계속 잘 동작하는 분산시스템이라고 보면된다.) 에 기본적인 문제이다.

consensus 는 여러개의 서버들이 값들(values)에 대해 동의하는 것을 포함한다. 그들이 어떤 값에 대한 결정에 도달하자마자, 그것은 최종결정이다. 일반적인 consensus algorithm 들은 다수의 서버들이 동작할 때 일을 진행한다. 예를 들면, 5개 서버로 된 cluster 는 심지어 2개의 서버에 문제가 생겨도 일을 계속해 나갈 수 있다. 만약 더 많은 서버에 문제가 생기면, 그들은 일을 진행하는 것을 멈춘다.(그러나 절대 틀린 결과를 return 하지는 않을 것이다.)

동의는 일반적으로 fault-tolerant system 들을 만드는 일반적인 방법인 replicated state machine들이 있는 상황안에서 발생한다.
각각의 서버들은

state machine과
log

를 갖는다. state machine 은 우리가 fault-tolerant 하고 싶은 구성요소(component)다. 예를 들면 hash table 같은 것이 있다.

client 는 하나의 믿을 수(reliable) 있는 state machine 과 상호작용하게된다.

각 state machine 은 input command 들을 그들의 log 로 부터 받는다.
우리의 hash table 예제에서, log 는 'x 를 3으로 set 하라' 같은 command 들을 가지고 있을 것이다. 서버들의 log 가 갖고 있는 command 에 대해 동의하기 위해서 consensus algorithm 을 사용한다.
consensus algorithm 은 다음과 같은 것을 보장해야만 한다.

만약 n번째 command 로 어떤 state machine 이 'x 를 3으로 set 하라' 는 명령을 적용한다면,
다른 state machine 은 항상 다른 n번째 command 를 적용해야 한다.

결과적으로 각각의 state machine 은 같은 series of commands 를 처리한다. 그리고 그래서 같은 series of result 들을 생산하고 같은 series of states 에 도달하게 된다.

----------------------------------------------------------------

Raft algorithm[ref. 3]

제일 일반적인 동의알고리즘(consensus algorithm) 은 Paxos 인데 이녀석은 이해하기 어렵고, 정확히 구현하기도 어렵다고 알려져 있다.

Raft 는 새로운 동의알고리즘(consensus algorithm)
이해가능함을 위해 디자인됐다.

Raft 는

먼저 server 를 leader 로 선출한다.
그리고 모든 결정들을 leader 에게 모아준다.

이 2가지 과정이 상대적으로 독립적이며 Paxos 보다 나은 구조를 만들어준다.

Raft 는 아래 방법을 이용해서 리더를 선출한다.

투표(voting) 와
랜덤화한 타임아웃(randomized timeouts)

선거(election)는 리더가 이미 필요한 모든 정보를 저장했다는 것을 보장 해 준다. 그래서 데이터는 오직 리더에서 다른 서버들로만 흘러간다.

다른 leader-based algorithm 들과 비교하면, 이것은 방법(mechanism) 을 줄이고 행동을 단순화한다. 리더가 선출되며, 리더는 복사된 log 를 관리한다.

Raft 는 로그들이 어떻게 커지는 지에 관한 간단한 불변(simple invariant)을 레버리지(leverage)해서 알고리즘의 state space 를 줄이고 적은 mechanism 으로 이 작업을 달성한다.

Raft 는 이전의 알고리즘들에 비해 실제 세계 구현에도 적합하다. 이것은 실질적인 배포(deployments) 에도 충분히 잘 동작한다.

이것은 "고객 상호작용을 어떻게 관리하는지", "cluster 의 membership 을 어떻게 바꾸는지", 그리고 "로그가 너무 커졌을 때 그것을 어떻게 컴팩트하게 하는지"를 포함한 모든 완전한 시스템을 만드는 모든 측면을 언급한다.

cluster membership 을 바꾸기 위해, Raft 는 한번에 하나의 서버를 더하거나 뺀다.

(복잡한 변경은 이 기본 과정들로 작성할 수 있다.)

그리고 cluster 는 변경을 하는 중에도 계속해서 request 들을 계속 처리할 수 있다.

리더 선출(leader election)

node 의 state

node 는 다음 3가지 state 를 갖는다.

follower
candidate
leader

처음 시작할 때 node 는 모두 follower 이다. 만약 follower 가 leader 를 가지고 있지 않으면 그들은 candidate 가 될 수 있다.

또는, node 는 leader 로 부터 heartbeat 을 주기적으로 받는데, 이 heart beat 이 오지 않아서 heartbeat timeout 이 끝나면 leader 를 가지고 있던 node 이지만, 이 node 는 candidate 가 되는 것이다.

2개의 timout 세팅

node 는 다음 두종류의 timeout 을 갖게 된다.

election timeout:
follower 가 candidate 가 되기까지 걸리는 시간이다. 150ms ~ 300ms 사이의 random 한 값으로 각 node 가 각자 setting 한다.

그리고 만약 2개의 node 가 candidate 가 되는 경우에는 같은 election term 을 가진 2개의 election 이 발생한다. 이 경우 각 candidate 가 vote 를 해달라고 node 에게 message 를 보낸다.

그러면 한 node 는 같은 election term 을 가진 vote request 를 2개 받을 것이다.
이 경우에 node 는 먼저 온 vote request 에 대해서만 응답을 해주고, 나중에 온 vote request 에는 응답을 하지 않는다.(node 는 한 election term 에 대해서 한개의 vote 만 한다.)

이 때 누군가 과반수를 얻는다면 그 candidate 가 leader 가 되지만, 과반수를 얻지 못하면 candidate 가 timeout 되고 새로운 election term 을 시작하게 된다.

아래 "leader 선출 과정" 참고
heartbeat timeout
주기적으로 leader 가 message 를 보내는데 이 heartbeat timeout 시간안에 보내야 leader 가 살아있다고 판단한다. 만약 이 시간안에 message 가 오지 않으면 node 는 바로 candidate 가 된다.

초기상태

이제 막 node 들의 설치가 끝나고 node 들을 실행(run) 했다고 가정해보자.

각 node 는 각자 150ms ~ 300ms 사이의 random 한 값으로 election timeout 을 setting 하고, 그 시간이 끝나면 follower 에서 candidate 로 상태가 바뀐다.

각 node 가 random 하게 timeout 을 설정했기 때문에 각자 candidate 로 상태가 바뀌는 시간이 다를 것이다.

leader 선출 과정

일단 candidate 가 된 node 는,

새로운 선거기간(election term) 을 시작한다. (termCount: 1)
그리고 자기한테 vote 하고, (voteCount: 1)
다른 node 에게 vote 를 해달라고 request 를 보낸다.(Request Vote message)

이 때 timeout 시작한다. 이 timeout 까지 과반의 vote 를 획득해야 한다.

참고로 다른 node 가 leader 라면서 message 를 보낼 수 있는데 이때는 termCount 가 자신보다 높은지를 확인하고, 높다면 자신은 follower 가 된다.

자세한 사항은 In Search of an Understandable Consensus Algorithm > 5.2 Leader election 을 참고하자.
그러면 request 를 받은 node 들 중에 이 선거기간(election term) 에 "vote 를 하지 않은 node" 들은 candidate 에게 vote 를 해준다.
그리고 이 node 들은 자신들의 election timeout 을 reset한다.
이렇게 해서 한 candidate 가 과반수의 vote(majority of votes) 를 얻으면 그 candidate 가 leader 가 된다. 이 과반수가 leader 가 단 하나만이 존재하도록 보장해 준다.

여러개의 candidate 가 vote 를 해달라고 node 에게 message 를 보내게 되면, node 는 같은 termCount(election term) 을 가진 request 을 여러개 받게 된다. 이 경우에 node 는 먼저 온 request 에 vote 를 하고, 뒤이어 오는 다른 request 에는 vote 를 하지 않는다.(한 election term 에는 한개의 vote 만을 하는 것이다.)

이래서 만약 어떤 candidate 도 '과반수' 를 얻지 못한다면, candidate 들은 timeout 되고, 새로운 election term 을 시작하게 된다.

leader 와 heart beat(Append Entries message)

node 가 leader 가 되면

leader 는 Append Entries message 를 follower 들에게 보내기 시작한다.
이 message 들은 각 node 들이 가지고 있는 heart beat timeout 에 의해 정해진 시간(interval)안에 node 들에게 도착하게 된다.
이 message 를 받으면 node 들은 heart beat timeout 을 reset 하고 다시 시작한다.
그리고 leader 에게 응답을 보낸다.
이 상태가 유지되면 election term 은 계속 같은 id 를 유지하게 된다.

follower 가 heart beat 을 받는 것을 멈추고 candidate 가 될 때까지, 선거기간(election term) 은 계속 된다. 즉 새로운 candidate 가 생겨서 새로운 election term 이 시작되기 까지는 기존의 election term 이 유지되는 것이다.

만약 현재 leader node 가 어떤 이유로 멈추면, hear beat timeout 시간안에 Append Entries message 가 오지 않아서 heartbeat timeout 이 끝나게 된다. 그럼 node 는 바로 candidate 가 되고, "leader 선출 과정" 을 시작하게 된다.

Log Replication, 로그 복제

로그는 client 가 request 한 command 를 적어놓은 것이기 때문에 로그 복제는 command 의 복제라고 보면 된다. 즉 로그 복제를 한다는 것은 실제 동작을 복사해서 follower node 에게 전달하는 것이다. (이것은 state machine 이기 때문에, 같은 순서의 command 를 제공하기만 한다면, 같은 결과를 가져오기 때문에 가능한 것이다.)

이 log replication 은 리더에 의해서 시작된다. 이는 Raft 에서 client 가 leader 에만 접근가능하기 때문이다.

여하튼 leader 는 위에서 heartbeat 로 사용했던 Append Entries message 를 이용해서 변경사항을 node 들에 전달한다.

이것을 대략 정리하면 아래와 같다.

일단 leader node (node A 라고 하자.)가 command 를 받으면
그것을 바로 수행하지 않고, 그 command 를 log 에 적는다.
그리고 다른 node 들에게 그 command 를 날려준다.
그럼 다른 node 들도 그 command 를 받고 log 에 적은 후에
log 를 적었다고 node A 에게 응답을 준다.
그럼 node A 가 응답들을 보고 과반수 이상이 command 를 log 에 적었다는 것을 확인하면,
node A 는 log 에 적어놓은 그 command 를 실제로 수행 한다.(commit)
그리고 client 에게 응답을 준다.

이 경우에 client 가 응답을 못받으면, command 는 실행되고, client 는 command 가 수행된지를 몰라서 같은 작업을 다시 반복하게 된다. 이렇게 계속 같은 작업을 하게 될 수 있기 때문에 command 에 unique serial number 를 포함시킨다.[ref. 4 > Client interaction]
그 다음 다른 node 들에게 자신(node A) 가 commit 했다고 알려준다.
그럼 다른 node 들도 log 에 적어놓은 comand 를 commit 하게 된다.

관련해서 자세한 사항은 ref. 2 를 참고하자. ref.2 에는 추가적으로 partition 이 나눠져서 log 가 2개가 생기는 경우에 대한 예제도 있다.

Client

client 가 처음에 cluster 에 접근하게 되거나 leader 가 crash 되었거나 하면, 여러 node 중에 아무 node 에나 접근하게 된다. 이 때 node 는 이 client 를 무조건 reject 하고 leader 정보를 준다. 그럼 client 가 이 정보를 가지고 다시 leader 로 접근하게 된다.

원래 node 가 leader node 로 부터 AppendEntries message 를 주기적으로 받는데, 이 녀석에 leader 의 network 주소도 같이 있어서 redirect 시켜주는 것은 어렵지 않다.

Read-only operation

Read-only 명령은 log 에 굳이 명령을 적지 않고 수행해도 문제가 없다. 다만 이 경우에 return 해주는 data 가 오래된 data(stale data) 가 아니어야만 한다.

그런데 client 가 통신하고 있는 도중에 leader 가 교체된 상태라면, data 는 최신 data 를 보장할 수 없다. client 에게 return 하는 data 가 아직 leader 의 최신 data 로 update되지 않은 data 일 수 있다.

(참고 : https://youtu.be/6Kwx8zfGW0Y?t=2032)

stale data 의 보장

log 를 이용하지 않고 stale data 가 아닌것을 보장하기 위해 Raft 에서 2가지 예방책이 필요하다.

리더가 최근 정보를 가져야만 한다. 이정보의 내용들은 당연히 commit 이 이미 된 내용(committed entries)이어야 한다.(Leader Completeness Property )

그러나 term 의 시작시점에서는 log 에 적혀있는 entry 중에 어떤 녀석이 commit 된 내용인지 알 수 없다.(ref. 4 > figure 8 참고)

이것을 알기 위해서 Raft 에서는 각 리더가 term 의 시작시점에 blank no-op entry 를 log 에 commit 한다. (그러니까 no-op entry 에 대한 commit 까지 완료하면, 이전의 entry 들은 commit 이 제대로 됐다고 볼 수 있다?)
두번째로 리더 노드는 read-only request 를 처리하기 전에 자신이 리더에서 물러난 상태인지 여부를 확인해야만 한다.

Raft 는 read-only reqeust 에 응답하기 전에 리더가 heartbeat message 를 cluster 의 과반수의 node 와 교환하게해서 이것을 처리한다.

User-group

궁금한 점은 아래 user-group 을 이용하면 될 듯 하다.

raft-dev - Google 그룹스

References

Raft Consensus Algorithm: raft 알고리즘과 관련된 자료들이 전부 모아져 있다. 동영상, library 들의 link 도 있다.
The Secret Lives of Data : Raft 설명, 자세하게 예제를 slide 를 이용해서 설명해준다.
Diego Ongaro's PhD dissertation, Consensus: Bridging Theory and Practice, published by Stanford University in 2014 > Abstract
In Search of an Understandable Consensus Algorithm,

쿠...sal

[컴][알고리즘] Raft 알고리즘