팩소스 (컴퓨터 과학)

**팩소스**(Paxos)는 신뢰할 수 없는 프로세서들의 네트워크에서 합의 문제를 해결하기 위한 프로토콜 그룹이다. 합의 문제는 구성원이나 구성원 간의 통신 매체에 장애가 발생할 수 있는 경우 어려워진다. 합의 프로토콜은 레슬리 램포트 에 의해 제안되고 프레드 슈나이더에 의해 검증된 분산 컴퓨팅을 위한 상태 기계 접근법 기초이다. 상태 기계 접근법은 알고리즘을 장애 허용 분산 시스템에서 구현되도록 변환하는 기술이다. 애드혹 기법은 예상치 못한 중요한 실패 케이스를 남길 수 있다. 램포트와 그의 동료들에 의해 제안된 원칙적인 방법은 모든 경우가 안전하게 처리되는 것을 보장한다. 팩소스 프로토콜은 1989년에 처음으로 공개되었으며 그리스의 팩소스 섬에서 가상의 입법 합의 시스템에 사용된 후 이름지어졌다. 이후에 1998년에 저널 기사로 게재되었다. 팩소스 계열 프로토콜은 프로세서 수, 합의 값 (agreed value), 합의 값 학습 전까지의 메시지 지연, 개별 참여자의 활동 수준, 메시지 전송 횟수, 실패 종류 등을 트레이드 오프하는 것을 포함한다. Fischer, Lynch와 Paterson의 논문에 따르면 결정적 장애 허용 합의 프로토콜이 비동기 네트워크에선 진행을 보장하진 않지만, 팩소스는 안정성(consistency)을 보장하며 진행을 방해할 수 있는 조건이 발생하기 어렵다. 팩소스는 일반적으로 내구성이 요구되는 곳(예 : 파일 또는 데이터 베이스 복제하는 경우)에 쓰인다. 팩소스 프로토콜은 일정 수 이하의 복제본이 응답하지 않는 동안에도 진행을 시도한다. 또한 영구적으로 실패한 복제본을 제거하거나 새로운 복제본을 추가하는 메커니즘도 있다.
# 역사
이 주제는 팩소스 프로토콜보다 오래되었다. 1988년에 Lynch, Dwork와 Stockmeyer는 일반적인 "부분 동기화" 계열 시스템에서 합의의 해결 가능성을 시연했다.doi=10.1145/42282.42283 팩소스는 분산 트랜잭션이라는 맥락에서 1988년 Oki와 Liskov가 발표한 viewstamped replication에서 협의를 위해 쓰인 프로토콜과 매우 유사하다. 이러한 선행연구에도 불구하고, 팩소스는 우아한 형식주의를 제안했고, 장애허용 분산 합의 프로토콜을 위한 안전성 증명을 가장 먼저 포함했다.
# 전제
팩소스를 쉽게 설명하기 위해, 다음과 같은 전제와 정의를 분명하게 명시한다. 적용 가능성을 확대하는 기술은 문헌에 알려져 있으며 이 문서에서 다루지 않는다.
## 프로세서
* 프로세서는 임의의 속도로 동작한다. * 프로세서는 실패할 수도 있다. * 안정적인 저장소와 함께 하는 프로세서는 실패한 이후 프로토콜에 다시 참여할 수 있다 (충돌-복구 실패 모델을 따른다). * 프로세서는 담합, 거짓말, 또는 프로토콜을 파괴하려는 시도를 하지 않는다. (즉, 비잔틴 오류가 발생하지 않는다. 프로세서의 임의/악성 행위 장애에 의해 생기는 장애 허용에 대한 해법은 비잔틴 팩소스을 보시오.)
## 네트워크
* 프로세서는 다른 프로세서로 메시지를 보낼 수 있다. * 메시지는 비동기적으로 전송되고 배달까지 임의로 길어질 수 있다. * 메시지가 손실되거나 순서가 변경 또는 중복될 수 있다. * 메시지는 훼손 없이 배달된다. (즉, 비잔틴 오류가 발생하지 않는다. 메시지 채널 내의 임의/악의적 행위로 인한 오염된 메시지에 대한 해법은 비잔틴 팩소스를 보시오.)
## 프로세서 수
:일반적으로, 합의 알고리즘은 프로세서를 이용하여 임의의 프로세서가 동시에 고장나더라도 진행할 수 있다: 즉, 비결함 프로세스 수가 결함 프로세스 수보다 반드시 많아야한다. 그러나 바꿔말하자면 *F *개보다 많은 실패가 동시에 일어나지 않는 이상 유지되는 프로토콜로 쓰일 수 있다.
## 역할
:팩소스는 프로세서의 행동을 프로토콜 상의 그들의 역할(클라이언트, 수락자, 제안자, 학습자, 리더)에 따라 설명한다. 일반적인 구현에서 단일 프로세서는 하나 이상의 역할을 동시에 수행한다. 이것은 프로토콜의 정확성에 영향을 미치지 않는다. (일반적으로 프로토콜 내 메시지 지연이나 횟수를 향상시키기 위해 역할을 결합한다.) :; 클라이언트 :: 클라이언트는 *요청* 을 분산 시스템에 게시하고, *응답*을 기다린다. 분산 파일 서버 안에 있는 파일 쓰기 요청을 예로 들 수 있다. :; 수락자(유권자) :: 수락자는 프로토콜의 장애 허용 "메모리"로 동작한다. 그룹 내 모인 수락자는 쿼럼이라고 불린다. 수락자에게 보내진 메시지는 반드시 수락자들의 쿼럼에 보내져야한다. 쿼럼의 수락자로 받은 복사본 외 수락자로부터 받은 메시지는 무시된다. :; 제안자 :: 제안자는 클라이언트를 대변하며 수락자에게 동의하도록 설득을 시도하고 옹호한 클라이언트 요청을 설득하고 충돌이 발생할 경우 프로토콜을 진전시키기 위해 중재자처럼 행동한다. :; 학습자 :: 학습자는 프로토콜을 위한 응답 요소로 행동한다. 클라이언트의 요청이 수락자에 의해 동의되면 학습자는 움직인다 (즉, 요청을 실행하고 클라이언트에게 응답을 보낸다). 처리의 가용성을 높이기 위해 추가적인 학습자를 추가할 수 있다. :; 리더 :: 팩소스는 진행을 위해 식별 가능한 제안자(리더)를 필요로 한다. 많은 프로세스가 자신이 리더라고 믿을 수 있지만, 프로토콜은 그들 중 하나가 선택될 때만 진행을 보장한다. 만약 두 프로세스가 그들이 리더라고 믿는다면, 그들은 지속적으로 충돌하는 업데이트를 제안하여 프로토콜을 지연시킬 수 있다. 하지만 이 경우에도 안전성은 유지된다.
## 쿼럼
:쿼럼은 적어도 일부 살아남은 프로세서가 결과에 대한 정보를 유지하는 것을 보장하는 것으로 팩소스의 안전성을 보여준다. :쿼럼은 수락자의 과반수가 참여한 집단으로 정의된다. 예를 들어, 다음과 같은 수락자 집합 {A,B,C,D}가 주어졌을 때, 주요 Quorum은 적어도 수락자 셋을 포함해야한다. 일반적으로 각 수락자의 가중치가 다를 수 있으며, 이런 경우 쿼럼은 전체 수락자의 가중치의 절반보다 큰 가중치를 가진 수락자들의 집합으로 정의될 수 있다.
## 선택
팩소스에서 리더들은 서로 충돌하는 값 들 중에서 선택을 하여야한다. 값들이 충돌할 경우, 리더는 반드시 최근 라운드로부터 하나의 값을 선택하여야한다. 프로토콜은 어떤 값이 반드시 선택되어야하는지 정하지 않으며 선택에 상관 없이 정확성을 보장한다. 한편 진행을 방해하기 위한 선택도 가능하다. 일반적으로 선택 함수는 최근 라운드에서 가장 다수인 값을 선택한다.
# 안전성과 생존성 속성
안정성 보장을 하기 위해서 팩소스는 3가지 안전성 속성을 정의하고 실패 패턴과 관계 없이 항상 이 속성들을 보유한다: ; 유효성 (또는 비자명성) : 제안된 값만이 선택 받고 학습될 수 있다. ; 일치 (또는 일관성, 안전성) : 단 하나의 값만이 학습될 수 있다. 즉, 다른 두 학습자는 서로 다른 값을 배울 수 없다. ; 종결 (또는 생존성) : 충분한 프로세서가 정상 작동 중일 때 어떤 값이 제안되면 학습자는 결국 어떤 값을 학습한다.
# 일반적인 적용법
대부분의 팩소스 적용법에선 각 참여자가 3가지 역할(제안자, 수락자, 학습자)로 나눠 동작한다. 아래 방법은 정확성을 희생시키지 않으면서 메시지 복잡성을 크게 줄인다.: *팩소스에서는 클라이언트가 명령을 리더에게 보낸다. 정상 동작 중엔, 리더는 클라이언트의 명령을 받아 새 명령 번호 i를 할당한 다음 수락자 프로세스 집합에 메시지를 보내 i번째 합의 알고리즘의 인스턴스를 시작한다.*" 역할을 병합함으로써 팩소스 프로토콜은 데이터베이스 커뮤니티의 전형적인 클라이언트-마스터-복제본 스타일 배포로 "축소"된다. 이러한 팩소스 프로토콜들의 이점은 역할을 병합하여 구현하더라도 안정성을 보장한다는 것이다. 일반적인 구현의 메시지 흐름은 다중 팩소스에서 다룬다.
# 베이직 팩소스
이 프로토콜은 팩소스 계열 중 가장 단순하며 일반적으로 구현되는 프로토콜이 아니다. 베이직 팩소스 프로토콜의 각 "인스턴스" (또는 "실행")은 하나의 출력 값을 결정한다. 이 프로토콜은 여러 라운드에 걸쳐 진행되며 성공적인 라운드는 2단계(학습을 포함할 경우 3단계)를 가진다.
## 1 단계
이 단계에서 제안자는 수락자로부터 제안 번호를 승인 받는다.
### 단계 1a: *준비 (Prepare)*
: **제안자**(또는 **리더**)는 제안 번호로 쓰기 위한 숫자 *N* 을 선택한다. 숫자 *N* 은 반드시 이전의 제안 번호들보다 커야한다. 제안자는 *N* 을 포함한 *준비* 요청을 **수락자**들의 **쿼럼**에 보낸다. 제안자는 수락자들의 쿼럼과 통신할 수 없을 경우 팩소스를 초기화할 수 없다.
### 단계 1b: *약속 (Promise)*
: **수락자들**은 **제안자**로부터 *준비* 요청을 기다린다. 만약 수락자가 *준비* 요청을 받았을 경우, 수락자는 반드시 받은 *준비* 요청의 식별 번호 *N*을 확인하여야한다. 다음과 같은 두 가지 경우가 있다. ::* *N* 이 이전에 제안자들로부터 수락자가 받은 어떤 제안 번호들보다 높은 경우, :::수락자는 제안자에게 n보다 크지않은 제안 번호(더 오래된 제안 번호)를 허용하지 않겠다는 *약속*으로 응답한다. 이 인스턴스에서 수락자가 제안을 수락한 적이 있을 경우, 이전에 수락한 제안 번호 *M* 과 대응하는 승인된 값 *W*는 제안자에 대한 응답에 반드시 포함되어야 한다. ::* *N* 이 이전에 제안자로부터 수락자가 받은 제안 번호보다 작거나 같은 경우, :::수락자는 받은 요청을 무시할 수 있다. 응답하지 않아도 팩소스는 동작하나 최적화를 위해 제안 번호 n으로 합의를 만들려는 시도를 멈추도록 거절 (*Nack*) 응답을 보내 제안자에게 알려주는 것이 좋다.
## 2 단계
이 단계에서 제안자는 수락자에게 제안 수락을 요청한다.
### 단계 2a:*수락 (Accept)*
: 만약 제안자가 수락자들의 쿼럼으로부터 충분한 *약속*을 받은 경우, *수락* 요청에 제안 값 *V*를 **선택**해야한다. 만약 수락자로부터 이전에 승인된 값을 받았다면 제안자는 반드시 *V* 값을 승인된 값 중에서 선택해야한다. 전달 받은 승인된 값이 없다면 제안자는 원하는 값을 *V*로 선택할 수 있다. : 제안자는 제안에 선택한 값 *V*와 제안 번호 *N* (이전에 수락자에게 보낸 준비 메시지에 포함된 것과 같은)을 포함한 *수락* 메시지 *(N, V)*를 수락자들의 쿼럼에 보낼 수 있다. : 이 *수락*은 "제안 수락 **요청**"으로 해석되어야한다.
### 단계 2b:*수락됨 (Accepted)*
: 만약 수락자가 제안자로부터 *수락* 메시지 *(N, V)*를 받으면, 수락자는 제안 번호 *N*이 마지막으로 약속한 제안 번호일 경우에만 *수락* 메시지를 받아들여야한다. ::* *N*이 마지막으로 약속한 제안 번호가 맞을 경우, ::: 수락자는 값 *V*를 수락해야하며, *수락됨* 메시지를 제안자와 모든 학습자에게 보내야한다. ::* *N*이 마지막으로 약속한 제안 번호가 아닐 경우, ::: 수락자는 받은 메시지를 무시할 수 있다. 그러나 다음 라운드가 실행될 수 있도록 거절 (*Nack*) 응답을 보내 제안자에게 알려주는 것이 좋다.
## 라운드가 실패할 경우
: 여러 제안자가 충돌하는 준비 메시지를 보낼 때 또는 제안자가 쿼럼으로부터 응답( ***약속*** 또는 ***수락됨*** )을 받지 못하였을 때 라운드는 실패한다. 이러한 경우 다른 라운드는 반드시 더 높은 제안 번호로 시작해야한다.
## 이미지로 나타낸 베이직 팩소스의 메시지 흐름
다음 다이어그램들은 베이직 팩소스 프로토콜을 적용한 몇 가지 사례/상황을 나타낸다. 몇몇 사례는 베이직 팩소스 프로토콜이 분산 시스템의 특정 (중복) 구성 요소의 오류에 어떻게 대처하는지 보여준다.
### 실패가 없는 베이직 팩소스
아래 다이어그램에는 클라이언트 하나, 제안자 하나, 수락자 셋(즉, Quorum 크기가 3이다), 학습자 둘이 있다. 이 다이어그램은 첫 번째 라운드의 성공을 나타낸다 (즉, 네트워크에서 프로세스가 실패하지 않음).

Client   Proposer     Acceptor     Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| ||->|->| | | Accept!(1,V)
| ||->| Accepted(1,V)
|| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| | | | ! | | !! FAIL !!
| ||->| | | Accept!(1,V)
| ||->| Accepted(1,V)
|| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| ||->|->| | | Accept!(1,V)
| ||->| Accepted(1,V)
| | | | | | ! !! FAIL !!
|| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| || | | | | Accept!(1,V)
| ! | | | | |
| | | | | | | !! NEW LEADER !!
| X--------->|->|->| | | Prepare(2)
| ||->|->| | | Accept!(2,V)
| ||->| Accepted(2,V)
|| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| ||->|->| | | Prepare(2)
| ||->|->| | | Prepare(2)
| ||->|->| | | Prepare(3)
| ||->|->| | | Accept!(2,Va)
| | ||->|->| | | Prepare(4)
| | ||->|->| | | Accept!(3,Vb)
| || | | | | | Request
| X--------->|->|->| | | Prepare(N)
| ||->|->| | | Accept!(N,I,V)
| ||->| Accepted(N,I,V)
|| | | | | | Request
| X--------->|->|->| | | Accept!(N,I+1,W)
| ||->| Accepted(N,I+1,W)
|| | | Request
| X->|->| Prepare(N)
| ||->| Accept!(N, I, Vn)
| X<>X<>X Accepted(N, I)
|| | | Request
| X->|->| Accept!(N,I+1,W)
| X<>X<>X Accepted(N,I+1)
||->|->|->| | | Any(N,I,Recovery)
| | | | | | | |
X------------------->|->|->|->| | | Accept!(N,I,W)
| ||->| Accepted(N,I,W)
||->|----->|->| Accepted(N,I,V)
| | ||->| Accepted(N,I,W)
| | | | | | | | |
| | | | | | | | | !! Detect collision & recover
| | X------->|->|->|->| | | Accept!(N+1,I,W)
| | ||->| Accepted(N+1,I,W)
||->|->|->| | | Any(N,I,Recovery)
| | | | | | | | |
| | | | | | | | | !! Concurrent conflicting proposals
| | | | | | | | | !! received in different order
| | | | | | | | | !! by the Acceptors
| X--------------?|-?|-?|-?| | | Accept!(N,I,V)
X-----------------?|-?|-?|-?| | | Accept!(N,I,W)
| | | | | | | | |
| | | | | | | | | !! Acceptors disagree on value
| | ||->|----->|->| Accepted(N,I,V)
| | ||->| Accepted(N,I,W)
| | | | | | | | |
| | | | | | | | | !! Detect collision & recover
| | ||->| Accepted(N+1,I,W)
||->|->| Any(N,I,Recovery)
| | | | | |
| | | | | | !! Concurrent conflicting proposals
| | | | | | !! received in different order
| | | | | | !! by the Servers
| X--------?|-?|-?|-?| Accept!(N,I,V)
X-----------?|-?|-?|-?| Accept!(N,I,W)
| | | | | |
| | | | | | !! Servers disagree on value
| | X<>X->|->| Accepted(N,I,V)
| | |X Accepted(N,I,W)
| | | | | |
| | | | | | !! Detect collision & recover
| | X<>X<>X<>X Accepted(N+1,I,W)
|| | | | | | Request
| X--------->|->|->| | | Accept!(N,I,V)
| | X<>X<>X | | Verify(N,I,V) - BROADCAST
| ||->| Accepted(N,V)
||->|->| | | Accept!(N,I,V)
| X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST
||->|->! | | Accept!(N,I,V)
| X<>X<>X------>|->| Accepted(N,I,{V,W}) - BROADCAST
| | | ! | | !! Learners receive 2 different commands
| | | ! | | !! Correct Acceptors notice error and choose
| X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST
|<-------------------X--X Response(V)
| | | ! | |