Paxos Made Simple

Paxos Made Simple by Leslie Lamport

Paxos Made Simple이라는 글의 저자인 Leslie Lamport는 분산 컴퓨팅 분야에서는 너무나 유명한 분이기 때문에 따로 설명할 필요가 없을 정도입니다. 예를 들어, 1978년에 출판된 “Time, Clocks, and the Ordering of Events in a Distributed System”과 같은 페이퍼는 인용 회수로 볼 수 있는 그 영향력 뿐만 아니라 OS 수업의 읽기 과제로도 빠질 수 없는 그야말로 seminal work입니다. 그의 주요한 업적 중 하나가 바로 Paxos 알고리즘인데, 최근에는 Chubby나 Zookeeper 등의 제품으로 구현되어 분산 시스템의 중요성이 점점 떠오르고 있는 요즈음 더욱 더 일상적으로 쓰이게 되어가고 있습니다.

The Paxos algorithm, when presented in plain English, is very simple.

Abstract에서 보다시피 이 글은 Paxos 알고리즘을 쉬운 말로 설명하고자 하는 시도인데, 합의 문제로부터 정의되는 조건을 충족하기 위한 자연스러운 해결책이 바로 Paxos 알고리즘임을 보이려 하고  있습니다.

하지만, 논리적인 단계들을 정확하기 이해하기 위해서는 쉬운 말로 쓰여진 용어들을 정확하게 해석해야 하기 때문에, 프로그래머 입장에서 볼 때는, 오히려 의사 코드 수준으로 설명하는 다른 글 (예를 들어, Paxos Made Moderately Complex)들이 훨씬 더 이해하기 쉽다는 생각이 들었습니다.

아래는 요약이라고 하기에는 너무 길고, 그렇다고 번역이라고 할 수도 없지만, 개인적으로 중요하다고 생각한 점들을 기록한 메모라고 보시면 좋을 것 같습니다.

1. Overview

Paxos 알고리즘은

• 여러 노드 사이에서 하나의 값을 합의하기 (consensus) 위한 synod 알고리즘과
• 이를 이용해 동일한 순서로 오퍼레이션을 실행할 수 있도록 sequence number별로 오퍼레이션의 합의하는 알고리즘으로

구성되어 있습니다.

2. The Consensus Algorithm

2.1. The Problem

일반적으로 합의 알고리즘은 여러 프로세스들로부터 여러 값들을 제안 받고, 그 값 들 중 하나의 값을 선택하고 선택한 값을 여러 프로세스들이 인지하는 문제입니다.

안전성 (safety) 요건은 다음과 같습니다.

• 제안된 (proposed) 값들 중 단 하나의 값이 선택될 수 있으며 (chosen)
• 프로세스들은 선택된 값만을 인지 (learns) 해야합니다.

synod 알고리즘에서는 proposer, acceptor, learner로 프로세스들의 논리적인 역할을 구분하고 있습니다.

각 agent 사이의 통신은 비동기적이며 non-Byzantine 모델입니다. 즉,

• 각 agent는 느려질 수 있으며 정지하거나 재기동할 수 있습니다.
• 메시지는 느리게 배달되거나 중복되거나 소실될 수 있지만, 변조되지는 않습니다.

 2.2. Choosing a Value

첫번째로 받은 제안을 선택하는 단 하나의 acceptor가 존재한다면 쉽게 합의를 이룰 수 있으나, 그 하나의 acceptor에서 failure가 발생하면 합의를 이룰 수 없게 되기 때문에 답이 될 수 없습니다. 따라서, 다수의 acceptor가 존재해야합니다. proposer는 다수의 acceptor에게 제안을 보낼 수 있고, 과반수 (majority)의 acceptor가 수락 (accept)한 값을 선택하는 방법을 생각해봅시다.

이를 위해서는 acceptor는 많아야 (at most) 하나의 값을 수락해야 합니다. 단 하나의 propser가 하나의 값만을 제안하더라도 값이 선택될 수 있어야 하기 때문에 다음 요구사항을 도출됩니다.

P1. acceptor는 수신한 첫번째 제안을 수락해야한다.

이 때 문제는 다수의 proposer가 동시에 여러가지 값들을 제안했을 때, 다수결에 의해서는 단일한 값을 선택할 수 없는 경우가 발생합니다. 예를 들어, 단 2개의 값을 제안한다고 하더라도 정확히 반수의 acceptor들의 수락을 나누어 가진다면 다수결이 성립하지 않게 됩니다. 이 문제를 해결하기 위해서, acceptor가 하나 이상의 제안을 수락할 수 있도록 허용해야 합니다.

하지만, 여기서 문제는 하나 이상의 제안을 수락하게 됨으로써 하나 이상의 제안이 선택될 가능성이 생긴다는 점입니다. 따라서, 하나 이상의 제안이 선택되더라도 그 제안들이 제안하는 값은 모두 동일함을 보장할 방법이 필요합니다.

이것들 다시 얘기하면, 어떤 제안이 선택된다면 그 이후의 선택되는 제안들도 그 제안과 같은 값을 가진다 (P2)는 말로 풀어낼 수 있습니다. 그 충분조건으로서, 어떤 제안이 선택된다면 이 후의 제안들은 (선택되거나 수락되지 않더라도) 모두 그 제안과 동일한 값을 가지도록 (P2b) 하는 방법을 모색해봅니다. 여기서, P2b의 충분조건에 해당하는 P2c를 발견합니다.

P2c. 일련번호가 n이고, 값이 v인 제안이 제기되었다면, 다음과 같은 성질을 만족하는 과반수의 acceptor 집합 S가 존재한다:

• S에 속하는 어떤 acceptor도 n보다 작은 일련번호의 제안을 수락한적이 없거나,
• S에 속하는 acceptor가 수락한 일련번호가 n보다 작은 모든 제안들 중 가장 큰 일련번호를 가진 제안의 값은 v임.

P2c를 만족시키기 위해서는, n번째 제안을 하려고 하는 proposer는 n보다 작은 일련번호의 제안들 중 다수의 acceptor 집합에 의해 수락되었거나 수락될 가장 높은 숫자의 제안을 알아내어야 합니다. 그런데, 미래의 수락에 대해 예측하는 것을 불가능하므로, 반대로 이 조건을 위배하는 수락이 없도록 하는 약속을 proposer가 acceptor로부터 받아내는 방법이 있습니다. 다시 말해, proposer는 acceptor들이 n보다 작은 제안을 더이상 수락하지 않을 것을 요청하는 것입니다.

결과적으로 proposer의 알고리즘은 다음과 같습니다.

1. proposer는 새로운 일련번호 n을 선택하고 어떤 acceptor의 집합에게 다음과 같이 응답하도록 요청을 보낸다 (prepare request):
   1. n보다 작은 제안을 수락하지 않을 것을 약속
   2. 현재까지 수락했던 제안들 중 n보다 작지만 가장 큰 일련번호를 가진 제안
2. 다수의 acceptor로부터 proposer가 요청한 응답을 받는다면, n번째 제안을 제기할 수 있다.
   1. 단, 응답으로 돌아온 가장 큰 일련번호의 제안이 존재한다면, 그 제안의 값과 제기하려는 제안의 값은 동일해야함.
   2. 그러한 제안이 존재하지 않는다면 어떤 값의 제안이라도 무방함.
3. proposer는 acceptor에게 제안을 수락할 것을 요청한다. (accept request)

acceptor는 proposer의 어떤 요청이든 무시할 수 있어야 하기 때문에 응답할 수 있는 조건을 정하면 됩니다. prepare 요청에는 언제든지 응답하더라도 상관이 없고, accept 요청에는

P1a. acceptor는 n보다 큰 숫자의 prepare 요청에 응답하지 않은 경우에만, n번째 제안을 수락할 수 있다.

prepare 요청에 언제든지 응답하더라도 알고리즘의 동작에 문제는 없지만, n번 prepare 요청을 받았을 때 n보다 큰 prepare 요청에 응답한적이 있다면 n번 prepare 요청에 응답하는 것은 아무런 의미가 없으므로 무시하도록 합니다. 이미 수락한 제안에 대한 prepare 요청도 동일한 이유로 무시합니다.

결과적으로 acceptor는 수락했던 가장 큰 일련번호의 제안과 응답했던 가장 큰 일련번호의 prepare 요청만 기억하고 있으면 됩니다. proposer의 경우 제안을 포기하거나 잊어버려도 동작에 상관이 없습니다. 다만, 제안 일련번호의 발급은 중복되어서는 안됩니다.

다시 정리하면 다음과 같은 알고리즘이 됩니다.

• Phase 1.
  • (a) proposer는 새로운 일련 번호 n을 선택하고, 다수의 acceptor에게 일련번호 n의 prepare 요청을 보냄.
  • (b) acceptor가 이미 응답했던 prepare 요청의 일련 번호보다 더 큰 일련번호 n의 prepare 요청을 받는다면, n보다 작은 일련번호의 제안을 수락하지 않는다는 약속과, 지금까지 수락했던 가장 큰 일련번호의 제안을 응답으로 보냄.
• Phase 2.
  • (a) proposer가 prepare 요청의 응답을 다수의 acceptor로부터 받는다면, 일련번호 n의 제안에 대한 accept 요청을 보냄.
  • (b) acceptor가 n번 제안에 대한 accept 요청을 받는다면, 일련번호가 n보다 큰 prepare 요청에 응답한 적이 없을 경우에만, 그 제안을 수락한다.

Phase 2에서 만약 acceptor가 일련번호가 n보다 큰 prepare요청에 응답한 적이 있다면, 단순히 무시하기보다는 proposer에게 그 제안을 포기하라고 알려준다면, 정확성에 영향 없이 최적화를 할 수 있습니다.

2.3. Learning a Chosen Value

다수의 acceptor가 어떤 제안을 수락했다면 그 제안은 선택된 것으로 learner에게 알려주어야 합니다. 간단하게는 acceptor가 자신이 수락한 모든 제안을 모든 learner에게 보내주면 되지만, 그렇다면 너무 많은 메시지를 보내어야 합니다. 따라서, acceptor들은 특별한 (distinguished) learner 또는 그 집합에게만 수락한 제안을 보내고, 어떤 값이 선택될 경우에만 다른 learner에게 그 제안을 보내주도록 할 수 있습니다.

메시지의 손실로 인해 learner가 선택된 값을 알지 못하는 일이 일어날 수도 있습니다. learner가 acceptor에게 물어볼 수 있다고 하더라도 acceptor의 failure로 인해 다수에 의해 수락된 값을 알지 못하는 경우도 발생할 수 있습니다. 이 때, learner는 proposer에게 제안을 하도록 해서 어떤 값이 선택되었는지를 알아내는 방법이 있습니다.

2.4. Progress

두 proposer가 계속 제안을 발행하지만 어떤 제안도 선택되지 않는 시나리오를 쉽게 상정할 수 있습니다. 알고리즘의 진행(progress)을 보장하기 위해서, 특별한 (distinguished) proposer만이 제안을 발행하는 유일한 프로세스가 되어야 합니다. 알고리즘의 liveness를 보장하기 위해서 proposer를 선출하는 알고리즘은 무작위성이나 timeout과 같은 실시간성을 이용해야만 합니다.

2.5. Implementation

• 특별한 proposer와 특별한 learner가 될 leader를 선택합니다.
• 합의 알고리즘은 위에서 설명한 synod 알고리즘이고, 이 때 사용되는 요청과 응답은 일반적인 메시지로 보냅니다.
• acceptor는 응답하기 전에 의도한 응답을 기록하기 위해서 stable storage를 사용합니다.
• 서로 겹치지 않는 집합의 숫자를 선택하고, 각각의 proposer는 자신이 발급한 제안을 기억하다록 해서 제안의 일련번호를 unique하게 유지합니다.

3. Implementing a State Machine

하나의 서버는 클라이언트로부터의 명령을 어떤 순서로 수행하는 deterministic state machine으로 표현됩니다. 따라서, 여러 서버에서 동일한 순서의 명령을 실행한다면, 동일한 순서로 상태와 출력을 생성할 것입니다.

모든 서버의 state machine이 동일한 순서로 명령을 실행하도록 보장하기 위해서는 순서 상의 각각의 명령을 합의하기 위한 합의 알고리즘의 instance들을 사용합니다. 즉, i번째 instance에서 합의 알고리즘에 의해 선택된 값이 i번째 state machine 명령이 됩니다.

통상의 작동에서는 단일 서버가 리더로 선출되어 특별한 proposer 역할을 합니다. 클라이언트가 리더에게 명령을 보내면 리더는 각 명령이 몇번째 순서인지 정합니다. 즉, 어떤 명령을 리더가 135번째라고 결정하면 135번째 합의 알고리즘 instance의 값으로 선택하려고 시도합니다. 이 시도는 보통은 성공하지만, 서버의 failure가 발생하거나 다른 서버도 자신이 리더라고 생각하는 경우가 있으면 실패할 수 있습니다.

Paxos 알고리즘의 중요한 장점은 2개의 phase로 나누어져 있어서, phase 2까지 시작되기 전까지는 값이 결정되지 않는다는 것입니다. 즉, 여러 instance들에 대해 phase 1을 실행한 후, 그 결과에 따라서 값을 정해서 phase 2를 시작할 수 있습니다.

특히, 새로 선택된 리더는 무한히 많은 consensus algorithm instance의 phase 1을 실행합니다. 모든 instance에 대해 동일한 일련번호의 제안을 사용한다면, 단 하나의 메시지를 모든 서버에 보내는 것으로 이를 처리할 수 있습니다. acceptor는 이미 phase 2 메시지를 받았을 때만 simple OK이상의 응답을 하기 때문에, 역시 모든 instance에 대해 하나의 메시지로 응답하는 최적화가 가능합니다.

리더의 실패나 새로운 리더의 선출은 흔히 발생하지 않기 때문에 실제로 state machine 명령을 실행하는 실제 비용은 phase 2를 실행하는 비용입니다. phase 2는 fault가 존재하는 하에 합의를 이르기 위한 최소한의 비용임을 증명할 수 있으므로, Paxos 알고리즘은 본질적으로 최적입니다.

비정상적인 조건에서 리더가 없다면 새로운 명령은 제안되지 않습니다. 여러 서버가 자신이 리더라고 생각한다면 어떤 값도 선택되지 않을 수 있습니다.