받은 것과 확정한 것은 다르다

한 줄 요약

리더가 값을 받아 자기 로그에 적었다는 사실은 아무것도 보장하지 않는다. 과반이 같은 자리에
같은 항목을 갖고, 그 항목이 리더의 현재 임기일 때 비로소 '커밋' 이고, 그때서야 클라이언트에게
성공이라고 말할 수 있다.

왜 이게 필요했나

선거가 끝나면 쓰기를 받는 곳이 하나로 정해진다. 그런데 그 하나가 받은 값을 나머지에게
어떻게 퍼뜨릴 것인가. 단순히 "보내고 잊는다" 로 하면, 리더가 값을 받자마자 죽었을 때
그 값은 어디에도 없다. 반대로 "모두가 받을 때까지 기다린다" 로 하면 한 대만 느려도
전체가 멈춘다. 합의가 고르는 지점은 그 사이의 과반이다.

과반을 고르는 이유는 성능이 아니라 안전이다. 두 개의 과반은 반드시 겹치므로, 어떤
항목이 과반에 닿아 있으면 다음 리더가 될 수 있는 후보 중 적어도 하나는 그 항목을
갖고 있다. 여기에 조건을 하나 더 붙이면 — 후보의 로그가 투표자의 것만큼은 최신일 때만
표를 준다 — 그 항목을 가진 노드만 리더가 될 수 있게 된다. 그래서 커밋된 항목은
어떤 미래의 리더에게도 남는다.

어떻게 동작하나

로그는 덧붙이기만 하는 목록이고, 항목마다 그때의 임기가 함께 붙는다. 그 임기가
두 로그를 비교하는 유일한 근거다.

index :   1        2        3        4term  :   1        1        2        3value : "a"      "b"      "c"      "d"

리더는 팔로워에게 항목을 보낼 때 "네 로그의 2번 자리가 임기 1이면, 그 뒤에 이것들을
붙여라" 라고 말한다. 팔로워는 그 앞자리만 확인한다. 전체를 비교하지 않는 이유는
로그 일치성 때문이다 — 같은 자리에 같은 임기의 항목이 있으면 그 앞은 전부 같다는
성질이 규칙에서 따라 나온다. 앞자리가 어긋나면 팔로워는 거절하고, 리더는 한 칸 뒤로
물러나 다시 묻는다. 맞는 지점을 찾으면 거기서부터 자기 것으로 채운다.

커밋은 리더가 센다. 각 팔로워가 어디까지 받았는지를 세어, 과반이 가진 가장 높은 자리를
커밋 번호로 삼는다. 여기에 거의 항상 빠뜨리는 단서가 붙는다.

리더는 자기 임기의 항목이 과반에 닿았을 때만 커밋 번호를 올린다.앞 임기의 항목은 그 자체로는 과반에 닿아도 커밋하지 않는다.

이 단서가 없으면 이런 일이 난다. 앞 임기의 항목이 과반에 복제되어 커밋했는데, 그 리더가
죽고 그 항목을 갖지 않은 다른 노드가 (더 높은 임기의 항목을 갖고 있어서) 리더가 되면,
그 자리를 다른 항목으로 덮어쓴다. 이미 확정했다고 말한 값이 사라지는 것이다. 논문은
이 경우를 그림 8로 설명하고, 해법으로 위의 단서를 넣는다. 새 리더가 자기 임기의 항목을
하나라도 커밋하는 순간, 그 앞의 것들이 함께 안전해진다.

리더가 팔로워마다 따로 들고 있는 값이 하나 더 있다. '이 팔로워에게 다음에 어디부터
보낼 것인가' 다. 리더가 새로 뽑히면 이 값을 자기 로그의 끝으로 낙관적으로 잡아 두고,
거절당할 때마다 한 칸씩 줄인다. 대부분의 팔로워는 한두 번 만에 맞는 지점을 찾으므로
이 낙관이 평소에는 공짜다. 대신 오래 떨어져 있던 노드에서는 되감기가 길어지고,
그것이 스냅샷이 필요해지는 이유가 된다.

현장에서 만나는 모습

이 구분은 클라이언트가 받는 응답의 의미를 바꾼다. etcd 의 쓰기가 성공을 돌려줬다면
그 값은 과반에 닿아 있고, 그래서 리더가 그 직후에 죽어도 살아남는다. 반대로 응답이
timeout 이었다면 그 쓰기는 성공했을 수도 실패했을 수도 있다 — 과반에 닿은 뒤
응답만 유실됐을 수 있기 때문이다. 그래서 분산 저장소를 쓰는 코드는 재시도를 멱등하게
만들어야 한다. etcd 문서가 트랜잭션과 리비전을 앞세우는 이유가 여기에 있다
([etcd — 왜 etcd 인가](https://etcd.io/docs/v3.5/learning/why/)).

따라잡기도 매일 보는 장면이다. 팔로워 하나가 재시작하면 리더가 보내는 자리 번호를
한 칸씩 뒤로 물리며 맞는 지점을 찾는다. 로그가 길면 이 되감기가 오래 걸리고, 그래서
실제 구현은 스냅샷을 함께 쓴다. etcd 는 로그가 일정 개수 쌓이면 압축하는데, 그 값을
정하는 --snapshot-count 의 기본값은 v3.2 에서 10,000 에서 100,000 으로 바뀌었다
([etcd 유지보수 문서](https://etcd.io/docs/v3.5/op-guide/maintenance/)).

세 번째로 자주 보는 것은 '느린 팔로워 한 대' 다. 과반만 있으면 커밋이 진행되므로
느린 한 대는 서비스를 막지 않는다. 그래서 눈에 띄지 않고, 어느 날 다른 한 대가 재시작할
때 비로소 드러난다 — 그 순간 과반을 만들 수 있는 건강한 노드가 하나뿐이 되기 때문이다.
복제 지연은 장애가 아니라 여유분의 소진으로 읽어야 한다.

다음 실습에서 할 것

로그 규칙 네 가지를 직접 쓴다 — 덧붙이기, 로그 일치성 확인, 어긋나는 자리부터 잘라 내기,
그리고 커밋 번호 계산이다. 마지막 두 단계에서는 세 노드에 값을 써서 커밋이 퍼지는 것을
보고, 팔로워 하나를 죽였다 되살려 빈 로그에서 따라잡는 과정을 직접 확인한다.