自作LSM Treeで学ぶ、ストレージエンジンのしくみ

GREE Tech Conference 2025で発表された資料です。
https://techcon.gree.jp/2025/session/Short-Session-2

Transcript

1. 自作 LSM Tree で学ぶストレージエン ジンのしくみ グリーエックス株式会社 エンジニア 高田倫太朗
2. 高田 倫太朗 2025年にグリーホールディングスに新卒入社。 現在、広告事業のサーバーサイドエンジニアとして、 Golang, k8s等を用いて開発業務を行っている。 大学で、機械学習、信号処理を専攻。 受託開発企業、スタートアップ企業などでのインター ンを経て、2025年からグリーホールディングスで勤 務。 グリーエックス株式会社 エンジニア 2
3. 目次・アジェンダ • LSM Tree の概要 • LSM Tree のコンポーネント ◦ MemTable ◦ WAL (Write-Ahead Log) ◦ SSTable (Sorted String Table) ◦ インデックス (Bloom filter) ◦ コンパクション • まとめ 3
4. LSM Tree の概要 4
5. LSM Tree (Log-Structured Merge Tree) • 概要 ◦ 書き込み処理を重視したデータ構造 ◦ 大規模データベースやキーバリューストアで使われる ◦ Bigtable, RocksDB, LevelDB などで採用されている • 特徴 ◦ 書き込みは高速 ▪ シーケンシャル書き込み中心 ▪ メモリ上にデータを集約 (Memtable) して一定サイズでディスクにフラッシュ ◦ 読み込みは複雑 ▪ 複数階層のSSTableを探索する必要がある ▪ Bloomフィルタやキャッシュで高速化 5
6. SSTable SSTable LSM Tree フローイメージ 6 Memtable 読み取り処理 書き込み処理 WAL SSTable Memtable SSTable Bloomフィルタ コンパクション • データの操作が発生すると Memtable (バッファ) に記載 • Memtableのサイズが閾値を超え るとSSTableにフラッシュされる • SSTableは読み込み専用で追記の み行われる • WALは障害時のリカバリー用の データ • 読み取り時は複数階層のSSTable を閲覧する必要がある
7. LSM Tree のコンポーネント 7
8. Memtable • データ操作が発生すると Memtableに記載する • メモリ上にソートされて格納 • (key, value) 形式のデータ • 検索のために索引が利用される (B木 など) 8 Key Value Entry Type Timestamp apple 100 PUT 2025-10-02 01:35:20 banana 120 PUT 2025-10-02 01:40:24 peach null DELETE 2025-10-02 01:35:57 orange 80 PUT 2025-10-02 06:00:28 Memtable データ例
9. Memtable 実装例 9 Entryの構造 Memtableの構造 Memtableへの追加処理
10. SSTable (Sorted String Table) • 読み取り専用のディスク上のテー ブル • Memtableのサイズが大きくなる とSSTableにフラッシュされる • SSTableはシーケンシャルに生成 • データを読み取る際は複数の SSTableを閲覧して、timestamp が新しいデータを取得する 10 Key Value Entry Type Timestamp apple 100 PUT 2025-10-02 01:35:20 banana 120 PUT 2025-10-02 01:40:24 peach null DELETE 2025-10-02 01:35:57 orange 80 PUT 2025-10-02 06:00:28 SSTable データ例 SSTable
11. SSTable 実装例 11 SSTableの構造 SSTableの作成タイミング SSTable生成
12. その他のコンポーネント • コンパクション ◦ SSTableのファイル数・サイズを減ら す処理 • Bloomフィルタ ◦ データを探す際にあるSSTableに存在 しないことを判定できる ◦ 読み取り性能の向上 • WAL (Write-Ahead Log) ◦ Memtableに書き込む前にWALにデー タを書き込む ◦ 耐障害性・順序保証 12 コンパクション イメージ SSTable1 SSTable2 SSTable1’
13. まとめ 13
14. まとめ • LSM Tree 概要 ◦ 書き込み処理を重視したデータ構造 ◦ Bigtable, RocksDB, LevelDB などで採用されている ◦ 書き込みは高速 ▪ シーケンシャル書き込み中心 • コンポーネント ◦ Memtable: メモリ上にソートしてデータを格納。 ◦ SSTable: 読み取り専用のソート済みデータ。Memtableのサイズが大きくなると生成。 ◦ WAL: Memtableに書き込み前に書き込む。耐障害性が高まる。 ◦ コンパクション: SSTableの数が増えたときなどに数やサイズを減らす処理 ◦ Bloomフィルタ: 該当のSSTableに探しているデータがないことを保証するフィルタ 14
15. ご清聴ありがとうございました 15