팩소스 (컴퓨터 과학)
팩소스(Paxos)는 신뢰할 수 없는 프로세서들의 네트워크에서 합의 문제를 해결하기 위한 프로토콜 그룹이다. 합의 문제는 구성원이나 구성원 간의 통신 매체에 장애가 발생할 수 있는 경우 어려워진다.[1]
합의 프로토콜은 레슬리 램포트[2] 에 의해 제안되고 프레드 슈나이더[3]에 의해 검증된 분산 컴퓨팅을 위한 상태 기계 접근법 기초이다. 상태 기계 접근법은 알고리즘을 장애 허용 분산 시스템에서 구현되도록 변환하는 기술이다. 애드혹 기법은 예상치 못한 중요한 실패 케이스를 남길 수 있다. 램포트와 그의 동료들에 의해 제안된 원칙적인 방법은 모든 경우가 안전하게 처리되는 것을 보장한다.
팩소스 프로토콜은 1989년에 처음으로 공개되었으며 그리스의 팩소스 섬에서 가상의 입법 합의 시스템에 사용된 후 이름지어졌다.[4] 이후에 1998년에 저널 기사로 게재되었다.[5]
팩소스 계열 프로토콜은 프로세서 수, 합의 값 (agreed value), 합의 값 학습 전까지의 메시지 지연, 개별 참여자의 활동 수준, 메시지 전송 횟수, 실패 종류 등을 트레이드 오프하는 것을 포함한다. Fischer, Lynch와 Paterson의 논문[6]에 따르면 결정적 장애 허용 합의 프로토콜이 비동기 네트워크에선 진행을 보장하진 않지만, 팩소스는 안정성(consistency)을 보장하며 진행을 방해할 수 있는 조건이 발생하기 어렵다.
팩소스는 일반적으로 내구성이 요구되는 곳(예 : 파일 또는 데이터 베이스 복제하는 경우)에 쓰인다. 팩소스 프로토콜은 일정 수 이하의 복제본이 응답하지 않는 동안에도 진행을 시도한다. 또한 영구적으로 실패한 복제본을 제거하거나 새로운 복제본을 추가하는 메커니즘도 있다.
역사 편집
이 주제는 팩소스 프로토콜보다 오래되었다. 1988년에 Lynch, Dwork와 Stockmeyer는 일반적인 "부분 동기화" 계열 시스템에서 합의의 해결 가능성을 시연했다.[7] 팩소스는 분산 트랜잭션이라는 맥락에서 1988년 Oki와 Liskov가 발표한 viewstamped replication에서 협의를 위해 쓰인 프로토콜과 매우 유사하다.[8] 이러한 선행연구에도 불구하고, 팩소스는 우아한 형식주의를 제안했고, 장애허용 분산 합의 프로토콜을 위한 안전성 증명을 가장 먼저 포함했다.
전제 편집
팩소스를 쉽게 설명하기 위해, 다음과 같은 전제와 정의를 분명하게 명시한다. 적용 가능성을 확대하는 기술은 문헌에 알려져 있으며 이 문서에서 다루지 않는다.
프로세서 편집
- 프로세서는 임의의 속도로 동작한다.
- 프로세서는 실패할 수도 있다.
- 안정적인 저장소와 함께 하는 프로세서는 실패한 이후 프로토콜에 다시 참여할 수 있다 (충돌-복구 실패 모델을 따른다).
- 프로세서는 담합, 거짓말, 또는 프로토콜을 파괴하려는 시도를 하지 않는다. (즉, 비잔틴 오류가 발생하지 않는다. 프로세서의 임의/악성 행위 장애에 의해 생기는 장애 허용에 대한 해법은 비잔틴 팩소스을 보시오.)
네트워크 편집
- 프로세서는 다른 프로세서로 메시지를 보낼 수 있다.
- 메시지는 비동기적으로 전송되고 배달까지 임의로 길어질 수 있다.
- 메시지가 손실되거나 순서가 변경 또는 중복될 수 있다.
- 메시지는 훼손 없이 배달된다. (즉, 비잔틴 오류가 발생하지 않는다. 메시지 채널 내의 임의/악의적 행위로 인한 오염된 메시지에 대한 해법은 비잔틴 팩소스를 보시오.)
프로세서 수 편집
- 일반적으로, 합의 알고리즘은 프로세서를 이용하여 임의의 프로세서가 동시에 고장나더라도 진행할 수 있다: 즉, 비결함 프로세스 수가 결함 프로세스 수보다 반드시 많아야한다. 그러나 바꿔말하자면 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)
| |<---------X--X--X | | Promise(1,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(1,V)
| |<---------X--X--X------>|->| Accepted(1,V)
|<---------------------------------X--X Response
| | | | | | |
V은 (Va, Vb, Vc) 중 최신 값이다.
베이직 팩소스에서의 오류 사례 편집
가장 간단한 오류 사례는 수락 자의 실패 (수락 자 쿼럼이 살아있을 때)와 중복 된 학습자의 실패이다. 이러한 경우 프로토콜은 "복구"가 필요하지 않다 (즉, 여전히 성공합니다). 아래 그림과 같이 추가 라운드나 메시지가 필요하지 않다.
수락자가 실패했을 때의 베이직 팩소스 편집
다음 다이어그램에서는 수락자 중 하나가 장애를 일으켜 쿼럼 크기가 2가 된다. 이 사례에선 베이직 팩소스 프로토콜은 여전히 성공적으로 동작한다.
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| | | | ! | | !! FAIL !!
| |<---------X--X | | Promise(1,{Va, Vb, null})
| X--------->|->| | | Accept!(1,V)
| |<---------X--X--------->|->| Accepted(1,V)
|<---------------------------------X--X Response
| | | | | |
학습자가 실패했을 때의 베이직 팩소스 편집
다음 사례에서는 학습자 중 하나가 실패하지만 베이직 팩소스 프로토콜은 여전히 성공적으로 동작한다.
Client Proposer Acceptor Learner
| | | | | | |
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(1)
| |<---------X--X--X | | Promise(1,{null,null,null})
| X--------->|->|->| | | Accept!(1,V)
| |<---------X--X--X------>|->| Accepted(1,V)
| | | | | | ! !! FAIL !!
|<---------------------------------X Response
| | | | | |
제안자가 실패했을 때의 베이직 팩소스 편집
이 사례에선 제안자는 값을 제안했지만 동의 받기 전에 실패하였다. 정확하게는 수락 메시지의 중간에서 실패해서 쿼럼 내의 단 하나의 수락자만이 값을 받았다. 그 동안 새 리더가 선출되었다(선출 과정은 생략). 이 사례에서는 두 라운드가 나타나있다.
Client Proposer Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| |<------------X--X--X | | Promise(1,{null, null, null})
| | | | | | |
| | | | | | | !! Leader fails during broadcast !!
| X------------>| | | | | Accept!(1,V)
| ! | | | | |
| | | | | | | !! NEW LEADER !!
| X--------->|->|->| | | Prepare(2)
| |<---------X--X--X | | Promise(2,{V, null, null})
| X--------->|->|->| | | Accept!(2,V)
| |<---------X--X--X------>|->| Accepted(2,V)
|<---------------------------------X--X Response
| | | | | | |
여러 명의 제안자가 충돌 할 때의 베이직 팩소스 편집
가장 복잡한 경우는 여러 명의 제안자가 스스로를 리더라고 믿는 경우이다. 예를 들어 현재의 리더는 실패하고 나중에 복구될 수 있지만 다른 제안자들은 이미 새로운 리더를 다시 선출했다. 복구된 리더는 아직 이것을 알지 못하고 현재 지도자와 충돌하여 한 라운드를 시작하려 한다. 아래 다이어그램에서는 실패한 라운드가 4회 표시되었지만 (다이어그램 하단에 제안 된 것처럼) 더 많은 라운드가 있을 수 있다.
Client Leader Acceptor Learner
| | | | | | |
X----->| | | | | | Request
| X------------>|->|->| | | Prepare(1)
| |<------------X--X--X | | Promise(1,{null,null,null})
| ! | | | | | !! LEADER FAILS
| | | | | | | !! NEW LEADER (knows last number was 1)
| X--------->|->|->| | | Prepare(2)
| |<---------X--X--X | | Promise(2,{null,null,null})
| | | | | | | | !! OLD LEADER recovers
| | | | | | | | !! OLD LEADER tries 2, denied
| X------------>|->|->| | | Prepare(2)
| |<------------X--X--X | | Nack(2)
| | | | | | | | !! OLD LEADER tries 3
| X------------>|->|->| | | Prepare(3)
| |<------------X--X--X | | Promise(3,{null,null,null})
| | | | | | | | !! NEW LEADER proposes, denied
| | X--------->|->|->| | | Accept!(2,Va)
| | |<---------X--X--X | | Nack(3)
| | | | | | | | !! NEW LEADER tries 4
| | X--------->|->|->| | | Prepare(4)
| | |<---------X--X--X | | Promise(4,{null,null,null})
| | | | | | | | !! OLD LEADER proposes, denied
| X------------>|->|->| | | Accept!(3,Vb)
| |<------------X--X--X | | Nack(4)
| | | | | | | | ... and so on ...
멀티 팩소스 편집
팩소스의 일반적인 적용법에서는 연속된 합의 값이 분산 상태 기계에 대한 명령처럼 동작하길 요구한다. 만약 각 명령이 베이직 팩소스 프로토콜의 단일 인스턴스의 결과라면, 상당량의 오버 헤드가 발생한다.
만약 리더가 비교적으로 안정적이면 1단계(제안,약속)은 불필요해진다. 따라서 미래의 프로토콜 인스턴스이 동일한 리더로 진행된다면 1단계를 생략할 수 있다.
이를 생략하기 위해 각 라운드에서 같은 리더에 의해 증가되는 라운드 번호 I를 메시지에 넣는다. 멀티 팩소스는 장애 방지 메시지 횟수를 4번에서 2번으로 줄인다.
이미지로 나타낸 멀티 팩소스의 메시지 흐름 편집
실패가 없는 멀티 팩소스 편집
다음 다이어그램은 첫 리더와 베이직 팩소스의 단일 인스턴스(또는 실행)를 보여준다. 멀티 팩소스는 여러개의 베이직 팩소스 인스턴스로 구성될 수 있다는 것을 기억하라.
Client Proposer Acceptor Learner
| | | | | | | --- First Request ---
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(N)
| |<---------X--X--X | | Promise(N,I,{Va,Vb,Vc})
| X--------->|->|->| | | Accept!(N,I,V)
| |<---------X--X--X------>|->| Accepted(N,I,V)
|<---------------------------------X--X Response
| | | | | | |
V는 Va, Vb, Vc 중 최신 값이다.
1단계가 생략된 멀티 팩소스 편집
이 사례에선 인스턴스들 중 일부분이 같은 리더를 이용하기 때문에 1단계(준비, 약속)은 생략되었다. 리더가 안정적이어야 한다는 것을 기억하라. 리더는 충돌하거나 바뀌어선 안된다.
Client Proposer Acceptor Learner | | | | | | | --- Following Requests --- X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I+1,W) | |<---------X--X--X------>|->| Accepted(N,I+1,W) |<---------------------------------X--X Response | | | | | | |
역할이 붕괴된 멀티 팩소스 편집
일반적인 멀티 팩소스의 적용법은 제안자, 수락자 그리고 학습자 역할을 "서버"로 합친다. 따라서 "클라이언트"와 "서버"만이 남는다. 다음 다이어그램은 제안자, 수락자, 학습자 역할이 "서버"로 합쳐진 베이직 팩소스 프로토콜의 첫 인스턴스를 보여준다.
Client Servers
| | | | --- First Request ---
X-------->| | | Request
| X->|->| Prepare(N)
| |<-X--X Promise(N, I, {Va, Vb})
| X->|->| Accept!(N, I, Vn)
| X<>X<>X Accepted(N, I)
|<--------X | | Response
| | | |
리더가 같은 역할이 붕괴된 멀티 팩소스 편집
이전 베이직 팩소스 프로토콜 인스턴스들과 같은 리더를 쓰는 베이직 팩소스 프로토콜의 인스턴스들 중 일부는 1단계를 생략할 수 있다.
Client Servers X-------->| | | Request | X->|->| Accept!(N,I+1,W) | X<>X<>X Accepted(N,I+1) |<--------X | | Response | | | |
패스트 팩소스 편집
패스트 팩소스는 종단 간 메시지 지연을 줄이기 위해 베이직 팩소스를 일반화한 것이다. 베이직 팩소스에선, 클라이언트의 요청에서 학습까지 3번의 메시지 지연이 발생한다. 패스트 팩소스는 2번의 메시지 지연이 가능한 대신 3f + 1개의 수락자를 요구하며 클라이언트에게 여러 곳에 요청을 보내는 것을 요구한다.
직관적으로 봤을 때, 리더는 제안할 값을 가지고 있지 않으면 클라이언트가 수락자에게 수락 메시지를 직접 보내야한다. 수락자는 베이직 팩소스에서와 같이 리더와 학습자에게 수락됨 메시지를 전달할 것이며 클라이언트에서 학습자까지는 2번의 메시지 지연이 발생한다.
리더는 충돌을 감지했을 때 충돌을 해결하기 위해 새로운 수락 메시지를 보낸다. 이러한 중재된 복원 방법은 클라이언트에서 학습자 사이에서 4번의 메시지 지연을 요구한다.
최종적인 최적화 기법은 리더가 사전에 복구 방법을 지정하여 수락자와 공유하는 것이다. 이 중재가 없는 복원 방법은 수락자들 스스로 복원하는 것을 가능하게 한다. 이 경우 충돌 복원은 3번의 메시지 지연을 발생시킨다. (학습자가 수락자로 동작할 경우 2번의 메시지 지연만 발생한다.)
충돌 없는 패스트 팩소스의 메시지 흐름 편집
Client Leader Acceptor Learner | | | | | | | | | X--------->|->|->|->| | | Any(N,I,Recovery) | | | | | | | | X------------------->|->|->|->| | | Accept!(N,I,W) | |<---------X--X--X--X------>|->| Accepted(N,I,W) |<------------------------------------X--X Response(W) | | | | | | | |
제안이 충돌한 패스트 팩소스의 메시지 흐름 편집
- 중재된 복원에서의 제안 충돌
Client Leader Acceptor Learner | | | | | | | | | | | | | | | | | | | | | | | | | | | !! Concurrent conflicting proposals | | | | | | | | | !! received in different order | | | | | | | | | !! by the Acceptors | X--------------?|-?|-?|-?| | | Accept!(N,I,V) X-----------------?|-?|-?|-?| | | Accept!(N,I,W) | | | | | | | | | | | | | | | | | | !! Acceptors disagree on value | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | | !! Detect collision & recover | | X------->|->|->|->| | | Accept!(N+1,I,W) | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |
- 중재가 없는 복원에서의 제안 충돌
Client Leader Acceptor Learner | | | | | | | | | | | X------->|->|->|->| | | 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 | | |<-------X--X->|->|----->|->| Accepted(N,I,V) | | |<-------|<-|<-X--X----->|->| Accepted(N,I,W) | | | | | | | | | | | | | | | | | | !! Detect collision & recover | | |<-------X--X--X--X----->|->| Accepted(N+1,I,W) |<---------------------------------X--X Response(W) | | | | | | | | |
※ 프로토콜은 누락된 클라이언트의 요청을 어떻게 처리할지 정하지 않는다.
역할이 합쳐진 중재 없는 복원을 사용한 패스트 팩소스의 메시지 흐름 편집
아래의 다이어그램에선 수락자 역할과 학습자 역할을 병합되었다.
Client Servers | | | | | | | | X->|->|->| 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<>X Accepted(N,I,W) | | | | | | | | | | | | !! Detect collision & recover | | X<>X<>X<>X Accepted(N+1,I,W) |<-----------X--X--X--X Response(W) | | | | | |
일반화된 팩소스 편집
일반화된 합의는 분산 상태 기계의 명령과 상태 머신들의 일관성을 위지하기 위해 쓰이는 합의 프로토콜 사이의 관계를 다룬다. 주된 연구는 충돌된 제안이 어떠한 순서로든지 상태 머신에 반영될 수 있을 때의 합의 프로토콜의 최적화를 포함한다. 충돌된 제안의 명령들이 자리 바꿈이 가능한 상태 기계의 명령인 경우이다.
이러한 사례에서 충돌된 명령들은 충돌을 해결하거나 반복 제안, 거절 등에 필요한 지연을 피하기 위해 동시에 수용될 수 있다.
비잔틴 팩소스 편집
팩소스는 거짓을 포함한 메시지 작성, 다른 참여자와 공모, 선택적 비참여 등을 포함한 임의의 실패를 지원하기 위해서 확장될 수 있다. 이러한 유형의 실패는 램포트에 의해 솔루션이 보급된 후 비잔틴 장애라고 불린다.
Castro와 Liskov에 의해 제안된 비잔틴 패소스는 정보를 분배하고 다른 프로세서의 행동을 증명하는 역할을 하는 추가적 메시지 (증명)을 추가하였다.
안정적 상태의 비잔틴 멀티 팩소스 메시지 흐름 편집
Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Accept!(N,I,V) | | X<>X<>X | | Verify(N,I,V) - BROADCAST | |<---------X--X--X------>|->| Accepted(N,V) |<---------------------------------X--X Response(V) | | | | | | |
마틴과 Alvisi에 의해 제안된 패스트 비잔틴 팩소스[9]는 클라이언트가 직접 수락자에 명령을 전달함으로써 지연을 줄인다.
패스트 팩소스가 수락됨 메시지를 학습자들에게만 보낼 때 패스트 비잔틴 팩소스는 모든 수락자와 모든 학습자에게 수락됨 메시지를 보낸다는 것을 기억하라:
안정적 상태의 패스트 비잔틴 멀티 팩소스 메시지 흐름 편집
Client Acceptor Learner | | | | | | X----->|->|->| | | Accept!(N,I,V) | X<>X<>X------>|->| Accepted(N,I,V) - BROADCAST |<-------------------X--X Response(V) | | | | | |
두 프로토콜에서 실패 시나리오는 같다. 각 학습자는 서로 다른 수락자들로부터 F+1개의 동일한 메시지들 받기를 기다린다. 수락자는 정보를 공유하기 때문에 학습자의 상태를 예측할 수 있다. 학습자가 F+1개의 동일한 메시지를 받을 수 없는 경우 정상인 수락자는 합의된 값을 다시 브로드캐스팅할 것이다.
실패가 발생한 패스트 비잔틴 멀티 팩소스 메시지 흐름 편집
Client Acceptor Learner
| | | ! | | !! One Acceptor is faulty
X----->|->|->! | | 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)
| | | ! | |
같이 보기 편집
- Chandra-Toueg 합의 알고리즘
- 상태 기계 접근법
- 래프트 (컴퓨터 과학)
각주 편집
- ↑ Pease, Marshall; Shostak, Robert; Lamport, Leslie (April 1980). “Reaching Agreement in the Presence of Faults”. 《Journal of the Association for Computing Machinery》 27 (2). 2007년 2월 2일에 확인함.
- ↑ Lamport, Leslie (July 1978). “Time, Clocks and the Ordering of Events in a Distributed System”. 《Communications of the ACM》 21 (7): 558–565. doi:10.1145/359545.359563. 2007년 2월 2일에 확인함.
- ↑ Schneider, Fred (1990). “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial” (PDF). 《ACM Computing Surveys》 22: 299. doi:10.1145/98163.98167.
- ↑ Leslie Lamport's history of the paper
- ↑ Lamport, Leslie (May 1998). “The Part-Time Parliament”. 《ACM Transactions on Computer Systems》 16 (2): 133–169. doi:10.1145/279227.279229. 2007년 2월 2일에 확인함.
- ↑ Fischer, M. (April 1985). “Impossibility of distributed consensus with one faulty process”. 《Journal of the ACM》 32 (2): 374–382. doi:10.1145/3149.214121.
- ↑ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (1988년 4월 1일). “Consensus in the presence of partial synchrony”. 《Journal of the ACM》 35 (2). doi:10.1145/42282.42283.
- ↑ Oki, Brian; Liskov, Barbara (1988). 〈Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems〉. 《PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of Distributed Computing》. 8–17쪽. doi:10.1145/62546.62549.
- ↑ Martin, Jean-Philippe; Alvisi, Lorenzo (July 2006). “Fast Byzantine Consensus” (PDF). 《IEEE Transactions on Dependable and Secure Computing》 3 (3): 202–215. doi:10.1109/TDSC.2006.35. 2018년 3월 5일에 확인함.