Raft Consensus Algorithm

Raft 알고리즘을 Kubernetes 카테고리에 넣은 이유는 Kubernetes, ETCD외 Karpenter, AWS LoadBalancer Controller 와 같이 Raft 알고리즘이 사용되는것들의 로그들을 보면 Leader Election 과 비슷한 로그들을 확인 할 수 있다.

그로 인해 Raft 알고리즘에 대해 충분히 이해 하면 Kubernetes 운영 관리자 입장에서 좋을 것 같아 정리 한다.

 

개요

Raft란 뗏목을 의미하며 분산 시스템 환경에서 일관성 있는 상태를 유지하기 위해 사용되는 합의 알고리즘이다.
Kubernetes에서는 Raft 알고리즘을 사용하여 클러스터 내에서 리더를 선출하고, 리더를 통해 클러스터 전체의 일관성 있는 상태를 유지한다.

 

---

동작 원리

Raft Consensus Algorithm은 분산 시스템에서 모든 노드들은 1명의 리더와 나머지 노드들은 팔로워로 구성되며, 후보자는 리더가 응답이 없거나 타임아웃 상태 일 때 일시적으로 발생한다.

• 리더(Leader) : 리더는 클러스터를 관리하는 핵심 서버이며, 클라이언트의 요청을 모두 처리하고 클러스터의 상태 변경 사항을 모두 기록합니다 로그 복제를 통해 다른 팔로워들에게 복제하며 일관성을 유지한다.
  리더는 반드시 1명이고 다른 노드들은 리더의 지시에 따라 동작한다.
  
  
• 후보자(Candidate) : 리더가 타임아웃 상태이거나 응답이 없으면 새로운 리더 선출을 위해 자신을 후보자로 등록한다 타임아웃이 발생하면 자신의 임기(term)을 증가시키며 팔로워들에게 투표를 요청하며 과반수 이상일 시 자신이 리더가 된다.
  
  
• 팔로워(Follower) : 리더의 지시를 받는 일반 노드이며, 리더의 요청을 받아 로그 복제, 커밋 등의 작업을 수행합니다 일정 시간동안 리더의 요청을 받지 못하면 타임아웃이 발생하여 후보자 상태로 전환 된다.

 

위와 같이 클라이언트는 리더에게만 통신한다 리더는 변경사항을 로그(log)를 생성하여 팔로워들에게 전달 하며 모든 팔로워들에게 복제하여 전달하고 팔로워들은 리더에게 로그에 대한 응답을 리더에게 보낸다.

 

 

---

 

 

 로그 복제 (Log Replication)

• 리더는 상태 변화 로그를 기록하고, 이를 다른 노드들에게 복제한다.
• 로그는 일관성 있게 유지되며, 리더가 변경되더라도 클러스터는 일관성이 유지 된다.

 

---

 

리더 선출(Leader Election)

Raft 알고리즘에서 리더는 팔로워들의 투표를 받고 과반수가 넘는 팔로워가 리더가 됩니다.

 

리더가 없거나 팔로워가 타임 아웃이 발생할 때 해당 팔로워는 후보자가 되어 새로운 리더 선출을 시작하며 과반수 이상을 받은 팔로워는 리더가 됩니다 리더가 선출 된 후 남은 노들들은 팔로워가 됩니다.

 

순서대로 정리하자면

1. 클러스터에 리더가 없거나 팔로워의 타임아웃이 발생
2. 타임아웃이 가장 먼저 발생한 팔로워는 후보자가 된다.
3. 후보자는 자신에게 먼저 투표하고 노드들에게 투표 요청을 보낸다.
4. 투표 요청을 받은 노드가 후보자에게 투표 응답을 보내고 자신의 선거 타임아웃을 초기화 한다.
   투표 과정에 있는 노드 외에 후보자가 발생하지 않도록 제어한다.
5. 과반수 이상을 받은 노드는 새로운 리더로 선출 된다.

 

 

Diego Ongaro, John Ousterhout 논문

 

 

 

---

 

 

틀린 내용이 있다면 지적 부탁드리겠습니다.

 

감사합니다.

 

 

Ref. https://raft.github.io/

https://raft.github.io/raft.pdf  (논문)

Raft Consensus Algorithm