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

自作 LSM Tree で学ぶストレージエンジンのしくみグリーエックス株式会社エンジニア高田倫太朗

高田倫太朗 2025年にグリーホールディングスに新卒入社。現在、広告事業のサーバーサイドエンジニアとして、 Golang, k8s等を用いて開発業務を行っている。大学で、機械学習、信号処理を専攻。受託開発企業、スタートアップ企業などでのインターンを経て、2025年からグリーホールディングスで勤務。
グリーエックス株式会社エンジニア 2

目次・アジェンダ • LSM Tree の概要 • LSM Tree のコンポーネント ◦
MemTable ◦ WAL (Write-Ahead Log) ◦ SSTable (Sorted String Table) ◦ インデックス (Bloom ﬁlter) ◦ コンパクション • まとめ 3

LSM Tree の概要 4

LSM Tree (Log-Structured Merge Tree) • 概要 ◦ 書き込み処理を重視したデータ構造 ◦
大規模データベースやキーバリューストアで使われる ◦ Bigtable, RocksDB, LevelDB などで採用されている • 特徴 ◦ 書き込みは高速 ▪ シーケンシャル書き込み中心 ▪ メモリ上にデータを集約 (Memtable) して一定サイズでディスクにフラッシュ ◦ 読み込みは複雑 ▪ 複数階層のSSTableを探索する必要がある ▪ Bloomフィルタやキャッシュで高速化 5

SSTable SSTable LSM Tree フローイメージ 6 Memtable 読み取り処理書き込み処理 WAL
SSTable Memtable SSTable Bloomフィルタコンパクション • データの操作が発生すると Memtable (バッファ) に記載 • Memtableのサイズが閾値を超えるとSSTableにフラッシュされる • SSTableは読み込み専用で追記のみ行われる • WALは障害時のリカバリー用のデータ • 読み取り時は複数階層のSSTable を閲覧する必要がある

LSM Tree のコンポーネント 7

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 データ例

Memtable 実装例 9 Entryの構造 Memtableの構造 Memtableへの追加処理

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

SSTable 実装例 11 SSTableの構造 SSTableの作成タイミング SSTable生成

その他のコンポーネント • コンパクション ◦ SSTableのファイル数・サイズを減らす処理 • Bloomフィルタ ◦ データを探す際にあるSSTableに存在
しないことを判定できる ◦ 読み取り性能の向上 • WAL (Write-Ahead Log) ◦ Memtableに書き込む前にWALにデータを書き込む ◦ 耐障害性・順序保証 12 コンパクションイメージ SSTable1 SSTable2 SSTable1’

まとめ 13

まとめ • LSM Tree 概要 ◦ 書き込み処理を重視したデータ構造 ◦ Bigtable, RocksDB,
LevelDB などで採用されている ◦ 書き込みは高速 ▪ シーケンシャル書き込み中心 • コンポーネント ◦ Memtable: メモリ上にソートしてデータを格納。 ◦ SSTable: 読み取り専用のソート済みデータ。Memtableのサイズが大きくなると生成。 ◦ WAL: Memtableに書き込み前に書き込む。耐障害性が高まる。 ◦ コンパクション: SSTableの数が増えたときなどに数やサイズを減らす処理 ◦ Bloomフィルタ: 該当のSSTableに探しているデータがないことを保証するフィルタ 14

ご清聴ありがとうございました 15

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

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

gree_tech PRO

More Decks by gree_tech

Other Decks in Technology

Featured

Transcript