Bigtable論文から学ぶシンプルなデザイン

Transcript

1. Bigtable論文から学ぶ シンプルなデザイン プレシカナイト 2026/02/04
2. かたやん 株式会社AJA DSP Division • Golang / GoogleCloud / Kubernetes • 24新卒バックエンドエンジニア • ダイレクト広告 daisuke0x17 wwktyn Profile 2
3. 1. 背景 2. データ構造 3. アーキテクチャ 4. 読み書きの仕組み 5. まとめ 背景 1
4. Googleが抱えていた課題 • 商用 DB の限界 ◦ コストとスケーラビリティ 4 • 爆発的なデータ量 ◦ Webインデックス ◦ 衛星画像 • 多様なワークロード ◦ バッチ処理（スループット） ◦ リアルタイム配信（低レイテンシ） → わいらが作るやで💪
6. Bigtable 誕生 • Not a RDB • 分散ストレージ • 疎で分散された、永続的な多次元ソート済みマップ ◦ Sparse, Distributed, Persistent, Multi-dimensional Sorted Map → どういうこと🤔 6
7. データ構造 2 1. 背景 2. データ構造 3. アーキテクチャ 4. 読み書きの仕組み 5. まとめ
8. データモデル構造 • Row Key ◦ 任意の文字列 ◦ 行単位のアクセスはAtomic • Column Key ◦ “family: qualifier” の形式 ◦ family: 事前定義 ◦ qualifier: 動的に追加可能 • Timestamp ◦ バージョン管理に利用 → 多次元マップ 8
9. • 辞書順ソート ◦ データは RowKey の辞書順に保存 • 局所性 ◦ 関連するデータが物理的に近くに保存 • Tablet ◦ 行の範囲ごとにデータを分割した単位 • 分散の単位 ◦ Tablet が分散と負荷分散の基本単位 → 疎で分散された、多次元ソート済みマップ RowとTablet 9
10. • Column Family ◦ 列の集合 ◦ アクセス制御や圧縮の単位 • タイムスタンプ ◦ 各セルは複数のバージョンを持てる ◦ 64bit 整数 • ガベージコレクション ◦ 古いバージョンを自動的に削除する設定が可能 Column Familyとタイムスタンプ 10
11. 具体例：Webtable 11 • Reversed URLでドメインごとの局所性を確保
12. アーキテクチャ 3 1. 背景 2. データ構造 3. アーキテクチャ 4. 読み書きの仕組み 5. まとめ
13. アーキテクチャの構成要素 13 • GFS（Google File System） ◦ ログファイルとデータファイルの保存に使用 • Chubby（分散ロックサービス） ◦ Master の選出 ◦ Tablet Server の生存確認 ◦ スキーマ情報の保存 • SSTable（Google SSTable file format） ◦ 内部で使用される Immutable な ファイルフォーマット 疎で分散された、永続的な多次元ソート済みマップ
14. クラスタの全体像 14 • Master Server ◦ 1台のみ ◦ Tablet の割り当て、負荷分散を担当 ◦ データは扱わない • Tablet Server ◦ 多数存在 ◦ データの読み書きを担当 • Client ◦ データの読み書きは Master を経由せず 直接 Tablet Server と通信
15. 読み書きの仕組み 4 1. 背景 2. データ構造 3. アーキテクチャ 4. 読み書きの仕組み 5. まとめ
16. 復習：Tablet とは 16 データは Row Key の範囲ごとに「Tablet」という単位で分割される • 1つの Tablet = 100〜200MB 程度 • 各 Tablet は1台の Tablet Server が担当 • データ量が増えると自動で分割（Split）
17. 3層の階層構造 17 問題：数千〜数万の Tablet があるとき、どうやって目的の Tablet を見つける？ → 3 階層で管理 • Root Tablet：METADATA Tablet の場所を保存（目次） ◦ ※ 絶対に分割されない • METADATA：User Tablet の場所を保存（索引） • User Tablet：実データ
18. 読み込みの仕組み 18 Client は最大3回の問い合わせでデータに到達 1. Chubby に聞く→ Root Tablet の場所を取得 2. Root Tablet に聞く → 該当範囲の METADATA Tablet の場所を取得 3. METADATA Tablet に聞く → 目的の User Tablet の場所を取得 4. User Tablet に直接アクセス → データ取得 ※ 結果はキャッシュされ、次回以降は ④ のみ
19. 書き込みの仕組み 19 1. CommitLog ◦ ディスク（GFS）上のログに書き込み 2. Memtable ◦ メモリ上のソートされたバッファに書き込み 3. SSTable ◦ Memtable がいっぱいになると 不変の SStable ファイルとして書き出し
20. Appendix：Compaction 20 • Minor Compaction ◦ Memtable を SSTable に変換して保存 • Merging Compaction ◦ 複数の SSTable と Memtable をマージ • Major Compaction ◦ 全 SSTable を1つに統合 ◦ 削除済みデータを物理的に消去 ◦ リソース回収
21. まとめ 5 1. 背景 2. データ構造 3. アーキテクチャ 4. 読み書きの仕組み 5. まとめ
22. まとめ 22 • Simple designs are valuable ◦ 単一行のみアトミック（複雑なトランザクションなし） ◦ Master はメタデータ管理のみ（データパスから除外） ◦ SSTable は Immutable（並行制御がシンプルに） ◦ 階層は常に3層（探索コストが予測可能） 参考：https://cloud.google.com/blog/ja/products/gcp/google-technology-through-published-papers-part3 Chang, Fay, et al. "Bigtable: A distributed storage system for structured data." ACM Transactions on Computer Systems (TOCS) 26.2 (2008): 1-26.