Algorithm

Raft 합의 알고리즘 완전 가이드

Somaz 2025. 12. 31. 07:34
728x90
반응형

Overview

이 가이드는 분산 시스템의 핵심 기술인 Raft 합의 알고리즘을 처음부터 끝까지 완전히 이해할 수 있도록 구성된 종합 학습 자료이다.

 

 

 

 

📅 관련 글

2022.09.26 - [Open Source Software] - Redis(Remote Dictionary Server)란?

2025.04.02 - [CS 지식] - [CS 지식20.] OS 캐시와 디스크 I/O: MySQL, Redis 퍼포먼스 분석

2025.08.12 - [Container Orchestration/Kubernetes] - Kubernetes 환경에서 Redis Redlock 구현하기: 분산 락의 완전한 이해

 

 

학습 목표

이 가이드를 통해 다음을 습득할 수 있다.

  • Raft 알고리즘의 동작 원리와 핵심 개념 완전 이해
  • 분산 시스템에서 합의가 필요한 이유와 해결 방법
  • 리더 선출, 로그 복제, 장애 처리 등 핵심 메커니즘
  • 실제 구현 방법과 코드 예시 (Go 언어)
  • 운영 환경에서의 최적화 기법과 모니터링 방법

 

 

가이드 구성

  1. 기초 개념: Raft란 무엇이며 왜 필요한가
  2. 핵심 구조: 노드 상태, Term 개념, 기본 아키텍처
  3. 동작 원리: 리더 선출과 로그 복제 과정 상세 분석
  4. 안전성: 데이터 일관성과 장애 허용 메커니즘
  5. 실전 활용: 구현 예시, 실제 사용 사례, 최적화 기법

 

 

대상 독자

  • 백엔드 개발자: 분산 시스템 설계에 관심 있는 개발자
  • 시스템 엔지니어: Kubernetes, etcd, Consul 등을 다루는 엔지니어
  • 아키텍트: 고가용성 시스템 설계를 담당하는 아키텍트
  • 학습자: 분산 시스템 이론을 실무에 적용하고 싶은 학습자

 

 

핵심 포인트 미리보기

  • 이해하기 쉬운 설계: Paxos보다 훨씬 간단하고 직관적
  • 강력한 리더 기반: 중앙 집권적 접근으로 복잡성 해결
  • 수학적 안전성: 엄밀하게 증명된 일관성 보장
  • 실전 검증: etcd, Consul, TiDB 등에서 프로덕션 사용

 

 

 

 

 

 

 

 

Raft란 무엇인가?

Raft(Reliable, Replicated, Redundant, And Fault-Tolerant)는 분산 시스템에서 합의(Consensus)를 달성하기 위한 알고리즘이다.

 

2013년 Diego Ongaro와 John Ousterhout이 Stanford에서 개발했으며, 기존의 Paxos 알고리즘보다 이해하기 쉽고 구현하기 간단하다는 것이 가장 큰 장점이다.

 

 

 

 

 

왜 합의 알고리즘이 필요한가?

 

분산 시스템의 근본적 문제

분산 시스템에서는 여러 노드가 같은 상태를 유지해야 한다. 하지만 현실에서는

  • 네트워크 지연/파티션: 메시지가 늦게 도착하거나 아예 전달되지 않음
  • 노드 장애: 서버가 갑자기 죽거나 재시작됨
  • 동시성 문제: 여러 노드가 동시에 서로 다른 결정을 내림

 

 

 

 

합의가 필요한 상황들

 

상황 1: 분산 데이터베이스

  • 노드 A: "계좌 잔액 = 1000원"
  • 노드 B: "계좌 잔액 = 500원"
  • 노드 C: "계좌 잔액 = 1500원" → 어떤 값이 정답인가?

 

상황 2: 분산 락

  • 노드 A: "리소스 X는 내가 사용 중"
  • 노드 B: "리소스 X는 내가 사용 중" → 누가 실제로 사용해야 하는가?

 

상황 3: 리더 선택

  • 노드 A: "내가 리더다"
  • 노드 B: "내가 리더다" → 실제 리더는 누구인가?

 

Raft는 이런 상황에서 모든 노드가 같은 결론에 도달하도록 보장한다.

 

 

 

 

 

 

 

 

 

 

Raft의 핵심 구성 요소

 

 

 

1. 노드의 3가지 상태

Raft에서 각 노드는 다음 3가지 상태 중 하나를 가진다.

 

 

 

 

Leader (리더)

 

역할

  • 모든 클라이언트 요청을 처리
  • 로그 엔트리를 다른 노드들에게 복제
  • Heartbeat를 통해 자신의 리더십 유지

 

특징

  • 클러스터에 최대 1개만 존재
  • 모든 결정을 내리는 중앙 집권적 역할

 

 

Follower (팔로워)

 

역할

  • 리더의 요청에 응답
  • 로그 엔트리를 수신하고 저장
  • 리더의 Heartbeat를 기다림

 

특징

  • 대부분의 노드가 이 상태
  • 수동적 역할 (요청을 먼저 보내지 않음)

 

 

Candidate (후보자)

 

역할

  • 리더 선거를 시작
  • 다른 노드들에게 투표 요청
  • 과반수 득표 시 리더가 됨

 

특징

  • 일시적인 상태 (선거 기간 동안만)
  • Leader 또는 Follower로 전환

 

 

 

 

 

2. Term (임기) 개념

 

Term이란?

  • 논리적 시간 개념
  • 각 Term마다 최대 1명의 Leader 존재
  • Leader 선거가 일어날 때마다 Term 증가
Term 0: [Leader A]
Term 1: [Leader B] 
Term 2: [Leader C]
Term 3: [선거 실패]
Term 4: [Leader A]

 

 

 

 

 

 

 

 

Raft 동작 원리

Raft의 동작은 크게 2단계로 나뉜다.

 

 

 

1단계: Leader Election (리더 선출)

 

선거 시작 조건

  • 클러스터 시작 시 (모든 노드가 Follower)
  • Follower가 리더의 Heartbeat를 받지 못할 때
  • Candidate가 선거에서 승리하지 못할 때

 

선거 과정

 

 

 

 

 

투표 규칙

  • Term 조건: 후보자의 Term이 자신의 Term보다 크거나 같아야 함
  • 최신성 조건: 후보자의 로그가 자신의 로그만큼 최신이어야 함
  • 1표 원칙: 같은 Term에서는 최대 1번만 투표

 

선거 결과

  • Case 1: 과반수 득표 → Leader 당선
  • Case 2: 과반수 실패 → 새로운 Term으로 재선거
  • Case 3: 동시 후보 → Split Vote, 재선거

 

 

 

 

 

 

 

2단계: Log Replication (로그 복제)

 

클라이언트 요청 처리 과정

 

 

 

 

로그 구조

 

각 로그 엔트리 구성

  • Index: 로그 내 위치
  • Term: 엔트리가 생성된 Term
  • Command: 실제 명령어

 

예시

Index: 1  Term: 1  Command: "SET a=10"
Index: 2  Term: 1  Command: "SET b=20"  
Index: 3  Term: 2  Command: "SET c=30"
Index: 4  Term: 2  Command: "SET d=40"

 

 

 

 

복제 과정 상세

 

  1. Leader가 로그 엔트리 생성
    • 새로운 요청이 오면:
      • 로그에 새 엔트리 추가 (uncommitted 상태)
      • 모든 Follower에게 AppendEntries RPC 전송
  2. Follower가 로그 엔트리 검증
    • 받은 엔트리를 검증:
      • 이전 엔트리와 연결성 확인
      • Term 일치성 확인
      • 충돌 시 로그 덮어쓰기
  3. 과반수 복제 후 Commit
    • 과반수 노드가 응답하면:
      • Leader가 엔트리를 committed로 표시
      • 다음 Heartbeat에서 Follower들에게 commit 알림
      • 모든 노드가 해당 엔트리 적용

 

 

 

 

 

 

 

 

 

 

Raft의 안전성 보장

 

 

1. Leader Election Safety

  • 각 Term에서 최대 1명의 Leader만 선출된다

 

보장 방법

  • 과반수 투표 요구
  • 같은 Term에서 노드당 최대 1표
  • Split Vote 시 재선거

 

 

 

2. Log Matching Property

  • 같은 Index와 Term을 가진 엔트리는 같은 내용이다.

 

보장 방법

  • Leader가 특정 Index에 하나의 엔트리만 생성
  • 엔트리는 절대 변경되지 않음

 

 

 

3. Leader Completeness

  • 이전 Term에서 committed된 엔트리는 새 Leader의 로그에 반드시 존재한다.

 

보장 방법

  • 선거 시 로그 최신성 검증
  • 가장 최신 로그를 가진 후보만 당선 가능

 

 

 

4. State Machine Safety

  • 모든 노드가 같은 Index에 같은 명령을 적용한다.

 

보장 방법

  • Leader Completeness
  • Log Matching Property
  • 순차적 적용

 

 

 

 

 

 

 

장애 상황별 처리

 

1. Leader 장애

 

상황: Leader가 갑자기 죽음

 

처리 과정

  1. Follower들이 Heartbeat 타임아웃 감지
  2. 새로운 Term으로 리더 선거 시작
  3. 가장 최신 로그를 가진 노드가 새 Leader
  4. 새 Leader가 미완료 로그 복제 재개

 

결과: 새로운 Leader 선출, 서비스 계속

 

 

 

2. Follower 장애

 

상황: Follower 하나가 죽음

 

처리 과정

  1. Leader가 해당 Follower에게 복제 실패 감지
  2. 나머지 노드들로 과반수 확보 가능하면 계속 진행
  3. 장애 노드가 복구되면 누락된 로그 자동 동기화

 

결과: 과반수 유지 시 서비스 무중단

 

 

 

 

3. 네트워크 파티션

 

상황: 5노드 클러스터가 3+2로 분할

  • 파티션 A (3노드): 과반수 → 정상 동작 가능
  • 파티션 B (2노드): 소수 → 읽기 전용 모드

 

처리:

  • 파티션 A: 새 Leader 선출, 쓰기 가능
  • 파티션 B: Leader 선출 불가, 읽기만 가능
  • 파티션 복구 시: 자동 동기화

 

 

 

4. Split Brain 방지

 

핵심 원리: 과반수 원칙

 

예시 (5노드)

  • 정상: 5노드 중 3노드 이상 동의 필요
  • 파티션: 3+2 분할 시, 3노드 그룹만 동작
  • 보장: 동시에 2개 Leader 불가능

 

수학적 증명

  • N개 노드에서 과반수 = N/2 + 1
  • 두 그룹이 모두 과반수를 가질 수 없음
  • 따라서 Split Brain 불가능

 

 

 

 

 

 

실제 구현 예시

 

기본 구조 (Go 언어)

type RaftNode struct {
    // 상태 정보
    currentTerm int
    votedFor    *int
    log         []LogEntry
    
    // 휘발성 상태
    commitIndex int
    lastApplied int
    
    // Leader 전용 (선거 후 초기화)
    nextIndex   []int
    matchIndex  []int
    
    // 노드 정보
    id    int
    peers []int
    state NodeState
}

type LogEntry struct {
    Term    int
    Index   int
    Command interface{}
}

type NodeState int
const (
    Follower NodeState = iota
    Candidate  
    Leader
)

 

 

 

RequestVote RPC

type RequestVoteArgs struct {
    Term         int // 후보자의 Term
    CandidateID  int // 후보자 ID
    LastLogIndex int // 후보자의 마지막 로그 인덱스
    LastLogTerm  int // 후보자의 마지막 로그 Term
}

type RequestVoteReply struct {
    Term        int  // 현재 Term (후보자 업데이트용)
    VoteGranted bool // 투표 결과
}

func (rf *RaftNode) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
    rf.mu.Lock()
    defer rf.mu.Unlock()
    
    reply.Term = rf.currentTerm
    reply.VoteGranted = false
    
    // Term 조건 확인
    if args.Term < rf.currentTerm {
        return
    }
    
    if args.Term > rf.currentTerm {
        rf.currentTerm = args.Term
        rf.votedFor = nil
        rf.state = Follower
    }
    
    // 투표 조건 확인
    if (rf.votedFor == nil || *rf.votedFor == args.CandidateID) &&
       rf.isLogUpToDate(args.LastLogIndex, args.LastLogTerm) {
        rf.votedFor = &args.CandidateID
        reply.VoteGranted = true
        rf.resetElectionTimeout()
    }
}

func (rf *RaftNode) isLogUpToDate(index, term int) bool {
    lastIndex, lastTerm := rf.getLastLogInfo()
    
    // 더 높은 Term을 가지거나, 같은 Term에서 더 긴 로그
    return term > lastTerm || (term == lastTerm && index >= lastIndex)
}

 

 

 

AppendEntries RPC

type AppendEntriesArgs struct {
    Term         int        // Leader의 Term
    LeaderID     int        // Leader ID
    PrevLogIndex int        // 새 엔트리 직전 로그 인덱스
    PrevLogTerm  int        // PrevLogIndex의 Term
    Entries      []LogEntry // 복제할 엔트리들
    LeaderCommit int        // Leader의 commitIndex
}

type AppendEntriesReply struct {
    Term    int  // 현재 Term
    Success bool // 복제 성공 여부
}

func (rf *RaftNode) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {
    rf.mu.Lock()
    defer rf.mu.Unlock()
    
    reply.Term = rf.currentTerm
    reply.Success = false
    
    // Term 확인
    if args.Term < rf.currentTerm {
        return
    }
    
    rf.resetElectionTimeout()
    
    if args.Term > rf.currentTerm {
        rf.currentTerm = args.Term
        rf.votedFor = nil
    }
    rf.state = Follower
    
    // 로그 일치성 확인
    if args.PrevLogIndex > 0 {
        if len(rf.log) < args.PrevLogIndex ||
           rf.log[args.PrevLogIndex-1].Term != args.PrevLogTerm {
            return
        }
    }
    
    // 엔트리 추가
    if len(args.Entries) > 0 {
        rf.log = rf.log[:args.PrevLogIndex]
        rf.log = append(rf.log, args.Entries...)
    }
    
    // Commit 업데이트
    if args.LeaderCommit > rf.commitIndex {
        rf.commitIndex = min(args.LeaderCommit, len(rf.log))
    }
    
    reply.Success = true
}

 

 

 

 

 

 

실제 사용 사례

 

1. etcd (Kubernetes)

 

용도: Kubernetes 클러스터 상태 저장

 

특징

  • 모든 K8s 설정이 etcd에 저장
  • Raft로 고가용성 보장
  • 일반적으로 3-5개 노드 구성

 

예시 구성

  • etcd-0 (Leader)
  • etcd-1 (Follower)
  • etcd-2 (Follower)

 

 

2. Consul (HashiCorp)

 

용도: 서비스 디스커버리, 설정 관리

 

특징

  • 분산 서비스 메쉬의 중앙 저장소
  • Raft로 데이터 일관성 보장
  • Multi-Datacenter 지원

 

예시 구성

  • consul-server-0 (Leader)
  • consul-server-1 (Follower)
  • consul-server-2 (Follower)

 

 

3. TiKV (TiDB)

 

용도: 분산 데이터베이스의 스토리지 엔진

 

특징

  • Region별로 Raft 그룹 구성
  • 수천 개의 Raft 그룹이 동시 실행
  • 데이터 샤딩과 복제를 동시에 처리

 

 

4. CockroachDB

 

용도: 분산 SQL 데이터베이스

 

특징

  • Range별 Raft 복제
  • 강력한 일관성 보장
  • 자동 장애 복구

 

 

 

 

 

Raft vs 다른 합의 알고리즘

 

vs. Paxos

항목 Raft Paxos
이해도 쉬움 어려움
구현 복잡도 단순 복잡
성능 높음 높음
검증 상대적 최신 오랜 검증
리더십 강한 리더 리더 없음

 

 

 

vs. PBFT (Practical Byzantine Fault Tolerance)

항목 Raft PBFT
장애 모델 Crash Fault Byzantine Fault
성능 높음 낮음
복잡도 단순 매우 복잡
노드 수 요구 2f+1 3f+1
사용 케이스 일반 분산 시스템 블록체인, 보안 중요

 

 

 

 

 

 

 

Raft 최적화 기법

 

1. 배치 처리 (Batching)

// 여러 요청을 한 번에 처리
func (rf *RaftNode) batchAppend() {
    entries := []LogEntry{}
    
    // 여러 클라이언트 요청을 수집
    for i := 0; i < batchSize && len(rf.pendingRequests) > 0; i++ {
        req := <-rf.pendingRequests
        entry := LogEntry{
            Term:    rf.currentTerm,
            Index:   rf.getNextIndex(),
            Command: req.Command,
        }
        entries = append(entries, entry)
    }
    
    // 한 번에 복제
    rf.replicateEntries(entries)
}

 

 

 

 

2. 파이프라이닝 (Pipelining)

// 이전 복제 완료를 기다리지 않고 다음 복제 시작
func (rf *RaftNode) pipelineReplication() {
    for _, peer := range rf.peers {
        go func(peerID int) {
            for {
                // 다음 전송할 엔트리 확인
                entries := rf.getNextEntries(peerID)
                if len(entries) > 0 {
                    rf.sendAppendEntries(peerID, entries)
                }
                time.Sleep(10 * time.Millisecond)
            }
        }(peer)
    }
}

 

 

 

 

3. 로그 압축 (Log Compaction)

// 오래된 로그를 스냅샷으로 압축
func (rf *RaftNode) createSnapshot() {
    snapshot := rf.stateMachine.CreateSnapshot()
    
    // 스냅샷 이전의 로그 제거
    rf.log = rf.log[rf.lastSnapshotIndex:]
    rf.lastSnapshotIndex = rf.commitIndex
    rf.lastSnapshotTerm = rf.currentTerm
    
    rf.saveSnapshot(snapshot)
}

 

 

 

 

 

운영 시 주의사항

 

1. 클러스터 크기 선택

 

권장 크기:

  • 3노드: 1개 장애 허용 (개발/테스트)
  • 5노드: 2개 장애 허용 (프로덕션)
  • 7노드: 3개 장애 허용 (고가용성)

 

주의사항:

  • 홀수 개 노드 사용 (Split Vote 방지)
  • 너무 많으면 성능 저하
  • 지리적 분산 시 네트워크 지연 고려

 

 

2. 타임아웃 설정

// 일반적인 타임아웃 설정
const (
    ElectionTimeoutMin = 150 * time.Millisecond
    ElectionTimeoutMax = 300 * time.Millisecond
    HeartbeatInterval  = 50 * time.Millisecond
    RPCTimeout        = 100 * time.Millisecond
)

// 네트워크 환경에 따른 조정
if rf.networkLatency > 50*time.Millisecond {
    ElectionTimeoutMin *= 2
    ElectionTimeoutMax *= 2
    HeartbeatInterval *= 2
}

 

 

 

 

3. 모니터링 메트릭

# 모니터링해야 할 핵심 지표
- raft_leader_elections_total
- raft_leader_last_contact_seconds
- raft_log_entries_total
- raft_log_commits_total  
- raft_rpc_duration_seconds
- raft_cluster_size
- raft_nodes_health

 

 

 

 

4. 백업 및 복구

# etcd 백업 예시
etcdctl snapshot save backup.db

# 복구
etcdctl snapshot restore backup.db \
  --name m1 \
  --initial-cluster m1=http://host1:2380 \
  --initial-cluster-token etcd-cluster-1

 

 

 

 

 

마무리

Raft는 분산 시스템에서 이해하기 쉽고 구현하기 간단한 합의 알고리즘이다. 강력한 Leader 기반의 접근 방식으로 복잡한 분산 문제를 우아하게 해결한다.

 

 

핵심 포인트

  • 단순함: Paxos보다 훨씬 이해하기 쉬운 설계
  • 안전성: 수학적으로 증명된 안전성 보장
  • 실용성: 많은 프로덕션 시스템에서 검증됨
  • 확장성: 클러스터 크기에 따른 적절한 성능

 

선택 기준

  • 일반적인 분산 시스템: Raft 추천
  • 매우 높은 성능 요구: 최적화된 Paxos 고려
  • 비잔틴 장애 대응: PBFT 계열 알고리즘 필요
  • 단순한 요구사항: 단순한 Master-Slave 복제도 고려

 

 

Raft를 이해하면 현대 분산 시스템의 핵심 동작 원리를 파악할 수 있고, etcd, Consul 같은 도구들의 내부 동작도 명확하게 이해할 수 있게 된다.

 

 

 

 

 

 

 

 

Reference

 

원본 논문 및 학술 자료

 

주요 구현체

 

학습 자료

 

동영상 강의

 

도구 및 라이브러리

 

벤치마크 및 성능 분석

 

프로덕션 사용 사례

 

추가 읽을거리

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Algorithm'의 다른글

  • 현재글Raft 합의 알고리즘 완전 가이드
댓글

티스토리툴바