PolarDB:WAL 並列リプレイ

用語

• Block：データブロック。

• WAL：先行書き込みログ (Write-Ahead Logging)。

• Task Node：並列実行フレームワークにおけるサブタスク実行ノード。1 つのサブタスクを受信して実行できます。

• Task Tag：サブタスクの分類識別子。同じタグを持つサブタスクは、順番に実行する必要があります。

• Hold List：並列実行フレームワークの各子プロセスがリプレイサブタスクをスケジュールして実行するために使用する連結リスト。

仕組み

• 概要

  1 つの WAL ログで複数のデータブロックが変更されることがあります。WAL ログのリプレイプロセスは、次のように定義できます。

  1. i 番目の WAL ログの LSN が LSN<sub>i</sub>​ であり、m 個のデータブロックを変更すると仮定します。i 番目の WAL ログによって変更されたデータブロックのリストは、Block<sub>i</sub>​=[Block<sub>i,0</sub>​,Block<sub>i,1</sub>​,...,Block<sub>i,m</sub>​] と表されます。

  2. 最小のリプレイサブタスクは Task<sub>i,j</sub> = LSN<sub>i</sub> -> Block<sub>i,j</sub> と定義されます。このサブタスクは、データブロック Block<sub>i,j</sub> 上で i 番目の WAL ログをリプレイすることを表します。

  3. したがって、m 個のブロックを変更する WAL ログは、m 個のリプレイサブタスクのコレクションとして表すことができます：TASK<sub>i,∗</sub> = [Task<sub>i,0</sub>, Task<sub>i,1</sub>, ..., Task<sub>i,m</sub>]。

  4. さらに、複数の WAL ログは、一連のリプレイサブタスクのコレクションとして表すことができます：TASK<sub>∗,∗</sub> = [Task<sub>0,∗</sub>, Task<sub>1,∗</sub>, ..., Task<sub>N,∗</sub>]。

  ログリプレイサブタスクのコレクション Task<sub>∗,∗</sub> では、サブタスクの実行は必ずしも先行するサブタスクの結果に依存しません。

  リプレイサブタスクのコレクションが TASK<sub>∗,∗</sub> = [Task<sub>0,∗</sub>, Task<sub>1,∗</sub>, Task<sub>2,∗</sub>] であると仮定します。ここで、

  • Task<sub>0,∗</sub> = [Task<sub>0,0</sub>, Task<sub>0,1</sub>, Task<sub>0,2</sub>]

  • Task<sub>1,∗</sub> = [Task<sub>1,0</sub>, Task<sub>1,1</sub>]

  • Task<sub>2,∗</sub> = [Task<sub>2,0</sub>]

  また、Block_0,0 = Block_1,0、Block_0,1 = Block_1,1、および Block_0,2 = Block_2,0 とします。

  この場合、並列でリプレイできるサブタスクのコレクションは [Task_0,0, Task_1,0]、[Task_0,1, Task_1,1]、[Task_0,2, Task_2,0] の 3 つです。

  まとめると、リプレイサブタスクのコレクション内の多くのサブタスクシーケンスは、最終結果の一貫性に影響を与えることなく並列実行できます。PolarDB は、この概念を並列タスク実行フレームワークで使用しており、WAL ログのリプレイプロセスに適用されます。

• 並列タスク実行フレームワーク

  共有メモリのセグメントは、同時実行プロセス数に基づいて均等に分割されます。各セグメントはサーキュラーキューとして機能し、1 つのプロセスに割り当てられます。各サーキュラーキューの深さは、パラメーターを設定することで構成できます。

  • ディスパッチャープロセス。

    • タスクを指定されたプロセスにディスパッチすることで、同時実行スケジューリングを制御します。

    • 完了したタスクをキューから削除します。

  • プロセスグループ。

    グループ内の各プロセスは、対応するサーキュラーキューからタスクを取得し、タスクの状態に基づいて実行します。

  • タスク

    サーキュラーキューはタスクノードで構成されます。各タスクノードには、Idle、Running、Hold、Finished、Removed の 5 つの状態のいずれかがあります。

    • Idle：タスクノードにタスクが割り当てられていません。

    • Running：タスクノードにタスクが割り当てられており、実行待機中または実行中です。

    • Hold：タスクノード内のタスクは先行タスクに依存関係があり、そのタスクが完了するのを待つ必要があります。

    • Finished：プロセスグループ内のプロセスがタスクの実行を完了しました。

    • Removed：ディスパッチャープロセスがタスクの状態が Finished であることを検出すると、そのすべての前提条件タスクも Finished 状態である必要があります。その後、ディスパッチャープロセスは状態を Removed に変更します。この状態は、ディスパッチャープロセスが管理構造体からタスクとその前提条件を削除したことを示します。このメカニズムにより、ディスパッチャープロセスが依存タスクの結果を正しい順序で処理することが保証されます。

    上記のステートマシン遷移において、黒い線でマークされた遷移はディスパッチャープロセスで完了します。オレンジ色の線でマークされた遷移は、並列リプレイプロセスグループで完了します。

  • ディスパッチャープロセス

    ディスパッチャープロセスは、タスクハッシュマップ、タスク実行キュー、タスクアイドルノードの 3 つの主要なデータ構造を使用します。

    • タスクハッシュマップ：タスクタグとそれに対応するタスク実行リストとの間のハッシュマッピングを記録します。

      • 各タスクには特定のタスクタグがあります。2 つのタスクに依存関係がある場合、それらは同じタスクタグを共有します。

      • タスクがディスパッチされる際、タスクに前提条件がある場合、その状態は Hold とマークされます。タスクは、その前提条件が実行されるのを待つ必要があります。

    • タスク実行キュー：現在実行中のタスクを記録します。

    • タスクアイドルノード：プロセスグループ内の異なるプロセスに対して、現在 Idle 状態にあるタスクノードを記録します。

    ディスパッチャーは、以下のスケジューリングポリシーを使用します。

    • 新しいタスクと同じタスクタグを持つタスクがすでに実行中の場合、新しいタスクは、そのタスクタグの連結リストの最後のタスクを処理しているプロセスに優先的に割り当てられます。このポリシーは、依存関係のあるタスクを同じプロセスで実行することで、プロセス間の同期にかかるオーバーヘッドを削減することを目的としています。

    • 優先プロセスのキューがいっぱいの場合、または同じタスクタグを持つタスクが実行中でない場合、プロセスグループから順番にプロセスが選択されます。その後、そのプロセスのキューから Idle 状態のタスクノードが取得され、タスクがスケジュールされます。このポリシーは、タスクをすべてのプロセスにできるだけ均等に分散させることを目的としています。

    

  • プロセスグループ

    この並列実行は、同じタスクノードデータ構造を共有する同じタイプのタスクに適用されます。プロセスグループが初期化されるとき、SchedContext を構成して、特定のタスクを実行する関数ポインターを指定できます。

    • TaskStartup：プロセスがタスクを実行する前に必要な初期化操作を実行します。

    • TaskHandler：受信したタスクノードに基づいて特定のタスクを実行します。

    • TaskCleanup：プロセスが終了する前に必要なクリーンアップ操作を実行します。

    

    プロセスグループ内のプロセスは、サーキュラーキューからタスクノードを取得します。タスクノードの状態が Hold の場合、プロセスはタスクノードを Hold List の末尾に挿入します。タスクノードの状態が Running の場合、プロセスは TaskHandler を呼び出してタスクを実行します。TaskHandler が失敗した場合、システムはタスクノードにリトライ回数 (デフォルト：3) を設定し、タスクノードを Hold List の先頭に挿入します。

    プロセスは、Hold List の先頭から実行可能なタスクを検索します。タスクの状態が Running で、待機回数が 0 の場合、プロセスはタスクを実行します。タスクの状態が Running で、待機回数が 0 より大きい場合、プロセスは待機回数を 1 減らします。

• [WAL 並列リプレイ]

  LogIndex データは、先行書き込みログ (WAL) とそれが変更するデータブロックとの間のマッピングを記録し、LSN による取得もサポートします。スタンバイノードでの WAL ログの継続的なリプレイ中、PolarDB は並列タスク実行フレームワークを使用します。このフレームワークは LogIndex データを使用して WAL ログのリプレイタスクを並列化し、スタンバイノードでのデータ同期を高速化します。

  ワークフロー

  • Startup プロセス：WAL ログを解析し、WAL ログをリプレイせずに LogIndex データを構築します。

  • LogIndex BGW リプレイプロセス：並列タスク実行フレームワークのディスパッチャープロセスとして機能します。このプロセスは LSN を使用して LogIndex データを取得し、ログリプレイサブタスクを構築し、それらを並列リプレイプロセスグループに割り当てます。

  • 並列リプレイプロセスグループ内のプロセス：ログリプレイサブタスクを実行し、データブロック上で単一のログをリプレイします。

  • バックエンドプロセス：データブロックを読み取るとき、プロセスは PageTag を使用して LogIndex データを取得します。この操作により、ブロックを変更した LSN ログの連結リストが取得されます。その後、プロセスはデータブロック上でログチェーン全体をリプレイします。

  • ディスパッチャープロセスは LSN を使用して LogIndex データを取得します。LogIndex の挿入順に PageTag とそれに対応する LSN を列挙して、タスクノードとして機能する {LSN -> PageTag} マッピングを構築します。

  • PageTag は、タスクノードのタスクタグとして使用されます。

  • 列挙されたタスクノードは、リプレイのために並列実行フレームワークのプロセスグループの子プロセスにディスパッチされます。

使用ガイド

polar_enable_parallel_replay_standby_mode = ON