Distributed Consensus Algorithm(분산 합의 알고리즘)
분산 합의 알고리즘은 여러 노드로 구성된 분산 시스템에서 모든 노드들이 특정 값에 대해서 동의(consensus) 하도록 만드는 알고리즘으로 분산 환경에서 데이터 일관성, 장애 허용성, 시스템 안정성을 보장하는데 사용 된다.
주요한 3가지 특징을 가지고 있다.
- Consistency (일관성): 모든 노드가 동일한 데이터를 공유
- Fault Tolerance (장애 허용성): 일부 노드가 장애가 나더라도 시스템은 정상적으로 작동
- Eventual Agreement (최종 동의): 네트워크 상태가 안정적이면 모든 노드가 같은 결론으로 동작
Raft Consensus Algorithm, 뗏목 합의 알고리즘
Raft 는 분산 합의 알고리즘 중 하나로 기존 Paxos 알고리즘에 대안으로 Paxos 알고리즘에 비해 이해하기 쉽고 구현에 용이하다는 특징을 가지고 있다.
Clsuter내 모든 노드들은 노드 간 상호작용을 통해 상태를 유지하며 다음중 하나의 상타를 가진다:
- Leader(리더) : 클러스터내 하나의 노드만 Leader를 하며 요청을 처리하고 로그 복제 수행.
- Follwer(팔로워) : Leader로부터 로그를 수신하고 상태 유지.
- Candidate(후보자) : Leader가 사용 불가능해지는 경우 Leader 선출을 위해 일시적으로 변경된 상태
Raft Consensus Algorithm 의 주요 기능
Leader Election, 리더 선출
클러스터내 기존 리더가 어떠한 장애로 새로운 리더를 선택하는 과정으로 클러스터내 새로운 텀(Term)이 시작되며
선출이 성공적으로 완료되면 해당 텀은 정상 운영 상태로 유지되며 선출에 실패한다면 새로운 텀이 시작되고 다시 선출이 진행.
- 노드들은 선출 타임아웃(Election timeout) 기간 동안 리더로부터 하트비트(Heartbeat)를 수신하지 못했다면 리더가 없다고 생각하고 후보자(Candidate) 상태 변경과 리더 선출을 시작합니다.
- 선출 타임아웃이 가장 먼저 끝난 노드는 후보자로 상태 변경이 되며 텀 카운터를 증가시키고 자신에게 투표하고 다른 노드들에게도 투표를 요청합니다.
- 후보자가 자신의 텀보다 더 큰 텀 번호를 메시지를 수신하면 후보자는 팔로워로 변경되고 해당 후보자를 리더로 투표한다.
- 전체 노드의 과반수를 받은 후보자는 새로운 리더로 선정된다.
* Term: 선거 시작부터 신규 리더를 선출하는 임의의 시간 간격.
* Election timeout: 팔로워에서 후보자 변환까지 대기 시간으로 노드마다 서로 다른 값을 가짐. 이는 동시에 후보자가 되지 않도록 하며 표 분산 가능성을 줄이는데 도움을 준다.
* Heartbeat: 리더가 팔로워에게 송신하는 메시지.
Split vote, 투표가 분산된 경우
여러 노드가 동시에 후보자가 되어 투표 결과가 과반수가 되지 않는 경우 발생하며 다시 리더 선출 과정을 반복하지만 해당 기간 동안 시스템은 정체 되어 있는다.
빈번한 리더 변경
네트워크 문제로 하트비트가 정상 수신되지 못하는 경우가 발생하고 빈번한 새로운 리더 선출을 반복하는 경우가 있을 수 있다.
이런 경우 우선 네트워크 문제를 해결하고 하트비트 간격을 조정할 수 있다.
Log Replication, 로그 복제
로그 복제는 리더가 클라이언트의 요청을 처리하여 모든 노드들을 일관된 상태로 유지하도록 보장하는 과정.
- 데이터 변경 요청을 받은 리더 노드는 요청을 로그 엔트리(Log entry) 변환한다.
로그 엔트리에는 텀(Term: 선출 임기 번호), 인덱스(Index: 클러스터내 로그 위치), 커맨드(Command: 요청) 정보를 포함한다. - 리더는 우선 자신의 로그에 새로운 엔트리를 추가하며 Before commit 단계 이다.
- 리더는 팔로워에게 로그 엔트리를 송신하고 팔로워는 이전 로그와 텀, 인덱스를 비교 후 일치하지 않는다면 리더와의 동기화 요청을 보낸다. 일치한다면 자신의 로그에 추가하고 리더에게 성공 응답 (ACK)
- 리더는 과반수의 팔로워가 성공 응답을 했다면 해당 로그를 커밋(Commit)
만약 실패 응답을 받았다면 팔로워와 동기화를 위해서 일치하는 가장 최신 인덱스를 찾음. - 리더는 로그를 커밋한 후 로그 인덱스를 팔로워에게 통지하고 상태를 공유하며 클라이언트에게도 성공 응답을 반환한다.
- 리
Log Consistency, 일관성
로그는 항상 과반수 이상의 노드에 복제된 이후에만 커밋되며 리더는 AppendEntries RPC에서 이전 로그 인덱스와 이전 로그 텀 정보를 사용해 팔로워의 로그와 리더 로그가 일치하는지 확인을 한다. 만약 불일치가 발생하면 리더는 팔로워 로그를 동기화하여 일관성을 복원한다.
알고리즘 구현체
https://github.com/mahyarmirrashed/raft
참고
https://en.wikipedia.org/wiki/Raft_(algorithm)
https://raft.github.io/slides/uiuc2016.pdf
https://seongjin.me/raft-consensus-algorithm/