🦄 합의 알고리즘 Raft 논문 읽기 - 2. 리더의 역할

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

• 리더 노드의 역할 2가지: 클라이언트 요청 처리, 로그 복제
• 로그 복제: 리더 노드는 로그 복제를 시작하고, 팔로워 노드는 ACK를 보낸다. 로그는 복제, 커밋, 적용된다.

다 뽑았니? 이제 할 일을 하자

지난 글에서는 raft 알고리즘에서 리더 선출을 하는 방법을 알아보았다. 이번에는 대체 리더가 무슨 일을 어떻게 해야 하길래 그렇게 열심히 뽑았는지 살펴보자.

리더의 역할

Raft 시스템에서 리더 노드는 크게 2가지 역할을 한다.

• 클라이언트의 요청을 처리하고
• 팔로워 노드에게 로그 복제가 이루어지도록 총괄한다.

클라이언트의 요청 처리

‘클라이언트의 요청 처리’에서의 클라이언트가 뭔지 헷갈릴 수 있다. 여기서 말하는 클라이언트는 raft 알고리즘으로 동작하는 분산 시스템의 클라이언트를 말한다. 예를 들어 몽고DB에서 raft 알고리즘을 사용 중이라면 이 때 클라이언트는 몽고DB로 요청을 보내는 클라이언트가 되고, ‘클라이언트의 요청’은 새로운 데이터 생성, 수정 등 우리가 하는 일반적인 CRUD 연산이 된다.

리더 노드가 클라이언트의 요청을 처리한다는 건, 다른 팔로워 노드는 그 요청을 처리하지 않음을 의미하기도 한다. 즉, raft 알고리즘을 사용하는 상태 기계(state machine)의 상태에 변경이 생겨야 한다면 그 변경 요청을 받아들이는 엔드포인트는 항상 리더 노드가 된다. 노드 하나만 요청을 처리할 수 있다니 너무 비효율적이지 않을까? 라고 질문할 수도 있겠다. 그래서 읽기 연산은 팔로워 노드에게도 보내거나 lease 모드, quorum reads 를 쓰는 등 raft 를 변형한 여러가지 알고리즘이 쓰인다. 실제로 몽고DB에서는 레플리카 셋에 대해 raft 알고리즘 변형 버전을 사용한다.

로그 복제

Raft 알고리즘을 쓴다는 건 리더-팔로워 노드가 존재하고 그 노드들이 서로 같은 데이터 상태를 유지해야함을 의미한다. 그것이.. 합의 알고리즘의 목적이니까..! 이 목적을 달성하기 위해 리더 노드는 이런 일을 하게 된다.

• 로그 복제 요청
• 로그 복제 요청에 대한 ACK 처리
• 로그 복제 요청 재시도

앞서 봤듯이 리더 노드만 클라이언트의 요청을 받아들이기 때문에 팔로워 노드는 클라이언트가 요청을 보냈다는 사실을 알 수 없다. 대신 리더 노드가 먼저 팔로워 노드에게 로그 복제 요청을 보낸다. 팔로워 노드는 그 요청을 받으면 그제서야 로그 복제에 참여하게 된다.

로그 복제 요청에는 팔로워 노드에 반영해야 할 데이터가 들어있다. 0번 key에 대한 값을 10으로 업데이트 와 같은 식이다. 팔로워 노드는 이 요청을 받아서 자신의 로그에 추가한 다음 이 사실을 리더에게 다시 알린다. ACK를 보내는 것이다. 리더는 어떤 팔로워가 ACK를 보냈는지, 즉 누가 로그 복제에 성공했는지를 지켜본다.

과반수 이상이 로그 복제에 성공했다는 ACK를 보냈다면 그 로그 엔트리는 리더 노드에게 적용해도 되는 엔트리가 된다. 리더 노드의 상태 기계(state machine)의 0번 key 값을 바꾸는 시점은 바로 이 때가 된다. 만약 과반수 이상의 ACK를 확보하지 못했다면 리더는 계속해서 로그 복제 요청을 보낸다. (로그 복제 요청 재시도)

AppendEntries RPC

여기까지 읽어보았다면 노드 간 통신 속도가 상당히 빨라야할 것 같다는 생각이 들 것이다. Raft 에서는 RPC 를 사용해 각 노드 간 데이터를 주고받는다. 리더가 팔로워 노드에게 보내는 RPC 는 병렬로 전송된다. Raft 알고리즘 안에서 보내는 여러가지 RPC를 목적에 따라 이름 붙였는데, 로그 복제 요청은 AppendEntries RPC 를 통해 전달된다. 로그 복제 요청인데 왜 뭔가 추가한다는 의미의 Append 를 썼을까?

위의 로그 복제 과정을 다시 살펴보자.

로그 복제 요청에는 팔로워 노드에 반영해야 할 데이터가 들어있다. 0번 key에 대한 값을 10으로 업데이트 와 같은 식이다. 팔로워 노드는 이 요청을 받아서 자신의 로그에 추가한 다음 …

팔로워 노드한테 들어간 건 값을 ‘변경’하라는 요청인데, 팔로워는 이걸 ‘자신의 로그에 추가’ 한다고 했다. 그렇다면 업데이트는 하지 않는걸까?

정답은 ‘아니다’. 업데이트도 일어난다. 그 대상이 다를 뿐이다.

Raft 에 참여하는 리더, 팔로워 노드에는 변경 사항이 생겼다는 사실이 쌓이기만 한다. 업데이트는 ‘Raft 를 사용해서 관리되고 있는 상태 기계(state machine)’에 일어난다. 즉, 0번 key와 그 값은 상태 기계에 저장된다. 리더, 팔로워 노드는 그 상태 기계에 일어난 변화에 대한 기록을 남기는 역할을 하는 것이다. 비유하자면 상태 기계는 데이터베이스, 리더와 팔로워 노드는 메세지큐처럼 데이터를 다룬다고 생각해볼 수 있다.

그림을 그리면 이렇게 된다. 리더와 팔로워가 저장하는 로그에는 각 키별로 일어난 값의 변화가 그대로 저장되고, 값의 변경은 state machine 에 반영된다. 클라이언트가 0번 key 에 대한 값을 요청한다면 state machine 의 것을 읽어서 돌려주는 것이다. 그림에서 마지막으로 과반수 이상의 노드에 로그가 복제된 사실은 key: 0, value: 10이기 때문에 리더 노드는 자신의 state machine 에 그 사실을 반영한 상태이다. 이 때 ‘과반수’를 판단할 때는 리더 자기자신도 포함되기 때문에 노드 2개에 복제된 로그는 과반수 이상이 복제한 로그라고 본다.

Committed Log Entry 커밋 된 로그

과반수 이상이 복제에 성공한 로그 엔트리를 ‘commit 되었다’고 표현한다. 리더는 가장 최근에 커밋된 로그 엔터리의 인덱스를 갖고 있으면서 팔로워에게 AppendEntries RPC 를 보낼 때마다 같이 보낸다.

이 때 주의할 점은 커밋된 로그와 적용한 로그가 다르다는 사실이다.

• 커밋 된 로그: 과반수 이상이 복제한 로그
• 적용(apply) 한 로그: 리더/팔로워 노드가 자신의 상태에 적용한 로그

팔로워는 리더의 AppendEntries RPC 에 들어온 ‘마지막으로 커밋된 엔트리 인덱스’를 본 다음에야 그 엔트리를 자기 자신에게 적용한다. 즉, 팔로워가 ACK 를 보내기 전까지도 자신의 state machine 에는 아직 그 엔트리가 적용되지 않은 상태인 것이다. 로그 엔트리 하나에 대한 처리는 아래 순서로 진행된다.

1. 리더 노드가 클라이언트의 요청을 받음
2. 리더 노드는 자신의 로그에 새로운 엔트리를 추가
3. 리더 노드가 팔로워 노드에게 병렬로 AppendEntries RPC 를 전송 (로그 복제 요청)
4. AppendEntries RPC 를 받은 팔로워 노드가 자신의 로그에 엔트리를 추가한 다음 리더에게 ACK를 전송
5. 과반수 이상의 팔로워로부터 ACK를 받았다면, 리더는 추가한 엔트리를 커밋된 상태로 표기하고 자신의 state machine 에 엔트리의 내용물을 적용
6. 팔로워 노드는 다음 AppendEntries RPC를 받고 ‘마지막으로 커밋된 엔트리 인덱스’를 확인하여 그 엔트리에 해당하는 내용물을 자신의 state machine 에 적용

정리

• 리더 노드의 역할은 크게 2가지다: 클라이언트의 요청을 처리하고 팔로워 노드에 대한 로그 복제를 담당한다.
• 리더는 로그 복제를 위해 AppendEntries RPC 를 보내고, 팔로워는 이를 받아서 처리한다.
• 커밋된 로그와 state machine에 적용된 로그는 다르다.