SSTable・ブロックフォーマットとデータブロックキャッシュ
LSM系DBの読み取りコストは、SSTableの中身を知ると一気に見通せます。data/index/filterブロックの構造、restart pointによるキー圧縮、ブロックキャッシュとの噛み合い方が原理から分かります。
- 1.SSTableはdataブロック群の上にindexブロック・filterブロック・footerを積んだ自己記述ファイル。footerからindexを引き、indexから目的のdataブロックのオフセットを得て、ブロック単位で読む。
- 2.dataブロック内はキー昇順で並び、一定間隔のrestart pointを基準に隣接キーの共通プレフィックスを省くプレフィックス圧縮で詰める。検索はrestart pointを二分探索してから線形に展開する。
- 3.ブロックキャッシュは「展開済みdataブロック」を単位にキャッシュし、圧縮ブロックや圧縮率に直結する。indexやfilterを常駐させ、点検索のディスクI/Oをブロック1個に抑えるのが速さの肝。
SSTable は「自己記述ファイル」である
LSM-Tree が MemTable を不変ファイルとして書き出した SSTable（Sorted String Table）は、単なるキー値の羅列ではありません。LevelDB が定めた .ldb／.sst フォーマットを RocksDB がほぼ継承しており、ファイル末尾から順にたどれば中身を自分で説明できる自己記述構造になっています。なぜ末尾からなのか。ファイルは追記しながらシーケンシャルに書くため、各 dataブロックのサイズやオフセットは全部書き終えた後にしか確定しません。そこで「目次」にあたる indexブロックや filterブロックは最後に書き、ファイル末尾の固定長 footer がそれらの位置を指す、という構成になります。
読み取りは常に footer から逆順にたどります。footer → index → data という参照の連鎖が、点検索をディスク読み取りブロック1個分に抑える仕組みの土台です。
ブロックの階層構造
SSTable は先頭から dataブロックが並び、その上に metaindex・index・footer が乗ります。
| ブロック | 位置 | 中身 | 役割 |
|---|---|---|---|
| dataブロック | 先頭から多数 | キー昇順のキー値ペア（restart point単位で圧縮） | 実データ。読み取りの最小I/O単位 |
| filterブロック | data群の後 | ブロック単位またはファイル単位のブルームフィルタ | 「このキーは無い」を即断し無駄読みを排除 |
| metaindexブロック | indexの手前 | filterブロック等のメタ情報への参照表 | メタブロックの所在を引く |
| indexブロック | 末尾近く | 各dataブロックの最終キーとオフセット長 | 目的キーが属するdataブロックを特定する |
| footer | ファイル最末尾（固定長） | metaindex/indexブロックのオフセットとマジック番号 | ファイル全体の入口 |
各ブロックは「ブロック本体 + 1バイトの圧縮タイプ + 4バイトの CRC32C」という共通の包み（block trailer）で囲まれます。ブロック単位で圧縮（Snappy・LZ4・Zstd など）とチェックサムを持つため、読むときはブロック丸ごとを単位に展開・検証します。これは行ではなくページ単位で I/O する点で、スロット式ページの発想とも通じます。
点検索の流れ
get(key) の流れ
1. footer を読む（固定長, ファイル末尾）
2. footer→indexブロックを読む（多くはキャッシュ常駐）
3. index を二分探索 → key を含みうる dataブロックの {offset,size} を得る
4. （filterがあれば）そのブロックのブルームフィルタに問い合わせ
「無い」なら dataブロックを読まずに終了
5. dataブロックを1個だけ読み・展開し、ブロック内を検索
index は「各 dataブロックの最終キー以上で最小のセパレータ」を持つので、目的キーがどのブロック範囲に落ちるかを二分探索1回で決められます。ブルームフィルタはその手前で「そもそも読む必要があるか」を判定し、存在しないキーのディスク I/O をほぼ消します。
restart point とプレフィックス圧縮
dataブロックの中身が、このフォーマットの一番の工夫どころです。キーはブロック内で昇順に並ぶため、隣り合うキーは先頭部分が一致しがちです（user:1001、user:1002 のように）。そこで各エントリは前のキーとの共通プレフィックス長だけを記録し、差分（suffix）のみを格納します。これがプレフィックス圧縮です。
ただし全エントリを前のキーに依存させると、ブロックの途中から読むには先頭から全部展開し直す必要が出てしまいます。これを避けるために、一定間隔（既定で16エントリごと等）にrestart point を置きます。restart point のエントリだけは共通プレフィックス長を0としてキー全体を格納し、そこから次の restart point までが圧縮の独立した区間になります。
| エントリの構成 | 意味 |
|---|---|
| shared | 直前キーと共有するプレフィックスのバイト長（restart点では0） |
| non_shared | このキー固有のサフィックスのバイト長 |
| value_length | 値のバイト長 |
| key_delta | 共有しない部分のキーのバイト列（non_shared分） |
| value | 値のバイト列 |
ブロック末尾には restart point のオフセット配列とその個数が置かれます。検索はこうなります。まず restart point 配列を二分探索して目的キー以下の最大の restart 区間を選び、その restart point からキーを順に線形展開して目的キーを探す。つまりブロック内検索は「区間単位の二分探索 + 区間内の線形走査」の二段構えで、完全な逐次展開を避けつつ圧縮も効かせます。
restart=16 のブロック（イメージ）
[0] user:1000 ← restart point（キー全体を格納）
[1] shared=6 "01" ← user: + 1001（前と6バイト共有）
[2] shared=6 "02" ← user:1002
...
[16] order:5000 ← restart point（プレフィックス途切れ→全体格納）
...
末尾: restart offsets[] と restart 数
restart 間隔を広げるほど「全体格納するキー」が減って圧縮率は上がりますが、目的キーまでの線形展開が長くなり CPU を食います。間隔を狭めると検索は速いが圧縮が緩む。block_restart_interval はこの圧縮率と検索コストのトレードオフを握るパラメータです。
ブロックキャッシュとの相互作用
ここまでで読み取りがdataブロック単位で進むことを見ました。だからこそキャッシュもブロック単位になります。RocksDB の ブロックキャッシュは、ディスクから読んで展開・検証を終えた dataブロックを保持します（圧縮されたまま別途持つ compressed block cache もあります）。同じブロックへの再アクセスは展開コストごと省けます。
ここが バッファプール と対照的な点です。B+Tree 系のバッファプールが固定長ページを in-place で更新しキャッシュ上で書き換えるのに対し、SSTable は不変なのでブロックキャッシュは読み取り専用で、ダーティページの書き戻しという概念がありません。不変性ゆえにキャッシュ管理が単純で、ロックも最小限で済みます。
| 観点 | ブロックキャッシュ（LSM/SSTable） | バッファプール（B+Tree） |
|---|---|---|
| 単位 | 可変長ブロック（展開後） | 固定長ページ |
| 対象の可変性 | 不変（読み取り専用） | 可変（in-placeで更新） |
| 書き戻し | 無い（dirty pageが無い） | ある（dirty pageをWAL順守で書く） |
| 常駐させたいもの | index・filterブロック | 上位ノード・ホットページ |
実務で効くのは、indexブロックと filterブロックを優先的にキャッシュ常駐させることです。RocksDB の cache_index_and_filter_blocks と pin_l0_filter_and_index_blocks_in_cache が典型で、これらが追い出されると点検索ごとに index/filter の再読み込みが要り、せっかくの「dataブロック1個」設計が崩れます。dataブロックのキャッシュヒット率は、ブロックサイズ（既定4〜32KB級）にも左右されます。
ブロックを大きくすると index が小さくなり（ブロック数が減る）圧縮も効きやすい一方、点検索1回で展開する量が増え、キャッシュには無駄なキーまで載ります。範囲スキャン主体なら大きめ、点検索主体なら小さめが基本線。コンパクション戦略でブロックが書き直される頻度とも合わせて調整します。
大きな範囲スキャンやコンパクション読み取りは、二度と使わないブロックでブロックキャッシュを埋め尽くし、ホットな点検索のブロックを追い出すことがあります（キャッシュ汚染）。RocksDB の fill_cache=false 等で「スキャンで読んだブロックはキャッシュに載せない」よう制御するのは、この巻き添えを避けるためです。
footer→index→dataの参照連鎖で点検索がブロック1個のI/Oに収まること、restart pointがプレフィックス圧縮の独立区間を作り「二分探索＋線形展開」を可能にすること、ブロックキャッシュは展開済みdataブロック単位で不変・書き戻し無しであること、そしてindex/filterブロックの常駐が速度の鍵になることをセットで押さえます。
まとめ
SSTable は dataブロック群の上に filter・metaindex・index・footer を積んだ自己記述ファイルで、footer→index→data の連鎖により点検索をdataブロック1個のI/Oへ落とし込みます。dataブロック内はキー昇順に並び、restart point ごとにキー全体を格納してその区間だけプレフィックス圧縮することで、「区間の二分探索＋区間内の線形展開」で検索と圧縮を両立します。各ブロックは圧縮タイプと CRC を持ち、ブロックキャッシュは展開済みブロックを単位に保持する読み取り専用キャッシュで、バッファプールと違い書き戻しがありません。index/filterブロックを常駐させ、ブルームフィルタで無駄読みを切ることが、LSM の読み取りを実用速度にする決め手です。
データベース Article
SSTable・ブロックフォーマットとデータブロックキャッシュを実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
SSTable
比較で見る軸
難易度: advanced / カテゴリ: データベース / タグ数: 6
導入後に効く点
dataブロック内はキー昇順で並び、一定間隔のrestart pointを基準に隣接キーの共通プレフィックスを省くプレフィックス圧縮で詰める。検索はrestart pointを二分探索してから線形に展開する。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- データベース
- タグ数
- 6
判断チェックリスト
- 自社の用途が「SSTable / ブロックフォーマット」に近いか確認する。
- 強みである「SSTableはdataブロック群の上にindexブロック・filterブロック・footerを積んだ自己記述ファイル。footerからindexを引き、indexから目的のdataブロックのオフセットを得て、ブロック単位で読む。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。