Paxos

여러 대의 컴퓨터가 값 하나에 합의하기 위한 규칙입니다. 한쪽이 값을 제안하면 나머지가 받아들일지 답합니다. 과반이 받아들인 값 하나만 선택됩니다. 몇 대가 멈추거나 메시지가 사라져도 이미 선택된 값은 뒤집히지 않습니다.

상세

Paxos 가 푸는 문제는 합의입니다. Leslie Lamport 는 「Paxos Made Simple」에서 값을 제안할 수 있는 프로세스들의 모임을 가정하고 시작합니다. 합의 알고리즘은 제안된 값들 가운데 단 하나가 선택되도록 보장합니다. 아무 값도 제안되지 않으면 아무 값도 선택되지 않아야 합니다. 값이 선택됐다면 프로세스들이 그 선택된 값을 학습할 수 있어야 합니다. 그 값이 실제로 무엇인지는 시스템마다 다릅니다 — 뒤에서 볼 Chubby 셀은 마스터가 살아 있음을 알리는 heartbeat 값을, 복제 로그를 쓰는 시스템은 로그에 다음으로 적을 항목을 이 값으로 씁니다.

같은 글이 적은 안전성 요구사항은 셋입니다.

• 제안된 적이 있는 값만 선택될 수 있습니다.
• 단 하나의 값만 선택됩니다.
• 어떤 프로세스도 실제로 선택되지 않은 값을 선택됐다고 학습하는 일은 없습니다.

진행성 요구사항은 정밀하게 명세하지 않겠다고 Lamport 는 못 박습니다. 다만 목표는 제안된 어떤 값이 결국 선택되는 것, 그리고 값이 선택됐다면 프로세스가 결국 그 값을 학습할 수 있는 것이라고 적혀 있습니다.

세 역할

합의에 참여하는 주체를 명세는 에이전트라고 부릅니다. 에이전트는 합의에서 한 가지 역할을 맡는 참여자를 가리키는 이름입니다. 역할은 셋으로 갈립니다.

구현에서는 프로세스 하나가 둘 이상의 에이전트 노릇을 겸할 수 있습니다. 에이전트를 프로세스에 어떻게 대응시키는지는 명세의 관심사가 아니라고 Lamport 는 적습니다.

과반이라는 장치

값을 고르는 가장 쉬운 방법은 수락자를 하나만 두는 것입니다. 제안자가 그 수락자에게 제안을 보냅니다. 수락자는 자기가 받은 첫 제안 값을 고릅니다. 단순하지만 그 수락자가 실패하면 더는 진행할 수 없습니다.

그래서 수락자를 여럿 둡니다. 제안자가 수락자 집합에 값을 보냅니다. 수락자는 그 값을 수락할 수 있습니다. 충분히 큰 수락자 집합이 값을 수락하면 그 값이 선택됩니다. 충분히 크다는 것은 과반입니다. 어떤 두 과반도 적어도 한 수락자를 공유하기 때문입니다. 수락자가 최대 하나의 값만 수락할 수 있다면 이 방식이 성립한다고 Lamport 는 적습니다.

분산 합의에서 결정을 내리는 데 필요한 참여자의 최소 수를 정족수라고 부릅니다. Paxos 의 정족수는 과반입니다. 이 문서가 과반이라고 적은 자리는 전부 정족수를 말합니다.

제안 번호를 붙이는 이유

앞 절의 마지막 문장에는 조건이 하나 달려 있습니다. 수락자가 값을 최대 하나만 수락할 때 성립한다는 조건입니다. 그 조건은 곧 풀립니다. 어떻게 풀리는지가 제안 번호가 태어나는 자리입니다.

실패도 메시지 유실도 없다면, 제안자 하나가 값 하나만 제안했을 때 그 값이 선택되기를 바라게 됩니다. 여기서 첫 요구가 나옵니다. 수락자는 자기가 받은 첫 제안을 반드시 수락해야 한다는 것입니다. Lamport 는 이 요구에 P1 이라는 이름을 붙입니다.

그런데 P1 만 두면 문제가 생깁니다. 서로 다른 제안자가 비슷한 시각에 여러 값을 제안하면, 모든 수락자가 값을 수락했는데도 어느 한 값도 과반의 수락을 못 받는 상황이 생길 수 있습니다. 제안된 값이 둘뿐이어도 그렇습니다. 각각이 수락자의 절반쯤에게 수락되면, 수락자 하나가 실패하는 것만으로 둘 중 어느 값이 선택됐는지 알아낼 수 없게 될 수 있습니다.

P1, 그리고 과반이 수락해야 값이 선택된다는 요구. 이 둘을 함께 두면 하나가 따라 나옵니다. 수락자는 제안을 둘 이상 수락할 수 있어야 한다는 것입니다. 앞 절이 달아 두었던 조건이 여기서 풀립니다.

수락자가 여러 제안을 수락한다면 그 제안들을 서로 구별해야 합니다. 그래서 제안마다 자연수를 하나씩 붙입니다. 그 수가 제안 번호입니다. 이제 제안은 제안 번호와 값의 쌍입니다. 서로 다른 제안은 서로 다른 번호를 갖도록 요구합니다. 그것을 어떻게 달성할지는 구현에 달렸다고 적고 Lamport 는 일단 그렇다고 가정하고 넘어갑니다.

번호가 생기면서 「값이 선택됐다」의 뜻도 정확해집니다. 어떤 값을 가진 단 하나의 제안이 수락자 과반에게 수락되면 그 값이 선택된 것입니다. 그때 그 제안도 선택됐다고 말합니다.

제안은 여럿 선택되어도 됩니다. 대신 선택된 제안들이 전부 같은 값을 갖는다는 것을 보장해야 합니다. 다음 절의 조건들이 그 보장을 만들어 갑니다.

제안 번호는 자연수입니다. 어느 두 번호를 집어도 어느 쪽이 큰지 반드시 정해집니다. 이렇게 모든 두 원소 사이의 앞뒤가 빠짐없이 정해지는 순서를 전순서라고 부릅니다.

조건을 좁혀 가는 과정

이 절이 하려는 말은 하나입니다. P1 이 만든 문제에서 출발해 조건을 P2·P2a·P2b·P2c 로 한 단계씩 좁혀 가면, 마지막 조건인 P2c 하나만 지켜도 P2b·P2a·P2 가 저절로 지켜진다는 것입니다. P1 자체는 뒤(교환 순서)에서 더 강한 조건 P1a 로 대체됩니다 — P1a 가 P1 을 포섭합니다. Paxos 의 본문은 이렇게 요구사항을 하나씩 강화해 가며 얻어집니다. 조건에는 이름이 붙어 있습니다. 표의 「발의하다」는 앞서 쓴 「제안하다」와 같은 동작을 가리키는 다른 말입니다.

번호가 전순서를 이루기 때문에, P2 는 단 하나의 값만 선택된다는 결정적 안전성을 보장합니다. 선택되려면 적어도 한 수락자가 수락해야 하므로 P2a 를 만족시키면 P2 도 만족합니다.

그런데 통신이 비동기(메시지가 지연되거나 순서가 뒤바뀌거나 유실될 수 있고, 도착 시점을 보장할 수 없는 통신 방식)라, 어떤 수락자 c 가 아무 제안도 받지 못한 채로 값이 선택될 수 있습니다. 이때 새 제안자가 깨어나 다른 값으로 더 높은 번호의 제안을 내면 P1 이 c 에게 그 제안을 수락하라고 요구합니다. 그것이 P2a 를 어깁니다. P1 과 P2a 를 함께 유지하려면 P2a 를 P2b 로 강화해야 합니다. 제안은 수락되기 전에 제안자가 먼저 발의해야 하므로 P2b 는 P2a 를, P2a 는 다시 P2 를 함의합니다.

P2b 를 어떻게 만족시킬지는 그것을 증명하는 방법에서 나옵니다. 번호 m 과 값 v 인 제안이 선택됐다고 두고, m 보다 큰 번호 n 으로 발의되는 어떤 제안도 값 v 를 갖는다는 것을 보이면 됩니다. 증명은 n 에 대한 귀납(작은 값에서 성립함을 보이고, 그것을 딛고 한 단계 큰 값에서도 성립함을 보여 모든 값에 대해 성립시키는 증명 방식)으로 합니다. m 부터 n − 1 까지의 번호로 발의된 제안이 전부 값 v 를 갖는다는 가정을 하나 더 얹는 것입니다.

번호 m 인 제안이 선택됐다는 것은, 그 제안을 전부 수락한 수락자 과반 집합이 하나 있다는 뜻입니다. 그 집합을 C 라고 부릅니다. 귀납 가정과 합치면 두 가지가 따라 나옵니다. C 의 모든 수락자는 각자 m 부터 n − 1 사이의 번호를 가진 제안을 적어도 하나는 수락했습니다. 그리고 그 범위(m 부터 n − 1) 안의 번호를 가진 제안이라면, 어떤 수락자가 수락한 것이든 전부 값 v 를 갖습니다(귀납 가정).

P2c. 어떤 v 와 n 에 대해, 값 v 와 번호 n 인 제안이 발의된다면 수락자 과반으로 이루어진 집합 S 가 존재합니다. 그 S 는 아래 둘 가운데 하나를 만족합니다.

(a) S 의 어떤 수락자도 n 보다 작은 번호의 제안을 수락한 적이 없다. (b) S 의 수락자들이 수락한 n 보다 작은 번호의 제안들 가운데, 번호가 가장 높은 제안의 값이 v 다.

이 불변식(한 번 성립하면 이후에도 계속 성립하도록 지켜야 하는 조건, 이름은 P2c)을 유지하면, 번호 n·값 v 인 제안이 발의될 때 위 (a) 또는 (b) 를 만족하는 수락자 과반 집합이 존재한다고 보장됩니다. 그런 집합을 아무거나 하나 잡아 S 라고 부르고, 그 S 가 실제로 값 v 를 가리키는지 봅니다. 두 과반은 반드시 겹치므로 S 는 C 의 원소를 적어도 하나 가집니다. 그 공유된 수락자는 이미 m 부터 n − 1 사이의 제안을 수락한 적이 있으므로, S 는 (a)(S 의 어떤 수락자도 n 보다 작은 번호의 제안을 수락한 적이 없다)를 만족할 수 없습니다. 그러니 (b)가 성립합니다 — S 안에서 수락된 것 가운데 번호가 가장 높은 제안이 있고, 그 제안의 값은 귀납 가정에 따라 v 입니다. 그래서 번호 n 인 제안이 값 v 를 갖는다고 결론지을 수 있습니다.

S 는 제안자가 미리 지정하는 집합이 아닙니다. 그런 과반 집합이 하나라도 있으면 조건이 성립한다는 뜻입니다. 실제로 제안자가 그런 집합을 손에 넣는 방법이 다음 절의 Phase 1 입니다. P2c 의 불변식을 유지하면 P2b 를 만족시킬 수 있습니다.

교환 순서

값 하나를 정하는 데 두 국면(Phase)이 돕니다. 국면마다 제안자가 수락자 과반에게 요청을 보냅니다. 아래 그림은 수락자가 셋인 경우입니다. 셋 가운데 둘이 과반입니다.

sequenceDiagram
    participant P as 제안자
    participant A as 수락자 A
    participant B as 수락자 B
    participant C as 수락자 C
    P->>A: prepare 요청 · 번호 n
    P->>B: prepare 요청 · 번호 n
    P->>C: prepare 요청 · 번호 n
    A-->>P: 약속 + 수락한 제안 중 번호가 가장 높은 것 (있으면)
    B-->>P: 약속 + 수락한 제안 중 번호가 가장 높은 것 (있으면)
    Note over P,C: 셋 중 둘이 응답했다. 과반이다
    P->>A: accept 요청 · 번호 n · 값 v
    P->>B: accept 요청 · 번호 n · 값 v
    A-->>P: 수락
    B-->>P: 수락
    Note over P,C: 과반이 수락했다. 값 v 가 선택됐다

Phase 1

제안자는 새 제안 번호 n 을 고르고, 어떤 수락자 집합의 과반에게 prepare 요청을 보냅니다. 이 요청은 두 가지를 답해 달라는 요청입니다. 하나는 n 보다 작은 번호의 제안은 다시는 수락하지 않겠다는 약속입니다. 다른 하나는 그 수락자가 지금까지 수락한 제안 가운데 n 보다 작은 번호를 가진 가장 높은 번호의 제안입니다. 그런 제안이 있으면 그렇게 답하고, 없으면 없다고 답합니다.

수락자 쪽 규칙은 이렇습니다. 자기가 이미 응답한 어떤 prepare 요청보다도 큰 번호 n 의 prepare 요청을 받으면, 그 요청에 위의 약속과 자기가 수락한 제안 중 번호가 가장 높은 것을 실어 응답합니다. 수락한 제안이 있으면 그것을 싣습니다.

Phase 1 이 있는 이유는 P2c 에 있습니다. 번호 n 의 제안을 내려는 제안자는 과반의 수락자 각각이 n 보다 작은 번호 가운데 이미 수락했거나 앞으로 수락할 제안 중 번호가 가장 높은 것을 알아야 합니다. 이미 수락한 것을 아는 일은 쉽지만 미래의 수락을 예측하는 일은 어렵습니다. 그래서 제안자는 예측하는 대신 그런 수락이 없을 것이라는 약속을 받아 내어 미래를 통제한다고 Lamport 는 적습니다.

Phase 2

제안자가 번호 n 의 prepare 요청에 대한 응답을 과반의 수락자로부터 받으면, 번호 n 과 값 v 로 제안을 낼 수 있습니다. v 는 응답들 가운데 가장 높은 번호를 가진 제안의 값입니다. 응답들이 아무 제안도 보고하지 않았다면 v 는 제안자가 고른 아무 값이나 될 수 있습니다. 제안자는 응답을 준 그 수락자들 각각에게 accept 요청을 보냅니다.

Lamport 는 이 자리를 같은 글에서 두 번 적습니다. 알고리즘을 이끌어 내는 대목에서는 제안자가 어떤 수락자 집합에 accept 요청을 보낸다고만 적습니다. 그 집합이 처음 prepare 요청에 응답한 집합과 같을 필요는 없다고 덧붙입니다. 두 국면으로 정리해 적은 대목에서는 응답을 준 그 수락자들 각각에게 보낸다고 적습니다. 알고리즘의 정의로 읽을 것은 뒤쪽입니다.

수락자는 번호 n 의 accept 요청을 받으면 그 제안을 수락합니다. 다만 n 보다 큰 번호의 prepare 요청에 이미 응답했다면 수락하지 않습니다. 이 규칙에는 P1a 라는 이름이 붙어 있습니다. 수락자는 n 보다 큰 번호의 prepare 요청에 응답한 적이 없을 때만 번호 n 의 제안을 수락할 수 있다는 것입니다. P1a 가 P1 을 포섭한다고 Lamport 는 적습니다.

수락자는 어떤 요청이든 안전성을 해치지 않고 무시할 수 있습니다. 그래서 명세가 정하는 것은 언제 응답해도 되는지뿐입니다. prepare 요청에는 언제나 응답할 수 있습니다. accept 요청에는 응답하지 않겠다고 약속하지 않은 경우에만 응답할 수 있습니다.

제안자는 각 제안마다 알고리즘을 따르기만 하면 제안을 여러 개 낼 수 있습니다. 프로토콜 도중 아무 때나 제안을 버릴 수도 있습니다. 버려진 제안의 요청이나 응답이 한참 뒤에 목적지에 도착하더라도 정확성은 유지됩니다.

선택된 값을 학습하기

학습자가 값이 선택됐음을 알려면 어떤 제안이 수락자 과반에게 수락됐다는 사실을 알아내야 합니다. 방법이 두 갈래입니다. 오가는 메시지가 서로 다릅니다.

뻔한 방법은 수락자가 제안을 수락할 때마다 모든 학습자에게 그 제안을 보내는 것입니다. 학습자가 선택된 값을 가능한 한 이른 시점에 알 수 있습니다. 대신 응답 수가 수락자 수와 학습자 수의 곱이 됩니다. 아래 그림은 수락자 셋 · 학습자 둘인 경우입니다.

sequenceDiagram
    participant A as 수락자 A
    participant B as 수락자 B
    participant C as 수락자 C
    participant L1 as 학습자 1
    participant L2 as 학습자 2
    A->>L1: 수락한 제안
    A->>L2: 수락한 제안
    B->>L1: 수락한 제안
    B->>L2: 수락한 제안
    C->>L1: 수락한 제안
    C->>L2: 수락한 제안
    Note over A,L2: 응답 수 = 수락자 수 × 학습자 수 = 3 × 2 = 6

다른 갈래는 지정된 학습자를 하나 두는 것입니다. 여기서 비잔틴 실패라는 낱말이 나옵니다. 노드가 멈추는 대신 규칙을 어긴 메시지, 곧 거짓이거나 변조된 메시지를 보내는 실패를 그렇게 부릅니다. 비잔틴 실패가 없다는 가정 덕분에 한 학습자가 다른 학습자에게서 값이 수락됐다는 사실을 알아내기가 쉽습니다. 수락자들이 지정된 학습자 하나에게만 수락을 응답하고, 그 학습자가 값이 선택됐을 때 나머지 학습자에게 알리는 방식을 쓸 수 있습니다. 아래 그림도 같은 수락자 셋 · 학습자 둘로 그립니다.

sequenceDiagram
    participant A as 수락자 A
    participant B as 수락자 B
    participant C as 수락자 C
    participant D as 지정된 학습자
    participant L as 학습자 2
    A->>D: 수락한 제안
    B->>D: 수락한 제안
    C->>D: 수락한 제안
    D->>L: 값이 선택됐다는 통지
    Note over A,L: 응답 수 = 수락자 수 + 학습자 수 = 3 + 2 = 5 · 왕복이 한 번 더 든다

이 방식은 모든 학습자가 선택된 값을 알아내는 데 왕복이 한 번 더 듭니다. 지정된 학습자가 실패할 수 있으므로 신뢰성도 덜합니다. 대신 응답 수가 수락자 수와 학습자 수의 곱이 아니라 합이 됩니다.

예시

아래 두 시스템의 문서는 앞 절과 다른 낱말을 씁니다. 하는 일로 맞춰 보면 이렇습니다. 복제본은 같은 코드를 돌리는 서버 한 대입니다. accept 메시지를 받아들이거나 거절하는 쪽이니 앞 절의 수락자 자리입니다. 조정자는 그 복제본 가운데 값을 골라 뿌리는 자리를 맡은 하나입니다. 앞 절의 제안자 자리입니다. 값이 정해졌다는 통지는 마지막 commit 메시지가 나릅니다. 앞 절에서 학습자에게 알리던 자리입니다. 메시지 이름도 이렇게 맞춰집니다 — propose 는 앞 절의 prepare 요청과 같은 자리이고, promise 는 그 요청에 대한 약속 응답과 같은 자리입니다. accept 는 이름이 그대로이고, acknowledgment 는 그 accept 에 대한 수락 응답과 같은 자리입니다.

Chubby 셀의 왕복 한 번

Paxos 알고리즘이 값 하나를 정하려고 한 번 도는 것을 인스턴스라고 부릅니다. 그 인스턴스 하나에서 다섯 개의 메시지가 돕니다. 엔지니어링 보고서 「Paxos Made Live」가 이름과 각 메시지가 싣는 것을 그대로 적어 둡니다.

Chubby 는 Google 의 잠금 서비스입니다. 복제로 결함 내성을 얻습니다. 전형적인 셀은 같은 코드를 돌리는 복제본 다섯 개로 이루어집니다. 분산 합의 알고리즘이 정족수로 결정을 내리기 때문에 가용성을 높이려면 복제본이 여럿 필요합니다. 셀 하나가 살아 있으려면 다섯 복제본 가운데 셋이 돌고 있어야 합니다. 그 셋이 아래 표에 나오는 과반입니다.

propose 와 promise 의 교환은 앞 절 Phase 1 의 요청·응답과 같은 자리이지만, 여기서는 그 결과로 한 복제본을 조정자로 세우는 데까지 씁니다 — 과반이 답하면서 더 높은 번호를 본 적이 없다고 알리면 그 복제본이 조정자 노릇을 합니다. promise 가 값을 함께 실어 오는 이유는 이미 합의된 값을 새 조정자가 뒤집지 못하게 하기 위해서입니다. 새 조정자는 받아 온 값 가운데 가장 최근 조정자의 것을 고릅니다. 아무 promise 도 값을 싣고 있지 않으면 제출된 값 가운데 아무거나 고를 수 있습니다.

번호 s 는 아무렇게나 고르지 않습니다. 복제본마다 쓸 수 있는 번호가 갈라져 있습니다.

s mod n = ir

n 은 복제본 수이고 ir 은 복제본 r 에게 준 고유 id 로 0 이상 n 미만의 값입니다. 복제본 r 은 자기가 본 어떤 번호보다 큰 번호 가운데 이 식을 만족하는 가장 작은 s 를 고릅니다. 복제본 다섯 개짜리 Chubby 셀이면 n 이 5 입니다. 복제본마다 나머지가 다르므로 번호가 겹치지 않습니다.

accept 가 나르는 값 v 에도 실물이 있습니다. 마스터는 오랜 기간 조정자 자리를 지키는 복제본을 가리키는 이름입니다. 그 마스터가 자기 리스를 갱신하려고 더미 "heartbeat" 값을 주기적으로 Paxos 에 제출합니다. 리스는 그동안 무엇을 하지 않겠다고 정해 둔 기간입니다. Chubby 의 마스터 리스는 복제본 과반이 몇 초 동안 다른 마스터를 뽑지 않겠다고 한 약속입니다. 마스터가 계속 과반의 표를 얻는 한 복제본들이 주기적으로 갱신해 줍니다. 그 제출 하나가 인스턴스 하나이고, 그 인스턴스의 accept 메시지가 나르는 v 가 그 더미 값입니다.

다섯 메시지에는 디스크 쓰기가 딸려 있습니다. 지금까지 서술한 그대로의 Paxos 는 메시지를 보내는 쪽이 보내기 전에 자기 상태를 기록하도록 요구합니다. 그래서 디스크 쓰기 다섯 번이 한 줄로 늘어섭니다. 앞의 쓰기가 디스크로 내려간 뒤에야 다음으로 넘어갈 수 있습니다. 이렇게 전체가 끝나는 시각을 결정하는 단계들의 사슬을 임계 경로라고 부릅니다. 사슬 위의 한 단계가 늦어지면 전체가 그만큼 늦어집니다. 복제본들이 통신망에서 가까이 있는 시스템이라면 디스크로 내려보내는 시간이 구현 전체의 지연을 지배할 수 있습니다.

Multi-Paxos

실제 시스템은 Paxos 를 값 하나가 아니라 값의 열에 합의하기 위한 구성 요소로 씁니다. 여러 서버가 같은 순서로 값을 이어 적어 나가는 기록인 복제 로그가 그런 자리입니다. 단순하게 구현하려면 Paxos 알고리즘을 인스턴스마다 되풀이해 실행하면 됩니다.

여러 Paxos 인스턴스를 사슬로 엮어 메시지 수를 줄이는 최적화가 알려져 있습니다. 인스턴스 사이에 조정자의 정체가 바뀌지 않으면 propose 메시지를 생략할 수 있습니다. 이 최적화를 쓰려고 Multi-Paxos 알고리즘은 조정자를 오랜 기간 하나로 잡고 바뀌지 않게 하도록 설계될 수 있습니다. 그 조정자를 마스터라고 부릅니다. 이 최적화까지 붙으면 Paxos 알고리즘은 복제본마다 인스턴스당 디스크 쓰기 한 번만 요구합니다. 그 쓰기들은 서로 병렬로 실행됩니다. 마스터는 자기 accept 메시지를 보낸 직후에 씁니다. 다른 복제본들은 자기 acknowledgment 메시지를 보내기 전에 씁니다. 부하가 걸린 시스템에서 전체 Paxos 알고리즘을 도는 인스턴스는 1퍼센트 미만입니다.

sequenceDiagram
    participant M as 마스터
    participant R as 나머지 복제본들
    Note over M,R: 조정자가 그대로다 — propose 생략
    M->>R: accept · 값 v
    Note over M: 보내자마자 디스크에 쓴다
    R-->>M: acknowledgment
    Note over R: 보내기 전에 디스크에 쓴다
    M->>R: commit

그래서 위의 다섯 메시지가 처음부터 다 도는 때는 조정자가 바뀔 때입니다. 마스터가 실패하면 새 마스터를 뽑는 리더 선출이 자동으로 일어납니다. 그 복제본이 자기 번호로 propose 를 뿌리는 데서 왕복이 다시 시작합니다 — Chubby 예시에서 본 다섯 메시지 표 그대로입니다.

Spanner

Spanner 는 Google 의 전역 분산 데이터베이스입니다. 상태 기계는 같은 명령을 같은 순서로 적용하면 언제나 같은 상태에 이르는 프로그램을 말합니다. Paxos 상태 기계가 자기 메타데이터와 로그를 자기 태블릿(테이블을 행 구간으로 쪼갠 한 조각)에 저장합니다. spanserver 는 그 태블릿들을 맡는 서버입니다.

복제를 위해 각 spanserver 는 태블릿마다 그 위에 Paxos 상태 기계 하나를 구현합니다. 태블릿마다 Paxos 상태 기계를 여럿 두던 초기 판도 있었습니다. 그 설계의 복잡도 때문에 포기했다고 논문은 적습니다.

로그를 두 번 적는 것은 편의를 위해 내린 선택이고 언젠가 고칠 가능성이 크다고 논문은 덧붙입니다.

실패

Paxos 가 깨지는 자리는 안전성이 아니라 진행성입니다. 제안자 둘이 번갈아 번호를 올리면 아무 값도 선택되지 않는 상황을 쉽게 구성할 수 있다고 Lamport 는 적습니다.

제안자 p 가 번호 n1 으로 Phase 1 을 끝냅니다. 그다음 제안자 q 가 n1 보다 큰 번호 n2 로 Phase 1 을 끝냅니다. 수락자들이 n2 보다 작은 번호의 새 제안은 수락하지 않겠다고 약속했으므로 p 의 번호 n1 짜리 accept 요청은 전부 무시됩니다. 그래서 p 는 n2 보다 큰 새 번호 n3 로 Phase 1 을 다시 시작해 끝냅니다. 이번에는 q 의 두 번째 accept 요청이 무시됩니다. 이것이 끝없이 이어집니다.

sequenceDiagram
    participant p as 제안자 p
    participant A as 수락자 과반
    participant q as 제안자 q
    p->>A: prepare · 번호 n1
    A-->>p: 약속 (n1)
    q->>A: prepare · 번호 n2 · n2 는 n1 보다 크다
    A-->>q: 약속 (n2)
    p->>A: accept · 번호 n1
    Note over A: n2 를 약속했다. n1 은 무시된다
    p->>A: prepare · 번호 n3 · n3 는 n2 보다 크다
    A-->>p: 약속 (n3)
    q->>A: accept · 번호 n2
    Note over A: n3 을 약속했다. n2 는 무시된다
    Note over p,q: 이 뒤로 서로 상대보다 큰 번호로 새로 시작하는 일이 끝없이 되풀이된다

진행을 보장하려면 제안을 내려고 시도하는 유일한 주체로 지정된 제안자를 하나 뽑아야 합니다. 앞서 본 조정자·마스터가 바로 이 지정된 제안자의 자리입니다 — Multi-Paxos 가 조정자를 오랜 기간 하나로 잡아 두는 것도 이 지정된 제안자를 안정적으로 유지하려는 것입니다. 그 지정된 제안자가 수락자 과반과 통신에 성공하고, 이미 쓰인 어떤 번호보다 큰 번호를 쓴다면, 수락되는 제안을 내는 데 성공합니다. 더 높은 제안 번호를 가진 요청을 알게 됐을 때 자기 제안을 버리고 다시 시도하면, 지정된 제안자는 결국 충분히 높은 제안 번호를 고르게 됩니다.

제안자와 수락자와 통신망이 충분히 제대로 돌고 있다면, 지정된 제안자 하나를 선출하는 것으로 진행성을 얻을 수 있습니다. 그런데 FLP(Fischer, Lynch, Paterson) 불가능성이라는 유명한 결과가 있습니다. 이 FLP 불가능성 결과는 제안자를 뽑는 신뢰할 만한 알고리즘이 무작위성이나 실제 시간 가운데 하나를 반드시 써야 한다는 것을 함의합니다. 타임아웃을 쓰는 것이 그 예입니다. 다만 선출의 성공 여부와 무관하게 안전성은 보장된다고 Lamport 는 못 박습니다.

메시지 유실 때문에, 값이 선택됐는데도 아무 학습자도 그것을 끝내 알지 못할 수 있습니다. 학습자가 값이 선택됐는지 알아야 한다면, 제안자에게 위의 알고리즘대로 제안을 하나 내게 하면 됩니다. 그 제안이 Phase 1 을 도는 동안 제안자는 과반의 수락자로부터 그들이 수락한 제안 가운데 번호가 가장 높은 것을 받아 옵니다. 이미 선택된 값이 있었다면 제안자는 그 값을 자기 제안의 값으로 삼게 됩니다. P2 가 보장하는 것이 그것입니다. 그래서 새 제안이 수락되는 것을 보면 학습자는 선택된 값을 알게 됩니다.

보장과 가정

보장은 앞서 적은 안전성 요구사항 셋입니다. 제안된 적이 있는 값만 선택될 수 있고, 단 하나의 값만 선택되며, 실제로 선택되지 않은 값을 선택됐다고 학습하는 프로세스는 없습니다. 진행성은 정밀하게 명세되지 않습니다. Chubby 논문은 이 경계를 한 문장으로 옮겨 적습니다. Paxos 는 타이밍 가정 없이 안전성을 유지하지만, 진행성을 보장하려면 시계를 들여와야 한다는 것입니다.

가정은 통상적인 비동기 비잔틴 아닌 모델입니다.

비잔틴 실패가 없다는 가정은 값을 정하는 자리에서만 쓰이지 않습니다. 학습 단계에서도 쓰입니다. 학습자끼리 값이 수락됐다는 사실을 서로에게서 알아내는 일이 이 가정 위에서 쉬워집니다.

관련 항목

참여자

제안자 · 수락자 · 학습자

함께 쓰이는 장치와 개념

합의 · 정족수 · 리더 선출 · 상태 기계 · 비잔틴 실패

이것을 실제로 구현·채택한 제품

Chubby · Spanner · Boxwood