비잔틴 장애

비잔틴 장애는 고장 난 서버가 멈추지 않고 틀린 말을 계속하는 고장입니다. 상대마다 다른 값을 보내도 겉으로는 멀쩡해 보여서 가려내기 어렵습니다. 이 고장까지 견디려면 서버가 훨씬 많이 필요합니다. 그래서 분산 시스템은 이 고장을 가정할지부터 정합니다.

쉽고 빠른 이해

무슨 일이 벌어지나 — 고장 난 서버가 멈추는 대신 틀린 값을 보냅니다. 서버 하나가 옆 서버 둘에게 같은 주문의 금액을 한쪽에는 1만 원, 다른 쪽에는 2만 원으로 알리는 것이 그 예입니다.

왜 따로 부르나 — 멈춘 서버는 답이 없으니 빼고 가면 됩니다. 틀린 말을 하는 서버는 답을 하니 가려내기 어렵습니다. 어느 고장까지 견딜지 정해야 알고리즘을 고를 수 있어서 이름이 필요합니다.

어떻게 견디나

1. 서버들이 각자 들은 값을 서로 전해 맞춰 봅니다
2. 모인 답 가운데 정직한 답이 늘 더 많도록 서버 수를 넉넉히 잡습니다
3. 거짓말하는 서버 한 대를 견디려면 서버가 네 대 필요합니다

대가 — 서버도 메시지도 훨씬 많이 듭니다. 그래서 한 회사가 모든 서버를 관리하는 시스템은 대개 이 고장을 가정하지 않습니다. 서로 믿을 수 없는 서버가 섞이는 블록체인 같은 곳은 이 고장을 가정합니다.

상세

이 절은 비잔틴 장애가 다른 고장과 어떻게 다른지부터 봅니다. 그다음 서버 셋과 넷이 금액 하나를 주고받는 예로, 이 고장을 견디는 데 왜 서버가 더 드는지 따라갑니다. 끝으로 어떤 시스템이 이 고장까지 견디기로 하는지, 이름은 어디서 왔는지 봅니다.

팀원 다섯이 회식 날짜를 정한다고 해 봅시다. 한 사람이 메시지에 답을 안 하면 나머지 넷이 정하면 됩니다. 그런데 한 사람이 누구에게는 금요일에 된다고 합니다. 다른 누구에게는 금요일은 안 된다고 합니다. 그러면 일이 꼬입니다. 각자 들은 말이 다르니 누가 무슨 말을 들었는지부터 맞춰 봐야 합니다.

분산 시스템은 여러 서버가 네트워크로 메시지를 주고받으며 한 가지 일을 나눠 하는 시스템입니다. 이 서버 하나하나를 노드라고도 부릅니다. 이 문서는 줄곧 「서버」라고 부릅니다.

비잔틴 장애는 고장 난 서버가 아무렇게나 움직일 수 있다고 보는 고장입니다. 서버는 멈추지 않고 메시지를 계속 보냅니다. 그런데 그 내용이 틀리거나 상대마다 다릅니다.

같은 주문 금액을 저마다 한 벌씩 적어 두는 서버 셋을 생각해 봅시다. 그 가운데 하나가 다른 두 서버에 금액을 각각 1만 원과 2만 원이라고 알리면 비잔틴 장애입니다. 회식 날짜를 두고 두 말을 한 사람이 바로 이런 서버입니다.

비잔틴 고장이나 비잔틴 실패라고도 부릅니다.

고장 모델 안의 비잔틴 장애

분산 알고리즘이 옳다고 말하려면 서버가 어떻게 고장 날 수 있는지부터 정해야 합니다. 이 약속을 고장 모델이라고 부릅니다. 알고리즘은 고장 모델이 허락한 고장까지만 견딥니다. 그 밖의 고장이 나면 알고리즘이 옳다는 보장도 사라집니다.

흔히 쓰는 고장 모델 셋을 좁은 것부터 놓으면 아래 표와 같습니다. 아래로 갈수록 고장 난 서버가 할 수 있는 일이 넓어집니다.

넓은 모델은 좁은 모델을 품습니다. 멈춘 서버는 그 뒤로 모든 메시지를 빠뜨리는 서버와 같으니 누락 고장의 한 경우입니다. 비잔틴 장애는 무엇이든 할 수 있으니 앞의 둘을 다 품습니다. 아래 그림에서 바깥 상자일수록 넓은 모델입니다.

flowchart TD
    subgraph BYZ["비잔틴 장애"]
        subgraph OMI["누락 고장"]
            CRASH["멈춤 고장"]
        end
    end

비잔틴 장애를 견디는 알고리즘은 곧 가장 넓은 고장을 견딥니다. 그만큼 값도 가장 비쌉니다.

틀린 말이 생기는 원인

비잔틴 장애라고 하면 해커가 서버를 빼앗은 장면을 떠올리기 쉽습니다. 공격도 원인 하나입니다. 악의가 없어도 이 고장은 생깁니다.

셋 가운데 어느 것이든 다른 서버에게는 똑같이 보입니다. 메시지는 제때 옵니다. 형식도 맞습니다. 내용만 틀립니다.

비잔틴 장애를 견디는 알고리즘은 원인을 묻지 않습니다. 고장 난 서버가 가장 나쁘게 움직인다고 봅니다. 고장 난 서버 여럿이 짜고 움직이는 경우까지 셈에 넣습니다.

상대마다 다른 말을 하는 고장

비잔틴 장애에서 가장 까다로운 것은 한 서버가 상대마다 다른 말을 하는 경우입니다. 받은 쪽은 저마다 멀쩡한 메시지 하나를 받았을 뿐입니다. 혼자서는 이상한 점을 모릅니다.

알아채려면 서버끼리 들은 말을 서로 전해 맞춰 봐야 합니다. 아래 그림은 서버 셋 가운데 X 가 고장 난 경우입니다. 메시지에는 보낸 쪽을 증명하는 표식이 없다고 둡니다. 표식이 있으면 사정이 달라집니다. 그 이야기는 뒤의 서명 소절에서 봅니다.

sequenceDiagram
    participant X as 서버 X · 고장
    participant A as 서버 A
    participant B as 서버 B
    X->>A: 금액은 1만 원
    X->>B: 금액은 2만 원
    B->>A: X 가 나에게 2만 원이라고 했다
    Note over A: X 와 B 중 누가 거짓말인지 모른다

A 는 X 에게서 1만 원을 들었습니다. B 에게서는 「X 가 2만 원이라고 했다」를 들었습니다. X 가 두 말을 했을 수 있습니다. B 가 X 의 말을 지어냈을 수도 있습니다.

A 가 쥔 값은 1만 원과 2만 원 하나씩입니다. 다수결을 해도 1대 1로 비깁니다. A 는 어느 쪽이 거짓말인지 가릴 길이 없습니다.

서버를 하나 더해 넷으로 두면 사정이 달라집니다. 서버는 X·A·B·C 입니다. 이번에도 X 가 금액을 알리는 쪽입니다. 이번에는 X 가 고장 났다고 미리 정하지 않습니다. 넷 가운데 누구든 한 대가 거짓말을 할 수 있습니다.

A·B·C 는 저마다 값 세 개를 모읍니다. X 에게 직접 들은 값 하나와 나머지 두 서버가 전해 준 값 둘입니다. 그리고 셋 가운데 많은 쪽을 고릅니다.

먼저 B 가 거짓말하는 경우입니다. X 는 셋에게 똑같이 1만 원이라고 알립니다. B 만 A 에게 「X 가 2만 원이라고 했다」고 지어내 전합니다. 아래 그림은 이것을 A 의 눈으로 본 것입니다.

sequenceDiagram
    participant X as 서버 X
    participant A as 서버 A
    participant B as 서버 B · 고장
    participant C as 서버 C
    X->>A: 금액은 1만 원
    X->>B: 금액은 1만 원
    X->>C: 금액은 1만 원
    B->>A: X 가 나에게 2만 원이라고 했다
    C->>A: X 가 나에게 1만 원이라고 했다
    Note over A: 1만 원 둘 · 2만 원 하나 → 1만 원

A 가 모은 값은 1만 원 둘과 2만 원 하나입니다. 다수결은 1만 원입니다. X 가 알린 참말이 이깁니다. C 도 같은 셈으로 1만 원을 고릅니다.

다음은 X 가 거짓말하는 경우입니다. X 가 A 와 C 에게는 1만 원, B 에게는 2만 원이라고 알립니다. 정직한 A·B·C 는 들은 값을 손대지 않고 서로 전합니다. 세 서버가 모은 값은 아래 표와 같습니다.

세 서버 모두 1만 원 둘과 2만 원 하나를 쥡니다. 정직한 셋이 같은 묶음을 쥐니 같은 결론에 이릅니다. X 가 두 말을 해도 A·B·C 는 서로 어긋나지 않습니다.

비잔틴 장애를 견디는 데 드는 서버 수

앞 소절에서 거짓말하는 서버 하나를 견디는 데 서버 넷이 들었습니다. 그 예는 모든 서버의 말이 결국 닿는다고 두었습니다. 서버마다 말을 다 모은 뒤에 골랐습니다. 이 소절은 모든 답을 기다릴 수 없는 네트워크에서 같은 수가 다른 길로 다시 나오는 것을 봅니다.

여러 서버가 값 하나에 뜻을 모으는 일을 합의라고 부릅니다. 앞 소절의 예도 서버들이 금액 하나에 뜻을 모으려던 합의였습니다. 복제된 데이터베이스가 다음에 적을 기록 하나를 고르는 일도 합의입니다.

비동기 네트워크는 메시지가 언제 도착할지 보장하지 않는 네트워크입니다. 여기서는 답이 없는 서버가 멈췄는지 늦는 중인지 가를 수 없습니다. 그래서 어느 서버도 모든 답을 기다릴 수 없습니다. 답이 몇 개 모이면 나아가야 합니다.

서버가 모두 n 대이고 그중 f 대까지 고장 날 수 있다고 합시다. f 대는 끝내 답을 안 할 수 있습니다. 한 서버가 기다릴 수 있는 답은 n−f 개까지입니다.

그런데 모인 n−f 개의 답 안에도 거짓말하는 서버가 f 대 섞일 수 있습니다. 답을 안 한 f 대는 늦었을 뿐인 정직한 서버였을 수 있기 때문입니다. 그러면 모인 답 가운데 정직한 답은 n−2f 개뿐입니다.

서버 7대 가운데 2대까지 고장 날 수 있을 때(n=7, f=2) 한 서버가 본 모습은 아래와 같습니다. 답을 안 한 2대와 거짓말한 2대가 서로 다른 서버라는 것이 요점입니다.

block-beta
columns 1
  a["답 안 함 · 늦었을 뿐인 정직한 서버 2대 · f"]
  b["답함 · 거짓말하는 서버 2대 · f"]
  c["답함 · 정직한 서버 3대 · n−2f"]

정직한 답이 거짓 답보다 많아야 다수결이 통합니다. 그림에서는 정직한 답 3개가 거짓 답 2개보다 많습니다. 식으로 쓰면 n−2f 가 f 보다 커야 하므로 n 은 3f 보다 커야 합니다. 가장 작은 n 은 3f+1 입니다.

멈춤 고장만 견디면 되는 합의에는 2f+1 대로 충분합니다. 멈춘 서버는 답을 안 할 뿐 틀린 답을 하지 않습니다. 모인 답은 모두 믿을 수 있습니다.

남는 조건은 합의가 한 번 정한 값을 뒤에서 뒤집으면 안 된다는 것입니다. 값을 정할 때 답한 서버들과 나중에 답한 서버들이 한 대라도 겹치면, 그 서버가 앞서 정한 값을 알려 줍니다.

절반을 넘는 수를 과반이라고 부릅니다. 어느 두 과반을 골라도 적어도 한 서버가 겹칩니다. 모이는 답 n−f 개가 과반이면 되므로 n 은 2f 보다 크면 됩니다. 가장 작은 n 은 2f+1 입니다.

견딜 고장 수가 늘수록 두 모델의 차이가 벌어집니다.

늘어나는 것은 서버 수만이 아닙니다. 비잔틴 장애를 견디는 쪽은 서버끼리 들은 말을 전해 맞춰 보느라 메시지도 훨씬 많이 주고받습니다.

서명이 막는 것과 못 막는 것

디지털 서명은 메시지에 보낸 쪽만 만들 수 있는 표식을 붙이는 기술입니다. 받은 쪽은 누구나 그 표식으로 보낸 쪽을 확인할 수 있습니다. 비잔틴 장애를 견디는 알고리즘은 이것을 흔히 씁니다.

서명이 있으면 앞의 서버 셋 그림에서 B 는 X 의 말을 지어낼 수 없습니다. X 의 서명이 붙은 메시지를 손대지 않고 넘겨야 합니다. 아래 그림이 그 경우입니다.

sequenceDiagram
    participant X as 서버 X · 고장
    participant A as 서버 A
    participant B as 서버 B
    X->>A: 1만 원 · X 서명
    X->>B: 2만 원 · X 서명
    B->>A: X 서명이 붙은 2만 원을 손대지 않고 넘긴다
    Note over A: X 가 서명한 두 값이 다르다 → X 가 두 말을 했다

A 는 X 가 서명한 1만 원과 2만 원을 나란히 봅니다. X 가 두 말을 했다는 증거를 쥔 것입니다.

서명이 모든 것을 풀지는 않습니다. 고장 난 서버는 여전히 답을 안 할 수 있습니다. 서명한 틀린 값을 모두에게 똑같이 보낼 수도 있습니다.

서명이 있어도 비동기 네트워크에서는 거짓말하는 서버 f 대를 견디는 데 여전히 3f+1 대가 듭니다. 답은 이때도 n−f 개에서 끊어야 합니다. 그 안에 서명한 거짓 답이 f 개 섞일 수 있는 것도 같습니다.

비잔틴 장애를 견디기로 하는 시스템

비잔틴 장애까지 견디는 성질을 비잔틴 장애 허용이라고 부릅니다. 영어로 BFT(Byzantine Fault Tolerance)라고 줄여 씁니다. 시스템이 어느 고장까지 견디는지 말할 때 쓰는 이름입니다.

합의 알고리즘도 이 성질로 갈립니다. PBFT(Practical Byzantine Fault Tolerance, 실용적 비잔틴 장애 허용)는 비잔틴 장애까지 견디는 합의 알고리즘으로 널리 알려져 있습니다. Raft 와 Paxos 는 멈춤 고장만 견디는 합의 알고리즘입니다.

한 회사가 모든 서버를 관리하는 시스템은 대개 이 고장을 가정하지 않습니다. 서버를 모두 믿을 수 있으면 비잔틴 장애를 견디느라 드는 서버와 메시지가 낭비가 됩니다.

비잔틴 장애를 가정하는 곳은 서버끼리 서로 믿을 수 없는 시스템입니다. 누구나 서버를 띄워 참여할 수 있는 블록체인이 대표입니다. 비행기 제어 컴퓨터도 이 고장을 가정합니다. 하드웨어가 망가져 틀린 값을 낼 수 있습니다. 그 값 하나가 사고로 이어집니다.

멈춤 고장만 가정하는 시스템도 틀린 말을 아예 내버려 두지는 않습니다. 망가진 데이터처럼 흔한 경우는 값싼 장치로 걸러 냅니다.

체크섬이 그런 장치입니다. 체크섬은 데이터에서 계산한 짧은 값입니다. 데이터가 조금만 바뀌어도 이 값이 달라집니다. 받은 쪽이 다시 계산해 맞춰 보면 오는 길에 망가진 것을 알아챕니다.

이름의 유래와 두 장군 문제

이 이름은 비잔틴 장군 문제라는 사고 실험에서 왔습니다. 비잔틴 제국의 장군 여럿이 적의 도시를 둘러싸고 전령으로만 연락하며 공격할지 물러날지 정합니다. 장군 가운데 배신자가 섞여 있어 동료마다 다른 말을 전할 수 있습니다. 충성스러운 장군들이 모두 같은 결정을 내리게 하는 것이 이 문제입니다.

두 장군 문제와 헷갈리기 쉽습니다. 두 장군 문제에는 배신자가 없습니다. 전령이 도중에 잡혀 메시지가 사라지는 것이 문제입니다. 비잔틴 장군 문제는 메시지가 잘 닿는 대신 보낸 쪽이 거짓말을 합니다.

관련 항목

비잔틴 장애가 속하는 상위 분류

분산 시스템 · 고장 모델 · 시스템 모델 · 부분 실패 · 장애 허용

비잔틴 장애보다 좁은 고장 모델

멈춤 고장 · 누락 고장 · 멈춤 복구 고장 · 타이밍 고장 · 네트워크 분단 · 메시지 유실

비잔틴 장애를 일으키는 원인과 공격

비트 플립 · 데이터 손상 · 버그 · 시빌 공격 · 중간자 공격

비잔틴 장애를 견디는 합의 알고리즘

비잔틴 장애 허용 · PBFT · Tendermint · HotStuff · 작업 증명 · 지분 증명

비잔틴 장애를 빼고 멈춤 고장만 견디는 합의 알고리즘

합의 · Raft · Paxos · Viewstamped Replication · Zab · 상태 머신 복제

비잔틴 장애를 가려내고 막는 수단

디지털 서명 · 메시지 인증 코드 · 체크섬 · 정족수 · 과반 · 다수결

비잔틴 장애 이론이 기대는 가정과 사고 실험

비동기 네트워크 · 부분 동기 모델 · 동기 네트워크 · FLP 불가능성 · CAP · 비잔틴 장군 문제 · 두 장군 문제

비잔틴 장애를 가정하는 시스템

블록체인 · 비트코인 · 이더리움 · 분산 원장 · 비행 제어 컴퓨터