論文から垣間見るAmazon Redshiftの進化と深化 2022 #jawsug #bdjaws

データアナリティクス事業本部のコンサルティングチームの石川です。

本日は、2022年5月に発表された論文 「Amazon Redshift re-invented」を実際に読み、難しいところや弊社が実際に検証をした点を補足して解説します。普段はRedshiftの機能や使い方の解説が多く、あまり触れられることの少ないUnder the hoods 的なお話しようと思います。

本エントリはAWS Analytics Advent Calendar 2022の12/24（土）の記事です。

論文の詳細については、2022/12/19のBigData JAWS #22にて、登壇した資料をご覧ください。ブログの中では、紹介した機能についてのブログを紹介しています。

このブログをおすすめする人

オライリーの「データ指向アプリケーションデザイン」や「詳説データベース」とかを読むと、Redshiftの内部がどうなってるのか気になってソワソワしてしまう人。

何でこんな話をしようと思ったか

• 弊社クラスメソッド社内で、「Redshiftの面白そうな論文あるよ、みんなで読書会しない？」という呼びかけをきっかけに論文読書会することになり、愉快な仲間たちが集まった
• 案の定、論文読書会が盛り上がった、、、でも若者たちにもこの喜びを伝えたいという想い（重い？）
• クリスマスイブだから（言いたいだけです）

論文 Amazon Redshift re-invented

1. INTRODUCTION

Amazon Redshift開発の4つの重点ポイントは、以下のとおりです。

• 複雑化する分析クエリのパフォーマンス向上を実現するために、様々な性能対策。詳細については、後ほど、解説します
• より多くのデータ、より多くのユーザー数の処理に応えるために、ストレージとコンピューティングを分離する、、、いわゆる「ストレージとコンピューティングの分離」ってやつです
• 使い勝手の良さの追求することです。Redshiftの専門家でなくても、統計情報や機械学習を用いた自動チューニングを提供すること
• DynamoDB、Aurora、S3、SageMakerといった、様々なAWSサービスとRedshiftのシームレスな統合すること

補足：Redshiftの成り立ち

元々 ParAccel社が開発したコモディティハードウェアで動作するデータウェアハウスのソフトウェアをAWSがソースとライセンスを購入、AWS上のインフラに展開したのが始まりです。サービス開始時から10年間のSQLを書き換えることなく、現在でも動作する高い互換性を維持しています。一方、現在のアーキテクチャは、クラウドネイティブなデータウェアハウスに正常進化を遂げ、全く別物になっています。

以下、PostgreSQLからAmazon Redshiftの成り立ちです。

引用：RDBMS_Genealogy_V6

2. PERFORMANCE THAT MATTERS

システムアーキテクチャ、データ構成、クエリ処理フローの概要を説明します。また、Redshiftのハードウェアベースのクエリ高速化レイヤであるAQUAと、Redshiftの高度なクエリ書き換え機能についても触れています。

論文のこの章が全体の1/3くらいを占めており、難易度もここが山場と考えて良いです。

System Architecture

• Amazon Redshift：列指向の超並列処理（MPP）型のデータウェアハウスです。Redshiftクラスタは、1つのコーディネータであるリーダーノードと、複数のコンピュートノードで構成されている
• Redshift Managed Storage：S3上のRedshift Managed Storage（RMS）に保存され、コンピュートノードではローカルに取り付けられたSSDに圧縮された列指向のフォーマットでキャッシュされる
• Concurrency Scaling：より多くの処理能力を必要とする状況において、動的にスケールアウトし、何百もの同時実行クエリに対して一貫して高速なパフォーマンスを提供できる
• AQUA：FPGAを活用してパフォーマンスを向上させるクエリアクセラレーションレイヤーです
• Compilation-As-A-Service：Redshiftフリートで実行されるさまざまなクエリフラグメントに対して最適化された生成コードをキャッシュするマイクロサービスです
• Data Sharing：Redshiftクラスタ間で、読み取り目的のライブデータを安全かつ容易に共有することができる

Query Flow

• ①リーダーノードは、クエリを受信
• ②クエリを受信すると、Parser、Rewrite、Optimaizerを順に実行
• ③コストベースのオプティマイザが、最適なプランを選択
• ④実行計画立案後、クエリの実行を制御は、ワークロード管理（WLM）が担う
• ⑤カラムナデータは、ローカルに接続されたSSDからスキャンされるか、S3上のRMSから読み込まれます

Redshiftのコード生成

Redshiftは、大量のデータに対する複雑なクエリの高速実行に重点を置いた分析用データベースです。

• Redshiftはスキーマとクエリプランに対応するC++コードを生成する
• 生成されたC++コードはコンパイルされてコンピュートノードに転送される
• コンパイルされたファイルは segment と呼ばれる
• segment は step と呼ばれるオペレーターのパイプラインで構成される
• segment と step は物理クエリプラン (physical query plan) の一部である
• segment の最後の step だけがパイプラインを終了できる

Inline Expression Functions

基本的な操作にはインライン関数を利用して、処理の高速化をしている。

Compilation Service

クエリ実行に使用される最適化されたC++コードをオブジェクトファイルにコンパイルするサービス。

CPU-Friendly Encoding

カラムをディスクに保存する時の圧縮方式はLZOやZSTDなどの汎用圧縮アルゴリズムに加え数値や日付/時刻型に適したAZ64アルゴリズムで高い圧縮率と解凍速度を両立させた。

Adaptive Execution

実行エンジンは、実行統計に基づいて生成されたコードや実行時のプロパティを動的に変更し、パフォーマンスを高めるための実行時決定を行う。

• 大量データのJOINが発生すると
  • コンピュートノード間のデータ転送 => ネットワーク ボトルネック
  • メモリ不足のためにページアウトの発生 => I/O ボトルネック
  • ハッシュテーブルに存在しないキーを除外し、これらを抑制したい
• Bloom Filter(BF)を使い、JOIN不要な行(データ)を除外

AQUA for Amazon Redshift

Redshift Managed Storageのオフクラスターキャッシング層および複雑なスキャンと集計のプッシュダウンアクセラレータのマルチテナントサービス。

• クラスタ外部のReshiftのストレージとの中間に位置するキャッシュレイヤーとして機能する
• AQUAはReshiftクラスタのローカルSSDのホットデータをキャッシュする
• S3のようなリージョナルサービスからのデータ取得のレイテンシーを減らす
• コンピュートノードのキャッシュストレージにデータをロードする機会を減らす
• ネットワークボトルネックを意識させないように、AQUAはストレージではなく関数としてのインタフェースを提供する
• Nitro ASICによる暗号化処理のハードウェアアクセラレーション

Query Rewriting Framework

DSLベースの新しい Query Rewriting Framework（QRF）を備えており、これは２つの目的に対応しています。

• クエリの書き換えや最適化
  • 結合、接合、集約の実行順序を最適化する書き換えルールの導入に利用
  • サブクエリをブルートフォースで繰り返し実行するよりも、大規模な結合の方が実行モデルのメリットが大きいので、クエリのデコレーション時にも利用
• マテリアライズド・ビューを使ったクエリの書き換え
  • QRFによるクエリ書き換えは、問い合わせ表現（ASTまたは代数）の一部をマッチングして抽出するパターンマッチャーと、パターンマッチャーによって抽出された部分を用いて新しい問い合わせ表現を作成するジェネレータのペアとして簡単に表現できる。概念がシンプルなため、数日で非相関の書き換えを開発できた
  • さらに、Redshiftが入れ子や半構造化データ処理に関わる書き換えを導入することを可能にし、マテリアライズドビューの適用範囲を広げた

3. SCALING STORAGE

Redshiftの高性能トランザクションストレージ層であるRMS（Redshift Managed Storage）について、紹介します。

Redshift Managed Storage（RMS）

RMSは、ユーザーデータとトランザクションメタデータの両方を管理し、AWS Nitro Systemの上に構築されています。

• RMSは、ベアメタルと区別できない高帯域幅のネットワーキングとパフォーマンスを備えている
• Redshiftは、ワークロードのパターンと、自動的なきめ細かいデータ退避やインテリジェントなデータプリフェッチなどの技術を活用し、ローカルSSDのパフォーマンスを実現しながら、S3にストレージを自動的にスケーリングする
• トランザクションは、RMSによってS3に同期的にコミット、複数のクラスターがライブでトランザクション的に一貫性のあるデータにアクセスできる
• 状態は1つのクラスターによって所有および管理されますが、並行リーダーとライターはRMS上でコンピューティングスケーリングを提供します
• オンデマンドでスピンアップされる並行クラスターは、スナップショットアイソレーションに依存し、クエリ要求に対応するためにデータのオンデマンドフェッチを優先します

Decoupling Metadata from Data

データからメタデータを分離すると、ElasticResizeとクロスインスタンスリストアが可能になる。

• どちらの機能も、メタデータを1つのクラスター構成から別のクラスター構成にシャッフルするため、メタデータをデータから分離すると、効率的な実装につながる可能性がある
• Elastic Resizeを使用すると、ノードを追加してパフォーマンスを向上できる
• クロスインスタンスリストアを使用すると、ユーザーは、あるインスタンスタイプのクラスターから取得したスナップショットを、異なるインスタンスタイプまたは異なる数のノードのクラスターに復元できる
• ElasticResizeとクロスインスタンスリストアは、Elastic Resizeテクノロジーを活用して、数分で移行を提供します。

Expand Beyond Local Capacity

S3を使用してクラスターのストレージ容量を拡張し、ローカルメモリとSSDをキャッシュとして利用することで、スケーラビリティを強化している。

• セクションでは2つのコンポーネント：階層型ストレージキャッシュとダイナミックディスクキャッシュ
• RMSは、階層型ストレージキャッシュを使用して、クラスターの再構成（Elastic Resize、クラスターの復元、ハードウェア障害など）後にローカルSSDにデータをキャッシュします。アクセスされる可能性が最も高いデータブロックでローカルディスクをキャッシュする
• Redshiftは階層型ストレージキャッシュの上にダイナミックディスクキャッシュを利用して、メモリ内の最もホットなブロックを維持する
• さらに、ディスクキャッシュは、新しいデータブロックやクエリ固有の一時ブロックなど、クエリによって作成された他のブロックを保持する

Incremental Commits

S3をプライマリストレージとして使用するには、データのフットプリントとコストを削減するために増分コミットが必要となる

• RMSは変更されたデータだけを検知し、ログを反映
• 差分更新方式（旧型）:redirect-on-write protocol
  • 変更のあったブロックをまるごと新規に書き込み、ポインターを付け替える
• 差分更新方式（新型）:log-based commit protocol
  • このログはLog-structured file systemのことAurora なども採用
  • インメモリ構造と永続構造で処理を分ける
  • 永続構造のスーパーブロックでは、単にログを記録するだけ
  • ランダムI/OではなくシーケンシャルI/Oのため、コミット・パフォーマンス40％向上
• メタデータはグローバルに分散、耐久性・可用性のため複数AZ/リージョンにまたぎ、メタデータはAWSグローバルインフラで共有・リレーできる
• ログ構造メタデータが特に有効なのは、並列スケーリング、データ共有でトランザクションの一貫したデータが必要
  • 新しいログをローカルスーパーブロックに適用→ソースデータと同期

Concurrency Control

Redshiftはマルチバージョン同時実行制御（MVCC）を実装している。

• Readerはブロックしないし、ブロックもされない
• Writerは他のWriterにブロックされる場合がある
• トランザクション開始時のスナップショットを参照可能
• Redshiftは serializable 分離レベルを強制しているのでロストアップデートやread/writeのスキューが発生しない
• RedshiftのドキュメントではMVCCという単語では紹介されていない
• 以前はトランザクションの依存性管理をグラフベースの仕組みで行っていた
  • この方法は同時に実行されている個々のトランザクションの状態を保持しておく必要があった
• スナップショット分離の certifier (証明者) として Serial Safety Net (SSN) ベースのデザインを採用した。
  • 前回コミット時からのサマリー情報を保持するだけで良くメモリ効率が向上
  • SSNは Serializable Snapshot Isolation (SSI) のようなアルゴリズムと比べても性能がよい。
  • SSNベースのアルゴリズムに最適化と拡張を加えた。以前利用していた certifier と互換性を持つようにした。
  • オリジナルのSSNはコミット時にabort検出していたのを処理中にも検出するようにした。
  • 古いデザインと比べてリソースの消費量がかなり減った。特にメモリはワークロードにもよるが最大で8GB下がった。

4. SCALING COMPUTE

Redshiftのコンピュート層について紹介します。

Cluster Size Scaling

Elastic Resizeにより、お客様は現在のコンピュートニーズに応じて、クラスターからコンピュートノードを迅速に追加または削除することができる。

• サイズ変更後、移動したデータ・パーティションはオンデマンドのリクエストとホットデータを優先して、バックグラウンドでS3からローカルストレージに読み込む
• データパーティションの再割り当てのため、Elastic Resize後のノードあたりのデータパーティション数は、リサイズされていないRedshiftクラスタのものと異なる

Concurrency Scaling

同時実行スケーリングは、単一のRedshiftクラスターが提供できるよりも多くの同時実行性を必要とする場合に、Redshiftを動的にスケールアウトできる。

• 1つのクラスタではクエリを同時実行できないときにクラスタの追加が行われる
  • クラスタ内ノードではなく、既存とは別のクラスタが追加される
• キューに溜まっているクエリは追加されたクラスタにルーティングされる
  • ユーザ側は考慮不要。気にせず既存クラスタのエンドポイント宛にクエリを投げてOK
• 新たに追加されたクラスタはRMSからデータを取得する

Compute Isolation

Redshift Data Sharing を用いたコンピュートの分離する。

• RA3インスタンスで利用可能
• RA3インスタンスではストレージが分離されている
• コンシューマクラスタ側が必要なコンピューティングリソースを使用する
• コンシューマ側で書き込みもできる
• オブジェクト 「datashare」に共有したいスキーマ、表などを追加する

5. AUTOMATED TUNING AND OPERATIONS

クラスターのメンテナンス、パッチ適用、監視、サイズ変更、バックアップ、暗号化など、従来のデータウェアハウジングに加えて、メンテナンスタスクとパフォーマンスチューニングの自動化について紹介します。

ここでは、一般的な機能紹介なので簡単に解説します。

Automatic Table Optimizations

テーブルの分散キーやソートキーなど、ワークロードのパフォーマンス最適化を自動化する。

• Automatic Table Optimization(ATO)がキーの選出・適用を自動化
  • ワークロードの解析・推薦の流れ
  • 最適化されたクエリープラン、カーディナリティー、predicate selectivitiesといったメタデータを定期的に収集し、推奨値を生成
  • 期待される効果も予測し、効果の高いもののみを推薦

Automatic Table Optimization(ATO)が順次自動適用され、35時間後にはパフォーマンスが改善。

Automatic Workload Management

Redshiftの自動ワークロード管理（AutoWLM）は、アドミッションコントロール、スケジューリング、およびリソース割り当てを担う。

Query Predictor Framework

RedshiftのQuery Predictor Framework による AutoWLMは、クエリのメモリ消費量と実行時間を予測するための機械学習モデルを採用。クエリのメモリ消費量と実行時間を予測するのにXGBOOSTによる推論を実施している。

Materialized Views

マテリアライズド・ビュー（MV）は、予測可能で繰り返されるクエリを高速化するために特に有効。

補足：現在は、AutoMV（自動マテリアライズド・ビュー）が提供されており、自動的にマテリアライズド・ビューが内部的に作成され、自動的にクエリ実行時に適用されることでクエリ実行のレスポンスやスループットが向上する。

Smart Warmpools, Gray Failure Detection and Auto-Remediation

日常的に起こるハードウェア障害やサービス障害を発生させないための工夫も実装されている。

Serverless Compute Experience

Redshift Serverlessは、コンピューティングリソースの自動プロビジョニング、サイジング、スケーリングをアルゴリズムに依存する。autonomics（自動化）に取り組みを拡張して、Redshift Serverless を導入した。

6. USING THE BEST TOOL FOR THE JOB

AWSとRedshiftが、それぞれのユースケースに最適なサービスセットを顧客が簡単に利用し、Redshiftのクラス最高の分析機能とシームレスに統合する方法について説明します。

ここでは、一般的な機能紹介なので簡単に解説します。

Data in Open File Formats in Amazon S3

Redshift Spectrumを介して、S3のオープンファイル形式のデータにアクセスする機能です。

Redshift ML with Amazon SageMaker

Redshift MLは、SQLを使用して機械学習モデルをトレーニングし、予測（推論）を簡単に実行する。Redshift MLは、SageMakerを利用している。

OLTP Sources with Federated Query and Glue Elastic Views

Federated Queryは、RedshiftからOLTPサービスのライブデータに直接クエリを実行したり、GlueElasticViewsを使用してRedshiftへのデータのシームレスなコピーと同期の両方を容易に実現する。

Redshift’s SUPER Schemaless Processing

RedshiftのSUPER型は、スキーマレスな半構造化データの効率的かつ柔軟に保存する機能を提供する。

Redshift with Lambda

Redshiftは、AWS Lambdaコードに基づくユーザー定義関数（UDF）の作成をサポートしている。

7. CONCLUSION

• マネージドストレージ、スケーリング、データ共有、AQUAなどのイノベーションにより、パフォーマンスとスケーラビリティを成長させてきた
• 同時に、使いやすさも進化してきた
  • 自動化されたワークロード管理、自動化されたテーブル最適化、マテリアライズドビューを使用した自動クエリ書き換え
  • 優れたクエリパフォーマンスを実現
• さらに、Redshiftは、追加のデータ（半構造化、空間）および複数のAWSサービスとのインタフェースが可能になった
• Amazon Redshiftは、
  • 分化された実行コア、
  • 数十PBsのデータと数千人の同時ユーザーに対応する拡張性
  • 使いやすいMLベースの自動化
  • 幅広いAWSエコシステムと緊密に統合された、クラウドDWHのベストソリューション

最後に

恐らく、Redshiftを使いたい人は大きく2つに分類されると考えます。とにかく専門的な知識なしにデータウェアハウス（DWH）であるRedshiftを使いたいという方と、機能の詳細やアーキテクチャをより理解して緻密なチューニングやクラスタ構成をしたい方です。

現在のRedshiftは、概ね自動的にチューニングされるように設計されているため専門的な知識なしにデータウェアハウス（DWH）が利用できるように深化しています。更にRedshift Serverlessを利用するとクラスタのサイジングやスケーリングなども意識する必要がないように進化しています。しかし、データ分析基盤の大規模化やセキュリティ要件などによって、ワークロードやクラスタ構成を分ける必要が生じたとき、パフォーマンスやコスト効率などの考慮が求められます。そのようなときこそ、機能の詳細やアーキテクチャをより理解することが役立つのではないかと私は考えています。

今まで個人的にいだいていた、内部はこうなっているであろうという妄想に対しての、答え合わせと、新しい発見が多くありました。また、今回の論文を読むにあたり、「Vectorized Scans」、「Volcano execution model」、「メモリストール削減のプリフェッチ」など、DBの一般的に採用されている方式や高速化技法を改めて学ぶきっかけになりました。論文を書いてくださったAWSの皆さん、一緒に論文を読んでワイワイしてくれた仲間たちに感謝です。読んでくださった皆さんにとっても良いクリスマスでありますように！

論文や公開資料

Amazon Redshift: Ten years of continuous reinvention

2022/05/18に、Amazon Redshift re-inventedという論文が掲載されました。

Amazon Redshift re-invented（SIGMOD/PODS 2022）

2022/06にIppokratis Pandissさんが、Amazon Redshift re-inventedというタイトルでSIGMOD/PODS 2022に登壇しています。

（補足）Amazon Redshift の 進化の歴史とこれから/redshift-evolution-2021

re:Invent2021の前（2021/05/03）の時点となりますが、AWSの大薗さんのわかりやすくまとまっていますのでご覧ください。

これらの論文に対してデータベースの一般的アーキテクチャや高速化技法の解説と、最新のre:Invent2022の 10 years of innovation in integration, data sharing & moreの内容も加味して、ご紹介させていただきます。