なぜ ClickHouse はこれほど速いのか?
他にも多くの要因が、データベースの性能に寄与しています。そのデータ指向性 以外にも、ClickHouse が特に他の列指向データベースと比較して高速である理由を詳しく説明します。
アーキテクチャの観点から見ると、データベースは(少なくとも)ストレージ層とクエリ処理層で構成されています。ストレージ層は、テーブルデータの保存、読み込み、管理を担当し、クエリ処理層はユーザーのクエリを実行します。他のデータベースと比較して、ClickHouse は両方の層で非常に高速な挿入と SELECT クエリを実現するための革新を提供しています。
ストレージ層:同時挿入が互いに隔離されている
ClickHouse では、各テーブルは複数の「テーブルパーツ」で構成されています。ユーザーがテーブルにデータを挿入すると(INSERT 文)、毎回 パート が作成されます。クエリは常に、クエリが開始されたときに存在するすべてのテーブルパーツに対して実行されます。
大量のパーツが蓄積されるのを避けるために、ClickHouse はバックグラウンドで マージ 操作を実行し、常に複数の小さなパーツを1つの大きなパーツに統合します。
このアプローチにはいくつかの利点があります:すべてのデータ処理を バックグラウンドのパートマージにオフロード することで、データの書き込みを軽量かつ非常に効率的に保ちます。個々の挿入は「ローカル」であるため、テーブル全体のデータ構造を更新する必要がありません。その結果、複数の同時挿入は相互の同期や既存のテーブルデータとの同期を必要とせず、したがって挿入はディスクの I/O の速度にほぼ等しくなります。
VLDB 論文の全体的なパフォーマンス最適化セクションを参照してください。
🤿 これについての詳細は、オンディスクフォーマット セクションにあります。
ストレージ層:同時挿入と選択が隔離される
挿入は SELECT クエリから完全に隔離され、挿入されたデータパーツのマージはバックグラウンドで行われ、同時クエリには影響しません。
🤿 これについての詳細は、ストレージ層 セクションにあります。
ストレージ層:マージ時計算
他のデータベースとは異なり、ClickHouse はすべての追加データ変換を マージ バックグラウンドプロセス中に実行することで、データの書き込みを軽量かつ効率的に保ちます。これには以下が含まれます:
-
置換マージ:入力パーツの行について最も新しいバージョンのみを保持し、他の全ての行バージョンを破棄します。置換マージは、マージ時のクリーンアップ操作として考えることができます。
-
集約マージ:入力パーツの中間集約状態を新しい集約状態に結合します。一見すると理解が難しいようですが、実際にはインクリメンタル集約を実装しているだけです。
-
TTL (有効期限) マージ:特定の時間に基づくルールに基づいて、行を圧縮、移動、または削除します。
これらの変換のポイントは、ユーザーのクエリが実行されるときからマージ時間に作業(計算)をシフトすることです。これは2つの理由で重要です:
一方では、ユーザーのクエリは「変換された」データ、例えば前もって集約されたデータを活用できる場合、数百倍以上速くなることがあります。
他方では、マージの実行時間の大部分は入力パーツの読み込みと出力パーツの保存に消費されます。マージ中にデータを変換するための追加の手間は、通常、マージの実行時間にあまり影響を与えません。これらすべての魔法は完全に透明であり、クエリの結果(パフォーマンスを除く)には影響しません。
🤿 これについての詳細は、マージ時データ変換 セクションにあります。
ストレージ層:データプルーニング
実際には、多くのクエリが繰り返し行われます。つまり、定期的に(例えば異なるパラメータ値を使用して)ほとんど変更されずに実行されます。同じまたは類似のクエリを繰り返し実行することで、インデックスを追加したり、データを再配置して頻繁にクエリがアクセスしやすくすることができます。このアプローチは「データプルーニング」とも呼ばれ、ClickHouse にはそのための3つの技術があります:
-
主キーインデックス:テーブルデータのソート順を定義します。適切に選択された主キーにより、上記のクエリの WHERE 句のようなフィルターを、フルカラムスキャンの代わりに高速なバイナリ検索を使用して評価できます。より技術的には、スキャンの実行時間はデータサイズに対して線形から対数に変わります。
-
テーブルプロジェクション:テーブルの内部の代替バージョンで、同じデータを格納していますが、異なる主キーでソートされています。プロジェクションは、複数の頻繁なフィルター条件がある場合に便利です。
-
スキッピングインデックス:列に最小値や最大値のような追加のデータ統計を埋め込むインデックスです。スキッピングインデックスは主キーおよびテーブルプロジェクションとは直交し、列内のデータ分布に応じてフィルターの評価を大幅に加速できます。
これら3つの技術はすべて、フルカラムリードの間にできるだけ多くの行をスキップすることを目的としています。なぜなら、データを読み込む最も速い方法は、それを全く読まないことだからです。
🤿 これについての詳細は、データプルーニング セクションにあります。
ストレージ層:データ圧縮
さらに、ClickHouse のストレージ層は、異なるコーデックを使用して生のテーブルデータを追加(およびオプションで)圧縮します。
列ストアは、同じタイプとデータ分布の値が一緒に配置されるため、このような圧縮に特に適しています。
ユーザーは指定することで、カラムがさまざまな一般的な圧縮アルゴリズム(ZSTD など)や、浮動小数点値のための GORILLA や FPC、整数値のための DELTA や GCD、あるいはAESのような暗号化コーデックを使った圧縮を行うことができます。
データ圧縮はデータベーステーブルのストレージサイズを削減するだけでなく、多くの場合、クエリパフォーマンスも改善します。なぜなら、ローカルディスクやネットワークI/Oはしばしば低スループットに制約されるからです。
🤿 これについての詳細は、オンディスクフォーマット セクションにあります。
最先端のクエリ処理層
最後に、ClickHouse はベクトル化されたクエリ処理層を使用しており、可能な限りクエリ実行を並列化して、最大の速度と効率でリソースを活用します。
「ベクトル化」とは、クエリプランの演算子が、単一の行の代わりにバッチで中間結果行を渡すことを意味します。これにより、CPU キャッシュの利用が向上し、演算子は SIMD 命令を適用して複数の値を一度に処理できるようになります。実際、多くの演算子は複数のバージョンで提供されており、これは各 SIMD 命令セットの世代に1つずつ対応しています。ClickHouse は、実行されるハードウェアの能力に基づいて、最も新しく最も速いバージョンを自動的に選択します。
現代のシステムには数十の CPU コアがあります。すべてのコアを活用するために、ClickHouse はクエリ プランを複数のレーンに展開します。通常、各コアごとに1レーンが割り当てられます。各レーンは、テーブルデータの非重複の範囲を処理します。このようにして、データベースのパフォーマンスは使用可能なコア数と共に「垂直的に」スケールします。
単一のノードがテーブルデータを保存するには小さすぎる場合、クラスターを形成するためにさらにノードを追加できます。テーブルは「シャード」分割され、ノード全体に分散できます。ClickHouse はテーブルデータを保存するすべてのノードでクエリを実行し、ノードの数に応じて「水平的に」スケールします。
🤿 これについての詳細は、クエリ処理層 セクションにあります。
入念な細部への配慮
「ClickHouse は異常なシステムです - 皆さんは 20 バージョンのハッシュテーブルを持っています。皆さんは、ほとんどのシステムが1つのハッシュテーブルを持っているところで、このような素晴らしいものを持っています。 ... ClickHouse は、これらの専門的なコンポーネントを持っているため、この素晴らしいパフォーマンスを発揮します」 Andy Pavlo, CMUのデータベース教授
ClickHouse を 際立たせる のは、低レベルの最適化に対する入念な配慮です。機能するデータベースを構築するのは一つのことですが、さまざまなクエリタイプ、データ構造、分布、インデックス設定にわたってスピードを提供するように設計するのは、「異常なシステム」のアートが輝くところです。
ハッシュテーブル。 ハッシュテーブルを例に考えてみましょう。ハッシュテーブルは、結合や集約に使用される中心的なデータ構造です。プログラマーとしては、これらの設計決定に考慮する必要があります:
- 選択するハッシュ関数、
- 衝突解決: オープンアドレッシング か チェイニング、
- メモリレイアウト:キーと値のための1つの配列か、それとも別々の配列か?
- フィルファクター:いつどのようにサイズを変更するか?サイズ変更中に値を移動する方法は?
- 削除:ハッシュテーブルはエントリの強制削除を許可すべきか?
サードパーティのライブラリが提供する標準的なハッシュテーブルは機能的には動作しますが、高速ではありません。優れたパフォーマンスには入念なベンチマーキングと実験が必要です。
ClickHouse の ハッシュテーブル実装 は、クエリとデータの特性に基づいて、30以上のプリコンパイル済みハッシュテーブルバリアントの1つを選択します 。
アルゴリズム。 アルゴリズムについても同様です。例えば、ソートでは次のことを考慮するかもしれません:
- ソートするもの:数値、タプル、文字列、または構造体?
- データは RAM に格納されていますか?
- ソートは安定であるべきですか?
- データ全体がソートされる必要がありますか、それとも部分的なソートで十分ですか?
データ特性に依存するアルゴリズムは、一般的な対応物よりもさらに優れた性能を発揮します。データ特性が事前に知られていない場合、システムはさまざまな実装を試みて、実行時に最良のものを選択できます。例として、ClickHouse における LZ4 デコンプレッションの実装に関する 記事を参照してください。
🤿 これについての詳細は、全体的なパフォーマンス最適化 セクションにあります。
VLDB 2024 論文
2024年8月、私たちは初めての研究論文が VLDB で受理され、公開されました。VLDB は非常に大規模なデータベースに関する国際会議で、データ管理の分野において最も権威のある会議の一つと広く見なされています。何百件もの投稿の中で、VLDB の受理率は一般に約20%です。
論文の PDF や、ClickHouse の最も興味深いアーキテクチャ的およびシステム設計要素を簡潔に説明した ウェブ版 を読むことができます。
私たちの CTO であり ClickHouse の創設者である Alexey Milovidov が論文を発表しました(スライド こちら)、その後 Q&A が行われました(すぐに時間切れになりました!)。録画されたプレゼンテーションは、こちらで視聴できます: