합의 — 유미위키

합의는 여러 서버가 값 하나를 함께 정하게 하는 일입니다. 서버마다 다른 값을 내놓아도 끝에는 모두 같은 값을 고릅니다. 한번 정한 값은 누구도 뒤집지 않습니다. 몇 대가 죽거나 메시지가 늦게 도착해도 이 약속이 지켜져야 합니다.

쉽고 빠른 이해

합의는 서버 여러 대가 「다음 값은 이것」을 한목소리로 정하는 일입니다. 예를 들어 서버 세 대가 「지금 대표는 누구인가」를 정한다면, 셋이 서로 다른 대표를 믿는 일이 없어야 합니다.

이게 없으면 서버마다 다른 값을 믿게 됩니다. 한쪽은 주문이 들어왔다고 알고 다른 쪽은 모릅니다. 대표가 둘이 되어 같은 데이터를 따로 고치기도 합니다.

어떻게 도나:

한 서버가 값을 내놓습니다
다른 서버들이 받아들였다고 답합니다
절반이 넘는 서버가 받아들이면 그 값으로 정해집니다
정해진 값은 다시 바뀌지 않습니다

대가가 있습니다. 절반이 넘는 서버와 연락이 닿아야 값을 정할 수 있습니다. 네트워크가 갈라져 적은 쪽에 남은 서버들은 기다리기만 합니다. 메시지를 여러 번 주고받아야 해서 서버 한 대에 쓰는 것보다 느립니다.

그래서 절대 갈리면 안 되는 값(대표, 락)에만 씁니다. 잠깐 달라도 되는 값(조회수)에는 안 씁니다.

상세

「합의」는 일상에서 「합의된 표준」처럼 사람들이 뜻을 모았다는 뜻으로도 씁니다. 이 편이 다루는 것은 분산 시스템의 합의입니다. 여러 컴퓨터가 네트워크로 메시지를 주고받으며 값 하나를 함께 정하는 계산 문제입니다.

비유로 보는 합의

친구 다섯이 단체 문자로 저녁 메뉴를 정한다고 해 봅시다. 누구는 짜장면, 누구는 김밥을 말합니다. 문자가 늦게 가기도 합니다. 누구는 휴대폰이 꺼져 답이 없습니다.

그래도 끝에는 모두가 같은 메뉴를 알고 식당에 가야 합니다. 두 명은 중국집으로, 세 명은 분식집으로 가면 실패입니다. 합의는 이 상황을 사람 대신 컴퓨터가 겪는 것입니다.

입력과 출력

앞에서 서버라고 부른 것, 곧 합의에 참여하는 컴퓨터 하나하나를 노드라고 부릅니다. 이제부터는 노드로 통일합니다.

입력은 노드마다 하나씩 내놓는 값입니다. 앞에서 「값을 내놓는다」고 한 이 값이 제안입니다. 출력은 노드마다 내리는 결정 하나입니다.

결정이 올바르려면 세 조건을 모두 지켜야 합니다.

조건	뜻	어기면 생기는 일
일치	결정을 내린 노드들은 모두 같은 값을 골랐다	노드끼리 서로 다른 값을 믿는다
타당성	결정된 값은 어떤 노드가 제안한 값이다	아무도 원하지 않은 값이 정해진다
종료	멈추지 않은 노드는 언젠가 결정을 내린다	영원히 기다리며 아무것도 못 한다

타당성은 당연해 보이지만 빼면 문제가 싱거워집니다. 「무조건 0 을 고른다」는 규칙만으로도 일치와 종료를 지킬 수 있기 때문입니다. 제안된 값 가운데서 골라야 한다는 조건이 있어야 노드끼리 실제로 소통하게 됩니다.

조건을 두 무리로 가르기

위 세 조건은 성격이 다른 두 무리로 나뉩니다. 일치와 타당성은 안전성입니다. 「나쁜 일이 절대 일어나지 않는다」는 약속입니다.

종료는 활성입니다. 「좋은 일이 언젠가 일어난다」는 약속입니다. 이 둘을 가르는 까닭은 아래 「늘 끝나는 방법은 없다」에서 드러납니다. 실제 알고리즘은 안전성을 늘 지키고 활성은 조건이 맞을 때만 지킵니다.

어려운 까닭

노드 하나에서 값을 정하는 일은 쉽습니다. 어려움은 노드가 여럿이고 서로 메시지로만 대화한다는 데서 옵니다.

메시지는 늦게 도착하거나 사라질 수 있습니다. 노드는 도중에 멈출 수 있습니다. 한 노드가 답이 없을 때 그 노드가 죽은 것인지 메시지가 늦는 것인지 알 수 없습니다.

그래서 「답 없는 노드는 죽었다고 치고 넘어가자」는 규칙이 위험합니다. 그 노드가 살아 있었다면 다른 값을 따로 정했을 수 있습니다. 반대로 「모두가 답할 때까지 기다리자」면 한 대만 멈춰도 전체가 멈춥니다.

과반이 열쇠인 까닭

대부분의 합의 알고리즘은 이 딜레마를 정족수로 풉니다. 정족수는 결정에 필요한 최소 노드 수입니다. 흔히 전체의 과반을 씁니다. 모두를 기다리지 않고 과반만 받아들이면 결정합니다.

과반이 통하는 까닭은 과반 두 무리가 반드시 한 노드 이상 겹치기 때문입니다. 노드가 다섯이면 과반은 셋입니다. 세 노드짜리 무리 둘을 어떻게 골라도 적어도 한 노드는 양쪽에 다 들어갑니다.

차례로 보면 이렇습니다. 먼저 노드 셋이 값 X 를 받아들여 X 로 결정됐습니다. 나중에 누군가 다른 노드 셋을 모아 값 Y 를 정하려 합니다.

이 나중 무리에도 X 를 받아들인 노드가 적어도 한 대 끼어 있습니다. 그 노드가 「이미 X 를 받아들였다」고 알립니다. 그러면 나중 무리는 Y 대신 X 를 따르게 되어 결정이 둘로 갈리지 않습니다. 이 알림을 주고받는 규칙을 어떻게 짜는지가 알고리즘마다 다릅니다.

과반만 있으면 되므로 몇 대가 멈춰도 견딥니다. 멈출 수 있는 노드 수를 f 라고 하면 노드가 2f+1 대 있어야 합니다. 다섯 대면 두 대까지, 세 대면 한 대까지 멈춰도 결정이 이어집니다.

노드 수	과반	멈춰도 되는 노드 수
3	2	1
4	3	1
5	3	2

표에서 네 대가 세 대보다 더 버티지 못한다는 점이 보입니다. 과반이 커지기만 하고 견디는 수는 그대로입니다. 그래서 합의를 쓰는 시스템은 흔히 노드 수를 홀수로 맞춥니다.

한 번 결정되는 흐름

알고리즘마다 세부는 달라도 뼈대는 비슷합니다. 한 노드가 값을 제안합니다. 다른 노드들이 그 값을 받아들입니다. 과반이 모이면 결정합니다.

아래 그림은 노드 셋에서 과반 둘이 모이는 흐름입니다. 노드 C 는 답이 늦지만 결정은 기다리지 않고 진행됩니다.

sequenceDiagram
    participant A as 노드 A
    participant B as 노드 B
    participant C as 노드 C
    A->>B: 값 X 를 제안한다
    A->>C: 값 X 를 제안한다
    B-->>A: 받아들였다
    Note over A,B: 자기 자신과 B 로 과반 둘이 모였다
    A->>B: X 로 결정됐다
    A->>C: X 로 결정됐다
    C-->>A: 뒤늦게 받아들였다

이 그림은 뼈대만 보입니다. 두 노드가 동시에 서로 다른 값을 제안하면 뼈대만으로는 결정이 갈릴 수 있습니다. 실제 알고리즘은 이것을 막는 장치를 더 둡니다. 그 세부는 Paxos와 Raft 항목에서 봅니다.

네트워크가 갈라지면

네트워크 장애로 노드들이 서로 연락이 안 되는 두 무리로 쪼개지는 일을 분단이라고 부릅니다. 노드 다섯이 셋과 둘로 갈라졌다고 해 봅시다.

셋인 쪽은 과반을 모을 수 있으니 계속 결정합니다. 둘인 쪽은 과반을 못 모으니 결정을 멈추고 기다립니다. 두 쪽이 따로 결정하는 일은 없습니다.

flowchart TD
    subgraph 큰쪽["노드 셋 — 과반"]
        A["노드 A"] --- B["노드 B"] --- C["노드 C"]
    end
    subgraph 작은쪽["노드 둘 — 과반 아님"]
        D["노드 D"] --- E["노드 E"]
    end
    큰쪽 -. "연결 끊김" .- 작은쪽
    큰쪽 --> Y["결정을 이어 간다"]
    작은쪽 --> N["결정을 멈추고 기다린다"]

이것이 합의가 치르는 대가입니다. 적은 쪽에 붙은 클라이언트는 쓰기가 막힙니다. 모든 노드가 같은 값을 본다는 약속을 지키려고, 적은 쪽이 요청에 답하는 능력을 내준 것입니다.

늘 끝나는 방법은 없다

분산 컴퓨팅에는 FLP 불가능성이라는 잘 알려진 증명이 있습니다. FLP 는 증명을 낸 세 사람 Michael Fischer, Nancy Lynch, Michael Paterson 의 성 머리글자입니다. 증명을 읽으려면 낱말 둘을 먼저 알아야 합니다.

첫째는 비동기 네트워크입니다. 메시지가 얼마나 늦을지 한계를 모르는 네트워크입니다. 늦는 노드와 죽은 노드를 가려낼 수 없는 앞의 상황이 바로 이것입니다.

둘째는 결정적 알고리즘입니다. 같은 입력에 늘 같은 순서로 움직이고 무작위 선택을 안 쓰는 알고리즘입니다.

증명의 내용은 이렇습니다. 비동기 네트워크에서는 노드 하나만 멈출 수 있어도, 안전성과 종료(활성)를 언제나 함께 지키는 결정적 알고리즘이 없습니다. 이 증명은 「합의는 불가능하다」는 뜻이 아닙니다. 운이 나쁘면 영원히 결정을 못 내리는 경우가 반드시 남는다는 뜻입니다.

실무 알고리즘은 이 벽을 이렇게 돌아갑니다. 안전성은 어떤 경우에도 지킵니다. 종료는 네트워크가 한동안 안정될 때만 약속합니다. 안정된다는 것은 메시지가 정해진 시간 안에 도착한다는 뜻입니다.

그 시간이 타임아웃입니다. 타임아웃이 지나도 답이 없으면 노드는 상대가 멈췄다고 짐작하고 제안을 새로 시작합니다. 짐작이 틀려도 안전성은 깨지지 않고, 결정이 조금 늦어질 뿐입니다.

거짓말하는 노드

지금까지는 노드가 멈추기만 한다고 가정했습니다. 이런 고장을 멈춤 고장이라고 부릅니다. 멈춘 노드는 답을 안 할 뿐 틀린 말을 하지는 않습니다.

노드가 멈추지 않고 틀린 메시지를 보내거나 상대마다 다른 말을 하는 고장도 있습니다. 이것이 비잔틴 실패입니다.

비잔틴 실패까지 견디려면 노드가 더 많이 필요합니다. f 대가 거짓말할 수 있으면 노드가 3f+1 대 있어야 합니다. 거짓말하는 f 대가 답을 안 할 수도 있으니, 나머지 노드의 답만으로 결정해야 합니다. 그 답 안에도 거짓말하는 노드가 f 대 섞일 수 있어서, 정직한 답이 그보다 많으려면 노드가 3f+1 대 필요합니다. 서버를 한 회사가 모두 관리하는 보통의 백엔드는 멈춤 고장만 가정하는 알고리즘을 씁니다. 비잔틴 실패를 가정하는 쪽은 서로 믿지 못하는 참여자가 모이는 블록체인 같은 곳입니다.

문제를 푸는 알고리즘

합의는 문제의 이름입니다. 그 문제를 푸는 절차에는 따로 이름이 있습니다. 멈춤 고장을 견디는 대표가 Paxos와 Raft입니다. Raft 는 Paxos 와 같은 문제를 풀되 이해하기 쉽게 짜는 것을 목표로 나왔습니다.

실무에서는 값 하나만 정하고 끝나는 일이 드뭅니다. 「첫 번째 명령은 무엇인가」, 「두 번째 명령은 무엇인가」를 차례로 계속 정해야 합니다. 이렇게 정해진 명령을 순서대로 쌓은 것이 복제 로그입니다.

모든 노드가 같은 복제 로그를 같은 순서로 실행하면 모두 같은 상태에 이릅니다. 이 방식을 복제 상태 기계라고 부릅니다. 합의가 데이터베이스와 설정 저장소를 여러 대로 늘리는 바탕이 되는 까닭입니다.

합의가 쓰이는 곳

합의는 「여러 대가 절대 다른 답을 가지면 안 되는 값」에 씁니다. 대표를 한 대만 뽑는 리더 선출이 그렇습니다. 여러 서버 가운데 한 곳만 작업을 쥐게 하는 분산 락도 그렇습니다.

etcd 와 ZooKeeper 가 이 일을 맡는 대표적인 저장소입니다. 애플리케이션이 합의 알고리즘을 직접 짜는 일은 드뭅니다. 대개 이런 저장소에 값을 맡겨 합의를 빌려 씁니다.

반대로 잠깐 서로 달라도 괜찮은 데이터에는 합의를 안 씁니다. 매번 과반과 메시지를 주고받는 비용이 크기 때문입니다. 조회수나 좋아요 수 같은 값은 흔히 최종 일관성으로 처리합니다.

합의

상세

비유로 보는 합의

입력과 출력

조건을 두 무리로 가르기

어려운 까닭

과반이 열쇠인 까닭

한 번 결정되는 흐름

네트워크가 갈라지면

늘 끝나는 방법은 없다

거짓말하는 노드

문제를 푸는 알고리즘

합의가 쓰이는 곳

관련 항목

합의를 푸는 알고리즘

합의가 지키는 성질

합의가 기대는 부품과 규칙

합의 위에 얹히는 구조

합의가 견디려는 장애와 한계

합의를 채택한 저장소

합의와 헷갈리는 이웃