> [!abstract] 概要 > 過去数十年で、格納・分析されるデータ量は指数関数的に増加してきた。ウェブ解析・金融・eコマースをはじめとする各産業の企業はこのデータに依存し始めており、製品改善・性能評価・ビジネス上の重要な意思決定に活用している。しかし、データ量がインターネット規模に達するにつれ、企業はコスト効率よくスケーラブルな方法で過去・新規のデータを管理し、多数の同時クエリと実時間レイテンシ（ユースケース次第で 1 秒未満）という要求のもとで分析する必要に迫られている。本論文は、ペタバイト規模のデータセットに対して高インジェスト率で高性能な分析を実現するよう設計された人気オープンソース OLAP データベース ClickHouse の概要を示す。ストレージ層は、従来の LSM ツリーに基づくデータ形式と、バックグラウンドで歴史データを継続的に変換する新技術（集計・アーカイブ等）を組み合わせる。クエリは便利な SQL 方言で記述され、オプションのコードコンパイルを伴う最先端のベクトル化クエリ実行エンジンで処理される。ClickHouse はクエリで無関係なデータの評価を避けるためのプルーニング技法を積極的に利用する。他のデータ管理システムはテーブル関数・テーブルエンジン・データベースエンジンの各レベルで統合できる。実世界のベンチマークは ClickHouse が市場で最も高速な分析データベースの一つであることを示している。 ## 論文情報 - **タイトル**: ClickHouse - Lightning Fast Analytics for Everyone - **著者**: [[Robert Schulze]]、Tom Schreiber、Ilya Yatsishin、Ryadh Dahimene、[[Alexey Milovidov]]（[[ClickHouse Inc.]]） - **媒体**: Proceedings of the VLDB Endowment（PVLDB）Vol. 17, No. 12, pp. 3731–3744 - **発表年**: 2024 - **DOI**: 10.14778/3685800.3685802 - **原本**: `.raw/papers/p3731-schulze.pdf`（14 ページ） ## 概要 ClickHouse は 2009 年にウェブ規模のログデータ向けフィルタ・集計演算器として始まり、2016 年にオープンソース化されたカラム型 OLAP データベースである。現代の分析データ管理における 5 つの課題（巨大データセットと高インジェスト率・多数同時クエリと低レイテンシ要求・多様なデータストアとフォーマット・便利なクエリ言語と性能観測・業界品質の堅牢性と柔軟なデプロイ）への解法を統合したシステムアーキテクチャを持つ。 ## 問題設定 - **入力**: 数兆行・数百カラムのテーブルに対するインタラクティブな SQL 分析クエリ、継続的な高レート INSERT - **前提**: 主にアペンドオンリーのワークロード（更新・削除は稀） - **要件**: ペタバイト規模のデータ・インジェスト中の同時クエリ・1 秒未満レイテンシ・多様な外部システムとの統合 ## アーキテクチャ **Figure 2: The high-level architecture of the ClickHouse database engine** ![[_attachments/p3731-schulze/fig02-architecture.png]] (Figure 2. ClickHouse エンジンの高レベルアーキテクチャ。クエリ処理層・ストレージ層・インテグレーション層の 3 層に分割され、アクセス層がプロトコル管理を担う。スレッド管理・キャッシング・ロールベースアクセス制御・バックアップ・継続的モニタリングが横断コンポーネントとして存在する。Source: Figure 2 of [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]].) ClickHouse エンジンは 3 つの主要層に分割される。 - **クエリ処理層**: SQL パース → 論理プラン → 物理プランのパイプライン。ベクトル化実行（MonetDB/X100 方式）と LLVM コード生成を組み合わせる - **ストレージ層**: MergeTree* ファミリーのテーブルエンジン群（詳細は §ストレージ層） - **インテグレーション層**: 50 以上の外部システムとの接続機構 デプロイモードは 4 種類: オンプレミス（シングルサーバまたはマルチノードクラスタ）・クラウド（ClickHouse Cloud、DBaaS）・スタンドアロン（コマンドライン分析ツール）・インプロセス（chDB、DuckDB 方式の埋め込み）。 ## ストレージ層（MergeTree*） ### オンディスクフォーマット 各テーブルは**不変のパート（part）**の集合として管理される。INSERT のたびに新しいパートが生成され、バックグラウンドのマージジョブが複数の小パートをより大きなパートに統合する（デフォルト上限 150 GB）。 - パートはカラムごとの別ファイルとして保存（10 MB 未満の小パートは 1 ファイルに統合） - 行は**グラニュール**（8192 行）単位に論理分割される——プルーニングの最小単位 - グラニュール複数をまとめた**ブロック**単位で圧縮して I/O を削減（デフォルト LZ4） - デルタ符号化 → LZ4/Zstd 圧縮 → AES 暗号化のようなコーデックチェーンが可能 - `LowCardinality(T)`: 低カーディナリティカラムを整数 ID に置換する辞書符号化 - `Nullable(T)`: ビットマップで NULL を管理 **従来 LSM との違い**: ClickHouse の MergeTree* はすべてのパートを**階層なしで等価**に扱う。このためトゥームストーン（墓石）による更新・削除が使えず、マージ時変換（§マージ戦略）で対処する。また、従来 LSM が持つ WAL（先行書き込みログ）を使わず、INSERT を直接ディスクに書き込む。 ### データプルーニング（3 機構） **第 1 機構: スパース主キーインデックス** - 主キーカラムで各パート内のグラニュールをソート - 各グラニュールの先頭行の主キー値 → グラニュール ID へのマッピングをメモリに保持（例: 8.1 百万行で 1000 エントリのみ） - WHERE 条件の主キープレフィックスに対し二分探索で対象グラニュールを絞り込む（Figure 4 参照） - 単調性トレイト・逆像計算など関数の特性を活かした最適化も実装 **Figure 4: Evaluating filters with a primary key index** `EventTime` カラムの主キーインデックスにより、範囲述語は順次スキャンでなく二分探索で対象グラニュールを特定する。 **第 2 機構: プロジェクション（テーブル射影）** - 同じ行を別の主キーでソートした代替バージョンを維持 - クエリオプティマイザが I/O コスト見積もりに基づきメインテーブルかプロジェクションかを選択 - パートが存在しない場合はメインテーブルにフォールバック **第 3 機構: スキッピングインデックス** 複数グラニュールのブロック単位で小さなメタデータを保持し、無関係なスキャンを回避する。3 種類: 1. **ミンマックスインデックス**: インデックスブロックの最小値・最大値を保存。局所クラスタデータに有効 2. **セットインデックス**: 設定数の一意値を保存。局所カーディナリティが小さいデータに有効 3. **ブルームフィルタインデックス**: 行・トークン・n-gram ベース。テキスト検索に対応するが範囲や否定述語には不可 ### マージ戦略（バックグラウンドデータ変換） マージ時変換はペタバイト規模の高インジェストと歴史データ削減の両立を可能にする。INSERT 性能を損なわないが、「未変換の値がテーブルに残りうる」ため、一貫性が必要な場合は `SELECT FINAL` で補う。 **置換マージ（ReplacingMergeTree）**: 同一主キーを持つ行のうち、コンテナパートの生成タイムスタンプが最新のものだけを残す。update-heavy ユースケース向けの実質的な更新機構。 **集計マージ（AggregatingMergeTree）**: 同一主キーの行を部分集計状態（partial aggregation state）に折り畳む。マテリアライズドビューと組み合わせて使い、新パートが挿入されるたびに変換クエリを差分適用する（全件更新はしない）。 **TTL マージ**: 行ごとのタイムスタンプ式に基づき、1 パートを丸ごと以下のいずれかのアクションで処理: ①別ボリューム（低速・低コスト S3 等）へ移動 ②別コーデックで再圧縮 ③削除 ④ロールアップ（グルーピングキーで集計） ### 更新・削除 - **ミューテーション**: テーブルの全パートをインプレースで書き換える（非アトミック）。削除ミューテーションは全カラムを書き換えるため高コスト - **軽量削除（Lightweight Delete）**: 内部ビットマップカラムに削除フラグを立てるだけ。実際の物理削除は次回の通常マージ時。カラム数が多い場合はミューテーションより大幅に高速だが SELECT が遅くなる ### 冪等インサート（Idempotent Insert） 接続タイムアウト後の再送問題への解法。サーバが最後の N 件（デフォルト 100 件）のパートハッシュを保持し、既知ハッシュの再インサートを無視する。非レプリケーション環境ではローカル保存、レプリケーション環境では Keeper に保存。 ### データレプリケーション Figure 6 参照。Raft コンセンサスアルゴリズム（ClickHouse Keeper が実装、ZooKeeper の代替）を使いレプリケーションログを管理。INSERT・マージ・ミューテーション・DDL 操作をログに記録し、他ノードが非同期にリプレイする。テーブルは**結果整合性**（eventually consistent）。 3 つの高速化最適化: ①新規ノードはログ先頭からでなく最終書き込みノードの状態をコピー ②マージはローカルで再実行するか他ノードから結果パートを取得（設定で選択） ③独立したログエントリを並列リプレイ ### ACID 準拠 クエリ開始時に全パートのスナップショットを取り、並列 INSERT やマージの参加を防ぐ（スナップショット分離、MVCC の変形）。ただし同時書き込みが複数パートに及ぶ場合は厳密な ACID 準拠にならない。デフォルトで fsync を省略し（書き込みスループット優先）、電源断時の若干のデータ損失を許容。 ## クエリ処理層 ### 3 レベルの並列化 **Figure 7: Parallelization across SIMD units, cores and nodes** ![[_attachments/p3731-schulze/fig07-parallelization.png]] (Figure 7. ClickHouse は SIMD ユニット・CPU コア・クラスタノードの 3 レベルでクエリを並列化する。データ要素は SIMD 命令で同時処理、データチャンクは複数スレッドで並列処理、テーブルシャードは複数ノードで同時スキャンされる。Source: Figure 7 of [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]].) 1. **SIMD 並列化**: 手書き intrinsics または LLVM 自動ベクトル化。cpuid に基づいて SSE 4.2 / AVX2 / AVX-512 カーネルを実行時に選択 2. **マルチコア並列化**: MonetDB/X100 と同じベクトル化モデル（データチャンク単位の演算子間受け渡し）。物理プランをコアへの実行レーン（lane）に展開し、Repartition 交換演算子で負荷バランス調整 3. **マルチノード並列化**: Distributed テーブルエンジンがシャードを透過的に管理。イニシエータノードが可能な限り処理をリモートノードにプッシュダウン ### クエリ最適化 - AST レベル: 定数畳み込み・スカラー抽出（`sum(a*2)` → `2*sum(a)`）・共通部分式除去・OR → IN 変換 - 論理プラン: フィルタプッシュダウン・関数評価と並び替えステップの順序最適化 - 物理プラン: MergeTree* の主キーをオーダー BY カラムが覆う場合はソート演算子を除去、プレフィックス一致時はソート集計（ハッシュ集計より少メモリ）を選択 ### クエリコンパイル LLVM を使い隣接演算子を動的融合（例: `a*b+c+1` を 1 演算子に統合）。GROUP BY の複数集計関数・複数ソートキーのソートにも適用。同一式が設定回数以上実行されると初めてコンパイルを開始し、コンパイル済み演算子はキャッシュして再利用。 ### ハッシュテーブル最適化 グループ化カラムのデータ型・推定カーディナリティ等に基づき 30 以上のハッシュテーブル実装から最適を選択。主な最適化: 256 サブテーブルの 2 レベルレイアウト・文字列専用ハッシュテーブル・キーを直接バケットインデックスにするルックアップテーブル・ランタイム統計から予測サイズでハッシュテーブル生成。 ### 並列ハッシュジョイン パーティションドハッシュテーブルを使った非ブロッキング共有パーティションアルゴリズム（Blanas et al., 2011）。ビルドフェーズの複数レーンがハッシュ関数の剰余でパーティションを決定し Gather 交換演算子で同期。ラッチ競合を大幅に低減。 ### ワークロード分離 - **同時実行制御**: CPU コア数比に基づきクエリあたりのワーカースレッド数を動的調整 - **メモリ制限**: サーバ・ユーザ・クエリの各レベルでバイト単位追跡。超過時は外部アルゴリズムにフォールバック - **I/O スケジューリング**: FIFO / SFC 等のポリシーでワークロードクラスごとにローカル・リモートディスクアクセスを帯域制限 ## インテグレーション層 50 以上のインテグレーションテーブル関数とエンジンを提供（2024 年 3 月時点）。対象: ODBC・MySQL・PostgreSQL・SQLite・Kafka・RabbitMQ・Redis・S3/GCP/Azure・Iceberg・DeltaLake・Hudi など。接続方式: - **テーブル関数**: SELECT の FROM 句で一時的にリモートデータを読み書きする ad-hoc アクセス - **インテグレーションテーブルエンジン**: CREATE TABLE AS 構文でリモートデータソースを永続テーブルとして公開。パッシブ（クエリ転送）とアクティブ（リモート変更を定期プル）の 2 種類 - **インテグレーションデータベースエンジン**: リモートデータベースの全テーブルを ClickHouse にマッピング - **辞書（Dictionary）**: 任意のデータソースから周期的にプルしてキャッシュ。低レイテンシ結合に有効 - **データフォーマット**: 90 以上（CSV・JSON・Parquet・Avro・ORC・Arrow・Protobuf 等） - **互換インタフェース**: MySQL / PostgreSQL ワイヤプロトコル互換で既存 BI ツールから接続可能 ## 性能分析ツール - **サーバ・クエリメトリクス**: `system.*` テーブルから統一インタフェースで取得（アクティブパート数・キャッシュヒット率・ブロック読み取り数等） - **サンプリングプロファイラ**: サーバスレッドのコールスタックを収集し、フレームグラフ等の外部ツールにエクスポート - **OpenTelemetry 連携**: クエリ処理の全ステップにわたるトレーススパンを生成・収集・分析 - **EXPLAIN**: AST・論理/物理プラン・実行時挙動の詳細表示 ## 実験結果 ### ClickBench（非正規化テーブル） **Figure 10: Relative cold and hot runtimes of ClickBench** ![[_attachments/p3731-schulze/fig10-clickbench.png]] (Figure 10. ClickBench の相対コールド・ホット実行時間（対数スケール）。最速クエリを基準に相対値を算出し幾何平均で集計。ClickHouse は冷温ともに全本番データベース中最速を達成（研究システム Umbra はホット限定で上回る）。MySQL=2957/1011、PostgreSQL=762/329、Druid=35.96/15.44、Redshift=16.94/14.90、Pinot=12.33/4.82、Snowflake=8.39/5.23、Umbra=1.23/1.57、ClickHouse=2.57。Source: Figure 10 of [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]].) 100 百万行のページヒット統計テーブルに対する 43 クエリ。AWS EC2 c6a.4xlarge（16 vCPU、32 GB RAM）でシングルノード測定。主キーは指定するが圧縮チューニング・プロジェクション・スキッピングインデックスは未使用という軽いチューニングのみ。結果: **ClickHouse は本番グレード全データベース中で冷温ともに最速**。研究データベース Umbra はホットランタイムのみ上回る。 ### VersionsBench（バージョン間性能推移） 2018 年 3 月〜2024 年 3 月の 77 バージョンを対象に、ClickBench・MgBench 15 クエリ・Star Schema Benchmark・NYC Taxi Rides 4 クエリの計 4 ベンチマークを月次実行。VersionsBench の加重幾何平均は **6 年間で 1.72 倍改善**（2022 年 8 月のカラムバイカラムフィルタ評価技法が最大の跳躍）。LTS リリースは前 LTS と同等以上の性能を維持。 ### TPC-H（正規化テーブル） TPC-H scale factor 100 でのホットランタイム測定（AWS EC2 c6i.16xlarge、64 vCPU、128 GB RAM）。相関サブクエリ（Q2/Q4/Q13/Q17/Q20-22）と特定ジョインプラン最適化を要するクエリ（Q7-Q9/Q19）は除外。残り 11 クエリのうち 5 クエリが Snowflake（ウェアハウスサイズ L）より高速、6 クエリが Snowflake より低速。ジョイン再順序化・ジョイン述語プッシュダウンは未実装であり、2024 年実装予定とされている。 ## 新規性・強み - **LSM ツリーの再解釈**: 階層なし・全パート等価・ペイロード別マージ戦略（置換/集計/TTL）による継続的データ変換は、従来 LSM の汎用コンパクションと一線を画す - **3 層並列化の統合**: SIMD・コア・ノードを単一バイナリで透過的に扱える実装 - **強力なプルーニング機構の組み合わせ**: スパースインデックス・プロジェクション・スキッピングインデックスを状況に応じて使い分け - **50 以上の統合**: 論文時点で最多の組み込みデータ統合オプションと主張 - **性能インスペクションの標準化**: system テーブル統一インタフェース・サンプリングプロファイラ・OpenTelemetry 統合 ## 弱点・課題 - 結果整合性のみ（スナップショット分離）——厳密な ACID トランザクションは将来の予定 - 相関サブクエリ未対応（v24.6 時点） - ジョイン再順序化・ジョイン述語プッシュダウンが未成熟（TPC-H の一部クエリで Snowflake に劣後） - 更新・削除は設計上の弱点（アペンドオンリー向け）——軽量更新は 2024 ロードマップに記載 ## 関連研究との比較 | システム | 類似点 | 相違点 | |---------|-------|-------| | Druid / Pinot | 高インジェスト率リアルタイム OLAP・水平パート分割 | Druid/Pinot はパートが永続不変（マージなし）、専用ノード構成 | | Snowflake | マイクロパーティション（≒パート）・データプルーニング | ClickHouse は完全カラム型格納 vs Snowflake はハイブリッド PAX、分散アーキテクチャが異なる | | DuckDB | 埋め込みモード（chDB として対応）・OLAP 向け | DuckDB は DataBlocks（軽量圧縮・HTAP）、MVCC による直列化可能トランザクション | | Photon / Velox | ベクトル化実行エンジン | ClickHouse はエンジンのみでなくストレージ・統合層を持つ完全 DB | ## 強み / 弱点まとめ **Strengths**: ClickBench 最速・6 年で 1.72 倍の継続改善・単一バイナリの簡潔さ・50 以上の統合・強力な 3 機構プルーニング **Weaknesses**: トランザクションは限定的・ジョイン最適化が未成熟・更新コストが高い・OLTP ワークロードは苦手 ## 関連 - 概念: [[列指向OLAPデータベース]] / [[LSMツリー]] / [[LSMツリーコンパクション]] / [[並列データベース]] / [[時系列データベース]] / [[べき等性]] / [[結果整合性]] / [[データパーティショニング]] - エンティティ: [[ClickHouse]] / [[ClickHouse Inc.]] / [[Robert Schulze]] / [[Alexey Milovidov]] ## 出典 本ページの全主張は `.raw/papers/p3731-schulze.pdf` の以下の箇所に遡及済み: - 論文情報・キーナンバー: pp. 3731 PVLDB Reference Format / DOI 記載 - MergeTree* フラット構造: p. 3733 §3 "ClickHouse treats all parts as equal instead of arranging them in a hierarchy" - データプルーニング 3 機構: pp. 3734–3735 §3.2 - マージ戦略: pp. 3735–3736 §3.3 - 更新・削除: p. 3735 §3.4 - 冪等インサート: p. 3736 §3.5 - レプリケーション: p. 3736 §3.6 - 3 レベル並列化: pp. 3737–3739 §4.1–4.3 - ClickBench 結果 / VersionsBench: pp. 3741 §6.2 - TPC-H 結果: p. 3741 §6.2.2 Figure 12 - 1.72 倍改善: p. 3741 "The performance of VersionBench improved by 1.72 × over the past six years"