PolarDB-X In-memory Column Index | 列指向エンジンの誕生

本記事はこちらのブログを参考にしています。
翻訳にはアリババクラウドのModelStudio(Qwen)を使用しております。

Lijiu による

背景

2022年5月、PolarDB-X はデータベースの HTAP（Hybrid Transactional/Analytical Processing）統合能力を強化するために、ハイブリッド行・列ストレージアーキテクチャの開発を開始しました。これは、データ圧縮率が高く、ストレージコストを削減できる列形式でのデータ保存により、分析処理（AP）能力をさらに向上させることを目指しています。これにより、ユーザーはデータ分析シナリオでより良い体験を得ることができます。2024年4月にリリースされた PolarDB-X V2.4 では、インメモリ列インデックス（IMCI）が導入され、元のアーキテクチャ に 列エンジンノード を追加しました。次の図は現在のアーキテクチャを示しています。
! 1

コンピュートノード (CN)

システムのエントリーポイントとして設計されており、SQL パーサー、オプティマイザー、エグゼキューターなどのモジュールが含まれます。CN はステートレスであり、分散データルーティング、計算、動的スケジューリング、分散トランザクションの 2 相コミット（2PC）調整、およびグローバルセカンダリインデックスの維持を担当します。また、SQL スロットリングや三役モードなどの企業レベルの機能も提供します。

データノード (DN)

DN はデータの永続化を担当し、Paxos プロトコルに基づいて高信頼性と強整合性を保証します。また、マルチバージョン同時実行制御（MVCC）を通じて分散トランザクションの可視性を維持します。

グローバルメタサービス (GMS)

GMS はテーブル、スキーマ、統計などのグローバルに一貫したシステムメタデータを維持します。アカウントや権限などのセキュリティ情報も管理し、タイムスタンプオラクル（TSO）を提供します。

変更データキャプチャ (CDC)

CDC ノードは、MySQL Binlog 形式およびプロトコルと完全に互換性のある増分データサブスクリプション機能を提供します。また、MySQL Replication プロトコルと互換性のあるマスタースレーブレプリケーション機能も提供します。

列ストアノード

列ストアノードは永続的な IMCI を提供し、分散トランザクションのバイナリログをリアルタイムで消費して OSS 上に IMCI を構築し、リアルタイム更新の要件を満たします。CN と組み合わせると、列ストアノードはスナップショット整合性を持つクエリ機能を提供できます。

1. 設計の考え方

最初のステップは、以下の期待に応えるアーキテクチャを決定することです：

• アーキテクチャは既存の行ストレージに影響を与えてはいけません。そのため、リソースを分離する必要があり、列ストアノードが追加されます。
• CN と DN を分離することで、リソース利用率と高可用性が大幅に向上します。
• 分散フレームワークを引き続き使用して拡張性を向上させるため、共有ストレージが採用されます。

これらの考慮事項に基づき、分散データベースの基本的な概要が形成されます。
! 2

図に示すように、左側の PolarDB-X は以前の行ストアアーキテクチャです。このアーキテクチャに列エンジンを追加して、行ストアデータを同期し、共有ストレージに列形式で保存します。読み取り専用の列ストアコンピュートノードは、ユーザーからの SQL リクエストを受け取り、それを演算子に解析してクエリを行い、共有ストレージ内のファイルを読み取ってデータを返します。これにより、各コンポーネントの機能が明確な完全なデータリンクが形成されます。

次のステップは、各コンポーネントの設計を詳細化することです。

第二ステップ：共有ストレージの形式を決定

列ストレージは主に分析計算シナリオ向けです。このデータシナリオには、ストレージにいくつかの要件があります：

• 大規模なストレージ：AP シナリオでは大容量のストレージ、高い拡張性、および拡張可能性が必要です。
• 高帯域幅：AP シナリオには大量の計算と高スレッド並行処理が含まれるため、高帯域幅が必要です。
• 永続性と安全性：これらはストレージにとって不可欠な機能です。
• 最小化されたストレージコスト：すべてのユーザーは、パフォーマンスと信頼性の要件を満たしながら、可能な限りストレージコストを削減したいと考えています。

これらの要素を考慮し、PolarDB-X は Alibaba Cloud Object Storage Service (OSS) を一般的なシナリオとして選択しました。OSS は大規模で安全、低コスト、かつ高信頼性のクラウドストレージサービスであり、99.9999999999% のデータ耐久性と 99.995% のデータ可用性を提供します。通常のユーザーは性能面で 10Gbps の帯域幅を達成でき、最も重要なのはそのストレージコストが非常に低いことです。OSS の低コストにより、列ストレージ費用を大幅に削減できます。さらに、列ストアファイルは異なる圧縮アルゴリズムをサポートしており、通常は 3 倍から 10 倍のデータ圧縮効率を持ち、圧縮コストをさらに削減します。

ただし、OSS はパブリッククラウドユーザーに適しています。他のアプリケーションシナリオでは、NFS や S3 などの他の共有ストレージがサポートされる必要があります。したがって、列エンジンと CN はファイルシステムインターフェースを抽象化する必要があります。これにより、後続のさまざまなストレージモデルとの互換性が容易になります。

第三ステップ：読み取り専用列ストアコンピュートノードの設計

PolarDB-X 行ストアは比較的成熟したコンピュートノード設計ソリューションですが、列ストレージと行ストレージではオプティマイザーやエグゼキューターに大きな違いがあります。AP と TP シナリオは根本的に異なります。そのため、読み取り専用列ストアコンピュートノードは AP シナリオに特化したオプティマイザーとエグゼキューターを設計する必要があります。PolarDB-X は既存の行ストアコンピュートノードに基づいて設計し、同じコードベースを使用しながら異なるモードで起動します。このアプローチにより、ハイブリッド行・列ストレージの最適な実行計画を設計し、行ストレージと列ストレージの利点を最大限に活用できます。ユーザーが SQL 文を実行すると、行ストレージと列ストレージで同時に処理され、結果が返されます。

新しいハイブリッド行・列ストレージのデータベースアーキテクチャにおいて、私たちは多様化するデータ処理ニーズに適応し、データベースの最前線で技術革新を推進するためのベストプラクティスを探求しています。

第四ステップ：適切な列エンジンの設計、データ同期の完了、および行ストレージから列ストレージへの変換

この部分については
しかし、バッチ処理には待機時間が伴うため、パフォーマンスと行-列間の遅延のバランスを取ることが重要です。! 5
前述の図に示されているように、ユーザーはPolarDB-Xの行ストレージにデータを書き込み、トランザクション1から5を順番にコミットします。PolarDB-XのCDCノードはグローバルbinlogを生成するのに時間を要します。このプロセス中、レイテンシは比較的小さく、通常数百ミリ秒以内です。もし列指向エンジンがトランザクションをバッチでコミットする場合、バッチが蓄積されるまで待たなければならず、それが列ストレージと行ストレージ間のレイテンシを増加させる可能性があります。バッチ処理はbinlogの消費を加速しますが、列指向エンジンはトラフィックに基づいて動的にコミットタイミングを決定します。データ量があるサイズに達するか、または列ストレージのレイテンシがしきい値に達した場合、コミットがトリガーされ、列ストレージと行ストレージ間のレイテンシが最小限に保たれます。同時に、列指向エンジンがデータをコミットするたびに、列ストレージバージョンのスナップショットが生成されます（上記の図のV1、V2、V3を参照）。binlogイベントにはCTS値が含まれており、列ストレージバージョンはこの値をバージョン番号としてTSO値を記録します。トランザクションのコミットTSO値は、行ストレージトランザクションの可視性に関連しています。したがって、列ストレージスナップショットに対応する行ストレージスナップショットを取得でき、列指向データと行指向データ間の一貫性検証の理論的根拠を提供します。

2.2 列ストレージ

列指向エンジンによるデータ入力を受けて、トランザクションは1つ以上のbinlogイベントを消費することにより間隔をおいてコミットされます。各トランザクションにはINSERT、DELETE、UPDATEイベントが含まれており、これらはDML操作を表します。これらのイベントは行ストレージに基づいて組み合わされ、データを1行ずつ消費していきます。列指向エンジンはこれらのデータを行ストレージから列ストレージに変換し、共有ストレージOSSにアップロードする必要があります。最初に、PolarDB-Xは列ストレージファイル形式としてApache ORCフォーマットを選択しました。Apache ORCはHadoopエコシステム向けに設計された効率的な列ストレージ形式であり、大規模なデータストレージと処理の効率を向上させます。これはデータウェアハウスのシナリオや分析クエリで広く使用されています。! 6

ORC形式はデータを「ストライプ」と呼ばれる単位で整理します。各ストライプはデータを格納し、インデックス情報を含んでいます。各ストライプの位置はファイルの末尾に記録されており、高速なデータ検索を可能にします。このフォーマットには以下の特徴があります。

• 高性能: 長期的な最適化を経て、Apache ORCは成熟した製品であり、高いI/O読み書き性能を持っています。
• 高圧縮率: Apache ORCはZLIB、SNAPPY、LZO、LZ4、ZSTDなどの複数の圧縮アルゴリズムをサポートしています。
• 柔軟なインデックス構造と統計情報: Apache ORCは多様なインデックスをサポートしており、最大値や最小値などの複数の統計情報を埋め込んでいます。
• 豊富なデータ構造: Apache ORCはstructs、lists、mapsなど複雑なデータ型をサポートしています。

列ストレージフォーマットが決定されました。次に、効率的に行ストレージから列ストレージへの変換を行う方法を考える必要があります。適切なストレージモデルを設計するために考慮すべきいくつかの制約があります。

• 共有ストレージOSSは追記のみをサポートし、ランダムな修正はできません。
• ORC形式の列指向ファイルは通常バッチデータを含み、個々のファイルは比較的大きくなります。

最もシンプルなシナリオでは、INSERT操作のみがあり、すべてのデータが有効であると仮定します。最もシンプルなストレージ構造は次の図に示されています。! 7

完全なプロセスは、まずCSVファイルにデータを追加し、ファイルがいっぱいになったら行ストレージファイルをORC列指向ストレージファイルに変換することです。実際のシナリオではDELETEおよびUPDATE操作があり、既存データの修正がストレージアーキテクチャの複雑さを増します。以下は一般的なプラクティスです。

最初の方法はCopy-on-Write (COW) モデルです。データが更新されるとき、元のデータからレプリカがコピーされ、そのレプリカに対してデータ更新が行われます。更新が完了すると、元のデータは現在のレプリカに置き換えられます。下図に示すように、この方法はファイル更新において災害的になることがあります。ほとんどの場合、各ファイル内のデータのごく一部しか変更されないにもかかわらず、ファイル全体を再書き込みする必要があり、深刻な書き込み増幅問題を引き起こします。したがって、COWモデルはB+ツリーのような小さなデータブロックを持つデータ構造に適しています。このデータ構造では、COWモデルを通じてデータノードを更新でき、許容可能な書き込み増幅をもたらします。! 8

二つ目の方法はLog-Structured Merge (LSM)ツリーモードです。これはLSMツリー構造を使用してデータを保存し、ランダム書き込みを逐次書き込みに変更し、DELETEおよびUPDATE操作に新しいバージョンの値を追加することを指します。メモリ内で書き込みしきい値に達するとSSTファイルが形成され、バックグラウンドでコンパクションによってデータがマージされ、冗長なデータが削除され、データがソートされます。下図に示すように、SSTableファイル形式を列ストレージに変更することで書き込み操作に適応できますが、読み取りパフォーマンスは大幅に低下します。これは複数層のデータを読み取る必要があり、大量のファイルが関与し、マージ処理が必要となるためです。! 9

三つ目の方法はDelta Mainモデルで、LSMツリー構造に似ています。LSMツリーのアイデアに基づき、データは依然として逐次書き込まれ、データの変更はレコードの追加によって実現されます。追加されたレコードはDelta Dataと見なされ、Delta Dataがしきい値に達するとMain Dataに変換されます。ユニット内のデータは範囲、パーティション、またはファイル内のデータと見なすことができます。ビジネス要件に基づいてデータを分離でき、これにより読み取りパフォーマンスが最適化されます。特定の範囲内のデータの場合、Main DataとDelta Dataのみにアクセスすればよく、マージする必要のあるデータ量が大幅に減少します。また、バックグラウンド非同期ス
読み取り時に、ファイルのすべてのビットマップはOR演算を介して1つのビットマップに統合され、ファイルのすべての削除マーカーを表します。パーティション内のすべてのファイルのビットマップデータは、DELファイル（実際にはビットマップのシリアライズされたデータ）に継続的に書き込まれます。これは、ビットマップデータが一般的に小さく、小さなデータの書き込みを避けるために1つのファイルに集約されるためです。
• UPDATEイベントはDELETE操作とINSERT操作に変換されます。
• DDLイベントはデータ変更操作とは別にコミットされます。したがって、DDLイベントは個別に操作を実行します。図には主キーインデックスもあり、これはDELETEイベントのデータ行（およびファイル位置）を迅速に特定するために使用され、削除マーカーを追加します。そのため、カラムナエンジンはkey-valueストアを維持します。各行のデータにはその一意性を示す主キー値があり、位置情報は{ファイルID、インデックスの行番号}で、サイズは4B + 4Bバイトです。したがって、主キーインデックスは小さな値を持つKV永続ストレージです。グループコミットは、複数のINSERT、DELETE、UPDATE操作を含むトランザクションをバッチでコミットすることを意味します。したがって、カラムナエンジンは最初にメモリ内で変更を集約できます。同じ主キー値に対する異なる操作の場合、冗長な履歴バージョンはメモリ内で直接削除でき、コミット操作を減らすことができます。たとえば、挿入後にその行を削除しても追加の書き込みは不要です。同じ主キーに対する任意の書き込み動作は、いくつかの場合に分解できます。

操作タイプ（同じ主キー値）	操作	マージ結果
Insert	mem.add(pk, row)	\
Delete	mem.remove(pk)	\
Update	mem.remove(pk, row1)mem.add(pk, row2)	\
Insert-Insert	\ （主キーの競合、予期しない）	\
Insert-Delete	mem.add(pk, row)mem.remove(pk)	何もなし
Insert-Update	mem.add(pk, row1)mem.remove(pk, row1)mem.add(pk, row2)	mem.add(pk,row2)
Update-Insert	\ （主キーの競合、予期しない）	\
Update-Delete	mem.remove(pk, row1)mem.add(pk, row2)mem.remove(pk, row2)	mem.remove(pk,row1)
Update-Update	mem.remove(pk, row1)mem.add(pk, row2)mem.remove(pk, row2)mem.add(pk, row3)	mem.remove(pk,row1)mem.add(pk,row3)
Delete-Insert	mem.remove(pk)mem.add(pk, row)	mem.remove(pk)mem.add(pk, row)
Delete-Delete	\ （重複削除、予期しない）	\
Delete-Update	\ （存在しないデータの変更、予期しない）	\

これにより、一部の操作は中間データの送信を減らすためにマージおよび簡略化できることがわかります。読み取り専用カラムストアノードからカラムストレージデータを読み取る場合、各パーティションには次の3種類のファイルが含まれます。
• CSVファイル：これは追記専用形式で書き込まれた行ストアデータを含みます。データは複数の列のデータが行ごとに書き込まれた組み合わせであり、CSV形式に似ているため、CSVファイルと呼ばれますが、テキスト形式のファイルではありません。PolarDB-XのCSVデータ形式は特別なバイナリシリアライゼーションを採用しており、一般的なCSV形式での区切り文字の問題を回避できます。さらに、CSVファイルのサイズまたは行数がしきい値に達すると、圧縮が行われ、ファイルがカラムストレージ用のORCファイルに変換されます。
• ORCファイル：これはカラムストレージ形式のデータを含みます。生成後は変更されず、カラムストレージの主要なデータでもあります。各ファイルは範囲内のデータを表し、内部のエントリはソートされています。
• DELファイル：これはパーティション内のすべてのファイルの削除ビットマップマーカーデータを記録します。本質的に、各CSVまたはORCファイルにはDELファイルに保存されている対応するビットマップがあります。

特にDELデータなどのDeltaデータは、可能な限りキャッシュする必要があります。これにより、ORCファイルを読み取る際に無効なデータを迅速にフィルタリングできます。DELデータをメモリに保持することがより有益です。同時に、ORCファイルは範囲内で順序付けられており、ソートキーでソートされているため、簡単にトリミングして条件を満たすデータを読み取ることができます。一方、CSVファイルは順序付けされておらず、トリミングできません。この部分のデータをキャッシュすることで読み取り性能も向上します。したがって、Deltaデータはできるだけ小さくし、最初にキャッシュする必要があります。カラムストレージの主キーインデックスはカラムストアの読み取りノードによって読み取られません。その理由は次の通りです。

1. 主キーインデックスは、カラムナストレージエンジンの書き込みノードが主キーのファイル位置を特定するのに役立ちます。読み取りノードがKVストレージにアクセスできる場合、KVストレージへの分散型同時読み書きアクセスが無視できないほどKVストレージ構造の複雑さを増大させます。KVストレージは主キーとそれが存在するファイルのみを記録します。単一のKV検索は効率的ですが、カラムストレージは大規模なデータ分析やクエリシナリオでより多く使用されます。単一行データのクエリには、行ストレージの方が適しており、効率的な読み取りを提供できます。

2.3 カラムナ主キーインデックス

前述のように、カラムナエンジンには主キーインデックスが含まれており、削除された主キーのファイルを迅速に特定し、ファイルのビットマップに削除マーカーを迅速に追加するために使用されます。したがって、カラムストレージの主キーインデックスは小さな値を持つKVストレージです。KVストレージ構造も設計する必要があります。まず、KVストレージの使用シナリオの特徴を考慮する必要があります。
• KVは主キーとファイル位置で構成されます。ファイル位置情報は{ファイルID、インデックスの行番号}で、合計8バイト（4B + 4B）です。
• KVストレージ構造は永続化され、共有ストレージに保存される必要があります。
• リクエストには範囲ベースの読み取りがないREAD、INSERT、DELETEが含まれます。
• 高性能な読み取りとバッチ処理が必要です。

一般的なKVストレージ構造には主にHash、B+ Tree、Radix-Tree、およびLSMツリーが含まれます。範囲ベースの読み取りが不要な場合、Hash構造はパフォーマンスの観点で最適な選択肢です。しかし、現在では永続化されたHash製品は少なく、通常はメモリ内のキャッシュとして使用されます。永続化の要件と共有ストレージにおける順次書き込みの特性を考えると、PolarDB-Xはこのシナリオに適した独自のKVストレージを開発することを選択しました。Hash構造の高性能性とLSMツリーのI/O最適化を組み合わせて、PolarDB-XはHash-LSMツリーのKVストレージを設計しました。範囲ベースのソートがないLSMツリー構造は次の図に示されています。

範囲ベースのソートがないLSMツ

PolarDB-Xのカラムナエンジンに関する詳細解説

2.5 データ削除圧縮（Delete Compaction）

ORCファイル内のホールが大きい場合、無効なデータホールを削除し、ストレージスペースを回収するためにファイルが再書き込みされます。このプロセスは「delete compaction」と呼ばれます。まとめると、PolarDB-Xカラムナストレージエンジン内のすべてのファイル再編成操作は「compaction」という包括的な用語に含まれます。これらのタスクは非同期でバックグラウンドでスケジュールされ実行されます。目的に応じたさまざまなcompactionタスクがありますが、ここでは詳細には触れません。

カラムナインデックスの構築

前述のセクションでは、カラムナエンジンがどのようにデータを同期するかについて説明しました。IMCI（In-Memory Columnar Index）が初期データなしで作成された場合、binlogイベントを通じてデータのインポートを開始し、正常に動作できます。しかし、実際のシナリオでは、テーブルにはすでにデータが含まれているか、過去のbinlogファイルが期限切れになっていることがよくあります。このような状況では特別な処理が必要です。次の図は、IMCIの構築プロセスを示しています。

カラムナエンジンがbinlogイベントストリーム内でIMCI DDLイベントの作成を検出すると、テーブルのDML操作の同期を開始します。ここで生成されるデータは「増分データ」と呼ばれます。同時に、もう一つのスレッドがPolarDB-Xの行ストレージからすべての既存データをselectロジックを通じて取得します。このデータは「全データ」と呼ばれています。全データが取得されると、システムは全データと増分データをマージします。このマージされたデータセットがIMCI全体のデータセットを構成します。その後、エンジンは引き続きbinlogデータの同期を続けます。このプロセスには多くの実装の詳細が含まれており、後続の記事で構築プロセスを詳しく説明します。

2.6 高可用性

カラムナエンジンは高可用性のためにプライマリ-セカンダリアーキテクチャを使用しています。次の図に示すように、常駐しているセカンダリノードは起動状態にあります。プライマリノードが故障した場合、セカンダリノードは迅速にプライマリノードを選択して行から列へのデータ同期を行うことができます。これにより、低レイテンシでのカラムストレージが確保されます。ホットスタンバイモードはほとんどのアプリケーションシナリオに対応できます。カラムナエンジンはデータを一切保存せず、ステートレスであるため、ノード数は2つだけです。カラムストレージのメタデータはMetaDBに保存されており、これは高可用性を特徴とする3ノードのPaxosアーキテクチャです。カラムストレージのファイルデータは共有ストレージに保存されています。OSSも非常に高い可用性を持っています。カラムナエンジンの書き込みノードを追加することでいつでもプライマリノードの選定に参加できるため、通常は1つのセカンダリノードで十分です。

カラムナエンジンノードはリースメカニズムを使用してプライマリノードを選択します。MetaDBにはカラムナエンジンのすべてのノード情報を記録するシステムテーブルが存在します。一度に選択できるプライマリノードは1つだけで、残りのノードはセカンダリノードとなります。プライマリノードは継続的に更新され、頻繁なプライマリ-セカンダリ切り替え（HA）を回避できます。セカンダリノードも定期的にプライマリノードとして選択を試みます。プライマリノードが故障しリースが期限切れになると、セカンダリノードがリースを取得し新しいプライマリノードとなり、プライマリ-セカンダリの切り替えを完了します。セカンダリノードはホットスタンバイ状態であり、負荷がなくリソース利用率が低いことを考慮すると、PolarDB-Xのカラムナエンジンはプライマリノードが一部のバックグラウンドタスクをセカンダリノードにスケジュールして実行することをサポートしています。例えば、いくつかのcompactionタスクを実行することで、プライマリノードの負荷を軽減し、セカンダリノードのリソース利用率を向上させることができます。

3. 使用シナリオ

PolarDB-Xのカラムナインデックスは2023年11月にパブリッククラウドで徐々に展開されました。これまでに多くのユーザーが使用しており、一部は本番サービスに導入しています。多数の実際の使用シナリオを通じて、PolarDB-XはIMCIの一般的な使用方法をいくつか特定しました。これには、高性能クエリ、履歴データスナップショットの読み取り、およびカラムストアベースのアーカイブデータが含まれます。

3.1 高性能クエリ

PolarDB-Xは分散型HTAPデータベースです。複雑な分析APクエリの場合、それらを読み取り専用のカラムストアインスタンスにルーティングすることで、TPワークロードのトラフィックに影響を与えることなくクエリ性能が大幅に向上します。これにより、ユーザーのシナリオにより適切に対応できます。トラフィックの分散に関して、PolarDB-Xはインテリジェントルーティングと手動ルーティングをサポートしています。次の図に示す通りです。

パラメータを設定することで、トラフィックを自動的に読み取り専用カラムストアインスタンスにルーティングし、カラム指向データを読み取ることができます。また、異なるデータベース接続文字列に基づいて行指向またはカラム指向データにアクセスし、ベストプラクティスを実現できます。詳細については、[Row-column routing mechanism](https://www.alibabacloud.com/help/en/polardb/polardb-for-xscale/row-column-routing-mechanism target=_blank)をご覧ください。

3.2 履歴データスナップショットクエリ

前述のように、カラムナエンジンはグローバルbinlogを通じてデータを同期し、トランザクションに基づいてバッチでデータをコミットしてカラム指向データのバージョンを作成します。さらに、カラム指向データはファイルに追記または新規ファイルを作成して書き込まれますが、変更は行われません。したがって、各カラム指向データバージョンは一連のファイルとその長さメタデータを含んでいます。カラムストレージバージョンにはTSO値が含まれており、これはbinlogに記録されたトランザクションTSOから取得されます。各バージョンは読み取り可能なスナップショットバージョンです。次の図は例を示しています。

カラムストレージによって自動的にコミットされるスナップショットオフセットに加えて、PolarDB-Xはユーザーがコマンドpolardbx.columnar_flush()を呼び出すことを提供します。このコマンドはbinlogイベントに書き込まれ、ユーザーのTSO値を返します。このイベントがbinlog同期で識別されると、システムは強制的にカラムストレージバージョンをコミットします。これは必要なカラムストアスナップショットバージョンを作成することに相当します。TSO値