# スロット化ページ ## 定義 スロット化ページ(slotted page、スロットディレクトリとも呼ばれる)は、可変長レコードをディスク上のページ内で効率的に管理するための技法である。ページをスロット(セル)のコレクションとして編成し、ページの両側にある2つの独立した領域に、セルへのオフセットポインタとセル自体をそれぞれ配置する(ポインタはページの一方の端から、セルは反対の端から詰めていく)。順序を維持するために必要なのはポインタの再編成のみであり、レコードの削除はポインタの無効化・削除だけで行える。PostgreSQLをはじめ多くのデータベースで採用されている。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.5) スロット化ページが解決する課題は3つある。(1) 可変長レコードをサイズが一致する空き領域が見つからない限り回収できないという断片化問題、(2) 削除済み領域の回収、(3) 実際の配置に関わらずページ内のレコードを一意な識別子で参照できること、である。スロット化ページは、ページ外からスロットをIDでのみ参照させることで、実際の物理配置をページ内に閉じた問題にする。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.5) セルは**キーセル**(内部ノード用。セパレータキーと子ページへのポインタを保持)と**キーバリューセル**(リーフノード用。キーとデータレコードを保持)に区別され、ページ内のすべてのセルは型が統一される(混在しない)。セルはページに挿入順で配置される一方、セルへのオフセットポインタはキー順にソートされ、二分探索を可能にする。新規セルの追加時は既存セルを再配置する必要がなく、挿入位置より後ろのポインタをシフトするだけで済む。削除されたセルの領域は即座に詰め直さず、メモリ内の利用可能リスト(解放セグメントのオフセットとサイズ)で管理し、ファーストフィット/ベストフィットで新規セルに再利用する。連続した十分な空きがなく断片化した空きの合計だけが足りる場合は、有効なセルを読み取り・書き直してページをデフラグする。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.6-3.8) ## 横断的知見 - **オーバーフローページは、スロット化ページのセルサイズ上限を「max_payload_size」という明示的な閾値として定義し、超過分を通常セルの外へ逃がすことで区別する**: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] はスロット化ページのセルが可変長になりうることを示すが、セルサイズの上限そのものは規定しない。[[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] §4.1.5 はこの空白を埋め、ノードに直接格納できるペイロードのバイト数(max_payload_size、ノードサイズをファンアウトで割った値)を明示的な閾値として定義し、これを超えるペイロードをプライマリページからリンクされたオーバーフローページへ格納するとする。この結果、通常セルは「max_payload_size以下のペイロードを保持しプライマリページに収まるセル」、オーバーフローセルは「先頭がプライマリページに、残りがリンクされた別ページに分割格納されるセル」として区別される。すなわち3章が定義した「セルは可変長でよい」という抽象的な設計原則を、4章が具体的な閾値とページ間リンク機構によって実装可能な形に落とし込んでおり、以前の未解決の問い(オーバーフローページがセルサイズ上限をどう扱うか)はこれで解消された。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.6, [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] §4.1.5) - **スロット化ページのデフラグは、MVCC下では「削除済みセルの即時回収」ではなく「見た可能性のある全トランザクションの完了」を条件とする回収に置き換わる**: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] はセルの削除・デフラグを利用可能リストとファーストフィット/ベストフィットによる領域再利用として説明するが、並行トランザクションとの調整には踏み込まない。[[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] §4.7.1 はこの調整を具体化し、一部のデータベースが削除・更新されたセルをマルチバージョン同時実行制御のためにそのまま残し、更新が完了するまで並行トランザクションからアクセス可能な状態を保ち、他のスレッドがアクセスしなくなり次第回収すると述べる。ゴーストレコードをたどる構造を維持する実装では、それらを見た可能性のあるすべてのトランザクションが完了した時点で回収する。これにより、以前の未解決の問い(デフラグは同時実行制御下でどう調整されるか)に対し、「ロック・ラッチによる排他」ではなく「可視性に基づく遅延回収」という具体的な回答が得られた。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] §3.8, [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] §4.7.1) ## 未解決の問い - キーと値をリーフレベルで別々に格納する局所性改善パターン(ch.3 §3.8で言及)は、[[B-Treeノードレイアウト最適化]]が扱うprefix truncation・dense leafとどう組み合わさるか、あるいは競合するか。 - ファーストフィット/ベストフィットのどちらの戦略が、実際のワークロード(挿入・削除パターン)でページ断片化率と性能のトレードオフとして優れるか、定量比較はあるか。 - オーバーフローページ自体が断片化した場合(ch.4 §4.1.5で「オーバーフローページもプライマリページと同様に断片化しうる」と述べられる)、そのデフラグ・回収は通常のスロット化ページのデフラグ手続きと同じアルゴリズムを共有するのか、専用の帳簿管理が必要か。 - ゴーストレコードの回収判定(「見た可能性のある全トランザクションの完了」)は、長時間実行される読み取りトランザクションが存在するワークロードで、どの程度ページ断片化を長期化させるか。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]] - 概念: [[B-Tree]] / [[B-Treeノードレイアウト最適化]] / [[バイナリエンコーディング]] - エンティティ: [[PostgreSQL]] / [[SQLite]] ## 出典 - [[@2021__OReillyJapan__詳説 データベース - Chapter 3 ファイルフォーマット]](§3.5 スロット化ページ、§3.6 セルのレイアウト、§3.7 セルをスロット化ページに結合、§3.8 可変長データの管理) - [[@2021__OReillyJapan__詳説 データベース - Chapter 4 Bツリーの実装]](§4.1.5 オーバーフローページ、§4.7.1 更新と削除による断片化)