Raft 알고리즘

Raft 알고리즘은 분산 시스템에서 리더 선출과 로그 복제를 통해 강한 일관성을 보장하는 **합의 알고리즘(Consensus Algorithm)**입니다. Raft는 Paxos 알고리즘보다 이해하고 구현하기 쉬운 설계를 목표로 만들어졌으며, 주로 분산된 키-값 저장소(예: etcd, Consul)에서 사용됩니다.

1. Raft 알고리즘의 주요 목표

• 강한 일관성(Strong Consistency):
  • 분산된 노드 간에 단일 데이터 상태를 유지.
• 고가용성(High Availability):
  • 일부 노드에 장애가 발생하더라도 정상 동작.
• 간단한 설계:
  • Paxos보다 이해하고 구현하기 쉽게 설계.

2. Raft 알고리즘의 주요 구성 요소

(1) 클러스터의 상태

Raft 클러스터는 여러 노드로 구성되며, 각 노드는 세 가지 상태 중 하나에 있을 수 있습니다:

• Leader:
  • 클러스터의 중심 역할을 하며, 모든 클라이언트 요청을 처리하고 로그를 복제.
• Follower:
  • 리더의 명령을 수신하고 응답.
• Candidate:
  • 새로운 리더를 선출하기 위해 선거 과정에 참여.

(2) 주요 데이터 구조

• 로그(Log):
  • 모든 상태 변경 요청(명령)이 기록됨.
• 터미널(term):
  • 선거 주기를 나타내는 숫자로, 새로운 리더가 선출될 때마다 증가.
• 리더 커밋 인덱스(commit index):
  • 클러스터에서 합의된 마지막 로그 항목의 인덱스.

3. Raft의 주요 동작

(1) 리더 선출

• 클러스터는 항상 하나의 리더만을 가집니다.
• 리더는 장애가 발생할 수 있으므로 필요시 새로운 리더를 선출.

리더 선출 과정:

1. 타이머 만료:
   • Follower는 리더로부터 일정 시간 동안 통신(Heartbeat)을 받지 못하면 Candidate로 전환.
2. 투표 요청:
   • Candidate는 다른 노드들에게 투표를 요청.
3. 투표 과정:
   • 과반수(Quorum)의 투표를 얻은 노드가 리더로 선출.
4. 리더 선출 완료:
   • 새로운 리더는 다른 노드에게 자신의 리더 상태를 알림.

(2) 로그 복제

• 리더는 클라이언트의 상태 변경 요청(예: 데이터 쓰기)을 처리하고, 이를 로그로 기록한 후 Follower에게 복제.
• 로그가 과반수 노드에서 저장되면 커밋이 완료.

로그 복제 과정:

1. 리더가 클라이언트 요청을 로그에 기록.
2. 리더가 로그 항목을 Follower에게 전송.
3. Follower가 로그를 저장한 뒤 리더에게 응답.
4. 과반수 노드가 로그를 저장하면 리더가 해당 항목을 커밋.

(3) 로그 일관성 보장

• Raft는 리더가 보낸 로그 항목이 Follower와 일치하도록 보장.
• 용어:
  • 매칭 항목: 리더와 Follower가 동일한 로그를 가지고 있는 항목.
  • 불일치 해결: Follower의 로그가 리더와 다를 경우 리더가 자신의 로그로 덮어씀.

4. Raft의 특징

(1) 강한 일관성

• Raft는 리더 기반 구조를 사용하여 로그를 순차적으로 복제하고 일관성을 유지.

(2) 간단한 설계

• Raft는 선거 과정, 로그 복제, 로그 일관성 보장과 같은 복잡한 개념을 이해하기 쉽게 나눠서 설계.

(3) 장애 허용

• 과반수 노드가 가용한 한, Raft 클러스터는 정상 동작.
  • 예: 5개 노드 중 2개가 장애가 나도 동작 가능.

(4) 효율성

• Follower는 리더의 명령을 따르기만 하므로, 분산 시스템의 동작을 단순화하고 성능을 최적화.

5. Raft 알고리즘의 주요 단계

(1) Normal Operation

• 리더가 클라이언트 요청을 처리하고 로그 복제.

(2) Leader Election

• 리더 장애 발생 시 새로운 리더를 선출.

(3) Log Replication

• 리더가 클라이언트 요청을 처리하여 로그 항목을 Follower에 복제.

(4) Crash Recovery

• 장애가 난 노드는 복구 후 로그를 리더로부터 동기화.

6. 주요 용어

7. Raft의 사용 사례

(1) etcd

• Kubernetes에서 사용되는 분산 키-값 저장소.
• 클러스터 상태 데이터를 저장하고 관리.

(2) Consul

• 서비스 디스커버리 및 구성 관리 도구.
• 분산 환경에서 상태를 일관되게 유지.

(3) TiDB

• 분산 SQL 데이터베이스.
• Raft를 통해 데이터 일관성을 유지.

8. Raft 알고리즘의 장단점

장점

1. 구현 용이성:
   • Raft는 이해하기 쉽게 설계되어 Paxos보다 구현이 간단.
2. 강한 일관성:
   • 로그 복제를 통해 데이터 일관성 보장.
3. 높은 안정성:
   • 노드 일부 장애에도 클러스터가 지속적으로 동작.

단점

1. 네트워크 오버헤드:
   • Heartbeat와 로그 복제 때문에 네트워크 트래픽이 증가.
2. 리더 의존성:
   • 리더 장애 시 새로운 리더 선출 과정에서 지연 발생 가능.
3. 확장성 제한:
   • 노드 수가 많아질수록 리더 선출과 로그 복제의 비용이 증가.

9. 결론

Raft는 분산 시스템에서 데이터 일관성과 가용성을 보장하기 위한 강력한 알고리즘입니다. 이해하기 쉬운 설계로 인해 Paxos보다 널리 사용되며, Kubernetes의 etcd와 같은 분산 키-값 저장소에서 중요한 역할을 합니다.