이번 시리즈에서는 In Search of an Understandable Consensus Algorithm
(Extended Version) 를 읽고 정리합니다. 이번 글에서는 다음 부분을 다룹니다:

- Raft 개요: Raft는 일관된 분산 로그를 유지하기 위해 필요한 동작을 리더 선출, 로그 복제, 안전성 3가지 작은 일로 나누어 정리한다.
- 리더 선출: Raft는 투표 과정을 통해 로그 복제를 관리하고 시스템 일관성을 유지할 리더를 선출한다.

Raft 개요

강한 일관성을 보장하는 합의 알고리즘

Raft 는 복제된 로그를 관리하기 위한 알고리즘이다. Raft 알고리즘의 기본 모드에서는 1개의 리더가 write/read 요청을 모두 처리하고, N개의 팔로워가 로그를 복제하는 역할을 한다. 즉, 팔로워는 리더와 다른 팔로워 노드가 죽었을 때를 대비한 백업 역할만 수행한다. Raft 는 강한 일관성을 보장하기 위해 응답 지연을 약간 포기하도록 설계되었다. Kafka (KRaft 버전), MongoDB, RabbitMQ 등에서 Raft 를 사용하고 있다.

제 1 목표: 이해하기 쉬워야 한다.

Raft 알고리즘에는 2가지 목표가 있다. 1순위 목표는 이해하기 쉬운 합의 알고리즘을 만드는 것이고, 2순위 목표는 실제 분산 시스템을 설계하는데 쓰일 수 있는 기반을 제공하는 것이다. 왜 ‘실용적임’보다 ‘이해하기 쉬움’이 우선순위가 더 높냐고 묻는다면, 그렇지 않은 분산 시스템은 이해하기가 너무 어렵고 구현하기 까다로워서 제대로 써먹는데가 없기 때문이다. Raft 와 비교되는 Paxos 라는 알고리즘이 그렇다.

이해하기 쉬운 분산 시스템 합의 알고리즘을 만들기 위해 아래 두가지 전략을 사용했고 Raft 가 탄생했다.

• Divide and Conquer
• 고려해야 할 상태 수를 줄이고 최대한 단순화

하나씩 살펴보자.

Divide and Conquer

컴퓨터 공학 알고리즘을 공부하면서 항상 마주치는 그 divide and conquer 가 맞다. 논문에서는 ‘합의 알고리즘’이라는 복잡해보이는 알고리즘을 다음 3가지 부분으로 나누어 하나씩 정복하는 과정이 나온다.

• Leader election: 지금 존재하는 리더에 장애가 생겼을 때 반드시 새로운 리더가 선택되어야한다.
• Log replication: 리더는 반드시 클라이언트로부터 로그 엔트리를 받고 클러스터 내에서 이를 복제해야 하며, 다른 로그도 '동의'하게 만들어야한다.
• Safety: Raft 의 안전성은 State Machine Safety 로부터 나오며, 이 성질은 리더 선출 메커니즘에 제약 조건을 추가함으로써 보장할 수 있다.

고려해야 할 상태 수를 줄이고 최대한 단순화

여기서 말하는 ‘상태’는 분산 시스템 클러스터의 전체적인 상태를 말한다. 예를 들어 ‘리더 노드 1개가 죽었음’, ‘팔로워 노드 1개를 제외한 나머지 리더, 팔로워 노드가 모두 죽었음’, ‘리더 선출 과정이 끝나지 않았는데 갑자기 자신이 리더라고 주장하는 노드가 나타남’ 같은게 있다. (보기만 해도 재밌는 마음이 아픈 상황!)

Raft 에서는 저런 시나리오 하나하나를 신경쓰지 않아도 되도록 상황을 심플하게 해결하고자 했다. 저런 상황을 완전히 방지할 수는 없지만 최대한 빠르게 복구될 수 있도록 만든 것이다. 그 예시 중 하나로 ‘리더에게 모든걸 맡기는’ 부분이 있다. P2P 가 아닌 리더-팔로워 구성이기 때문에 로그 복제 과정이 간결해진 것이다.

어떻게 작동하나요? 쓱 훑어보기

Raft 의 전반적인 동작 방법을 간단하게 알아보자. 훑어보기 편하게 짧게 정리해보면…

• Raft 클러스터는 일반적으로 5개 노드로 구성
• 각 서버는 다음 3가지 역할 중 하나를 함: 리더, 팔로워, 후보
  • 정상적인 상황에서 항상 1개의 리더만 존재
    • 리더가 모든 클라이언트 요청을 처리
      • 만약 클라이언트가 팔로워에게 요청을 보냈다면 팔로워는 리더로 그 요청을 리다이렉트
  • 팔로워는 수동적: 리더나 후보의 요청을 받아들이기만 하고 스스로 요청을 만들어내지 않음.
  • 후보는 새로운 리더 선출 과정을 위한 역할
• Raft 에서는 시간을 임의의 길이로 쪼개어 term 으로 관리. 즉, 일종의 logical clock,
  • 새로운 term 의 시작 시점: 리더 선출이 시작될 때
  • term 이 종료되는 시점
    • 새 term 이 시작되기 전
    • 투표에서 리더를 선출하지 못했을 때
  • 즉, 하나의 term 에는 최대 1개 (!= 정확히 1개)의 리더가 존재
• 각 서버는 자신의 current term 을 갖고, 다른 노드와 통신할 때 항상 이걸 주고받는다.
  • 다른 서버보다 작은 term 을 갖고 있는 서버는 그보다 큰 값으로 업데이트
  • 리더가 자신의 term 이 다른 서버보다 작다는걸 인지하면 즉시 팔로워 역할로 돌아감.
  • 자신의 term 보다 작은 값을 가진 요청이 들어왔다면 해당 요청은 무시
• Raft 에서 서버끼리의 통신은 RPC 를 통해 이루어 짐
  • 만약 시간 내에 응답을 받지 못했다면 계속 재전송
  • RPC 전송은 병렬 처리

… 대략 이렇게 된다. 이번에는 Raft 노드 중에서 핵심 역할을 맡고 있는 리더 노드를 어떻게 선출하는지 알아보자. 리더 선출은 divide and conquer 를 통해 찾은 3가지 미션 중 하나이기도 하다.

리더 선출

언제, 어떻게, 왜 하는가?

Why?

가장 쉬운 답변부터 해보자. 왜 하는가? 리더 역할 노드가 있어야 사용자 요청을 받아들이고 로그 복제를 관리하는 주체가 생기기 때문이다. 즉, Raft 에서 P2P가 아닌 리더-팔로워 아키텍처를 선택했기 때문이다.

When?

그렇다면 리더 선출을 언제 해야하는지 알아보자. 직관적으로 대답하기는 쉽다. ‘리더가 없을 때, 그러니까 맨 처음 클러스터가 시작했을 때나 살아있던 리더에 장애가 발생했을 때’이다. 그러면 이 상황을 어떻게 알아챌 수 있을까?

먼저 맨 처음 클러스터가 시작할 때 리더를 선출하는 방법은 쉽다. 사실 선출 과정이 필요없다. 클러스터 초기 설정값에 어떤 노드가 리더가 될지 셋팅해주면 되기 때문이다. 문제는 그 다음이다. 잘 동작하던 리더 노드에 문제가 생겼다는 사실을 ‘자동으로’ 알아채고 ‘자동으로’ 선거를 시작할 방법이 필요하다.

리더 선출을 트리거하기 위해 heartbeat 메커니즘을 사용한다. 리더 노드는 자신이 살아있음을 모든 팔로워에게 일정한 주기로 전송한다. 노드 간 통신은 RPC 를 사용하고 병렬 전송한다고 하였으니 이 heartbeat 도 RPC 를 통해 병렬적으로 전송한다.(그렇지 않으면 느리다!) 이 RPC 를 AppendEntries RPC 라고 하자. 리더는 내용물이 비어있는 빈 AppendEntries RPC 를 팔로워에게 전송한다.

팔로워는 리더가 일정 시간이 지나도록 heartbeat 를 전송하지 않으면 리더 노드에 문제가 생겼다고 간주하고 새 리더를 뽑기 위한 투표를 시작한다. 이 때 ‘일정 시간’을 election timeout 이라고 한다. Election timeout 이 바로 리더 선출을 위한 트리거인 것이다.

그러면 election timeout 은 어떻게 정할까? 어떻게 해야 리더가 멀쩡하게 살아있는 상황과 장애가 생긴 상황을 구분할 수 있는 적절한 값을 찾아서 정할 수 있을까? 잘 살아있는 리더가 보낸 AppendEntries RPC(heartbeat) 가 팔로워에게 미처 도달하기 전에 election timeout 이 발생하면 곤란하다. 또한 서로 다른 두 팔로워가 동일한 election timeout 값을 가져서 동시에 타임아웃이 발생해서도 안된다. 그러면 두 팔로워가 동시에 선거를 시작할 것이고 서로에게 투표 요청을 보내는 등 복잡한 상황이 생길 수 있다.

Raft 에서는 앞서 말한 것처럼 최대한 심플한 방법을 택했다. 랜덤으로 각 노드별 election timeout 을 할당하는 것이다. 이 랜덤값은 새 term 이 시작될 때마다 계속 바뀐다. 가능한 1개의 서버만 election timeout 이 발생하도록하여 split vote 를 방지하기 위해서다.

물론 이 때 랜덤 값의 범위는 정해놓는다. 리더가 보낸 AppendEntries RPC(heartbeat) 가 팔로워에게 도달할 정도의 시간은 벌어야 하기 때문이다. 논문에서는 고정된 값의 election timeout 을 지정하면 자꾸 코너 케이스가 생겨서 알고리즘이 복잡해졌다고 언급했다.

요약하자면, 팔로워가 선거를 시작하며 그 시점은 리더가 보낸 heartbeat 신호를 받지 못한 채 자신의 election timeout 이 지났을 때이다.

How?

선거를 시작하기 전에 이해해야 하는 개념이 하나 있다. 바로 ‘Quorum 정족수’ 개념이다. 정족수는 제안이 합의가 되기 위해 제안에 찬성해야 하는 노드의 최소 개수를 의미한다. 예를 들어 전체 노드가 5개이고 정족수가 2일 때, ‘1번 노드가 리더다.’ 라는 제안에 대해 최소 2개 노드만 찬성표를 던져도 모든 노드는 1번 노드가 리더라고 생각해야 한다.

여기서 정족수의 중요성이 나타난다. 전체 노드가 5개, 정족수가 2라면 이상한 상황이 벌어질 수 있다. 1번과 2번이 ‘1번이 리더다’에 찬성하고 3번과 4번이 ‘3번이 리더다’에 찬성했다면 ‘리더는 1번과 3번이다’가 최종 합의가 되어버리기 때문이다. 그래서 합의 알고리즘에서는 정족수로 과반수를 사용한다.

• 과반수는 전체 개수의 절반이 넘는 수를 의미한다. (절반이 아니다. 절반보다 많아야 한다.)
  • 전체가 홀수인 경우: (N + 1) / 2
    • 따라서 전체 노드가 5개일 때 올바른 정족수는 3이다.
  • 전체가 짝수인 경우: N / 2 + 1
    • 따라서 전체 노드가 6개일 때 올바른 정족수는 4이다.

자 이제 선거가 시작되면 어떻게 되는지 알아보자. 그리고 ‘진짜로 랜덤 timeout을 두면 모든게 해결되는지’도 알아보자.

1. 특정 팔로워가 자신의 election timeout 이 지나도록 리더의 heartbeat 를 받지 못함
2. 팔로워가 자신의 term 값을 올리고 후보 역할이 됨 - 이 후보를 C₁ 이라고 하자.
   1. term 은 Raft 에서 논리적 시계 역할을 한다고 하였다. ‘어떻게 작동하나요? 쓱 훑어보기’ 부분을 참고하자.
3. C₁ 이 자기 자신에게 1표를 던지고 RequestVote RPC 를 다른 서버에게 발행
   1. C₁ : 야 우리 리더 죽은거같은데 새로 하나 뽑아야겠다. 일단 나 후보로 등록하고 찬성표 하나! 너네도 답장 줘
   2. 리더 선출이 되기 위한 조건인 '과반수의 찬성표'에서 '과반수'에는 C₁ 자기자신도 포함된다.
4. 아래 3가지 상황이 발생하기 전까지 C₁ 은 후보 상태로 대기

여기까지는 심플하다. 그런데 3가지 상황은 어떤 상황일까?

• C₁ 이 리더로 결정됨
• 투표가 끝나기 전, C₁ 이 아닌 다른 서버로부터 heartbeat 를 받음
• Split Vote: 리더가 뽑히지 못한 채로 시간이 흐름

각 상황이 어떻게 발생할 수 있는지 (how), 발생한 다음에는 어떻게 되는지 (and) 살펴보자.

4-1. C₁ 이 리더로 결정됨

• how? 동일한 term 에 대해 과반수의 서버가 C₁ 이 리더임에 동의한 경우.
  • 각 서버는 하나의 term 에 대해서 최대 1개의 후보에게만 찬성표를 던질 수 있다.
    • 찬성표를 받을 후보를 고르는 기준: FIFO. 나한테 제일 먼저 받은 RPC 가 있을 것이다. 그걸 보낸 팔로워한테 찬성표를 던진다.
    • 새 투표가 시작될 때마다 term 값이 바뀌기 때문에 각 서버는 투표별로 최대 1개의 후보에게만 찬성표를 던진다는 사실이 보장된다. 따라서 하나의 투표에 대해 2개의 리더가 선출될 수는 없다.
• and? 리더가 된 C₁ 은 나머지 서버에게 heartbeat 을 보낸다. 이 때 새 term 값도 같이 전송된다.
  • 원래 팔로워였던 노드는 더 큰 term값으로 heartbeat 가 들어왔군. 내 current term 도 업데이트하고 리더 노드 정보도 업데이트해야겠어 라고 판단한다.
  • 원래 리더였던 노드는 장애가 복구된 다음 C₁ 의 메세지를 받고서 term 값이 내가 갖고 있던거보다 크고 heartbeat 메세지다. 내가 죽은 사이에 새 리더가 생겼군 하고 팔로워 상태로 돌아간다.

4-2. 투표가 끝나기 전, C₁ 이 아닌 다른 서버로부터 heartbeat 를 받음

• and? Heartbeat 에 있는 term 이 C₁ 의 것보다 크다면: Heartbeat 를 보낸 노드가 리더임을 인정하고 C₁ 은 팔로워 역할이 된다.
  • how? 어떻게 C₁ 의 투표 도중에 C₁의 term 보다 큰 누군가가 heartbeat 를 보낼 수 있었을까?
    • 먼저 C₁ 의 term 보다 큰 term 을 갖고 있었다는 것은 새 투표가 시작되었다는 것을 의미한다. term 값은 새 투표가 시작될 때마다 커지기 때문이다.
    • 새 투표가 시작되었다는 것은 곧, 어떤 팔로워 노드(C₂ 라고 하자.)의 election timeout 이 지났음을 의미한다.
    • 투표 도중에 C₂ 의 election timeout 이 지나는 케이스는 충분히 발생할 수 있다. 투표 도중 네트워크 상태가 나빠져서 그 election timeout 이 지나도록 투표가 완료되지 않았을 때를 생각해볼 수 있다. 즉, 투표 과정이 너무 오래 걸려서 클러스터 전체가 지연되는 케이스는 발생하지 않음을 알 수 있다. 지금처럼 새 투표가 시작될 것이기 때문이다.
      • C₂: 아 모르겠고 난 election timeout 지났으니까 새 투표 시작합니다~ 나 후보로 바꾸고 찬성표 1개 던짐. 너희도 답장 줘
        • 이렇게하면 알고리즘은 간단해진다. ‘나의 Election timeout 은 지났지만 누군가에 의해 투표가 시작되었고 그게 끝나지 않았을 때’ 따위의 코너케이스는 고려하지 않아도 되기 때문이다.
• and? Heartbeat 에 있는 term 이 C₁ 의 것보다 작다면: 무시. 다시 대기 상태로 돌아간다.
  • how? 어떻게 C₁ 의 투표 도중에 C₁ 의 term 보다 작은 누군가가 heartbeat 를 보낼 수 있었을까?
    • 위 예시와 반대다. 위에서 C₁ 과 C₂ 를 바꿔서 대입해보면 바로 이 케이스가 된다. 어떤 팔로워 노드가 시작한 선거가 완료되기를 기다리다가 자신의 election timeout 이 끝나버려서 또 새로운 투표를 시작한 케이스다.

4-3. Split vote: 리더가 뽑히지 못한 채로 시간이 흐름

• how?
  • 리더가 되기 위해서는 과반수의 찬성표를 받아야 한다.
  • 아무도 리더가 되지 못했다는 것은 아무도 과반수의 찬성표를 받지 못했다는 것을 의미한다.
  • 주로 여러 팔로워가 동시에 후보 역할이 되었을 때 발생한다. 후보 역할이 된 노드는 새 선거를 만들면서 자기 자신에게 이미 찬성표를 던진 상태이기 때문이다.
• and?
  • 시간이 지나고 election timeout 이 만료되면 각 서버는 또 새로운 선거를 시작한다. 자신의 term 값을 올리고 RequestVote RPC 를 보내고 election timeout 값을 랜덤으로 설정한다.
  • 이론상, 이 상황이 영원히 유지될 수도 있다.

어라! 커버하지 못하는 케이스가 발견되었다. 하지만 이는 말 그대로 ‘이론상’의 일이다. Split vote 가 영원히 유지되려면 일정 범위 내에서 거의 몇 ms 차이로 아주 비슷한 값의 election timeout 값이 클러스터 내의 모든 노드에게 할당되어야 한다. 하지만 우리는 랜덤 알고리즘을 쓰기 때문에 그렇게 될 확률은 매우 낮다. 그러려고 랜덤을 쓰는 것이다.

정리

리더-팔로워 구조인 Raft 에서는 리더 선출 과정을 단순화하기 위해 몇가지 전략을 사용했다.

• Election timeout 은 랜덤으로 할당한다.
• 동시에 여러개의 선거가 이루어지는 것을 막지 않는다.

또한 최대 1개의 리더만 존재할 수 있도록 안전장치를 마련했다.

• RPC 메세지의 term 값과 자신의 term 값을 비교하여 무시할 건 무시하고, 따라야 할 메세지만 따른다.
• 각 노드는 하나의 선거에서 최대 1개의 후보한테만 찬성표를 던질 수 있다.

이를 통해 고려해야 할 상황의 수를 줄이고 이론상으로 발생 가능한 split vote 상황을 최대한 방지하고자 했다. (카프카, 몽고DB, RabbitMQ 등 상용 프로그램에서 쓰이고 있는걸 보면 정말 이론상에서만 발생하는 시나리오인듯하다. 혹은 사용하는 쪽에서 약간의 커스텀을 했거나..!)

다음 포스팅에서는 로그 복제 과정을 자세히 알아보자. 데이터 일관성을 지키기 위해 역시나 term 값을 활용한다.