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

• 안전성: 데이터 일관성을 보장하는 Raft 알고리즘의 제약 조건과 3가지 속성.

Safety

번역하기 조금 애매한 단어다. 안전성? 신뢰성? 섞어 쓰는 것 같다.

첫 번째 글에서는 리더를 선출하는 방법, 두 번째 글에서는 그렇게 해서 뽑힌 리더의 역할이 무엇인지 알아봤다. 이제 대략 Raft 가 어떻게 돌아가는지는 살펴본 셈이다. 모든 요청을 받아들이고 처리하는 리더를 뽑고, 그런 리더의 백업용으로 팔로워 노드를 둔다. 팔로워는 리더가 보내는 로그를 안전하게 잘 갖고 있다가 리더가 죽으면 선거에 참여하는 후보가 되고, 다시 또 새로운 리더를 뽑는다.

이번 글에서는 로그를 안전하게 잘 갖고 있는게 어떻게 가능한 지, 진짜로 안전하게 잘 갖고 있는게 맞는지 살펴볼 것이다. (역시 이런게 논문의 묘미 아닐까) 논문의 표현을 가져오자면..

이전 섹션에서는 Raft가 어떻게 리더를 선출하고 로그 항목을 복제하는지 설명했습니다. 하지만 지금까지 설명한 메커니즘만으로는 각 상태 머신이 정확히 동일한 명령을 동일한 순서로 실행한다는 것을 보장하기에 충분하지 않습니다.

예를 들어서 이런 일이 일어나지 않도록 안전장치가 필요하다: 팔로워 하나가 잠시동안 사용할 수 없는 상태가 되어 리더의 로그 복제 요청을 못 받아들이고 있다가, 갑자기 새 리더로 선출이 되어서 데이터가 꼬이는 일. 이런걸 막으려면 데이터 일관성을 보장해야 한다. Raft 는 강한 데이터 일관성을 보장하는 알고리즘이다. 진짜 그런지 알아볼 것이다.

Raft 에서는 안전장치 중 하나로 제약 조건을 만들었다. 어떤 서버가 리더로 뽑힐 수 있는지에 대한 조건이다. 이 제약조건과 더불어 Raft 에서 신뢰성을 보장하는 속성인 ‘리더 완전성 속성(leader completeness property)’과 ‘상태 머신 안전성 속성 (state machine safety property)’ 에 대해서도 살펴보자.

제약 조건 - 누가 리더가 될 수 있나

모든 리더 기반 합의 알고리즘에서 리더는 막중한 책임을 갖는다. 그 중 하나가 ‘커밋된 모든 로그 항목을 저장하기’다. 그렇지 않으면 데이터가 유실된 것이다. 따라서 Raft 에서 새로운 리더가 되고 싶은 서버는 바로 직전 텀까지 커밋된 모든 로그를 갖고 있어야 한다. 또한 이를 다른 리더에게 보낼 필요도 없어야 한다. 이걸 바꿔 말하면, Raft 에서 로그 엔트리는 항상 리더 → 팔로워 방향으로만 흐르며 리더는 자신이 갖고 있던 엔트리를 절대 덮어쓰지 않아야 한다.

만약 지금까지 커밋된 모든 로그를 갖고 있지 않다면 Raft 는 그 서버가 리더로 뽑히지 못하도록 막는다. 선거 후보는 리더로 뽑히기 위해 클러스터의 과반수만큼 동의를 얻어야 한다. 그 과반수만큼의 서버들은 후보가 가장 최신 로그를 갖고 있는지 확인하는 역할을 맡는다. 즉, 리더 후보를 제외한 나머지 서버 중 적어도 하나는 가장 최신 로그를 똑같이 갖고 있어야 한다. 그래야 이 후보가 조건을 만족하는지 판단할 수 있기 때문이다. 그렇다면 가장 최신 로그인지는 무엇을 기준으로 판단할까?

간단하다. 인덱스와 텀을 비교하면 된다.로그의 마지막 항목이 서로 다른 텀을 갖고 있다면 더 늦은 텀을 가진 로그가 더 최신이다. 로그가 같은 텀으로 끝난다면, 더 긴 로그가 더 최신이다. 끝!

투표권을 행사하는 서버들은 자신의 로그와 후보 노드의 로그 중 무엇이 더 최신인지 가려낸다. 자신의 로그가 더 최신이라고 판단하면 근 몇달 간 핫했던 키워드인 거부권을 행사하여 투표를 하지 않는다. 정족수를 채우지 못한 후보는 자연스럽게 물러날 것이고, 새 투표가 시작 될 것이다.

‘완전한 리더’ 속성

Raft 에서 보장하는 중요한 성질 중 하나로 리더 완전성 (leader completeness)이 있다. 이 속성은 엔트리 하나가 커밋되었다면 그 텀보다 높은 값을 갖는 모든 텀에 대한 리더의 로그에 그 엔트리가 존재함을 보장한다. 그러니까 한 번 커밋된 메세지는 리더가 바뀌어서 새 텀이 시작되더라도 사라지거나 바뀌지 않고 계속 남아있음을 보장하는 것이다. 따라서 리더가 된 서버는 자신이 리더가 되기 직전까지 모든 엔트리를 갖고 있게 된다.

이 속성이 진짜인지 어떻게 알아낼 수 있을까? 논문에서는 아주 아름다운 증명법을 써서 이 명제가 참임을 밝혀낸다. 바로 귀류법이다. 리더 완전성 속성이 성립하지 않는다고 가정한 다음, 모순을 증명할 것이다.

증명으로 들어가기 전에 미리 알아야 할 속성이 하나 있다. 바로 로그 매칭 속성 (log matching property) 다.

로그 매칭 속성

아래 두 속성을 묶어서 로그 매칭 속성 (log matching property) 이라고 한다. Raft 에서 무슨 일이 일어나도 이 속성은 보장되고 그래야만 한다.

• 만약 서로 다른 두 로그에 똑같은 인덱스와 텀을 가진 엔트리가 있다면, 그 두 엔트리는 동일한 커맨드를 담고 있는다.
  • 즉, 두 엔트리의 내용이 동일하다.
• 만약 서로 다른 두 로그가 똑같은 인덱스와 텀을 가진 엔트리 하나를 포함한다면, 두 로그는 그 엔트리 이전의 모든 엔트리에 대해 동일한 엔트리를 갖는다.

리더는 특정 텀과 인덱스 쌍 하나에 대해 최대 1개의 엔트리만 만들 수 있으며, 한 번 만들어진 엔트리의 인덱스는 바뀌지 않는다. 따라서 첫 번째 속성이 성립한다.

두 번째 속성은 AppendEntriesRPC 를 수행할 때 이루어지는 일관성 체크에 의해 보장된다. 리더는 새 엔트리 복제 요청을 보낼 때 바로 직전 엔트리에 대한 인덱스와 텀도 같이 보낸다. 팔로워는 그 인덱스와 텀 값을 가진 엔트리를 자신이 갖고 있어야만 요청을 받아들이고, 그렇지 않으면 거부한다.

자 이제 완전한 리더 속성이 보장됨을 증명해보자

텀 T 의 리더 leader_T 가 자신의 텀에서 로그 엔트리를 커밋했지만, 어떤 미래의 다른 리더에 의해 그 엔트리가 저장되지 않았다고 가정하자. 그리고 그 미래의 다른 리더를 leader_U, 그 때의 텀을 U 라고 하자. 이 때 U 는 U > T 가 되는 최소값, 즉 T 바로 다음 텀인 경우를 생각해 볼 것이다.

1. 커밋된 엔트리는 리더 선출 시점에 leader_U 의 로그에 없었을 것이다. 리더는 절대 엔트리를 삭제하거나 덮어쓰지 않기로 했기 때문이다.
2. leader_T 는 클러스터의 과반수에 엔트리를 복제했고, 그렇기 때문에 리더가 될 수 있었다. leader_U 역시 클러스터의 과반수로부터 투표를 받았기 때문에 리더가 될 수 있었다. 따라서, 최소한 서버 하나는 leader_T 로부터 엔트리를 받아서 복제하고 leader_U 에게 투표를 한 셈이다. 이 서버가 바로 아래 그림의 S3 이다.

S1이 leader_T, S5가 leader_U 이다. 총 서버가 5개니까 정족수는 3이다.

3. S3는 leader_U 에게 투표하기 전에 leader_T 로부터 커밋된 엔트리를 받아들였어야 한다. 만약 그렇지 않았다면, 현재 텀이 T보다 더 높으니 leader_T 의 AppendEntries 요청을 거절했을 것이기 때문이다.
4. S3는 leader_U 에게 투표할 때에도 그 엔트리를 저장하고 있었다. 가정에 의해 U 는 T 바로 다음 텀이니 그 사이 모든 리더들이 이 엔트리를 갖고 있었을 것이고, 리더는 엔트리를 절대 지우거나 수정하지 않으며, 팔로워는 리더와 충돌하는 경우에만 엔트리를 제거하기로 했기 때문이다.
5. S3 가 S5 를 리더로 투표했다는 것은 S5 의 로그가 그만큼 최신이었음을 의미한다. 그렇지 않았으면 투표를 하지 않았을 것이다. 그런데 이는 두 가지 모순 중 하나로 이어진다.

6-1. 만약 S3 와 leader_U 의 마지막 로그 텀이 같았다면, leader_U 의 로그는 최소한 S3 의 로그만큼 길어야 했을 것이다. 즉, leader_U 는 S3 가 갖고 있는 모든 엔트리를 갖고 있어야 했다. 하지만 이는 모순이다. 맨 처음 우리는 leader_U 가 커밋되었던 엔트리를 갖고 있지 않다고 가정했기 때문이다.

6-2. 그렇다면 S3 와 leader_U 의 마지막 로그 텀이 다르다면 어떻게 될까? 리더의 로그가 더 최신이어야 하기 때문에 leader_U 의 텀이 S3 의 텀보다 컸을 것이다. leader_U 가 갖고 있는 마지막 로그 엔트리를 생성한 이전 리더는, 자신의 로그에 커밋된 항목을 갖고 있었을 것이다. 그렇다면 로그 매칭 속성에 의해 leader_U 의 로그도 커밋된 엔트리를 포함해야 했을 것인데, 이는 모순이다.

1. 이로써 모순이 완성되었다. 따라서 T보다 큰 모든 텀의 리더는 텀 T 에서 커밋된 모든 항목을 포함해야 한다.
2. 따라서 리더 완전성 속성은 항상 보장된다.

역시.. 증명 과정은 재밌다.

상태 머신 안전성 속성

(이 속성도 당연히 보장되어야 할 것처럼 생긴 속성이다. 하지만 진짜로 보장되는지 밝히는게 바로 이 논문의 역할 중 하나다.)

• 어떤 서버가 특정 인덱스와 텀 값을 가진 로그 엔트리를 자신의 상태 머신에 적용했다면, 다른 어떤 서버도 같은 인덱스와 텀 값을 가진 인덱스에 대해 다른 로그 엔트리를 적용하지 않는다.

그러니까 한 번 적용된 인덱스-텀 값 조합은 시간이 지난 뒤 재활용될 수 없음을 의미한다. 이 속성이 보장되기 때문에 같은 인덱스, 같은 텀 값을 가진 엔트리가 있을 때 내용물이 같은 엔트리라고 생각할 수 있다. (모든걸 의심해야 하는 컴퓨터 세계에서 참 다행인 일이다.)

이 속성이 항상 성립하는지 잠깐 생각해보자. 리더 완전성 속성에서 힌트를 얻을 수 있다. 앞서 Raft의 리더 완전성 속성이 성립함을 보였으니 이건 믿고 쓸 수 있다. 이제 서버가 주어진 로그 엔트리를 적용하는 가장 낮은 텀을 생각해보자. 리더 완전성 속성에 의해 그보다 더 높은 텀의 모든 리더는 같은 로그 엔트리를 갖고 있어야 한다. 따라서 상태 머신 안전성 속성이 성립한다. 한 번 정해진 텀과 인덱스 쌍을 미래의 다른 엔트리가 차지할 수 없다.

마지막으로, Raft 서버는 로그 인덱스 순서대로 엔트리를 자신의 상태 머신에 적용한다. 이걸 상태 머신 안전성 속성과 합치면, 모든 서버들이 정확히 같은 로그 항목 집합을 같은 순서로 자신들의 상태 머신에 적용함을 의미한다. 이 글의 서두에서 가져왔던 인용문을 다시 한번 언급하자면,

이전 섹션에서는 Raft가 어떻게 리더를 선출하고 로그 항목을 복제하는지 설명했습니다. 하지만 지금까지 설명한 메커니즘만으로는 각 상태 머신이 정확히 동일한 명령을 동일한 순서로 실행한다는 것을 보장하기에 충분하지 않습니다.

이제는 상태 머신이 정확히 동일한 명령을 동일한 순서로 실행한다는 것이 보장된다는 것을 알게 되었다.

결론

Safety 보장을 위한 짧은 여정을 정리해보자. Raft 가 진짜 데이터 일관성을 보장하는지 밝혀내는게 목표였다.

• Raft 리더, 팔로워 노드는 자신만의 상태 머신을 갖고 로그를 복제한다. 이 때 모든 상태 머신이 정확히 동일한 명령을 동일한 순서로 실행해야 데이터 일관성이 보장된다.
• 리더가 될 수 있는 서버의 조건이라는 제약 조건을 걸었다. 후보 노드가 다른 노드로부터 표를 얻기 위해서는 지금까지 커밋된 모든 엔트리를 갖고 있어야 한다.
• 완전한 리더 속성은 한 번 커밋된 메세지가 이후에도 리더 노드에 계속 존재함을 보장한다. 이 속성이 보장됨을 증명하는 과정에서 로그 매칭 속성을 사용했다.
• 상태 머신 안전성 속성은 어떤 서버가 로그 엔트리를 한 번 적용했다면 다른 어떤 서버도 동일한 텀, 인덱스 값을 갖는 다른 엔트리를 적용할 수 없음을 보장한다. 이를 증명하기 위해 완전한 리더 속성을 사용했다.
• 따라서 Raft 상태 머신은 정확히 동일한 명령을 동일한 순서로 실행한다.