1편. 분산 합의란 무엇인가? - Raft의 기본 개념

Raft

 

분산 시스템에서 여로 노드가 마치 하나의 물리 노드처럼 일관된 상태를 유지하는 것은 어렵다. 네트워크 장애, 노드 실패, 패킷 손실 등등 다양한 문제들이 발생할 수 있고, 민감한 시스템의 경우 이는 큰 장애로 이어질 수도 있다. 이러한 문제를 해결하기 위해 등장한 개념이 합의 알고리즘(Consensus Algorithm) 이다.

 

그 중에서도 Raft 알고리즘이 가장 대표적이어 Raft를 한번 톺아보기로 했다.

Raft의 탄생 배경

Raft 이전의 대표적인 합의 알고리즘은 Paxos였다. 하지만 Paxos 알고리즘은 구현의 난이도가 높다는 단점이 있었다. 2013년 스탠포드에서 "Understandability"를 최 우선으로 하는 Raft 알고리즘을 개발했다.

Raft의 핵심 개념

서버 상태 (Server States)

Raft에서 서버의 상태는 아래 세 가지 상태 중에 하나다

1. follwer: 수동적인 상태로, leader와 candidate 요청에만 응답

2. candidate: 리더 선출 과정에서의 임시 상태

3. leader: 모든 클라이언트 요청을 처리하고 로그 항목을 다른 서버들에 복제

Term

Raft는 시간을 Term이라는 단위로 나눈다. 각 term은 고유한 번호를 가지며, 최대 하나의 리더만 존재할 수 있다. term은 선거가 시작될 때마다 증가하며, 분산 시스템에서 논리적인 시계 역할을 한다.

 

Raft의 세 가지 핵심 메커니즘

 

1. 리더 선출 (Leader Election)

선거 과정:

1. 서버가 시작하면 follower 상태로 시작
2. 리더로부터 hearbeat 받지 못하면 candidate가 됨
3. 자신의 term을 증가시키고 다른 서버들에게 투표 요청
4. 과반수 표를 얻으면 리더가 됨
5. 같은 term 에서 다른 서버가 리더가 되었다면 팔로워로 전환

선거 타임아웃:

1. 각 서버는 랜덤한 타임아웃을 가짐 (150~300ms)
2. 이를 통해 동시에 여러 서버가 후보자가 되는 것을 방지
3. split vote 상황 최소화

2. 로그 복제 (Log Replication)

로그 구조:

인덱스	1	2	3	4	5
term	1	1	2	3	3
명령	x=3	y=1	y=9	x=2	x=0

 

복제 과정:

1. 클라이언트가 leader에게 명령 전송
2. leader가 자신의 로그에 항목 추가
3. leader가 follower들에게 AppendEntries RPC 전송
4. 과반수의 follower가 응답하면 로그 항목을 커밋
5. 리더가 클라이언트에게 성공 응답

로그 일관성 보장:

• 로그 매칭 속성: 두 로그에서 같은 인덱스와 term을 가진 항목이 있다면, 해당 위치까지의 모든 항목이 동일
• leader 완정성: 특정 term에서 커밋된 로그 항목은 그보다 높은 term의 모든 leader에 존재

3. 안정성 (Safety)

핵심 안정성 속성:

• 선거 안정성: 특정 용어에서 최대 하나의 리더만 선출
• 리더 추가 전용: 리더는 기존 로그 항목을 덮어쓰거나 삭제하지 않음
• 로그 매칭: 두 로그의 특정 위치가 같은 용어라면 모든 이전 항목도 동일
• 리더 완전성: 커밋된 항목은 모든 미래 리더에 존재
• 상태 머신 안정성: 서버가 특정 인덱스에 로그 항목을 적용했다면, 다른 서버도 같은 항목 적용

Raft의 장점과 한계

장점

• 제작자의 철학에 맞게 이해하기 쉬워 구현에 용이
• 엄격한 안정성 보장

단점

• 과반수 원칙으로 가용성 제한
• 모든 변경사항에서 과반수 합의 필요로 인한 성능 오버헤드

실제 Raft 알고리즘으로 구현된 오픈소스

• etcd: 클러스터 메타데이터의 일관성 보장
• Consul: 서비스 디스커버리와 구성관리
• TiKV: 분산 트랜잭션 key-value 스토어로 데이터 복제를 위해 Raft 사용

참고.

https://raft.github.io/

Raft Consensus Algorithm

https://raft.github.io/raft.pdf