쿠버네티스의 분산 합의 알고리즘 (Raft 알고리즘)

최근에 사이드 프로젝트를 하느라 코딩을 많이해서 그런가 요즘은 이론 공부에 집중하게 되더군요. 조금 딴소리지만 처음 공식문서를 읽게 된게 Baeldung의 로컬 트랜잭션과 글로벌 트랜잭션인데 이걸 처음 읽고 충격에 빠지지 않을 수 없었습니다. 이론공부를 한다는게 이렇게 재밌는 일인가? 싶은 생각이 들었었죠. 

 

그 때가 벌써 2년전이네요. 그 이후로 공식 문서를 보는걸 좋아했는데 짧은 영어로 한글자 한글자 해석하면서 알게되는 변태같은 심연의 지식들이 너무 좋더라구요. 

 

이번 포스팅에선 분산 시스템에서 합의를 이뤄 리더를 선출해내는 분산 합의 알고리즘을 공부해보고 정리해봤습니다. 

 

분산 합의 알고리즘

Raft 알고리즘을 본격적으로 들어가기 전에 분산 합의 알고리즘이 어떤 것이며 왜 필요한지 정리하고 넘어가겠습니다. 

 

분산 합의 알고리즘은 말 그대로 분산 시스템에서 합의를 이루어 리더를 선출해내는 알고리즘입니다. 우선 합의를 한다는 말이 가지는 의미는 분산 시스템에서 각 노드들이 투표권을 가지고 리더를 선출한다는 의미입니다. 

 

분산 합의 알고리즘은 분산 시스템에서 상태를 저장해야하는 기술들에서 주로 볼 수 있습니다. 오늘 소개드릴 Raft 알고리즘은 아니지만 MySQL Orchestrator나 Redis Sentinel, Redis Cluster 같은 리더선출 기반 기술들에서 볼 수 있는 알고리즘입니다. 

 

많은 분산 합의 알고리즘이 있지만 그 중에서도 Raft는 이해하기 쉬운 구조로 되어있고 합리적인 선출 방식 덕분에 많은 곳에서 사용중입니다. 

 

보통 분산 시스템에서 상태를 저장해야하거나 리더가 특정 행동을 주도해야하는 경우 유용하게 사용됩니다. 그래서 Zookeeper나 Zookeeper의 의존성을 없애기 위해 Kafka에서 3.3부터 안정화된 KRaft가 바로 Raft를 이용해서 분산 합의를 이뤄낸 경우입니다. 

 

https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf

 

위의 링크는 2014년에 발표된 Raft 알고리즘의 논문인데요. 이해하기 쉽게 배려넘치는 글은 아니지만 그래도 Raft 알고리즘을 이해하는데 도움이 많이 됐습니다. 논문을 다 보실 필요는 없고 5장만 보시면 될 것 같습니다. 3페이지 정도 되는 분량이라 가볍게 읽기에도 좋을 것 같네요. 

 

Raft 알고리즘

Raft 알고리즘에선 세 가지 중요한 개념이 등장합니다. 

 

• Leader Election
• Log Replication
• Safety

하나씩 정리해보겠습니다. 

 

Leader Election

Raft 알고리즘은 기본적으로 리더를 선출하는 것이 베이스입니다. 이 때 중요한 개념이 바로 term인데요. 한국어로 번역하자면 "임기" 정도가 될 것 같습니다. 

 

이 임기 동안 서버들이 가질 수 있는 상태는 Leader, Fallower, Candidate 이렇게 세 가지입니다. 임기 동안 각 서버들은 랜덤한 timeout을 가지고 있고 이 timeout이 지나면 Candidate이 되며 리더가 되기위한 투표를 진행합니다. 

 

한번 다시 정리해보겠습니다. 

 

• Leader : 리더는 임기 (term) 동안 지속적으로 팔로워들에게 지속적으로 Heartbeat을 보내면서 자신이 아직 리더로서 건재하다고 요청을 보냅니다. 
• Follower : 팔로워는 임기 동안 리더로부터 지속적으로 Heartbeat를 받고 만약 Heartbeat를 받지 않은 팔로워는 timeout이 지나면 Candidate으로 격상합니다. 
• Candidate : 후보자로 격상된 팔로워가 다른 서버에게 투표를 요청하고 특정 알고리즘을 기반으로 투표를 진행한 뒤 과반수가 리더로 선출하는데 동의하면 리더로 격상됩니다. 이 특정 알고리즘은 뒤에서 소개해드릴 Log Replication에서 자세히 다루도록 하겠습니다. 

보통 Heartbeat와 리더 선출을 위한 투표는 수 밀리초에서 수백 밀리초 사이에 벌어집니다. 즉, 리더는 자신이 살아있다는 것을 서버에 알리기 위해 수~수백 밀리초동안 지속적으로 요청을 보낸다는 말인데요. 그럼 이게 서버에 부하가 가진 않을까 걱정이 됩니다. 

 

그래서 Raft 알고리즘에선 RPC 통신을 함으로써 리더 선출과 Heartbeat를 진행할 때 네트워크 부하와 서버 부하를 줄일 수 있게 됩니다. 

 

이에 관해서는 gRPC를 소개한 제 포스팅에서 자세히 설명이 되어있습니다. HTTP/2 기반의 통신으로 헤더 압축, 바디 압축, 멀티플렉싱으로 동기 통신에서 엄청난 성능을 보여주게 됩니다. 

 

물론 Raft 알고리즘에서 사용하는 RPC 통신은 gRPC는 아니지만 RPC 통신이라는 점에서 일맥상통하기에 추천드리는 포스팅입니다. 

 

https://coding-review.tistory.com/589

서버간 동기 통신을 더 빠르게! gRPC의 무기들 (+실증테스트)

 

Raft에선 두 가지 RPC 통신을 하게 됩니다. 바로 RequestVote RPC와 AppendEntries RPC 이렇게 두 가지의 RPC 통신입니다. 

 

논문에서도 이에 대한 자세한 내용은 없고 RequestVote는 리더 선출을 위한 투표용 RPC이고, AppendEntries는 Heartbeat를 위한 RPC 통신입니다. 

 

AppendEntries RPC가 보통 수십 밀리초단위로 Heartbeat를 체크하고 RequestVote는 200밀리초 정도 걸리는 조금 긴 RPC 통신입니다. 

 

Log Replication

Log Replication은 어떤 논리를 기반으로 리더를 선출할 것인지에 대한 Raft 알고리즘의 알파이자 오메가입니다. 

 

리더는 팔로워에게 Log (이하 로그) 라는 정보를 전파하게 되는데 이 로그는 우리가 아는 백트래킹용 로그가 아니고 해당 시스템이 어떤 임무를 수행해야하는지 적혀있는 TODO list같은 느낌의 무언가입니다. 

 

이렇게 로그를 관리하고 전파하는 이유는 후에 리더에 장애가 생겨 죽어버리면 다른 팔로워가 리더가 되면서 리더의 임무를 이어서 해야하는데 이전 리더가 하던 일을 이어받아야 하기 때문에 반드시 필요합니다. 

 

리더는 과반수의 팔로워들이 최신 로그를 가지게 되면 해당 로그를 커밋함으로써 로그 상태를 관리합니다. 

 

Raft 알고리즘에서 Log Replication으로 로그를 관리하지만 그 과정에서 일관성이 매우 중요한데요. Raft에선 이 일관성을 관리하기 위해 로그를 특정 규칙에 의해 관리가 되어야합니다. 

 

로그를 관리하는 과정을 이제 소개하려고 합니다. 그러기 위해선 앞서 설명한 term과 새로 등장하는 index에 대한 깊이있는 이해가 필요합니다. 

 

Safety

• term : 0부터 시작하는 term은 현재 리더의 임기를 보관하는 정보입니다. 이 정보를 기반으로 해당 로그가 최신 상태인지 구버전의 상태인지 확인할 수 있습니다. 
  
  예를 들어서 리더 서버가 현재 3이고 이 상태를 공유하는데 만약 2인 서버가 있다면 이 서버는 아직 로그가 전파되지 않았다는 의미이므로 구버전이라는 의미입니다. 
• index : 이 index는 kafka로 치면 offset과 비슷한 개념입니다. 현재 리더가 처리하고있는 명령의 순서이죠. 이 index가 작다는 이야기는 구버전이라는 의미입니다. 왜냐하면 현재 자신이 보유한 index가 높으면 그만큼 최신이라는 의미이기 때문이죠. 

 

이를 기반으로 투표는 다음과 같은 순서로 진행됩니다. 

 

1. 리더에 장애가 발생해 다운되었다. 
2. timeout이 끝난 팔로워가 후보자가 된다. 
3. 후보자는 다른 팔로워에게 투표를 권고하는 요청을 보낸다 (RequestVote RPC)
4. 팔로워가 후보자의 term과 index를 확인한다. 
5. term과 index를 기반으로 팔로워가 투표한다. 

이제 term과 index를 기반으로 투표하는데 어떤 기준으로 투표하는지에 대해서 정리해보겠습니다. 

 

팔로워는 다음과 같은 규칙을 따릅니다. 

 

• 자신보다 term이 같거나 높은 후보자에게 투표를 던진다. 
• 만약 term이 같다면 index가 높은 후보자에게 투표한다. 
• term이 낮거나 term과 index모두 자신보다 낮은 후보자에게는 투표하지 않는다. 

이로써 리더가 되는 후보자들은 모두 최신의 로그를 가지고 있어야 리더로 선출될 수 있습니다. 

 

이 과정을 틀린 가정을 기반으로 모순을 도출해내 이 틀린 가정이 어떻게 틀렸고 어떻게 일관성을 유지하고 있는지 정리해봤습니다. 

 

틀린 가정 : 리더T가 있고 리더T에 장애가 발생한 상황에서 후보자U가 새로운 리더로 선출되었다는 과정에서 후보자U는 리더T보다 로그가 뒤쳐져있으면서 리더로 선출되었다는 가정입니다. 우리는 앞서 term과 index로 리더로 선출될 후보자들은 항상 최신의 로그를 가지고 있다고 이야기했습니다. 이 가정 속에선 후보자U가 리더T보다 로그가 뒤쳐져 있는 상태에서 리더가 될 수 없는 것을 증명하려고 합니다. 

 

1. 리더T가 term이 3이고 index가 10인 상태에 대한 로그A를 커밋하고 장애가 발생해 죽어버린 상황.
2. 리더T가 로그A를 커밋했다는 것은 기존 서버들 중 과반수가 로그A를 가지고 있다는 뜻이 됩니다. 
3. 이 상태에서 후보자U가 리더로 당선 되었다는 것은 과반수로 후보자U에게 투표를 던졌다는 뜻입니다. 이 때 후보자U를 뽑은 서버들을 voter라고 칭하겠습니다. 
4. 리더T가 과반수에 로그A를 복제했기 때문에 voter는 로그A를 가지고 있습니다. 
5. voter는 로그A를 지우지 않습니다. 왜냐하면 팔로워는 로그를 쓰지 않고 리더 또한 기존 로그를 덮어쓰지 않기 때문입니다. 
6. voter가 후보자에 투표하기 위해선 후보자가 voter보다 높은 term을 가지고 있거나 같다면 높은 index를 가지고 있어야합니다. 
7. 그러므로 후보자U는 낮은 버전의 로그를 가지고는 리더에 당선될 수 없습니다. 

이 과정은 논문에서 설명하는 과정을 제가 조금 쉽게 풀어서 설명한 것인데 논문에서 설명한 방식 자체가 이해하기 쉬운 버전이 아니라 나름 쉽게 만들었는데도 이해하기가 쉽지 않네요.. 

 

쿠버네티스가 Raft 알고리즘을 활용하는 방법

Raft 알고리즘은 리더가 무언가를 해야하는 Zookeeper나 Kafka같은 시스템에서 주로 사용될 것 같지만 분산 시스템에서 상태를 일관성있게 유지해야하는 쿠버네티스에서도 Raft 알고리즘을 사용합니다. 

 

쿠버네티스는 etcd에서 Raft 알고리즘을 사용하는데 여기서 의문이 들었습니다. Raft 알고리즘은 분산 시스템에서 상태를 일관성 있게 유지해야하는데 etcd는 Control Plane에 하나만 존재하는데 어떻게 분산으로 관리한다는거지? 라는 생각이요. 

 

처음엔 멀티 클러스터에서의 etcd를 생각했지만 그게 아니고 etcd는 쿠버네티스 클러스터 내에 물리적으로는 하나만 존재하지만 논리적으로는 여러개의 노드에 나눠져 존재하고 있습니다. 

 

이 etcd에서는 쿠버네티스 클러스터 내부의 리소스 상태나 어떤 파드가 생성되어있는지 어떤 노드에 파드를 배치하면 안되는지와 같은 상태를 반드시 일관성있게 관리해야합니다. 

 

때문에 논리적인 etcd가 하나 죽더라도 물리적인 etcd에 영향을 끼치면 절대절대 안되는 상황이죠. 만약 물리적인 etcd에 영향을 끼친다면 쿠버네티스 클러스터 전체가 영향을 받아 온전하게 동작하지 않는 상태가 발생하기 때문에 etcd가 반드시 쿠버네티스 클러스터 내부에서 살아있어야합니다. 

 

이 때 Raft 알고리즘이 도움이 됩니다. etcd가 Raft 알고리즘으로 쿠버네티스 클러스터 내부의 상태를 일관성 있게 관리하여 쿠버네티스 클러스터를 죽지않도록 관리하는데 Raft 알고리즘을 사용하는 것이죠. 

 

etcd는 쿠버네티스에서 뇌같은 존재입니다. 단순히 쿠버네티스 내부의 데이터베이스가 아니고 etcd에 적재된 정보를 기반으로 쿠버네티스가 어떻게 행동할지에 대한 기준이 됩니다. 

 

그렇기에 etcd는 논리적으로 반드시 세개 이상 존재하는 것이 권장되고 과반수 투표를 위해 홀수개로 유지하는 것이 권장됩니다. 

 

마치며

사실 Raft 알고리즘에 대한 포스팅 내용인데 쿠버네티스 카테고리에 넣은 것은 Raft 알고리즘을 어디 따로 빼둘 카테고리가 없었기 때문입니다. 

 

쿠버네티스가 Raft 알고리즘을 이용해서 etcd를 관리하고 있기 때문에 명분이 생겨 쿠버네티스 카테고리에 Raft 알고리즘을 소개해봤습니다. 

 

근데 내용이 진짜 어려웠습니다. Raft 알고리즘 말고 Paxos라는 알고리즘은 이론적으로는 완벽에 가까운 합의 알고리즘이지만 굉장히 어렵다고 소문이 났는데 저는 Raft 알고리즘도 머리 터질뻔 했습니다... Paxos는 어느정도일지 쳐다도 보기 싫네요. 

 

이런 깊이있는 내용은 지피티가 헛소리를 많이 하기에 논문을 바탕으로 쓰게 되었습니다. 확실히 논문을 읽으니 제대로 공부했다는 기분도 들고 좋네요. 

 

이번 포스팅은 여기서 마치도록 하겠습니다. 긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 되세요!