Raft 합의 알고리즘
이번 포스팅에서는 Raft 합의 알고리즘을 공유해보려고 합니다.
개요
합의 알고리즘은 복제 상태 머신에서 비롯된 개념으로, 여러 서버에서 동일한 상태를 유지하고 요청에 대한 일관된 응답을 보장하기 위해서 사용됩니다. Raft는 대표적인 합의 알고리즘으로 복제 상태머신의 동기화 및 일관성 보장을 위해 설계되었습니다.
Raft 합의 알고리즘
가정
- non-Byzantine 환경
Raft 설계 목표
- 알고리즘에 대한 이해 가능성 (Understandable)
- 작동 및 작동하는 이유가 분명해지는 것도 중요
- 개발자에게 필요한 설계 작업량 감소
- 시스템 빌더가 실제 구현에서의 불가피한 확장이 가능하도록 직관 개발
이러한 목표를 달성하기 위해, 합의 방식을 분해를 통해 핵심요소를 3가지 분리하여 해결함
- 리더 선출(Leader election)
- 로그 복제(Log replication)
- 안정성 보장(Safety)
1. 기본 개념
상태
-
각 서버는 리더, follower(추종자), candidate(후보자) 3가지 상태 중 하나
- 단일 리더, 다른 모든 서버는 추종자
- 단일 리더는 모든 클라이언트의 요청을 처리
-
노드는 한 순간에 하나의 상태만을 가지며, 노드는 내부적으로 임기(Term) 제도를 운영
역할
- 추종자 : 수동적, 스스로 요청X, 리더와 후보자의 요청에 응답만
- 리더 : 모든 클라이언트 요청 처리, 클라이언트가 추종자에게 연락하면 추종자가 이를 리더에게 리디렉션
- 후보자 : 새로운 리더 선출용
Raft는 주어진 기간 동안 최대 1명의 리더가 있음을 보장
통신
RPC를 사용하여 통신하며, 합의 알고리즘에는 2가지 유형의 RPC만 필요
RequestVote RPCs- 리더 선출 중에 후보자에 의해 시작됨
AppendEntriesRPCs- 로그 항목을 복제하고 하트비트 형식을 제공하기 위해 리더에 의해 시작됨
2. 합의 방식
2.1 리더 선출
후보자는 3가지 중 하나가 발생할때까지 이 상태를 유지
- 선거 승리
- 다른 서버가 스스로 리더가 되는 경우
- 일정 기간, 승자가 나오지 않는 경유
- Vote Split이 발생하면, 임기를 늘리고 또 다른 RequestVote PRC 라운드를 시작 (재선거)
선거 제한 시간 초과를 사용해 Split 투표 해결
- 고정적 간격내의 랜덤한 시간, 150~300ms
- 이렇게 하면 서버가 분산되어, 대부분의 단일 서버만 시간 초과됨 (휴리스틱)
자기자신의 term을 걸고 싸우는 것
- 이전 리더선출 시에, 높은 term을 보유하고 있었다면 다음 선거에서 유리
2.2 로그 복제
리더가 선출되면, 클라이언트 요청 서비스 시작
- 리더가 요청을 처리한 후, 해당 로그를 모든 추종자에게 복제
- 추종자의 로그가 일관되게 유지되 않는 경우, 리더는 다시 로그를 전송
-
추종자 로그에서 시나리오 (a~f) 중 하나 발생
- (a~b) 항목 누락
- (c~d) 커밋되지 않는 추가 항목
- (e~f) 둘 다
2.3 안정성 보장
리더 선출과 로그복제만으로는 각 상태 시스템이 정확히 동일한 명령을 동일한 순서로 실행하도록 보장하는데 충분치 않음
- 리더로 선출될 수 있는 서버에 대한 제한을 추가
2.3.1 Election restriction
이전 term에서 커밋된 모든 항목이 해당 항목을 리더에게 전송할 필요없이, 선택되는 순간부터 각 새 리더에 존재하도록 보장하는 방식을 사용
- 로그 항목은 리더에서 추종자로 한 방향으로만 흐르며, 리더는 로그의 기존 항목을 덮어쓰지 않음
- Raft는 투표 프로세스를 사용하여 로그에 커밋된 항목이 포함되어 있지 않으면 후보자가 선거에서 승리하지 못하도록 방지함
- 후보자가 선출되려면 클러스터 대다수에 연락해야하며, 이는 모든 커밋된 항목이 해당 서버 중 적어도 하나에 있어야함을 의미
-
여기서의
최신-
두 로그 중 마지막 항목의 index과 term를 비교하여 어느 것이 더 최신인지 결정
- 로그가 동일한 term : 더 긴 로그가 더 최신
- 로그가 다른 term : 더 높은 임기를 가진 로그가 더 최신
-
2.3.2 Committing entries from previous terms
리더는 현재 임기의 로그 항목만 복제본을 계산하여 커밋됨
현재의 term(E4)을 다른 서버에 복제할 때, D는 E4를 저장하고, B,C,E는 이를 저장하지 않았을 경우
- 다수의 서버에 로그가 복제되었다고 판단할 수 없을 경우, 현재의 term에서 해당 로그를 커밋하지 않음
- 리더는 자신의 term에서 새로운 로그를 다수의 추종자에게 복제된 경우에만 커밋 가능
- 현재의 term은 2
A의 크래시: A가 크래시 발생하여 리더가 없게 되면, B가 새로운 리더로 선출됨
- B의 로그는 E4를 포함하지 않으며, 다음 term으로 넘어가면서 B의 term은 3으로 증가
문제 발생 상황
- B는 자신의 term이 3이므로, E4는 이제 자신의 로그에서 존재하지 않음
- Raft의 규칙에 따르면, B는 이전 term(2)의 로그 항목을 직접 커밋할 수 없음
- 이전 term의 로그 항목(E4)은 여전히 존재하지만, B는 E4를 커밋할 수 없고 오히려 새로운 로그 항목을 추가해야 함
해결 방법
-
현재 term의 로그 항목만 커밋
- B는 자신의 로그 항목(term 3)만을 관리함
- B는 자신의 로그에서 새로운 요청을 처리하고, 새로운 로그 항목을 만들어 다른 서버에 복제함
-
로그 매칭 속성 활용: Raft의 로그 매칭 속성을 통해, B가 E4와 같은 이전 term의 로그 항목을 원활하게 처리할 수 없습니다. 새로운 로그 항목을 추가하는 것은 가능하지만, B는 이전 term의 항목을 커밋할 수 없기 때문에 일관성을 유지할 수 있음
-
Raft의 보수적 접근
2.3.3 Safety argument
리더 완전성 속성은 Raft의 핵심 안전성 속성 중 하나
-
리더가 특정 term(T)에서 커밋한 로그는 이후의 모든 리더가 반드시 포함해야 한다는 것
- 리더는 다수의 추종자에 의해 선택되며, 이전 리더가 커밋한 항목은 다수의 서버에 복제되었기에 새로운 리더는 이 로그를 포함할 수 밖에 없음
해당 속성에 대한 모순 (리더 완전성 속성이 유지되지 않는다고 가정했을 때, 다음과 같은 모순을 증명)
-
전제
- 커밋된 항목은 선택 당시 U의 로그에 존재하지 않아야 함
- T는 클러스터의 대다수에 항목을 복제했으나, U는 클러스터의 대다수로부터 투표를 받음
-
모순
- 리더 T가 커밋한 항목이 리더 U의 로그에 없으므로, 리더 U는 리더 T가 커밋한 로그 항목을 포함할 수 없음
- 따라서, 모든 리더 U는 이전 리더 T의 커밋된 로그 항목을 포함해야 하며, 이는 리더 완전성 속성이 유지된다는 것을 의미
- 리더 T가 커밋한 항목이 리더 U의 로그에 없으므로, 리더 U는 리더 T가 커밋한 로그 항목을 포함할 수 없음
이는 Raft 알고리즘에서 리더 완전성 속성이 유지됨을 보장하며, 리더 T가 커밋한 모든 항목이 리더 U의 로그에 반드시 포함되어야 하며, 이를 통해 Raft의 안전성을 확보 가능함
2.4 Timing
Raft에 대한 요구사항 중 하나는 safety이 타이밍에 좌우되어서는 안된다는 것
- 일부 이벤트가 예상보다 더 빠르거나 느리게 발생한다고 해서, 시스템이 잘못된 결과를 생성해서는 안됨
- Raft에서 리더 선출 시, 요청은 병렬로 처리
-
두 서버간의 비교시에 중복 방지됨
- A가 B,C,D,E에 리더선출비교를 요청하면 B는 A한테는 안보내고 C,D,E한테 보내는 개념
가용성(적시에 클라이언트에 응답하는 시스템의 능력)은 필연적으로 타이밍에 따라 달라짐
- ex. 메시지 교환이 서버 충돌 사이의 일반적인 시간보다 오래걸리는경우, 후보자는 선거에서 승리할 만큼 충분히 오래 머물지 못함
- 리더 선출은 타이밍에 크게 의존하진 않지만, 적절한 RPC를 주고받는 건 중요
Raft는 시스템이 다음 타이밍 요구사항을 충족하는 한 꾸준한 리더를 선출하고 유지함
아래와 같은 시스템 속성들이 타이밍 제어에 영향을 줌
1. BroadcastTime
- 서버가 클러스터의 모든 서버에 RPC를 병렬로 보내고 응답을 받는 데 걸리는 평균 시간
- 요구사항: 리더가 하트비트 메시지를 신뢰성 있게 전송하고, 추종자들이 선거를 시작하지 않도록 하려면
BroadcastTime은ElectionTimeout보다 한 자릿수 정도 작아야 함
2. ElectionTimeout
- 선거 시간 초과 시간
- 특징: 랜덤화된 접근 방식을 사용하여 설정됨
- 이로 인해 분할 투표(split votes)가 발생할 가능성이 낮아짐
- 요구사항:
ElectionTimeout은MTBF보다 훨씬 짧아야하며, 시스템이 지속적으로 진행될 수 있음
3. MTBF (Mean Time Between Failures)
- 단일 서버의 평균 고장 사이 시간
- 단일 서버가 고장 나기 전까지의 평균 시간
- 특징: 일반적인 서버의
MTBF는 수개월 이상이며, 시스템의 기본 속성을 나타냄
4. 시스템 속성 간 관계
BroadcastTime과MTBF는 기본 시스템의 속성으로, 시스템의 안정성과 성능을 나타냄ElectionTimeout은 우리가 선택해야 하는 값으로, 대개 10ms에서 500ms 사이에서 설정됨
3. Cluster membership changes
실제로는 클러스터 구성(합의 알고리즘 참여하는 서버 집합)은 동적으로 변화함
- 새로운 서버 추가, 기존 서버 제거 등의 상황에서 로그 일관성을 유지하면서 안전한 구성 변경 처리 필요
그림처럼 클러스터 3개에서 5개로 증가한 경우
- 한 구성에서 다른 구성으로 직접 전환하는 것은 서로 다른 서버가 서로 다른 시간에 전환되기에 안전하지 않음
- 2명의 리더가 선출될 수 있어짐
- Raft는 이 문제를 해결하기 위해 Join consensus(결합 합의)를 적용
클러스터 멤버쉽 변경 과정 (2단계)
-
1단계 (Transitional Configuration)
- 구성 변경은 점진적으로 진행
- 기존, 신규 구성 모두 클러스터에 포함되며, 리더는 2가지 구성에 대해 로그 복제를 수행
- 두 구성에서 과반수 동의를 얻어야 로그 커밋 가능
-
2단계 (Final Configuration)
- 1단계에서 모든 로그가 동기화되고 안전하게 복제된 후, 해당 단계로 전환됨
- 이 시점에서 기본 구성원은 새로운 구성에서 제외, 새로 추가된 서버만 남게 됨
- 즉, 클러스터는 단 하나의 구성만 따르며 리더는 이 구성에 속한 서버로 로그 복제 수행
기본 아이디어는 서버별 전환 시간 허용 및 로그 엔트리에 새로운 설정 정보를 포함시켜 로그가 안전하게 커밋된 이후에만 새로운 구성을 활성화하겠다는 의미
클러스터 멤버쉽 변경 과정
- 점선 : 구성 변경의 타임라인, 커밋이 이루어지지 않은 상태
- 실선 : 최근 커밋된 구성항목을 표시, 실제로 클러스터가 따르는 구성 정보
C_old 는 구성변경이 이루어지더라도 여전히 안정적으로 작언 지원하며, 새로운 구성으로 전환하기 전까지 계속 사용되며, C_new는 호환성을 유지하다가, 최종 전환
4. 기대효과
- 시스템의 일관성 보장
- 각 노드의 상태를 동일하게 유지하여, 시스템 전반에 걸쳐 일관된 데이터를 제공
- 비결정성 제거를 통한 상태공간의 단순화
- 모든 요청은 리더를 통해 처리되며 동일한 클라이언트 요청에 대해 항상 동일한 결과를 보장 (결정성)
- 이는, 시스템의 예측 가능성을 높여 안정성을 높임
5. 요약
- 합의 과정에 대해 비교적 간단한 구조로 설계되어, 구현이나 직관적 설명이 용이
- 리더와 추종자 사이의 간단한 통신 패턴을 사용하므로 통신 비용이 적게 듦
- 단, 지도자의 네트워크 성능이 전체 합의 성능에 큰 영향을 미침 (리더 의존성이 높음)
- 리더 선출 지연 시, 그만큼 클라이언트 요청 처리에 일시적 중단됨
6. 결론
안정적인 SW 시스템 구축을 위한 핵심은 합의 알고리즘의 적용에 있음 (데이터의 일관성과 안정성 보장을 통한 시스템의 신뢰성 향상)
Raft는 리더를 선출한 다음, 복제된 로그 관리에 대한 전적인 책임을 부여함으로써 합의를 구현
7. Raft 활용 사례
- etcd
- docker swarm
- Consul
- RethinkDB
- TiKV
※ Official Document에 Raft를 사용중인 시스템과 Git 주소가 포함되어 있음
참고