MIT 6.5840 Paxos

목차
Paxos Made Simple
1. https://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf

Paxos Lecture
2. https://pdos.csail.mit.edu/6.824/notes/l-paxos.txt

Paxos Pseudo Code
3. https://pdos.csail.mit.edu/6.824/notes/paxos-code.html

Paxos Agreement - Computerphile (시각화를 잘 한 것 같음)
4. https://www.youtube.com/watch?v=s8JqcZtvnsM

Paxos Made Simple

Leslie Lamport
01 Nov 2001

초록
Paxos 알고리즘은 영어로 볼 때 간단합니다. (원문은 그리스어로 써있다고 한다.)

목차

1 Introduction
2 합의 알고리즘
2.1 문제 정의
2.2 값 선택
2.3 선택된 값을 알아내기
2.4 진행
2.5 구현
3 상태 머신 구현

1 개요

Fault Tolerant distributed system을 구현한 Paxos 알고리즘은 이해하기 어렵다고 알려져왔다. 왜냐하면 원서가 그리스어로 작성되어있었기 때문일것이다. 실제로는, Paxos는 가장 심플하면서도 이해하기쉬운 분산 알고리즘이다. 그 핵심에는 합의 알고리즘이 있다. synod 알고리즘이다. 다음 섹션은 이 합의 알고리즘을 만족시키기 위해 반드시 따라야하는 특징을 보여줄 것이다. 마지막 섹션에서는 완전한 Paxos 알고리즘을 보여줄것이다. 분산 시스템을 개발하기 위해 상태 머신 접근법에서 구현된 합의 알고리즘을 적용하여 얻어진것이며, 분산 시스템 이론에서 가장 많이 인용된 주제이다.

2 합의 알고리즘

2.1 문제

여기서 나는 proposer를 제안자로 쓸 수 있으나 원어 그대로 쓸것이다. chosen은 선출로 표기한다.

값을 제안하는 프로세스들의 집합을 가정하자. 합의 알고리즘은 그런 제안된 값들 중 단 하나를 선출하는 것이다. 만약 어느 값도 제안되지 않으면, 어떤 값도 선출되지 않는다. 만약 값이 선출되었다면, 프로세스들은 어떤 값이 선출되었는지 알 수 있어야한다. 합의 알고리즘을 만족시키는 요구사항은 다음과 같다.

1 제안 된 값들만 선출될 수 있다.
2 한 개 값 만 선출될 수 있다.
3 프로세스는 선출되지 않은 값을 알 수 없다.

우리는 liveness 요구사항을 엄밀하게 정의하지는 않겠다.

분산 시스템의 safety, liveness 개념은 이 논문을 작성한 Lamport가 제시한 개념이다. liveness는 분산 시스템에서 발생해야할 좋은 것들을 말한다. 이상적인 상태에서 시작된 작업의 정상 종료, 이상적인 상태에서 시작된 작업이 종료되지 않고 계속 실행, 임계영역에 진입을 시도할 때 결국(eventually) 임계영역에 진입함, 경합 상황에서 자원에 대한 공정한 접근이 보장되는것 등 시간이 지나면 결국 어떤 바람직한 상태가 되는 것을 liveness 개념이라고 한다. 임계영역에 들어가고자 하면 반드시 들어간다 는 긍정의 뜻이다. 반대로 safety 개념은 나쁜일을 발생시키지 않는 개념이다. 이상적인 상태에서의 실행이 종료되었으나, 실행의 결과가 만족하지 않는 경우. 두 프로세스가 동시에 실행되었으나 두 프로그램 카운터가 지정된 임계영역에서 실행되고 있을 때. 두 프로세스가 동시에 실행되었으나, 상대방의 상태 변화를 기다리고 있을 때.(데드락) 즉 여기 논문에서는 나쁜 상태를 가르키지 않는 - 보장하기 위한 요구사항만 검토할것이라는 이야기다 [https://en.wikipedia.org/wiki/Safety_and_liveness_properties]

그러나, 목표는 제안된 값 중 어떤 것은 결과적으로 선출이 될 것이고, 값이 선출이 되었다면 프로세스는 그 값을 알게될 것이라는 것이다.
우리는 합의 알고리즘을 수행하기 위해 세가지 롤을 가진 세가지 Agent를 정의할 것 이다. propsers, acceptors, learners 이다. 구현에서는 프로세스 한 개가 여러 Agent 처럼 작동을 할 수도 있다 그러나 Agent를 프로세스에 매핑하는 것은 여기서 고려할 사항은 아니다.

Agent들은 서로 message를 전송하며 통신한다고 가정하자. 우리는 관례적으로 사용되는 비동기, non-Byzantine model을 사용할 것이다.

1 Agents는 임의의 속도로 동작하며, 멈추거나 재시작할 수 있다. 값이 선출된 이후로 모든 Agent가 멈출 수도 있거나 재시작 할 수 있기에, 실패 후 재시작한 agent에서 몇 몇 정보를 기억할 수 없다면 해결책은 불가능할 수 있다.
2 Message는 임의의 길이로 전달될 수 있으며, 중복될 수 있고, 손실될 수 있고, 오염될 수 도 있다.

non-Byzantine model: 노드가 악의적인 행동을 하지 않고, 단순히 고장 등으로 멈추는 것만을 고려한다.

2.2 값 선택

값을 선출하는 가장 쉬운 방법은 acceptor Agent를 하나 가지는 것이다. propser는 가장 먼저 전달받은 제안된 값을 선출하도록 동작하는 acceptor에게, propose를 보낸다. 간단하지만, 이 해결책은 만족스럽지 못하다. 왜냐하면 acceptor가 실패한다면 추후 진행이 불가능하기 때문이다.
그래서 다른 방법으로 값을 선출하는 것을 고려해봐야한다. 한 acceptor대신 여러 acceptor agents를 활용해보자. propser가 propose 값을 acceptor set에게 보낸다. Acceptor는 propse된 값을 수락할 수 있다. 충분히 큰 acceptor set에 의해 수락된다면, 그 값은 선출된다. 근데 얼마나 커야할까? 한 값이 선출되기 위해선, 충분히 큰 수의 과반수 agent가 필요하다. 임의의 두 과반수는 반드시 적어도 하나의 공통 인자를 가지고, acceptor는 최대 하나의 값만 수락하므로, 두 개의 값이 선출될 수 없다.

{A, B, C} ... {C, D, E} 두 set이 있을 때 C는 공통인자이다. 이 때, acceptor C는 단 하나의 값만 수락 할 수 있다면 선출될 수 있는 값은 {A, B, C} ~ X 또는 {C, D, E} ~ Y 중 하나의 값만 선출될 수 밖에 없다. 만약 X면 {A, B, C}일 것 이다. 즉, 두 개의 서로 다른 값이 동시에 선택될 수 없다.

메시지 손실이나 실패를 제외하고, 단 한 proposer에 의해 값이 제안되면 값이 선출되는 것을 바란다. 이는 다음 요구 사항을 제시한다.

P1. Acceptor는 받은 값 중 처음으로 제안된 값을 반드시 수락한다.

이 요구사항은 다음 문제를 일으킨다. 다른 propser들이 같은 시간에 여러 값들을 제안할 수 있고, 이는 모든 acceptor들이 값을 수락할 수 있게 만든다. 이는, 어떠한 과반수의 값도 선출되지 않을 수도 있다. 값 두 개가 제안되었고, 각 값들이 acceptor 절반씩 수락된 상태에서, 한 acceptor가 실패한다면 어떤 값이 선출되었는지 알 수 없을 수 있다.

{A, B} -> value X 수락 {C, D} -> value Y 수락. B가 실패한 케이스에서 {A} -> X, {C, D} -> Y만 알 수 있다. 시스템 입장에서는 Y가 선택되었는지 아무것도 선택되었는지 알 수 없다.

P1과 acceptors의 과반수에 의해 값이 선출될 수 있다는 요구사항은 acceptor가 제안된 값을 한 개 이상의 수락해야한다는 것을 뜻한다.

바로 이전 예제, 실패하였을 경우를 고려하라.

우리는 acceptor가 각 제안에 번호를 매기면서 수락한다고 하자. 그러므로, 각 제안들은 value와 number(acceptor가 지정한)을 가진다. 혼란을 피하기 위해 우리는 각기 다른 제안들은 각기 다른 번호를 부여받는다고 하자. 이게 어떻게 되는지는 구현 방식에 따라 다르지만, 지금은 그렇다고 가정하자. 제안 하나가 어떤 값을 가지고 그게 과반수의 acceptor에 의해 수락되면 값이 선출된다. 이러한 상황에서, 우리는 제안(값)은 선출된다고 한다.

우리는 여러개의 제안이 선출될 수 있도록 허락할 수 있으나, 선출된 제안들이 모두 같은 값임을 보장해야한다. 제안의 번호를 기준으로 귀납적으로 생각하면, 다음 조건만 만족하면 충분하다.

P2. 만약 v값을 가진 한 제안이 선출된다면, 그 후 모든 순번 제안들이 선출된다면 v값이다.

번호는 순서대로 정렬된 순번이므로, 조건 P2는 한 값만 선출된다는 핵심적인 안정성 성질을 보장한다.
값이 선출될 수 있도록, 제안은 반드시 최소 하나의 acceptor에게 수락되어야하고, P2는 다음을 만족함으로써 충족할 수 있다.

P2a. 만약 v값을 가진 한 제안이 선출 된다면, 그 후 모든 순번 제안들이 어떤 acceptor들에게 수락된다면 그 값은 v이다.

우리는 여전히 어떤 제안들이 선출될 수 있도록 하기위해 P1을 유지한다. 왜냐하면 통신은 비동기며, 제안은 어떠한 제안도 받지 않은 acceptor c에 의해 값이 선출될 수 도 있기 때문이다.

말 그대로 시스템은 비동기이고, 임의의 acceptor c에 의해 Paxos 시스템에서 선출될 값이 결정될 수 있다는 말이다. 왜냐하면 P1은 처음으로 제안된 값을 반드시 수락하니 말이다.

새로운 proposer가 말 그대로 깨어났고, 다른 값의 후 순번의 제안을 하였을 때를 가정해보자. P1은 acceptor c가 이 제안을 수락한다고 해야한다. 근데 이 것은 P2a를 위반한다. P1과 P2a를 동시에 유지하기위해, P2a의 내용을 강화할 필요가 있다.

P2b. 만약 v 값을 가진 한 제안이 선출 된다면, 어떤 propser에서든지 제안된 후 순번 제안들의 값은 v이다.

제안은 acceptor에게 수락되기 이전에, 반드시 proposer로 부터 생성되어야하고, P2b는 P2a를 포함하므로, 즉 P2를 포함한다.

P2b가 어떻게 충족되는지를 확인하기 위해, 어떻게 그것이 성립되는지 증명할 방법을 고려해보자. 우리는 번호 m의 값 v로 선출된 어떤 제안이 있다고 가정하고, n > m인 번호를 가진 제안들 또한 값 v를 제안함을 증명하자. n에 대해 귀납법을 이용하여 쉽게 증명할 것이며, 번호 n의 제안이 다음과 같은 가정 하에서 값 v를 가짐을 증명할 것이다. 가정은 다음과 같다. m...(n-1) 번호의 제안은 값 v를 가진다. 여기서 i..j는 번호의 집합 i에서부터 j까지를 뜻한다. 번호 m의 제안이 선출되기 위해선, 그 번호 m을 과반수로 선택한 acceptors로 이루어진 집합 C가 존재해야한다. 이 것과 귀납적 가정을 조합하여 보면, m이 선출되었다는 가설은 다음을 뜻한다.

집합 C에 있는 모든 acceptors는 m...(n-1) 번호의 제안에 모두 수락하였고, 어떠한 acceptor에 수락된 m...(n-1) 번호의 모든 제안은 값 v를 가지고 있다

acceptor의 과반수 집합 S는 acceptor 집합 C의 원소를 최소 하나를 포함하므로, 다음과 같은 불변 속성을 확인함으로써, 값 v를 가지는 번호 n의 제안을 결론내릴 수 있다.

P2c. 어떤 v와 n에 대해서, 값 v를 가지며 번호가 n인 제안이 제시되면, 다음을 만족하는 acceptor의 과반수 집합 S는 존재한다. (a) 집합 S의 어떤 acceptor도 번호 n 미만의 제안을 수락하지 않는다. (b) 값 v의 제안은 집합 S의 acceptor가 수락한 번호가 n이하의 제안들 중 가장 순번이 높은 제안이다.

그러므로 우리는 P2c의 불변 속성을 만족함으로써 P2b를 충족할 수 있다.
P2c의 불변성을 얻기위해, n 번호의 제안을 제시하고 싶은 proposer는 반드시 n 이하의 번호 중 가장 큰 번호의 제안을 알아야한다. 즉, 어떤 과반의 acceptors에 의해서 수락되었거나 수락될 가능성이 있는 제안의 값을 알아야한다. 이미 수락된 제안을 아는 것은 쉽다. 미래에 수락될 제안을 아는 것은 어렵다. 미래를 예측하기보다는, propser가 다른 수락이 없을거라는 가능성을 제외함으로써 그것을 컨트롤한다. 다시 말해, proposer는 acceptor에게 더이상 n 이하의 번호를 가진 제안을 수락하지 말라고 요청한다. 이 방식은 proposer가 제안을 제시하는 알고리즘을 도출한다.

1. Propser는 번호 n 제안을 고르고 acceptor 집합 내의 각 원소에게, 다음과 같은 응답을 요구한다.
(a) n 번호 이하의 제안에 대해서 더이상 수락하지 않음을 약속
(b) n 번호 이하의 수락된 제안 중 가장 큰 순번의 제안
이를 번호 n인 prepare 요청이라고 한다

2 propser가 과반수 acceptor로 부터 요청하였던 응답을 받는다면, 번호가 n이며 값 v 에 대하여 제안을 할 수 있다. 여기서 v는 응답값 중에서 가장 높은 순번의 제안이거나 응답한 acceptor들이 어떠한 제안도 보고하지 않았다면, v는 proposer가 임의로 선출한 값이 된다.

proposer는 acceptor에게 선택될 제안을, 요청을 전송하여 제안한다. (이건 첫 요청이 받아들여진 acceptor와 같을 필요가 없다.) 이를 accept 요청이라고 하자.
이는 proposer의 알고리즘을 묘사한다. acceptor는 어떨까? acceptor는 proposer에게 2가지 요청을 받는다. prepare 요청과 accept 요청이다. acceptor는 조건을 충족하지 않는 어떠한 요청도 거절할 수 있다. 그래서, 우리는 요청에 대해 응답하는게 허용된 경우에만 이야기를 하고자 한다. prepare 요청에 대해서는 항당 응답할 수 있다. accept 요청에도 응답할 수 있는데, 이전에 제안을 수락하겠다고 약속한 적이 없는 경우에 한해 제안을 수락하는 방식으로 응답할 수 있다. 다르게 표현하자면,

P1a Acceptor는 번호 n의 제안에 대해 수락할 수 있다. 이는, 번호 n 보다 큰 prepare 요청에 대해 응답을 하지 않은 경우에 가능하다.

P1a가 P1을 포함한다는 것을 관찰하라.

우리는 제안 번호가 고유하다는 가정하에, 안전 속성(safety properties)를 만족하며 값을 선출하는 모든 알고리즘을 가졌다. 마지막 알고리즘은 약간의 최적화를 더해서 얻을 수 있다.

acceptor가 번호 n인 prepare 요청을 받는다고 가정하자, 그러나 이미 번호 n 보다 큰 prepare 요청으로 응답하였다고 하자. 그러므로 번호 n의 새로운 제안은 수락될 가능성이 없다. 그러므로 acceptor는 이 새로운 prepare 요청에 대해 답할 이유가 없다. 왜냐하면 propser가 제시하는 이 번호 n 제안은 수락하지 않을 것이기 때문이다. 그래서 우리는 prepare 요청에 응답을 하지 않게 할 수 있다. 그리고 이미 수락된 제안의 prepare 요청도 무시할 수 있다.

이 최적화를 하기위해서는, acceptor는 수락된 제안들 중 가장 높은 순번을 가진 제안을 기억해야하고 그리고 수락 응답을 하였던 prepare 요청 중 가장 높은 순번의 제안을 기억해야한다. 왜냐하면 P2c는 실패와 상관없이 불변해야하며, acceptor는 실패 또는 재시작을 하더라도 반드시 이 정보를 기억해야한다. proposer는 같은 순번의 제안 들 중에 제시하지 않은 제안들에 대해서는 항상 제안을 버릴 수 있거나, 제안에 대해서 잊어버릴 수 있다는 것을 기억해둬라.

propsoser와 acceptor의 이 동작을 같이 놓는다면, 알고리즘은 두 단계로 실행될 수 있음을 볼 수 있다.

Phase 1. (a) proposer는 n 순번의 제안을 선택하여 해당 순번 n 제안을 prepare 요청을 과반수의 acceptor에게 보낸다. (b) 만약 acceptor가 이미 응답하였었던 것 보다 큰 순번인 n인 임의의 prepare 요청을 받는다면, 순번 n번보다 낮은 제안을 수락하지 않음을 약속하고 또한 가장 높은 순번의 제안을 함께 응답한다.

Phase 2. (a) 만약 propser가 prepare 요청에 대해 과반수의 acceptor로 부터 응답값을 받았다면(순번 n), 그러면 accept 요청을 각 acceptor에게 순번 n과 값 v로 보낸다. 이 때 v는 응답받은 제안들 중 가장 큰 순번의 제안 값이다. 또는 이전에 제안이 없었다면 임의의 값이 될 수 있다. (b) 만약 acceptor가 순번 n에 대하여 accept 요청을 받는다면, 순번 n보다 큰 prepare 요청에 대해 응답을 하지 않은 경우에는 제안을 수락한다.

Proposer는 여러개의 제안을 수행할 수 있으며, 알고리즘은 각각 그 단계를 수행한다. Proposer는 임의의 시점에서 프로토콜 중간 지점에서 제안을 버릴 수 있다. (제안의 요청이나 응답이 제안이 버려진 뒤에도 그들의 목적지에 도착한다하더라도, 알고리즘의 정당성은 깨지지 않는다) 이미 더 높은 순번의 제안이 어떤 proposer에게 제안되려고 할때 그 보다 적은 순번의 제안을 버리는 것은 좋은 아이디어이다. 그러므로, acceptor가 prepare 또는 accept 요청을 무시한다면, 해당 제안을 버려야할 proposer에게 알려줘야한다. 이것은 알고리즘의 정당성에 영향을 끼치지 않는 성능 최적화다.

2.3 선출된 값을 알아내기

선출된 값을 알아내기 위해서, learner는 acceptor 과반수에 의해 수락된 제안을 알아내야한다. 확실한 알고리즘은, 제안을 선택한 acceptor에 대해 언제든지, 모든 learner에게 해당 제안을 알려주게 만드는 것이다. 이로 leaner는 어떤 값이 선출될수 있는지 알 수 있지만, 각 acceptor가 각 leaner에게 답을 해야하므로, learners * accetpors 갯수만큼 응답을 생성한다.
non-Byzantine 실패 모델의 가정은, 한 learner가 다른 learner에게 알려줄 수 있게 만들긴 쉽다. acceptor가 특별한 learner에게 그들이 수락한 것에 대해 응답하게 할 수 있고, 해당 learner가 다른 learner에게 알려줄 수 있게 할 수 있다. 이 접근법은 모든 learner가 선출된 값을 알아내기 위해선 한 번의 더 통신을 요구한다. 이 방식은 덜 신뢰성이 있긴 하지만, acceptor의 수와 learner의 수의 합으로만 응답을 구성할 수 있다.

non-Byzantine 모델에선 악의적인 노드가 없을 것이기에 learner -> learner는 가능하다.

더 일반화하여, acceptor는 특별한 learner 집합에게 그들이 수락한 제안을 알려줄 수 있고, 해당 learner들은 다른 learner에게 알려줄 수 있다. 더 큰 특별 learner 집합을 이용하여, 통신 비용을 높이더라도 신뢰성을 높일 수 있다.
메시지는 유실 될 수 있기에, 선출된 값이 어떠한 learner도 알수 없을 수 도 있다. learner는 acceptor에게 어떤 값을 수락했는지 물어봐야하고, acceptor가 실패로 특정 제안이 과반에 의해 수락되었는지 아닌지 알수 없을 수도 있다. 이런 상황에서, learner는 새 제안이 선출되었을 때만 어떤 값이 선출되었는지 알수 있다. 만약 어떤 값이 선출되었는지 learner가 알고 싶다면, proposer가 제안을 생성하게끔 할 수 있는데, 위에 설명된 알고리즘을 통해서 수행한다.

2.4 진행

두 proposer가 증가하는 순번으로 제안을 생성하고 제시하는 시나리오를 만들어보자. 여기서 어떠한 값도 선출되지 않는다. Proposer p가 순번 n1으로 Phase1을 완료한다고하자. 다른 proposer q가 순번 n2 (> n1)으로 제안을 완료한다고 하자. Proposer p의 Phase2의 순번 n1인 accept 요청은 무시된다. 왜냐하면 순번 n2보다 작은 제안에 대해선 무시하도록 되어있기 때문이다. 그래서 Proposer p는 Phase1을 종료하고, 새로운 순번 n3(> n2)에 대해 Phase1을 다시 시작한다. 그리고 Proposer q가 제안한 Phase2 accept 요청은 무시된다. 그리고 이게 반복된다.
이 진행을 보장하기 위해, 특별한 propser는 제안을 생성하는 유일한 proposer로 선출되어야 한다. 만약 특별 proposer가 과반수의 acceptor와 성공적으로 통신하게 된다면, 그리고 이미 사용된 순번의 제안보다 더 큰 순번으로 제안을 한다면, 해당 제안은 수락될 수 있을 것이다. 제안을 버리고, 더 높은 순번의 제안을 알게됨을 반복하면서 특별 proposer는 결국 더 높은 제안 순번을 선택하게 될것이다.
만약 이 시스템의 충분한 구성요소들이 (proposer, acceptors, communication of network)가 제대로 동작한다면, liveness는 단 하나의 특별 proposer를 선출함으로써 성립될 수 있다. Fisher, Lynch, Patterson의 유명한 연구결과는 랜덤적이거나 실시간인 - 예를 들어 타임아웃을 활용한, proposer를 선출하는 신뢰성있는 알고리즘을 생성할 수 있다. 하지만, safety는 proposer 선출의 성공 또는 실패와 상관없이 보장된다.

2.5 구현

Paxos 알고리즘은 프로세스들로 이루어진 네트워크를 가정한다. 이 합의 알고리즘에서, 각 프로세스는 proposer, acceptor, learner의 역할을 수행한다. 알고리즘은 특별한 proposer역할을 수행하는 leader로 선출될 수 있고, 또 learner로도 선출될 수 있다. Paxos 합의 알고리즘은 위에서 설명한것과 동일하게, 특별한 알고리즘이 아닌 일반적인 메시지를 주고 받음으로써 수행된다. (응답 메시지는 혼란을 방지하기 위해 제안과 해당 제안 순번으로 태깅된다.) 안정적인 저장장치, 실패를 방지하기 위해, 가 acceptor가 반드시 기억할 수 있는 정보를 저장할 수 있게끔 사용된다. acceptor는 실제 응답을 전송하기 이전에 해당 응답을 안정적인 저장장치에 저장한다.
서술할 나머지들은 어떠한 두 제안도 같은 순번으로 제안되지 않도록 보장하기 위해 사용되는 메커니즘이다. 다른 Proposer들은 순번 서로소 집합(disjoint set, 교집합이 없는) 으로 부터 값을 선택하며, 그래서 두 proposer는 절대로 같은 순번을 제안할 수 없다. 각 proposer 안정적인 저장장치에, 자신이 제안한 가장 높은 순번을 저장하고, 사용하였던 가장 큰 제안 순번보다 더 큰 순번으로 Phase1을 재개한다.

3 상태 머신을 이용한 구현

분산 시스템을 구현하는 가장 쉬운 방법은 중앙 서버로 클라이언트들이 명령을 전송하는 것이다. 서버는 클라이언트의 명령을 연속적으로 수행하는 결정적 상태 머신으로 기술될 수 있다. 상태머신은 현재 상태를 가지고 있다; 명령을 입력으로 가지면서 단계를 수행하고 결과를 내며 새로운 상태를 생산한다. 예를들어, 분산 은행 시스템의 클라이언트는 텔러일 수 있다. 그리고 상태 머신의 상태는 모든 사용자의 계좌 잔액으로 구성될 수 있다. 인출은 상태 머신에게 계좌의 잔액을 줄이는 방식으로 수행될 수 있다. 만약에 잔액이 인출액보다 크다면, 새로운 잔액을 결과물로 내며 수행된다.
단일 중앙서버를 사용한 구현은 서버가 실패하면 실패한다. 그러므로 우리는 서버 셋을 사용하고, 각 서버는 독립적인 상태머신으로 구현된다. 왜냐하면 상태머신은 결정적이며, 모든 서버는 동일한 연속된 인풋에 대해 동일한 상태로 변화될 것이고 동일한 결과를 낼것이기 때문이다. 명령을 발행하는 클라이언트는 임의의 서버에서 나온 결과를 사용할 수 있다.
모든 서버가 상태머신 명령을 동일한 순서로 실행하였음을 보장하기 위해, 우리는 Paxos 합의 알고리즘을 수행하는 독립적인 인스턴스들을 순차적으로 구현한다. 순서대로 i_th 번째 인스턴스에 의해 선출된 값은, i_th 번째 상태머신 명령어가 된다. 각 서버들은 역할을 수행한다. (proposer, acceptor, learner) 지금은, 나는 서버 집합이 고정되어있다고 가정하고, 합의 알고리즘의 모든 인스턴스들은 같은 agent 집합을 사용한다고 가정하자.
일반적인 동작에서, 단일 서버는 리더로 선출되고 합의 알고리즘의 모든 인스턴스에서 특별한 proposer처럼 동작한다. (제안을 발행하는 유일한 proposer) 클라이언트는 표시될 각 연속적인 커맨드를 결정할 리더에게 명령을 보낸다. 만약 리더가 특정 클라이언트의 명령이 135_th 번째 명령이 되기를 결정했다면, 합의 알고리즘에서 135_th 번째 인스턴스에서 값으로 선출하라고 명령한다. 대개 성공할 것이다. 시스템 실패 때문에 실패할 수 있거나,
다른 서버가 자신을 리더라고 생각하여 135_th 명령에 다른 아이디어를 낼 수도 있다. 그러나 합의 알고리즘은 최대 한 명령어만 135_th 으로 선출될 수 있게끔 한다.
이 동작을 최적화 하기위해서, paxos 합의 알고리즘은, phase 2까지는 제안된 값이 선출되지 않는다. proposer의 phase1 알고리즘을 완료하면, 제안될 값이 결정되거나 또는 proposer가 다른 값을 제안하기도 함을 기억하라.
나는 Paxos 상태 머신 구현이 일반적인 작업을 통해 어떻게 동작하는지 보여줄것이다. 그 후에, 어떤게 잘못될 수 있는지 도 보여줄 것이다. 나는 이전 리더가 실패하고 새 리더가 선출 될 때 어떤일이 발생하는지 보여줄 것이다. (시스템 시작은 어떠한 명령도 제안되지 않은 특별한 케이스이다)
새 리더가 선출되면, 합의 알고리즘의 모든 인스턴스에서 learner이기에, 이미 선출된 대부분의 명령들을 알아야한다. 명령 1-134, 138, 그리고 139을 알고있다고 하자. 즉, 합의 알고리즘에서 값이 다음 인스턴스 1-134, 138, 139에서 선출되었다고 하자. (나중에 우리는 이런 명령의 갭이 어떻게 발생하는지 알아볼것이다.) 그리고 135-137와 139보다 큰 모든 인스턴스는 Phase1을 실행한다. (이게 어떻게 동작하는지 아래에 기술한다.) 이 실행들의 결과가 인스턴스 135와 140에서 어떤값이 선출되는지 결정한다고 가정하자, 그러나 제안된 값은 모든 인스턴스에서 제약사항 없이 남겨두어라. 리더는 인스턴스 135와 140에서 phase2를 실행하고, 135와 140의 명령을 고른다.
리더는, 다른 서버들이 리더가 아는 모든 명령에 대해 아는 것 처럼, 1-135까지 명령을 실행할 수 있다. 그러나 138-140까지의 명령은 실행하지 못한다. 그 명령을 알지만, 136과 137의 명령이 선출되지 않았기 떄문이다. 리더는 클라이언트가 다음으로 요청한 두 명령을 136과 137 명령으로 사용할 수 있다. 그 대신, 우리는 이 갭을 즉시 상태를 변경하지 않은 특별 "no-op" 명령으로 136과 137로 제안하기로 하자. (합의 알고리즘의 인스턴스 136과 137이 phase2를 실행함으로써 수행된다.) 이 no-op 명령이 선출되면, 138-140 명령이 실행될 수 있다.
명령 1-140은 이제 선출되었다. 그리고 리더는 합의알고리즘에서 140보다 큰 모든 인스턴스에서 phase1을 실행하였다. 그리고 그 인스턴스들은 phase2에서 임의의 값을 선출할 수 있다. 클라이언트 요청에 의해 다음 명령을 141번으로 지정할 수 있고, 합의 알고리즘의 141번 인스턴스의 phase2를 제안할 수 있다. 그 다음에는 142번 명령을 받는 다음 클라이언트 명령을 제안할 수 있다.
리더는 제안된 141번 명령이 선출되기를 알기전 까지 142번 명령을 제안할 수 있다. 141번 명령을 제안하며 보낸 모든 메시지가 유실될 수 있으며, 다른 어떤 서버도 141번에 무엇이 제안되었는지 알기전에 142번 명령이 선출될 수 있다. 리더가 phase2 메시지에 대한 예상 응답을 받지 못하면, 그 메시지를 재전송한다. 모든것이 잘된다면, 그 명령은 선출될 것이다. 하지만 리더가 그 전에 실패하면, 선택된 연속적인 명령들에 갭이 생길 수 있다. 일반적으로 리더가 a개 만큼 앞서갈 수 있다고 하자. 즉, 1부터 i까지 명령이 선택된 이후, i+1부터 i+a까지 제안할 수 있다고 하자. 그러면 최대 a-1개의 공백이 발생할 수 있다.
새로 선출된 리더는 합의 알고리즘의 무한히 많은 인스턴스에 대해 phase 1을 수행한다. 위 시나리오에서는 135-137번과 139번보다 큰 모든 인스턴스에 대해 수행한다. 모든 인스턴스에 대해 동일한 Proposal number를 사용하면,다른 서버들에게 비교적 짧은 하나의 메시지를 보내는 것만으로도 이를 수행할 수 있다. phase1 에서 acceptor는 단순한 OK이상의 응답을 하는 경우는, 이미 어떤 proposer로 부터 phase2 메시지를 받은 경우뿐이다. (이 시나리오에서는 그런 경우가 135번과 140번 인스턴스뿐이었다.) 따라서 acceptor로 동작하는 서버는 모든 인스턴스에 대해 하나의 비교적 짧은 메시지로 응답할 수 있다. 따라서 무한히 많은 인스턴스에 대해 phase1을 수행하는 것은 전혀 문제가 되지 않는다.
리더의 실패와 새로운 리더의 선출은 드문 이벤트이므로, 상태 머신 명령을 실행하는 데 드는 실질적인 비용-즉, 그 명령/값에 대해 합의를 이루는 비용-은 합의 알고리즘 phase2를 실행하는 비용과 같다. 고장이 존재하는 환경에서 합의를 달성하는 어떤 알고리즘과 비교해도, Paxos 합의 알고리즘의 Phase2는 가능한한 최소 비용을 가진다는 것을 볼 수 있다. 따라서 Paxos 알고리즘은 본질적으로 최적이다.
이 시스템의 정상 동작에 대한 논의는, 현재 리더가 실패하고 새로운 리더가 선출되는 짧은 기간을 제외하면 항상 하나의 리더가 존재한다고 가정한다. 비정상적인 상황에서는 리더 선출이 실패할 수도 있다. 어떤 서버도 리더로 동작하지 않으면, 새로운 명령은 제안되지 않는다. 여러 서버가 자신이 리더라고 생각하면, 같은 합의 인스턴스에서 모두 값을 제안할 수 있고, 그로 인해 어떤 값도 선택되지 못 할 수 있다. 그러나 safety 성질은 유지된다. 두 서버가 i_th 번째 상태 머신 명령으로 선택된 값에 대해 서로 다른 값을 갖는 일은 절대 없다. 단일 리더의 선출은 오직 liveness를 보장하기 위해서만 필요하다.
서버 집합이 변경될 수 있다면, 합의 알고리즘의 각 인스턴스를 어떤 서버들이 구현하는지 결정할 방법이 있어야 한다. 이를 수행하는 가장 쉬운 방법은 상태 머신 자체를 통해 하는 것이다. 현재 서버 집합을 상태의 일부로 만들고, 이를 일반적인 상태 머신 명령으로 변경할 수 있다. 리더가 a개 앞서갈 수 있도록 하려면, 합의 알고리즘의 인스턴스 i+a를 실행하는 서버 집합을 i번째 상태 머신 명령을 실행한 이후의 상태에 의해 결정되도록 하면 된다. 이 방법은 임의로 복잡한 재구성 알고리즘을 단순하게 구현할 수 있도록 한다.

Paxos Lecture

basic Paxos exchange:
 proposer        acceptors
     prepare(n) ->
  <- prepare_ok(n, n_a, v_a)
     accept(n, v') ->
  <- accept_ok(n)
     decided(v') ->

definition: server S accepts n/v
  S responded accept_ok to accept(n, v)

definition: n/v is chosen
  a majority of servers accepted n/v

the crucial property:
  if a value was chosen, any subsequent choice must be the same value
    i.e. protocol must not change its mind
    maybe a different proposer &c, but same value!
    this allows us to freely start new rounds after crashes &c
    AND it allows a server to safely execute a chosen command, or reply to client
  tricky b/c "chosen" is system-wide property
    e.g. majority accepts, then proposer crashes
    no server can tell locally that agreement was reached

so:
  proposer doesn't send out value with prepare
  acceptors send back any value they have already accepted
  if there is one, proposer proposes that value
    to avoid changing an existing choice
  if no value already accepted,
    proposer can propose any value (e.g. a client request)
  proposer must get prepare_ok from majority
    to guarantee intersection with any previous majority,
    to guarantee proposer hears of any previously chosen value

proposer(v):
  choose n, unique and higher than any n seen so far
  send prepare(n) to all servers including self
  if prepare_ok(n, n_a, v_a) from majority:
    v' = v_a with highest n_a; choose own v otherwise
    send accept(n, v') to all
    if accept_ok(n) from majority:
      send decided(v') to all <-- 여기서 decide는 어떤 값이 선출되었는지를 알리는 것인데, 논문에서는 leader로 선출된 learner가 다른 learner에게 알려준다고 되어있다.

acceptor state:
  must persist across reboots
  n_p (highest prepare seen) <-- n_p 도 저장장치에 저장한다.
  n_a, v_a (highest accept seen)

acceptor's prepare(n) handler:
  if n > n_p
    n_p = n
    reply prepare_ok(n, n_a, v_a) <-- 여기서 n_a != n_p이다. n_a는 accepted n이기 때문이다. \
    n_p는 prepare요청에서 보인 가장 큰 일 뿐이다.
  else
    reply prepare_reject

acceptor's accept(n, v) handler:
  if n >= n_p
    n_p = n
    n_a = n
    v_a = v
    reply accept_ok(n)
  else
    reply accept_reject

Paxos Pseudo code

        --- Paxos Proposer ---

     1    proposer(v):
     2    while not decided:
     2        choose n, unique and higher than any n seen so far
     3        send prepare(n) to all servers including self
     4        if prepare_ok(n, na, va) from majority:
     5          v' = va with highest na; choose own v otherwise   
     6          send accept(n, v') to all
     7          if accept_ok(n) from majority:
     8            send decided(v') to all


        --- Paxos Acceptor ---

     9    state on each node (persistent):
    10     np     --- highest prepare seen
    11     na, va --- highest accept seen

    12    prepare(n) handler:
    13     if n > np
    14       np = n
    15       reply prepare_ok(n, na, va)
    16   else
    17     reply reject


    18    accept(n, v) handler:
    19     if n >= np
    20       np = n
    21       na = n
    22       va = v
    23       reply accept_ok(n)
    24   else
    25     reply reject

좀 더 시각화 된 것은 아래 영상에서 확인해보자.

https://www.youtube.com/watch?v=s8JqcZtvnsM
여기서 마무리한다!