【 Aptosのブロックチェーン 】詳細

今回は、APtosのブロックチェーンについて解説します。


Aptosは、事前に設定されたトランザクションの順序を活用し、ソフトウェアトランザクションメモリ技術と斬新な技術を組み合わせることにより、毎秒160,000以上の重要なMoveトランザクションを実行できます。

そのため効率的なマルチスレッドのメモリ内並列実行エンジンを設計・実装させました。

スポンサーリンク

ブロックチェーンのユースケース

Aptosに関する詳細はこちらです。→仮想通貨【 Aptosとは 】必要知識まとめ


今回は、Aptosのブロックチェーンに関してです。

Aptosは特定のユースケースに適用すると、STMのパフォーマンスが劇的に向上することが過去に示されていました。

実際、ブロックチェーンのユースケースに当てはまる3つの重要な観察項目が、BlockーSTMの設計を導いているのです。

トランザクションを個別にコミットする必要がない

汎用STMは、各スレッドには、任意の時間に到着する可能性のあるクエリに基づいてコミットするトランザクションの無限のストリームがあります。

しかしこれとは対照的にブロックチェーンでは、状態は通常、ブロックごとに更新されます。

これにより、BlockーSTMはトランザクションを個別にコミットする同期コストを回避できます。

代わりに、Block/STMはブロック内の全てのトランザクションを簡単な同期で遅延コミットします。

更に、ブロック間でメモリをクリーンアップできるため、ガベージコレクションは簡単です。

VMは楽観的なメモリアクセスに安全性に提供する

トランザクションはMoveやSolidityなどのスマートコントラクト言語で指定され、実行をカプセル化して安全な動作を保証する仮想マシンで実行されます。

これにより、抽象化が適切に分離され、BlockーSTMが並列投機的実行中の矛盾した状態(不透明度と呼ばれるプロパティ)の処理を回避できるようになります。

事前定義された順序は動機を減らす

一般に、STMライブラリは非決定性を対象とし、決定性をシステムの制限とみなし、パフォーマンスを妨げます。

これにより、同じブロックを実行するバリデーターが異なる最終状態になる可能性があるため、ブロックチェーンのユースケースには適していません。

ただし、Block-STMでは、決定論はパフォーマンスの祝福とみなされます。

実際、最終的な結果は、事前に設定された固定順序でのトランザクションの順次実行と一致することが保証されています。

そしてこの制約は、システムの利点として使用されます。


特定のリアライゼーションに同意することで、実行中に必要な同期の量が減るためです。

例えば、トランザクションtx5とトランザクションtx9の間に競合がある場合、tx9はtx 5を待機します。

そうでない場合、順序がなければこれらのトランザクションを実行sるうスレッドはタイを被る必要があります。

したがって、直感的なレベルでは、汎用STMが難しい問題(つまり、コンセンサスの形)を解決するのに対して、Block-STMはより単純な問題(トランザクションを実行するだけで良い)を対象としています。

コアテクニック

BlockーSTMは、吉備技術と斬新なアイデアを組み合わせています。

楽観的同時実行制御

トランザクションは楽観的に並行して伊jっこうされ、実行後に検証されます。

検証に失敗すると、再実行につながります。

事前設定された順序のため、検証は互いに独立しておらず、論理的に順番に発生する必要があります。

以前の作業とは異なり、検証が成功してもトランザクションをコミットできるとは限りません。

反対に、トランザクションの検証に失敗した場合は、後で検証に成功した場合にのみ、上位の全てのトランザクションをコミットできることを意味します。

マルチバージョンのデータ構造

BlockーSTMはマルチバージョンのデータ構造を使用して、書き込みと書き込みの競合を回避します。

同じ場所への全ての書き込みは、トランザクションIDと書き込みトランザクションが楽観的に再実行された回数を含むバージョンとともに保存されます。

トランザクションtxがメモリ位置を読み取る時、関連づけられたバージョンと共に、事前設定された順序でtxの前に現れる最上位のトランザクションによってこの位置に書き込まれた値をマルチバージョンデータ構造から取得します。

検証

実行中、トランザクションはread-setとwrite-setを記録します。

検証中に、読み取りセット内の全てのメモリ位置が読み取られ、返されたバージョンが読み取りセットに格納されていう対応するバージョンと比較されます。

コラボスケジュール

BlockーSTMは、スレッド間の検証および実行タスクを調整するための協調スケジューラを導入しています。

事前設定されあt順序は、トランザクションが順番にコミットされる必要があることを示しているため、トランザクション実行の検証が成功しても、コミットできることは保証されません。

これは、ブロック内の以前のトランザクションを注視して再実行srううと、読み取りセットが無効になり、再実行が必要になる可能性があるためです。

したがって、トランザクションと実行スレッド間の静的マッピングは機能しません。

代わりに、協調スケジューラは下位トランザクションの実行および検証タスクを優先します。

ただし、順序付きセットと優先度キューは、マルチコア環境で拡張sるうのが難しいことで有名です。

BlockーSTMは、カウントベースのアプローチを使用してこの問題を回避します。

動的依存関係推定

BlockーSTM事前設定された順序を利用して、アボートを劇的に回避します。

これは、アボートがカスケードして過剰な量の無駄な作業につながる可能性があるため、

STMシステムのパフォーマンスゲームの名前です。

検証が失敗すると、トランザクションの最後の実行の書き込みセットを使用して、マルチバージョンデータ構造内の全ての書き込みを推定としてマークすることにより、依存関係を推定します。

別のトランザクションが多値データ構造からESTIMATION値を読み取ると、依存関係が解決されるのを待つことができます。

ESTIMATIONを書き込んだトランザクションが実際に同じものに買い込む場合、推定がなければ処理は続行されますが、可能性は高くなります。

目標

ワークロード内の実際のアクセス競合を考慮して、可能な最大の固有のスピードアップを引き出す並列実行エンジンを統計します。

最高のプログラミングとユーザーエクスペリエンスを実現するには、アルゴリズムがユーザーに対して透過的である必要があります。

一部のブロックチェーン並列実行エンジンで採用されている代替アプローチは、ユーザーに事前に依存関係を宣言させることです。

これにより、トランザクションで実行できることが大幅に制限され、トランザクションの分割または再試行が必要になる場合があります。

代わりに、このようなコストとプログラミングの煩わしさを回避するために、並列実行エンジンのシステム設計目標は全ての競合を内部で管理し、ワークロードに自動的に適応することです。

STMアプローチ

ソフトウェアトランザクショなるメモリ(STM)ライブラリによって開拓されたアカデミックなアプローチは、競合を検出して管理数ためにメモリアクセスを計測することです。

オプティミスティックコンカレンシーを備えたSTMライブラリは、実行中のメモリアクセスを記録し、実行後に全てのトランザクションを検証し、検証で競合が発生した場合はトランザクションを注視して再実行します。

ただし、コンフリクトブックキーピングとアポーとが必要なため、STMライブラリは、カスタマイズされたソリューションと比較してパフォーマンスの制限を受けることが多く、本番環境に展開されることはほとんどありません。

評価

Aptosオープンソースコードベースの安全なRustにBlockーSTMを実装し、並行性のためにRayon・Dashmap・ArcSwapクレートに依存しています。

自明ではないピアツーピアMoveトランザクション(8回の読み取りと5回の書き込み)でシステムを評価しました。

下のグラフでは、Block/STEMとブロックの順次実行を比較しています。

各ブロックには10,000のトランザクションが含まれており、アカウントのak図によって競合と競合のレベルが決まります。

競合が少ない場合、Block STMは32スレッドでの順次実行よりも16倍のスピードアップを達成し、競合が多い場合、Block STMは8倍以上のスピードアップを達成します。

重要なのは、ワークロードが本質的にシーケンシャルである場合、Block STMはわずかなオーバーヘッドを発生させることです。

全体として、Block STMは動的かつ透過的に(ユーザーからのヒントなしで)ワークロードから固有の並列しょりを抽出できます。

関連する研究との詳細な比較については、下記の論文を(英語ですが)参照できます。

https://arxiv.org/pdf/2203.06871.pdf

異なる競合レベルでのブロックSTMパフォーマンス

このパフォーマンスを得るには下記です。

共同スケジューラとマルチバージョニング技術を併用することで、Block STMは事前に設定されたトランザクションの順序を活用して依存関係を推定し、無駄な作業量を大幅に削減できます。

協調スケジューラはアルゴリズムの重要な部分であり、パフォーマンスが重要なロジックのほとんどが含まれています。


特に、次のことが保証されます。

・中止されたトランザクションは全て再実行されますが、同じトランザクションが複数のスレッドによって同時に実行されることはない

・トランザクションが再実行された場合、上位の全てのトランザクションを再検証する必要がある(その結果、同じトランザクションの実行が異なるスレッドによって同時に検証される可能性があるが、中止できなくなるのは多くても1つだけ)

・依存関係が発生したトランザクションは、依存関係が解決された後に再開される

・全てのトランザクションは最終的にコミットされる


問題点は、同期のオーバーヘッドをできるだけ少なくして上記を保証することです。

実行タスクと検証タスクを追跡する、単純だがコストのかかる方法は、2つの優先キュー(または重複を避けるための順序が付けられたセット)は、2つの優先キュー(または重複を避けるための順序づけられたセット)を持つことです。

依存関係が解決されるか、検証が中止されると、対応するトランザクションの実行タスクが実行キューに追加されます。

同時に、トランザクションが実行されると、事前に設定された順序で上位の全てのトランザクションに対して検証タスクが作成され、検証キューに追加されます。

効率的な同時順序集合

代わりに、Block STMは事前に設定されたトランザクションの順序を活用し、2つのアトミックカウンターを使用します。

これらのカウンターは、実行または検証が必要なトランザクションの下限インデックスを追跡します。

各トランザクションのステータスを知る方法と組み合わせると、これらのインデックスを使用して、単純なアプローチから順序付きセットの背マンティクスを効率的にエミュレートできます。

擦れっっ度は、より低いインデックスでカウンターをフェッチしてインクリメントすることで繰り返しタスクを取得しようとし、ステータスを読み取って、対応するトランザクションの実行準備が整っているかどうかを確認またはカウンターによっては検証します。

更に、フェッチ&インクリメントはスレッドを様々なインデックスに自然に分散させ、ステータス情報が激しく競合しないようにするため、mutexを使用して実装を簡素化できます。

ただしロックフリーの実装は可能ですが、ベンチマークでは大幅な改善は見られません。


トランザクションの可能なステータスは下の図のとおりです。

このパラメータiは、トランザクションが再実行された回数です。


ロックを使用して依存関係のリストを同期しますが、注意を怠ると、協調スケジューラが回避しなければならない微妙な競合が依然として発生する可能性があります。

レイジーコミットメカニズム

BlockーSTMは、ブロック全体をコミットして、個々のトランザクションを安全にコミットできるタイミングを追跡するための同期コストを排除します。

つまり、次の全ての条件が満たされている場合、ブロック全体をコミットできます。

①実行インデックスと検証インデックスの両方がブロックサイズに達する

②進行中の検証および実行タスクはない

③全てのトランザクションのステータスはEXECUTED


「wat too too rigorous for a systems result」の照明で証明したように、Block-STMアルゴリズムの最初の2つの条件は3つの条件を暗示しています。

1と2をアトミックに検証するために、2つの追加カウンターを導入しています。

最初のカウンターは、進行中のタスクの数を追跡します。

コード内の間違った場所でこのカウンターをインクリメントまたはデクリメントするのは簡単で、2を確認できません。

このようなバグを回避するために、Resource Acquition Is Intialization(RAII)パターンを使用してカウンターをタスクガードと結合し、タスクがディスパッチされる前とタスクが完了した後にそれぞれ増加・減少するようにしました。


実行インデックスと検証インデックスを追跡するカウンターと共にこのカウンターをアトミックに読み取るには、二重収集手法を使用します。

これには、実行カウンターと検証カウンターが減少した回数を追跡するために、4つ目のアトミックカウンターを導入する必要があります。

次に、全てのカウンターの値を2回収集し(順序が重要)、両方のケースで条件1と2が満たされているばあい、証明したように、その間のある時点で、条件1と2は確かに同時に満たされました。

この場合、ブロック全体が安全にコミットされます。

これ以上の検証や実行タスクは不要であり、作成されることもありません。

課題

スマートコントラクトの実行は、ブロックチェーンの主要なスループットのボトルネックです。

ブロックを提案し、その順序に同意した後、バリデーターは順序づけられたブロックでトランザクションを実行する必要があります。

そしてバリデーターは同じ最終状態に到達する必要があります。

またこれは、トランザクションの順次実行に対応する必要があります。

根本的な解決策がないため、現在のブロックチェーンは順次実行されるか、πzフォーマンスを向上さえるために非常に並列なワークロード(つまり内部競合がない)を必要とします。

シーケンシャルな実行はうまくスケーリングできず、幅広いスマートコントラクトを考えると、全てのトランザクションが交換可能であると仮定することは非現実的です。


Aptos専門知識はこちらです。→【 Aptosブロックチェーンについて 】専門知識詳細

仮想通貨・Defi・NFT
スポンサーリンク
\Follow/
スポンサーリンク
\Follow me/
\Follow/
Miories
タイトルとURLをコピーしました