📃

Snowflakeの論文「The Snowflake Elastic Data Warehouse」を読んでみた_Part1

2024/04/24に公開

Snowflake

tech

はじめに

この記事は、最近読んだSnowflakeの論文「The Snowflake Elastic Data Warehouse」の内容を備忘的に残したものです。
※ Part2も近いうちに公開予定

論文は以下にて公開されていますので、誰でも読むことができます。

この論文を読んだ動機としては、「Snowflakeってなんで早いの？」とか「他のDWHやDBとどう違って何が優れているの？」という問いに対して、いわゆる表面的な回答ではなく、きちんとサービスの裏側の構造も理解したうえで回答できるようになりたい、と思うようになったためです。

かなり雑記に近い形となってしまいましたが、Snowflakeの内部アーキテクチャについて少しだけ深掘りしてみたい方や、上記の論文の内容について日本語で触れてみたい方の一助になれれば幸いです。また、私もまだまだ勉強中の身ですので、誤読している内容などがありましたらコメントにてご指摘ください。

今回は、まずPart1ということで、「1. INTRODUCTION」～「3. ARCHITECTURE」の内容を私なりにまとめてみます。

注意事項

この論文は2016年に寄稿されたものです。情報が古い可能性がありますので、ご注意ください。
当時SnowflakeはAWSでの稼働のみをサポートしていたので、Snowflakeの稼働環境はAWSを前提とした書き方になっています。

1. INTRODUCTION

Snowflakeが登場した背景について述べられている章です。
内部アーキテクチャに触れている章ではないので、軽くサマリしておきます。

クラウドの到来

ユーザーがクラウドの利点を享受するには、ソフトウェアがクラウドというリソースプール上で拡張できないといけない。
- クラウドの共有インフラは、規模の経済の拡大、高いスケーラビリティと可用性、予測不可能な需要に適応するような、従量課金制のコストモデルになっているため。
- 従来の固定的なリソースで動くDWHソリューションだと、拡張性が前提になっているクラウドの考え方にマッチしない。

データの変化

以前はDWH内のデータのほとんどが、トランザクションデータ、ERPデータ、CRMデータなど、組織内のデータソースから来ているデータだった。そのため、データの構造、量などが事前にある程度予測可能であった。
クラウド時代においては、アプリケーションログ、Webアプリケーションデータ、モバイルデバイス、ソーシャルメディア、IoT系のセンサーデータなど、外部ソースからのデータの割合が急増している。これらはスキーマレスな半構造化データとして届くことが多い。

ビッグデータプラットフォーム

SparkやHadoopなどのビッグデータプラットフォームに目を向ける人もいたが、これらを展開していくためには多大なエンジニアリング工数が必要になる。

Snowflakeの開発へ

上記のような状況を受けて、全く新しいクラウドネイティブなDWHシステム「The Snowflake Elastic Data Warehouse」を構築することにした。
- SnowflakeはHadoopやPostgreSQLなどをベースにしておらず、処理エンジンとその他ほとんどの部分はゼロから開発された。
Snowflakeの特徴は以下（各特徴の詳細は元論文を参照）
- 純粋なSaaS体験
- リレーショナル
- 半構造化
- 柔軟性
- 高可用性
- 耐久性
- コスト効率
- セキュア

※この辺りの特徴の裏付けとなるアーキテクチャなどについて、この論文で書かれています。

2. STORAGE VERSUS COMPUTE

シェアードナッシングについて

2016年当時、シェアードナッシングのアーキテクチャが高性能なDWHの主流アーキテクチャになっていた。シェアードナッシングは、プロセッサノードが各々のローカルディスクを持つ構成。テーブルデータはノード間で水平にパーティショニングされ、各ノードは自身のローカルディスク上のレコードにのみ責任を持つ。

このアーキテクチャはパフォーマンス向上に寄与した一方で、コンピュートとストレージが密に結びついていることにより、以下のような特定のシナリオで問題が発生しうる。

複数の異なるワークロードに対して使うケース
- 各ワークロードで求められるスペックが異なるので、平均利用率が低いことには目をつむって、大きめのノードを確保しなければいけないケースが出てくる。
  ※例えば、バルクロード（高いI/O帯域幅、軽めの計算）に理想的なシステム構成は、複雑なクエリ（低いI/O帯域幅、重めの計算）には適していない。
ノードメンバーの変更
- ノード単位で障害が発生したり、ユーザーによってサイズ変更が行われると、大量のデータを再シャッフルする必要がある。（問題のノードからデータを移動させて他のノードに分散させるイメージ）
- しかも、同じノードでデータの再シャッフルとクエリ処理の両方を担当するので、再シャッフル時にはクエリパフォーマンスにも影響が出てしまう。
アップグレード
- システムのダウンタイムなしに、次々とノードがアップグレードされるようなオンラインアップグレードの実装が非常に困難。

クラウド時代における状況

シェアードナッシングには上述のような課題があったが、クラウド時代は以下のような状況がある。

Amazon EC2のようなIaaS環境では、様々なタイプ、サイズのノードが用意されており、データ（処理内容）に合わせて適切なタイプを選択できる。
ノード単位の障害とそれによるノードメンバーの変更なども、クラウド環境では例外ではなく、当たり前に起こることである。
オンラインアップグレードが可能になることで、ソフトウェアの開発サイクルを劇的に短縮できる。
柔軟なスケーリングができれば、ユーザーはリソース消費をその時々のニーズに合わせられる。

Snowflakeではストレージとコンピュートを分離

以上のようなことが理由で、Snowflakeではストレージとコンピュートを分離しており、この新しいアーキテクチャを、マルチクラスタ共有データアーキテクチャ
（multi-cluster, shared-data architecture）と呼んでいる。以下ざっくりと特徴を列挙。

コンピューティングは、Snowflakeの独自のシェアードナッシングエンジンを通じて提供される。
ストレージはAmazon S3を使って提供される。
※原理的にはAzure Blob Storage、Google Cloud Storageでも十分に対応可能。
コンピュートとストレージ間のネットワークトラフィックを削減するために、各コンピュートノードはローカルディスクにテーブルデータの一部をキャッシュする仕組みを採用。
ローカルディスクはあくまでも一時データとキャッシュのみに使われる。（SnowflakeはSSDを使用）
キャッシュが使われることで、ネットワーク経由でストレージにアクセスする際の待機時間を短縮できるので、クエリパフォーマンスを向上させるのに役立つ。
※シェアードナッシングのパフォーマンスの高さは認めつつ、それと同等か（キャッシュがウォームなケースであれば）それ以上のパフォーマンスが出るように工夫している。

3. ARCHITECTURE

alt text
元論文「The Snowflake Elastic Data Warehouse」より引用

Snowflakeは3つのアーキテクチャ層に分かれており、それぞれのサービス層はRESTfulインタフェースを通じて通信されている。各サービス群は独立してスケール可能。

データストレージ
- Amazon S3を使用してテーブルデータとクエリ結果を保存する。
仮想ウェアハウス
- システムの「筋肉」にあたる。
- 仮想マシンの柔軟性のある（elasticな）クラスタ内で、クエリ実行を処理する。
クラウドサービス
- システムの「頭脳」にあたる。
- メタデータを管理するサービスの集合体。

3.1 Data Storage

HDFSや、それと同様の独自ストレージサービスを開発するのではなく、S3をストレージとして採用した。（開発者目線として）背景は以下の通り。

S3はパフォーマンスのばらつきがあったものの、使い勝手の良さ、高可用性、高耐久性については他の追随を許さなかった。
そのため、独自のストレージサービスを開発するよりも、仮想ウェアハウスのローカルキャッシュや、データスキューを回復する技術の方にエネルギーを費やすことにした。

また、S3の特性として以下が挙げられる。

ローカルディスクに比べれば、当然アクセスレイテンシが高くなる。
比較的シンプルなHTTP(S)ベースの PUT / GET / DELETE インタフェースを持っている。これが最も重要。
- ファイルはフルで新しく書き込まれるか、丸々上書きされるしかできない。ファイル内にデータを追加したりすることはできない。

以上の特性を踏まえて、Snowflakeは以下のように S3 のストレージを使用している。

テーブルデータは大きな不変（immutable）ファイルに分割される。
- これが従来のDBにおけるブロックやページに相当する。
- 各ファイル内で各属性や列の値がグループ化され、列指向（PAX / hybrid columnar）で圧縮される。
- 各ファイルにはヘッダがあり、ファイル内の各列のオフセットなどが含まれている。
- S3はファイルの一部に対するGETリクエストができるので、ファイルヘッダと取得したい列のみをダウンロードすることができる。

また、Snowflakeはテーブルデータ以外でも S3 を使用する。

一時データ
- （大規模な結合などで）ノードのローカルディスク容量が尽きたときにクエリオペレータによって生成される一時データ。
- S3にスピルしながら処理することで、Out of MemoryやOut of Diskのエラーが発生することなく、任意のサイズのクエリを実行できる。
大規模なクエリ結果
- S3にクエリ結果を保存することで、従来のDBにあったサーバーサイドのカーソルが不要になり、クエリ処理が簡素化される。
メタデータ
- どのS3ファイルによってどのテーブルが構成されているかといったカタログ情報や、統計、ロック、トランザクションログなど。
- これらはクラウドサービス層の一部として、トランザクショナルなキーバリューストアに保存されている。

3.2 Virtual Warehouses

仮想ウェアハウスはEC2インスタンスのクラスタで構成される。

各クラスタは「仮想ウェアハウス（VW）」という形で抽象化される。
VWを構成する個々のEC2インスタンスはワーカーノードと呼ばれる。Snowflakeのユーザーがこのワーカーノードと直接やり取りすることは無い。
- ユーザーはVWを構成するワーカーノードがどれなのか、何台なのかを知らないし、気にする必要もない。
VWはTシャツサイズ（XS、S、M、Lなど）として抽象化することで、基盤となるクラウドプラットフォームに依存することなく、Snowflakeのサービスを展開できるようにした。

3.2.1 Elasticity and Isolation

以下のようなVWの柔軟性により、ユーザーは需要に合わせてコンピュートリソースを動的に使うことができる。これはSnowflakeのアーキテクチャの最大の利点であり、差別化要因の1つである。

VWは純粋なコンピュートリソースと見なせる。自由に作成、削除、サイズ変更が可能。（VWを作成したり削除したりしても、データベースの状態には影響しない）
クエリがないときはVWを落としておくことができる。
VWを柔軟に扱えることで、同じ費用でも優れたパフォーマンスを達成できることが多い。
- 例えば、4ノードで15時間かかるデータロードが、32ノードで2時間に短縮できるかもしれず、しかもトータルコストはほとんど変わらない、ということがありうる。

また、個々のクエリは1つのVWで実行され、ワーカーノードはVW間で共有されない。

新しいクエリが送信されると、それぞれのVWの各ワーカーノードは新しいワーカープロセスを生成。
ワーカープロセスはそのクエリの間だけ生存。
クエリが失敗した場合、ワーカープロセスは最初から再試行する（テーブルファイルが不変なので、部分的な再試行ができない）

3.2.2 Local Caching and File Stealing

VWの各ワーカーノードは、ローカルディスク上にテーブルデータのキャッシュを保持している。キャッシュは過去にアクセスされたテーブルファイル（つまりS3オブジェクトの集まり）。
※もう少し正確に言うと、そのファイルのヘッダーと個々のカラム。

キャッシュの特徴は以下の通り。

キャッシュはワーカーノードが稼働している間だけ存在する。
- 同時に稼働している他のワーカープロセスや後続のワーカープロセスでもキャッシュは共有されるので、クエリ間でキャッシュが共有される動きになる。
- キャッシュは単純なLRU（least-recently-used）置換ポリシーに従う。つまり、直近で使用されていないキャッシュを最初に破棄する仕組み。
キャッシュのヒット率を改善するために、クエリオプティマイザ側で工夫されている。
- クエリオプティマイザは、テーブルファイル名に対する一貫したハッシュを使用して、ワーカーノードのキャッシュに割り当てる。
- そのため、同じテーブルファイルにアクセスする後続のクエリや、同時実行中のクエリが、同じワーカーノード上によって実行される形になる。
- （ノードの故障やVWのサイズ変更によって）ワーカーノードのセットが変更されても、各ノードが持つデータはすぐにシャッフルされず、LRUで少しずつキャッシュコンテンツを置き換えていくという、「遅延型」のキャッシュになっている。

クラウドDWHではキャッシュ以外に、データスキューへの対応が特に重要である。
ネットワーク等様々な要因により、一部のノードの実行速度が他のノードよりも大幅に遅くなってしまうことがあるが、その問題に対してSnowflakeは以下のように対処できるようにしている。

ノード（ノードA）は自分の担当するファイル処理が終了すると、他のノード（ノードB）に対して、追加のファイルを要求する。（ノードAでもっとファイル処理できるよ！ということ。）
ノードBの入力ファイルセットに多くのファイルが残っていると分かった場合、そのファイルの所有権がノードAに譲渡され、ノードAはS3からそのファイルを直接ダウンロードし、処理の肩代わりをする。
こうしたファイルスティールの仕組みによって、処理が遅くなったノードにさらに負荷がかかって状況が悪化する、ということを防いでいる。

（補足）このファイルスティールの仕組みは、以下のmediumブログの中ほどにある絵が分かりやすかったです。こちらの方も今回の論文についてまとめています。

3.2.3 Execution Engine

これまで述べてきたスケーラビリティは重要だが、もちろん単一ノードごとの処理効率も重要である。例えば、1000ノードで高速にクエリを実行できたとしても、他のシステムではそのクエリを10ノードで同じ時間で実行できます、ということなら意味ないよね、という話。
Snowflakeは、DBaaS市場の中でも最高のパフォーマンスをユーザーに提供するため、独自のSQLエンジンを実装している。以下の3つがキーワード。

カラム型
- カラム型のストレージとSQL実行の組み合わせは、分析（OLAP）ワークロードにとって、行指向のそれよりも優れていると考えられている。
- カラム型の場合、CPUキャッシュとSIMD命令をより効果的に使用し、圧縮効率も良い。
ベクトル型
- Snowflakeは、たとえばMapReduceのように、中間結果を実体化することはしない。
- データはパイプライン方式で、数千行のバッチをカラム型で処理。これにより、I/Oを節約し、キャッシュ効率を大幅に向上させている。
プッシュベース
- Snowflakeでは、親オペレータが子オペレータからデータをプルするのではなく、子オペレータが親オペレータにデータを積極的にプッシュする仕組みを採用している。

（補足）ベクトル型、プッシュベースの話についてはまだ完全に理解できているわけではないですが、なんとなくのイメージを掴むために以下のブログも参考にしました。

3.3 Cloud Services

クラウドサービス層の各サービス（アクセス制御、クエリオプティマイザ、トランザクションマネージャなど）は、存続時間が長く、多くのユーザーによって共有される前提で開発されている。
また、各サービスは内部的に複製されていて、個々のノードが故障してもデータの損失が発生しないようにしており、高可用性とスケーラビリティを担保している。

3.3.1 Query Management and Optimization

まず、ユーザーによる全てのクエリは、クラウドサービス層を経由する。クエリのライフサイクルの初期段階として、このクラウドサービス層にて構文解析、オブジェクト解決、アクセス制御、プラン最適化などが処理される。
Snowflakeのクエリオプティマイザの特徴は以下の通り。

典型的なCascadesスタイルのアプローチに従っており、トップダウンでコストベースの最適化を行う。
最適化に使用されるすべての統計情報は、クエリ実行の間、自動的に保持される。
Snowflakeはインデックスを使用しないため、プラン検索空間は他の（インデックスを使う）システムよりも小さくて済む。結合時のデータ配布の形式など、多くの決定を先送りにすることで、さらにプラン空間を削減する。このようにして、オプティマイザが誤った決定を行う数を減らし、クエリパフォーマンスの安定性を高めている。

オプティマイザが完了すると、実行計画の結果がクエリ処理を担うすべてのワーカーノードに配布される。
また、クエリが実行されている間、クラウドサービス層はクエリの状態を継続的に監視しており、全てのクエリ情報と統計情報は監査、パフォーマンス分析のために保存される。

3.3.2 Concurrency Control

同時実行制御もすべてクラウドサービス層で処理される。
Snowflakeはスナップショット分離（SI）によってACIDトランザクションを実装している。つまりトランザクションによる全てのデータ読み取りは、トランザクションが開始した時点のスナップショットを見ることになる、ということ。
SIは多版型同時実行制御（MVCC）の上に実装されている。

MVCCはSnowflakeが使用するテーブルファイル（S3保存）が不変であるという事実を考えると自然な選択。
テーブルに対する書き込み操作（INSERT、UPDATE、DELETE、MERGE）について、以前のテーブルのバージョンに対してファイル単位で追加もしくは削除することで、新しいバージョンのテーブルを作成することで実現する。
こうしたファイルの追加と削除は、キーバリューストアのメタデータで追跡され、特定のテーブルのバージョンに属するファイルの集まりを、非常に効率的に計算することができる。

SI のためだけでなく、Snowflakeはこれらのスナップショットを使用して、タイムトラベルや効率的なクローニングを実現している。

（補足）トランザクション分離レベルの話は、Snowflake公式ドキュメントにもこっそり記載があります。

3.3.3 Pruning

クエリ処理において、クエリで必要なデータのみにアクセスするというのは最も重要な側面の1つである。
歴史的には、B+ツリーなどのインデックスを使用して、アクセス先のデータを絞り込んできた。インデックスはトランザクション処理では非常に効果的な一方で、以下のような考慮事項があり、Snowflakeのようなシステムには向いていない。

B+ツリーはランダムアクセスが行われるワークロードに向いているものであり、S3のように中規模のファイル単位でのストレージや圧縮ファイルのデータフォーマットを使う場合には適していない。
インデックスを保持することにより、データ量とデータのロード時間を大幅に増加させてしまう。
ユーザーは明示的にインデックスを作成し、維持しなければならない。これはSnowflakeが目指す、純粋なSaaS体験を提供するというアプローチに大きく反する。

Snowflakeはインデックスを使用せず、プルーニングという仕組みを使用して検索対象データを絞り込むことにした。

システムは、与えられたデータチャンク（レコードセット、ファイル、ブロックなど）のデータ分布情報、特にチャンク内の最小値と最大値を保持する。Snowflakeはすべての個々のファイルについて、こうしたプルーニングのメタデータを保持している。
このメタデータを使用して、どのチャンクが不要であるかを判断できるようになる。
このメタデータは、従来のインデックスとは異なり、実際のデータよりも非常にデータ量が小さいため、ストレージのオーバーヘッドを小さく抑えられる。
こうしたプルーニングの仕組みは、「ユーザーからのインプットが必要ない」「拡張性が高く勝手にスケールしてくれる」「メンテナンスが容易」という特徴を備えており、Snowflakeの設計原則にもうまくマッチしている。

また、Snowflakeは静的なプルーニングだけでなく、動的なプルーニングも行う。
例えばハッシュJOIN処理の一部として、Snowflakeはビルド側の結合キーの分布に関する統計情報を収集する。この情報がプローブ側にプッシュされ、プローブ側でファイル全体をフィルタリングするために、また場合によってはファイルをスキップするために使用される。

感想

Snowflakeの内部アーキテクチャや背景の設計思想にも踏み込んで書かれているので、論文を読む前に比べるとSnowflakeというサービスへの解像度が格段に上がりました。個人的に面白かったのは以下のような点です。

テーブルファイルがS3上のimmutableなファイルであると考えると、マイクロパーティションという仕組みがいかに理にかなっているかが分かる。
ファイルスティールの仕組みによってデータスキューの問題に対応しているというのが面白い。もちろんパーティション単位でデータの偏りがあると処理の並列実行が難しくはなりそうだけど。
MVCCの上に実装されるスナップショット分離について、immutableなテーブルファイルを使っていることが背景にあるという点、またそのスナップショットを使ってタイムトラベルやクローニングの機能が実装されているという点も、裏側の動作原理を知れたみたいで面白かった。
そしてなんといっても、Snowflakeはとことんユーザー目線で開発されているということが分かった！

論文自体は少し古いですが、とことんユーザー体験にこだわる設計思想や、3層アーキテクチャの動作原理などは今読んでも廃れない内容かなと思います。興味がわきましたら、ぜひ原文を読んでみてください。

後半の内容もすでに読んではいるので、また近いうちに記事化しようと思います！