콘클라베를 통해 Raft 합의 알고리즘을 이해해보자 (feat. Kubernetes etcd)

근황 잠깐 말하자면 오픈소스를 직접 만들고 있다. 추후 목표중 하나로 '분산 클러스터링'을 염두하여 설계해왔다. 
 
https://github.com/downfa11-org/go-broker/issues/16

Add Distributed Coordination for Broker Cluster · Issue #16 · downfa11-org/go-broker

 
문서화하는 과정에서 짬짬히 etcd 원리를 공부하고 있는데 최근 본 논문을 읽으면서 찰떡 비유를 생각해냈다. 원본 논문 직역하던거도 거의 끝나가서 아마 조만간 올리지 않을까 싶다.
 
Raft 알고리즘의 개발팀은 어떤 철학을 갖고 설계했는지 잠깐 언급하자면, "이해하기 쉬운가?"에 치중해 있다. 단순성을 위해서 기존 복잡한 Pasox 등 알고리즘의 대체제를 가져온 것이다. CNCF 오픈소스나 Apace Kafka에서도 쓰이니 성공이지만 이해하기 쉬운지는 모르겠다.
 

---

 
국내에서 운영 환경에서의 분산 클러스터링이 추세를 보이고 있지만, 우리는 정작 내부적으로 여러 노드들간 리더 선출 과정이나 어떤 방식으로 가용성을 유지하는지에 대해 알지 못한다.
 
실제 교황청의 콘클라베 방식은 아래에서 예시든대로 이뤄지지 않는다.. 그냥 역사 좋아하다보니까 내가 이해하기 쉽게 적음. 독일왕이 선제후들의 투표를 받아 신성 제국의 황제로 선출되는 예시가 좋았으려나
 
 

분산 합의(consensus) 알고리즘

분산 시스템 안에서 상호 노드간의 합의를 이뤄서 리더를 선출하는 알고리즘을 말한다. 쉽게 설명하면, 투표권을 가진 각 노드가 다수결에 기반해서 리더를 선출한다는 의미이다.
 
MySQL Orchestrator, Redis Sentinel, Redis Cluster 등과 같은 기술들에서도 분산 합의는 내부적으로 이뤄진다. 이처럼 많은 consensus 알고리즘이 존재하지만, 그중에서도 Raft는 이해하기 쉬운 구조로 합리적인 선출 방식으로 많은 인기를 끌고 있다.
 
 

Raft 알고리즘

https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf
 
정족수를 채우기 위한 똇목(Raft) 알고리즘으로 이해하고 있었는데, 이번 기회에 좀더 찾아보면서 알게된 녀석.
 
Apache Kafka가 3.x 버전 이전까지 Zookeeper를 함께 사용해서 metadata를 관리해왔다고 알려져 있다. 내가 처음 kafka를 접한 시기는 이미 3.3 이후로 관습적으로만 zookeeper에 대해 들어왔지 실제로 사용해본 적은 없다.
 
하지만 이 Zookeeper 역시도 분산 시스템을 위한 리더 선출 과정에서 Raft 알고리즘을 사용하고 있었고, Kafka 3.3 이후 안정화된 KRaft 역시도 Raft 알고리즘에 기반하고 있다.
 

Leader Election

선출된 리더가 직무를 수행하는 기간을 term이라고 하는데, 앞으로 이야기하는데 있어서 중요하니 알아두자.
이 term 기간동안 각 노드들이 가질 수 있는 상태는 Leader, Follower, Candidate가 존재한다.

• Leader: 교황님은 term 기간동안 모든 신도들에게 내가 아직 살아있소(heartbeat)를 보내면서 교황청의 권위를 만국에 호소한다.
• Candidate: 추기경들이 모두 모였으니 투표에 의해 과반수를 얻은 노드를 차기 교황으로 선출한다.
• Follower: 신도들은 교황이 죽으면 자리에서 일어나 새로운 리더를 선출하기 위한 콘클라베를 준비한다.

ElcetionTimeout의 무작위성: 각 노드들은 서로 랜덤한 timeout을 갖고서 투표권을 갖는 Candidate가 될 수 있다. 

• RequestVote RPC: 리더 선출 투표용
• AppendEntries RPC: Heartbeat용

 
이 heartbeat와 리더 선출을 위한 투표는 보통 수 ms~ 수백 ms 사이에 벌어진다.
리더는 숨도 못쉬고 계속해서 heartbeat나 보내고 있어야 하는데, 서버에 부하가 가진 않을까.
  → RPC 통신(RequestVote RPC, AppendEntries RPC)으로 네트워크나 서버 부하를 줄인다.
 

Log Replication

어떤 알고리즘을 토대로 리더를 선출할까?
 
리더는 팔로워들에게 Log라는 정보를 전파하는데, 이 로그는 ‘해당 시스템이 수행해야할 임무가 적힌 todolist’이다.
이 할일 목록(Log Entry)을 리더는 계속 팔로워들에게 전파하고 과반수 이상의 팔로워들이 최신 로그를 가지게 되면서 해당 로그를 Commit한다.
 
커밋된 로그를 통해 일관성을 보장받고, 리더가 만일 장애가 생겨서 죽어버리면 새로 선출된 후계자가 선왕의 못다이룬 꿈을 대신 이뤄줘야 정통성을 보장받기 마련이다.
 

Safety

그럼 이 로그는 어떻게 관리해야 최신 버전에 대한 일관성을 유지할 수 있을까?
 
term: 앞서 말한 현직 교황님의 임기 기간. 종신직이라 취임날부터 선종하시는 그날까지 term이 된다.

• 이 term이 리더 서버보다 이전 버전이라면 해당 노드는 아직 로그를 전파받지 않은 구버전이라는 의미이다.

index: 현재 리더가 처리하고 있는 명령의 순서인데 offset, index 뭐 비슷한 개념이다.

• 자기가 보유한 index가 높으면 그만큼 최신이다.

 
앞서 Log Replication에서 선왕의 못다이룬 꿈을 이어야 진정한 계승자로서 정통성을 보장받는다고 했다.
term은 누가 선왕의 임종을 더 마지막까지 지켜봤는지, index는 선왕이 가장 최근까지 이루던 업적들로 이해하면 된다.
이 두 값이 가장 최신 상태인 노드가 진정한 계승자로 선출된다.
 
 

콘클라베로 리더 선출 과정을 다시 보자.

 

1. 현직 교황님이 선종하셨다. (리더의 장애 발생으로 다운)
2. 교인들은 추기경(Candidate)들을 모아서 콘클라베를 연다. (timeout이 끝난 follower들이 Candidate 상태로 전이)
3. 교황 후보자는 다른 팔로워들에게 투표를 권고한다.(RequestVote RPC)
4. 팔로워들은 후보자의 term과 index를 확인해서 최신 버전인지에 대한 일관성을 보장한다.
5. 투표가 시작된다.
   1. 투표자들은 자신보다 term이 같거나 높은 후보자에게 투표한다.
   2. term이 같다면, index가 더 높은 후보자에게 투표한다.

위 방식으로 교황 후보자들은 모두 가장 최신 term, index를 가져야 선출될 수 있는 셈이다.
 

Kubernetes가 Raft를 활용하는 방법

마찬가지로 분산 시스템인 Kubernetes 역시도 상태를 일관성 있게 유지하기 위해서 Raft 알고리즘을 통해 리더를 선출한다.
Control Plane에 내부 컴포넌트로 동작하는 etcd가 그 역할을 대신한다.
 
Kubernetes가 자체적으로 Raft 알고리즘을 이용하는게 아니라, 클러스터의 상태 관리를 통째로 위임받은 etcd가 내부적으로 Raft를 이용하는 것이다. 클러스터 내부에서 특히 리소스의 상태를 일관성 있게 관리해야하고 이를 etcd가 전담하고 있다.

• API Server의 Pod, Node, Config, Policy
• Scheduler의 Pod 배치 결과
• Controller Manager의 Replica 개수나 Deployment 상태 등

단순한 데이터베이스가 아니라 etcd에 적재된 정보를 기반으로 k8s가 어떻게 행동할지에 대한 기준이 된다.
 

etcd가 여러 개의 노드로 구성하는 Raft 기반 클러스터를 형성하고, 그 리더가 commit한 로그를 통해 Kubernetes의 상태를 일관성 있게 보관한다.

 
이 commited log는 ‘할일 목록(Log Entry)’이라고 앞서 설명했다.
 
당연히 kubernetes의 리소스 상태의 변경 명령(command)들이 protobuf encoding된 key-value 형태로 전달된다.
 
 
 
 
출처 및 인용.
usenix - In Search of an Undrestandable Consensus Algorith, (diego Ongaro and John Ousterhout, Stanford Univ)