それはメモリレイテンシの問題だ、愚か者

それはメモリレイテンシの問題だ、愚か者

データベースのCPU使用率が100%に達したとき、それは実際に何を意味するのでしょうか？ CPUは単純化のために線形にコードを実行すると考えがちですが、実際にはCPUは信じられないほど複雑な獣であり、一度に多くの命令を実行できる可能性もあれば、全く実行できない場合もあります（コンソールが100%を示しているにもかかわらず）。CPUは多くのことができるため、100%のCPUが別の100%のCPUよりもはるかに少ない処理しか行っていない可能性があります。「アイドル」状態のCPUとは、タスク（Linuxタスク）がCPU時間を必要としない状態を指します。これは、CPU自体が完全に飽和していることを意味するわけではありません。では、CPUが100%に見えても、なぜ完全に利用されないのでしょうか？

その答えは通常、メモリです。

メモリへのアクセスは、CPUの内部操作に比べて桁違いに遅いです。その程度を把握するために、最新のCPUは1ナノ秒あたり約4〜8命令を処理できる可能性があります。RAMへのメモリアクセスには、約50〜100ナノ秒かかることがあります。計算を簡単にするために、これは最新のCPUがRAMからの1回のメモリアクセスごとに約400〜800命令を実行できることを意味します。

CPU

CPUコア 4–8 命令/ns

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

GBs ・ ~400–800 命令/アクセス

これを踏まえ、CPUはこの遅延を回避するようにゼロから設計されています。最も明白な対処法はCPUキャッシュです。CPUキャッシュは、RAMよりもCPUに近い場所にメモリを保持し、文字通りCPUチップに焼き付けられています。最も近いキャッシュ（L1キャッシュ）は、メモリ操作あたり約1nsかかります。これはRAMよりも50〜100倍高速です！もちろん、「問題」はCPUキャッシュがかなり小さいことです。最新CPUのL1キャッシュはおそらく約64KBですが、より遠いキャッシュはハイエンドプロセッサで数百MBまでです。優れたデータベースは、キャッシュを最大限に活用するために、データを小さな「チャンク」で操作しようとします。パフォーマンスエンジニアリングでは、キャッシュ利用率が最重要事項の1つとしてよく挙げられます。

キャッシュ利用率をより深く理解するために、GROUP BY集計を見てみましょう。GROUP BYでは、データセットを取得し、特定の列（または複数）でグループ化し、集計（例: カウント、別の列の合計）を実行します。「ナイーブ」な方法は、グループキーをキーとするHashTableを作成し、それがどんどん大きくなることです。各行について、そのキーが存在するかどうかを確認します。存在する場合、対応する集計に移動して結果を更新します。簡単ですよね？問題は、数百万の一意のグループがある場合、キャッシュを全く利用できていないことです！ほぼすべてのHashTableアクセスは、RAMにアクセスする「コールド」ヒットになります。これは、CPUが100%利用されているように見えても、実際にはコールドメモリへのアクセスを常に待っていることを意味します。

これを実証するために、最先端のPivotエンジンを使用してそれを「破壊」します！複雑なロジックをすべて削除し、単純さに置き換えます。

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() {
        // Group Keyが存在しない場合は0に設定します
        // その後、グループに1を加算します。これにより、count(*) GROUP BY key_columnが得られます
        *self.counts.entry(key).or_insert(0) += 1;
    }
}

次に、ClickBenchが提供する「hits」データセット（9900万行）に対して、単純なクエリ SELECT count(*), UserID FROM hits GROUP BY UserID を実行します。このクエリは、UserID ごとのカウントを返します。つまり、UserID ごとにHashMapにエントリが作成されます。ネタバレですが、一意のUserIDは約1700万です。
パフォーマンスチェックは、CherryServersの友人たちから提供されたベアメタルサーバー（AMD EPYC 9124 Genoa、16コア、128 GB DDR5）で行います。セキュリティ上の理由（例: DRAMコントローラーから私たちに渡されているメモリ量を確認したい）で、それらが公開されていない一般的なAWS/GCPマシンは使用できません。このナイーブなグループバイは多くのコアで実行できないため、単一コアに限定します。

実行するには：

cat > config.yaml <<'EOF'
server:
  bind: 127.0.0.1:5440
workers: 1
datastores:
  default:
    kind: pivotlake
    location: ./data
    default: true
users:
  pivot:
    auth:
      method: trust
EOF
taskset -c 3 pivot server --config config.yaml &
psql -h 127.0.0.1 -p 5440 -U pivot -c '\timing on' -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

これは...驚異的な3.9秒かかります。良いのでしょうか？悪いのでしょうか？この世のすべては相対的なものだ、と彼らは言います。サーバーを再起動せずにクエリを再度実行すると、3.6秒かかります。2回目の実行がより興味深いものです。ディスクは関与しておらず、すべてがページキャッシュにすでに収まっています。

taskset -c を使用したことに気づくでしょう。これはプロセスを指定されたCPUにピン留めします。これにより、そのCPUで perf stat を実行して内部で何が起こっているかを確認できます。2つのメトリックグループを測定します。メモリによってCPUスロットが停止している割合（その間何も行われていない）、および実際にマイクロオペレーションをリタイアしているCPUスロットの割合です。

sudo perf stat -C 3 -M backend_bound_memory,retiring -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

そして、この結果が得られます。

Performance counter stats for 'CPU(s) 3':

        8364109137      ex_no_retire.load_not_complete   #     50.1 %  backend_bound_memory
       38233214040      de_no_dispatch_per_slot.backend_stalls
        8977647849      ex_no_retire.not_complete
       11861387798      ls_not_halted_cyc
       11431618219      ex_ret_ops                       #     16.1 %  retiring
       11858248045      ls_not_halted_cyc

       4.030148989 seconds time elapsed

これは、CPUがメモリの待機のために50.1%の時間何もできなかったことを示しています！そして、CPUが実際にオペレーションをリタイアしていた（つまり、実行していた）のはわずか16.1%の時間でした。

CPUメモリロードのうち、DRAMから（キャッシュからではなく）どれだけ来ているかを示す別の興味深い統計値を取得します。

sudo perf stat -C 3   -e ls_dmnd_fills_from_sys.dram_io_near   -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

そして、その結果は次のとおりです。

 Performance counter stats for 'CPU(s) 3':

          76190837      ls_dmnd_fills_from_sys.dram_io_near

       3.996301634 seconds time elapsed

すべてのロードは64バイト（取得できる最小量、キャッシュライン）なので、64を掛けると、このクエリ中にCPUロードでDRAMから4.5GBをプルしたことがわかります（プリフェッチなし）。

次に、CPUキャッシュを活用するようにアルゴリズムを改善してみましょう。これを行うために、ラジックスパーティショニングと呼ばれる手法を使用します。アイデアは、マージを2つの別々のフェーズに分割することです。

フェーズ1: このフェーズでは、キーを4096個の異なるパーティションに単純に分離します（単純なSlabVecのVecです。SlabVecは、すでにページインされているメモリの上にあるVecに似たデータ構造です。Pivotでは生のメモリにVecを使用しません。なぜなら、多くのばらつきが生じるためです。これはこのブログ記事の対象ではありません！）。パーティションは、キーをハッシュし、その上位12ビット（2 extsuperscript{12}=4096）を取得することによって決定されます。

fn consume(
    &mut self,
    batch: RecordBatch,
    _sender: &mut dyn Sender<RecordBatch>,
) -> unary::Result<()> {
    let keys = batch.column(self.key_column).as_primitive::<Int64Type>();
    for &key in keys.values() {
        let hash = self.hasher.hash_one(key);
        // 上位12ビットを取得したいので、ハッシュ（u64）を52ビット右シフトします
        let partition = (hash >> 52) as usize;
        self.partitions[partition].push(&mut self.allocator, (hash, key));
    }
    Ok(())
}

→

partition = hash >> 52、最初の3桁の16進数

パーティション 0
0x000000… –
0x000FFF…

4242

パーティション 1
0x001000… –
0x001FFF…

5

パーティション 2
0x002000… –
0x002FFF…

77997

…

パーティション 4095
0xFFF000… –
0xFFFFFF…

13

フェーズ2: すべてのデータが処理されたら、パーティションごとに処理を進め、各パーティションでHashMapを作成し、集計してから出力します。このフェーズは元のアルゴリズムと非常に似ていますが、フェーズ1のハッシュを使用します。

fn into_outputter(self) -> unary::Result<Option<Self::Outputter>> {
    let mut groups = Vec::new();
    for rows in &self.partitions {
        let mut table: HashTable<(u64, i64, u64)> = HashTable::new();   // (hash, key, count)
        rows.for_each(|(hash, key)| {
            match table.entry(hash, |group| group.1 == key, |group| group.0) {
                Entry::Occupied(mut group) => group.get_mut().2 += 1,
                Entry::Vacant(slot) => { slot.insert((hash, key, 1)); }
            }
        });
        groups.extend(table.into_iter().map(|(_, key, count)| (key, count)));
    }
    Ok(Some(Outputter::new(groups)))
}

パーティション、一度に1つずつ

0–1完了 2進行中 3–4095待機中

パーティション 2

HashTable

出力

77997

→

UserID count

7

3

99

1

→

(UserID, count)

(7, 3)

(99, 1)

一見すると、このソリューションは奇妙に見えるかもしれません。私たちはより多くの操作を行っています。少ないのではなく！両方のソリューションで、各行はハッシュされ、HashMapに入力されます。しかし、このソリューションでは、まず無意味に見えるVecにデータをプッシュしています。

ここでの鍵（言葉遊びではありません）は、なぜこれを行ったのかを理解することです。それは、集計するHashMapを小さくするためです。グループバイを4096個のピースに分割することで、作業用HashMapがCPUキャッシュに収まる可能性がはるかに高くなります。HashMapのルックアップを行うたびに、CPUは関連メモリがキャッシュに収まっている可能性が高くなり、大幅な時間を節約できます。しかし、なぜ私を信じるのですか？実行してみましょう！

taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c '\timing on' -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

そして…ドーン！3.3秒、そして2回目の実行で2.7秒！間違いなく改善しました。しかし、この点を強調するために、もう一度 perf を実行してみましょう。

sudo perf stat -C 3 -M backend_bound_memory,retiring -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

そして、私たちの結果は次のとおりです。

 Performance counter stats for 'CPU(s) 3':

        3790955223      ex_no_retire.load_not_complete   #     23.5 %  backend_bound_memory
       20376118172      de_no_dispatch_per_slot.backend_stalls
        5442424751      ex_no_retire.not_complete
       10083617764      ls_not_halted_cyc
       19350459182      ex_ret_ops                       #     32.2 %  retiring
       10023435553      ls_not_halted_cyc

       3.575992317 seconds time elapsed

これで状況が完全に変わったことがわかります。メモリ待機に費やされる時間は23.5%（以前は50%）であり、オペレーションの実行に費やされる時間は32%です。実際にはより多くの作業を行っていることに気づくかもしれません。この実行では、19350459182オペレーション（ex_ret_opsカウンター）を実行しましたが、以前はデータベースは11431618219オペレーションを実行していました。しかし、これは価値があります。なぜなら、前述のように、コールドDRAMアクセスをCPU命令に変換できるなら、それはほぼ常に良い取引だからです。この場合、メモリによって停止していたCPUスロット数を8364109137から3790955223に減らしました。

DRAMからプルするメモリ量をさらに確認するために、DRAMからのメモリロードがどれだけあるかを再度確認します。

sudo perf stat -C 3   -e ls_dmnd_fills_from_sys.dram_io_near   -- taskset -c 7 psql -h 127.0.0.1 -p 5440 -U pivot -c "SELECT count(*) FROM (SELECT COUNT(*), UserID FROM hits GROUP BY UserID)"

 Performance counter stats for 'CPU(s) 3':

          25688280      ls_dmnd_fills_from_sys.dram_io_near

       3.009547012 seconds time elapsed

やった！これは、オンデマンドでDRAMから1.5GBをプルしたことを意味します。ナイーブバージョンでは4.5GBでした。

もちろん、これはGROUP BYでCPUキャッシュを活用できる限界ではありません。CPUキャッシュを活用することだけが、DRAMレイテンシを「隠す」方法ではありません。別のトリックは、必要になる前にメモリをキャッシュにプリフェッチすることです。さらに別のトリックは、メモリ帯域幅を最大化できるアルゴリズムを作成することです。しかし、それはこのブログでは扱いません！次のブログで、JOINプロービングの一見非常に奇妙な実装について説明します。

今のところ、あまり説明せずに、Pivotが単一コアでこのクエリを実行する速度を示します。

Time: 1848.353 ms (00:01.848)

そして、プルするRAMの量です。

 Performance counter stats for 'CPU(s) 3':

          14917958      ls_dmnd_fills_from_sys.dram_io_near

       2.182674864 seconds time elapsed

これは954 MBに相当します。

もちろん、Pivotは16コアすべてで並列実行するように設計されています（そこには他の多くの興味深いケースがあります）。その場合、次のようになります。

Time: 171.773 ms

素晴らしいです :)

超高速なパフォーマンスをParquet上で体験したい場合は、Pivotをお試しください（OSSの楽しみです！）。また次回お会いしましょう。