블록체인의 "생물학적 시계"는 어떻게 생겼습니까?

'시간'은 변화하는 시대 속 영원한 화두다. 시간이 지남에 따라 블록체인 및 기타 분산 시스템에 대한 논의가 진행되고 있습니다. 시간은 프로세스와 노드를 연결하며, 블록을 체인으로 연결하는 분산형 네트워크를 측정하기 위해 시간의 "세분성"도 사용합니다.

분산 시스템에서 시간에 대한 어려움은 서로 다른 참가자의 "물리적 시계"가 완전히 일치하기 어렵다는 것입니다. 분산 시스템 마스터인 Lamport는 블록체인을 포함한 분산 시스템에 "생물학적 시계"를 도입하는 것처럼 문제를 시간과 질서의 관계로 변환하고 논리적 시계의 개념을 제시하는 분산 방식을 제공합니다.

stakefish는 Vac 분석가이자 ENS 개발자인 Dean Eigenmann의 기사를 편집하여 시간, 시계 및 순서에 대한 Lamport의 논의를 소개하고 모든 사람이 다른 관점에서 블록체인 및 분산 시스템 시간을 이해하도록 상기시킵니다.

분산 시스템에 대한 일련의 기사를 시작하기에 더 적합한 주제는 무엇입니까? Ethereum의 개인 정보 거래 프로토콜 AZTEC? 마스터하기 어렵다고 알려진 Paxos 알고리즘? 이 항목은 나중에 작성하도록 남겨 둡니다. 오늘은 기본 주제인 분산 시스템에서의 시간이라는 주제를 시작으로 선택했습니다.

이 기사는 Turing Award 수상자이자 컴퓨터 전문가인 Leslie Lamport가 쓴 유명한 논문 "Time, clocks, and the ordering of events in a distribution system"을 해석합니다. 오랜 시간이 지난 후에 이 게시물을 다시 읽고 핵심 개념을 추출하는 것은 재미있습니다.

LaTeX, TLA+, Paxos를 만든 것으로 유명하고 비잔틴 일반 문제에 대해서도 논의하는 Leslie Lamport에 익숙하지 않은 친구들도 일반적인 아이디어를 얻을 수 있습니다. 물론 Lamport 시계(첫 번째 논리 시계)도 있으며 이 기사에서는 기본 개념도 소개합니다.

먼저 분산 시스템의 정의를 살펴보겠습니다. Lamport의 정의는 다음과 같습니다.

"시스템 내 정보 전달 지연이 단일 프로세스의 이벤트 간 시간과 비교하여 무시할 수 없는 경우 시스템을 분산 시스템이라고 합니다."

나는 이 정의가 메시지 전송과 수신 사이의 지연에 초점을 맞추기 때문에 마음에 듭니다.

정의가 명확하게 정의되면 정식 소개를 시작합니다.

보조 제목

로컬에서 이벤트를 정렬하는 것은 이보다 쉬울 수 없습니다. 각 이벤트가 발생했을 때 타임스탬프를 할당하기만 하면 됩니다. 모든 이벤트의 전체 순서를 얻을 수 있습니다. 즉, 모든 이벤트를 특정 순서로 정렬할 수 있습니다.

그러나이 문제는 분산 시스템의 맥락에서 훨씬 더 어렵습니다. 왜?

모두 분산 시스템의 매우 단순한 특성 때문입니다. 메시지가 노드 간에 전송된 후 향후 어느 시점에서든 0, 1회 또는 그 이상 도착할 수 있습니다. 이 경우 분산 시스템의 여러 노드가 시간에 동의할 수 없습니다. 예를 들어:

노드는 현재 시간을 12:00:00으로 표시하기 위해 다른 노드에 메시지를 보낼 수 있지만 수신자는 메시지가 전달되는 데 걸린 시간을 모르므로 여전히 12:00인지 확인할 방법이 없습니다. 00 도착하면. 그렇다면 하루 종일 노드 간에 메시지를 주고 받아도 정보가 동기화되었는지 여부를 확인할 방법이 없습니다. 타이밍에 동의할 수 없다면 사건의 순서에 대해서도 동의할 수 없습니다.

그렇다면 이 문제를 어떻게 해결해야 할까요?

분산 시스템에서 여러 노드는 서로 메시지를 보내 통신합니다. 노드는 정보를 받으면 먼저 정보를 확인하고 다음 이벤트를 실행합니다. 이러한 주문은 원래 "인과 관계"를 나타냅니다. 즉, 정보를 수신하기 전에 먼저 보내야 합니다.

주석: 이 인과관계는 원인과 결과 사이의 논리적 관계가 아니라 순차적 관계입니다.

그런 다음 인과 관계에 따라 명령을 내릴 수 있습니다. 메시지를 수신하기 전에 메시지를 보내야 합니다. 두 사건 A와 B만 보면 "이전에 일어난다"라는 관계를 부여함으로써 순서를 설명할 수 있습니다.

이제 이 관계는 물리적 시간에 대한 체계적인 개념 없이 식별할 수 있습니다. A가 B에 인과적 영향을 미쳤다면 사건 A는 사건 B보다 먼저 발생해야 합니다. 인과 관계를 통해 시스템에서 관련 이벤트의 순서, 즉 부분 순서를 결정할 수 있습니다.

부분 순서에도 한계가 있습니다. 종속성을 확인할 수 없으면 시스템의 모든 이벤트의 정확한 순서를 알 수 없습니다. 시스템 전체에 동시에 많은 이벤트가 있을 수 있으므로 모든 노드가 이러한 이벤트의 발생을 인식하는 것은 아닙니다.

보조 제목

그러나 이제 부분적인 순서가 있으므로 시스템에 시계를 추가하여 시스템의 모든 이벤트의 전체 순서를 얻을 수 있습니다.

이제 우리는 분산 시스템에서 물리적 시계를 사용하는 것이 실현 가능하지 않다는 것을 알았습니다. 그러면 논리적 시계를 사용해야 합니다. 논리적 시계는 기본적으로 이벤트에 숫자를 할당할 수 있는 기능입니다. 이 숫자는 이벤트가 발생한 시간(이제부터 이 숫자를 시간이라고 함)을 나타내며 물리적 시간과 관련이 없습니다.

텍스트

∀a,b a → b ⟹ C(a) < C(b)

위의 표현은 무엇을 의미합니까?

화살표 "→"는 "happened before (이전에 일어난)"를 의미하고, C는 시계 기능을 나타내며 간단히 시간으로 이해할 수 있습니다. 따라서 의미를 표현하면 다음과 같습니다. 각 이벤트 a, b에 대해 a가 b보다 먼저 발생하면 a의 시간은 b의 시간보다 적습니다.

그러나 역 추론은 사실이 아닙니다. 한 이벤트의 시간이 다른 이벤트의 시간보다 작기 때문에 이 이벤트가 이전에 발생했다고 말할 수 없으며 동시에 발생할 수 있습니다.

위의 그림에서 우리는 노드 α에서 각각 시간 1과 시간 2에 하나의 이벤트가 발생하고 노드 β에는 자신의 시간 1에 하나의 이벤트가 발생했음을 알 수 있습니다. 노드 α에서 시간 1과 시간 2의 이벤트는 노드 β에서 시간 1의 이벤트와 동시에 발생하며 인과 관계가 없습니다.

• a와 b가 단일 노드의 두 이벤트이고 a가 b보다 먼저 발생하면 a의 시간은 b의 시간보다 작아야 합니다.

• a가 메시지를 보내는 노드이고 b가 메시지를 받는 또 다른 노드라면 a의 시간은 여전히 ​​b의 시간보다 작아야 합니다.

노드는 이벤트 사이에 시간이 흐르도록 해야 합니다. 그렇지 않은 경우 시계는 다른 노드에서 받은 메시지에 포함된 시간보다 늦은 시간으로 진행되어야 합니다. b는 시계가 빠르게 조정된 후에 발생할 수 있습니다.

예

예

마지막으로 논리적 시계의 사용을 보기 위해 상태 시스템을 설정합니다. 예를 들어, 여러 노드가 공유 리소스에 액세스하려고 하고 한 번에 하나의 노드만 액세스할 수 있는 분산 시스템이 있습니다. 상태 시스템은 다음 조건을 충족해야 합니다.

• 조건 1: 자원에 접근할 수 있는 노드는 다른 노드가 접근하기 전에 먼저 자원을 해제해야 합니다.

• 조건 2: 리소스 요청은 요청이 이루어진 순서대로 액세스 권한을 부여받아야 합니다.

• 조건 3: 액세스 권한이 부여된 모든 노드가 결국 리소스를 해제하면 결국 모든 요청이 허용됩니다.

중간 코디네이터를 도입하지 않겠습니까? 이 경우 먼저 요청이 발생했지만 나중에 도착하면 조건 2를 만족할 수 없으며, 또 다른 이유는 탈중앙화 솔루션을 채택하고자 하기 때문입니다.

따라서 우리는 여전히 이 논리적 시계를 충족시키기 위한 조건을 구축해야 합니다. 조건을 충족하는 방법?

Lamport는 분산형 솔루션을 제공합니다. 첫째, 우리는 모든 노드가 요청 대기열을 저장하기를 원합니다. 둘째, 몇 가지 간단한 가정이 충족되어야 합니다.

• 가정 1: 모든 메시지는 보낸 순서대로 수신됩니다.

• 가정 2: 결국 모든 메시지가 수신됩니다.

• 가정 3: 모든 노드는 시스템의 다른 모든 노드에 직접 메시지를 보낼 수 있습니다.

더 복잡한 알고리즘과 프로토콜이 있는 경우 위의 가정을 무시할 수 있습니다.

이제 이 3가지 조건을 만족하는 알고리즘을 정의하고 실제로 시계의 기능을 보여줄 수 있습니다.

1. 노드가 리소스를 요청하려는 경우 현재 시간으로 요청을 생성하고 대기열에 추가한 다음 다른 모든 노드로 보냅니다.

2. 다른 모든 노드는 이 요청을 대기열에 넣고 응답 메시지를 다시 보냅니다.

3. 리소스를 해제하는 노드는 현재 시간과 함께 해제 메시지를 보내고 대기열에서 원래 요청을 삭제합니다.

4. 노드가 해제 메시지를 받으면 자체 대기열에서 관련 요청을 지웁니다.

5. 노드가 다른 요청보다 먼저 대기열에 자신의 요청을 가지고 있으면(전체 시간순으로) 해당 리소스에 자유롭게 액세스할 수 있으며 그 이후에 다른 모든 노드로부터 메시지를 받습니다.

위의 알고리즘은 각 노드에서 완전히 독립적으로 실행되는 분산형 알고리즘으로 시계를 사용하여 요청을 일반적인 순서로 정렬하여 리소스에 대한 액세스와 노드 간의 조정을 달성합니다.

자, 우리는 글을 통해 이러한 논리적 시계를 사용하여 분산 시스템에서 이벤트를 정렬하는 방법을 대략적으로 배웠고, 분산 시스템이 리소스에 액세스할 때 순서를 결정하는 실제 응용을 분석했습니다. 피드백을 환영하며 분산 시스템에 대한 더 많은 기사를 계속 업데이트할 것입니다.

원제: 시간, 시계, 그리고 질서

딘 아이겐만

텍스트