【Bullshark】順序付けのプロセスの抽象化,数学ベース
TODO: バリデータの投票状態を図解するとなお良い
プロセス番号を割り振って,1つの画像で何が起きているのかをわかるようにする
一応完成
プロセス
wave_{w-1}のround4で選出されたwave_wのsteady-state leaderとfallback leaderが選出される
リーダー選出はここで行われる
Narwhalによってすでに処理されたサブDAGを対象に最後にコミットされたサブダグとリーダースケジュールをリカバーのために取得する,
spawn_consensus()
get_restored_consensus_output()
Primary::start()
spawn_primary()
--- ここからが本当のBullshark構造体の出番
新しいBullshark構造体のインスタンスを生成する
Bullshark::new()
Bullshark構造体
コンセンサスプロトコルでの処理を開始し,
Consensus構造体
run()メソッド
バリデータが新しい証明書を受信することで,NarwhalでのサブDAGとなるcert_AがBullsharkに渡される
Consensus::spawn()
run_inner()
Bullshark::process_certificate()メソッドに対してConsensusState構造体を持つConsensus構造体とその証明書を渡す
ConsensusState構造体
wave wでround1でanchor-leader_A1が配置され,全てのバリデータへブロードキャストされる
round2でn = 4 (v1, v2, v3, v4), f = 1とする.v1とv2がそれぞれA1に投票する
A1がquorum(f+1)を達成するとこれが他の全てのバリデータに同期される
この結果から,round1のanchor-leader_A1はsteady-state leaderと定義される
round3のためのsteady-state leaderであるanchor leader a2が選出される
ここもリーダー選出
round 3でanchor-leader_A2が配置されブロードキャストされる
round 4でv2とv3とv4がa2に投票する
round 4は偶数ラウンドであるので,最新のラウンドと現在のConsensusState構造体をBullshark::commit_leader()に渡す
process_certificate()
A2がquorum(f+1)を達成し,これが他の全てのバリデータに同期される
w+1のためのsteady-state leaderとfallback leaderが選出される
次のwaveのリーダー選出
1つ前のラウンド(子ラウンド)でf+1のQuorumを達成していることを検証(validate)する
commit_leader()
Bullshark::commit_leader()がBullshark::process_certificate()内で受け取った引数をそのままBullshark::order_leaders()に渡し,最新のラウンド-2から最後にコミットされたラウンド+2の範囲を指定する
commit_leader()
order_leaders()
つまり,ラウンドを2つずつ戻って最後にコミットされたラウンド+2まで行う
e.g., rとr-2の次はr-2とr-4
order_leaders()
Bullshark::linked()で2つの証明書(一番初めのループ処理では最新のラウンドのリーダーと前のリーダーの間)が連結されているかどうかを確認する.
linked()
これらが連結されていれば,推移性はあるものの,DAGベースだとファイナリティ達成と見做せる一面がある.
アンカーリーダー(証明書)間連結されている場合,コミット予定のアンカーリーダーを両端キューでBullshark::commit_leader()に返す
linked()
A1とA2はQuorum IntersectionとDAGの構造によりA1の後にA2がコミットされるように順序付けされる
リーダーを古い順からシーケンスする
commit_leader()
新たに最後にコミットされたDAGをバリデータが保持できるように永続化する
commit_leader()
コミットのトリガーをしたことの通知とトランザクション実行に必要な情報を保持しコンセンサスコミットするためのサブDAGの順序のある集合を返す
このCommittedSubDag構造体が決定論的ルールによってトランザクションの順序付けがされる
Outcome::Commitが通知
commit_leader()
CommittedSubDag
process_certificate()もその集合を集めて同じことをやっている
トランザクションを実行するクライアントを生成する.
spawn_consensus()のConsensus::spawn()
Executor::spawn()
spawn_subscriber()
サブDAG内の各証明書のすべてのバッチを保持するConsensusの出力をConsensus Handlerに渡す
run_notify(state, rx_notifier, rx_shutdown_notify)
handle_consensus_output(message)
ConsensusOutput構造体
最後にコミットされたラウンドとConsensusの出力にあるリーダーラウンドと違うことを確認する
handle_consensus_output()
トランザクションが重複していないこと,すでに処理されていないことを確認
handle_consensus_output()
コミットされたサブDAGをもとに最終的な実行トランザクションをガスフィーに従ってトランザクションの順序付けを行う
アンカー間の並び替えもトランザクションベースではここで行われている,決定論ルール
handle_consensus_output()
ConsensusTransactionOrdering enum, sui/crates/sui-protocol-config/src/lib.rs
コミットに失敗した証明書はNarwhalに返す
run_inner()
SuiNodeを起動し,プロトコルやメトリクス,トランザクションマネージャ等も初期化されている
起動
sui-node/src/main.rs
start_async()
初期化
AuthorityState::new()
ここから準備完了の証明書の実行処理の行うタスクを開始する
execution_process()
新しいtxが処理可能になるたびにループ処理を実行する,実行中に恒久的なエラーは起こるはずがなく,一時的な障害のために最大10回,証明書を実行するロジック処理を行うAuthorityState::try_execute_immediately()を実行,再試行する.再試行のインターバルは1秒
execution_process()
try_execute_immediately()
これは以下のことを保証している
これはロックされている前提であり,ロックの設定の保証ができない場合,execute_certificate()を実行する
ロックはenqueue_impl()で実行されている
まだ実行していないトランザクションだけを集める
対象トランザクション内のオブジェクトのロック情報を取得する
self.inner.write()で書き込みロックを取得する
multi_input_objects_available()でオブジェクトの可用性を確認
オブジェクトの可用性とキーをペアする
enqueue_impl()を使っているリーフからルートの順
enqueue()で実行されている
enqueue_certificates()で実行されている
enqueue_certificates_for_execution()で実行されている
execute_certificate()で実行されている
handle_submit_to_consensus()で実行されている
handle_transaction_v2()で実行されている
transaction_v2_impl()
execute_certificate()
実行と出力のコミットは原子的に行われ、クラッシュした実行は観察可能な影響を持たない
実行が成功した場合、出力はストレージにのみ書き込まれる
同じトランザクションの同時実行を防ぎ,トランザクションの効果がすでに書き込まれているかを確認し,重複実行を避けるようにする
try_execute_immediately()
トランザクション実行に必要な入力オブジェクトを読み取る
read_objects_for_execution()
try_execute_immediately()
実際の証明書の処理を開始し,トランザクションの実行ロックを取得し,実行準備のための検証を行う
この検証(validate)はowned and shared locksについて,データベースから状態を読み取るので副作用はない やるのは,prepare_certificate()
process_certificate()
try_execute_immediately()
トランザクションをコミットする
ファイナリティ達成の瞬間
commit_certificate()
トランザクションキーと効果の署名をエポックストアに挿入します。これにより、トランザクションの記録が永続化されます。
commit_certificate()
トランザクションとその出力オブジェクトがコミットされたことをTransaction Managerに通知します。
notify_commit()で通知
commit_certificate()
Transaction Managerの構造体を指定
トランザクションがコミットされたことを通知し、ロックを解放
notify_commit()
--- プロセスはここで終了