최상의 답변
이 문서는 놀랍도록 명확한 설명과 증거를 제공합니다. http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
여기에 명확한 요약을 제공하겠습니다.
Paxos 알고리즘은 일부 피어가 값에 대해 동의하는 것입니다. Paxos는 한 피어가 일부 값이 과반수에 의해 합의되었다고 믿는 경우 다수가
절대 다른 값에 동의하지 않습니다. 프로토콜은 모든 계약이 반드시 진행되도록 설계되었습니다. 합의에 대한 향후 시도는 해당 노드 중 하나 이상을 통과해야합니다. 따라서 : 결정에 도달 한 후 제안하는 모든 노드는 다수의 노드와 통신합니다. 프로토콜은 이전의 ag를 학습하도록 보장합니다. 그 다수의 가치에 의존합니다.
작동 방식은 다음과 같습니다.
3 개의 노드 A, B 및 C가 있다고 가정합니다. A는 value “Foo.”
알고리즘은 3 단계로 작동합니다. 각 단계에서 대다수 노드의 확인에 도달해야합니다.
먼저 준비 단계가 있습니다. A 는 준비 요청 을 A, B 및 C에 보냅니다. Paxos는 시퀀스 번호를 사용하여 보장을 달성하십시오. 준비 요청은 노드에게 다음과 같이 약속하도록 요청합니다. “준비 요청에있는 시퀀스 번호보다 작은 시퀀스 번호를 가진 제안은 절대 수락하지 않습니다.” 노드는 이전에 동의 한 값 (있는 경우)으로 응답합니다. (매우 중요합니다) : 노드 A는 가장 높은 시퀀스 번호로 수신 한 값을 제안해야합니다. 이 작업은 이전에 합의 된 값이 보존된다는 보장을 제공합니다.
다음으로 수락 단계가 있습니다. A 는 수락 요청 을 A, B, C에 보냅니다. 수락 요청 상태 : ” foo를 수락합니까? ” 수반되는 시퀀스 번호가 노드가 이전에 약속 한 것보다 낮지 않거나 노드가 이전에 수락 한 요청이면 새 값과 시퀀스 번호를 수락합니다.
노드 A가 수락하면 대부분의 노드에서 값이 결정됩니다. 이번 Paxos 라운드는 다른 값에 동의하지 절대 합니다.
세 번째 단계는 반드시 필요한 것은 아니지만 매우 중요합니다. 프로덕션 화 된 Paxos 구현에서 최적화. A 가 대부분의 수락을받은 후 결정된 메시지를 A, B 및 C. 이러한 메시지는 모든 동료에게 값이 선택되었음을 알리고 결정 프로세스의 끝을 가속화합니다.
이 메시지가 없으면 다른 동료들은 합의에 대해 배울 가치를 제안해야합니다. 준비 단계에서 그들은 “이전에 합의 된 가치를 알게되었습니다. 일단 합의가 이루어지면 노드는 합의를 인식 할 것입니다.
여기에서 몇 가지 주요 문제를 설명했습니다.
- 모든 시퀀스 번호는 단조롭게 증가해야하며 노드별로 고유해야합니다 . 즉, A 와 B 는 모두 시퀀스 번호 k로 메시지를 보낼 수 없습니다. 프로토콜로 전송되는 모든 메시지에는 시퀀스 번호가 포함됩니다. 노드는 확인한 가장 높은 수락 요청과 준비 단계에서 약속 한 가장 높은 값을 추적해야합니다.
- 실패 조건. Paxos 라운드가 실패 할 가능성이 높습니다. 실패 할 경우 한 노드는 단순히 더 높은 시퀀스 번호로 다시 제안을 시도합니다.
- 종료 조건. 내가 설명한 Paxos 버전이 반드시 종료되는 것은 아닙니다. 공식적인 종료 증명을 위해 몇 가지 조정이 필요합니다.
답변
Paxos가 합의를 이루었으므로 분산 데이터베이스에서 쓰기를 그대로 복제하는 데 사용할 수도 있습니다. 그룹의 모든 노드간에 일관된 이벤트 순서를 보장 할 수 있습니다. Chubby by Google은 강력한 일관된 파일을 제공하기 위해 Paxos를 사용합니다. 여기에서 혼란이 발생합니다. 복제에 둘 다 사용할 수있는 경우 뷰 동기화와 paxos 간의 관계는 무엇입니까?
작은 역사 : Lamport는 80 년대 초에 상태 머신 복제 개념을 도입했습니다. 상태 머신 복제는 시스템이 모든 노드에 동일한 순서로 이벤트를 전달하고 결정적으로 처리되어 그룹의 모든 노드에서 일관된 상태를 보장 함을 의미합니다. 그러나이 개념이 도입되었을 때 네트워크가 동기식이라는 것을 포함하여 모든 종류의 가정이 수반되었습니다.따라서 상태 머신 복제는 실용적이지 않은 이론적 도구에 불과했습니다. View synchrony는이 시점에서 도입되었으며 그러한 가정을하지 않음으로써 일관성을 달성하는 것을 목표로했습니다. 목표는 그러한 보증을 제공하는 실용적인 시스템을 갖추는 것이 었습니다.
Paxos의 출판은 뷰 동기화 작업이 진행되는 동안 발생했습니다. Paxos는 복제본이 이제이 합의 알고리즘을 사용하여 클라이언트 요청의 실행 순서에 동의 할 수 있으므로 상태 머신 복제를 달성 할 수 있습니다. Paxos는 동기식 네트워크 나 장애에 대해 어떠한 가정도하지 않았습니다. Paxos는 또한 그룹 멤버십 프로토콜을 제공했습니다. 현재 뷰 싱크로 니와 팍 소스 사이에 남아있는 차이점은 추상화가 공식화되는 방식에만있었습니다. 둘 다 동적 멤버십을 제공하고 유사하게 실패를 처리합니다. 차이점은 실제로 모델에만 있습니다. 강조 할 수있는 몇 가지 차이점은 다음과 같습니다.
- Virtual Synchrony는 Paxos에 비해 간단한 그룹 멤버십 프로토콜을 가지고 있습니다. Virtual Synchrony는 그룹 멤버십을 별도의 서비스로 실행합니다.
- Paxos는 가상 동기화가 차단되는 특정 파티션의 경우 진행될 수 있습니다.
- Virtual Synchrony는 현재의 Paxos보다 빠릅니다.
두 시스템 모두 진화 및 수렴 되었습니다. 현재로서는 둘 사이에 중요한 차이점을 그리는 것이 매우 어렵습니다.
Lalith는 Virtual Synchrony 프로토콜을 명확하게 설명하고 Paxos 또는 다른 모든 합의 변형 이 뷰 동기화에 사용될 수 있음을 올바르게 지적합니다. 합의와는 별도로 Paxos는 Virtual synchrony가 이미 제공하는 그룹 멤버십 및 기타 기능을 제공합니다. 가상 동기화와 Paxos는 모두 동일한 보증을 제공하고 거의 같은시기에 개발되었으므로 가상 동기화의 사양은 합의에 Paxos를 사용하지 않습니다. 그러나 가상 동기화 모델은 완전히 정렬 된 전송 프로토콜 (ABCAST라고도 함)을 사용하여 원자 브로드 캐스트를 달성하고 또 다른 프로토콜을 사용하여 그룹보기를 업데이트하며 이는 합의 변형