Geth クライアントのスナップショット高速化メカニズムを理解するための記事
編集者注: この記事は以下から引用しましたイーサリアム愛好家 (ID: ethfans)編集者注: この記事は以下から引用しました
イーサリアム愛好家 (ID: ethfans)
イーサリアム愛好家 (ID: ethfans)
、著者: Péter Szilágyi、翻訳: A Jian、Odaily が許可を得て転載。
この記事は、Geth クライアントの回答シリーズの最初の記事です。Geth クライアントについて積極的に質問することができます。毎週小さな記事を使用して、投票数の多かった質問に回答します。今週最もリクエストが多かった質問は、「フラット データベース構造とレガシー構造の主な違いについて話してもらえますか?」です。
イーサリアムの状態
アクセラレーション構造 (アクセラレーション構造) について詳しく説明する前に、イーサリアムの「状態」の概念と、さまざまな抽象レベルでの状態の保存方法を確認してみましょう。
イーサリアムには、アカウントのコレクションとコントラクトごとのアカウント スロットのコレクションという 2 つの異なるタイプの状態があります。完全に抽象的な観点から見ると、どちらの種類のデータもキーと値のペアです。アカウント コレクションは、アドレスをそのアドレスの nonce、残高などにマッピングします。コントラクトのストレージ フィールドは、(コントラクトによって定義および使用される) 任意の値を何らかの値にマップします。
残念ながら、これらのキーと値のペアをフラット データとして保存することは非常に効率的ですが、その正確性を検証することは計算的に困難になります。データが変更されるたびに、すべてのデータをボトムアップでハッシュする必要があります。
常にデータベース全体をハッシュする必要を避けるために、データベースを連続した部分に分割し、一種のツリー構造を作成できます。最もオリジナルで有用なデータはリーフ ノードに配置され、ツリー上の各内部ノードはノードの下にあるコンテンツのハッシュ値です。このようにして、値を変更したいときは、対数回のハッシュ演算を行うだけで済みます。このようなデータ構造には、実は「メルケルツリー」というよく知られた名前があります。
しかし、まだ終わったわけではありません。この方法はまだ計算の複雑さが不足しています。マークル ツリー構造は既存のデータを変更する場合には非常に効率的ですが、データの挿入や削除によって基礎となる小さなデータ ブロックの境界が変更されると、計算されたすべてのハッシュ値が無効になります。
このとき、データベースをやみくもにグループ化するのではなく、キー自体を使用してデータを整理し、共通のプレフィックスに基づいてデータをツリー状の形式に配置することができます。このように、挿入操作と削除操作は両方ともすべてのノードに影響を与えるのではなく、ツリーのルートからリーフまでのパス上の (対数) ノードにのみ影響します。このデータ構造は「パトリシアツリー」と呼ばれます。
パトリシアツリーのツリー階層とマークルツリーのハッシュアルゴリズムという上記2つの手法を組み合わせたものがいわゆる「メルケル・パトリシアツリー」であり、実際にも使われているイーサリアムの状態を表すデータ構造です。変更、挿入、削除、検証のいずれであっても、存在するのは対数的な複雑さだけです。唯一の小さな例外は、試行のバランスをとるために、一部のキーが挿入前にハッシュされることです (ちょっとした追加として、試行のバランスをとるために、挿入前にキーがハッシュされることです)。
イーサリアムの状態ストレージ
上記は、イーサリアムが状態を保存するためにマークル パトリシア ツリー構造を使用する理由を説明しています。残念ながら、必要な操作は高速ですが、各オプションには犠牲が伴います。更新操作と検証操作の対数的な複雑さは、個々のキーの読み取りと保存が対数的である (対数読み取りと対数保存) ことを意味します。これは、ツリー構造の各内部ノードをハードディスク上に個別に保存する必要があるためです。
現時点ではアカウント ツリーの深さが正確にはわかりませんが、約 1 年前にはアカウントの状態が 7 レベルのツリーを埋めていました。これは、すべてのツリー操作 (例: 読み取りバランス、書き込みノンス) が少なくとも 7 ～ 8 個の内部ノードにアクセスし、したがって少なくとも 7 ～ 8 回の永続的なデータベース アクセスを実行することを意味します。 LevelDB はデータを最大 7 レイヤーに編成するため、追加の乗数が存在します。最終的には、単一状態のアクセスが 25 ～ 50 のランダム ディスク アクセスに増幅されることが予想されます。これに、ブロック内のすべてのトランザクションのすべての状態の読み取りおよび書き込みを掛けると、恐ろしい数字が得られます。
[もちろん、すべてのクライアント実装はオーバーヘッドを可能な限り低く抑えようとします。 Geth は、より大きなメモリ領域を使用して複数のノードをキャッシュし、また、メモリ内プルーニング メカニズムを使用して、数ブロック後に削除されるデータがディスクに書き込まれることを回避します。しかし、これを明確にするためには別の記事が必要です。 ]
さらに恐ろしいのは、この数字が、すべての状態を 24 時間 365 日確認することが保証されているイーサリアム ノードを実行するコストであるということです。
もっとうまくできるでしょうか？
すべての訪問が同じように作成されるわけではありません
イーサリアムの運用は、暗号による国家証明に依存しています。すべてのデータを検証する機能を維持したい限り、ハードディスクの読み取りおよび書き込みの増幅の問題を回避することはできません。つまり、私たちは検証したデータを信頼することができ、そうしています。
各状態オブジェクトを繰り返し検証するのは意味がありませんが、ハードディスクからデータを取得するたびに検証しなければならないのでは、非常に意味のないことを行っていることになります。マークル パトリシア ツリー構造は本質的に書き込み操作用に設計されていますが、読み取り操作には負担がかかります。それを取り除くことはできませんし、スリムにすることもできませんが、だからといってあらゆる機会に使用しなければならないというわけではありません。
Ethereum ノードのアクセス状況のシナリオは、大きく次の 3 つのカテゴリに分類できます。
新しいブロックをインポートする場合、EVM コードの実行により、多かれ少なかれバランスのとれた数の状態の読み取りと書き込みが生成されます。ただし、サービス拒否攻撃に使用されるブロックでは、書き込み操作よりもはるかに多くの読み取り操作が生成される可能性があります。
ノード オペレーターが状態を取得するとき (ethcall や同様の操作の呼び出しなど)、EVM コードの実行では読み取り操作のみが生成されます (もちろん書き込み操作がある場合もありますが、これらの操作によって生成されたデータは最終的に破棄され、永続化されません)ハードドライブの内部に）。
ノードがブロックチェーンを同期しているとき、シンクロナイザーはリモート ノードからステータスを要求し、要求先はデータをマイニングしてネットワークを通じてシンクロナイザーに拡散します。
上記のアクセス パターンに基づいて、ステート ツリーに触れることなく読み取り操作を短縮できれば、多くのノード操作を大幅に高速化できます。これにより、以前はコストが高すぎて実現不可能だったいくつかの新しいアクセス パターン (状態の反復など) も可能になります。
もちろん、犠牲は避けられません。ツリー構造を削除しないと、新しいアクセラレーション構造によって追加のオーバーヘッドが発生します。唯一の疑問は、追加のオーバーヘッドは試してみる価値があるほど十分な見返りがあるのかということです。
フォローしてください
私たちはすべての問題を解決するために魔法のマークル パトリシア ツリー構造を開発しました。そして今度は読み取り操作をそれをバイパスさせたいと考えています。では、読み取り動作を再び高速化するには、どのようなアクセラレーション構造を使用すればよいでしょうか?明らかに、ツリー構造が必要ない場合は、ツリー構造に伴う複雑さをすべて脇に置いて、元の状態にすぐに戻ることができます。
この記事の冒頭で述べたように、理論的には、理想的なイーサリアムの状態のデータ保存方法は、単純なキーと値のペアである必要があり、メルケル パトリシア ツリーの制限がなければ、それを妨げるものは何もありません。この理想のプランを実現するために！
少し前に、Geth はスナップショット アクセラレーション構造を導入しました (デフォルトでは有効になっていません)。スナップショットは、特定のブロックにおけるイーサリアムの状態の完全なビューです。実装の詳細を抽象化し、すべてのアカウントとコントラクトのストレージ スロットを単純にスタックし、フラットなキーと値のペアで表します。
アカウントまたは特定のストレージ スロットにアクセスしたいときは、各ツリーに対して 7 ～ 8 回クエリを実行するのではなく、LevelDB のクエリ操作を 1 回支払うだけで済みます。理論的には、スナップショットの更新も非常に簡単で、ブロックの処理後、更新するストレージ スロットごとに追加の LevelDB 書き込み操作を 1 回実行するだけです。
実際、スナップショット アクセラレーション構造により、書き込み操作の複雑さが O(log n) から O( 1 + log n) (LevelDB オーバーヘッドで乗算)、ディスク ストレージが O(n log n) から O(n + n log n) に増加しました。
悪魔は細部に宿る
イーサリアム状態スナップショットの可用性を維持することも簡単ではありません。ブロックが引き続き次々に生成され、最後のブロックの上に積み上げられている限り、最新の変更をスナップショットにマージする粗雑な方法は問題なく機能します。ただし、ブロックチェーンの小さな再構成 (たとえ 1 ブロックでも) でさえ、元に戻す操作がまったく設計されていないため、スナップショット メカニズムが機能しなくなります。フラット データ表現パターンの場合、永続的な書き込みは一方向の操作です。さらに悪いことに、古い状態にアクセスする方法がありません (たとえば、一部の dApps は 3 ブロック前の状態、または高速/スナップ同期モードの 64 ブロックの状態にアクセスする必要があります)。
これらの制限を克服するために、Geth クライアントのスナップショットは、古いブロック (たとえば、上位 128 ブロック) での状態の完全なスナップショットである永続ハードディスク層と、メモリ内の差分層 A の 2 つの部分で構成されています。最新の書き込み操作を収集するために使用されるコンポーネントのツリー。
新しいブロックを処理するとき、これらの書き込みをハードディスク層に直接マージするのではなく、これらの変更を含む新しいメモリ内の差分層を作成するだけです。メモリ内の diff レイヤーが十分な数のレイヤーに蓄積されると、一番下のレイヤーが更新のマージを開始し、それらをハードディスク層にプッシュします。状態オブジェクトを読み取る必要がある場合、最上位の差分レイヤーから検索を開始し、差分レイヤーまたはハードディスク層で見つかるまで下に進みます。
このデータ表現は非常に強力で、多くの問題を解決します。メモリ内の差分層はツリーを形成しているため、128ブロック内のチェーン再構成は親ブロックに属する差分層を取り出してビルドを開始するだけで済みます。古い状態を必要とする dApp と Farsyncers は、最新の 128 個の状態にアクセスできます。オーバーヘッドは 128 回のマッピング ルックアップになりますが、128 回のメモリ内ルックアップは、8 回のハードディスク読み取りおよびレベル DB の 4 ～ 5 倍の増幅よりも数桁高速です。
もちろん、まだ落とし穴はたくさんあります。あまり深くは説明しませんが、単に次のリストを列挙します。
自己破壊 (契約自己破壊操作) (および削除操作) は、差分層の下降を短絡する必要があるため、特に対処が困難です。
永続ハードディスク層よりも深いチェーンの再編成がある場合、現在のスナップショットは完全に破棄され、再生成されます。一連の操作全体は非常に高価です。
ノードがシャットダウンされると、メモリ内の diff レイヤーをログに保存し、バックアップのためにロードする必要があります。そうしないと、再起動後にスナップショットが役に立たなくなります。
最下位の差分レイヤーを、特定のメモリ使用量を超えた場合にのみディスクにフラッシュされるアキュムレータとして使用します。これにより、複数のチャンクにまたがる同じスロットへの書き込みの重複排除が可能になります。
コントラクトが同じ古いストレージ スロットに繰り返しアクセスした場合にハード ディスクが破損しないように、ハード ディスク層に読み取りキャッシュを割り当てる必要があります。
メモリ内の差分レイヤーで累積ブルーム フィルターを使用して、状態オブジェクトが差分レイヤーに存在する可能性が高いか、ディスクに直接ジャンプする必要があるかを迅速に検出します。
元のデータ (アカウント アドレス、契約ストレージ キー) はキーとして設定されませんが、これらのデータのハッシュ値がキーとして使用され、スナップショットの反復順序がマークル パトリシア ツリーの順序と同じであることが保証されます。
永続ハードディスク層を生成する時間は、状態ツリー ウィンドウをプルーニングする時間よりもはるかに長いため、ジェネレーターでもチェーンの操作を動的に追跡する必要があります。
美と醜の共存
Geth のスナップショット アクセラレーション構造により、状態読み取りの複雑さが 1 桁減少します。これは、読み取りベースの DoS 攻撃を開始するのが桁違いに難しく、ethcall 呼び出しも桁違いに高速であることを意味します (CPU ボトルネックがない場合)。
もちろん、これらすべてにコストがかかるわけではありません。初期同期が完了した後、メイン ネットワークに参加しているノードが初期スナップショットを構築する (その後、その可用性を維持する) のに 9 ～ 10 時間かかり、15 GB を超える追加のハード ディスクが必要です。
エピローグ
悪い部分はどこですか？スナップショット メカニズムをリリースするのに十分な自信を築くまでに 6 か月かかりました。スナップショット メカニズムはまだデフォルトの機能ではなく、--snapshot フラグを使用してアクティブに有効にする必要があります。また、メモリ使用量とクラッシュ回復に関してはまだ改良作業が残っています。すること。
全体として、私たちはこの改善を非常に誇りに思っています。膨大な量の作業が必要で、すべてを自分で実装し、うまくいくことを祈りながら暗中模索でした。もう 1 つの興味深い点は、リーフ同期の最初のバージョンは 2 年半前に作成されましたが、それを駆動するために必要なアクセラレーション構造が不足しているため、ブロックされているということです。
