クラウドネイティブ データ ウェアハウスは、大規模クラスター内の関連クエリのパフォーマンス問題をどのように解決するのでしょうか?

著者 |ユ・イー

序文

近年、データベース システムによって提供されるデータの量は飛躍的に増加しており、同時に、ますます複雑化するビジネス ニーズやますます厳しくなるリアルタイム要件などの課題にも直面しています。スタンドアロンのデータベース システムは徐々に現代のデータベース サービス要件を満たせなくなってきたため、分散データベース/データ ウェアハウスがますます広く使用されるようになりました。

リアルタイム分析 (OLAP) の分野では、分散データ ウェアハウスはシステムの分散特性を十分に発揮し、複雑な OLAP タスクを分解してシステム内のすべてのノードに分散して計算することで、分析パフォーマンスを向上させることができます。分散型データ ウェアハウスは、増加するユーザーのビジネス データ量のニーズを満たすために、システム ノードの容量をより簡単に拡張することもできます。しかし、分散データ ウェアハウスのユーザーが避けることのできない問題の 1 つは、データ ウェアハウス クラスターのサイズが大きくなるにつれて、容量拡張のコスト効率が低下することです。

この現象が発生する理由の 1 つは、データベース サービスで最も広く使用されている演算子の 1 つであるテーブル結合が、分散コンピューティングにおけるシステム ノード間のデータ相互作用に依存していることです。分散クラスターの規模が大きくなると、ノード間のデータ相互作用のコストが大幅に増加します。この場合、分散システムのネットワーク処理能力が大いに試され、データ相互作用の負担を軽減するために、ユーザーのデータ テーブル設計と SQL 記述能力が頼りになります。

この問題に対処するために、業界のさまざまな分散データベース システムでは、さまざまな Join ランタイム フィルタリング アルゴリズムが提案されています。 AnalyticDB for PostgreSQL（以下、ADB PG）は、PB レベルの MPP アーキテクチャのクラウドネイティブ データ ウェアハウスであり、上記のような課題にも直面しています。この記事では、ADB PG アーキテクチャ設計の観点から ADB PG でのランタイム フィルターの実装について説明し、ブルーム フィルターに基づく ADB PG 動的結合フィルターの技術的な詳細を紹介します。

ADB PG アーキテクチャの概要

ADB PG はオープンソース プロジェクト Greenplum 上に構築されています。これは、単一マシンの PostgreSQL の拡張です。単一または複数のサーバー上で複数の PG サービスを同時に起動し、クラスターを形成して分散方式でデータベース サービスを提供します。 ADB PG は各 PG サービスをセグメントと呼び、スライスの概念を導入します。スライスは、分散システムのネットワーク構造を解決するために使用されます。データベースに MPP 多段階計算が含まれる場合、たとえば、ハッシュ結合の左側のテーブルと右側のテーブルの結合キーが同じハッシュ分布を満たさない場合、結合キーをネットワーク転送を通じて再配布する必要があります。 ADB PG は、ネットワーク伝送の前段階と後段階を異なるスライスに分割します。以下は、ADB PG クラスターの図です。

このアーキテクチャにおける大規模クラスターでのテーブル結合のパフォーマンス問題をどのように解決するのでしょうか?この問題を解決するための業界における 1 つのソリューションは、ネットワーク プロキシ ノードを導入することです。同じマシン内のセグメントはネットワーク データをローカル プロキシ ノードに送信し、プロキシ ノードは他のマシン上のプロキシ ノードとネットワークの送受信を実行して、ネットワークの輻輳を軽減します。このソリューションは、ADB PG アーキテクチャに大きな課題をもたらし、Join のネットワーク シャッフル オーバーヘッドを根本的に削減するものではありません。そのため、結合のルートから結合によって計算されるデータの量を削減するために、AnalyticDB PG は結合ランタイム フィルター ソリューションを設計し、実装しました。

ランタイムフィルタとブルームフィルタ

ランタイム フィルタの目的は、結合計算の前に一部のデータをフィルタリングすることであり、フィルタ実装「キャリア」が必要です。 ADB PG のアーキテクチャ設計とストレージ層およびネットワーク層の特性を考慮し、ランタイム フィルターの実装形式として Bloom Filter を使用することを選択しました。

ブルーム フィルタは、要素がセットに属しているかどうかを判断するためによく使用される確率的なデータ構造です。 Bloom Filter の利点は、非常に高いスペース効率と、通常は高い計算パフォーマンスを備えていることです。欠点は、偽陽性率はあるものの、偽陰性率はないこと、つまり、要素がセットに属するかどうかを判断するブルーム フィルタの結果が単純に真か偽かではなく、「真である可能性」または「偽である可能性」であることです。

上図は標準的なブルームフィルタの計算アイデアの概略図で、0と1はブルームフィルタが集合情報を表すために使用するビット配列、つまり1ビットずつ格納されます。上記の x、y、z は、ブルーム フィルターに挿入される 3 つの要素を表します。ハッシュ値は3つのハッシュアルゴリズムを使用して計算され、ビット配列に設定されます。以下は、要素 w がセットに属するかどうかを判定します。 3つのハッシュ値のうち1つがビット配列に設定されていないため、wがセットに属していないことは確かです。

ブルーム フィルタは通常、次のパラメータで記述されます。

• m --- ブルームフィルタのビット配列サイズ m ビット
• k --- 使用されるハッシュ関数の数
• p --- 偽陽性率
• n --- ブルームフィルタによって挿入された要素の数

導出プロセスを省略し、パラメータ間の関係を直接示します。

ブルーム フィルタが十分に大きい場合は、次のように簡略化できます。

Bloom Filter を設計する際には、実際のコンピューティング シナリオに基づいて n と m を事前に決定できます。上記の式は、独立変数 k と従属変数 p を持つ関数 p(k) とみなすことができます。この関数は、k > 0 の場合 (n:m によって決定)、通常は単調ではありません。したがって、ブルームフィルタを設計する際には、最小の偽陽性率 p を得るためにハッシュ関数の数 k をどのように決定するかを考慮する必要があります。上記の式によれば、p が最小値のとき、対応する k の値は次のようになります。

ブルームフィルタパラメータ設計:

Bloom Filter を ADB PG Join フィルタリング最適化に適用するには、まず Bloom Filter のパラメータを設計して選択する必要があります。 Bloom Filter によって挿入される要素数 n については、実行プランで取得される Join right テーブル プランの行数をそのまま使用できます。理想的なフィルタリング率を得て、誤検出率 p を減らすために、ADB PG は PG のハイバージョン Bloom Filter の考え方を採用し、Bloom FIlter のバイトサイズを n の 2 倍、つまり全体の n:m が 1:16 になるように設計します。この設計では、最適な k 値は 11 であると計算できます。p(k) 関数を下の図に示します。 k = 11 の場合、最小 p = 0.046% が得られます。

k = 11 は、各要素に対して 11 個のハッシュ値を計算して Bloom Filter ビット配列に挿入する必要があることを意味します。これは ADB PG では受け入れられず、ブルーム フィルターを構築するコストは明らかに高すぎます。 ADB PG は、ブルーム フィルタを構築する際、誤判定率やハッシュ計算などの要素を考慮して適切な k 値を選択します。

Bloom Filter を構築するための基本原則を決定した後、次のステップはエンジニアリングの実装です。 Bloom Filter のエンジニアリング実装は非常にシンプルで効率的です。通常、ビットセット配列を直接使用して Bloom Filter を構築し、ビット操作を通じて Bloom Filter の挿入と検索を実装できます。次の図は、Bloom Filter ビットセット配列に要素を挿入するための計算図を示しています。

ADB PG の動的結合フィルター

ADB PG ハッシュ結合のブルーム フィルターの設計が完了したら、結合のランタイム フィルターにブルーム フィルターを適用する方法について説明します。 ADB PG では、ブルーム フィルターに基づくランタイム フィルターを動的結合フィルターと呼びます。

1. 動的結合フィルタの実装

ADB PG オプティマイザは通常、右側のテーブルを小さいテーブルとして、左側のテーブルを大きいテーブルとして選択するため、ADB PG は動的結合フィルタを一方向のフィルタリング機能として設計します。つまり、右側のテーブルが左側のテーブルをフィルタリングするためにのみ使用され、左側のテーブルが右側のテーブルをフィルタリングする形式は当面考慮されません。同時に、ハッシュ結合の左テーブルリンク内のさまざまな演算子のフィルタリングに動的結合フィルタを柔軟に適用することもできます。

ハッシュ結合の形式が異なるため、動的結合フィルターの実装は、ローカル結合と MPP 結合の 2 つの形式にまとめることができ、ランタイム フィルターに演算子をプッシュダウンする機能があるかどうかに基づいてさらに区別されます。

ローカル結合

ローカル結合とは、左側のテーブルと右側のテーブルの結合キーが同じハッシュ分布を満たし、データをシャッフルする必要がないことを意味します。このとき、ハッシュ、ハッシュ結合、左テーブルスキャンは同じスライス、つまり同じプロセス内にあります。 Bloom Filter を左のテーブルの Scan 演算子に直接渡して、プロセス空間で出力をフィルター処理できます。

MPP参加

MPP 結合とは、左側のテーブルと右側のテーブルの結合キーが同じハッシュ分布を満たしておらず、結合キーに基づいてデータをシャッフルする必要があることを意味します。前述のように、AnalyticDB for PG のハッシュ結合とハッシュ演算子は同じスライスに存在する必要があります。したがって、基本原理に基づいて、左テーブルのシャッフル、つまりハッシュ結合の前に左テーブルに動きがあるシナリオのみを考慮する必要があります。

MPP Join が存在する別の状況は、左側のテーブルが Motion 下の単純な Scan ではなく、Join Key の Bloom Filter を Scan にプッシュするための関連情報がないことです。そして、最終的な基準は、ネットワーク経由で送信されるデータの量を削減することです。モーション センダーのデータを削減するには、モーションの前に Bloom Filter を配置します。

2. ブルームフィルタネットワーク伝送

動的結合フィルターは、各コンピューティング ノードにローカル ブルーム フィルターを確立します。各コンピューティング ノードは、フィルタリング計算を開始する前に、他のすべてのノードのブルーム フィルターを収集し、完全なブルーム フィルターをローカルで形成する必要があります。 Bloom Filter の送信と受信を、フル送信とビット送信の 2 つのモードに分けます。送信する前に、2 つのモードのデータ サイズを決定し、データ サイズが小さいモードを適応的に選択できます。

ブルームフィルター完全透過

ブルームフィルタビット伝送

パフォーマンステスト

次に、ADB PG Dynamic Join Filter のパフォーマンスをテストします。テスト クラスターは、ADB PG パブリック クラウド上に構築されたインスタンスです。テストでは、TPC-H 1TB テスト セット (スケール = 10000) を使用します。このテストでは、動的結合フィルター機能をオン/オフにして実行パフォーマンスを比較します。次の図は、さまざまな実行パフォーマンスでの TPC-H クエリ テストの結果を示しています。

Dynamic Join Filter により、Q5、Q8、Q9、Q17 で大幅なパフォーマンスの向上が達成されたことがわかります。その中で、Q17 は最適化パフォーマンスが最も優れており、実行時間は 137 秒から 8 秒に最適化されています。 Q10 ではパフォーマンスがわずかに低下し、10 秒から 12 秒になりました。これは、Q10 の結合キーが完全に一致し、動的結合フィルターが動的な高度なフィルタリングを実行できないためです。オプティマイザーはコストを正確に見積もることができず、プランでは引き続き動的結合フィルターが使用されます。さらに、Q20 はオプティマイザのプッシュダウン ルールにより、動的結合フィルターも選択しませんでした。実際、分析の結果、Q20 は Q17 と類似しており、Dynamic Join Filter の使用に適しています。これらの問題を解決するために、ADB PG オプティマイザー関連の機能は現在も開発と反復が進められています。

まとめと今後の計画

ダイナミック ジョイン フィルターは、ADB PG アーキテクチャ設計とストレージ層およびネットワーク層の特性に基づいて、ジョイン ランタイム フィルターの実装形式としてブルーム フィルターを使用します。 TPC-H テストで大幅なパフォーマンス向上を達成しました。今後は、顧客体験の向上に向けて、以下の側面をさらに開発・最適化していきます。

動的結合フィルター機能を改善して、ハッシュ結合のさまざまなモードをサポートし、さらにマージソート結合とネストループ結合の最適化に拡張しました。

オプティマイザのコスト見積モデルの精度を向上させ、オプティマイザのプッシュダウン ルールを改善します。

ランタイム フィルターの適応スケジューリング。

Cloud Native Data Warehouse ADB PG のホームページへようこそ。詳細はこちら: https://help.aliyun.com/product/35364.html