問題はメモリレイテンシだ、愚か者よ：Pivotの基数分割GROUP BY
CPU使用率が100%と報告されていても、そのサイクルの大部分はメモリを待つために費やされており、有用な命令を実行していない可能性があります。Pivotのブログ記事「問題はメモリレイテンシだ、愚か者よ」は、9900万行のClickBench hits データセットに対するシングルコアのGROUP BYクエリでこれを実証しています。単純なハッシュテーブル版ではCPUスロットの50.1%がメモリでストールし、実行中の操作は16.1%のみでしたが、基数分割版ではメモリストールが23.5%に減少し、DRAMトラフィックは4.5GBから1.5GBに削減され、実行時間は3.6秒から2.7秒に短縮されました。
なぜ100%CPUがほとんどアイドル状態になり得るのか
Linuxは、タスクがCPU時間を必要とするときにCPUをビジーとマークします。これは、コアが毎サイクル命令を発行していることを意味するものではありません。コアは100%の使用率を示しながら、実行スロットのほとんどがメモリアクセスでブロックされている可能性があります。
CPUとメモリのスケールギャップがその理由です。Pivotの記事では、最新のCPUは1ナノ秒あたり約4〜8命令を処理できるのに対し、DRAMアクセスには約50〜100ナノ秒かかると推定しています。つまり、CPUは1回のDRAMアクセスにかかる時間に約400〜800命令を実行できるということです。
| レベル | おおよそのレイテンシ | おおよそのサイズ | アクセスあたりの命令数 |
|---|---|---|---|
| L1キャッシュ | ~1 ns | ~64 KB | ~4-8 |
| L2キャッシュ | ~3-4 ns | ~1 MB | ~15-30 |
| L3キャッシュ | ~10-15 ns | 最大数百MB | ~50-100 |
| DRAM | ~50-100 ns | GB | ~400-800 |
CPUキャッシュはこのギャップを隠すために存在しますが、実際のデータセットに比べると小さいものです。予測可能なパフォーマンスを望むデータベースは、CPUが繰り返されるコールドDRAMアクセスを吸収することに頼るのではなく、ワーキングセットをコアの近くに保つ必要があります。
単純なGROUP BY：1つのハッシュテーブル、数百万のコールドミス
Pivotは、キャッシュ局所性の低さのコストを示すために、エンジンを単純なハッシュテーブル集計に絞り込みました。クエリはClickBenchの hits データセット（9900万行、約1700万の一意な UserID 値）に対する SELECT count(*), UserID FROM hits GROUP BY UserID でした。
単純な実装では、単一の成長するハッシュテーブルにキーごとに1エントリを挿入または更新します：
fn consume(
&mut self,
batch: RecordBatch,
_sender: &mut dyn Sender<RecordBatch>,
) -> unary::Result<()> {
let group_keys = batch.column(self.key_column).as_primitive::<Int64Type>();
for &key in group_keys.values() {
*self.counts.entry(key).or_insert(0) += 1;
}
}
数百万の一意なグループがあるため、ほぼすべてのハッシュテーブルアクセスはDRAMにアクセスするコールドミスになります。CPUはビジーに見えるかもしれませんが、ほとんど待機しています。
測定は、AMD EPYC 9124 Genoa、16コア、128 GB DDR5を搭載したCherryServersのベアメタルサーバーで実行されました。単純なGROUP BYは多くのコアで実行できなかったため、プロセスは単一コアに固定されました。最初の実行は3.9秒かかり、2回目の実行はデータがすでにページキャッシュにありディスクの関与がない状態で3.6秒かかりました。
perf stat は問題を直接示しました：
- 50.1%
backend_bound_memory - 16.1%
retiring - 8,364,109,137
ex_no_retire.load_not_complete - 11,431,618,219
ex_ret_ops
別のカウンター ls_dmnd_fills_from_sys.dram_io_near は76,190,837回のDRAMフィルを記録しました。キャッシュラインあたり64バイトで、これはクエリ中にDRAMから約4.5GBがプルされたことになります（プリフェッチなしで）。
基数分割：より多くの命令、より少ないDRAMアクセス
基数分割は、集計を2つのフェーズに分割して、ワーキングハッシュテーブルをCPUキャッシュに収まるほど小さくします。
フェーズ1では、Pivotは各キーをハッシュし、ハッシュの上位12ビットを使用して行を4,096個のパーティションのいずれかにルーティングします。パーティションは SlabVec であり、すでにページインされているメモリ上のベクターのような構造です。フェーズ2では、Pivotは一度に1つのパーティションを処理し、そのパーティション用の小さなハッシュテーブルを構築して集計し、結果を出力します。
このアプローチはより多くの総作業を行います：すべての行がハッシュされルーティングされ、その後集計中に再度ハッシュされます。このトレードオフは意図的です。ハッシュテーブルが小さいほどL1、L2、またはL3キャッシュに収まる可能性が高く、ルックアップがDRAMではなくキャッシュにヒットします。Pivotの記事は、コールドDRAMアクセスをCPU命令に変換することは通常良いトレードオフであると主張しています。
同じシングルコアでの結果：
- 最初の基数分割実行：3.3秒
- 2回目の基数分割実行：2.7秒
backend_bound_memory：23.5%retiring：32.2%ex_ret_ops：19,350,459,182（単純版の11,431,618,219から増加）- DRAMフィル：25,688,280（64バイト/フィルで約1.5GB）
基数版はより多くの操作を実行しましたが、メモリでストールする時間は大幅に短縮されました。メモリストールは8,364,109,137 CPUスロットから3,790,955,223に減少し、DRAMトラフィックは約4.5GBから約1.5GBに減少しました。
Pivotのチューニング済み実装と並列結果
Pivot自身の実装はデモ版よりもさらに進んでいます。シングルコアでは、同じクエリで1,848.353ミリ秒、14,917,958回のDRAMフィル（約954MBのDRAMトラフィック）を報告しています。
16コアでは、Pivotはクエリに171.773ミリ秒を報告しています。記事では、キャッシュ利用だけがDRAMレイテンシを隠す唯一の方法ではないと述べており、プリフェッチとメモリスループットを最大化するアルゴリズムについては、JOINプロービングに関するフォローアップで取り上げるとしています。
Hacker Newsのコメント投稿者が議論した内容
Hacker Newsの投稿は254ポイントと92コメントを獲得しました。議論は、キャッシュ局所性のデモンストレーションへの賞賛と、この技術や製品が新しいかどうかへの懐疑に分かれました。
あるコメント投稿者は、本番システムでメカニカルシンパシーを無視することの広範なコストを説明しました：
私は仕事で別のチームと一緒に働いていますが、そこでは大量のメッセージパッシング、深くネストされたクラス階層でのC++仮想メソッド、大きなDOM、市販のC++ STLコンテナを使用しています... STM32MP1上で、これはインオーダーのCortex-A7とわずかなキャッシュしかありません。一方、私のチームでは、インラインで割り当てるカスタムC++ STLコンテナ、SAXスタイルの処理ライブラリ、2000年代のビデオゲームのようなインデックス+世代を使用するリンクを持つオブジェクトプールを書きました... 1メガバイト未満のRAMのSTM32H5上で。メカニカルシンパシーは、私がデモを見せる人々にとって失われた芸術のように感じられます... そして私は最初のチームに、ベンチマーク数値で、私が彼らとの間で桁違いのボトルネックにならないことをデモしなければなりませんでした。
別のコメント投稿者は、CPU使用率の罠の直接的な例を示しました：
私は一緒に働いたチームと非常に長い議論をしたことを覚えています。彼らはCPUがすでに100%だったのでサービスがこれ以上速くリクエストを処理できないとほとんど確信していました。結局、サービスのメモリアクセスパターンを整理することで、1秒あたりのリクエスト数を3倍にしました...
他のコメント投稿者は新規性に疑問を呈しました。ある人は書きました：
えっと、これはただの基数分割集計じゃないの？階層的（固定2レベル）集計は古いよ。ここで新しいことは何？Pivot自体の縮図だと思う。DuckDBとClickHouseの両方が存在するのに、なぜこのプロジェクトが存在するのか理解できない。
別の人はこのアプローチをクラスタ化ハッシュマップと表現しました：
提示された解決策は、クラスタ化ハッシュマップまたは「局所性感応」と呼べるものだと思います。それでも桁違いに優れているわけではありません。
この記事は基数分割を発明したと主張しているわけではありません。その貢献は、データベースクエリがメモリストールによってどれだけ失うかを測定したデモンストレーションと、Pivotが自社エンジンでキャッシュ認識集計をどのように適用しているかを見せることです。コメントスレッドは、そのデモンストレーションが新しいデータベースプロジェクトを正当化するのに十分かどうかについてのより広い意見の相違を反映しています。
最後のコメントは、クリーンなコードと高速なコードの間のトレードオフを次のように表現しました：
クリーンなコードは美しい、便利な嘘が私たちを楽しませるように。キャッシュ認識コードは醜い、真実が傷つくように。道徳は最初から正直であることを示唆している、キャッシュ局所性を目指すことに早熟はない。
実用的な教訓は製品の議論よりも狭いです：100%のCPUはCPUが飽和している証拠ではありません。データ集約型ワークロードでは、メモリストールとDRAMトラフィックがより良い説明であることが多く、データをCPUキャッシュに収まるように分割することで、命令数が増えても実行時間を短縮できます。
Sources
関連
- Dispatch
- Dispatch
- Dispatch
- Dispatch
- Dispatch