Gbcast

Gbcast

Gbcast(그룹 브로드캐스트라고도 함)는 크래시 [1][2][3]장애가 발생한 머신의 네트워크 내의 리시버 그룹에서 순서 있는 폴트 톨러런스(모두 또는 없음) 메시지 전달을 제공하는 신뢰성 높은 멀티캐스트프로토콜입니다이 프로토콜은 신뢰할 수 없는 프로세서의 네트워크에서 컨센서스를 해결할 수 있으며 상태 시스템 [4][5]복제를 구현하는 데 사용할 수 있습니다.Gbcast는 독립 실행형 방식으로 사용할 수도 있고 가상 동기 실행 모델을 지원할 수도 있습니다. 이 경우 Gbcast는 일반적으로 그룹 구성원 관리를 위해 사용되는 반면 다른 더 빠른 프로토콜은 일상적인 통신 작업에 선호됩니다.

역사

1985년에 [1]도입된 Gbcast는 동적으로 재구성 가능한 멤버십을 가진 상태 머신 복제를 구현하기 위해 널리 배포된 최초의 신뢰할 수 있는 멀티캐스트 프로토콜이었다.이전 작업에서 이 문제는 이론적으로 다양한 모델에서 해결되었지만, Gbcast는 스테이트 머신 내에서 복제된 데이터를 갱신하는 데 사용되는 것과 동일한 멀티 캐스트를 사용하여 그룹 멤버쉽을 동적으로 재구성할 수 있음을 보여줌으로써 혁신적이었습니다.이 멀티캐스트는 bei뿐만 아니라 멤버들도 자유롭게 가입 및 탈퇴할 수 있도록 진화합니다.ng는 장애 발생 시 삭제됩니다.이 기능은 가입 멤버 초기화에 사용되는 상태 전송 메커니즘과 함께 가상 동기 프로세스 그룹 실행 모델의 기초를 나타냅니다.

스테이트 머신 레플리케이션이라는 용어는 레슬리[4] 램포트에 의해 처음 제안되었으며 Fred B에 의해 작성된 설문지가 발표된 후 널리 채택되었습니다. 슈나이더.[6]이 모델에는 일련의 명령어를 복제품에 폴트 톨러런스 방식으로 적용할 수 있도록 결정론적 객체(상태 머신)가 복제되는 시스템이 포함됩니다.재구성 가능한 상태 시스템은 멤버 자격을 변경하여 새 멤버를 추가하거나 [7]이전 멤버를 제거할 수 있습니다.Gbcast 및 Lamport에서 널리 인용되고 있는 스테이트 머신 복제 프로토콜인 Paxos를 포함하여 [5]일부 스테이트 머신 프로토콜은 이러한 상황이 발생했을 때 재구성할 필요 없이 현재 멤버의 서브셋을 일시적으로 사용할 수 없게 할 수 있습니다.

스테이트 머신의 레플리케이션은 분산된 컨센서스 [8]문제와 밀접하게 관련되어 있습니다.분산된 컨센서스 문제에서는 프로세스의 집합이 선거의 승자와 같은 몇 가지 결정 결과에 대해 합의해야 합니다.특히, 상태 머신 복제 문제에 대한 어떠한 해결책도 분산된 합의를 해결할 수 있다는 것을 보여줄 수 있습니다.그 결과 분산된 컨센서스에 대한 불가능 결과가 상태 시스템 복제 문제에 대한 해결책에 적용됩니다.이 발견의 함축적 의미는 라이브에서 논의된다.

Gbcast는 상태 시스템 복제 문제에 대한 대부분의 솔루션이 복제 중인 애플리케이션과 긴밀하게 통합되어 있다는 점에서 다소 이례적입니다.반대로 Gbcast는 멀티캐스트 API로 설계되어 있으며 그룹 구성원에게 메시지를 전달하는 라이브러리에 의해 구현됩니다.Lamport, Malkhi 및 Zhou는 상태 기계 모델을 올바르게 구현하기 위해 필요한 내구성 속성을 가진 신뢰할 수 있는 멀티캐스트 프로토콜이 거의 없다는 점에 주목합니다.Gbcast에 필요한 [7]속성이 표시됩니다.

Gbcast 프로토콜은 Isis [1]Toolkit의 가상 동기화 모델을 지원하는 인프라스트럭처에 대해 논의한 1985년 출판물에서 처음 설명되었습니다.추가적인 세부 사항은 1987년 이후의 저널 [2]기사에서 제공되었고, 그 해 11월 코넬 개발자들에 의해 오픈 소스 버전의 프로토콜이 발표되었습니다.Isis는 주로 프로세스 그룹의 구성원 자격을 유지하기 위해 프로토콜을 사용했지만 최종 사용자가 직접 호출할 수 있는 API도 제공했습니다.이 기술은 1988년 IS 시스템이 상용화되고 지원이 가능해지면서 널리 쓰이게 되었다.1998년 당시 Isis Distributed Systems의 모회사인 Stratus Computer가 순수하게 통신업계의 하드웨어 솔루션에 집중하면서 이 시스템에 대한 상업적 지원은 종료되었습니다.

프로덕션 환경에서 IS를 사용한 시스템의 예로는 뉴욕 증권거래소가 있습니다.뉴욕 증권거래소는 약 10년간 거래 플로어의 구성 가능한 폴트 톨러런스 및 자가 복구 보고서 인프라스트럭처를 관리하고 거래소에서 사용하는 "백 오피스" 시스템의 견적 및 거래 보고서를 오버헤드로 중계합니다.프랑스 항공 교통 관제 시스템은 Isis를 계속 사용하고 있습니다. 1996년부터 이 시스템은 항공 교통 관제사가 사용할 내결함성 워크스테이션 클러스터를 만들고 항공 교통 관제 센터 간의 라우팅 업데이트를 신뢰성 있게 중계하기 위해 사용되었습니다. 시간이 지남에 따라 프랑스 기술은 다른 유럽 ATC 시스템에도 채택되었습니다.미 해군 이지스는 1993년부터 ISIS를 이용해 신뢰할 수 있는 자가 복구 통신 인프라를 지원해 왔습니다.Isis는 또한 재무, 통신, 프로세스 제어, SCADA 및 기타 중요한 인프라 도메인에 수백 명의 다른 프로덕션 사용자를 보유하고 있었습니다.자세한 것은,[3] 을 참조해 주세요.

문제문

Gbcast에 의해 해결된 근본적인 문제는 다음과 같습니다.즉, 그룹 멤버의 초기 세트가 주어지고 멀티캐스트 추상화를 지원하여 그룹 멤버가 다양한 명령 또는 요구를 인코딩하는 메시지를 보낼 수 있도록 하는 것입니다.프로토콜은 그룹의 구성원이 메시지를 보낼 경우 해당 그룹의 모든 구성원이 다른 배달된 메시지에 대해 동일한 순서로 메시지를 받을 수 있도록 전달할 메시지와 그 순서에 동의해야 합니다.

그룹 멤버의 집합은 멤버가 실패하거나 가입할 때마다 변경되며, Gbcast는 "새로운 뷰" 이벤트로 응용 프로그램에 전달되는 특수 멀티캐스트를 통해 그룹 멤버쉽을 유지하기 위해 사용되지만 Gbcast 프로토콜 라이브러리에서 유지되는 그룹 멤버쉽 목록도 조정됩니다.따라서 응용 프로그램은 특정 그룹 구성원이 가입할 때 "초기 뷰"에서 시작하여 시간이 지남에 따라 진화하며 다른 뷰 변경 이벤트 및 멀티캐스트메시지에 대해 순서가 매겨지는 일련의 멤버십뷰를 참조합니다.이러한 멀티 캐스트는 전달이 예약된 보기에 나열된 실패하지 않은 모든 멤버에게 전달됩니다. 이 속성은 가상 동기화라고 합니다.

네트워크 파티션은 그룹을 둘 이상의 분리된 하위 그룹으로 분할할 수 있으며, 일부 그룹 구성원은 그룹의 다른 파티션이 서로 상충하는 다른 결정을 내린 것을 알지 못한 채 결정을 내리는(아마도 로켓을 발사하는) 분할 두뇌 동작의 위험을 발생시킬 수 있습니다.Gbcast는 이러한 위협에 대한 보호 기능을 제공합니다. 이 프로토콜은 그룹의 단일 기본 파티션에서만 진행이 이루어지도록 보장합니다.따라서 네트워크 파티션이 발생하면 멤버의 최대 1개의 서브그룹이 동작을 계속하고 다른 서브그룹은 확실히 정지 및 셧다운됩니다.

장애가 발생한 멤버가 회복된 경우(또는 파티셔닝 장애로 인해 일부 멤버가 장애로 잘못 인식되어 뷰에서 삭제된 경우) 통신이 복원된 후 해당 멤버가 다시 가입할 수 있습니다.불명확함을 피하기 위해 ephonative 번호가 사용됩니다.이 카운터는 프로세스가 그룹에 가입할 때마다 증가하며 프로세스 ID의 일부로 취급됩니다.특정(processor-id, process-id, incomponation-number) 태플은 최대 한 번에 그룹에 가입하고 실패하거나 타임아웃이 발생하여 강제로 탈퇴합니다.

Gbcast와 Paxos를 모두 포함하여 동적으로 재구성 가능한 시스템은 더 이상 진행할 수 없는 상태가 될 수 있습니다.예를 들어 동작 프로세스가 설정에서 잘못 삭제되어 뷰의 나머지 멤버 내에서 실제 크래시가 너무 많이 발생할 경우 이 문제가 발생할 수 있습니다.이러한 상황에서는 데이터센터 관리 인프라스트럭처가 애플리케이션 전체를 재시작합니다.이것은, 무제한의 중단에 견딜 수 있어 관리 인프라스트럭처를 개입시키지 않고 충분한 수의 그룹 멤버에 액세스 할 수 있게 되면 재개하는, 재구성 불가능한(vanilla) Paxos 의 동작과는 대조적입니다.자세한 프로토콜 설명에는 다음 용어가 사용됩니다.

과정

  • 프로세스는 임의의 속도로 동작하는 프로세서에서 실행됩니다.
  • 프로세스에서 크래시(중지) 장애가 발생할 수 있습니다.
  • 프로세스는 3개의 태플(processor-id, process-id, incomponation-number)로 일의로 식별됩니다.
  • 안정적인 스토리지를 사용하는 프로세스는 오류 발생 후(크래시 복구 실패 모델에 따라) 발생 횟수를 늘린 후 프로토콜에 다시 가입할 수 있습니다.
  • 프로세스는 공모하거나 거짓말을 하거나 프로토콜을 전복하려고 시도하지 않습니다.(즉, 비잔틴의 실패는 발생하지 않습니다.)

네트워크

  • 시스템 내의 모든 프로세스는 시스템 내의 다른 모든 프로세스로 메시지를 보낼 수 있습니다.
  • 메시지는 비동기적으로 발송됩니다.메시지 배달에는 시간 제한이 없습니다.
  • 메시지가 손실, 정렬 또는 중복될 수 있습니다.
  • 메시지는 파손 없이 전달됩니다.

이것들은, 약한 전제 조건입니다.메시지를 전혀 전달하지 않는 네트워크는, 그것들을 만족시킵니다(이러한 네트워크에서는, 완전하고 영속적인 파티셔닝 장해가 발생하고 있다고 말할 수 있습니다.Gbcast가 진척을 보증하기 위해 필요한 네트워크 조건은 다음과 같습니다.실제로 Gbcast는 일반적으로 데이터센터 내에서 사용됩니다.이들 데이터센터에는 일시적인 장애가 발생할 수 있지만 파티셔닝 장애는 드물며 일반적으로 노드의 작은 서브셋에만 영향을 미칩니다.따라서 분석을 위해 실제 도입에서 발생하는 것보다 더 가혹한 네트워크 환경을 가정합니다.

프레젠테이션을 단순화하기 위해 TCP와 같은 확인/재전송 방식을 채택하여 각 프로세스 쌍 간에 신뢰할 수 있는 시퀀싱된 비반복 메시지 채널의 착각을 발생시킨다고 가정합니다.이 채널 추상화가 반복적으로 재시도되어 일부 메시지에 대한 확인 응답을 얻을 수 없는 경우 타임아웃이 발생합니다.같은 TCP 유사 채널을 사용하면 1 대 모든 기능을 지원할 수도 있습니다.이 기능을 사용하면 단일 프로세스가 채널을 통해 일부 메시지를 일부 그룹의 다른 모든 뷰 멤버에게 전송할 수 있습니다.이것은 1 대 모든 요구를 여러 개의 1 대 1 메시지에 매핑함으로써 이루어집니다.이러한 1-to-all 채널에는 원자성 보증이 없습니다.메시지 송신중에 송신측이 장해가 발생했을 경우, 수신처의 일부에만 도달하는 경우가 있습니다.

프로세스 그룹 및 뷰

Gbcast는 일련의 프로세스에 대해 정의됩니다.전개된 시스템에서는 이러한 그룹에 이름(파일명 등), 그룹에 처음 접속하는 방법 및 흐름 제어 파라미터 등의 기타 속성이 있을 수 있습니다.그러나 간결하게 하기 위해 이러한 세부 사항은 여기서 생략한다.
멤버십 뷰란 연령별로 순위가 매겨진 멤버 목록(각 멤버가 최근에 그룹에 가입한 뷰에 따라 결정됨)이며 사전 순서 규칙에 따라 동점이 구분됩니다.
그룹의 초기 멤버십은 외부 에이전트에 의해 지정되며 그룹의 첫 번째 멤버십 뷰를 정의합니다.
후속 멤버십 뷰는 add 및 remove 명령을 적용하여 생성되며 시퀀스 번호로 식별됩니다.
새 보기는 "새 보기" 이벤트를 통해 보기에 속하는 프로세스에 보고됩니다.애플리케이션은 업콜(라이브러리에서 어플리케이션프로그램에 의해 정의된 핸들러로의 콜)을 통해 통지됩니다.

멀티캐스트 메시지

뷰의 멤버는 전달 시 적용되는 멤버십을 인식하지 않고 멀티캐스트메시지를 프로세스 그룹에 송신하도록 요구할 수 있습니다.
Gbcast 프로토콜은 아래에서 설명하는 일련의 보증과 함께 이러한 작업을 수행합니다.
배달은 응용 프로그램에 대한 업콜에 의해 이루어지며, 이 업콜은 메시지가 요구하는 모든 액션을 수행할 수 있습니다.

역할

Gbcast는 일련의 역할로 가장 잘 이해됩니다.

어플

애플리케이션은 하나 이상의 프로세서에서 실행할 수 있는 프로그램에 대응합니다.그런 다음 각 응용 프로그램 프로세스는 하나 이상의 프로세스 그룹에 가입합니다.
그룹에 속하는 어플리케이션프로세스가 Gbcast를 호출함으로써 새로운 멀티 캐스트를 시작한다.이 프로토콜은 대상 그룹의 모든 구성원이 아래에 설명된 메커니즘을 통해 메시지 전달을 확인했거나 결함으로 감지된 경우 종료된 것으로 간주됩니다.
착신 Gbcast 메시지는 표시 변경 알림과 마찬가지로 업콜을 통해 전달됩니다.
앞서 설명한 바와 같이 그룹의 멤버는 처음에 가입했을 때 시작되는 동일한 업콜 시퀀스를 관찰합니다.첫 번째 뷰와 새로운 뷰와 멀티캐스트메시지의 시퀀스입니다그룹의 모든 멤버는 같은 뷰에서 특정 멀티캐스트를 수신하고 멀티캐스트는 해당 뷰의 모든 비장애 멤버에게 전달됩니다.

지도자

그룹의 리더는 그룹의 일부 뷰에 대해 정의되며 뷰에서 순위가 가장 낮은 멤버입니다.앞서 설명한 바와 같이, 순위는 연령순서(나이 많은 구성원은 하위 등급)이며, 사전 정렬을 사용하여 동점을 깬다.

장애 검출

시스템의 모든 컴포넌트는 장애를 검출하는 역할에 참여할 수 있습니다.검출은 장애 보고와는 다릅니다(새로운 뷰를 통해 이루어지며 메시지 전달에 대해 순서가 지정됩니다).
네트워크 계층에서 지원되는 채널 추상화는 타임아웃에 의해 장애를 감지합니다.(네트워크 모델에서는 크래시된 타깃프로세스에 메시지를 송신하려고 하는 프로세스에서는 항상 타임아웃이 발생하지만 일시적인 파티셔닝 장애로 인해 메시지가 지연되면 채널 추상화가 동작 프로세스를 장애로 잘못 보고할 수도 있습니다).
타임아웃이 발생한 프로세스에서는 연관된 채널의 엔드포인트에 장애가 발생했음을 선언할 수 있습니다.
프로세스가 일부(processor-id, process-id, incomponation-number) 태플의 장애를 학습하면 모든 채널의 다음 발신 메시지에 해당 정보가 포함됩니다.
다른 프로세스가 실패했다고 간주하는 프로세스는 실패한 화신으로부터의 메시지를 거부하여 "당신은 실패했습니다"라고 응답합니다(즉, 실패에 대한 가십을 처리하고 실패한 그룹 구성원을 배제합니다).
실패한 프로세스의 새로운 형태로부터의 착신 메시지는 "새로운" 프로세스로부터의 메시지로 취급됩니다.

프로세스 실패

현재 뷰에서 실패한 것으로 탐지된 멤버는 실패한 프로세스로 간주됩니다.
(메시지를 거부하는 다른 프로세스와 통신을 시도함으로써) 장애가 발생한 것으로 간주되는 운영프로세스가 시스템에서 종료되거나 시스템 번호가 증가하여 재가입될 수 있습니다.

새로운 리더

현재 뷰의 하위 프로세스가 모두 실패한 프로세스인 경우 다음으로 높은 순위의 비실패 프로세스가 새 리더로 지정됩니다.
새로운 리더가 리더가 되려면 아래에서 설명하는 프로토콜을 실행해야 합니다.

쿼럼스

쿼럼은 그룹 뷰 및 멀티캐스트메시지의 글로벌하게 합의된 단일 시퀀스가 존재하는지 확인하고 그룹이 여러 파티션(t의 다른 멤버와 통신할 수 있는 멤버의 개별 서브셋)으로 분할되는 경우 여러 파티션에서 진행되지 않도록 함으로써 Gbcast의 안전 속성을 보증하기 위해 사용됩니다.다른 서브셋의 멤버는 사용할 수 없습니다).쿼럼은 특정 뷰에 대해 정의됩니다.

구성원 {A,B,C….}이 n개인 view i를 지정하면 뷰 쿼럼은 해당 뷰 멤버의 과반수 서브셋입니다.이는 기본 멤버쉽이 정적인 시스템에서 정의되는 용어와는 대조적입니다. Gbcast의 경우 그룹의 멤버쉽이 변경되고 새로운 뷰가 정의됨에 따라 쿼럼 크기가 시간이 지남에 따라 변경됩니다.

안전 및 생존 속성

안전을 보장하기 위해 Gbcast는 세 가지 안전 속성을 정의하고 장애 패턴에 관계없이 이러한 특성이 유지되도록 합니다.

사소하지 않다

일부 그룹 구성원에 의해 실제로 전송된 멀티캐스트만 전달됩니다.프로세스가 그룹 멤버로부터 실패했다고 생각되는 메시지를 수신하면 이러한 메시지는 거부됩니다.

일관성.

뷰의 멤버가 멀티캐스트를 다른 멀티캐스트에 대해 어떤 순서로 전달(또는 새로운 뷰를 보고)하는 경우, 같은 메시지를 전달(또는 같은 뷰를 보고)하는 같은 뷰의 다른 모든 멤버는 같은 순서로 전달합니다.

조건부 수명

멀티캐스트의 경우M일부 뷰에서 송신되어 송신자가 동작 가능한 상태로 유지되면 최종적으로 그 뷰의 모든 멤버(그 크래시를 제외한)가 전달됩니다.M모든 조건에서 생존을 보장할 수는 없기 때문에 추가 조건을 부과합니다.이 속성은 충분히 많은 프로세스가 장애가 없는 상태에서만 필요합니다(아래에서 자세히 설명하겠습니다).

기본 Gbcast

이 프로토콜은 일반적인 조건에서 사용되는 프로토콜입니다.

Gbcast에서는 각 운영 프로세스가 현재 보기를 가지며 각 보기가 리더를 정의합니다.현재 뷰에서 자신이 리더라고 믿는 프로세스만이 새로운 멀티캐스트를 시작할 수 있습니다.다른 멤버는 1대 1 연결을 통해 리더에게 멀티캐스트를 전송하고 리더가 프로토콜을 실행할 때까지 기다리면서 멀티캐스트를 릴레이해야 합니다.

리더가 아닌 멤버가 멀티캐스트 릴레이를 시도하고 있을 때 리더에 장애가 발생했을 경우 송신자는 보류 중인 요청의 상태를 판단해야 합니다.이것은 다음과 같이 이루어집니다.구성원은 자신의 멀티캐스트 전달을 관찰합니다.따라서 오래된 리더에 장애가 발생한 새로운 뷰가 정의되면 멀티캐스트가 전달되거나(이 경우 송신자는 수신자 중 하나였기 때문에 이를 알고 있다), 또는 새로운 뷰의 전달을 통해 리더가 보류 중인 메시지를 릴레이하지 못했다고 결론지을 수 있으며 새로운 l을 요구함으로써 메시지를 재발송신해야 합니다.릴레이(비일관성)를 실시합니다.

준비 단계

리더는 신뢰할 수 있는1 대 모든 네트워크층을 사용하여 메시지를 최신 뷰의 멤버에게 송신하고 각각을 정수 시퀀스 번호로 식별함으로써1개 또는 여러 멀티캐스트메시지의 시퀀스를 제안합니다.새로운 뷰가 정의될 때마다 시퀀스 번호가 1로 리셋됩니다(다음 설명과 같이 특수한 종류의 멀티캐스트를 통해).리더는 다른 멤버들과 마찬가지로 프로토콜에 참여하면서 "혼잣말"을 합니다.복구 중에(아래에서 설명) 새 리더가 이전 리더가 시작했지만 완료하지 못한 프로토콜을 완료하려고 시도함에 따라 새 리더가 이전에 제안한 보기 또는 메시지를 다시 제안할 수 있습니다.이 경우 새 리더는 원래 순서를 존중하고 동일한 보기 또는 메시지를 다시 제안합니다.

약속 단계

각 수신자는 메시지의 복사본을 보관하고 전달 약속으로 응답합니다(수신자 자신이 그룹 뷰의 멤버로 남아 있는 한 이러한 약속은 이행되지만 수신자가 실패할 경우 약속은 실행되지 않을 수 있습니다).복구 중에 수신인은 동일한 메시지에 대해 중복된 준비 요청을 수신할 수 있습니다.일부 메시지가 동일한 시퀀스 번호로 다시 제안될 경우 수신자는 약속을 반복하기만 하면 됩니다.

커밋 스텝

리더는 그룹의 각 멤버에 대해 약속 메시지가 있거나 타임아웃이 발생할 때까지 약속 메시지를 수집합니다(이 경우 리더는 의심스러운 멤버를 회피하고 메시지 송신 서브시스템이 이 정보를 네트워크 상에서 피기 때문에 해당 멤버를 장애로 의심합니다).리더로부터 후속 메시지를 수신하는 프로세스도 새롭게 의심되는 멤버를 배제하기 시작합니다).
리더는 프로토콜을 실행하는 보기와 관련하여 정의된 대로 구성원 쿼럼으로부터 약속을 수신하면 커밋 요청을 보냅니다.리더가 쿼럼이 부족하여 그룹 멤버의 과반수 이상이 의심되면 더 이상 진척을 볼 수 없게 되고 리더는 종료됩니다(어플리케이션 프로그램이 새로운 프로세스 이름을 사용하여 그룹에 다시 가입할 수 있지만 이전 프로세스 이름에서 이 프로세스에 의한 추가 진행은 불가능합니다).
리더는 준비 단계 또는 제안 단계에서 실패에 대해서도 알고 있을 수 있습니다.
준비 단계에서 일부 뷰 구성원은 제안 요청을 승인하지 못할 수 있으며, 이 경우 해당 구성원에 대한 리더의 채널에서 타임아웃이 발생합니다.리더는 그들을 실패한 멤버로 표시했을 것이다.
또한 약속 단계에서 약속 메시지를 수신함으로써 리더가 다른 그룹 멤버에 의해 검출된 실패한 멤버를 알게 되었을 수도 있습니다.따라서 커밋 단계 시작 시 리더는 실패한 뷰 구성원의 빈 목록과 함께 약속 쿼럼을 가집니다.
따라서 리더는 뷰에서 실패한 멤버를 삭제하는 뷰 변경 이벤트에 대한 제안과 함께 뷰의 비실패 멤버에게 "Commit" 메시지를 발송하여 커밋 스텝과 제안 스텝을 하나의 액션으로 결합합니다.장애검출이 발생한 후 그룹 내 각 멤버에 대한 첫 번째 메시지가 해당 장애검출정보를 피기백하여 멤버가 장애가 발생한 멤버를 배제하는 것에 주의해 주십시오.따라서 장애를 알게 된 멤버는 즉시 실패한 멤버를 회피하기 시작하고 리더는 뷰 변경 프로토콜을 시작하는 추가 단계를 수행합니다(이 과정을 완료하는 데 시간이 걸립니다).
제안에서 구성원을 추가하여 보기를 변경한 경우, 리더는 가입 구성원에게 새 보기를 보냅니다. 그러면 가입 구성원들의 초기 보기가 되고 이후 프로토콜 실행에 참여할 수 있습니다.
회복 중에 참가자는 이전에 커밋된 메시지에 대해 중복된 커밋을 받을 수 있습니다.이 경우 전송 단계는 시작되지만 메시지 또는 보기는 응용 프로그램에 다시 전달되지 않습니다.

납품 단계

구성원은 Commit 메시지를 수신하면 리더가 제안한 순서대로 관련 메시지 또는 새 보기를 응용 프로그램에 전달합니다.리더는 신뢰할 수 있는1 대 1 채널에서 사용되는 확인 응답을 수신하면 이 스텝이 성공했음을 학습합니다.

메시지 흐름: 기본 Gbcast, 단순한 케이스

(쿼럼 크기 = 2, view1={A,B,C})

회원 지도자 부재 응용 계층 ABCABCX?>요청에 따르면 김정일이 멀티 캐스트 MX를 보낼까?->, ->, ->, Propose(1.1:M)( 보기 1, 순서 1, 메시지 M).            <-----X--X--X Promise(1.1) X-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------M-> M-> M-> M-> M->

기본 Gbcast 오류 사례

가장 간단한 오류 사례는 하나 이상의 구성원이 실패했지만 쿼럼이 활성 상태인 경우입니다.아래 예에서 그룹은 {A,B,C}으로 구성되며 A가 리더 역할을 합니다. C약속 단계에서 장애가 발생하여 리더에서 처리까지의 신뢰할 수 있는 채널 내에서 타임아웃이 발생합니다.C따라서 리더는 M의 전달을 커밋하지만 동시에 제거하기 위한 프로토콜을 시작합니다.C새 보기 {A,B}을(를) 생성하는 그룹에 속합니다.C가 실제로 실패하지 않은 경우 그룹에 다시 가입할 수 있지만 새로운 번호(실제로 C는 C'로 다시 가입해야 합니다)를 사용합니다.C에서A 또는 B로의 메시지는 각각 명백한 장애를 알게 된 순간 거부됩니다.A와 B는 C를 회피합니다.

메시지 흐름: 기본 Gbcast, 리더 이외의 멤버 장애

(쿼럼 크기 = 2, view1={A,B,C})

회원 지도자 부재 응용 계층 ABCABCX?>Request(M)X?->, ->, ->, Propose(1.1:M)!CFAILS!&.그것은,-----X.XPromise(1.1)X?->, ->, Commit(1.1), Propose(1.2:"C를 제거하")<-----X--X?->, M->, MCommitted(M), Delivers M;Promise(1.2)X?->, ->, ->, Commit(1.2),<-----X--X--X---->V->, V예탁(.1.2);Delivers view2={A, B}

Commit 및 새로운 Proposal(및 피기백 장애 알림)이 하나의 메시지로 결합되어 있는 것에 주의해 주십시오.이것에 의해, 새로운 장해가 검출된 후에 액션을 커밋 하는 모든 프로세스가, 그 장해에 대해 동시에 학습해, 관련하는 프로세스를 회피해, 그 프로세스는 뷰로부터 신속히 삭제됩니다.C가 크래쉬하지 않은 경우, C는 재접속할 수 있습니다.이것에 의해서, 그 번호가 C'로 붙여지고 나서, 리더에 의해서 그룹에 재접속하도록 요구됩니다.새 이름과 함께 구성원 목록에 추가되고 보기 구성원 중 가장 높은 순위(가장 어린 구성원이기 때문에)를 가집니다.

메시지 흐름: 기본 Gbcast, 멤버 추가 {D,E,F}, 리더 이외의 멤버 장애

아래 표시된 예에서는 처음에 멤버 {A,B,C}을(를) 포함하는 그룹에 {D,E,F}을(를) 추가하라는 메시지가 표시되지만 멤버 C는 프로토콜 중에 실패합니다.멤버십 변경 요구는 특별한 종류의 멀티캐스트로 취급되며 이벤트의 시퀀스는 동일합니다.따라서 예제는 이전 예제와 거의 동일하지만, 이제 일련의 새로운 뷰 이벤트가 애플리케이션에 전달됩니다.(쿼럼 크기 = 2, view1={A,B,C})

회원 지도자 부재 응용 계층 ABCDEFABCDEFX?>Request("D,E,F을 추가하")X?->, ->, -&gt을 말한다.                                  (1.1을 제안하다:"D,E,F을 추가하")**!C야!!<-----X--XPromise(1.1)X?->, ->, Commit(1.1), Propose(2.1:"C를 제거하")<-----X--X---X--X--X---->V->, V-->V-FAILS.>V->, VCommitted(1.1); view2={A,B,C,D,E,F};Promise(2.1) X----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

프로토콜이 끝날 때 새 활성 보기는 view3={A,B,D,E,F}이고 새 쿼럼 크기는 3입니다.그러나 쿼럼 크기가 4인 "인증" 보기, view2={A,B,C,D,E,F}가 있습니다.리더가 C를 제거한 제안 단계에 대한 4가지 약속을 받지 않았다면 view3의 커밋 단계를 실행할 수 없었을 것입니다.이것은 기본 정책을 나타내고 있습니다.새 보기를 커밋하는 데 필요한 쿼럼은 항상 이전 보기의 크기를 기반으로 합니다.

리더가 실패했을 때 사용되는 테이크오버 프로토콜

다음 실패 사례는 리더가 실패하여 새로운 리더가 생기는 경우입니다.리더를 이어받기 위해 새로운 리더가 먼저 인수 프로토콜을 실행하고, 그 다음 새로운 리더가 위와 같이 기본 Gbcast를 실행할 수 있습니다.테이크오버 프로토콜은 다음과 같습니다.

문의 단계

새 리더는 실패하지 않은 멤버에게 전달하기로 약속한 메시지를 듣기 위해 1 대 1 메시지를 보냅니다.

Promise-List 스텝

각 수신자는 약속된 메시지의 현재 목록을 리더에게 보냅니다.수신자가 초기 보기가 부족한 경우, 리더에게 초기 보기에 대한 요청을 보냅니다.
새 리더는 접촉한 각 멤버로부터 약속 목록을 받거나 타임아웃될 때까지 기다립니다.타임아웃이 발생하면 새로운 리더는 문제의 멤버를 의심하고 다른 멤버와 마찬가지로 회피합니다.그것은 나중에 더 자세히 설명하듯이, 결국 이러한 기피 회원들을 배제하는 관점을 제안할 것이다.

필요한 경우 반복

새 리더는 약속 목록을 검사하고 새 멤버를 추가하는 멤버십 변경 메시지를 찾습니다.존재하는 경우 문의 단계와 약속 목록 수집 단계를 반복하여 신규 회원에게 문의합니다.이는 결국 더 많은 구성원을 추가하는 추가 제안의 발견으로 이어질 수 있다.모든 멤버(현재 또는 추가할 것을 제안)가 약속 목록으로 응답했거나 새 리더에 의해 의심되면 프로세스가 종료됩니다.

쿼럼 확인

조사 단계 종료 시 리더는 접촉한 프로세스 중 일부로부터 약속 목록 응답을 받았습니다.응답하지 않는 멤버는 의심됩니다.새로운 리더가 제안된 뷰의 목록을 작성합니다.인수 제안의 다음 단계로 진행하려면 새 리더가 이 목록에 대해 커밋되거나 제안된 각 뷰로부터 쿼럼의 응답을 받아야 합니다.목록에 커밋되거나 제안된 뷰에 대해 쿼럼의 응답을 받지 못한 경우 새 리더는 리더 자리를 물려받지 못해 성공할 수 없습니다.프로토콜이 종료되고 새 프로세스 실행 번호를 사용하여 시스템에 새 구성원으로 다시 가입해야 합니다.

새로운 리더로 시작

쿼럼을 성공적으로 체크한 후, 새로운 리더가 리더가 됩니다.이제 기본 프로토콜을 실행할 수 있습니다.약속된 메시지 또는 뷰 변경을 약속 목록에서 학습한 순서대로 다시 제안합니다.이러한 메시지 또는 뷰 변경은 새로운 view-change 명령어를 사용하여 해당 메시지에 이어 조회 단계에서 응답하지 못한 오래된 리더 및 기타 멤버를 삭제합니다.약속 목록 단계 중 멤버가 초기 보기가 부족하다고 응답한 경우 새 리더는 해당 구성원에게 적절한 초기 보기를 보냅니다.

결투 리더

약속 리스트에는 같은 슬롯에 대해 2개 이상의 다른 제안이 포함될 수 있습니다.이것은 첫 번째 리더 A가 시스템에서 분할되었지만 그래도 제안을 했을 경우에만 발생합니다.X소수(정족수 미달) 멤버만 볼 수 있습니다.새로운 리더 B가 인수에는 성공했지만, A의 제안(커밋할 수 없는 것)은 듣지 못했다.B는 이제 Y를 제안하고, 다시 소수의 멤버에게 Y를 제안합니다.이제 B가 실패했다고 생각되고 C가 이어받습니다.C가 제안을 배우는 것은 가능하다.X같은 슬롯에 대해 Y를 선택합니다.C는 오래된 리더 A와 관련된 제안을 무시하되 새로운 리더 B와 관련된 제안(이 경우 제안)은 유지해야 합니다.X쿼럼을 달성할 수 없기 때문에 커밋할 수 없는 반면, 보다 최근의 리더에 의해 작성된 제안 Y는 커밋될 수 있습니다(그렇지 않으면 X가 쿼럼에 도달했을 경우 B는 제안 X를 알고 반복할 수 있습니다).따라서 B는 이 사실을 몰랐기 때문입니다.X,X쿼럼을 받지 않아야 합니다.)
C의 인수 프로토콜은 해당 제안을 결정하기 위해 리더 A와 B 사이의 결정론적 순서를 사용합니다.X왜냐하면 리더 B가 리더가 되기 위해 A를 피해야 했기 때문이다.반대로 C는 제안 Y가 C의 인수 스텝과 교차했기 때문에 A가 B의 실패를 의심하더라도 제안 Y가 커밋될 수 있다고 가정해야 합니다.규칙은 리더의 번호를 순서대로 매기고 제안서에 리더 번호를 포함시킴으로써 구현됩니다.문의 단계에서 새로운 리더는 같은 슬롯에 대해 경합하는 제안을 수신한 경우 더 많은 수의 리더로부터의 제안을 사용할 수 있습니다.

발신 메시지에 대한 장애 의심 피기백

새 리더는 이전 리더가 실패했다고 믿고 있으며 다른 멤버들도 실패했다고 생각할 수 있습니다.따라서 조회 단계 또는 새로운 제안 단계에서도 1개 이상의 멤버에 대한 피기백 장애 메시지가 전송될 수 있습니다.이것은 프로토콜에 대한 핵심 요건입니다. 왜냐하면 그것은 그 구성원들이 나중에 배제되도록 하기 때문입니다: 만약 더 이상의 통신이 배제된 구성원들로부터 수신된다면, 수신자는 그 메시지들을 거부할 것입니다.따라서 멤버 중 하나가 오래된 리더L에 대해 약속 목록 단계를 실행한 경우 L로부터의 추가 제안 또는 커밋메시지는 해당 멤버에 의해 처리되지 않습니다.이를 통해 현재 뷰에서 쿼럼을 달성했을 가능성이 있는 모든 약속된 메시지가 포함된 새 리더가 수집한 약속 목록이 완성됨을 알 수 있습니다.또한 아직 쿼럼에 도달하지 못한 일부 약속된 메시지가 포함될 수 있습니다.

메시지 흐름: 기본 Gbcast, 리더 장애, 테이크오버, 새로운 리더에 의한 기본 Gbcast

(쿼럼 크기 = 2, 보기 1 = {A,B,C})

멤버 리더 멤버어플리케이션레이어 A B A C A B C C X ------------------------------> 프로포즈(1.1:M)!!지도자 송신 중에, C까지 닿지 않아 제안하다!*< 할 것이며,----------X—-X Promise(1.1)**!!(THELEADER)FAILED HAS!NEWLEADER:B!?------------>->, 조사하다("B때문에 A타카를 접수하고 있지faile로D")<>------------X--XPromiseLists(1.1:M)X------------>->, 제안하다(1.1:M. 제안하다(1.2:"remove A")<>------------X--X?->, Promise(1.1), Promise(1.2)X------------>->.----->, Commit(1.1), Commit(1.2),<>-.----------------------------------------------------------------------------------------------------------------------------------------------X--X?>M;V->.M;V Committed(1.1), Committed(1.2), Delivers(M).뷰 2={B,C} 제공

메시지 흐름: 기본 Gbcast, 멤버 추가 {D,E,F}, 리더 실패

보다 복잡한 사례의 예로서 리더는 뷰의 크기를 늘리는 커밋 도중에 실패한다.

(쿼럼 크기 = 2, 보기 1 = {A,B,C})

회원 지도자 부재 응용 계층 BABCDEFABCDEFX--->, Request("D, E, F추가")X------------>-&gt을 말한다.                                     제안하다(1.1x!지도자 송신 중에, 제안하다 C에 도달하지 않지 않는다.!*< 할 것이며,----------X—-X Promise(1.1)**!!(THELEADER)FAILED HAS!NEWLEADER:B!?------------&.gt, ->.문의("A가 실패했기 때문에 B가 인계받습니다") <-----------------X PromiseLists(1.1: "D, E, F 추가"), ?-------------------------------------------------------> -> 반복된 문의("B가 A가 실패했기 때문에 인계받습니다") <-------------------------------------XPromiseLists(1.1:"D, E, F추가"), X,---------->->, ->, ->, ->, Propose(1.1:"D, E, F추가"), Propose(2.1:"A를 제거하")<>------------X--X--X--X--XPromise(1.1), Promise(2.1), X,---------->->, ->, ->, ->, 저지르다(1..1.(2.1을 가하다.); <-------------X->X->X->X ----------------------->V->V->커밋(1.1), 커밋(2.1), 뷰2={A,B,C,D,E,F}를 제공합니다.뷰3={B,C,D,E,F} 제공

이 예에서는 문의의 반복 "in action"을 볼 수 있습니다.B는 문의의 첫 단계에서 {D,E,F}를 추가하는 프로토콜을 학습하기 때문에 문의가 반복되고 이번에는 D,E 및 F에 접속합니다.C에서 다시 문의할 필요는 없습니다.그것은 이전에 취득한 것과 같은 정보를 되돌리기 위해서입니다.

이 예에서는 최종 커밋에 의해 실제로는 멤버B와 C에서2개의 뷰가 연속적으로 전달됩니다.2개의 제안이 동시에 송신된 경우에도 view2의 커밋은 뷰1의 쿼럼에서 확약이 필요한 반면 view3의 커밋은 뷰2의 멤버로부터의 쿼럼 응답이 필요합니다.초기 뷰 전송은 다이어그램에 명시적으로 표시되지 않지만 가입 멤버는 view2까지 그룹에 가입하지 않기 때문에 1.1 프로토콜에 참여하지 않습니다.멤버 B와 C에서는 파이프라인 효과가 발생합니다.view1의 이벤트가 커밋된 상태에서도 view2와 관련된 이벤트가 이미 제안되고 있습니다.

정확성

Gbcast가 중요하지 않은 것을 만족시키는 것을 나타내기 위해 우선 임의의 전달 액션에서 클라이언트가 대응하는 이벤트를 요구한 시점까지 역추적합니다.분명히 합법적으로 전송된 메시지만 전달됩니다.그러나 이 프로토콜은 더 이상 중요하지 않습니다. 특정 멤버로부터의 메시지가 전달되는 것은 해당 멤버가 일부 뷰에서 아직 라이브 참가자일 때뿐임을 보여줘야 합니다.따라서 리더가 멀티캐스트를 시작했지만 전달되기 전에 실패한 경우를 살펴봅니다.여기서 새로운 리더는 보류 중인 제안을 검출하여 뷰 변경 이벤트 전에 주문하거나 새로운 리더가 보류 중인 제안을 검출하지 못했습니다.이 경우 새로운 뷰의 모든 멤버가 오래된 리더로부터의 지연 착신 메시지를 회피합니다.따라서 멀티캐스트메시지가 송신된 뷰가 보류 중일 때 전달되거나 전혀 전달되지 않습니다.

일관성을 확립하기 위해 먼저 쿼럼에 실패하거나 접속을 잃지 않는 리더가 1명밖에 없는 경우를 분석합니다.리더는 이벤트를 시퀀스화하여 해당 멤버가 포함된 첫 번째 뷰부터 각 멤버를 포함하므로 모든 멤버는 동일한 메시지를 시스템에 추가한 뷰부터 전달합니다.

새로운 리더가 취임하면 가장 최근에 커밋된 뷰에 대한 멤버 정족수에 도달해야 합니다.이 쿼럼에는 반드시 이전 리더가 커밋할 수 있는 제안을 받은 프로세스가 하나 이상 포함됩니다.따라서 새로운 리더는 잠재적으로 약속된 제안을 학습하고 새로운 제안의 서픽스로 포함시킬 것입니다.즉, 어떤 프로세스가 이벤트를 전달하고 시스템이 진행되면 살아남은 모든 구성원은 결국 동일한 이벤트를 동일한 순서로 전달합니다.

관련된 두 가지 사례를 분석함으로써 가입자가 최초 견해를 제공받을 수 있음을 알 수 있습니다.리더가 실패하지 않으면 최종적으로 신뢰할 수 있는 채널로 초기 뷰를 전송합니다.리더가 실패하여 일부 멤버가 초기 뷰가 부족한 경우 새 리더는 "약속 목록" 응답을 받은 후 해당 뷰를 조회 단계 메시지에 보냅니다.

회피 규칙 때문에 그룹의 논리 파티셔닝을 할 수 없습니다.새로운 견해를 약속하기 위해서는 오래된 지도자가 현재의 견해 정족수에서 약속을 얻어야 한다.새로운 리더가 취임하면 약속될 수 있었던 모든 관점을 알게 될 것이다.따라서 제안된 다음 뷰를 커밋하려면 해당 중간 뷰의 쿼럼(있는 경우)과 상호 작용해야 합니다.파티셔닝으로 이어질 수 있는 시나리오에서는 리더 A가 B에서 타임아웃하고 B를 제외한 일련의 새로운 보기와 이벤트를 생성했을 수 있습니다.그러나, 이 경우, 구관 또는 중간 관점 구성원의 대다수는 A가 B가 실패했다고 믿는다는 것을 알게 될 것이고, 문의할 때 B를 피하게 될 것이다.어느 경우든 B는 쿼럼을 얻을 수 없기 때문에 진행할 수 없다.대칭 인수는 B가 A를 제외한 새 보기를 성공적으로 정의하면 A가 제안할 수 있는 다른 새 보기에 대한 쿼럼을 가져올 수 없음을 나타냅니다.

라이브

Gbcast 프로토콜은 실행 시 항상 다음과 같이 진행됩니다.v홀드 시간t멤버의 정족수 미만인 경우v뷰 멤버의 일부 서브셋 내에서 실패(또는 실패한 것으로 의심됨)합니다.진행률을 최대화하려면 제외되었지만 활성 상태인 구성원을 그룹에 다시 가입시키는 것이 중요합니다. 그러면 잘못된 장애 탐지로 인해 보기가 지속적으로 축소되지 않습니다.그러나 모든 프로세스가 현재 보기 멤버의 정족수 이상으로 의심될 경우 프로토콜은 복구되지 않고 진행되지 않습니다.

이 특성은 찬드라 및 투그에 의해 정의된 바와 같이 합의 달성을 위한 "가장 약한 고장 검출기"인 <>W와 유사하지만 "강하다".이를 확인하려면 뷰에서 잘못 제외된 프로세스에 대해 서로 의심하는 쿼럼이 "너무 빨리" 발생하여 다시 가입하는 실행을 고려하십시오.Gbcast는 진행되지 않으며 실제로 그룹을 셧다운하고 재시작해야 합니다.

Gbcast가 일반적으로 사용되는 데이터 센터에서는 이러한 실행은 거의 발생하지 않지만, 분명히 적대적인 방식으로 구축될 수 있습니다.

토론:장애 감지

Gbcast 프로토콜에서는 잘못된 장애 의혹이 발생할 가능성은 낮다고 가정합니다. 장애 의혹이 자주 발생하고 운영 프로세스가 장애로 의심될 경우 스킴이 고장납니다.이와 같이 확인 응답을 수신하지 못하면 결국 연결이 끊어지는 TCP 프로토콜을 생각해 보십시오.TCP는 거의 보편적으로 사용되기 때문에 어느 엔드포인트도 장애가 발생하지 않았을 때 TCP 접속이 자주 끊어지면 웹에 막대한 장애가 발생합니다.따라서 타임아웃은 보수적으로 설정됩니다.Gbcast를 사용하는 시스템에도 같은 전제가 필요합니다.

이와는 대조적으로, Chandra와 Toug가 탐색한 것과 같은 다른 고장 감지 스킴은 잘못된 고장 의심 비율을 높일 수 있습니다.Paxos를 비롯한 일부 프로토콜은 비용이 많이 드는 결과 없이 잘못된 오류 의심을 허용할 수 있습니다.어떤 접근법이 다른 접근법보다 본질적으로 나은지는 이 논의의 범위를 벗어난다.단순히 접근 방식이 다르며, 타임아웃이 지나치게 공격적으로 설정되면 Gbcast가 효과적이지 않다는 점을 강조합니다.

한 가지 극단적인 시나리오는 네트워크 파티셔닝이벤트입니다오늘날의 데이터센터와 네트워크에서는 종종 하나의 머신과 그 위의 모든 프로세스가 서로 연결된 상태로 있는 대규모 머신 풀에서 일시적으로 분할되는 이벤트가 발생합니다.이러한 경우는 Gbcast에서는 장애로 취급되지만, 나머지 접속 멤버에 충분한 수의 프로세스가 포함되어 있는 경우, 시스템의 대부분은 단순히 절단된 멤버를 제외하도록 재구성됩니다.파티션이 복구되면 나중에 다시 연결하고 그룹에 다시 가입할 수 있습니다.

데이터센터에서는 보다 극단적인 파티셔닝이 발생할 수 있습니다.이 경우 네트워크 스위치에 장애가 발생하여 여러 대의 머신(랙 전체 또는 컨테이너 전체)이 인터넷 및 데이터센터의 나머지 부분과 연결이 끊길 수 있습니다.이러한 경우 모든 멤버가 다른 멤버를 의심하기 시작하는 그룹을 생각할 수 있습니다.이 경우 Gbcast는 진행되지 않으며 관리 인프라스트럭처는 애플리케이션 전체를 재시작해야 합니다.한편, 대부분의 대규모 데이터 센터에서는, 이러한 장해가 발생하고 있는 머신의 operating system도 셧다운 해, 접속이 회복되었을 때만 재기동합니다.따라서 실제로 시스템의 재기동은 피할 수 없습니다.즉, Paxos와 같은 프로토콜이 있으며, 이러한 프로토콜은 기계 자체가 계속 작동하다가 나중에 적절한 연결을 회복할 경우 이러한 장애를 극복할 수 있습니다.

트랜시스 시스템은 Gbcast 프로토콜의 확장을 탐색하여 여러 개의 파티션을 형성하고 독립적으로 진행하며 재머지할 수 있도록 했습니다.그러나 이 주제는 현재 논의의 범위를 벗어납니다.

토론:결투 리더

Paxos 프로토콜에서는 두 명 이상의 리더가 동일한 슬롯에 대해 서로 다른 명령을 제안하여 "듀얼"하는 상황이 발생할 수 있습니다.이 문제는 Gbcast에서도 발생할 수 있습니다.

통상적인 일련의 사건에서, 한 명의 리더가 이전 리더가 실패했기 때문에 인계받고, 조사 단계에서 이전 리더가 한 제안을 학습한 후, 새로운 제안과 함께 동일한 제안을 반복한다.따라서 같은 제안이 같은 슬롯에서 반복되기 때문에 슬롯의 내용에 대한 결투는 발생하지 않습니다.

결투에 가장 가까운 상황은 구 리더가 다수당으로부터 분할되어 새로운 리더가 그 뒤를 이어 일부 멤버와 접촉할 수 없는 경우입니다(단, INQUIRE 단계에서 필요한 쿼럼을 획득합니다).여기서 새 지도자는 이전 지도자가 제안한 몇 가지 제안을 알지 못할 수도 있고, 만약 새로운 지도자가 접촉하지 않은 구성원들에게만 전달된다면 여전히 제안할 수도 있다.

회피 메커니즘은 그러한 결손을 해결한다.새로운 리더가 INQUIRE 단계에서 쿼럼을 획득했을 때, 새로운 PROJUAL을 개시할 가능성이 있는 경우, 이전 리더가 쿼럼을 획득하는 것도 차단되었습니다.현재 대부분의 멤버가 이전 리더를 회피하고 있습니다.따라서 새 지도자에 의해 어떤 제안도 빠지면 그것은 반드시 정족수에 이르지 못하고 앞으로 정족수에 이르지 못할 것이다.게다가, 그러한 제안을 알고 있는 회원은, 새로운 리더로부터 외면당하게 된다. 왜냐하면, 새로운 리더는, (회원의 문의에의 회신을 기다리는 것을 포기했을 때) 그들은 실패한 것으로 간주되기 때문이다.새로운 리더로부터 새로운 제안을 배우는 멤버들도 그것들을 피하게 될 것이다.

Gbcast에서 지도자의 배척은 미리 정해진 지도자의 서열 순서로 이루어집니다. 즉, 고위 지도자는 자신의 자리를 차지하려고 할 때 하위 지도자를 배척할 뿐입니다.팍소스 투표 메커니즘은 정확히 같은 목적을 수행하지만, 참가자들이 새로운 투표용지("순위")를 가정하여 반복적으로 인수 시도를 할 수 있도록 하는 데 차이가 있다.그 결과 팍소스 지도자의 좌천은 돌이킬 수 있고, 다른 한편으로 이론적으로 결투 지도자는 영원히 지속될 수 있다.

Paxos와 쌍시뮬레이션의 동등성

표면적으로는 상당히 다르지만, 자세히 연구한 결과 Gbcast는 팍소스와 놀라울 정도로 비슷한 것으로 나타났다.실제로 Paxos는 다음과 같은 일련의 (역전 가능한) 단계를 통해 Gbcast로 "변환"할 수 있습니다.간략하게 하기 위해 이러한 단계를 비공식적으로 설명하고 자세한 증거를 생략합니다.

이 변환에서는 내구성이 고려되지 않습니다.Gbcast는 내구 상태를 프로토콜이 아닌 애플리케이션의 속성으로 취급하는 반면, Paxos는 일련의 내구 명령 로그에 이벤트를 기록하므로 서비스 전체가 종료되고 재시작된 후에도 상태를 복구할 수 있습니다.Gbcast에서의 동등한 동작에는, 모든 수신 메세지가 애플리케이션에 로그에 기록됩니다만, 이 경우는 여기서 다루지 않습니다.

  1. 기본 Paxos 프로토콜부터 시작합니다.재결합 프로세스를 지속적으로 보기의 구성원이었던 프로세스와 구별하기 위해 프로세스 식별 번호를 추가합니다.그룹 구성원에게 연령에 따른 순서를 부과하고, 가장 나이 많은 구성원(사전 편찬)을 리더로 지정합니다.비리더는 리더를 통해 요청을 발행합니다.
  2. 두 프로토콜 모두 요청 배치를 허용합니다.기본 Paxos에는 알파라는 동시성 매개 변수가 있습니다. 리더는 프로토콜의 최대 알파 인스턴스를 동시에 실행할 수 있습니다.Gbcast를 사용하면 리더가 단일 프로토콜 인스턴스에서 여러 이벤트를 제안할 수 있습니다. 즉, 메시지 배달이나 이벤트 보기를 제안할 수 있습니다.
  3. 팍소스는 일반적으로 신뢰할 수 있는 질서 있는 통신을 필요로 하지 않습니다.신뢰할 수 있는 일대일 채널 추상화에서 실행되도록 프로토콜을 수정합니다(일대다 메시지는 Paxos에 의해 일대일 채널 세트를 통해 전송됩니다.송신된 모든 메시지가 순서대로 수신되어 전달되거나 발신측에서 타임아웃이 발생한다고 가정할 수 있습니다.
  4. Paxos 슬롯 번호가 Gbcast 시퀀스 번호가 됩니다.팍소스 투표 번호는 사실상 조회 단계에서 상충하는 제안을 구별하는 데 사용되는 제안 리더 번호로 변환됩니다.
  5. 그룹 구성원 자격에서 프로세스를 추가하거나 제거하여 작동하는 보기 수정 명령 범주를 정의합니다.Gbcast에서 사용되는 장애 검출 메커니즘을 도입하여 타임아웃된 멤버를 삭제하도록 리더에게 요구합니다.그룹에서 삭제되어 그룹에 접속이 재정립된 멤버는 새로운 번호에 가입해야 합니다.응용 프로그램에 대한 업콜별로 보기를 보고합니다.
  6. 기본 Paxos는 그룹 멤버의 쿼럼에만 멀티캐스트를 제안할 수 있기 때문에 일반적인 멤버는 명령어목록에 공백이 있을 수 있습니다.그렇기 때문에 Paxos에서는 학습자가 멤버의 쿼럼을 읽고 명령 목록을 병합해야 합니다.수정된 프로토콜에서는 모든 멀티캐스트가 실패하지 않은 모든 멤버에게 제안되며 실패한 멤버는 뷰에서 삭제됩니다.따라서 Paxos와 달리 수정된 프로토콜은 단일 라이브 멤버가 완전한 커밋 이벤트 목록을 갖는 속성을 가집니다.실제로 프로토콜은 현재 구성원 보기 크기와 동일한 쓰기 쿼럼과 읽기 쿼럼이 1입니다.이는 데이터베이스 또는 객체의 실제 상태를 유지하고 실제 이벤트 시퀀스를 학습하기 위해 병합해야 하는 일련의 업데이트로 상태를 나타내는 애플리케이션을 구축할 때 편리합니다.

Paxos를 정의하는 쿼럼 메커니즘(새로운 Paxos 리더가 인수할 때 사용되는 질문 포함)은 이제 Gbcast의 단계에 정확히 일치하는 것으로 보입니다.일반적으로 팍소스 프로토콜의 특징으로 여겨지는 투표 메커니즘은 지도자의 후계 순서를 추적하는 카운터로 감소한다.이러한 단순화는 기본적으로 리더가 의심되는 경우 해당 리더가 보기에서 제거되고 프로토콜에 참여하기 전에 다시 가입해야 한다는 보장 때문입니다.

따라서 Gbcast와 Paxos는 가정을 변경하지 않고 동일한 정확성 속성으로 서로 변환할 수 있습니다.분명히 프로토콜은 비슷해 보이진 않지만 깊은 연관이 있어실제로 Gbcast에 의해 표시되는 전달 이벤트의 시퀀스는 Paxos의 일부 실행에서도 발생할 수 있으며, 그 반대도 마찬가지입니다.Paxos에서 학습된 이벤트의 시퀀스는 Gbcast의 일부 실행에서도 발생할 수 있습니다.

위에서 설명한 증명 유형은 공식적으로 바이 시뮬레이션이라고 불립니다. 하나는 한 프로토콜이 다른 프로토콜과 함께 나타낼 수 있는 모든 (입력 시퀀스, 출력 동작) 쌍이 가능하다는 것을 보여줍니다.이중 시뮬레이션을 수행할 때, 한 프로토콜은 지원하지만 다른 프로토콜은 부족한 기능은 연구 중인 "동작"의 일부로 간주되지 않을 경우 무시될 수 있습니다.예를 들어 새로운 뷰의 Gbcast 보고서(Paxos에 없는 이벤트)는 여기서 출력 이벤트로 취급되지 않습니다.

Paxos와 Gbcast의 차이점 요약

  • Gbcast에는 내구성이 없습니다.프로토콜은 디스크의 이벤트 로그를 유지하지 않으며 내구성은 애플리케이션 고유의 속성으로 취급됩니다.대조적으로 Paxos는 내구성을 보증합니다.시스템 셧다운에서 회복된 후에도 Paxos 애플리케이션은 수신된 메시지의 전체 로그를 학습할 수 있습니다.
  • 제안 단계에서 Gbcast는 가장 빠른 쿼럼으로 진행하는 것이 아니라 모든 참가자의 응답을 기다려야 합니다(또는 최대 타임아웃이 될 때까지 기다렸다가 나머지 참가자를 의심해야 합니다).Gbcast에서는 장애 의심 비용이 높고 너무 많은 장애가 의심되면 프로토콜의 진행이 중단되어 관리 계층이 전체 애플리케이션 그룹을 재시작해야 할 수 있습니다.따라서 실제로 Gbcast에서는 Paxos에 대해 보수적인 타임아웃 설정이 필요합니다.
  • Gbcast를 사용하면 오류가 발생할 경우(예를 들어 운영 프로세스가 의심되고 회피됨) 해당 프로세스는 중단되어야 합니다(다른 이름으로 다시 가입할 수 있음).Paxos를 사용하면 f>0인 경우 프로세스가 프로토콜 인스턴스에 참여할 수 없는 경우 오류 없이 후속 프로토콜 인스턴스에 계속 참여할 수 있습니다.
  • 뷰의 동작 멤버는 Gbcast와의 명령어목록에 공백이 없습니다(모든 멤버는 완전한 상태를 가집니다).Paxos를 사용할 때 운영 멤버의 명령어목록에 공백이 생길 수 있습니다(학습자는 이러한 공백을 메우기 위해 Paxos의 목록 쿼럼을 병합합니다).
  • 파크시되지만 이런 경우에는 명령에 제소되었고 이것은 질서에서 벗어나 다른 순서대로(이 문제가 되는 시나리오를 본 적은 한가지 경우 지도자들 대결을 포함하는데 전념할 수 있고, alpha&gt를 사용하는 여러 명령 1을 제안하는 것을 제창한 A을 제안하는 명령 a1과 a2, 그리고 지도자 B를 제안하고 명령을 b1과 b2;둘 다 그때 실패하세요음.정말C가 이어받으면 결국 b2를 커밋하고 a1: 요구를 시작한 어플리케이션에 의해 바람직하지 않을 수 있는 결과가 됩니다.Gbcast를 사용하면 리더는 일련의 액션을 설명하는 단일 제안을 발행하여 여러 명령을 시작할 수 있습니다.그룹이 한꺼번에 커밋되기 때문에 개시 순서가 존중됩니다.
  • Gbcast에서는 명령어가 시작된 뷰에서 전달됩니다.재구성 가능한 Paxos는 커밋 발생 시 액티브한 멤버십뷰에 앞서 멤버십뷰와 관련된 슬롯에서 명령어를 커밋할 수 있습니다.따라서 Paxos에서는 응용 프로그램이 어떤 방식으로든 뷰에 민감한 경우 수신자가 명령어를 실행할 수 있는지 여부를 판단할 수 있도록 명령어는 뷰 식별자를 전송해야 합니다.
  • Gbcast는 구성 변경 시 프로토콜을 중단할 필요가 없습니다. 새 제안의 속도는 구성원 자격 변경 중에도 일정할 수 있습니다.재구성 가능한 Paxos의 많은 구현에서는 그렇지 않습니다.
  • Gbcast와 Paxos를 모두 사용하면 이전 뷰의 쿼럼에 액세스할 수 있고 새 뷰를 확인할 수 있는 경우에만 재구성이 가능합니다.단, Paxos에서는 이전 뷰와 관련된 슬롯에 대해 제안된 명령어의 결과를 학습하는 데에도 요건이 적용됩니다.실제로 이로 인해 Paxos 재구성 계산이 Gbcast보다 장기간에 걸쳐 연장될 수 있습니다.이 경우 응용 프로그램 내에 상태가 저장되며 수명이 긴 명령어리스트가 아닙니다.Paxos는 새로운 뷰가 활성화되고 모든 복제본이 오래된 상태를 학습할 때까지 오래된 뷰와 관련된 상태를 폐기할 수 없습니다.
  • Gbcast에는 가비지 컬렉션 프로토콜이 필요하지 않습니다. 각 메시지 또는 보기가 커밋되어 애플리케이션에 보고될 때 가비지 컬렉션 프로토콜을 폐기할 수 있기 때문입니다.Paxos는 명령 로그의 쿼럼 체계를 사용하여 수용기에서 상태를 유지하고 결과가 커밋되고 모든 학습자(복제)가 결과를 학습한 후 이러한 명령 슬롯을 해방하기 위해 가비지 컬렉션 프로토콜을 필요로 합니다.

라이브스 비교

Paxos와 Gbcast는 모두 FLP 불가의 [9]결과를 받습니다.따라서 어떤 프로토콜도 가능한 모든 조건에서 라이브를 보장할 수 없습니다.기껏해야 장애 검출 메커니즘의 술어로 표현되는 활성 상태가 보장되는 조건에 대해 이야기할 수 있습니다. 활성 상태가 유지되면 프로토콜이 활성화됩니다.Basic Paxos와 Gbcast의 존속 조건은 비슷하지만 동일하지는 않습니다.

Gbcast에서는 위에서 언급한 바와 같이 상호의혹의 순환이 일어나면 진전은 결코 재개되지 않을 것이다. 즉, 일단 상호 회피하는 과정의 쿼럼이 발생하면, 어떤 지도자도 약속의 쿼럼을 얻는 것이 불가능해진다.

(수정되지 않은) Paxos 프로토콜을 사용하면 이 문제가 발생하지 않습니다. 즉, 과도한 수준의 상호 의혹이 종료되면 진행이 재개됩니다.따라서 Paxos는 상호 의심 쿼럼 이상이 발생하는 기간이 발생하더라도 <>W 조건을 충족하는 장애 검출 메커니즘에서 진전을 이룹니다.

예를 들어 {A}이(가) 포함된 그룹으로 시작하는 경우입니다.B,C}를 사용하면 네트워크 파티션이 확인되면 Paxos가 재개되지만 Gbcast가 영구적으로 종료되고 어떤 형태의 관리 인프라스트럭처가 시스템을 재시작해야 할 수 있습니다.장애 발생 시 그룹 상태를 유지해야 하는 경우 이러한 인프라스트럭처는 마지막으로 장애가 발생한 멤버를 식별하고 해당 마지막 멤버가 저장한 체크포인트를 사용하여 그룹을 재시작합니다.

Paxos 배치에서는 일반적으로 Paxos를 재구성하기 위해 작업자의 개입이 필요합니다.이러한 설정에서는 Gbcast는 Paxos가 진행할 수 없는 기간 동안 진행할 수 있습니다.그룹에 원래 그룹 크기의 쿼럼 미만으로 천천히 떨어지는 구성원 자격이 있다고 가정합니다.Gbcast는 한 명의 멤버로도 계속 작동할 수 있습니다.Paxos는 뷰의 정족수 미만이 활성화 되어 있는 기간에는 진전을 보지 못합니다.

상태 이전 필요성

Gbcast를 구현하는 Isis 등의 시스템에서는 일반적으로 상태 전송 메커니즘이 제공됩니다.새 뷰에 가입 멤버를 나타내는 일부 기존 멤버가 그룹 상태의 복사본을 체크포인트로 만듭니다.그런 다음 새로운 멤버에 복사됩니다.이 멤버는 가입된 시점에서 체크포인트를 초기 그룹 상태로 로드합니다(다양한 대역외 복사 방식을 사용하여 가입 전에 상태를 프리로드할 수 있습니다.이 방법은 상태가 너무 커서 마지막 순간에 전송할 수 없는 경우입니다.Gbcast에서는 멤버가 그룹에서 삭제되면 갱신이 수신되지 않기 때문에 스테이트 전송이 필요합니다.Gbcast는 일반적으로 메모리 상태를 유지하고 수신 시 업데이트를 하나씩 적용하는 응용 프로그램에서 사용되기 때문에 갭이 발생하면 복제품은 더 이상 유용하지 않습니다.

이는 Paxos와 대조적입니다.이 프로토콜에서는 기본 쿼럼 업데이트 체계의 결과로 공백이 발생할 수 있습니다. 이 체제는 모든 구성원이 모든 업데이트를 볼 수 있음을 보장하지 않으며 일부 메시지를 전달하지 않을 수 있는 신뢰할 수 없는 메시지 전달 계층에서 실행될 수 있습니다.Paxos 학습자 알고리즘은 여러 이력을 읽고 이러한 차이를 메우기 위해 결합합니다.따라서 Paxos는 일반적으로 일시적인 장애를 극복하고 장애가 발생한 멤버를 그룹에서 실제로 삭제하지 않고 계속 작동합니다.실패한 멤버는 업데이트를 놓치지만 그룹을 재설정하지 않는 한 상태 전송은 필요하지 않습니다.

동적으로 재구성 가능한 시스템 복제 프로토콜은 무엇입니까?

Gbcast 프로토콜은 Gbcast, View-Stamped Replication(Oki 및 Liskov), Basic Paxos(Lamport), Dwork, Lynch 및 Stockmeyer의 [13]부분 동기 프로토콜 등 자체 멤버쉽을 관리할 수 있는 여러 상태 시스템 프로토콜이 도입된 초기에 공개되었습니다.이 중 Gbcast는 1985년과 1987년에 발표된 논문 중 가장 먼저 발표되었으며, 다른 논문들은 1988년부터 발표되었습니다.따라서 Gbcast가 실제로 최초의 Paxos 프로토콜이라고 주장할 수 있다.그러나 이러한 문장은 "Paxos"를 모두 상태 기계 복제를 구현하고, 구성원 자격의 동적 재구성을 지원하며, 동일한 정확성 속성을 가지지만 활성 조건이 다른 프로토콜 패밀리를 포함하는 매우 광범위한 용어로 취급합니다.이 정의에 따르면 Gbcast는 Paxos 프로토콜입니다.

한 프로토콜이 보여줄 수 있는 모든 실행이 다른 프로토콜에 의해 제시되고 가정과 진행 조건이 동일한 경우, 등가성이 이중 시뮬레이션을 사용하여 공식화되면 비교는 더욱 복잡해진다.이 정의에 따르면 Gbcast는 Paxos 프로토콜이 아닙니다. 각 프로토콜은 다른 프로토콜과 동일한 실행을 나타낼 수 있지만(어플리케이션으로부터의 요청과 애플리케이션에 대한 알림의 관점에서만 볼 수 있음), 두 프로토콜은 비슷하지만 동일하지는 않습니다.그러나 이러한 엄격한 정의는 다른 문제를 일으킵니다. 이를 채택할 경우 Paxos의 일부 버전은 Paxos 프로토콜이 아닙니다.예를 들어 "저렴한 팩소스"와 "수직 팩소스"는 기본 [14]팩소스와 동일한 바이시뮬레이션이 아닙니다.

따라서 그 질문은 좀 더 구체적으로 말하지 않으면 답이 없고, 사용하는 동등성의 정의에 따라 다른 답이 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Birman, Kenneth (Dec 1985). Replication and Fault-Tolerance in the ISIS System. 10th ACM Symposium on Operating Systems Principles. pp. 79–86.
  2. ^ a b Birman, Kenneth; Joseph, Thomas (February 1987). "Reliable Communication in the Presence of Failures" (PDF). ACM Transactions on Computer Systems. 5: 47–76. doi:10.1145/7351.7478.
  3. ^ a b Birman, Kenneth (July 1999). "A Review of Experiences with Reliable Multicast". Software: Practice and Experience. 29 (9): 741–774. doi:10.1002/(sici)1097-024x(19990725)29:9<741::aid-spe259>3.0.co;2-i. hdl:1813/7380.
  4. ^ a b 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. Retrieved 2007-02-02.
  5. ^ a b c Lamport, Leslie (May 1998). "The Part-Time Parliament". ACM Transactions on Computer Systems. 16 (2): 133–169. doi:10.1145/279227.279229. Retrieved 2007-02-02.
  6. ^ Schneider, Fred (1990). "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial" (PDF). ACM Computing Surveys. 22 (4): 299–319. doi:10.1145/98163.98167.
  7. ^ a b Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (March 2010). "Reconfiguring a State Machine". SIGACT News. 41 (1): 63–73. doi:10.1145/1753171.1753191.
  8. ^ Pease, Marshall; Robert Shostak; Leslie Lamport (April 1980). "Reaching Agreement in the Presence of Faults". Journal of the Association for Computing Machinery. 27 (2): 228–234. doi:10.1145/322186.322188. Retrieved 2007-02-02.
  9. ^ a b 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.
  10. ^ Lamport, Leslie; Robert Shostak; Marshall Pease (July 1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. doi:10.1145/357172.357176. Retrieved 2007-02-02.
  11. ^ Birman, Ken; Dahlia Malkhi; Robbert van Renesse (November 2011). "Virtually Synchronous Methodology for Dynamic Service Replication" (PDF). Microsoft Research TechReport MSR-2010-151. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  12. ^ Oki, Brian; Barbara Liskov (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. pp. 8–17. doi:10.1145/62546.62549.
  13. ^ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). "Consensus in the Presence of Partial Synchrony" (PDF). Journal of the ACM. 35 (2): 288–323. doi:10.1145/42282.42283.
  14. ^ Lamport, Leslie (2012). Unpublished remark.