データベースストレージ 基礎

row 42 はエンジンがアドレス指定できるものではない。できるのはヒープファイル内のページとその中のスロットで、この 2 つがタプルの身分証だ：

アドレスが検索ではなく算術であることに注目してほしい：12 ページ目は 98,304 バイト目から始まる。どのページも同じ大きさだからだ。この節の残りはその制約の下にある —— 可変長の行を固定長の箱に収める解き方は、どのエンジンもスロテッドページだ。

実際の比率で描くと、8 KB の Postgres ページは 24 バイトのヘッダ、そこから下へ伸びるスロット配列、そして反対の端から上へ伸びるタプルデータでできている。スライダを引いて 104 バイトのタプルを詰め、両端が閉じるのを見てほしい：

ヘッダが存在する理由である不変条件に注目してほしい：pd_lower ≤ pd_upper、空き領域はちょうどその差だ。タプル 1 つは 108 バイト —— 本体 104 とスロット 4 —— なので 75 個が入り、68 バイトが取り残される。75 を越えても挿入は失敗せず、別のページへ行く。テーブルが行のファイルではなく配列である理由がこれだ。

このページの中身もその場では編集されない。MVCC のもとで UPDATE はまるごと新しいバージョンを書き、古いほうを死んだと印を付ける。新しいほうがここに収まるかはfillfactor が決める。それを決めてから行を更新してほしい：

既定の fillfactor 100 では余地が無く、更新はどれも別ページに着地して全インデックスにエントリを書く。fillfactor 90 なら同じ 8 回が全部 HOT だ —— インデックスは古いラインポインタを指したままで、それが転送するので、インデックスページに触らない。

なぜ 8 KB か。ページが I/O の単位であり、キャッシュの単位であり、多くのロックの単位であり、ログレコードの単位でもあるからで、そのサイズは 4 つ全部を同時に動かす。これらのエンジンが実際に出荷する 5 つのサイズをスライダで歩き、ポイント読み取りとスキャンが逆方向へ引っ張り合うのを見てほしい：

ポイント読み取りは 1 行のためにページ 1 枚を丸ごと動かすので、4 KB は 39 倍、64 KB は 630 倍に増幅する。スキャンは逆に引く：同じ 1 万行が 4 KB では 271 回、64 KB では 17 回だ。スライダ上のエンジンが全部 8 KB と 16 KB に住んでいるのは、そこが両方とも我慢できる唯一の場所だからだ。

タプルは 1 ページに収まらなければならず、64 KB の JSON 文書は収まらない。 Postgres の答えが TOAST だ：しきい値を越えると値はページを出て、その場に残るものは 18 バイトのポインタで、兄弟テーブルのチャンクを指す。属性を大きくして、出ていくところを見てほしい：

破線のしきい値に注目してほしい —— 2032 バイト、ページサイズではなくページの 4 分の 1 だ。越えると値は圧縮され、 1,996 バイトのチャンクに切られる。64 KB は33 行のチャンクだ。読み取りは透過的。 TOAST 列の UPDATE は違う：MVCC が新版を書くので、 1 バイトのために 33 チャンク全部が書き直される。

ここまでがディスクだ。データベースがまるきり使い物にならないわけではない理由が バッファプールだ：(relation, page) をキーにページを RAM に保持するハッシュテーブル。ヒット率を動かして、平均読み取りのどれだけがヒットではなくミスのものかを見てほしい：

99% でも棒がほぼ全部ローズであることに注目してほしい。ヒットは 0.1 µs、NVMe のミスは 100 µs なので、100 回に 1 回のミスだけで平均は 1.10 µs —— 全キャッシュ経路の 11 倍になる。95% は「高そう」に聞こえて 5.10 µs を測る： 4 ポイントの差で 99% より 4.6 倍悪い。ヒット率は線形のつまみではない。

プールは有限なので、1 枚入れれば 1 枚追い出す。Postgres は clock sweep を使う：針がバッファを回りながら使用カウンタを 1 ずつ減らし、すでに 0 になっている最初のバッファを取る。1 周させてみてほしい：

どれだけ時間がかかるかに注目してほしい。1 周目では何も追い出せない。どのバッファも少なくとも 1 度は触られていたからだ。針がぐるりと回りきってはじめて犠牲者が存在する。それこそが要点で、このスイープは LRU リストを維持せずに LRU を近似する。そのリストの維持はバッファアクセスのたびにロックを取ることを意味する。

LRU の近似には有名な破綻がある。1 回きりのシーケンシャルスキャンは読んだページをきっかり 1 度ずつ触るので、素の LRU ではスキャンされたページが 1 枚ずつホットなページを追い出す。スキャンを伸ばして、ホットセットが死ぬのを見てほしい：

先頭挿入では 16 ページのスキャンでホットページが 1 枚も残らない。しかも故障は無音だ：書き込みは無傷、スキャンも速く、被害は数分後に無関係なクエリのレイテンシの段差として現れる。InnoDB の中点挿入なら同じスキャンはリスト末尾の 37% にしか届かず、11 枚は長さに関係なく生き残る。

書き込みは起きた時点ではディスクへ行かない。変更されたページはダーティと印を付けられてプールに残り、最終的にそれを全部押し出すのがチェックポイントだ。checkpoint_completion_target がそのフラッシュに区間のどれだけを使わせるかを決める。それを下げて、フラッシュ速度がデバイス予算を置き去りにするのを見てほしい：

4 GB のダーティバッファを既定 0.9 に広げれば 15 MB/s —— 予算の内側で、見えない。0.05 に載せれば273 MB/s、デバイスにそれは無い：カーネルはfsync でブロックし、前景のクエリが全部その後ろで詰まる。古典的なチェックポイントストールで、設定のバグだ。

B+ ツリーは「手数の多い二分木」ではない。ノードがページである木で、 1 ノードはページに入るだけの子を持つ。これが効くのは、検索の代価が触ったページ数であって比較した回数ではないからで、二分インデックスがB+ ツリーに即座に負けるのもそこだ：

テーブルが育つにつれ差が開くのを見てほしい。10 億行で二分インデックスは 30 段、B+ ツリーは 4 段 —— 同じ答えにページ読み取りが 7.5 倍だ。二分は 1 段で 1 ビット、B+ ツリーは 1 段で 9 ビット買うからだ。

だから分岐数は設計ではなく算術だ。キーと8 バイトの下降ポインタと 4 バイトのスロットで 1 エントリ。ノードは使えるページが割り切れるだけ持つ。2 本のスライダを動かして、ファンアウトが動くのを見てほしい：

16 KB の InnoDB ページと 16 バイトのキーでノードあたり 584 エントリ。キー幅がどれほど効くかに注目してほしい： 64 バイトのキー —— たとえば VARCHAR を主キーにした場合 —— で同じページが 215 まで落ちる。同じインデックスバイト数でファンアウトが 3 分の 1 になり、幅の広い自然キーが木の段を 1 つ増やすのはここだ。

どの段もファンアウト倍になるので、深さは 584 を底とする行数の対数で伸びる。行数を 12 桁ぶん上げて、段が何回増えるか数えてほしい：

4 段で 1,160 億行をアドレスできる。「実際どれくらい深くなるのか」への答えがこれだ：深くならない。10 億行のテーブルはルートからリーフまで 4 回のページ読み取りで、ルートとその 1 つ下の段は合わせて 585 ページ、9 MB でバッファプールを出ない —— だから実際の検索はキャッシュ済みのプローブ 3 回と、ミスするかもしれない 1 回だ。

プランナが users_pkey を選んだときに買ったのが、まさにこれだ。下降を 1 歩ずつ進めてほしい：越えた段、今探しているページ、そして最後にインデックスを完全に離れるヒープ取得:

最後のステップで読み出しが跳ぶのに注目してほしい。キャッシュ済みプローブ 4 回は 0.60 µs。ヒープ取得はミスすれば 100 µs —— その前の下降全体の 167 倍だ。見た目が同じ EXPLAIN 出力が実行時に 2 桁違いうる理由がこれで、リーフだけで答えるカバリングインデックスにこれだけの価値がある理由でもある。

それはインデックス側で買い戻せる。クエリのペイロード列を自分のリーフに抱えさせる —— INCLUDE リストだ。列を足して、インデックスが代金を払うのを見てほしい：

3 列すべてを抱えると 100.6 µs の検索が 0.60 µs のインデックスオンリースキャンになり —— インデックスは 18.7 GB から 86.2 GB へ育つ。リーフ 1 枚が 818 エントリから 177 エントリになるからだ。内部ノードは無傷で、INCLUDE は底だけを広げる。木は深くならず、太くなる。

B+ ツリーのプラスはリーフが連結されていることだ。範囲クエリは 1 度下降して、あとは横に歩く。上限を上げて、1 回の下降と横歩きをハッシュインデックスがやらざるを得ないことと比べてほしい：

2,000 行のときB+ ツリーは 15 ページを読み、ハッシュインデックスは 2,001 回の個別検索をする。ハッシュインデックスには「次のキー」という概念が無いからだ。順序付きインデックスの論拠はこれが全部で、ORDER BY、MIN、MAX、そしてキーセットページングが B+ ツリーではただ同然、ハッシュでは不可能な理由でもある。

代価は挿入で出る。エントリは空きのあるリーフに入る —— 空きが尽きるまでは。 8 個ぶんの空きがあるリーフにキーを押し込み、 9 個目が分割を強いるのを見てほしい：

破れたページは差分では直せないので、Postgres はチェックポイント後に初めて触ったページごとに 8 KB のイメージ全体をログに書く。素の挿入は WAL 約 100 バイト。分割を起こす挿入はリーフ 2 枚と親を書き直し、16 KBかかる —— 同じ 1 行に 165 倍だ。

そのためキーの順序はスループットの判断になる。連番キーは何度も同じ最右リーフに落ちる。ランダムキーはどこにでも落ちる。挿入数を上げて、連番とランダム UUIDを切り替えてほしい：

連番の 2,000 挿入はリーフ 10 枚を汚し WAL 275 KB。同じ 2,000 をランダム UUIDにすると 1,648 枚 —— 5,000 リーフ上のクーポンコレクター期待値 —— を汚し 13 MB を出す。ログもレプリケーション帯域も 49 倍、おまけに 1 度しか触られないページで埋まったバッファプールが付く。v7 UUID か bigint か、請求書かだ。

もう 1 つ成立していなければならないことがある：リーダが下降している最中に、ライタがその足元のノードを分割する場合だ。素の latch coupling は子をラッチするまで親を握り続ける。安全だが、経路を直列化する。リーダを歩かせ、木を切り替えてほしい：

Lehman と Yao の B-link ツリーは全ノードに右リンクを持たせるので、分割後に到着したリーダはルートからやり直すかわりに横へ 1 本進む。 Postgres の nbtree がこの理由で B-link だ：分割が親のラッチを保持しなくなり、ライタが下降中のリーダを止めなくなる。

2 つの構造は同じ問い —— このキーはどこに住むのか —— に正反対の方針で答える。B+ ツリーはソート済みの構造を 1 つ持ち、その場で編集する。LSM はたくさん持ち、1 つも編集せず、後でマージする。同じ 12 回の書き込みを両方に投げてほしい：

書き込みがどこに落ちるかに注目してほしい。その場でなら 12 回の書き込みが 9 つの別々のページに散り、そのどれもがシークとページの書き直しだ。追記なら 12 個は 1 本のファイルに連続する —— 同じ 12 個の事実を、キー順ではなく到着順で記録しただけだ。

だから書き込みはシークしない。ログに追記し、RAM 上の memtable に挿入して、返る。 memtable が満杯になって初めて木に何かが届く。書き込み量を上げて、SSTable が現れるのを見てほしい：

この経路のどこにもランダムが無いことに注目してほしい。RocksDB の既定 64 MB のmemtable は 64 MB 書くごとに 1 回のフラッシュを意味し、フラッシュとはすでにソート済みの構造を 1 本のシーケンシャル書き込みでファイルにすることだ。書き込みの上限はデバイスのシーケンシャル帯域であって、ランダム書き込み IOPS ではない —— 同じ NVMe 上でこの 2 つはおよそ 1 桁違う。

SSTable はソート済みのバイト列だけではない。自前のインデックスブロック —— 4 KB のデータブロック 1 つに 1 エントリ —— とフィルタブロックを持ち、どちらもファイルに比例して育つ。1 つ大きくしてほしい：

そのメタデータがいかに安いかに注目してほしい：64 MB のテーブルでインデックスとフィルタを合わせてファイルの 1.8% しかなく、それが 16,384 個の 4 KB ブロックから 1 つを 1 回の読み取りで見つけさせ —— あるいは何も読まずにファイルごと飛ばさせる。

これらのファイルは無限には溜められないので、各段が上の段の 10 倍を持つレベルに整理される。データセットのサイズを上げて、必要なレベルがいかに少ないかを数えてほしい：

1 テラバイトで L0 の下に 5 レベル。 B+ ツリーがくれたのと同じ対数で、底が 584 から 10 に変わっただけだ —— LSM の読み取りが B+ ツリーの読み取りより高くつく理由と、その差の大きさが、まさにこれだ。LSM は探す場所が多いから、多くの場所を探さなければならない。

だから読み取りは下っていく。memtable、次に L0 の全ファイル、そして各レベル 1 ファイル —— 各停留所でブルームフィルタがただでファイルを飛ばすか、本物のディスク読み取りを払わせるかする。この検索を下らせてほしい：

どの停留所がただなのかに注目してほしい。ブルームフィルタは偽陰性を出せないので、「無い」は確定で、ハッシュ数回以外は何も要らない。ディスクを触るのは「あるかも」だけだ。フィルタが無ければ、どの読み取りも全レベルからブロックを取ることになり、この構造はどの深さでも使い物にならない。

フィルタもただではない：RAM であり、キーあたりのビット数で大きさが決まる。それを飢えさせて偽陽性率を上げ、ただのスキップがただでなくなるのを見てほしい：

RocksDB 既定のキーあたり 10 ビットで率は 0.82%。 6 レベルで 1,000 回の検索あたり 49 回の無駄読み、10 億キーに 1.16 GB のRAM。5 ビットなら RAM は半分、率は 9.1% —— 1,000 回あたり 543 回だ。閉じた形は 0.6185 のビット数乗で、 1 ビットごとに誤りは 1.6 で割られる。

後回しにした請求が届くのがコンパクションだ。あるレベルを次のレベルへマージすると下のレベルを約 T 回書き直すので、書き込み増幅は T × レベル数になる ——読み取り増幅は逆に動く。倍率を動かし、方式を切り替えてほしい：

2 本の棒が逆方向に動き、両方が小さくなる設定が無いことに注目してほしい。既定倍率 10 の leveled は書き込み増幅 52 倍と、探るべきファイル 10 個。 tiered は 7 倍と 55 個だ。実際の RocksDB が測るのは 52 ではなく 10〜30 倍で、動的レベルサイジングが中間のレベルを名目容量よりはるかに小さく保つからだが、取引の形はまさにこの通りだ。

これは取り込みに硬い上限を課し、それを越えたときの故障が LSM の本番事故だ。書き込み速度をコンパクションが排出できる量より上へ押し、L0 が埋まるのを見てほしい：

600 MB/s のデバイスが 52 倍の増幅を払うとユーザ書き込みは11.5 MB/s しか吸収できず、超えた分は積み上がる。 50 MB/s なら L0 は 60 秒で level0_stop_writes_trigger に達して書き込みが止まる。トリガより下の故障は無音で、しかも悪い：スループットは健全に見えたまま、あらゆる検索が 10 個でなく 40 個のファイルを黙って探っている。

最後にもう 1 つの非対称。ファイルが不変なので、削除は何も消せない —— キーが消えたと述べるトゥームストーンを書く。行を削除して、データベースが大きくなるのを見てほしい：

領域が返ってくるのは、コンパクションがそのトゥームストーンを最下層まで運んだときだけで、冷たいデータではそれが永久に来ないこともある。さらに悪いことに、範囲スキャンは範囲内のトゥームストーンを全部読まなければならない： Cassandra は tombstone_failure_threshold(既定 10 万)でクエリを中止する。「古い行をいくつか削除した」が「あのパーティションの読み取りが例外を投げるようになった」に変わるのはこうしてだ。

規則は 1 文で例外は無い：データページへの変更は、それを記述するログレコードが先に永続ストレージ上に無い限り、永続ストレージに到達してはならない。ページはその後いつ書かれてもよい ——ログこそが正典だ。

これが割に合うのは、復旧がページの中身をすでに判別できるからだ。どのページも最後に適用されたレコードの LSN を持ち、REDO はそれ以下のレコードを全部飛ばす。復旧を前へ引いてほしい：

ページがすでに持つ 4 レコードはスキップされるので、ログを 2 度再生しても 1 度と同じページになる。この冪等性のおかげで復旧自体がクラッシュしてもやり直せる —— さもなければ起動中に落ちたマシンは二度と立ち上がらない。

規則が存在する理由を見るには、一度壊してみる価値がある。ログレコードとダーティページのどちらが先にディスクへ届くかを選び、クラッシュをその間に動かしてほしい：

ページが先でも派手には失敗しないことに注目してほしい。復旧はログにそのページの話を何も見つけず、もう正しいと結論する —— 中途半端に適用された変更がデータベースの真実になり、チェックサム失敗だけがそれを知る唯一の機会になる。ログが先のクラッシュは退屈で、それこそが要点だ。

この規則のもとで、1 回のコミットは安いステップ 4 つと高いステップ 1 つになる ——仕事、それからフラッシュだ。歩いて、時間がどこにあるかを見てほしい：

棒のどれだけが fsync なのかに注目してほしい。ページの変更、レコードの構築、コミットレコードの追記で合わせて 0.6 µs。fdatasync はこの記事で最良のハードウェアでも 30 µs だ。データベースが書き込みを速くするためにやることは全部、あの 1 区間への攻撃だ。

しかもあの区間はソフトウェアの数字ではない。ログの下にあるデバイスの性質であり、 2 桁半動く。4 つを歩いて、それぞれが定める上限を読んでほしい：

1 セッションは fsync 1 回より速くコミットできないので、上限は 1 ÷ fsync だ：電源断保護付き NVMe で毎秒 33,333、7,200 rpm のディスクで 120 —— プラッタ 1 回転、8.33 ミリ秒で、どうチューニングしてもその下には行けない。保護の無いコンシューマ NVMe が 1,000 なのは、企業機なら無視できるオンボード DRAM を排出するからだ。

毎秒 120 コミットでは使い物にならないので、どのエンジンもそれを受け入れない。 fsync が飛んでいる間に到着したコミットは次の便に相乗りする。セッション数を上げて、fsync の速度が動くのを拒むのを見てほしい：

フラッシュは共有され、待ちは共有されないので、同じディスク上の 64 セッションが 120 回の fsync から毎秒 7,680 コミットを退役させる —— しかもその 1 つ 1 つが自分のデータの永続化をちゃんと待っている。グループコミットは意味論に触れずにスループットを買う。既定で有効な理由であり、synchronous_commit = off が書き込みボトルネックの正解にほぼならない理由でもある。

ログのもう 1 人の消費者はスタンバイで、synchronous_commit がコミットをその管のどこまで待たせるかを決める。スタンバイを遠ざけ、水準を切り替えてほしい：

local がまったく動かないことに注目してほしい。マシンから出ないからだ。同一リージョンのremote_apply は 5.06 ミリ秒 —— local の 165 倍 —— コミットが往復とスタンバイでの再生の両方を待つようになるからだ。レプリカ上で自分の書き込みが読める保証はそれで買っており、値段はそれで全部だ。

ログにはもう 1 つ仕事がある：クラッシュはそこから修復される。ARIES は最後のチェックポイント以降のレコードを 3 パスで処理し、一度もコミットしなかったものに触るのは最後の 1 回だけだ。走らせてほしい：

REDO はコミット済みかどうかに関わらず全部を再生することに注目してほしい。そうせざるを得ない：このパスはデータベースをクラッシュ時点の正確な状態に戻し、それでようやくUNDOが一度もコミットしなかったものを巻き戻せる。1 パスでやるには、それを決めるレコードを読む前に各トランザクションの運命を知る必要がある。

だから復旧時間はログがどれだけあるかで決まり、データベースがどれだけ大きいかでは決まらない。max_wal_size がそのつまみだ。上げて、REDO が伸び、チェックポイントがまばらになるのを見てほしい：

既定の 1 GB では、Postgres が与える 1 コアで 80 MB/s としてREDO は 13 秒。16 GB では 205 秒 —— 3 分半のダウンタイムを、16 分の 1 の回数のチェックポイント、したがって 16 分の 1 の全ページイメージと引き換えに買っている。これがつまみの裏にある本当の取引で、性能の判断ではなく復旧目標の判断だ。

そして人が実際に手を伸ばすつまみに行き着く。synchronous_commit = off は fsync を待つのをやめ、それでも成功を返す。wal_writer_delay を動かして、クラッシュが持っていくものを読んでほしい：

既定の 200 ミリ秒では露出は遅延 3 つぶん —— 600 ミリ秒 ——、いま測った毎秒 7,680 コミットなら 4,608 トランザクションだ。何も壊れてはいない：データベースは一貫した状態で戻り、ただそれらを忘れている。最後の 0.5 秒を失っても本当に構わないときに使うもので、グラフの見栄えのためではない。

覚える価値があるのは3 段目から 5 段目への跳びだ：ページ読み取りはマイクロ秒、ディスク 1 回転はミリ秒。この段差より上はメモリ予算で調整する。下ではハードウェアを選んでいるのであって、設定ファイルは助けにならない。

B+ ツリーが勝つのは一番上の棒だけだ。キー順なら 1 バイト書くごとに 1.8 バイトしか動かさず、並ぶものが無い。ランダム UUID 順では 105 バイト動かし、 leveled LSM より悪い。判断を決めるのは構造ではなくキーの順序で、その次に来るのが常駐のバックグラウンドコンパクタを養えるかどうかだ。

最後の危険信号は、いちばんチューニングらしく見えるものだ。Postgres のプールはカーネルを通して読むので、それがキャッシュするページはたいていOS ページキャッシュにもある。マシンを多めに取って、同じバイトが 2 度キャッシュされるのを見てほしい：

25% では重なりが 16 GB、カーネル側にまだ 42 GB。90% を越えるとソートにも接続にも残らず、スワップし始める。InnoDB の 70〜80% が移植できないのは、あちらが O_DIRECT で 2 つ目のコピーを持たないからだ。

• 「性能のため」の synchronous_commit = off。 グループコミットなら耐久性を失わずに大半が手に入る。
• 主キーにランダム UUID。WAL 49 倍。UUIDv7 は時刻順だ。
• LSM の write スループットへのアラート。張るべきは L0 のファイル数だ。
• fsync について嘘をつくドライブキャッシュ。 電源断テストで検証すること。