FLP 불가능성

FLP 불가능성은 여러 서버가 값 하나에 합의하는 일을 언제나 끝낼 수는 없다고 못 박는 증명입니다. 메시지가 언제 도착할지 모르는 네트워크에서는 서버 한 대만 멈출 수 있어도 그렇습니다. 그래서 실무의 합의 알고리즘은 틀린 답을 내지 않는 것만 늘 지킵니다. 결정을 끝내는 일은 네트워크가 잠잠해질 때로 미룹니다.

쉽고 빠른 이해

무엇을 말하나 — 여러 서버가 같은 값을 고르는 절차는 끝나지 않을 수도 있다는 증명입니다. 답이 얼마나 늦을지 모르고 서버 한 대가 멈출 수 있으면 그렇습니다. 세 서버가 다음 리더를 정한다고 해 봅시다. 한 서버의 답이 안 오면 나머지 둘은 그 서버가 멈췄는지 느린지 알 수 없습니다.

왜 알아야 하나 — 합의를 언제나 끝낼 수는 없다는 이 한계를 모르면, 어떤 상황에서도 반드시 결정하는 합의를 만들려다 헛수고를 합니다. 합의를 쓰는 저장소가 가끔 결정을 못 하고 멈추는 것도 고장이 아니라 이 한계에 부딪힌 것입니다.

어떻게 증명하나

1. 결과가 아직 안 정해진 상태에서 출발할 수 있습니다
2. 결과를 정할 메시지가 오려 하면 네트워크가 그 메시지를 조금 늦춥니다
3. 늦은 메시지는 멈춘 서버와 구별이 안 됩니다. 알고리즘은 그 메시지 없이 나아가다 다시 결과가 안 정해진 상태로 돌아옵니다. 이것이 끝없이 되풀이됩니다

무엇을 내주나 — 실무 알고리즘은 틀린 결정을 절대 안 내리는 쪽을 지킵니다. 대신 네트워크가 흔들리는 동안에는 결정이 멈출 수 있습니다.

상세

이 절은 이 증명이 무엇을 불가능하다고 말하는지, 왜 그런지, 실무 알고리즘이 이 한계를 어떻게 비켜 가는지를 다룹니다. 서버 몇 대가 값 하나를 정하는 가장 작은 상황을 가지고 봅니다.

친구 셋이 단체 대화방에서 저녁 메뉴를 정한다고 해 봅시다. 한 친구가 답이 없습니다. 휴대폰이 꺼진 것인지 바빠서 늦는 것인지는 대화방만 보고는 알 수 없습니다. 끝까지 기다리면 영영 못 정할 수 있습니다. 안 기다리고 정하면 늦게 온 답이 판을 뒤집을 수 있습니다.

FLP 는 이 증명을 낸 세 사람 Michael Fischer · Nancy Lynch · Michael Paterson 의 성 머리글자입니다. 증명이 보인 것을 한 문장으로 적으면 이렇습니다. 메시지가 늦어지는 한도가 없는 네트워크에서 서버 한 대라도 멈출 수 있으면, 합의를 언제나 끝내는 결정적 알고리즘은 없습니다. 결정적 알고리즘은 같은 상황이면 늘 같은 일을 하는 알고리즘입니다.

참여자는 서버라고 부릅니다. 분산 컴퓨팅 이론에서는 같은 것을 프로세스라고 부릅니다.

합의가 지켜야 하는 세 조건

합의는 여러 서버가 같은 값 하나를 고르는 일입니다. 고를 값은 서버들이 하나씩 내놓은 값 가운데서 나옵니다. 리더를 한 대만 뽑는 일도, 로그의 다음 칸에 들어갈 명령을 고르는 일도 합의입니다.

합의 알고리즘은 조건 셋을 지켜야 합니다. 표의 마지막 열은 그 조건 하나만 빼면 나머지 둘을 얼마나 쉽게 지킬 수 있는지 보입니다.

세 조건은 서로를 받칩니다. 하나를 빼면 나머지 둘은 아무 궁리도 없는 시시한 알고리즘으로 지켜집니다. 셋을 함께 지키려 할 때만 어려워집니다.

앞의 둘은 안전성 조건입니다. 나쁜 일이 절대 안 일어난다는 약속입니다. 그래서 어긋나면 어긋난 순간을 짚을 수 있습니다.

종료는 활성 조건입니다. 좋은 일이 언젠가는 일어난다는 약속입니다. 실행 도중에는 아직 안 일어났을 뿐인지 영영 안 일어날지 알 수 없습니다. FLP 불가능성은 이 두 종류의 약속을 언제나 함께 지킬 수는 없다고 말합니다.

증명이 세운 세 가정

불가능하다는 말은 어떤 세계에서 불가능한지를 같이 들어야 뜻이 섭니다. 증명은 가정 셋을 둡니다.

첫째는 비동기 네트워크입니다. 메시지는 결국 도착하지만 얼마나 늦을지 한도가 없는 네트워크입니다. 서버는 시간을 재서 판단하지도 못합니다. 그래서 「일정 시간 안에 답이 없으면 멈춘 것」이라고 판단할 근거가 없습니다.

둘째는 멈춤 고장입니다. 서버가 고장 나면 그냥 멈추고 다시 돌아오지 않는 고장입니다. 틀린 메시지를 보내지는 않습니다. 증명은 이런 서버가 딱 한 대만 있을 수 있다고 봅니다.

셋째는 결정적 알고리즘입니다. 같은 상태에서 같은 메시지를 받으면 늘 같은 일을 하는 알고리즘입니다. 동전을 던지듯 무작위로 고르는 단계가 없습니다.

앞의 두 가정은 알고리즘 쪽에 넉넉합니다. 메시지는 사라지지 않습니다. 고장은 한 대뿐입니다. 고장 난 서버도 거짓말을 하지 않습니다.

셋째 가정만 알고리즘을 묶는 제약입니다. 무작위로 고르는 수단을 못 쓰게 막습니다. 이렇게 넉넉한 세계에서도 안 된다는 것이 이 증명의 무게입니다.

불가능하다는 말의 범위

증명이 막는 것은 「언제나 끝난다」는 약속 하나입니다. 합의가 불가능하다는 뜻이 아닙니다. 대부분의 실행에서 합의 알고리즘은 잘 끝납니다.

증명이 보이는 것은 끝나지 않는 실행이 적어도 하나 반드시 있다는 것입니다. 증명은 네트워크가 메시지 배달 순서를 가장 나쁘게 고른다고 봅니다. 그런 순서에서 알고리즘은 틀린 답도 내지 않고 답을 내지도 않은 채 계속 돕니다.

알고리즘이 고를 수 있는 길은 둘뿐입니다. 끝내려고 멈춘 서버를 안 기다리고 결정하면, 가장 나쁜 순서에서 일치가 깨질 수 있습니다. 일치를 지키려고 기다리면, 가장 나쁜 순서에서 끝나지 않습니다. 세 조건을 모든 실행에서 함께 지키는 길은 없습니다.

한계가 생기는 원인

이 한계는 수학 증명에서 나옵니다. 기술이 좋아져도 풀리지 않습니다.

증명은 귀류법으로 갑니다. 귀류법은 반대 주장이 참이라고 놓고 모순을 끌어내는 증명 방법입니다. 이 증명은 세 조건을 다 지키는 알고리즘이 있다고 놓습니다. 그다음 그 알고리즘에서 끝나지 않는 실행을 직접 만들어 보입니다.

핵심은 느린 서버와 멈춘 서버를 가를 수 없다는 점입니다. 비동기 네트워크에는 답이 안 오는 이유를 알려 주는 신호가 없습니다. 알고리즘은 멈춘 서버를 끝없이 기다릴 수 없으니, 답이 안 온 서버를 빼고 나아가야 합니다. 증명은 이 틈을 파고듭니다.

설명을 줄이려고 가장 단순한 합의를 봅니다. 서버마다 0 이나 1 을 내놓습니다. 모두가 그 둘 가운데 하나를 고릅니다.

증명은 실행 중의 상태를 둘로 가릅니다. 앞으로 메시지가 어떤 순서로 오든 결과가 한 값으로 이미 정해진 상태가 있습니다. 이런 상태를 결과에 따라 0 으로 정해진 상태, 1 로 정해진 상태라고 부릅니다.

메시지가 오는 순서에 따라 0 으로도 1 로도 갈 수 있는 상태도 있습니다. 결과가 아직 안 정해진 이 상태를 양가 상태(bivalent)라고 부릅니다. 증명의 세 단계는 양가 상태가 끝없이 이어지는 실행을 만듭니다.

첫째, 양가 상태로 시작하는 입력이 있습니다. 서버 A · B · C 가 내놓는 값을 차례로 적으면, 000 은 셋 다 0 을 내놓은 시작입니다. 한 대씩 0 에서 1 로 바꿔 가며 시작 상태를 000 → 100 → 110 → 111 로 줄 세웁니다.

맨 앞 000 은 모두가 0 을 내놓았습니다. 타당성 조건 때문에 결과는 0 이어야 합니다. 맨 끝 111 은 같은 까닭으로 결과가 1 이어야 합니다.

이제 시작 상태가 전부 한 값으로 정해져 있다고 가정해 봅시다. 그러면 줄 어딘가에서 0 으로 정해진 시작과 1 로 정해진 시작이 이웃합니다. 100 은 0 으로, 110 은 1 로 정해졌다고 합시다. 둘은 서버 B 의 값만 다릅니다.

아래 그림은 이 가정 아래의 줄입니다. 가운데 두 칸이 이웃한 두 시작입니다.

flowchart TD
    S0["000 · 0 으로 정해진 시작"]
    subgraph N["이웃한 두 시작 · B 의 값만 다르다"]
        S1["100 · 0 으로 정해진 시작"]
        S2["110 · 1 로 정해진 시작"]
    end
    S3["111 · 1 로 정해진 시작"]
    S0 --> S1 --> S2 --> S3
    N --> X["B 가 처음부터 멈추면 A · C 에게 둘은 똑같아 보인다"]
    X --> Y["같은 값을 고른다 · 둘 중 하나는 어긋난다"]

이때 B 가 처음부터 멈췄다고 해 봅시다. 멈춘 서버가 하나 있어도 종료 조건 때문에 A 와 C 는 결정해야 합니다. 그런데 A 와 C 에게 두 시작은 똑같아 보입니다. 그래서 두 경우 모두 똑같이 움직여 같은 값을 고릅니다.

100 이라면 0 을, 110 이라면 1 을 골라야 합니다. 같은 값을 골랐으니 둘 중 하나는 어긋납니다. 처음 가정이 틀린 것입니다. 양가 상태인 시작 상태가 적어도 하나 있습니다.

둘째, 양가 상태는 양가 상태로 이어 갈 수 있습니다. 결과를 정할 메시지가 서버 A 에게 가는 중이라고 해 봅시다. 네트워크는 그 메시지를 A 앞에서 조금 붙잡아 둡니다. 비동기 네트워크라서 허용되는 일입니다.

그동안 다른 서버들은 A 가 멈췄을 수도 있다고 보고 A 없이 나아갑니다. A 를 끝까지 기다리면, A 가 정말 멈춘 경우에 끝나지 않기 때문입니다.

그 메시지를 받았는지는 A 한 대의 상태만 바꿉니다. A 없이 나아가는 다른 서버들은 두 경우를 가리지 못해 같은 값을 고릅니다. 그래서 받은 쪽은 0 으로, 안 받은 쪽은 1 로 결과가 갈라질 수는 없습니다. 붙잡아 둔 메시지를 배달한 뒤에도 양가 상태에 닿는 순서가 반드시 남습니다.

셋째, 둘째 단계를 끝없이 되풀이합니다. 되풀이할 때마다 가장 오래 기다린 메시지부터 배달합니다. 그러면 모든 메시지가 결국 도착합니다. 메시지는 하나도 안 사라지고 멈춘 서버도 없습니다. 그런데도 결정은 영영 안 나는 실행이 만들어집니다.

stateDiagram-v2
    state "양가 상태" as bi
    state "0 으로 정해진 상태" as zero
    state "1 로 정해진 상태" as one
    [*] --> bi : 양가 상태인 시작에서 출발
    bi --> bi : 결과를 정할 메시지를 늦추고 다시 양가 상태로
    bi --> zero
    bi --> one

네트워크는 이 그림에서 양가 상태로 돌아오는 화살표만 계속 고릅니다. 한 값으로 정해진 상태로 가는 두 화살표는 늘 남아 있습니다. 그래도 한 번도 고르지 않습니다.

끝나지 않는 실행에서 멈춘 서버는 한 대도 없습니다. 한 대가 멈출 수 있다는 가능성만으로 충분합니다. 그 가능성 때문에 알고리즘은 누구도 끝까지 기다려 주지 못합니다.

한계를 비켜 가는 두 방법

이 한계는 못 넘습니다. 할 수 있는 것은 세 가정 가운데 하나를 바꿔, 한계에 부딪히지 않는 세계로 옮겨 가는 것입니다. 실무에서 쓰는 방법은 둘입니다.

첫째 방법의 바탕은 부분 동기 모델입니다. 메시지 지연에 한도가 있다고 보는 모델입니다. 그 한도가 얼마인지 모르거나, 어느 시점부터만 지켜진다고 봅니다. 한도가 지켜지기 시작하는 때가 앞에서 말한 「네트워크가 잠잠해지는 때」입니다.

비동기와 동기 사이에 있어서 부분 동기라고 부릅니다. Paxos 와 Raft 가 이 방법을 씁니다. 타임아웃이 지나도 답이 없으면 상대가 멈췄다고 짐작하고 다음 단계로 넘어갑니다. 짐작이 틀려도 일치는 안 깨집니다. 결정이 늦어질 뿐입니다.

이렇게 시간을 재서 멈춘 서버를 짐작하는 부품을 따로 떼어 장애 감지기라고 부릅니다. 이 짐작은 틀릴 수 있습니다. 틀릴 수 있는 짐작을 쓰면서도 일치를 지키도록 짜는 것이 이런 알고리즘의 일입니다.

둘째 방법은 무작위 합의입니다. 이런 알고리즘은 서버들이 값을 한 번씩 주고받는 차례를 되풀이합니다. 이 한 차례를 라운드라고 부릅니다. 결과가 안 정해진 채 라운드가 끝나면, 서버마다 동전을 던져 다음 라운드에 내놓을 값을 정합니다.

네트워크는 배달 순서는 고를 수 있어도 동전의 앞뒤는 고를 수 없습니다. 동전들이 우연히 같은 쪽으로 모이는 라운드가 오면 그 라운드에서 결정이 납니다. 그런 라운드가 영영 한 번도 안 올 확률은 0 입니다. 몇 라운드가 걸릴지는 약속하지 못합니다.

두 방법을 섞기도 합니다. Raft 는 리더 선출에서 서버마다 타임아웃 길이를 무작위로 고릅니다. 여러 서버가 한꺼번에 후보로 나서 표가 갈리는 일이 끝없이 되풀이되지 않게 하려는 장치입니다.

두 방법 모두 한계를 넘은 것이 아닙니다. 네트워크가 끝내 잠잠해지지 않으면 첫째 방법은 여전히 결정을 못 내립니다. 둘째 방법은 몇 라운드가 걸릴지 여전히 모릅니다.

실무에서 이 한계가 드러나는 모습

etcd 나 ZooKeeper 처럼 합의를 쓰는 저장소는 쓰기를 리더 한 대가 받습니다. 네트워크가 흔들리는 동안에는 리더 선출이 끝나지 않고 되풀이될 수 있습니다. 새 리더가 서지 못하면 쓰기가 멈춥니다. 알고리즘이 고장 난 것이 아닙니다. 일치를 지키려고 종료를 미루는 중입니다.

그래서 합의 시스템을 굴릴 때 손대는 값이 타임아웃입니다. 너무 짧으면 느린 서버를 멈췄다고 잘못 짐작해 선출이 잦아집니다. 너무 길면 진짜로 멈춘 서버를 알아채는 데 오래 걸립니다. 어느 값을 골라도 한계는 그대로입니다. 한계에 부딪히는 빈도만 바뀝니다.

「어떤 상황에서도 반드시 결정한다」고 약속하는 합의 설계는 세 가정 가운데 하나를 바꾼 것입니다. 바꾼 가정이 안 보이면, 일치가 깨지는 실행이 그 설계 어딘가에 숨어 있습니다.

헷갈리는 이웃 불가능성

분산 시스템의 불가능성 결과는 FLP 말고도 있습니다. 셋은 무엇이 망가진다고 가정하는지와 무엇이 안 된다고 말하는지가 다릅니다.

표에서 FLP 의 가정이 가장 순합니다. 네트워크가 끊기지도 않고 메시지가 사라지지도 않습니다. 메시지가 늦을 수 있다는 것과 한 대가 멈출 수 있다는 것만으로 합의가 끝나지 않을 수 있습니다.

관련 항목

FLP 불가능성이 한계를 정하는 문제

합의 · 원자적 브로드캐스트 · 리더 선출 · 복제 상태 기계 · 분산 락

증명을 이루는 가정과 논법

비동기 네트워크 · 멈춤 고장 · 결정적 알고리즘 · 양가 상태 · 귀류법

이 증명이 함께 지킬 수 없다고 보인 성질

안전성 · 활성 · 일치 · 타당성 · 종료

이 한계를 비켜 가는 수단

부분 동기 모델 · 동기 네트워크 · 타임아웃 · 장애 감지기 · 무작위 합의 · 하트비트

우회 위에서 도는 합의 알고리즘

Paxos · Raft · Zab · Viewstamped Replication · PBFT

분산 시스템의 다른 불가능성 결과

CAP · 두 장군 문제 · 비잔틴 장군 문제 · PACELC

이 한계에 부딪히는 합의 저장소

etcd · ZooKeeper · Consul

이것이 속하는 상위 분류

분산 시스템 · 분산 컴퓨팅 이론 · 부분 실패 · 장애 허용