ブロックチェーンの「体内時計」はどのようなものですか?

stakefish

特邀专栏作者

2020-01-17 06:42

この記事は約3123文字で、全文を読むには約5分かかります

論理クロックの概念により、ブロックチェーンやその他の分散システムが正常に保たれます。

AI要約

展開

論理クロックの概念により、ブロックチェーンやその他の分散システムが正常に保たれます。

移り変わる時代の中で「時間」は永遠のテーマです。ブロックチェーンやその他の分散システムでは、時間に関する議論が行われています。時間はプロセスとノードを結び付けます。また、ブロックをチェーンに接続する分散ネットワークを測定するために時間の「粒度」も使用します。
分散システムにおける時間に関する問題は、さまざまな参加者の「物理時計」が完全に一致することが難しいことです。分散システムのマスターであるランポートは、ブロックチェーンを含む分散システムに「生物時計」を導入するのと同じように、問題を時間と順序の関係に変換する分散型の方法を提供し、論理時計の概念を提唱します。
stakefish は、Vac アナリストで ENS 開発者のディーン・アイゲンマンによる記事を編集し、時間、時計、順序に関するランポートの議論を紹介し、ブロックチェーンと分散システムの時間を別の角度から理解することを皆に思い出させています。

分散システムに関する一連の記事を始めるのに適切なトピックはどれですか?イーサリアムのプライバシートランザクションプロトコルAZTEC?習得が難しいことで知られる Paxos アルゴリズム?これらのトピックは後で書くことにします。今日、私は最初に基本的なトピック、つまり分散システムにおける時間のトピックを選択しました。

この記事は、チューリング賞受賞者でコンピュータの第一人者であるレスリーランポートによる有名な論文「分散システムにおける時間、時計、およびイベントの順序」を解釈したものです。しばらく経ってからこの投稿を読み返して、重要な概念を抽出するのは楽しいです。

Leslie Lamport について詳しくない友人でも、LaTeX、TLA+、Paxos の作成で有名であり、ビザンチン一般問題についても議論しているので、概要を理解することができます。もちろん、ランポートクロック（最初の論理時計）もありますが、この記事ではその基本的な概念も紹介します。

まず分散システムの定義を見てみましょう。ランポートによる定義は次のとおりです。

「システム内の情報配信の遅延が、単一プロセスのイベント間の時間に比べて無視できない場合、そのシステムは分散システムと呼ばれます。」

私がこの定義を気に入っているのは、メッセージの送信と受信の間の遅延に焦点を当てているからです。

定義が明確になったら、正式な導入を開始します。

副題

ローカルでのイベントの並べ替えはこれ以上に簡単です。各イベントに発生時のタイムスタンプを割り当てるだけです。すべてのイベントの全体的な順序を取得できます。これは、すべてのイベントを特定の順序で配置できることを意味します。

しかし、分散システムの場合、この問題はさらに困難になります。なぜ？

これはすべて、分散システムの非常に単純な性質によるものです。メッセージはノード間で送信された後、将来の任意の時点で 0 回、1 回、またはそれ以上到着する可能性があります。この場合、分散システム内のさまざまなノードは時刻について一致できません。例えば：

ノードは別のノードにメッセージを送信して、現在時刻を 12:00:00 としてマークできますが、受信者はメッセージの配信にどれくらい時間がかかったのかわからないため、まだ 12:00 であるかどうかを確認する方法はありません。到着したら00。その場合、ノード間でメッセージが丸 1 日送受信されたとしても、情報が同期されているかどうかを判断する方法はありません。タイミングについて合意できない場合は、イベントの順序についても合意できません。

では、この問題をどうやって解決すればいいのでしょうか？

分散システムでは、複数のノードが相互にメッセージを送信することによって通信します。ノードは情報を受信すると、まず情報を確認し、次のイベントを実行します。このような命令はもともと「因果関係」を示しており、情報は受信する前に送信する必要があります。

注釈: この因果関係は順序関係であり、原因と結果の間の論理的な関係ではありません。

次に、因果関係に基づいて順序を導き出すことができます。メッセージは、メッセージが受信される前に送信されなければなりません。二つの出来事AとBを見ただけで、「前に起こる」という関係を与えることで順序を記述することができます。

さて、この関係は物理的な時間の体系的な概念なしで特定できます。つまり、イベント A がイベント B に因果関係をもたらした場合、イベント A はイベント B の前に発生したはずです。因果関係により、システム内の関連するイベントの順序、つまり部分的な順序を決定することができます。

部分的な順序付けには制限もあります。依存関係を判断できないと、システム内のすべてのイベントの正確な順序がわからない可能性があります。システム全体で多くのイベントが同時に発生する可能性があるため、すべてのノードがこれらのイベントの発生を認識しているわけではありません。

副題

しかし、部分的な順序が得られたので、システムにクロックを追加して、システム内のすべてのイベントの合計順序を取得できます。

分散システムで物理クロックを使用するのは現実的ではないことがわかりました。その場合は、論理クロックを使用する必要があります。論理クロックは本質的に、イベントに番号を割り当てることができる機能です。この数字はイベントが発生した時間を表し (以降、この数字を時間と呼びます)、物理的な時間とは関係ありません。

文章

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

上の式は何を意味するのでしょうか？

矢印「→」は「前に起こった（前に起こった）」を意味し、Cは時計機能を表しており、単純に時間として理解できます。したがって、意味を表現すると、次のようになります。各イベント a、b について、a が b より前に発生した場合、a の時間は b の時間よりも小さくなります。

しかし、逆の演繹は真ではなく、ある出来事の時間が別の出来事の時間より短いからといって、その出来事が以前に起こったとは言えず、それらは同時である可能性があります。

上の図では、ノード α では時刻 1 と時刻 2 にそれぞれ 1 つのイベントが発生し、ノード β では独自の時刻 1 に 1 つのイベントが発生していることがわかります。ノード α の時刻 1 および時刻 2 のイベントは、ノード β の時刻 1 のイベントと同時であり、因果関係はありません。