비동기 네트워크

비동기 네트워크는 메시지가 언제 도착할지 아무것도 보장되지 않는다고 보는 가정입니다. 분산 시스템 이론은 알고리즘이 옳은지 따질 때 이 가정을 깔고 시작합니다. 이 가정 위에서는 답이 늦는 서버와 멈춘 서버를 가려낼 수 없습니다. 코드를 비동기로 짜는 일과는 다른 이야기입니다.

쉽고 빠른 이해

무슨 일을 하나 — 분산 알고리즘을 따질 때 「네트워크는 메시지를 언제 배달할지 보장하지 않는다」고 가정하게 합니다. 서버 A 가 서버 B 에 요청을 보냅니다. 한참 동안 답이 없어도 A 는 B 가 멈췄는지 늦는 중인지 알 길이 없습니다.

왜 이렇게 가정하나 — 현실의 네트워크도 도착 시간을 보장하지 않습니다. 가장 불리한 경우를 가정하고도 옳은 알고리즘은 네트워크가 어떻게 굴든 옳습니다.

어떻게 도나

1. 보낸 메시지는 언젠가 꼭 도착합니다. 얼마나 늦을지에는 한도가 없다고 봅니다
2. 서버가 일을 처리하는 속도에도 한도가 없다고 봅니다
3. 그래서 기다린 시간만 보고 상대가 멈췄다고 단정하지 못합니다

대가 — 이 가정 위에서는 못 하는 일이 생깁니다. 서버 한 대만 멈출 수 있어도, 여러 서버가 값 하나에 뜻을 모으는 일을 언제나 끝낸다고 보장할 수 없습니다. 그래서 실무의 알고리즘은 틀린 값을 고르지 않는다는 보장만 이 가정 위에서 지킵니다. 언젠가 끝낸다는 보장은 네트워크가 언젠가는 제때 움직인다고 보는 더 너그러운 가정에 맡깁니다.

상세

이 절은 먼저 비동기 네트워크가 무엇을 가정하는지 봅니다. 그다음 그 가정 때문에 무엇을 알 수 없게 되는지, 왜 이렇게 비관적으로 가정하는지를 따라갑니다. 끝으로 이웃한 두 모델과 견주고, 이 가정 위에서 안 되는 일을 봅니다.

해외에 사는 친구에게 편지를 부쳤다고 해 봅시다. 몇 주가 지나도 답장이 없습니다. 편지가 아직 배에 실려 가는 중인지, 친구가 바빠서 답을 미루는지, 친구가 이사를 가 버렸는지 알 길이 없습니다. 우체국은 며칠 안에 닿는다고 약속해 주지 않습니다.

비동기 네트워크는 메시지가 도착하는 데 걸리는 시간에 상한을 두지 않는 가정입니다. 상한이 없다는 것은 「아무리 늦어도 이 시간 안에는 온다」고 말할 수 있는 값이 없다는 뜻입니다. 같은 데이터센터 안의 두 서버가 주고받는 요청 하나도 이 가정에서는 1초 뒤에 올 수도, 한 시간 뒤에 올 수도 있습니다.

시스템 모델이라는 가정

분산 알고리즘이 옳다고 말하려면 먼저 「어떤 세상에서 옳은가」를 정해야 합니다. 네트워크가 메시지를 잃어버리는지, 멈춘 서버가 다시 살아나는지, 시계를 믿을 수 있는지에 따라 같은 알고리즘이 옳기도 하고 틀리기도 합니다.

이런 가정의 묶음을 시스템 모델이라고 부릅니다. 알고리즘이 기댈 수 있는 것과 기댈 수 없는 것을 적어 둔 목록입니다. 알고리즘이 옳다는 증명은 이 가정 안에서만 성립합니다.

시스템 모델은 대개 시간과 고장을 따로 정합니다. 시간 쪽에서는 메시지와 처리가 얼마나 늦을 수 있는지를 정합니다. 고장 쪽에서는 서버나 네트워크가 어떤 식으로 고장 날 수 있는지를 정합니다. 비동기 네트워크는 시간 쪽에서 고르는 한 가지 답입니다.

비동기 네트워크가 두는 가정

비동기 네트워크는 시간에 관해 아무것도 보장하지 않습니다. 이것을 셋으로 나누면 아래 표와 같습니다.

셋째는 앞의 둘에서 따라 나옵니다. 상한이 없으면 시간을 재도 쓸 데가 없습니다. 「3초가 지났다」를 알아도 그 3초가 무엇을 뜻하는지 정해 줄 기준이 없기 때문입니다.

비동기 네트워크도 보장하는 것이 하나 있습니다. 보낸 메시지는 사라지지 않습니다. 늦을 뿐 언젠가는 도착합니다. 메시지가 사라지는 일은 시간 쪽이 아니라 고장 쪽에서 메시지 유실로 따로 다룹니다.

늦는 것과 멈춘 것을 못 가른다

이 가정에서 가장 큰 결과가 나옵니다. 서버 A 가 서버 B 에 요청을 보내고 답을 기다린다고 합시다. 답이 안 오는 이유는 셋 가운데 하나입니다. 요청이나 답이 아직 가는 중이거나, B 가 느리게 돌고 있거나, B 가 멈췄습니다.

A 에게는 셋이 똑같이 「아직 답이 없다」로 보입니다. 상한이 없으니 얼마를 기다려야 멈췄다고 확신할지 정할 수 없습니다.

타임아웃은 정해 둔 시간이 지나면 기다림을 끊는 장치입니다. 비동기 네트워크에서 타임아웃은 판정이 아니라 짐작입니다. 아래 그림이 그 짐작이 틀리는 경우입니다.

sequenceDiagram
    participant A as 서버 A
    participant B as 서버 B
    A->>B: 요청
    Note over B: 느리게 돌고 있다
    Note over A: 타임아웃이 지난다
    Note over A: B 가 멈췄다고 짐작한다
    B-->>A: 늦게 도착한 답
    Note over A: 짐작이 틀렸다

A 는 타임아웃이 지나자 B 가 멈췄다고 짐작하고 움직였습니다. B 는 멀쩡히 살아 있었습니다. 늦게나마 답도 보냈습니다. 비동기 네트워크 위의 알고리즘은 이런 틀린 짐작이 일어나도 망가지지 않게 짜야 합니다.

시간을 재서 상대가 멈췄는지 짐작하는 부품을 장애 감지기라고 부릅니다. 멈춘 서버를 빼고 일을 이어 가려면 이런 부품이 있어야 합니다. 그런데 비동기 네트워크에서는 한 번도 틀리지 않는 장애 감지기를 만들 수 없습니다.

틀리지 않는 감지기는 두 가지를 함께 지켜야 합니다. 멈춘 서버는 늘 멈췄다고 판정합니다. 산 서버는 한 번도 멈췄다고 판정하지 않습니다.

둘을 함께 지키려면 늦는 것과 멈춘 것을 가를 수 있어야 합니다. 비동기 네트워크에서는 그 둘을 가를 수 없습니다.

왜 이렇게 비관적으로 가정하나

현실의 네트워크도 도착 시간을 보장하지 않습니다. 스위치에 패킷이 몰리면 큐에 줄을 서서 기다립니다. 줄이 넘쳐 패킷이 버려지면 TCP(Transmission Control Protocol, 전송 제어 프로토콜)가 알아채고 다시 보냅니다. 그동안 메시지는 늦어집니다.

서버 쪽도 마찬가지입니다. 가비지 컬렉션은 쓰지 않는 메모리를 치우는 일입니다. 이 일이 프로그램을 잠시 멈춰 세우기도 합니다. 그동안 그 서버는 멀쩡하지만 아무 답도 못 합니다.

가상 머신도 서버를 멈춰 세웁니다. 가상 머신은 소프트웨어로 만든 컴퓨터입니다. 물리 서버 한 대를 여러 대처럼 나눠 쓰게 해 줍니다. 가상 머신을 돌리는 물리 서버(호스트)가 가상 머신 하나를 잠시 멈췄다가 다시 돌리면, 그 안의 프로그램은 자기가 멈췄던 줄도 모릅니다.

이런 지연은 대개 짧습니다. 하지만 얼마나 길어질지 한도를 댈 수는 없습니다. 「지연은 보통 짧다」에 기대 짠 알고리즘은 드물게 오는 긴 지연에서 틀린 결과를 낼 수 있습니다.

비동기 네트워크를 가정하고 옳다고 증명한 알고리즘은 이런 걱정이 없습니다. 지연이 어떻게 나타나든 증명이 무너지지 않습니다. 가장 불리한 경우를 가정하는 대가로 가장 넓은 경우에 통하는 보장을 얻습니다.

동기 · 부분 동기 모델과 견주기

시간 쪽의 가정에는 비동기 네트워크 말고도 흔히 쓰는 것이 둘 더 있습니다. 셋을 가르는 것은 지연에 상한이 있는지, 그리고 그 값을 알고리즘이 아는지입니다.

동기 네트워크는 알고리즘을 짜기 가장 쉽습니다. 모두가 같은 박자에 맞춰 메시지를 주고받는다고 가정할 수 있습니다. 대신 현실의 네트워크가 그 상한을 한 번이라도 어기면 증명이 무너집니다.

부분 동기 모델은 그 사이에 놓입니다. 네트워크가 한동안 제멋대로 늦다가도, 언젠가는 상한을 지키는 때가 온다고 봅니다. 그 때가 언제인지는 알고리즘이 모릅니다.

합의는 여러 서버가 값 하나에 뜻을 모으는 일입니다. 복제된 서버들이 다음에 적을 기록 하나를 똑같이 고르는 것이 그 예입니다. 합의 알고리즘은 이 일을 해 주는 알고리즘입니다.

Paxos 와 Raft 같은 실무의 합의 알고리즘은 두 성질을 서로 다른 가정 위에서 지킵니다. 첫째 성질은 안전성입니다. 틀린 값을 고르지 않는다는 성질입니다. 이 성질은 비동기 네트워크에서도 지킵니다.

둘째 성질은 활성입니다. 결정을 언젠가 끝낸다는 성질입니다. 이 성질은 부분 동기 모델에서만 지킵니다. 네트워크가 한동안 제때 메시지를 나르면 그때 결정이 끝납니다.

이 가정 위에서 안 되는 일

합의는 「동기 · 부분 동기 모델과 견주기」 소절에서 본 대로 여러 서버가 값 하나에 뜻을 모으는 일입니다. 비동기 네트워크는 이 일에 넘을 수 없는 한계를 긋습니다. 이 소절은 그 한계를 밝힌 증명 하나를 봅니다.

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

FLP 불가능성은 비동기 네트워크에서 합의를 언제나 끝내는 결정적 알고리즘이 없다는 증명입니다. FLP 는 증명을 낸 세 연구자 Michael Fischer · Nancy Lynch · Michael Paterson 의 성에서 딴 머리글자입니다. 서버가 딱 한 대만 멈출 수 있어도 이 결과는 성립합니다.

뿌리는 「늦는 것과 멈춘 것을 못 가른다」 소절에서 본 문제입니다. 알고리즘은 멈춘 서버를 끝없이 기다릴 수 없습니다. 그렇다고 답이 없는 서버를 빼고 나아가면, 그 서버가 느렸을 뿐일 때 판단이 어긋날 수 있습니다.

이 증명은 네트워크가 메시지의 도착 순서를 마음대로 정한다고 가정합니다. 그 순서를 알고리즘에 가장 불리하게 짜면, 결정이 영영 미뤄지는 경우가 반드시 생깁니다.

이 결과는 합의가 불가능하다는 뜻이 아닙니다. 대부분의 경우 합의는 잘 끝납니다. 「언제나 끝난다」는 보장 하나를 비동기 네트워크에서는 줄 수 없다는 뜻입니다.

비동기 호출과 다른 말

「비동기」라는 낱말은 코드에서도 흔히 씁니다. 비동기 호출은 일을 맡겨 두고 끝나기를 기다리지 않은 채 다음 일로 넘어가는 호출입니다. 비동기 네트워크는 이것과 관계가 없습니다.

동기 호출로만 짠 서버들도 도착 시간을 보장하지 않는 네트워크로 이어져 있으면 비동기 네트워크 위에 있습니다. 반대로 코드를 전부 비동기로 짜도 네트워크에 지연 상한이 생기지는 않습니다. 두 말이 함께 가진 것은 「상대의 시간에 맞추지 않는다」는 뿌리뿐입니다.

관련 항목

비동기 네트워크가 속하는 상위 분류

분산 시스템 · 분산 알고리즘 · 분산 컴퓨팅 · 시스템 모델

비동기 네트워크와 같은 축에서 맞세워지는 모델

동기 네트워크 · 부분 동기 모델 · 라운드 기반 모델 · 전역 시계

비동기 네트워크와 함께 가정하는 고장

멈춤 고장 · 비잔틴 장애 · 부분 실패 · 네트워크 분단 · 메시지 유실

비동기 네트워크를 현실에서 만드는 지연 원인

큐잉 지연 · 패킷 손실 · 재전송 · TCP · 가비지 컬렉션 · 가상 머신 · 꼬리 지연

비동기 네트워크에서 고장을 짐작하는 수단

타임아웃 · 장애 감지기 · 하트비트 · 리스 · 지수 백오프

비동기 네트워크가 긋는 불가능성 결과

FLP 불가능성 · 결정적 알고리즘 · CAP · 두 장군 문제 · 양가 상태

비동기 네트워크 위에서 합의를 푸는 알고리즘

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

비동기 네트워크 위의 알고리즘이 지키는 성질

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

비동기 네트워크와 이름이 겹치는 이웃

비동기 · 비동기 호출 · 비동기 프로그래밍 · 비동기 입출력 · 비동기 복제