Distributed Systems - 04. 합의 알고리즘

합의 알고리즘 — 여러 노드가 하나의 값을 정하는 법

2019년 한 Elasticsearch 클러스터에서 split-brain(뇌 분리)이 발생했다. 두 데이터센터 사이 네트워크가 30초간 끊겼다. 양쪽 데이터센터의 노드가 각자 자기를 "마스터"로 선언했다. 두 마스터는 같은 데이터에 서로 다른 쓰기를 적용했다. 네트워크가 복구됐을 때 두 마스터의 상태가 충돌했고, 시스템은 어느 쪽이 진짠지 결정하지 못해 일부 데이터를 잃었다.

이 사태의 원인은 — "누가 진짜 마스터인가"를 노드들이 동의하지 못한 것이다. 합의(consensus)가 없었다. 분산 시스템에선 이런 "동의"가 필요한 상황이 자주 온다 — 누가 리더인가, 다음 연산은 무엇인가, 클러스터에 새 노드를 추가할까. 이 글은 여러 노드가 하나의 값에 동의하게 만드는 알고리즘을 다룬다.

비유로 감 잡기 — 이사회가 CEO를 선출하는 상황

한 회사의 이사회가 CEO를 선출해야 한다고 하자. 이사 7명이 회의실에 모여 투표한다. 과반수(4명 이상)가 한 사람에게 몰리면 그가 CEO가 된다. 단순하다.

그런데 상황이 꼬이기 시작한다. 한 이사가 회의에 안 나왔다. 한 이사의 발언이 다른 이사에게 안 전해졌다. 회의실 A 그룹과 회의실 B 그룹이 통신이 끊겨 각자 회의를 진행했다. 한 이사가 의도적으로 A 그룹엔 "찬성"이라 하고 B 그룹엔 "반대"라 말했다.

이 모든 상황에서 — 한 명의 CEO만 선출돼야 한다. 두 명이 동시에 CEO를 자칭하면, 회사는 두 방향으로 갈라진다.

이게 바로 합의 알고리즘이 푸는 문제다. 결함이 있어도, 통신이 안 되어도, 거짓말쟁이가 있어도 — 결국 모든 정상 이사가 같은 CEO를 인정하게 만드는 것.

비유의 한계 — 이사회 비유는 '단발성 결정'을 가정한다. CEO는 한 번 뽑으면 끝. 하지만 분산 시스템의 합의는 지속적 — 다음 연산, 다음 연산 계속 결정해야 한다. 또한 이사회는 사람이 협상하지만, 시스템은 명확한 규칙을 기계적으로 따른다. 비유는 '지속성·기계적 규칙'에서 무너진다.

"합의"란 — 왜 필요한가, 왜 어려운가

합의(consensus)란 — 여러 노드가 하나의 값에 동의하는 것. 그 값이 "리더가 누구인가", "다음 로그 엔트리가 뭔가", "이 트랜잭션을 커밋할까" 등 뭐든 될 수 있다. 핵심은 — 모든 정상 노드가 같은 결론에 도달한다는 것.

왜 합의가 필요한가. 분산 시스템에선 한 노드가 결정하면 다른 노드들이 따라야 한다. 그렇지 않으면 — 각자 다른 결정을 하고 시스템이 갈라진다. 앞서 Elasticsearch 사례처럼. 합의는 이 갈라짐을 막는 장치.

왜 합의가 어려운가. 노드는 언제든 죽을 수 있고, 네트워크는 분단될 수 있고, 심지어 노드가 거짓말을 할 수도 있다. 이 모든 결함 환경에서 "모든 정상 노드가 같은 결론에 도달한다"를 보장하는 게 어렵다. 어떤 결함을 다루느냐에 따라 알고리즘과 비용이 다르다.

가장 단순한 형태 — 모두 동의, 결함 없음

이해를 위해 가장 단순한 형태부터 본다. 모든 노드가 살아 있고, 네트워크도 안정적이고, 거짓말쟁이도 없다. 이때 합의는 쉽다. 한 노드가 "값 V로 하자"고 제안하면, 다른 노드들이 다 동의하면 끝.

물론 현실에선 이런 환경이 없다. 하지만 출발점으로 중요하다 — "결함이 없으면 합의는 쉽다"는 사실. 합의가 어려운 건 결함 때문이다.

가장 어려운 형태 — 비잔틴 환경

반대 극단. 노드 중 일부가 거짓말을 한다. 한 노드가 A 노드에게는 "찬성"이라 말하고, B 노드에게는 "반대"라 말한다. 또는 "이 값 V를 받았다"고 하고서는 실제로는 안 받았다. 이런 환경을 비잔틴 결함이라 부른다.

왜 "비잔틴"인가. 1982년 Lamport, Shostak, Pease가 "비잔틴 장군 문제"라는 논문에서 이 문제를 형식화했다. 비잔틴 제국의 여러 장군이 적을 공격할지 말지 합의해야 하는데, 일부 장군과 메신저가 배신자여서 거짓 정보를 퍼뜨린다. 이 상황에서 어떻게 합의할까가 논문의 질문.

비잔틴 합의는 — crash 결함만 다루는 합의보다 훨씬 어렵다. 필요 노드 수도 더 많고 (f명의 배신자를 견디려면 3f+1개 노드 필요), 메시지도 더 오가고, 동기적 네트워크(지연에 상한)가 필요하다. 그래서 — 모든 시스템이 비잔틴 합의를 쓰진 않는다. 퍼블릭 블록체인(비트코인, 이더리움), 여러 조직이 공유하는 시스템에서나 쓰인다. 같은 회사 내부 클러스터에선 비잔틴 결함이 거의 일어나지 않으니까.

그 사이 — crash 결함만 다루는 실용적 합의

양극단 사이에 현실의 대부분 시스템이 있다. 노드가 죽거나 느려질 수는 있지만, 거짓말은 안 한다는 환경. 이런 결함을 crash 결함이라 부른다. 같은 회사가 운영하는 클러스터(etcd, Zookeeper, Kafka)가 보통 이 범주.

crash 결함 환경에서 합의를 다루는 대표 알고리즘이 Paxos와 Raft다. 둘 다 같은 문제를 다루지만, 접근이 다르다.

핵심 아이디어 — 과반수 (quorum)

Paxos와 Raft가 공유하는 핵심 아이디어는 과반수(quorum)다. 모든 노드가 동의하는 게 아니라, 과반수가 동의하면 결정으로 본다.

왜 과반수인가. 두 과반수 그룹은 항상 겹친다 (수학적 사실). 7명 중 4명이 "값 V로 하자"고 동의했으면, 다른 4명이 "값 W로 하자"고 동의하려면 — 적어도 한 명은 겹쳐야 한다 (4+4=8 > 7). 그 겹치는 사람이 두 그룹의 제안을 다 봤으니, 두 결정이 충돌하지 않게 조율된다.

이 과반수 아이디어가 — f개의 노드가 죽어도 합의가 진행되게 한다. 전체 2f+1개 노드가 있으면, f개가 죽어도 과반수(f+1개)가 살아 있어 합의를 이룰 수 있다.

Paxos — 수학적 접근

Leslie Lamport가 1989년에 발표한 Paxos는 합의 알고리즘의 원형이다. 세 역할을 나누는 게 특징.

• 제안자(Proposer) — 값을 제안하는 노드.
• 수락자(Acceptor) — 제안을 받아들일지 투표하는 노드.
• 학습자(Learner) — 결정된 값을 배우는 노드.

합의는 두 단계로 일어난다.

1. Prepare (준비) — 제안자가 "이 번호 N으로 제안하겠다"고 수락자들에게 알린다. 수락자들은 N이 자기가 본 가장 큰 번호면 "OK, 이전에 받아들인 제안이 있으면 알려줌"이라 응답한다.
2. Accept (수락) — 제안자가 "N으로 이 값 V를 받아들여라"고 수락자들에게 보낸다. 과반수 수락자가 OK하면 V가 결정된다.

이 과정의 묘미 — 이미 결정된 값은 번복되지 않는다. 더 큰 번호의 제안이 와도, 그 제안자는 이전에 결정된 값을 따라야 한다 (Prepare 단계에서 알게 되므로). 두 제안자가 경쟁해도 결국 같은 값에 도달한다.

Paxos의 강점은 수학적 엄격함이다. 그게 동시에 약점이기도 하다 — 이해하고 구현하기 어렵다. Google Chubby, Spanner, Zookeeper가 Paxos 기반이지만, 각자 변형을 가했다.

Raft — 엔지니어링 접근

2014년 Diego Ongaro와 John Ousterhout이 발표한 Raft는, Paxos와 같은 보장을 제공하되 이해하고 구현하기 쉽게 설계했다. 철학의 차이다 — Paxos는 수학적 우아함, Raft는 엔지니어링 단순함.

Raft의 핵심 설계 선택 — 리더(Leader)라는 단일 노드가 모든 결정을 주도한다. Paxos의 세 역할 분리 대신, 리더 하나가 클라이언트 요청을 받고, 팔로워(Follower)들에 전파하고, 과반수 확인을 받아 커밋한다. 단순한 구조.

flowchart TD
    C[Client] -->|모든 쓰기 요청| L[Leader]
    L -->|로그 엔트리 전파| F1[Follower 1]
    L -->|로그 엔트리 전파| F2[Follower 2]
    L -->|로그 엔트리 전파| F3[Follower 3]
    L -. 과반수 ack 시 커밋 .- L

세 가지 하위 문제로 쪼개진다.

리더 선출. 리더가 죽으면 새 리더를 뽑아야 한다. 각 노드는 일정 시간 동안 리더의 하트비트(주기적 신호)를 못 받으면 — 후보(Candidate)로 변신해 자기를 리더로 추대해달라 다른 노드들에게 요청한다. 과반수가 동의하면 새 리더가 된다. 한 번에 한 리더만 존재하도록 term 번호(선거 번호)로 구분한다.

로그 복제. 리더가 클라이언트 요청을 받으면 자기 로그에 연산을 적고, 모든 팔로워에 전송한다. 과반수 팔로워가 "받았다"고 확인(ack)하면, 그 연산을 커밋(실제 적용). 클라이언트에게 결과를 반환한다.

안전성. 리더가 바뀌어도 모든 노드가 같은 로그를 갖도록 보장. 새 리더는 자기 로그를 기준으로 팔로워들의 로그를 맞춘다. 이게 가능한 이유 — 과반수가 동의한 연산은 이미 "결정된" 것이므로, 새 리더도 그걸 따라야 한다.

Paxos vs Raft 비교

구분	Paxos	Raft
철학	수학적 우아함	엔지니어링 단순함
역할 구조	제안자·수락자·학습자 분리	리더가 모든 것 주도
강점	수학적 엄격함, 유연성	이해·구현 용이
약점	이해·구현 어려움	구조 고정 (유연성 적음)
대표 구현	Chubby, Spanner, Zookeeper	etcd, Consul, Kafka KRaft

왜 합의가 어려운가 — FLP 정리

여기까지 합의 알고리즘이 "어떻게 작동하는가"를 봤다. 이제 "왜 어려운가"를 묻자. 1985년 Fischer, Lynch, Paterson이 증명한 FLP 정리가 핵심이다.

한 문장으로 — 비동기 네트워크에서 단 하나의 노드라도 크래시할 수 있으면, 합의를 항상 보장하는 결정적 알고리즘은 없다. "비동기 네트워크"란 메시지 지연에 상한이 없는 환경. "결정적"이란 랜덤 없이 항상 같은 흐름으로 가는 알고리즘.

왜 그런가. 비동기 환경에선 "느린 노드"와 "죽은 노드"를 구분할 방법이 없다. 응답이 안 오는 게 — 느린 건지 죽은 건지 알 수 없다. 그래서 — 알고리즘은 영원히 기다리거나, 일단 결정을 내리되 위험을 감수해야 한다. 둘 다 "완벽한 보장"은 아니다.

그런데 현실에선 Paxos와 Raft가 잘 작동한다. 어떻게 FLP를 우회하나.

• 타임아웃 활용 — "느린 노드"와 "죽은 노드"를 구분하기 위해 시간 제한을 둔다. 응답이 N초 안에 안 오면 죽은 것으로 간주. 현실의 시스템은 사실상 부분 동기(partially synchronous)다 — 대부분의 시간엔 지연에 상한이 있다.
• 과반수 활용 — 모든 노드의 동의가 아니라 과반수의 동의로 충분. 일부 노드가 죽거나 느려도 진행.

FLP가 "완벽한 합의는 결정적 알고리즘으로는 어렵다"고 했지만, 현실에선 "충분히 좋은" 합의가 가능하다. 그게 Paxos와 Raft의 실용적 가치다.

Crash 결함 vs 비잔틴 결함 — 다시 비교

양극단을 다뤘으니, 이제 비교 표로 정리한다.

구분	Crash 결함 (Paxos, Raft)	비잔틴 결함 (PBFT, 블록체인)
노드가 할 수 있는 나쁜 행동	느려지거나 멈춤	위장, 거짓, 악의적 행동
필요 노드 수 (f개 결함 견디려면)	2f+1	3f+1
네트워크 가정	부분 동기 (타임아웃 기반)	동기 (지연 상한)
메시지 복잡도	O(N)	O(N²)
적합 환경	신뢰할 수 있는 기관의 클러스터	다수 기관 공유 시스템, 퍼블릭 블록체인
대표 구현	Raft (etcd, Consul), Paxos (Chubby, Spanner)	PBFT (Hyperledger), Tendermint

이 표가 말하는 점 — 비잔틴 합의는 훨씬 비싸다. 노드도 더 많고, 메시지도 더 오가고, 네트워크 가정도 강하다. 그래서 신뢰할 수 있는 환경에서는 굳이 비잔틴 합의를 쓰지 않는다.

설계 사례 — Raft의 핵심 흐름 간소화

Raft의 핵심 아이디어를 의사코드로 본다. 완전한 구현은 수천 줄이지만, 핵심은 리더 선출과 로그 복제 두 가지.

리더 선출

class RaftNode {
    enum Role { FOLLOWER, CANDIDATE, LEADER }

    Role role = Role.FOLLOWER;
    int currentTerm = 0;     // 선거 번호
    List<LogEntry> log = new ArrayList<>();

    // 리더의 하트비트가 일정 시간 없으면 선거 시작
    void startElection() {
        role = Role.CANDIDATE;
        currentTerm++;
        int votes = 1;  // 자기 표

        for (Node peer : peers) {
            // 다른 노드에 "나를 리더로 뽑아달라" 요청
            if (peer.requestVote(currentTerm, self.id())) {
                votes++;
            }
        }

        if (votes > peers.size() / 2) {
            becomeLeader();  // 과반수 득표 → 리더로
        }
    }

    void becomeLeader() {
        role = Role.LEADER;
        sendHeartbeats();  // 즉시 다른 노드에 "내가 리더다" 알림
    }
}

로그 복제

class RaftLeader {
    void handleClientCommand(Command cmd) {
        // 1. 리더의 로그에 연산 추가
        LogEntry entry = new LogEntry(currentTerm, cmd);
        log.add(entry);

        // 2. 모든 팔로워에 전파
        for (Node peer : peers) {
            replicate(peer, entry);
        }
        // 3. 과반수 ack가 오면 커밋 (비동기)
    }

    void tryCommit() {
        int n = findMajorityMatchIndex();  // 과반수가 반영한 가장 큰 인덱스
        if (n > commitIndex) {
            commitIndex = n;
            applyCommitted();   // 상태 기계에 적용
            respondToClient();  // 클라이언트에 응답
        }
    }
}

핵심 — 리더가 로그에 연산을 추가하고, 과반수 팔로워가 확인하면 커밋. 리더가 죽으면 새 리더가 선출되고, 새 리더는 자기 로그를 기준으로 팔로워들의 로그를 맞춘다.

합의 위반/오용 감지

신호	의미
두 노드가 동시에 리더를 자처 (split-brain)	리더 선출 합의 부재
죽은 리더의 쓰기가 커밋됨	과반수 확인 없이 커밋
팔로워의 로그가 리더와 영원히 안 맞음	로그 복구 메커니즘 결함
선출이 빈번하게 발생	타임아웃 설정 잘못 — 네트워크 지연을 장애로 오판
과반수가 안 모여도 진행	쿼럼 미흡 — 일관성 위반
신뢰 환경에 비잔틴 합의 사용	오버엔지니어링

합의의 실제 사용처

합의는 보이지 않는 곳에서 널리 쓰인다. 어디서 "동의"가 필요하면 합의가 있다.

• etcd — Kubernetes 클러스터의 모든 상태 저장. Raft 기반. k8s의 "사실은 무엇인가"를 etcd가 결정.
• Zookeeper — Hadoop, Kafka(KRaft 이전)의 조정 서비스. ZAB(Zookeeper Atomic Broadcast, Paxos 변형).
• Consul — 서비스 디스커버리 + KV 저장소. Raft 기반.
• Kafka KRaft — Kafka 3.3+에서 Zookeeper를 대체한 Raft 기반 메타데이터 관리.
• Spanner — Google의 글로벌 DB. Paxos 기반 복제.
• CockroachDB, TiDB, YugabyteDB — 분산 SQL DB. Raft 기반 복제.

이 시스템들의 공통점 — "여러 노드가 동의해야 하는 결정"이 있다. 리더가 누구인지, 다음 연산이 뭔지, 클러스터 구성이 어떻게 됐는지. 그 결정을 합의로 내린다.

다음으로 — 분산 트랜잭션

합의가 "하나의 값에 동의"라면, 분산 트랜잭션(07편)은 "여러 단계의 원자적 변경"을 다룬다. 주문→결제→재고 감소가 모두 성공하거나 모두 실패해야 하는 흐름. 2PC가 합의를 사용하지만, 블로킹 한계가 있다. Saga는 합의 없이 보상으로 다룬다.

합의의 핵심 통찰 — "여러 노드가 동의한다"는 건 가능하지만 완벽하진 않다 (FLP 정리). 실용적 알고리즘(Paxos, Raft)은 타임아웃과 과반수로 FLP를 우회한다. 이 우회가 가능한 이유 — 현실의 시스템이 완전히 비동기적이지 않기 때문. 타임아웃이라는 물리적 시간 개념을 도입함으로써, "느린 노드"와 "죽은 노드"를 구분할 수 있게 된다. 시간(09편)이 합의의 숨은 기반이다.

---

참고

• Lamport — "The Part-Time Parliament" (ACM TOCS, 1998), Paxos 원 논문 — 접근 2026-07-20
• Lamport — "Paxos Made Simple" (ACM SIGACT News, 2001) — 접근 2026-07-20
• Ongaro, Ousterhout — "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014), Raft 원 논문 — 접근 2026-07-20
• Fischer, Lynch, Paterson — "Impossibility of Distributed Consensus with One Faulty Process" (JACM, 1985), FLP 정리 — 접근 2026-07-20
• Lamport, Shostak, Pease — "The Byzantine Generals Problem" (ACM TOPLAS, 1982) — 접근 2026-07-20
• Castro, Liskov — "Practical Byzantine Fault Tolerance" (OSDI 1999), PBFT — 접근 2026-07-20
• Kleppmann — (O'Reilly, 2017), Ch.9 (일관성과 합의)