ディスクとページ
ディスクは1バイトずつではなく「ページ」というまとまり単位でしか読み書きできない。この一点から、ディスク上のデータ構造の速さは「ページを何回読むか」で測る、という物差しが生まれる。B-Tree も WAL もバッファプールも、この物理的な事情への対処として出てくる。コードは書かない、前提を掴むための章。
この章で知ること
コードは書かない前提章。B-Tree や db 編(WAL、バッファプール)の土台になる、 ストレージの3つの事実を図で掴む。
- ディスクは1バイトずつ読めない。ページという固定サイズの塊単位でしか読み書きできない
- だからディスク上のデータ構造の速さは、比較回数ではなくページ読み回数で数える
- 同じページを続けて触ればキャッシュが効いてメモリ速度になる(局所性の価値)
ページ: ディスクの読み書きの最小単位
ディスク(HDD/SSD)は本のようなもので、1文字だけ読むことはできず、ページ単位でめくる。 ハードウェア自体がセクタ(512B〜4KB)単位でしか転送できず、その上で OS やデータベースが 扱いやすい固定サイズに切り直す。これが「ページ」で、代表的なサイズは:
| 誰のページか | サイズ |
|---|---|
| OS のページキャッシュ | 4KB |
| PostgreSQL | 8KB |
| MySQL (InnoDB) | 16KB |
たとえ欲しいデータが1バイトでも、そのバイトを含むページがまるごとメモリに運ばれる:
ここから大事な発想の転換が生まれる。ページの中の処理(数百キーの二分探索でも)は メモリ上で済むので、ディスクの読みに比べれば誤差。だから ディスク上のデータ構造の速さは「ページを何回読むか」だけで数えればいい。 B-Tree の章で「速さの単位はページ読み回数」と言っているのはこの意味。
アクセス時間: メモリとディスクは別世界
「ページ読み1回」がどれくらい高くつくのか。桁で見る:
メモリと HDD の差は10万倍。人間の感覚に直すと、メモリが「机の上の紙を見る(1秒)」なら、 HDD のランダム読みは「倉庫まで往復する(1日以上)」に相当する。SSD でも1000倍の差がある。 「ディスクを1回でも読まずに済むならどんな工夫でも元が取れる」のはこの桁差のせい。
ランダム読みとシーケンシャル読み
同じ「ページを4枚読む」でも、並び方で速さが変わる。
- HDD: ランダム読みのたびに物理的なヘッド移動(約10ms)が入る。シーケンシャルなら 移動なしで連続転送できるので、100倍以上の差がつく
- SSD: 物理的な移動はないので差は縮むが、それでもシーケンシャルが有利。 OS が「次も隣を読むだろう」と先読みしてくれるのと、SSD 内部も連続アクセスに最適化されているため
db 編で WAL(書き込みを追記だけにするログ)を作るとき、この 「追記(シーケンシャル)は書き込みの中で最速」という事実が設計の根拠になる。
キャッシュ: 同じページなら2回目からタダ同然
読んだページはメモリに保持される(OS のページキャッシュ、DB のバッファプール)。 つまり「ページ読み回数」で数えるべきなのは正確にはキャッシュにないページを読む回数で、 同じページばかり触るアクセスパターンは実質メモリ速度になる。
これがB-Tree の章のデモで見られる、挿入の局所性の価値の正体になる:
- 昇順キー(UUIDv7 等): 挿入が常に右端の同じページに当たる。そのページはキャッシュに 乗りっぱなしなので、ディスク読みがほぼ発生しない
- ランダムキー(UUIDv4 等): 毎回違うページに当たる。テーブルが大きくなると キャッシュに乗り切らず、挿入のたびにディスク読みが発生する
設計の観点
- 物差しを1つに決める: ページ読み回数で数えると決めた瞬間、ページの中で何回比較したかは誤差になる。何で測るかを決めることが、設計の最初の仕事になる
- 単位に形を合わせる: 読み書きの単位が固定なら、データ構造もその単位に詰める。B-Treeの枝分かれの数がページサイズから決まるのは、その帰結でしかない
- 2つの割引を狙う: 安くなるのは、並んでいるとき(シーケンシャル)と、また同じところを触るとき(キャッシュ)の2つだけ。ディスク上の設計は、このどちらを引き出すかの選択になる
- 桁が違えば釣り合いも変わる: メモリとディスクが10万倍違うなら、ディスクを1回減らすためにメモリ上の計算を100倍やっても釣り合う。工夫の元が取れる範囲が、桁差で決まっている
- 書き換えを追記に寄せる: 追記が書き込みの中で最速なら、書き換えたいものも「先に追記してから」に置き換えられる。WAL もログ構造KVも、この置き換えから出ている
- 土台は1か所に置く: この事実には複数の章がぶら下がる。各章で説明し直さず、ここを参照する形にしてある
対照と実例
| 置き場所 | 1回のランダム読み | 並べて読むと | 設計への効き方 |
|---|---|---|---|
| メモリ | 約 0.0001 ms | ほぼ同じ | ここに載っているかどうかが最大の分かれ目 |
| SSD | 約 0.1 ms | 数倍〜十数倍速い | ランダムでも実用。それでも並びは有利 |
| HDD | 約 10 ms | 100 倍以上速い | ランダムを減らす設計でないと成立しない |
実例:
- PostgreSQL は 8KB: ページの中身(ヘッダ、行へのポインタ配列、行本体)まで公開されていて、実物の詰め方が読める
- InnoDB は 16KB:
innodb_page_sizeで 4KB から 64KB まで変えられる。行が大きいほど大きいページが有利になる - OS のページキャッシュは 4KB: DB が自前のバッファプールを持つのは、どのページを残すかを OS より上手に決められるからになる
裏どり:
- セクタは 512B から 4KB へ: 現在のディスクは物理 4KB(Advanced Format)で、論理 512B を装う互換モードを持つ。ずれた位置への書き込みは読み・変更・書き直しになるので、ページの境界をディスクの境界に合わせることに意味がある
- SSD は消去の単位が別: 読み書きはページ単位だが、消去はもっと大きいブロック単位になる。だから上書きは「別の場所に書いて古いほうを無効にする」形で行われ、装置の内部でログ構造と同じことが起きている。追記中心の設計が SSD と相性がよいのは偶然ではない
- 先読みは推測でしかない: OS は連続して読まれていると見なすと先を読む。ランダムだと分かっているなら、先読みを切ったほうが速いことがある(
posix_fadvise) - プランナは比で持っている: PostgreSQL はランダム読みを順次読みの4倍と見積もる既定値(
random_page_cost)を持つ。SSD ではこの比が実態より大きいため、下げるのが定番の調整になる - 10万倍という数字の出どころ: メモリと HDD の比較はランダムアクセス同士のもので、連続転送で比べれば差はずっと縮む。桁を言うときは、何と何を比べているかを添える必要がある
この章で扱わなかったこと
- ファイルシステムの層: ページとディスクの間には、ジャーナリングやエクステント割り当てがもう1段ある
- RAID と冗長化: 複数台に散らして速さと耐障害性を稼ぐ話は、ここでは触れない
- NVMe のキュー: 並列にどれだけ要求を積めるかで実効速度が変わるが、この章は1回の重さだけを扱った
- 圧縮: ページを圧縮すると読む量は減るが CPU を払う。この交換は扱わない
参考資料
- Latency Numbers Every Programmer Should Know — 年代別のレイテンシ比較
- PostgreSQL: Database Page Layout — 8KB ページの中身の実物
- Alex Petrov『Database Internals』1〜3章 — ページとB-Treeの関係を最も丁寧に扱う本