この記事はデータベース・システム系 Advent Calendar 2023の3日目の記事である。昨日の記事も僕でした。

間接参照を巨大仮想メモリで飲み込む

メインメモリはハードディスクやSSDより容量が小さく、この問題は当面は解決の目処が立たない。

そもそも今のDRAMより速くて安くて大きいストレージが仮に発明されてもそれがDRAMに取って代わるメインメモリの立ち位置になるだけであってその下のレイヤーには依然としてそのメインメモリより安くて大きなストレージが置かれる事になる。大局的な観点ではストレージの階層構造とは経済活動の鏡像でもある。

バッファプール

さて、耳にタコができるほど繰り返しているが現代のデータベースはディスクなどの永続ストレージにデータの本尊が保存され、メインメモリはそれに対する読み書きを高速化するためのデータ一時置き場としての役割を担当している。

代表的なRDBMSは32KBとか64KBとかの単位でディスクの断片を取り扱っており、これをページと呼ぶ。そのページがどれか必要になるたびにメモリに取り出して管理し、都度発生する読み書きを引き受け、必要がなくなったタイミングでディスクに書き戻す。一つのページに対する複数の書き込みをページ単位での最後の書き戻しで一手に引き受けるのでこれはバッファであり、それをたくさん保持する機構の事をバッファプールと呼ぶ。

バッファプールはおよそキャッシュでもあるが、その実体はハッシュテーブルと寿命管理が組み合わさった複雑なデータ構造であり、そのアクセスにはそれなりにコストがかかる。データベースのアクセス上重要なインデックス構造ではB+treeが使われる事が多いが、そのB+treeの1ノードは1ページに対応付けて実装するのが常套であるのでB+treeの高さが3なら3回バッファプールを参照する必要がある。

さて、バッファプールを参照するというのは存外骨が折れる作業である。ハッシュテーブルを共有しているのでスレッド間での調停が必要だし、ハッシュテーブル内でうまく対象物を見つけた後でもLRUやCLOCKなどの操作で参照が発生したことを記録する必要がある。また自分が読んでいる最中に他のスレッドによって書き戻されたり値が書き換わっては困るのでピンを刺す（そういう名前のビットを立てる）必要がある。保存されているキーと検索対象を見比べて自分が次に読むべきページ番号を覚えたらピンを抜く。こういう結構めんどくさい手続きが要るのである。特に参照しかしていないのにピンの抜き差しや参照数の更新を行わないと行けないのは現代のCPU的にもよろしくない。キャッシュコヒーレントトラフィックは書き込みが少し入るだけでも性能が半減以下になることは珍しくない。

Swizzlingとは

B+treeを辿る操作が支配的なワークロードはWeb系でよくあるが、OnLineTransactionProcessing(OLTP)と呼ばれる分野でも結構な支配項である。

「OLTP Through the Looking Glass, and What We Found There」という論文の中でも、バッファマネージャとその近辺で結構なCPU命令数を使っていると指摘されている（下図参照）。

そこで「In-Memory Performance for Big Data」という論文の中で提案されているのがPointer Swizzlingというテクニックである。Swizzleとは英単語としては「丸呑み」という意味である。

Pointer Swizzling自体は既に1990年に出た論文「Pointer Swizzling at Page Fault Time: Efficiently Supporting Huge Address Spaces on Standard Hardware」で提案されているのだが、斜め読みした感じこの論文はハードウェアの限定されたメモリ空間を超えるサイズのデータを透過的に扱えるようにする技法のようで、要点は以下だ

ディスクなどにあるメモリに乗り切らない巨大データが内部で参照しあっている
その一部をメモリに乗せてキャッシュする時に、メモリに乗っているデータ参照の論理ポインタを侵襲的に上書きして生ポインタに置き換える
参照元と参照先の両方がメモリに乗り続けている場合に限り、ディスク上にデータが載っているかどうかを確認することなく直接アクセスが可能
メモリからディスクなどに落とす直前には再度侵襲的に論理ポインタで上書きし直してからディスクに戻す

つまりこれをやるとディスクにあるデータの断片がまるでメモリに置いているかのような速度でアクセスすることができる。情報科学の世界には「どんな問題でも1段の間接参照を追加することで解決できる」という格言があり、これには「ただし間接参照が増え過ぎる問題以外は」という但し書きが時々付いているのだが、Swizzlingはその間接参照を直接参照に書き換えるという逆行を通して高速化している点が面白い。

しかしながらポインタというのは常に片方向の参照であり、メモリからディスクに戻す際にそのページの被参照ポインタのすべてを論理ポインタに書き戻す事はできない。生ポインタがメモリから消去された古いアドレスを指しているケースはプロセスをクラッシュさせうる問題である。この論文の中ではそういうケースに付いて、言語レベルでのガベージコレクションのタイミングなら被参照をすべて洗い出すのでそこでunswizzlingすればいい等と議論しているが、OSのレイヤーからそれを実現するのは不可能である。またファイルに意図的な値を書き込める攻撃者が存在しない場所を読ませようとしたりしてセキュリティ上の懸念があり得る。

日の目を見る丸呑み

このようにOSの文脈では汎用的に使われるには至らなかったSwizzlingであるが、In-Memory Performance for Big Dataの中ではこれはB+treeでのみ使えば良いと提言している。

なぜB+treeで使うのが良いかと言うと

ツリーのルートに近い方が必然的にメモリに乗り、リーフに近い方は必ずその親ノードにアクセスされた後にしかアクセスされないのでリーフに近い側を適応的に侵襲的に書き換えできる
OLTP（On-Line Transaction Processing）の文脈ではB+treeのページ解決時間が結構な割合を占めるのでポインタによる書き換えでツリーを辿る際に毎回バッファプールを参照する必要がなくなる恩恵は大きい
B+treeのアルゴリズムを吟味すればB+treeのノードの被参照のポインタの個数は制限できる。つまりunswizzlingの時に論理ポインタに書き戻すべきポインタの上限数は決まっている。そこだけどうにかできれば良い。
子ページのIDを64bitで持てば64bitのポインタとサイズは同じ。つまりこの論理ポインタは物理ポインタで侵襲的に上書きしても問題ない。

なんとB+treeで実装するのが理想的としか言いようがない特性が揃っている。

ところで教科書的なB+treeはリーフノード同士が左右の双方向参照で繋がっており並行して操作する際にバグの温床になりがちである。また、ノードのスプリット操作の際に木の上に辿る範囲を限定するためにブランチノードが兄弟ノードを持ち親ノードに挿入するのを遅延するB-link-treeという亜種がPostgreSQLでは使われている。そこでFoster B-treeというデータ構造であればすべてのノードは最大でも1つしか親ノードを持たない事を保証できるので、ここだけ双方向ポインタにすることでO(1)の参照コストでUnswizzlingが達成できる。Foster B-treeの解説は機会があれば別の日に譲ろう。少しポイントとなるのは物理ポインタが指す先をプール上のページそのものではなく各ページごとに紐付いているメタデータとする点である。一個分の間接参照が挟まる形になるがバッファプールへのアクセスを迂回できる恩恵と比べたら些細である。

さてこの方法はB+tree内部での参照に関しては圧倒的な高速化を実現する。ワーキングセットのサイズがメモリに収まる限りにおいてはなんとインメモリDBに遜色ないスピードを出すのだ。上の図のTraditionalとSwizzlingの間の開きがそれを物語っている。ボトルネックは解消された。ちなみにこのテクニックは親ノードへの参照が簡単に解決できない状況（B-link-tree）などでは実装の難度が大きく変わるためPostgreSQLやMySQLでは今も実装されてはいない。商用でも実装されたという噂は聞かない。

それは広義のTLBではないですか？

これまでページIDを論理ポインタ、メモリアドレスを物理ポインタという呼び方をしてきたが、大学でOSの授業をちゃんと聞いていた人は仮想メモリと物理メモリの話を思い出した事だろう。OSの上で走るアプリケーションは自プロセス内だけで通用する仮想メモリのポインタへアクセスすると、MMU(Memory Management Unit)がTLB(Transalte Lookaside Buffer)を参照して物理メモリに自動的に読み換えてアクセスする。この変換はハードウェアがサポートして勝手にやってくれるのでアプリケーションから見えるコストはゼロである。つまり論理アドレスを侵襲的に書き換えるなんて蛮行に及ばなくても、論理アドレスをCPUに投げつけたら自動でアクセス可能な物理アドレスに読み替えてアクセスしてくれている。これが仮想メモリと呼ばれる仕組みだ。さて、ところでメモリに入り切らない巨大ファイルを部分的にメモリに乗せてマッピングする専用の機能がLinuxにはある。それはmmapである。

ファイルマップドmmapでそれできるよ。できません

データベースの文脈でmmapを使う事に付いて論じた最近の研究が「Are You Sure You Want to Use MMAP in Your Database Management System?」である。結論から言うとDBMSでMMAP使うのはよしたほうがいいという主張である。

Linux側の都合でメモリ上のデータが勝手にディスクにsyncされる可能性があり、それが未コミットのトランザクションを含む場合WALより先に書き込まれてしまうと復旧不能になる
- mlockでsyncを禁じる事はできるが上限がある
メモリ上の表現とディスク上の表現を一致させる必要があるのでディスク保存時だけ圧縮といった芸当が禁じられる
Linuxのページ粒度での読み書きが行われるので前後ページも勝手に読まれたり（これは制御可能）不当な細粒度で書き出す事になる
mmap内部で取っているロックで競合した場合に何もできなくなる
ファイルから読み出した初回にだけデータ破損のチェックサム照合がしたいが、今のアクセスがmmapされたデータへの初回アクセスかを知るのは困難
内部で同期IOが使われているので速度が出ない。特にページのevictionはシングルスレッドで行われておりそこがボトルネックになった時は悲惨。

fio O_DIRECTを用いてディスクにアクセスした場合と比べてスループットが地を這っているmmap達の図

TLBを書き換える時はマルチコア環境では特に他のすべてのコアに割り込んでTLBを更新しなくてはならずそのオーバーヘッドが避けられない(TLB shootdown)
圧倒的な数のTLB shootdownを浴びるmmapの図

とファイルマップドなmmapはデータベース上で性能や正確性を追求するのであれば好ましくない性質が山盛りである。

仮想メモリを信じよ

ここまでの流れをおさらいすると

バッファプール→毎回ハッシュテーブル引いたりピンを管理するのが遅い

Swizzling→速いけど使える場所が限られるし書き戻さないと事故る

ファイルマップドmmap→実装上の問題が山盛り

と、どれを選んでも辛みがそれなりにあることが分かった所で新提案「Virtual-Memory Assisted Buffer Management」である。

基本的なアイデアとしては「ファイルにマッピングせずにDB最大サイズまで論理アドレスを予約して、ページ単位でファイル上のアドレスとメモリのマッピング操作をLinuxとMMUで吸収してもらおう」というものである。TLB shootdown問題は健在なので専用のカーネルモジュールexmapを実装し複数のページを一括して操作できるAPI(exmap)を設けて高速化を達成した。

具体的な実装としては

ファイルマッピングをしないモードでmmapを呼び出してDBの想定最大サイズの仮想メモリを要求する

Linuxとしてはページテーブルさえ確保できれば物理メモリの100倍だろうが許可はする

ページ毎にそのページの状態を管理する配列を用意しておき、初期状態では全体がevict状態になっているがアクセスが発生する度にそこを参照してEvicted/Locked/Unlocked/Markedの状態遷移の中で変化するようにしておく

Evictedなページに触る時はLockedに書き換えてからディスクから対応するページを読み出して当該アドレスに書き写す
Lockedなページに触る時はUnlockedになるまで待ち、それをLock状態に書き換えることで自分が使っていることを明示する
Unlockedなページの中でも使用頻度の低いものは削除待ちとしてMarked状態にされる

madviseでDONTNEEDを指定してLinuxにしばらく使わない事を明示するとLinuxはその領域を開放して、次回アクセス時はその領域を0埋めした状態でアクセスさせてくれる。

つまりその操作の前にディスクに永続化しておく必要がある

ページの置換アルゴリズムにはCLOCKを使ってバッファプールとして動くところまで作り、ベンチマークを取るとバッファプールを使っているWiredTigerにスケーラビリティで勝ることはもちろん、Swizzlingを使っているLeanStoreに対しても高い性能を発揮する事ができた。

自分の環境（メインメモリ64GBのLinux）で試しに小さいコードを書いてどこまで仮想メモリが確保できるのか二分探索で探してみた所85TB前後であった。

gist.github.com

85TBは単一のマシンにぶら下げるストレージとしては莫大であるがクラウドベースの最先端DBと比べると少し心もとない。ただ分散DBでも個々のワーカーが持つべきデータはせいぜいそのマシンに収まりきるデータでしか無いのでもう1段抽象化を噛ませれば85TBより遥かに大きなデータを扱うための部品としてこの技術が使えるかも知れない。