Consensus

📖 상세 설명

Consensus(합의)는 분산 컴퓨팅의 근본적인 문제입니다. 여러 노드가 네트워크로 연결된 시스템에서, 노드 장애나 네트워크 분리가 발생해도 모든 노드가 동일한 결정에 도달해야 합니다. 이 문제는 1985년 FLP Impossibility 정리에서 증명되었듯이, 비동기 시스템에서는 이론적으로 불가능하지만, 실용적인 가정 하에서 여러 알고리즘이 이를 해결합니다.

합의 알고리즘의 역사는 1989년 Leslie Lamport가 발표한 Paxos로 시작됩니다. Paxos는 수학적으로 완벽하지만 이해와 구현이 매우 어려웠습니다. 2013년 Diego Ongaro는 Paxos와 동일한 안전성을 보장하면서도 이해하기 쉬운 Raft를 발표했고, 이후 etcd, Consul 등에서 널리 채택되었습니다.

합의 알고리즘은 크게 CFT(Crash Fault Tolerant)와 BFT(Byzantine Fault Tolerant)로 나뉩니다. CFT는 노드가 단순 중단되는 장애만 처리하고(Raft, Paxos), BFT는 노드가 악의적으로 행동하는 비잔틴 장애까지 처리합니다(PBFT, Tendermint). BFT는 블록체인에서 주로 사용되며, CFT보다 더 많은 노드(3f+1 vs 2f+1)와 통신 오버헤드가 필요합니다.

실무에서 합의 알고리즘은 분산 데이터베이스(CockroachDB, TiDB), 메시지 시스템(Kafka KRaft, NATS JetStream), 서비스 디스커버리(Consul, etcd), 블록체인(Ethereum, Tendermint)의 핵심입니다. 시스템 요구사항에 맞는 알고리즘 선택이 성능과 안정성을 결정합니다.

합의 알고리즘의 핵심 속성

📊 알고리즘 비교

주요 합의 알고리즘 비교

사용 사례별 권장 알고리즘

💻 코드 예제

Raft 합의 과정 시뮬레이션 (Python)

import random
import time
from enum import Enum
from dataclasses import dataclass

class NodeState(Enum):
    FOLLOWER = "follower"
    CANDIDATE = "candidate"
    LEADER = "leader"

@dataclass
class LogEntry:
    term: int
    command: str

class RaftNode:
    def __init__(self, node_id: str, peers: list):
        self.id = node_id
        self.peers = peers
        self.state = NodeState.FOLLOWER
        self.current_term = 0
        self.voted_for = None
        self.log = []
        self.commit_index = 0

    def request_vote(self, candidate_term: int, candidate_id: str) -> tuple:
        """투표 요청 처리"""
        # 후보의 Term이 오래되었으면 거부
        if candidate_term < self.current_term:
            return self.current_term, False

        # 더 높은 Term이면 Follower로 전환
        if candidate_term > self.current_term:
            self.current_term = candidate_term
            self.state = NodeState.FOLLOWER
            self.voted_for = None

        # 아직 투표 안했으면 투표
        if self.voted_for is None or self.voted_for == candidate_id:
            self.voted_for = candidate_id
            return self.current_term, True

        return self.current_term, False

    def start_election(self) -> bool:
        """선거 시작"""
        self.state = NodeState.CANDIDATE
        self.current_term += 1
        self.voted_for = self.id
        votes = 1  # 자기 자신 투표

        print(f"🗳️ [{self.id}] 선거 시작 (Term {self.current_term})")

        # 다른 노드에게 투표 요청 (시뮬레이션)
        for peer in self.peers:
            # 실제로는 RPC 호출
            vote_granted = random.random() > 0.3  # 70% 확률로 투표
            if vote_granted:
                votes += 1
                print(f"  ✅ {peer}로부터 투표 획득")
            else:
                print(f"  ❌ {peer} 투표 거부")

        # 과반수 득표 시 Leader
        quorum = (len(self.peers) + 1) // 2 + 1
        if votes >= quorum:
            self.state = NodeState.LEADER
            print(f"👑 [{self.id}] Leader 당선! ({votes}/{len(self.peers)+1})")
            return True
        else:
            self.state = NodeState.FOLLOWER
            print(f"😔 [{self.id}] 낙선 ({votes}/{len(self.peers)+1})")
            return False

    def append_entries(self, leader_term: int, entries: list) -> tuple:
        """로그 복제 요청 처리"""
        if leader_term < self.current_term:
            return self.current_term, False

        self.current_term = leader_term
        self.state = NodeState.FOLLOWER
        self.log.extend(entries)

        return self.current_term, True

# 시뮬레이션 실행
if __name__ == "__main__":
    nodes = {
        "node-1": RaftNode("node-1", ["node-2", "node-3", "node-4", "node-5"]),
        "node-2": RaftNode("node-2", ["node-1", "node-3", "node-4", "node-5"]),
        "node-3": RaftNode("node-3", ["node-1", "node-2", "node-4", "node-5"]),
    }

    print("=== Raft 합의 시뮬레이션 (5노드 클러스터) ===\n")

    # 무작위 노드가 선거 시작
    candidate = random.choice(list(nodes.values()))
    candidate.start_election()

etcd 클러스터 상태 확인

# etcd 클러스터 상태 확인
etcdctl endpoint status --cluster -w table

# 출력 예시:
# +------------------+------------------+---------+---------+-----------+
# |     ENDPOINT     |        ID        | VERSION | DB SIZE | IS LEADER |
# +------------------+------------------+---------+---------+-----------+
# | 192.168.1.1:2379 | 8e9e05c52164694d |  3.5.12 |   20 MB |     true  |
# | 192.168.1.2:2379 | 91bc3c398fb3c146 |  3.5.12 |   20 MB |    false  |
# | 192.168.1.3:2379 | fd422379fda50e48 |  3.5.12 |   20 MB |    false  |
# +------------------+------------------+---------+---------+-----------+

# Raft 상태 확인
etcdctl endpoint status -w json | jq '.[] | {endpoint, raftTerm, raftIndex, isLeader}'

# Leader 이전 (유지보수용)
etcdctl move-leader 91bc3c398fb3c146

🗣️ 실무 대화 예시

⚠️ 주의사항

🔗 관련 용어

📚 더 배우기