캡 정리의 도시 된 증명

BY admin
|

캡 정리는 분산 시스템의 기본 정리이며,분산 시스템은 다음 세 가지 속성 중 최대 두 가지를 가질 수 있습니다.

  • 일관성
  • 가용성
  • 파티션 허용

이 가이드는 사진과 함께 길버트와 린치의 사양 및 캡 정리의 증거를 요약합니다!

캡 정리 란 무엇입니까?

캡 정리는 분산 시스템이 동시에 일관되고 사용 가능하며 파티션을 허용 할 수 없다고 명시합니다. 충분히 간단하게 들리지만 일관성이 있다는 것은 무엇을 의미합니까? 사용 가능? 파티션 허용? 지옥,당신은 심지어 분산 시스템에 의해 정확히 무엇을 의미합니까?

이 섹션에서는 간단한 분산 시스템을 소개하고 해당 시스템을 사용할 수 있고 일관성이 있으며 파티션을 허용한다는 것이 무엇을 의미하는지 설명합니다. 시스템 및 세 가지 속성에 대한 공식적인 설명은 길버트와 린치의 논문을 참조하십시오.

분산 시스템

매우 간단한 분산 시스템을 생각해 봅시다. 우리의 시스템은 두 개의 서버로 구성되어 있습니다. 이 두 서버 모두 동일한 변수를 추적하고 있습니다. $지 _1$와$지 _2$는 서로 통신 할 수 있으며 외부 클라이언트와도 통신 할 수 있습니다. 여기에 우리의 시스템이 어떻게 생겼는지입니다.

클라이언트는 모든 서버에서 쓰기 및 읽기를 요청할 수 있습니다. 서버가 요청을 받으면 원하는 계산을 수행한 다음 클라이언트에 응답합니다. 예를 들어,여기에 쓰기가 어떻게 생겼는지입니다.

그리고 여기에 읽기가 어떻게 생겼는지입니다.

이제 시스템을 구축했으므로 시스템이 일관성 있고 사용 가능하며 파티션 허용이 무엇인지 살펴 보겠습니다.

일관성

길버트와 린치가 일관성을 설명하는 방법은 다음과 같습니다.

쓰기 작업이 완료된 후 시작되는 모든 읽기 작업은 해당 값 또는 이후 쓰기 작업의 결과를 반환해야 합니다.

일관된 시스템에서 클라이언트가 서버에 값을 쓰고 응답을 받으면 읽은 모든 서버에서 해당 값(또는 더 신선한 값)을 다시 가져올 것으로 예상합니다.

다음은 일치하지 않는 시스템의 예입니다.

이 경우,우리는 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것)들에게 그(것

한편,여기에 일관된 시스템의 예가 있다.

이 시스템에서$1$는 클라이언트에 승인을 보내기 전에 해당 값을$2$로 복제합니다. 따라서 클라이언트가$2$에서 읽을 때$5$:$5 1$의 최신 값을 얻습니다.

가용성

길버트와 린치가 가용성을 설명하는 방법은 다음과 같습니다.

시스템에서 실패하지 않는 노드가 받은 모든 요청은 사용 가능한 시스템에서

응답을 발생시켜야 합니다. 서버는 클라이언트의 요청을 무시할 수 없습니다.

파티션 허용

길버트와 린치가 파티션을 설명하는 방법은 다음과 같습니다.

네트워크는 한 노드에서 다른 노드로 보낸 많은 메시지를 임의로 잃을 수 있습니다.

모든 메시지가 삭제 된 경우,우리의 시스템은 다음과 같이 보일 것입니다.

우리 시스템은 파티션을 허용하기 위해 임의의 네트워크 파티션에도 불구하고 올바르게 작동 할 수 있어야합니다.

증명

이제 우리는 일관성,가용성 및 파티션 허용 오차의 개념을 알게되었으므로 시스템이 동시에 세 가지를 모두 가질 수 없다는 것을 증명할 수 있습니다.

일관되고 사용 가능하며 파티션 허용 가능한 시스템이 존재한다는 모순에 대해 가정합니다. 우리가 할 첫 번째 일은 우리의 시스템을 분할입니다. 이렇게 생겼습니다.

다음,우리는 우리의 클라이언트 요청$에 쓸 것을$지 _1$. 우리의 시스템을 사용할 수 있기 때문에,$_1$응답해야합니다. 그러나 네트워크가 분할되어 있기 때문에 데이터를$2$로 복제 할 수 없습니다. 길버트와 린치는이 실행 단계를$\알파 _1$라고 부릅니다.

다음,우리는 우리의 클라이언트 문제 읽기 요청$지 _2$. 다시 말하지만,우리 시스템을 사용할 수 있기 때문에$2$가 응답해야합니다. 그리고 네트워크가 분할되어 있기 때문에$지 _2$에서 값을 업데이트 할 수 없습니다. 그것은 반환$50$. 길버트와 린치는이 실행 단계를$\알파 _2$라고 부릅니다.

$클라이언트가 이미$5$를$5$로 작성한 후 클라이언트에게$5$를 반환합니다. 이 일치하지 않습니다.

우리는 일관되고 사용 가능한 파티션 허용 시스템이 존재한다고 가정했지만 시스템이 일관성없이 작동하는 그러한 시스템에 대한 실행이 존재한다는 것을 보여주었습니다. 따라서 그러한 시스템은 존재하지 않습니다.