Raft Algorithm

RAFT 알고리즘은 Consensus Algorithm 은 분산환경에서 각 노드간 상태를 공유하는 알고리즘 중 하나이고 kubernetes 에서 etcd 의 고가용성을 위해 여러대로(홀수) 운영 했을 때 합의를 하는 알고리즘이다. 합의 알고리즘 종류로는 Paxos가 있고, Zookeeper에서 사용하는 Zab이 있다.

client가 단일 server에게 데이터를 저장하는건 server 의 node 가 하나이기 때문에 합의에 대한 문제가 없다. 하지만 server의 node가 여러개라면? 데이터는 어느 서버에 어떻게 저장을 해야할까? 어떻게 합의를 이뤄야 할까?

Replicated state machines

RAFT는 우선 선정된 리더를 통해서 합의를 이루고, 리더에게 replicated log 를 관리하는 권한을 부여 한다. 리더는 클라이언트로 부터 log 를  받아 다른 서버에 복제하고, 안전하게 log 항목이 state machine으로 적용되었을 때 서버에게 알려준다.
리더가 있으면 복제된 로그의 관리가 단순해진다. 리더는 다른서버의 확인 없어 데이터를 새 항목을 넣을 위치를 결정할 수 있으며, 데이터는 리데어서 다른 서버로 저장된다.
리더가 실패하거나 다른 서버와의 연결이 끊어질 수 있으며, 새로운 리더가 선출된다.
리더 접근 방법을 고려할 때 합의 문제를 지도자 선출, 로그 복제, 안전한 속성을 가져야 한다.

Raft 기본

Raft 클러스터는 여러 개의 서버가 포함되어 있고, 5개는 일반적인 숫자로 두번의 장애를 견딜 수 있다.
각각의 서버는 세가지의 상태(leader, follower, candidate) 중 하나로 주어고, 일반적인 동작시에는 정확히 한명의 리더가 있고, 모든 서버는 팔로워가 된다.
팔로워는 리더나 후보자들의 요청에만 반응한다.
리더는 클라이언트 요청을 다루고 만약 클라이언트가 팔로우에게 요청을 하면 팔로우는 클라이언트 요청을 리더에게 리다이렉션 한다.

아래의 그림은 서버 상태를 나나탠 그림으로 팔로워는 다른 서버의 요청에만 응답하고, 만약 아무론 통신을 받지 않으면 후보자가 된다. 그리고 즉시 선출한다.
클러스터 전체 과반수 투표를 받은 후보자는 새로운 리더가 된다.
리더는 실패할 때 까지 활동한다.

시간을 아래와 같이 임의의 길이의 term 으로 나눈다.

구간은 연속적인 정수로 번호가 매겨진다. 한나 이상의 후보가 지도자가 되려고 시도하는 선거로 시작하고, 후보가 당선이 되면 남은 term 동안 리더 역활을 한다. 후보나 지도자가 자신의 임끼가 만료된 것을 발견하면, 팔로워 상태로 돌아간다.

서버마다 다른 시간에 term 사이에 변화를 관찰할 수 있다.  각각의 서버는 시간 경과에 따라 단조롭게 증가하는 현재 기간의 숫자를 저장하고 있다.

현재 term은 서버가 통신 할 때마다 교환되며, 한 서버의 현재 term가 다른 서버보가 작으면 형재 term을 더 큰값으로 업데이트 한다.
만약 서버가 오래된 term 번호를 요청을 수신하면 요청을 거부한다.

Raft 서버는 Remote Procedure Calls(RPCs) 를 사용하여 통신한다. 그리고 기본적인 합의 알고리즘은 두개의 타입(RequestVote RPCs, AppendEntries RPCs)의 RPCs를 요구한다.
RequestVot RPCs는 선거하는동안 후보자에 의해 시작 된다.
AppendEntries RPCs는 로그 항목을 복제하고 heartbeat 형식을 제공하는 리더에 의해 시작 된다.
서버는 적시에 응답을 받지 못하면 RPC를 재시도 하고, 최상의 성능을 위해 병렬로 RPC를 사용한다.

리더선출

참고 문헌 : raft git 자료

답글 남기기