Open4

UUIDのキャッシュ効率についてChatGPTに聞いたやつ

UUID
データベース設計
ChatGPT で書いた
Nakano as a ServiceNakano as a Service

データベース設計において、主キーにUUIDを使用するとシーケンシャルなIDに比べてキャッシュのヒット率が低下するのはなぜですか？

Nakano as a ServiceNakano as a Service

とても良い質問です。

要点だけまずまとめると：

  • UUIDはランダムに生成されるので、データがディスクやインデックス上でバラバラに配置される
  • これにより、近くのデータをまとめてキャッシュに乗せる効率が悪くなる
  • 一方、シーケンシャルID（例：自動採番された整数）は順番に増えていくので、物理的にも論理的にもデータがまとまりやすい
  • そのため、同じページ（キャッシュ単位）に複数の近いレコードが載りやすく、キャッシュヒット率が高くなる

もう少し詳しく仕組みを説明しますね。

データベース内部で起こること

データベース（特にB+ツリーを使うインデックス構造）では、データはキー順に格納されます。

  • シーケンシャルなIDだと、次のデータはだいたい前のデータのすぐ隣に置かれます。
    • 例：id=100, id=101, id=102 ... という順番で並び、ストレージ上でも近い場所に配置される。
  • UUIDだと、新しいレコードを追加するとき、既存のツリーのランダムな場所に挿入されるので、データ配置が分散してしまいます。

キャッシュの影響

データベースはストレージから読み込んだデータを「**ページ単位（例えば8KB）」でキャッシュ（バッファプール）に保存します。

  • シーケンシャルIDだと、あるページに複数レコード（近いIDのもの）がまとまって乗るので、1回読み込めば近いレコードも一緒にキャッシュできる確率が高いです。
  • UUIDだと、バラバラなので1ページに関係ないレコードがまばらにしか載らず、すぐ別ページをまた読み込むことになり、キャッシュ効率が落ちるわけです。

図でイメージすると：

  • シーケンシャルID:
    [page1] id=100, id=101, id=102
[page2] id=103, id=104, id=105
  • UUID:
    [page1] id=b3f1..., id=9a7c..., id=7d2e...
[page2] id=f7e8..., id=1c9a..., id=32b4...

つまり、UUIDは物理的な局所性（locality of reference）が悪い、これが原因です。

もしさらに深堀りしたいなら、

  • UUID v1（タイムスタンプベース）は少しマシ
  • UUID v7（2022年にできた標準、タイムオーダー付きUUID）はこの問題を意識してる
    という話にも進められます！

続けて詳しく聞きたいですか？（たとえば「UUID v7だとキャッシュ効率はどうなるのか？」など）

Nakano as a ServiceNakano as a Service

キャッシュについて深掘りさせてください。ストレージからデータを取得する時に、あるページに複数レコードがまとめて乗るのは、ストレージデータ取得時にリーフブロックをまとめて取得してキャッシュしているからですか？

Nakano as a ServiceNakano as a Service

はい、かなり本質を突いています！
整理しながら少し丁寧に答えますね。

まず用語確認

  • ページ：ストレージ上の最小単位（PostgreSQLだと1ページ = 8KB）
  • リーフブロック（リーフノード）：B+ツリーの一番下の層、実際のデータ（もしくはデータへのポインタ）を持つブロック

質問に答えると

ストレージデータ取得時にリーフブロックをまとめて取得してキャッシュしているからですか？

厳密には

  • 「リーフブロックをまとめて取得している」というより
  • 「リーフブロック1個（≒1ページ）を読み込むと、そこに複数のレコードが詰まっていて、それがまるごとキャッシュに乗る」
  • ということです。

つまり、まとめて取得するというより、「ページ単位でしか読めない／キャッシュできない」から、結果的にまとめて載る、という方が正しいです。

どうしてそうなるか（内部の流れ）

  1. データベースは、インデックス（B+ツリー）をたどってリーフノードに到達する
  2. リーフノード（例えば8KB）を1ページ単位でストレージから読み出す
    • この時、8KBの中に複数レコードが入っている
  3. 読み出したページはバッファプール（キャッシュ領域）に置かれる
  4. 次に近いレコードを読みたいとき、すでにキャッシュにあればディスクアクセス不要になる（キャッシュヒット）

シーケンシャルIDだと良いこと

シーケンシャルIDなら、次にアクセスするレコードも同じリーフブロックに載っている確率が高いので、

  • 「すでにキャッシュにあるページから読む」
  • →「ディスクI/O発生しない」
  • →「高速になる」

この連鎖が起きやすいです。

UUIDだと悪いこと

UUIDのようにランダムなキーだと、

  • 新しいレコードがリーフノードのどこにでも入り込む
  • 近いID同士でも別のリーフブロック（別のページ）に配置される
  • →次のレコードを読むたびに新しいページをロードするはめになる（キャッシュヒット率低下）
  • →ディスクI/Oが増える
  • →性能が落ちる

です。

まとめ

観点 シーケンシャルID UUID（ランダムID）
物理配置 順番に並ぶ バラバラに配置
ページあたりレコード 近いIDのレコードが同じページに載りやすい ばらけるので一貫性がない
キャッシュヒット率 高い 低い
ディスクI/O負荷 少ない 多い

ここまでOKでしょうか？
もし次に進めるなら、

  • 「リーフノードの分裂」（UUIDだと頻繁に起きてBツリーが肥大化する話）
  • 「UUID v7ならどれくらいマシになるのか」
  • 「PostgreSQLで実際にページヒット率を測定する方法」

みたいな話にも進めます！
興味ある方向を教えてください！