HA(고가용성)과 Raft 알고리즘
HA를 알고 있는가? HA는 High Available의 줄임말로 노드의 장애 발생 시에도 서비스를 유지하기 위한 방법과 솔루션이다. HA를 이룩하기 위한 여러 방법론이 있지만, 이번에는 Raft 알고리즘을 통한 방법을 살펴보려고 한다.
Raft 알고리즘은 다른 말로 뗏목 합의 알고리즘이라고 하기도 한다. 중요한 건 합의다. 합의라는 건 여러 사람이 뜻을 같이 맞춰 나간다는 뜻이다. Raft 알고리즘은 투표를 통한 다수결로 뜻을 하나로 맞춘다.
Leader와 Follower
Raft 알고리즘은 보통 여러 노드가 있을 떄, 그 리더 노드를 한 명 뽑고, 나머지 노드들을 팔로워로 만드는 과정이다. 현실 세계에서도 마찬가지이다. 예를 들어, 대통령을 뽑을 때에도 국민들 중 한명을 대통령을 뽑고, 뽑힌 대통령은 대통령만의 역할을 수행하고 나머지 국민들은 국민들만의 역할을 수행하게 된다. 우리는 대통령을 뽑을 때 선거라는 이름의 투표를 하게 된다. Raft알고리즘은 이를 흉내내기 때문에, 선거에서 쓰이는 단어들이 많이 사용된다.
리더의 최소 조건 : 살아 있어야 된다.
다만, 현실의 대통령 선거의 Raft 알고리즘의 차이는 있다. 먼저, 현실의 대통령을 여러 자질을 평가해서 투표한다. 하지만 Raft 알고리즘은 굳이 그럴 필요는 없다. Raft 알고리즘에선 살아있는 것 만으로도 충분히 리더가 될 수 있는 자격을 얻는다.
과반수 이상의 동의를 얻어라!
현실의 대통령은 굳이 국민들의 과반수 이상을 얻을 필요는 없다. 그저 다른 후보자들에 비해 더 높은 득표율을 얻게 되면 성공한다.
Raft 알고리즘에서의 투표용지는 A 후보자가 리더가 되는 데 동의하십니까?라고 적혀 있다. 다른 후보자는 따로 생각하지 않는다. 이 때 A 후보자가 과반수 이상의 동의를 얻었다면. A는 리더가 될 수 있다.
정족수 (Quorum)
정족수는 방금 설명한 과반수이다. 예를 들어 투표에 1233명이 참가했다고 하자. 과반수는 (n/2)에서 정수로 올림으로 구할 수 있으므로 617명이 정족수라고 할 수 있다.
정족수를 위해 고려해야 할 점이 있다. 바로 투표에 참여하는 인원은 즉, 노드는 최소 3명 이상여야 한다는 점이다. 참여자가 한 명 혹은 두 명이면 안된다. 생각해보면 간단하다. 국민이 1명인 나라에서 대통령을 뽑는 것은 의미없다. 국민이 2명인 나라는 대통령 선거가 잘 될리가 없다. 왜냐하면 2명 서로 대통령하겠다고 우길 것이니깐...
노드의 개수는 보통 홀수가 권장된다. 짝수여도 큰 상관은 없지만, Raft 알고리즘 과정에 굳이 없어도 큰 상관이 없는 노드가 있게 되고, 이게 곧 노드의 낭비가 될 수 있다.
Raft 알고리즘의 과정
다음과 같이 1개의 리더와 3개의 팔로워 노드를 가지는 구성을 생각해보자
1. 평상시에
평상시에 각 노드들은 각자의 역할에 맞는 일을 수행한다. 보통 리더가 하는 일이 많을 것이고, 팔로워들은 리더의 데이터를 복제한다던지, 리더가 하지 않는 부가적인 역할을 수행할 수 있다.
각 노드들은 주기적으로 Heartbeat를 돌며 다른 노드들의 생사여부를 확인한다. 보통 상대방 노드와 통신이 잘되면 살아 있다는 뜻이며, 상대방 노드와 통신이 잘 되지 않는다면 상대방 노드는 죽었다고 판단할 수 있다.
가장 중요한 Heartbeat는 역시 리더와 팔로워간의 Heartbeat이다. 팔로워들은 리더와의 통신이 잘 안되면 본인이 따르고 있던 리더가 죽었다고 판단할 것이다.
2. 리더의 이상 발생과 첫번째 투표
각 노드들은 리더와 통신두절이라고 바로 리더에 이상이 발생했다고 판단하지는 않는다. 대신에 다른 팔로워들과 소통하며 정말로 리더가 죽었는 지 확인한다. 이 때 첫번째 투표가 발생하는데, 팔로워들의 투표결과 과반수 이상이 리더가 죽었다고 동의하면 정말로 리더가 죽었다고 판단할 수 있다.
3. 입후보와 두번째 투표
팔로워들은 리더가 죽었다고 판단되면, 본인 스스로 리더가 되고 싶어서 바로 입후보를 낸다. 입후보를 다른 팔로워들한테 내게 되면, 입후보를 받은 팔로워는 신청한 팔로워가 특별한 문제가 없다면 리더로 선출될 것을 동의하게 된다.
이상한 점이 하나 있을 것이다. 모든 팔로워들이 입후보를 내고 모두 후보자가 된다는 것이데, 본인이 후보인데 다른 후보자에게 투표를 하는 바보가 어디있겠는가? 하지만 Raft 알고리즘에서는 가능할 수 있다. 여러 조건에 맞게 리더를 양보할 수 있는데, 가장 쉽게 생각할 수 있는 아이디어는 본인보다 먼저 입후보를 낸 후보자에게 리더를 양보한다는 것이다.
4. 새로운 리더의 선출
본인이 입후보를 낸 결과 과반수 이상의 후보자들에게서 득표를 얻었다고 판단한 후보자는 본인 스스로 리더로서 등극한다. 그리고 이 사실을 다른 후보자들에게 알림으로서 2대 리더와 팔로워들의 역할이 결정지게 된다. 리더는 따로 설정된 게 없다면 주구장창 독재를 유지하면 리더가 될 것이며, 팔로워들은 평생 리더를 따라야 할 수도 있다.
다만 아까와 같이 리더가 죽어버리는 불상사가 발생하게 되면 새로운 선거는 다시 시작될 것이다.
5. 신규회원 등장
이 상태에서 신규회원이 등장한다면 어떤 일이 발생할까? 신규회원은 노드들을 쓱 둘러보고는 리더가 있다면 순순히 팔로워가 되기를 결심한다. 이는 설령 그 노드가 1대 리더였다고 하더라도, 1대 리더는 본인이 리더였다는 사실을 까맣게 잊은 채 팔로워가 될 수 있다.
Raft 알고리즘이 HA에 쓰이는 이유
HA는 보통 primary와 standby라는 개념으로 설명된다. 어떠한 서비스의 주된 일은 primary노드가 담당한다. 대신 primary가 이상 발생 시 standby가 primary가 되어 일을 이어받아 수행한다.
Raft 알고리즘은 primary와 standby의 확장판이라고 생각하면 된다. 우리는 팔로워라는 이름의 standby 후보를 여러개 가지고 있다. 보통의 일은 리더가 하지만, 팔로워는 리더가 하는 일과 데이터를 계속 동기화하거나 분산 저장한다. 그렇기 때문에 설령 리더가 불상사가 있더라도 팔로워들이 그 역할을 이어받을 수 있는 것이다.
다시 말해 HA가 primary와 standby를 준비해두는 것이라면, Raft 알고리즘은 standby가 여러개일 때 어떤 방식으로 standby를 primary로 승격시킬 지에 대한 알고리즘이라고 할 수 있다.
Raft 알고리즘은 여러 개의 노드로 구성되므로, 이를 클러스터 (혹은 클러스터링)이라고 부르는 경우들이 많다. 그리고 실제로 클러스터링 도구들에서 Raft 알고리즘을 사용해 HA를 구현하곤 한다.
예를 들어
1. Kafka 클러스터
2. Redis 클러스터
3. 쿠버네티스의 etcd 등
이 Raft 알고리즘을 사용하는 대표적인 예들이다.
