分散システムにおけるタイミングの問題

順序

技術的なポイントはどこにでもあるように思えますが、それらをつなぎ合わせてシステムを形成し、体系的に理解する時間とエネルギーを持っている人はほとんどいません。複数の人が共同執筆した「In-depth Distributed Cache」のように、キャッシュ技術を多角的に理解できる本は珍しいです。 「深淵の魚を妬むよりは、退いて網を編むほうがよい。」ストーン・ブラザーズによる時間に関するこの記事は昨年書かれたものですが、時が経つにつれてより新鮮さを増しています。

[[315238]]

目次

1 時間とは何か？

2 物理的な時間：壁時計

3 論理クロック: イベントのシーケンス

4 Truetime: 物理時計の復活

5 ブロックチェーン：時間の再定義

6 その他の影響

6.1 NTP時刻同期

6.2 有限時間における不可能性

6.3 レイテンシー

6.4 リース

7 結論

8 参考文献

[[315239]]

1 時間とは何か？

時間は非常に抽象的な概念であり、数え切れないほどの哲学者を悩ませてきました。

偉人ニュートンの空間と時間の絶対原理は、ほとんどの人々の見解を代表しているかもしれません。つまり、時間は宇宙全体で不変の定数であるということです。

• ニュートンの空間と時間の概念では、時間と空間は独立した無関係なものです。
• 絶対空間は、物理的な出来事が発生する場所を区別し、3 次元座標で記述される空の部屋のような空間です。
• 絶対時間は、物理的な出来事が起こる順序を区別するストップウォッチのようなもので、不可逆な 1 次元座標によって記述されます。

「ニュートンは時間が何であるかを知っていると思っていた」と誰かが冗談を言った。ニュートンの絶対空間と時間では、時間の概念は宇宙全体で一定かつ一貫しており、時間は一連の出来事を測定するための基礎となります。これは、時間が明確でイベントの順序が明確な単一のコンピューターまたは密に結合されたコンピューター クラスターと非常によく似ています。コンピュータサイエンスの最初の数十年間は、コンピュータ間のタイミングについて考えたことはありませんでした。

[[315240]]

もう一人の偉大な科学者、アインシュタインの特殊相対性理論には、2 つの主要な論点があります。

• • 時間を含む物理法則は、すべての観察者にとって同じです。
• • 光の速度は一定です。

しかし、一般相対性理論によれば、時空全体が重力場であり、時間も空間も連続的ではないとされています。

特殊相対性理論の主な意義は、概念的な同時性が存在しないということである。同時性の概念は観察者に対して相対的であり、時間の経過も観察者に対して相対的です。同時に、この理論は、物事が遠くで起こった場合、それが本当に起こったのかどうかを知るには時間がかかることも説明しています。この待ち時間は長くなる可能性があります。

[[315241]]

分散システムはアインシュタインの宇宙よりも悪いかもしれない。分散システムでは、情報の伝播に必要な時間枠は予測不可能であり、太陽光が地球に到達するのにかかる 8 分をはるかに超える可能性があります。この間、ネットワークの反対側のコンピューターで何が起こっているかを知る方法はありません。メッセージを送信して問い合わせや調査ができる場合でも、メッセージが配信されて応答されるまでには常に時間がかかります。したがって、システム遅延時間とタイムアウト値の設定は、分散システムの重要な設計ポイントの 1 つです。

「すべての抽象は数学であり、すべての結論は確率である。」情報配信の統計結果は得られますが、各メッセージの配信の正確な時間を知ることはできません。この観点から見ると、分散システムが正しく動作するかどうかは運次第であり、その確率は非常に小さいため、非常に信頼できると考えられます。

時間の性質に関して、エルンスト・マッハはこう言いました。「時間とともに物事がどのように変化するかを測定する能力は私たちにはない。」それどころか、私たちは物事の変化を通して時間の流れという抽象的な概念を創り出します。

『7つの簡単な物理学のレッスン』の中で、著者は、過去と未来が異なるのは熱が存在する場合のみであると指摘しています。過去と未来を区別する基本的な現象は、熱は常に熱い物体から冷たい物体へと流れるという点です。

つまり、アインシュタインは時間は幻想であると言ったのです。文学的な意味では、時間が私たちの人生を定義するのではなく、私たちの人生が時間を定義するのです。

おそらくこれが、物理クロックを放棄して論理クロックを使用する背景です。

2 物理的な時間：壁時計

物理的な時間。英語の文献では壁時計とも呼ばれます。ウォールタイムは、実世界時間またはウォールクロック時間とも呼ばれ、時計やウォールクロックなどのタイマーによって決定される経過時間です。 (「壁」という言葉は、もともと壁掛け時計を指して使われていました。)

[[315242]]

コンピュータの世界では、集中型システムでは時間は明確です。たとえば、プロセス A と B は、時刻を取得するために t1 と t2 でカーネルへのシステム コールを開始し、取得される時刻は t1 である必要があります。

​​

スタンドアロン システムの時間は、クロックのドリフトが最小限のクォーツ クロックに依存します。

3 論理クロック: イベントのシーケンス

分散システムにおける同期と非同期はどちらも物理的な時間に関する前提ですが、論理クロックは物理クロックの制限から解放される最初のものです。

論理クロックは、分散システム内のマシンが時間については一致しない可能性があるが、時間の発生順序については一致できると想定しています。メッセージは送信される前に受信することはできないため、プロセス A がプロセス B にメッセージを送信する場合、A が B より前に発生すると想定できます。

​​

これは、分散システム内の異なるノード上の異なるイベント間の因果関係を定義します。後に導出されたベクトルクロックについても同様です。

基本的に、論理クロックはイベントと整数値のマッピングを定義します。したがって、多くの論理クロックの実装では単調に増加するソフトウェア カウンターが使用され、このカウンターの値は物理クロックとはまったく関係がありません。分散システム内のノードとプロセスが論理クロックを使用する場合、ファイルの読み取りと書き込み、データベースの更新などのイベントに論理クロックのタイムスタンプが追加されます。

論理クロックの貢献は、1978 年に Leslie Lamport が発表した論文「分散システムにおける時間、クロック、およびイベントの順序付け」に由来しています。

​​

4 Truetime: 物理クロックの復活

Google の Spanner が新しいアイデアを提案しました。通信なしで、高精度で観測可能なエラーを備えたローカル クロック (TrueTime API) を使用してイベントにタイムスタンプを付け、分散システム内の 2 つのイベントの順序を比較します。この方法を使用して、Spanner はトランザクション間の外部一貫性を実現します (下の図を参照)。

​​

つまり、1 つのトランザクションが終了してから別のトランザクションが開始されます。 Spanner は、最初のトランザクションのタイムスタンプが 2 番目のトランザクションのタイムスタンプよりも前であることを保証できるため、2 つのトランザクションはシリアル化された後も正しい順序を維持できます。

TrueTime API はローカル時刻を提供するインターフェースですが、Linux の gettimeofday インターフェースとは異なり、タイムスタンプ t を返すだけでなく、エラー ε も返します。たとえば、返されたタイムスタンプが 1 分 30 秒 350 ミリ秒で、誤差が 5 ミリ秒の場合、実際の時間は 1 分 30 秒 345 ミリ秒から 355 ミリ秒の間になります。実際のシステムでの平均 ε は 4 ミリ秒です。

TrueTime API を使用すると、Spanner はトランザクション マーカーに付与されるタイムスタンプが、トランザクションが開始された実際の時間とトランザクションが終了した実際の時間の間にあることを確認できます。トランザクションの開始時に TrueTime API によって返された時間が {t1, ε1} の場合、実際の時間は t1-ε1 と t1+ε1 の間になります。トランザクションの終了時に TrueTime API によって返される時間が {t2, ε2} の場合、実際の時間は t2-ε2 と t2+ε2 の間になります。 Spanner は、トランザクションのタイムスタンプとして t1+ε1 と t2-ε2 の間の時点を選択しますが、そのためには t1+ε1 が t2-ε2 より小さいことが必要です。これを保証するために、Spanner はトランザクションの実行中に、t2-ε2 が t1+ε1 より大きくなるまで待機してからトランザクションをコミットします。このことから、Spanner でのトランザクションが完了するまでに少なくとも 2ε (平均 8 ミリ秒) かかることがわかります。

この新しい方法では通信のオーバーヘッドは回避されますが、待機時間が発生することがわかります。外部一貫性を確保するためには書き込み遅延は避けられませんが、これは一貫性と遅延の間にトレードオフがあるという CAP 定理によって明らかにされた法則を裏付けています。

​​

Google はなぜこのデザインを採用したのでしょうか?

Truetime は根本的にどのような問題を解決しますか?

Spanner は、グローバル分散システムにおける 2 つの主要な時間問題を解決するように設計されています。

1. データセンター間の時刻同期は非常に困難で不確実である
2. グローバル規模でリクエストをシリアル化することは不可能です

これらの問題の解決策は、不確実性を受け入れ、GPS と原子時計を使用して不確実性を最小限に抑えることです。グローバルまたは複数のリージョンに展開される Spanner のようなシステムの場合、システムの応答時間が許容範囲内であることを保証するために、トランザクションにタイムスタンプを割り当てるにはどうすればよいでしょうか。システム全体で中央ノードを使用してタイムスタンプを割り当てると、システムの応答時間は非常に制御不能になります。中央ノードから地球の反対側にいるユーザーの場合、応答時間は約 100 ミリ秒と推定されます。

トゥルータイムを理解するには？トランザクション操作における truetime の役割を理解するには、まず Spanner でサポートされているいくつかのトランザクション タイプを確認します。

​​

単純な読み取り専用トランザクション。 Spanner の読み取り専用トランザクションには次の要件があります。

 クライアントプログラム自体が再試行アクションを実装する

 読み取り操作は書き込みなしで明示的に宣言する必要があります（たとえば、ファイルを読み取り専用で開くなど）

 システムはロックを取得する必要がなく、読み取りプロセス中に書き込み操作をブロックしません。

 システムはレプリカの読み取りのタイムスタンプを決定するためにタイムスタンプを選択します

 タイムスタンプを満たすレプリカは読み取り操作に使用できます。

もちろん、スナップショットの読み取りはさらに簡単です。過去のスナップショットをロックなしで読み取ることができます。顧客はタイムスタンプを指定することも、システムにタイムスタンプを選択させることもできます。詳細に立ち入る必要はありません。

読み取り/書き込みトランザクションでは、外部の一貫性を確保するために 2 フェーズ ロックが使用されます。

​​

Spanner は、truetime メカニズムを使用して、システム内の操作の発生順に、線形化実行記録を構築します。したがって、Spanner は線形化可能性を実装するシステムであると言えます。

要約すると、Spanner は、グローバルに同期された (一定の誤差を伴う) 物理時間の truthtimestamp をシステム タイムスタンプとして、またシステム内のさまざまな操作のバージョン番号として使用します。

5 ブロックチェーン：時間の再定義

サトシ・ナカモトは、自身の論文「ビットコイン：ピアツーピアの電子キャッシュシステム」の中でタイムスタンプサーバーモデルを提案し、ブロックチェーンの基礎を築きました。二重支出問題を解決するために、サトシ・ナカモトは分散型自己検証システムを構想しました。

ミントベースのモデルでは、ミント作成者はすべてのトランザクションを把握し、どのトランザクションが最初に到着するかを決定します。信頼できる当事者なしでこれを実現するには、取引を公開する必要があり、参加者が取引の受信順序の単一の履歴に同意できるシステムが必要です。受信者は、トランザクションが最初に受信されたことに大多数のノードが同意していることを証明する必要があります。

私たちが提案するソリューションは、タイムスタンプ サーバーから始まります。タイムスタンプ サーバーは、タイムスタンプを付けるデータ ブロックのハッシュを取得し、そのハッシュを新聞や Usenet の投稿などで広く公開することによって機能します。明らかに、タイムスタンプは、ハッシュに入るためにはデータがその時点で存在していたに違いないことを証明します。各タイムスタンプ ハッシュには前のタイムスタンプのハッシュが含まれており、後続の各タイムスタンプが前のタイムスタンプの有効性を強化するチェーンを形成します。

​​

このようにして、ブロックチェーンのタイムマシンとしての時を刻むメカニズムが形成されます。 1 つのブロックの高さは 1 つの時間ウィンドウに対応するため、ブロックチェーンはタイムマシンとも呼ばれます。クロックが均等に動くように、POW ブロックチェーンはアルゴリズムの難易度を自動的に調整し、ビットコインでは約 10 分、イーサリアムでは約 15 秒など、平均的な物理的な時間範囲内でティック サイクルを維持します。非 POW ブロックチェーンもこのようなクロックティックを維持します。たとえば、Filecoin テストネットでは、これを約 45 秒に維持します。

さらに、非 POW ブロックチェーンでは固定クロックティックを維持することが困難です。 Filecoin を例にとると、UTC タイムスタンプがネットワーク全体で使用され (Google のアプローチと同様)、固定された物理的な時間間隔が実現されます。これには、ネットワーク内のすべてのサーバーが NTP サーバーと同期されている必要があり、厳密なクロック ドリフト範囲 (1 秒) が制限されます。ブロックチェーンのタイムマシン機能により、フォークなしではチェーン上のデータを改ざんすることはできません。ブロックチェーンが人々に物理的な時間の消失、エントロピーの増大、エネルギーの散逸、そして「青春の終わりと昨日の終わり」を思い起こさせるのは、このためです。

​​

ブロックチェーンの性質を踏まえて、研究者たちは代替の解決策を見つけようとしています。非常に魅力的なソリューションの 1 つは VDF です。 VDF は Verifiable Delay Function の略です。検証可能な遅延関数 VDF の概念は、スタンフォード大学のコンピューターサイエンスおよび電気工学の教授であり、コンピューターセキュリティ研究所の共同ディレクターである Dan Boneh 氏が、Crypto 2018 カンファレンスで発表した論文「検証可能な遅延関数」で初めて提案しました。関数は、VDF が入力ごとに一意の出力を持つ関数であることを示します。遅延は時間 T (ウォールタイム) で表すことができます。遅延関数は計算を時間 T で完了しますが、並列で加速して計算を時間 T 未満で完了することはできません。検証可能であるためには、遅延関数の出力が非常に簡単に検証できることが求められます。詳細については、「Paxos、PoW、VDF: 美しいゴールデンライン」の記事をお読みください。

関数：

§ 入力ごとに一意の出力

遅れ：

§はT時間で評価できる

§ 時間内に評価できない

検証可能:

​​

VDF 計算プロセスに関する最も重要な点は、計算時には大量の計算リソースが必要になりますが、検証時には比較的少ない計算リソースしか必要ないことです。計算と検証の間のこのような非対称な関係は、一見すると Proof of Work (PoW) に少し似ています。その結果、「プルーフ・オブ・ワークに戻ったようだ」「CPUをもう一ラウンド燃やさずにこれを行うことはできないのではないか」という批判が次々と出ました。 - 文書「VDF はプルーフ・オブ・ワークではない」では、次のように指摘しています。VDF と従来の PoW アルゴリズムはどちらも「計算が難しい」、「検証しやすい」などの性質を持っていますが、最も核心的な違いは、ブロックチェーン プルーフ・オブ・ワークのコンセンサス アルゴリズムは並列化可能なプルーフ・オブ・ワークであり、関数ではなく成功確率のみを持つという点です。対照的に、VDF は継続的な作業証明と決定論的な関数です。

[[315246]]

VDF と PoW の違いについては多くの議論がありました。一般的に、PoW は乱数のソースとしては欠陥があります。同時に、VDF は PoW を直接置き換えることはできません。ただし、これは VDF がコンセンサス プロトコルで使用できないことを意味するものではありません。理由は次のとおりです。

• PoW は並列コンピューティングの高速化に対して耐性がありませんが、VDF は耐性があります。実際、PoW は並列コンピューティングの加速に耐性がなく、これは Satoshi Nakamoto の「1 つの CPU、1 つの投票」というアイデアと一致しており、並列加速に対する耐性はこの目的に反するだけです。 VDF では、マルチ CPU 計算はシングル CPU 計算に比べてほとんど利点がありません。

• 固定された難易度設定 d の場合、PoW には多くの合法的な解決策があり、これは PoW コンセンサス ネットワークのスループットが安定し、マイナーの競争を刺激することを保証するための前提でもあります。そして、与えられた入力 x に対して、VDF は一意の出力を持ちます (これが関数と呼ばれる理由です)。

一般的に、VDF はブロックチェーンのタイムティック メカニズムの基本的なニーズをうまく説明しています。 Protocol Labs と Ethereum が共同で設立した研究所や、VDF に関心を持つ多数のプロジェクトなど、一部の非 PoW ブロックチェーンおよび非ブロックチェーン分野では多くの研究と探究が行われています。

注: Filecoin のプロトコル実装では VDF も考慮されています。

Filecoin プロトコルの将来のバージョンでは、ブロック時間を強力に強制し、このリーダー選出要件を満たすために、検証可能な遅延関数 (VDF) が使用される可能性があります。ハードウェア VDF セキュリティがより広範囲に及ぶことが証明されるまで、クロック同期を明示的に想定することを選択します。

​​

6 その他の影響

時間は人々の生活に影響を与えるのと同じように、コンピュータ システムのあらゆる側面に影響を与え、当然私たちにも影響を与えます。

6.1 NTP時刻同期

分散システムでは、時間に関する合意を得ることは非常に困難です。異なるマシンのクォーツ時計の周波数が一致しない場合があり、その結果、異なるマシンの時刻が一致しなくなります。異なるマシンの時間を同期するために、NTP プロトコルが提案されました。このようにして、マシンの時間は別の外部クロックに依存することになります。

​​

NTP プロトコルは、往復のネットワーク通信遅延が等しいという原則に基づいています。これに基づいて、2 台のマシン間の時間差を取得できます。 NTP サーバーから取得した時刻に、この遅延を加算 (ローカル マシンより遅れた時刻) または減算 (ローカル マシンより進んだ時刻) することでローカル時刻として設定し、時刻同期を実現できます。

6.2 有限時間における不可能性

1985 年、フィッシャー、リンチ、パターソンは有名な FLP 結果 (1 つのプロセスに障害がある場合の分散合意の不可能性) を発表しました。非同期システムでは、プロセスに障害が発生すると、システムが合意に達することは不可能です。 FLP は、少なくとも 1 つのプロセスがクラッシュする可能性がある非同期環境では、コンセンサス問題を決定論的に解決するアルゴリズムが存在しないことを示しています。エンジニアリングのアプリケーションでは、この理論は次のようにも理解できます。不安定な障害のある非同期システムでは、完全な障害検出器を持つことは不可能です。

根本的な理由は時間です。 FLP の結果は、合意に達することができないことを意味するのではなく、有限の時間内に必ずしも合意に達することができないことを意味するだけです。同期システムは、プロセス間およびプロセス内計算間のメッセージ受け渡しに既知の上限を提供します。非同期システムには固定の上限はありません。

『分散システム: 概念と設計』という本の中で、著者は FLP に関して次のように指摘しています。分散システムでは、1 つのプロセスが失敗した場合、プロセスが合意に達することができないということではありません。これにより、実際の状況と一致する 0 より大きい確率で合意に達することができます。たとえば、現在広域ネットワーク上で稼働している分散システムはすべて非同期ですが、トランザクション システムは長年にわたって合意に達することができています。

したがって、FLP は限られた時間内に合意に達することは不可能であると述べています。システムが合意に達する可能性は高いですが、これは保証されません。つまり、非同期システムでは、有限の時間内に一貫性を実現することは不可能です。分散コンピューティングでは、非同期システムや信頼性の低いチャネル全体で一貫性を実現することは不可能です。

したがって、一般的な一貫性の前提には保証が必要です。ここでは、ビザンチン型の障害は考慮せず、メッセージング システムは信頼できると想定します。したがって、一貫性に関する研究では、一般的に、チャネルが信頼できるか、非同期システムが動作していないことが前提となります。

[[315248]]

確率は分散システムの信頼性に大きな影響を与えます。世界の確率的な性質により、未来を正確に推測することはできませんが、メッセージが正確に配信されるかどうかを予測するには十分すぎるほどです。考えてみてください。限られた時間内に絶対的な一貫性を実現することは不可能だとわかっています。では、なぜプログラマーは自信を持ってタイムアウト値を 5 秒に設定するのでしょうか。

この世界の確率的な性質と同様に、分散システムも確率に基づいて構築されます。

6.3 レイテンシー

多くの人は、レイテンシをネットワーク レイテンシとして分類します。これは、データが伝送媒体を通過するのにかかる時間、つまり、メッセージがネットワークに入り始めてからネットワークから出始めるまでの時間を指します。実際、コンピュータの世界では、レイテンシはどこにでもあります。

VDF に加えて、プログラマーは次の時間数値も知っておく必要がある場合があります。

• L1 キャッシュ参照 ............................. 0.5 ns
• 分岐予測ミス ............................. 5 ns
• L2 キャッシュ参照 ................................ 7 ns
• ミューテックスのロック/ロック解除 ............................. 25 ns
• メインメモリ参照........................ 100 ns
• Zippy で 1K バイトを圧縮 ............. 3,000 ns = 3 µs
• 1 Gbps ネットワークで 2K バイトを送信する ....... 20,000 ns = 20 µs
• SSD ランダム読み取り ............................. 150,000 ns = 150 µs
• メモリから 1 MB を連続的に読み取る.....250,000 ns = 250 µs
• 同じデータセンター内の往復 ...... 500,000 ns = 0.5 ms
• SSD* から 1 MB を連続的に読み取る ..... 1,000,000 ns = 1 ms
• ディスクシーク ............................................. 10,000,000 ns = 10 ms
• ディスクから 1 MB を連続的に読み取ります... 20,000,000 ns = 20 ms
• パケットを送信 CA->オランダ->CA .... 150,000,000 ns = 150 ms
• ......

[[315249]]

6.4 リース

分散システムにおけるリースの一般的な説明は次のとおりです。

• リースは、ライセンサーによって一定期間付与される契約です。
• ライセンサーがリースを発行すると、受領者がリースを受領したか否かに関わらず、また受領者のその後の地位に関わらず、リースが満了しない限り、ライセンサーは約束を遵守し、約束した時期と内容に従ってリースを履行しなければなりません。
• 受信者は、有効期間内に認可プロバイダーのコミットメントを使用できます。リースの有効期限が切れると、受信者は承認を放棄し、実行を継続しなくなります。再度実行したい場合は、リースを再度申請する必要があります。
• リースされた証明書は、バージョン番号、期間、または固定の時点で無効とみなされます。

リースは分散システムのハートビートメカニズムであると言えます。分散システムでは、分散ロックやクラスター リーダーなどの役割はいつでも変更される可能性があります。デッドロックやリーダーの誤認識を回避するために、通常はリース メカニズムが設計されます。

[[315250]]

7 結論

この記事では、主にコンピュータ システムの進化における時間の問題、特に古典的な分散システムにおける時間の問題と時間によってもたらされる順序の問題について検討します。ビザンチンフォールトトレランスをサポートする最新のブロックチェーンネットワークシステムの時間的性質と、検証可能な遅延関数の最新の調査について説明します。

現在の分散システムは、時間と空間の制限を超えて動作することはできず、システムの設計も時間と空間の考慮の範囲によって制約されます。今後、量子コンピュータが時間と空間の制約にどのような変化をもたらすのか、注目したい。