합의 프로토콜

합의 프로토콜 (Consensus Protocol)

이 페이지는 Nomad의 합의(consensus) 프로토콜에 대한 개념 정보를 제공해요. 합의 프로토콜은 CAP가 정의하는 일관성(Consistency)을 제공해요. 합의 프로토콜은 "Raft: In search of an Understandable Consensus Algorithm"을 기반으로 해요. Raft에 대한 시각적 설명은 The Secret Lives of Data를 참고해요.

출처: 문서

본문

고급 주제! 이 페이지는 Nomad 내부 동작의 기술적 세부 사항을 다루고 있어요. 이 내용을 알지 못해도 Nomad를 효과적으로 운영하고 사용하는 데는 문제가 없어요. 이 세부 사항은 소스 코드를 직접 뒤지지 않고도 배우고 싶은 사람들을 위해 문서화된 것이에요.

Raft 프로토콜 개요 (Raft Protocol Overview)

Raft는 Paxos를 기반으로 하는 합의 알고리즘이에요. Paxos와 비교해 Raft는 더 적은 상태를 가지도록 설계되었고 더 단순하고 이해하기 쉬운 알고리즘이에요.

Raft를 논할 때 알아야 할 몇 가지 핵심 용어가 있어요.

• 로그 (Log) — Raft 시스템의 주요 작업 단위는 로그 항목이에요. 일관성 문제는 복제된 로그로 분해할 수 있어요. 로그는 항목의 정렬된 시퀀스예요. 모든 멤버가 항목과 그 순서에 동의하면 로그가 일관적이라고 간주해요.
• FSM — 유한 상태 머신(Finite State Machine)이에요. FSM은 그 사이의 전이와 함께 유한 상태 집합이에요. 새 로그가 적용됨에 따라 FSM은 상태 간 전이가 허용돼요. 동일한 로그 시퀀스의 적용은 동일한 상태를 결과로 해야 하며, 즉 동작이 결정적(deterministic)이어야 해요.
• 피어 집합 (Peer set) — 피어 집합은 로그 복제에 참여하는 모든 멤버의 집합이에요. Nomad의 목적상 모든 서버 노드는 로컬 리전의 피어 집합에 있어요.
• 쿼럼 (Quorum) — 쿼럼은 피어 집합 멤버의 과반수예요. 크기 n의 집합에 대해 쿼럼은 최소 ⌊(n/2)+1⌋ 멤버가 필요해요. 예를 들어 피어 집합에 멤버가 5개 있으면 쿼럼을 구성하려면 3개 노드가 필요해요. 어떤 이유로든 쿼럼의 노드를 사용할 수 없으면 클러스터는 사용할 수 없게 되고 새 로그를 커밋할 수 없어요.
• 커밋된 항목 (Committed Entry) — 항목이 쿼럼의 노드에 내구적으로 저장되면 커밋된 것으로 간주돼요. 항목이 커밋되면 적용될 수 있어요.
• 리더 (Leader) — 어느 시점이든 피어 집합은 단일 노드를 리더로 선출해요. 리더는 새 로그 항목을 수집하고, 팔로워에 복제하며, 항목이 커밋된 것으로 간주되는 시점을 관리하는 역할을 담당해요.

Raft는 복잡한 프로토콜이므로 여기서 자세히 다루지 않아요(더 포괄적인 처리를 원한다면 전체 스펙이 이 논문에서 제공돼요). 하지만 정신적 모델을 구축하는 데 유용할 수 있는 높은 수준의 설명을 제공하려고 해요.

Raft 노드는 항상 세 가지 상태 중 하나에 있어요: follower, candidate, leader. 모든 노드는 처음에 follower로 시작해요. 이 상태에서 노드는 리더의 로그 항목을 수락하고 투표할 수 있어요. 일정 시간 동안 항목을 받지 못하면 노드는 candidate 상태로 자체 승격해요. candidate 상태에서 노드는 피어에게 투표를 요청해요. candidate가 쿼럼의 투표를 받으면 leader로 승격돼요. 리더는 새 로그 항목을 수락하고 다른 모든 팔로워에 복제해야 해요. 또한 오래된 읽기(stale read)가 허용되지 않으면 모든 질의도 리더에서 수행해야 해요.

클러스터에 리더가 생기면 새 로그 항목을 수락할 수 있게 돼요. 클라이언트는 리더가 새 로그 항목을 추가하도록 요청할 수 있어요(Raft 관점에서 로그 항목은 불투명한 이진 blob이에요). 그러면 리더는 항목을 내구 저장소에 기록하고 쿼럼의 팔로워에 복제하려고 시도해요. 로그 항목이 커밋된 것으로 간주되면 유한 상태 머신에 적용될 수 있어요. 유한 상태 머신은 애플리케이션 특정적이며, Nomad의 경우 MemDB를 사용해 클러스터 상태를 유지해요.

당연히 복제된 로그가 무제한으로 성장하도록 허용하는 것은 바람직하지 않아요. Raft는 현재 상태를 스냅샷하고 로그를 압축하는 메커니즘을 제공해요. FSM 추상화 덕분에 FSM 상태를 복원하는 것은 이전 로그의 재생과 같은 상태를 결과로 해야 해요. 이를 통해 Raft는 시점의 FSM 상태를 캡처한 다음 해당 상태에 도달하는 데 사용된 모든 로그를 제거할 수 있어요. 이는 사용자 개입 없이 자동으로 수행되며, 무제한 디스크 사용을 방지하면서 로그 재생에 보내는 시간도 최소화해요. MemDB를 사용하는 장점 중 하나는 이전 상태가 스냅샷되는 동안에도 Nomad가 새 트랜잭션을 계속 수락할 수 있어 가용성 문제를 방지한다는 점이에요.

합의는 쿼럼이 사용 가능한 지점까지 결함 허용적이에요. 쿼럼의 노드를 사용할 수 없으면 로그 항목을 처리하거나 피어 멤버십을 추론하는 것이 불가능해요. 예를 들어 피어가 A와 B 두 개뿐이라고 가정해 봐요. 쿼럼 크기는 2이므로 로그 항목을 커밋하려면 두 노드 모두 동의해야 해요. A나 B가 실패하면 쿼럼에 도달하는 것이 불가능해져요. 즉 클러스터가 노드를 추가·제거하거나 추가 로그 항목을 커밋할 수 없게 돼요. 이로 인해 사용 불가능(unavailability) 상태가 돼요. 이 시점에서는 A나 B 중 하나를 제거하고 남은 노드를 부트스트랩 모드로 재시작하는 수동 개입이 필요해요.

3개 노드 Raft 클러스터는 단일 노드 장애를 견딜 수 있고, 5개 노드 클러스터는 2개 노드 장애를 견딜 수 있어요. 권장 구성은 리전당 3개 또는 5개 Nomad 서버를 실행하는 것이에요. 이는 성능을 크게 희생하지 않으면서 가용성을 극대화해요. 아래 배포 표는 가능한 클러스터 크기 옵션과 각각의 결함 허용성을 요약해요.

성능 측면에서 Raft는 Paxos와 비슷해요. 안정적인 리더십을 가정하면, 로그 항목 커밋에는 클러스터 절반에 대한 단일 왕복(round trip)이 필요해요. 따라서 성능은 디스크 I/O와 네트워크 대기 시간에 의해 결정돼요.

Nomad에서의 Raft (Raft in Nomad)

Raft에는 Nomad 서버 노드만 참여하고 피어 집합의 일부가 돼요. 모든 클라이언트 노드는 서버에 요청을 전달해요. Nomad의 클라이언트는 자신의 할당에 대해서만 알고 서버에서 해당 정보를 질의하면 되는 반면, 서버는 클러스터의 전역 상태를 유지해야 해요.

모든 서버가 피어 집합의 일부로 참여하므로 모두 현재 리더를 알아요. RPC 요청이 리더가 아닌 서버에 도착하면 요청은 리더로 전달돼요. RPC가 질의(query) 유형이면(즉 읽기 전용) 리더는 FSM의 현재 상태를 기반으로 결과를 생성해요. RPC가 트랜잭션(transaction) 유형이면(즉 상태를 수정) 리더는 새 로그 항목을 생성하고 Raft를 사용해 적용해요. 로그 항목이 커밋되고 FSM에 적용되면 트랜잭션이 완료돼요.

Raft 복제의 특성 때문에 성능은 네트워크 대기 시간에 민감해요. 이러한 이유로 각 리전은 독립적인 리더를 선출하고 분리된 피어 집합을 유지해요. 데이터는 리전별로 분할되므로 각 리더는 자체 리전의 데이터에 대해서만 책임이 있어요. 원격 리전에 대한 요청을 받으면 요청은 올바른 리더로 전달돼요. 이 설계는 일관성을 희생하지 않으면서 더 낮은 대기 시간 트랜잭션과 더 높은 가용성을 허용해요.

일관성 모드 (Consistency Modes)

복제된 로그에 대한 모든 쓰기는 Raft를 거치지만, 읽기는 더 유연해요. 개발자가 원할 수 있는 다양한 트레이드오프를 지원하기 위해 Nomad는 읽기에 대해 2가지 일관성 모드를 지원해요.

두 읽기 모드는 다음과 같아요.

• default — Raft는 리더 임대(leader leasing)를 사용해 리더가 자신의 역할이 안정적이라고 가정하는 시간 창을 제공해요. 하지만 리더가 나머지 피어와 분리되면, 이전 리더가 임대를 보유하고 있는 동안 새 리더가 선출될 수 있어요. 즉 리더 노드가 2개가 될 수 있어요. 이전 리더는 새 로그를 커밋할 수 없으므로 스플릿 브레인 위험은 없어요. 하지만 이전 리더가 읽기를 제공하면 값이 잠재적으로 오래됐을 수 있어요. 기본 일관성 모드는 리더 임대에만 의존하므로 클라이언트가 잠재적으로 오래된 값을 볼 수 있어요. 우리는 읽기가 빠르고 보통 강하게 일관되며, 트리거하기 어려운 상황에서만 오래되기 때문에 이 트레이드오프를 선택해요. 오래된 읽기의 시간 창도 리더가 분리로 인해 스텝 다운하기 때문에 제한돼요.
• stale — 이 모드는 리더인지 여부와 관계없이 모든 서버가 읽기를 제공할 수 있게 해요. 즉 읽기가 임의로 오래될 수 있지만 일반적으로 리더와 50밀리초 이내예요. 트레이드오프는 매우 빠르고 확장 가능한 읽기지만 오래된 값이 되는 것이에요. 이 모드는 리더 없이 읽기를 허용하므로, 사용할 수 없는 클러스터도 응답할 수 있어요.

배포 표 (Deployment Table)

아래는 다양한 클러스터 크기에 대한 쿼럼 크기와 결함 허용성을 보여주는 표예요. 권장 배포는 3개 또는 5개 서버예요. 단일 서버 배포는 장애 시 데이터 손실이 불가피하므로 매우 권장되지 않아요.

더 알아보기 (Learn more)

• Raft 논문
• 가십 프로토콜 (Gossip protocol)
• 페더레이션 (Federation)