팩소스 (컴퓨터 과학)팩소스(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] 이러한 선행연구에도 불구하고, 팩소스는 우아한 형식주의를 제안했고, 장애허용 분산 합의 프로토콜을 위한 안전성 증명을 가장 먼저 포함했다. 전제팩소스를 쉽게 설명하기 위해, 다음과 같은 전제와 정의를 분명하게 명시한다. 적용 가능성을 확대하는 기술은 문헌에 알려져 있으며 이 문서에서 다루지 않는다. 프로세서
네트워크
프로세서 수
역할
쿼럼
선택팩소스에서 리더들은 서로 충돌하는 값 들 중에서 선택을 하여야한다. 값들이 충돌할 경우, 리더는 반드시 최근 라운드로부터 하나의 값을 선택하여야한다. 프로토콜은 어떤 값이 반드시 선택되어야하는지 정하지 않으며 선택에 상관 없이 정확성을 보장한다. 한편 진행을 방해하기 위한 선택도 가능하다. 일반적으로 선택 함수는 최근 라운드에서 가장 다수인 값을 선택한다. 안전성과 생존성 속성안정성 보장을 하기 위해서 팩소스는 3가지 안전성 속성을 정의하고 실패 패턴과 관계 없이 항상 이 속성들을 보유한다:
일반적인 적용법대부분의 팩소스 적용법에선 각 참여자가 3가지 역할(제안자, 수락자, 학습자)로 나눠 동작한다. 아래 방법은 정확성을 희생시키지 않으면서 메시지 복잡성을 크게 줄인다.:
역할을 병합함으로써 팩소스 프로토콜은 데이터베이스 커뮤니티의 전형적인 클라이언트-마스터-복제본 스타일 배포로 "축소"된다. 이러한 팩소스 프로토콜들의 이점은 역할을 병합하여 구현하더라도 안정성을 보장한다는 것이다. 일반적인 구현의 메시지 흐름은 다중 팩소스에서 다룬다. 베이직 팩소스이 프로토콜은 팩소스 계열 중 가장 단순하며 일반적으로 구현되는 프로토콜이 아니다. 베이직 팩소스 프로토콜의 각 "인스턴스" (또는 "실행")은 하나의 출력 값을 결정한다. 이 프로토콜은 여러 라운드에 걸쳐 진행되며 성공적인 라운드는 2단계(학습을 포함할 경우 3단계)를 가진다. 1 단계이 단계에서 제안자는 수락자로부터 제안 번호를 승인 받는다. 단계 1a: 준비 (Prepare)
단계 1b: 약속 (Promise)
2 단계이 단계에서 제안자는 수락자에게 제안 수락을 요청한다. 단계 2a:수락 (Accept)
단계 2b:수락됨 (Accepted)
라운드가 실패할 경우
이미지로 나타낸 베이직 팩소스의 메시지 흐름다음 다이어그램들은 베이직 팩소스 프로토콜을 적용한 몇 가지 사례/상황을 나타낸다. 몇몇 사례는 베이직 팩소스 프로토콜이 분산 시스템의 특정 (중복) 구성 요소의 오류에 어떻게 대처하는지 보여준다. 실패가 없는 베이직 팩소스아래 다이어그램에는 클라이언트 하나, 제안자 하나, 수락자 셋(즉, 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)
| | | ! | |
같이 보기
각주
|
Portal di Ensiklopedia Dunia
