소개
Paxos는 불안정한 환경에서 합의를 도출해내는 프로토콜의 총제
- 불안정한 환경이란
- 신뢰할 수 없는 프로세서
- 실패할 가능성이 있는 통신
Leslie Lamport가 1989년에 제안
- 이름은 그리스 팍소스 섬에서 사용되었던 가상적인 입법 합의체에서 따온 것
프로세서의 갯수와 메시지 지연의 횟수, 개별 참여자의 활동 수준, 전송된 메시지 갯수, 실패의 종류 간의 다양한 트레이드 오프를 포함함
어떤 결정적인(deterministic) 장애허용 합의 시스템도 비동기 네트워크에서의 진행을 보장할 수 없음에도, Paxos는 안전을 보장하고 진행을 막을 수 있는 조건들이 유발되기 어렵다.
일부 레플리카가 응답하지 않을 때에도 영구적으로 제외시키거나 새로운 레플리카를 추가함으로써 진행이 이뤄지도록 시도하려고 함
가정
- 프로세서
- 임의의 속도로 동작함
- 실패를 경험할 수 있음
- 복구 후에 재참가할 수 있음
- 서로 공모하거나 거짓말하거나 프로토콜을 전복하려고 시도하지 않음
- 네트워크
- 다른 프로세서로 메시지를 보낼 수 있음
- 메시지는 비동기적으로 전송되고 배달이 임의로 지연될 수 있음
- 메시지는 분실되거나 순서가 뒤집히거나 복제될 수 있음
- 메시지는 손상없이 전송됨
- 프로세서의 갯수
- 합의 알고리즘에서는 보통 2F+1개의 프로세서를 가정함 (F개만큼이 동시에 실패했다고 가정했을 때)
- F개가 실패했을 때에도 진행 가능함 (실패한 프로세스 갯수보다 많이 살아남아 있으면)
역할
- 고객 client: 요청을 발행하고 응답을 기다림
- 수용자 acceptor(voter): 정족수(quorum)에 해당하는 그룹으로서 프로토콜을 장애를 감내하는 수준으로 기억하는 것을 담당함. 수용자 간에는 메시지가 공유되는 것이 보장됨
- 제안자 proposer: 고객의 변호인 역할. 합의가 진행되도록 조정하고 수용자들이 고객의 요청에 동의하도록 설득함
- 학습자 learner: 프로토콜의 복제 요소로 행동함. 합의가 이뤄지면 학습자가 고객에게 응답을 보내든가 하는 식으로 어떤 조치를 취함.
- 지도자 leader: 제안자 중에서 합의가 진행되도록 하나를 골라서 지도자로 정함. 복수의 지도자가 존재하면 프로토콜이 잠시 멈출 수 있음
정족수
- 살아있는 프로세서들이 결과에 대한 지식을 유지하고 있다고 보장하는 최소 프로세서들의 수
- 팍소스의 안전 특성(safety property)임.
- 엄밀한 정의: 수용자들의 부분집합으로서 임의의 두 부분집합이 최소 한 개 이상의 요소를 공유해야 함
- 또는 가중치가 주어져 있다면 수용자 전체의 가중치 합의 절반보다 큰 가중치 합을 가지는 부분집합으로 정의됨
예) 수용자 집합이 {A, B, C, D}라면, 정족수는 {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}가 가능하지만, {A, B}, {B, C}, {C, D}, {A, D}, {B, D}, {A, C}는 정족수가 아님 (와 {C, D}는 교집합이 {}이므로)
안전 및 활기(liveness) 특성
- 안전을 보장하기 위해 항상 보장되는 3가지 특성
- 비 사소성 non-triviality: 제안된 값만 학습될 수 있음
- 안전 safety: 최대 하나의 값만 학습될 수 있음
- 활기 liveness: C;L 값 C 가 제안되었다면 최종적으로 학습자 L은 어떤 값을 학습하게 됨 (충분한 프로세서가 장애없이 남아있다면)
전형적인 배치
- 대부분의 팍소스 배치에서 참여하는 프로세스 각각은 3가지 역할을 맡음. 제안자, 수용자, 학습자
- 이를 통해 정확도를 희생하지 않으면서 메시지 복잡도를 크게 낮춤
- 고객이 지도자에게 명령을 보내고, 지도자는 명령을 받아서 번호를 부여하고 수용자들에게 메시지를 전송함으로써 해당 번호의 합의 알고리즘 인스턴스를 시작함
- 역할을 병합함으로써 프로토콜은 효율적인 고객-지도자-레플리카 스타일 배치(전형적인 DB 공동체)로 접힘
- 병합된 역할을 가진 구현을 포함해서 팍소스 프로토콜은 안전 속성을 보장함
(미완성)