상자 없는 슈뢰딩거의 고양이: 분산 시스템의 합의 문제

그럼 상상해 봅시다. 방에는 5마리의 고양이가 갇혀 있는데, 주인을 깨우러 가기 위해서는 서로 동의해야 합니다. XNUMX마리가 기대어 있어야만 문을 열 수 있기 때문입니다. 고양이 중 한 마리가 슈뢰딩거의 고양이이고 다른 고양이들은 그의 결정에 대해 알지 못한다면 "어떻게 할 수 있습니까?"라는 질문이 생깁니다.

이 기사에서는 분산 시스템 세계의 이론적 구성 요소와 작동 원리에 대해 간단한 용어로 설명하겠습니다. 또한 Paxos의 기본 아이디어를 피상적으로 검토하겠습니다.

개발자가 클라우드 인프라, 다양한 데이터베이스를 사용하고 다수의 노드로 구성된 클러스터에서 작업할 때 데이터가 완전하고 안전하며 항상 사용할 수 있다고 확신합니다. 하지만 보장은 어디에 있습니까?

기본적으로 우리가 제공하는 보증은 공급업체 보증입니다. 문서에는 다음과 같이 설명되어 있습니다. "이 서비스는 매우 안정적입니다. 지정된 SLA가 있으므로 걱정하지 마십시오. 모든 것이 예상대로 분산되어 작동합니다."

우리는 최고를 믿는 경향이 있습니다. 대기업의 똑똑한 사람들이 모든 것이 잘 될 것이라고 확신했기 때문입니다. 우리는 질문하지 않습니다. 실제로 이것이 왜 작동할 수 있습니까? 그러한 시스템의 올바른 작동에 대한 공식적인 정당성이 있습니까?

나는 최근에 갔다 분산컴퓨팅학부 그리고 이 주제에서 많은 영감을 받았습니다. 학교 강의는 컴퓨터 시스템에 관한 강의라기보다는 미적분학 수업에 가까웠습니다. 하지만 이것이 바로 우리가 매일 사용하는 가장 중요한 알고리즘이 자신도 모르게 한 번에 입증된 방법입니다.

대부분의 최신 분산 시스템은 Paxos 합의 알고리즘과 다양한 수정 사항을 사용합니다. 가장 멋진 점은 이 알고리즘의 타당성과 원칙적으로 존재 가능성이 펜과 종이만으로 간단하게 입증될 수 있다는 것입니다. 실제로 이 알고리즘은 클라우드의 수많은 노드에서 실행되는 대규모 시스템에 사용됩니다.

다음에 논의될 내용에 대한 간단한 설명: 두 장군의 임무워밍업을 살펴보자 두 장군의 임무.

우리에게는 빨간색과 흰색의 두 군대가 있습니다. 백인 군대는 포위된 도시에 주둔하고 있습니다. 장군 A1과 A2가 이끄는 붉은 군대는 도시의 양쪽에 위치해 있습니다. 빨간 머리의 임무는 백인 도시를 공격하고 승리하는 것입니다. 그러나 각 붉은 장군의 군대는 개별적으로 백군보다 작습니다.

적색군의 승리 조건: 백색군에 비해 수적 우위를 확보하려면 두 장군이 동시에 공격해야 합니다. 이를 위해서는 장군 A1과 A2가 서로 합의해야 합니다. 모두가 따로 공격하면 빨간 머리가 패배합니다.

합의에 도달하기 위해 장군 A1과 A2는 백색 도시의 영토를 통해 서로에게 메신저를 보낼 수 있습니다. 메신저는 연합군 장군에게 성공적으로 도달할 수도 있고, 적에게 차단될 수도 있습니다. 질문: 빨간 머리 장군들 사이에 X 시간에 공격에 동의하는 일련의 통신이 있습니까(A1에서 A2로 또는 그 반대로 A2에서 A1로 메신저를 보내는 순서). 여기서, 보장은 두 장군이 동맹국(다른 장군)이 지정된 시간에 확실히 공격할 것이라는 명확한 확인을 갖는다는 것을 의미합니다 X.

A1이 A2에게 "오늘 자정에 공격하자!"라는 메시지와 함께 메신저를 보낸다고 가정해 보겠습니다. 장군 A1은 장군 A2의 확인 없이는 공격할 수 없습니다. A1의 메신저가 도착하면 A2 장군은 "예, 오늘 백인을 죽이자"라는 메시지와 함께 확인 메시지를 보냅니다. 그러나 이제 A2 장군은 그의 메신저가 도착했는지 여부를 알지 못하며 공격이 동시인지 여부도 보장할 수 없습니다. 이제 일반 A2는 다시 확인이 필요합니다.

그들의 통신을 더 자세히 설명하면 메시지 교환 주기가 아무리 많아도 두 장군이 메시지를 받았다는 것을 보장할 수 있는 방법이 없다는 것이 분명해집니다(두 메신저 중 하나를 가로챌 수 있다고 가정).

두 장군 문제는 통신이 불안정한 두 개의 노드가 있는 매우 간단한 분산 시스템을 잘 보여줍니다. 즉, 동기화가 100% 보장되지는 않습니다. 유사한 문제는 기사 뒷부분에서 더 큰 규모로 논의됩니다.

분산 시스템의 개념을 소개합니다.

분산 시스템은 메시지를 교환할 수 있는 컴퓨터 그룹(이하 노드라고 함)입니다. 각 개별 노드는 일종의 자율적 개체입니다. 노드는 스스로 작업을 처리할 수 있지만 다른 노드와 통신하려면 메시지를 보내고 받아야 합니다.

메시지가 정확히 어떻게 구현되는지, 어떤 프로토콜이 사용되는지 등은 이 맥락에서 우리에게 중요하지 않습니다. 분산 시스템의 노드들은 서로 메시지를 보내 데이터를 교환할 수 있다는 것이 중요하다.

정의 자체는 그다지 복잡해 보이지 않지만 분산 시스템에는 우리에게 중요한 여러 가지 속성이 있다는 점을 고려해야 합니다.

분산 시스템의 속성

1. 동시성 – 시스템에서 동시 또는 동시 이벤트가 발생할 가능성. 더욱이, 우리는 이러한 이벤트의 명확한 발생 순서가 없는 한 두 개의 서로 다른 노드에서 발생하는 이벤트를 잠재적으로 동시에 발생하는 것으로 간주합니다. 그러나 원칙적으로 우리는 그것을 가지고 있지 않습니다.
2. 글로벌 시계 없음. 글로벌 시계가 없기 때문에 명확한 이벤트 순서가 없습니다. 평범한 사람들의 세계에서 우리는 시계와 시간이 절대적으로 있다는 사실에 익숙합니다. 분산 시스템에 관해서는 모든 것이 변합니다. 초정밀 원자시계에도 드리프트가 있어서, 두 가지 사건 중 어느 것이 먼저 일어났는지 알 수 없는 상황이 있을 수 있습니다. 그러므로 우리도 시간에 의존할 수 없습니다.
3. 시스템 노드의 독립적인 오류. 또 다른 문제가 있습니다. 노드가 영원히 지속되지 않기 때문에 문제가 발생할 수 있습니다. 하드 드라이브에 오류가 발생하고, 클라우드의 가상 머신이 재부팅되고, 네트워크가 깜박이고 메시지가 손실될 수 있습니다. 또한 노드가 작동하지만 동시에 시스템에 반대되는 상황이 있을 수 있습니다. 문제의 마지막 클래스에는 문제라는 별도의 이름이 붙었습니다. 비잔틴 장군. 이 문제를 안고 있는 분산 시스템의 가장 유명한 예는 블록체인입니다. 그러나 오늘 우리는 이 특별한 종류의 문제를 고려하지 않을 것입니다. 우리는 단순히 하나 이상의 노드가 실패할 수 있는 상황에 관심을 가질 것입니다.
4. 노드 간 통신 모델(메시징 모델). 우리는 노드가 메시지를 교환하여 통신한다는 것을 이미 확립했습니다. 잘 알려진 메시징 모델에는 동기식과 비동기식의 두 가지 모델이 있습니다.

분산 시스템의 노드 간 통신 모델

동기식 모델 – 우리는 메시지가 한 노드에서 다른 노드로 도달하는 것이 보장되는 시간의 유한한 델타가 있다는 것을 확실히 알고 있습니다. 이 시간이 지나도 메시지가 도착하지 않으면 노드가 실패했다고 안전하게 말할 수 있습니다. 이 모델에서는 예측 가능한 대기 시간이 있습니다.

비동기식 모델 – 비동기식 모델에서는 대기 시간이 유한하다고 생각하지만 노드가 실패했다고 보장할 수 있는 시간 차이는 없습니다. 저것들. 노드의 메시지 대기 시간은 임의로 길어질 수 있습니다. 이것은 중요한 정의이므로 이에 대해 더 자세히 설명하겠습니다.

분산 시스템의 합의 개념

합의의 개념을 공식적으로 정의하기 전에 합의가 필요한 상황의 예를 살펴보겠습니다. 상태 머신 복제.

배포된 로그가 있습니다. 우리는 그것이 일관되고 분산 시스템의 모든 노드에 동일한 데이터를 포함하기를 원합니다. 노드 중 하나가 로그에 쓸 새 값을 학습하면 해당 작업은 이 값을 다른 모든 노드에 제공하여 모든 노드에서 로그가 업데이트되고 시스템이 새로운 일관된 상태로 이동하게 됩니다. 이 경우 노드가 서로 동의하는 것이 중요합니다. 모든 노드는 제안된 새 값이 정확하다는 데 동의하고, 모든 노드는 이 값을 수락하며, 이 경우에만 모든 사람이 새 값을 로그에 쓸 수 있습니다.

즉, 더 관련성이 높은 정보가 있고 제안된 값이 올바르지 않다고 반대하는 노드가 하나도 없었습니다. 노드 간의 합의와 하나의 올바른 허용 값에 ​​대한 합의는 분산 시스템에서의 합의입니다. 다음으로, 분산 시스템이 합의에 도달하도록 보장하는 알고리즘에 대해 이야기하겠습니다.

보다 공식적으로는 합의 알고리즘(또는 간단히 합의 알고리즘)을 분산 시스템을 A 상태에서 B 상태로 이전하는 특정 기능으로 정의할 수 있습니다. 또한 이 상태는 모든 노드에서 수락되며 모든 노드에서 이를 확인할 수 있습니다. 알고 보니 이 작업은 언뜻 보기에 그렇게 사소한 것이 아닙니다.

합의 알고리즘의 속성

시스템이 계속해서 존재하고 상태에서 상태로 이동하는 과정에서 어느 정도 진전을 이루려면 합의 알고리즘에는 세 가지 속성이 있어야 합니다.

1. 협약 – 올바르게 작동하는 모든 노드는 동일한 값을 가져야 합니다(문서에서는 이 속성을 안전 속성이라고도 함). 현재 작동 중인 모든 노드(다른 노드와의 연결이 끊어지거나 실패하지 않은)는 합의에 도달하고 최종 공통 값을 수락해야 합니다.

   여기서 우리가 고려하고 있는 분산 시스템의 노드가 동의하기를 원한다는 점을 이해하는 것이 중요합니다. 즉, 우리는 이제 무언가가 단순히 실패할 수 있는 시스템(예: 일부 노드 실패)에 대해 이야기하고 있지만 이 시스템에는 의도적으로 다른 노드에 대해 작동하는 노드(비잔틴 장군의 작업)가 확실히 없습니다. 이 속성으로 인해 시스템은 일관성을 유지합니다.

2. 진실성 — 올바르게 작동하는 모든 노드가 동일한 값을 제공하는 경우 v이는 올바르게 작동하는 모든 노드가 이 값을 수락해야 함을 의미합니다. v.
3. 종료 – 올바르게 작동하는 모든 노드는 결국 특정 값(활성 속성)을 갖게 되며, 이를 통해 알고리즘이 시스템에서 진전을 이룰 수 있습니다. 올바르게 작동하는 각 개별 노드는 조만간 최종 값을 수락하고 확인해야 합니다. "나에게는 이 값이 사실이며 전체 시스템에 동의합니다."

합의 알고리즘의 작동 방식에 대한 예

알고리즘의 속성이 완전히 명확하지 않을 수 있습니다. 따라서 우리는 모든 노드가 예상대로 작동하고 메시지가 손실되지 않고 중단되지 않는 동기식 메시징 모델을 사용하는 시스템에서 가장 간단한 합의 알고리즘이 어떤 단계를 거치는지 예를 통해 설명할 것입니다(이것이 실제로 발생합니까?).

1. 모든 것은 결혼 제안(Propose)으로 시작됩니다. 클라이언트가 "Node 1"이라는 노드에 연결되어 트랜잭션을 시작하고 노드 O에 새로운 값을 전달한다고 가정해 보겠습니다. 이제부터 "Node 1"을 호출하겠습니다. 제공. 제안자로서 "노드 1"은 이제 전체 시스템에 새로운 데이터가 있음을 알려야 하며 다른 모든 노드에 메시지를 보냅니다. "보세요! "오"라는 뜻이 떠올라서 적어보고 싶어요! 로그에도 "O"가 기록되는지 확인하시기 바랍니다.

   

2. 다음 단계는 제안된 가치에 대한 투표(Voting)입니다. 그것은 무엇을 위한 것입니까? 다른 노드가 더 최근의 정보를 수신하고 동일한 트랜잭션에 대한 데이터를 가지고 있는 경우가 발생할 수 있습니다.

   
   
   노드 "노드 1"이 제안을 보내면 다른 노드는 이 이벤트에 대한 데이터에 대한 로그를 확인합니다. 모순이 없으면 노드는 다음과 같이 발표합니다. “예, 이 이벤트에 대한 다른 데이터가 없습니다. "O" 값은 우리가 마땅히 받아야 할 최신 정보입니다."

   다른 경우에는 노드가 "노드 1"에 응답할 수 있습니다. "들어보세요! 이 거래에 대한 최신 데이터가 있습니다. 'O'가 아니라 더 나은 것입니다."

   투표 단계에서 노드는 결정을 내립니다. 노드는 모두 동일한 값을 수락할지 아니면 노드 중 하나가 반대 투표를 하여 해당 노드가 최신 데이터를 가지고 있음을 나타냅니다.

3. 투표가 성공적으로 이루어지고 모든 사람이 찬성하면 시스템은 가치 수용이라는 새로운 단계로 이동합니다. “노드 1”은 다른 노드로부터 모든 응답을 수집하고 다음과 같이 보고합니다. “모두가 “O” 값에 동의했습니다! 이제 저는 “O”가 우리의 새로운 의미이며 모든 사람에게 동일함을 공식적으로 선언합니다! 그것을 당신의 작은 책에 적어 두십시오. 잊지 마십시오. 일지에 적어 두세요!”

   

4. 나머지 노드는 "O" 값을 기록했다는 확인(Accepted)을 보냅니다. 이 시간 동안 새로운 것은 아무것도 도착하지 않았습니다(일종의 XNUMX단계 커밋). 이 중요한 이벤트가 끝나면 분산 트랜잭션이 완료된 것으로 간주합니다.
   

따라서 간단한 경우 합의 알고리즘은 제안, 투표(투표), 수락(수락), 수락 확인(수락)의 네 단계로 구성됩니다.

어떤 단계에서 합의에 도달할 수 없는 경우 제안된 값 확인을 거부한 노드가 제공한 정보를 고려하여 알고리즘이 다시 시작됩니다.

비동기 시스템의 합의 알고리즘

그 전에는 동기식 메시징 모델에 대해 이야기했기 때문에 모든 것이 순조롭게 진행되었습니다. 그러나 우리는 현대 사회에서 모든 것을 비동기식으로 수행하는 데 익숙하다는 것을 알고 있습니다. 노드의 응답을 기다리는 시간이 임의로 길 수 있다고 생각하는 비동기 메시징 모델을 사용하는 시스템에서 유사한 알고리즘이 어떻게 작동합니까? (그런데 노드의 실패도 다음과 같은 경우에 예로 간주될 수 있습니다.) 노드는 임의로 오랜 시간 동안 응답할 수 있습니다.)

이제 우리는 합의 알고리즘이 원칙적으로 어떻게 작동하는지 알았으므로 여기까지 온 호기심 많은 독자들을 위한 질문입니다. 비동기 메시지 모델을 사용하는 N 노드 시스템에서 시스템이 여전히 합의에 도달할 수 있도록 실패할 수 있는 노드 수는 몇 개입니까?

정답과 정당성은 스포일러 뒤에 있습니다.정답은 다음과 같습니다. 0. 비동기식 시스템에서는 노드 하나라도 실패하면 시스템은 합의에 도달할 수 없습니다. 이 진술은 특정 집단에서 잘 알려진 FLP 정리(1985, Fischer, Lynch, Paterson, 기사 끝 부분의 원본 링크)에서 입증되었습니다. “적어도 하나의 노드가 실패하면 분산 합의를 달성하는 것이 불가능합니다. .”

여러분, 그러면 문제가 생겼습니다. 우리는 모든 것이 비동기적인 것에 익숙합니다. 그리고 여기 있습니다. 계속 사는 방법?

우리는 이론과 수학에 대해서만 이야기하고 있었습니다. "합의를 이룰 수 없다"는 것은 수학적 언어를 우리의 언어인 공학으로 번역할 때 무엇을 의미합니까? 이는 "항상 달성될 수는 없다"는 의미입니다. 합의가 이루어지지 않는 경우도 있습니다. 이것은 어떤 경우인가요?

이는 바로 위에서 설명한 활성 속성을 위반하는 것입니다. 우리는 공통의 합의를 갖고 있지 않으며, 모든 노드로부터 응답이 없는 경우 시스템은 진전을 이룰 수 없습니다(한정된 시간 내에 완료할 수 없음). 비동기식 시스템에서는 예측 가능한 응답 시간이 없으며 노드가 충돌했는지 또는 응답하는 데 오랜 시간이 걸리는지 알 수 없기 때문입니다.

그러나 실제로 우리는 해결책을 찾을 수 있습니다. 오류가 발생할 경우 알고리즘이 오랫동안 작동할 수 있도록 하십시오(잠재적으로 무기한 작동할 수 있음). 그러나 대부분의 상황에서 대부분의 노드가 올바르게 작동하면 시스템이 발전하게 됩니다.

실제로 우리는 부분적으로 동기식 통신 모델을 다룹니다. 부분 동기화는 다음과 같이 이해됩니다. 일반적인 경우 비동기 모델이 있지만 특정 시점의 "전역 안정화 시간"이라는 특정 개념이 공식적으로 도입되었습니다.

이 순간은 한동안 오지 않을 수도 있지만 언젠가는 반드시 옵니다. 가상 알람 시계가 울리고 그 순간부터 메시지가 도착할 시간 델타를 예측할 수 있습니다. 이 순간부터 시스템은 비동기식에서 동기식으로 전환됩니다. 실제로 우리는 그러한 시스템을 정확하게 다루고 있습니다.

Paxos 알고리즘은 합의 문제를 해결합니다.

Paxos 일부 노드가 실패할 가능성이 있는 부분 동기식 시스템의 합의 문제를 해결하는 알고리즘 제품군입니다. 팩소스의 저자는 레슬리 램 포트. 그는 1989년에 알고리즘의 존재와 정확성에 대한 공식적인 증명을 제안했습니다.

그러나 그 증거는 결코 사소한 것이 아닌 것으로 드러났습니다. 알고리즘을 설명하는 첫 번째 출판물은 1998년에야 발표되었습니다(33페이지). 결과적으로 이해하기가 매우 어려웠으며 2001 년에 14 페이지에 달하는 기사 설명이 출판되었습니다. 실제로 합의 문제가 전혀 단순하지 않으며 그러한 알고리즘 뒤에는 가장 똑똑한 사람들의 엄청난 양의 작업이 있음을 보여주기 위해 출판물의 양이 제공됩니다.

Leslie Lamport 자신이 강의에서 두 번째 설명 기사에는 하나의 진술, 한 줄(어느 줄인지 명시하지 않음)이 있으며 다른 방식으로 해석될 수 있다고 지적한 것은 흥미 롭습니다. 그리고 이로 인해 많은 현대 Paxos 구현이 완전히 올바르게 작동하지 않습니다.

Paxos의 작업에 대한 자세한 분석에는 하나 이상의 기사가 필요하므로 알고리즘의 주요 아이디어를 아주 간략하게 전달하려고 노력할 것입니다. 내 기사 끝에 있는 링크에서 이 주제에 대해 더 자세히 알아볼 수 있는 자료를 찾을 수 있습니다.

Paxos에서의 역할

Paxos 알고리즘에는 역할이라는 개념이 있습니다. 세 가지 주요 사항을 고려해 보겠습니다(추가 역할에 대한 수정 사항이 있음).

1. 제안자(리더 또는 조정자라는 용어도 사용될 수 있음). 사용자로부터 새로운 가치를 배우고 리더의 역할을 맡은 사람들입니다. 그들의 임무는 새로운 가치에 대한 일련의 제안을 시작하고 노드의 추가 조치를 조정하는 것입니다. 또한 Paxos는 특정 상황에서 여러 리더의 존재를 허용합니다.
2. 수락자(유권자). 이는 특정 값을 수락하거나 거부하기 위해 투표하는 노드입니다. 합의 알고리즘의 다음 단계 이후 시스템이 어떤 상태로 갈 것인지(또는 가지 않을 것인지) 결정이 그들에 달려 있기 때문에 그들의 역할은 매우 중요합니다.
3. 학습. 시스템 상태가 변경되면 단순히 새로운 허용 값을 받아들이고 쓰는 노드입니다. 그들은 결정을 내리지 않으며 단지 데이터를 수신하여 최종 사용자에게 제공할 수 있습니다.

하나의 노드는 다양한 상황에서 여러 역할을 결합할 수 있습니다.

쿼럼의 개념

우리는 다음과 같은 시스템을 가지고 있다고 가정합니다. N 노드 그리고 그 중 최대 F 노드가 실패할 수 있습니다. F 노드가 실패하면 최소한 2F+1 수락자 노드.

이는 최악의 상황에서도 올바르게 작동하는 "좋은" 노드의 대부분을 항상 확보하기 위해 필요합니다. 그건 여 + 1 동의한 "좋은" 노드와 최종 값이 수락됩니다. 그렇지 않으면 우리의 서로 다른 지역 그룹이 서로 다른 의미를 가지며 서로 동의하지 못하는 상황이 발생할 수 있습니다. 따라서 투표에서 승리하려면 절대 다수가 필요합니다.

Paxos 합의 알고리즘의 작동 방식에 대한 일반적인 아이디어

Paxos 알고리즘에는 두 개의 큰 단계가 포함되며, 이는 차례로 각각 두 단계로 나뉩니다.

1. 1a단계: 준비. 준비 단계에서 리더(제안자)는 모든 노드에 다음과 같이 알립니다. “우리는 새로운 투표 단계를 시작합니다. 새로운 라운드가 생겼습니다. 이번 라운드의 수는 n입니다. 이제 투표를 시작하겠습니다." 현재로서는 새 주기의 시작만 보고할 뿐 새 값은 보고하지 않습니다. 이 단계의 임무는 새로운 라운드를 시작하고 모든 사람에게 고유 번호를 알리는 것입니다. 라운드 번호가 중요합니다. 이는 모든 이전 리더의 이전 투표 번호보다 더 큰 값이어야 합니다. 시스템의 다른 노드가 리더의 데이터가 얼마나 최근인지 이해할 수 있는 것은 라운드 수 덕분이기 때문입니다. 다른 노드는 이미 훨씬 나중 라운드의 투표 결과를 갖고 있으며 단순히 리더에게 그가 시대에 뒤처져 있다고 말할 것입니다.
2. 1b단계: 약속. 수락자 노드가 새로운 투표 단계의 번호를 받으면 두 가지 결과가 가능합니다.
   • 새 투표의 수 n은 수락자가 참여한 이전 투표의 수보다 큽니다. 그런 다음 Acceptor는 n보다 낮은 숫자의 투표에 더 이상 참여하지 않겠다는 약속을 리더에게 보냅니다. Acceptor가 이미 무언가에 투표한 경우(즉, 두 번째 단계에서 이미 일부 값을 수락한 경우) 수락된 값과 참여한 투표 수를 약속에 첨부합니다.
   • 그렇지 않고 Acceptor가 이미 높은 숫자의 투표에 대해 알고 있는 경우 준비 단계를 무시하고 리더에 응답하지 않을 수 있습니다.
3. 2a단계: 수락. 리더는 쿼럼(시스템의 대다수 노드)의 응답을 기다려야 하며, 필요한 수의 응답이 수신되면 이벤트 개발을 위한 두 가지 옵션이 있습니다.
   • Acceptor 중 일부는 이미 투표한 값을 보냈습니다. 이 경우 리더는 투표에서 최대 개수의 값을 선택합니다. 이 값을 x라고 부르면 "Accept (n, x)"와 같은 메시지를 모든 노드에 보냅니다. 여기서 첫 번째 값은 자체 제안 단계의 투표 번호이고 두 번째 값은 모두가 모인 것입니다. 즉. 우리가 실제로 투표하는 가치.
   • Acceptor 중 어느 누구도 값을 보내지 않았지만 단순히 이번 라운드에서 투표하겠다고 약속한 경우, 리더는 자신이 리더가 된 가치에 대해 투표하도록 그들을 초대할 수 있습니다. 그것을 y라고 부르자. 이전 결과와 유사하게 "Accept (n, y)"와 같은 메시지를 모든 노드에 보냅니다.
4. 2b단계: 승인됨. 또한 수락자 노드는 리더로부터 "Accept(...)" 메시지를 수신하면 일부(기타)를 약속하지 않은 경우에만 이에 동의합니다(모든 노드에 새 값에 동의한다는 확인을 보냅니다). 라운드 번호로 투표에 참여하는 리더 엔' > 엔그렇지 않으면 확인 요청을 무시합니다.

   대다수의 노드가 리더에 응답하고 모두가 새 값을 확인한 경우 새 값이 수락된 것으로 간주됩니다. 만세! 다수에 도달하지 못하거나 새 값 수락을 거부하는 노드가 있는 경우 모든 것이 다시 시작됩니다.

이것이 Paxos 알고리즘이 작동하는 방식입니다. 이러한 각 단계에는 많은 미묘함이 있으며 실제로 다양한 유형의 실패, 여러 리더의 문제 등을 고려하지 않았지만 이 기사의 목적은 독자에게 높은 수준의 분산 컴퓨팅 세계를 소개하는 것입니다.

또한 Paxos가 이러한 종류의 유일한 알고리즘이 아니며 다른 알고리즘도 있다는 점도 주목할 가치가 있습니다. 뗏목, 그러나 이것은 다른 기사의 주제입니다.

추가 연구를 위한 자료 링크

초급 수준:

• 분산 합의는 어떻게 작동하나요?, Preethi Kasireddy, Medium 블로그 기사
• Paxos가 간단해졌습니다. 진짜로, Adi Kancherla, Medium 블로그 기사
• 분산된 생각, 잇타이 아브라함, 블로그
• 동기화, 비동기 및 부분 동기화, Ittai Abraham, 블로그 기사

레슬리 램포트 레벨:

• 하나의 잘못된 프로세스로 분산된 합의가 불가능함(FLP 불가능), Fischer, Lynch 및 Paterson, 연구 논문, 1985
• 시간제 의회, 레슬리 램포트(Leslie Lamport), 연구 논문, 1998
• 간단해진 Paxos, 레슬리 램포트(Leslie Lamport), 연구 논문, 2001

출처 : habr.com