B3データ構造の重要性
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。イギリスのロンドンからお届けしています。Ken Wakatsumaです。
本日は、London Tech Talk第四弾目となる【Bookclub データベース・インターナルズ】の振り返りを収録していきます。今回は、Chapter 6、B3 Variantsについて振り返っていきます。
今回のショーの目玉は、B3の深い世界に潜り込んでいくということですね。今までは、データベースでよく使われるB3と呼ばれるデータ構造、の基構造について詳細に観測してきました。
今までのChapterでは、B3の基本を学んだり、DBMSでよく使われるB3は、実はそのASHの一つであるB++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
たくさん 生え て いる まあ ビーツリー の
そうですね 原生 林 と いい ます か ビーツリーフォレスト に まさに 入っ て いく よう な イメージ か な と 思っ て ます
実際 の 木 に も です ね 針葉樹 と か 紅葉樹 と いう か
いろいろ な 大まかな 分類 が あり ます けれど も 今回 は
ビーツリー と いう 木 の 多種 多様 な 側面 を まるで 植物学者 に なっ た つもり で
ビーツリーフォレスト に 一緒 に 分け入っ て いき ましょう
はい そこ で 今回 の 章 の 読む 目的 と し て は こちら です ね
なぜ データ ベース の 開発 に おい て
B プラス 3 だけ で は 不十分 だっ た の か
と いう ところ を 理解 できれ ば 本章 を 読む ゴール を 達成 でき た の で は ない か と 思い ます
B プラス 3 の 勉強 チャプター 4 で も し て き まし た けれど も なぜ B プラス 3 以外 の
アシュを 発明 する 必要 が あっ た の か と いう ところ です ね
まあ 例えば
ちょっと し た アナロジー で 紹介 し ます けれど も
植物 と か 野菜 果物 食べ物 の 世界 で も
もともと 地球 上 に 存在 し た の 原 に 入っ て いっ た よう な 小麦 と か お米 の 原種 だけ で は
増加 する 人口 に 対し て 十分 な 供給 が でき ない と いう こと で
人類 は 品種 改良 と いう 技 を 覚え て
長年 の 年月 を かけ て 原種 を 改良 し て き まし た よ ね
B プラス 3 の 世界 も 同様 か な と 思っ て い ます
変わり ゆく ビジネス の 要件 と か
進化 する ハードウェア に
まるで 足並み を 揃える か の よう に 品種 改良 し て くる 必要 が あっ た の で は ない か な と 僕 は
考え て い ます
本来 の B 3 そして その 3 年 後 に 発表 さ れ た B プラス 3 が もともと 何 を 解決 しよう と し
て い た の か と いう と これ は 振り返り に なり ます けれど も
ハードディスク の よう な
シークエンシャル な 書き込み と 読み込み を する ディスク から
データ ブロック を 読み込む 時 に いかに ディスク IO を 抑える か と いう こと でし た よ ね
ディスク IO を 抑える こと に よっ て パフォーマンス が 出 ます と
で も
それ だけ で は 不十分 な ケース が やっぱり 出 て き て しまう と
例えば 書き込み の ワークロード が 極端 な ケース で は どう する ん だ で あっ たり
メモリ 制限 が 厳しい 環境 で は どう する ん だ で あっ たり
いろんな 環境 が ある の で その 環境 に 合わせ た 適切 な B3 を 使う 必要 が あり まし た
例えば コンカレッション を 最適化 し た よう な アプリケーション の プロセス モデル で は どの よう な
B3 の アシュ が 最適 な の か と いう よう に いろいろ な 要件 が あり まし た の で
それぞれ の 要件 に 応じ て 品種 改良 を する 必要 が あっ た の で は ない か と 思い ます
そう いっ た その 品種 改良 さ れ た
一 つ を 学ん で いく と いう の が 本 書 の 目的 に なっ て い ます
B3の課題
はい それ で は 簡単 に 内容 を 振り返っ て いこう と 思い ます はい じゃあ まず
ちょっと B3 自体 の 簡単 の おさらい を しよう と 思い ます チャプター 4 を 覚え て いる 方 は
振り返り に なる か な と 思い ます
まず B3 と いう の は すごい 基本 から いき ます ね
前回 の 振り返り 収録 から 間 が 空い て しまっ た の で
B3 と いう の は
データ 構造 の 一 つ でし た ね
1970 年 代 から 研究 論文 が 盛ん に 発表 さ れ た B3 です けれど も
なぜ B3 が 必要 だっ た か と いう と
ハード ディスク HD の よう な シークエンシャル な 読み込み を する ディスク で も
効率 的 に データ を 管理 する ため の データ を 保存 しる 手法 と し て
適切 な データ 構造 し て B3 が 適し て いる と いう こと でし た
具体 的 な キーワード と し て は ハイ ファン アウト で ローハイト な B3 が 適し て いる と いう こと でし た ね
その 中 で も 特に
1973 年 に 論文 が 発表 さ れ た B プラス 3 と いう 種類 が 一番 メジャー でし て
B プラス 3 は どう いう こと か と いう と 実際 の データ ブロック と いう の を
機構 像 で 見 た 時 の リーフ ノード と 呼ば れる 一番 最下位 の ノード に のみ 格納 し
ルート ノード 根っこの ノード です ね それ から 中間 ノード
リーフ ノード に 至る まで の 間 の ノード と いう の は
この ノード へ の ポインター を 格納 する 形 を 取っ て い ます はい
さて
この B3 B プラス 3 に も
課題 が あり まし た
B3 と いう の は 効率 的 な データ の ルックアップ データ を 探す ため に です ね 常 に
バランス さ れ た 機構 像 で ある 必要 が あり まし た
バランス さ れ た と いう の は
すべて の ノード の 高 さ が 揃っ て いる と いう 状況 です ね
逆 に 言う と バランス さ れ て い ない 状況 と いう の は 例えば 機構 像 を 想像 し た 時 に
左側 の 木 は 高 さ が 3 つ の に 右側 の 木 は 高 さ が 4 つ と か 5 つ に なっ て しまう
これ は 右側 の 方 の
枝 が 長く なっ て いる 状況 です よ ね これ は バランス さ れ て い ない 状況 でし た
B3 と か B プラス 3 は データ を アペンド し たり 削除 する 度 に
その 枝 葉 が 伸び たり 枯ら れ たり し ます と もし その 時 に
バランス さ れ て ない 状態 に あっ たら ノード スプリット と か ノード マージュ と いう 操作 を 通し て
新しい 書き込み が ある 度 に 常 に 機構 像 を バランス さ れ た 状態 に 維持 する 必要 が あり まし た
これ が すごい ポイント です ね と いう の も 問題 の 根っこ は ここ から 来 て い ます
ノード スプリット と か ノード マージュ を し て いる 間 は 基本 的 に 機構 像 は 使え ない 状態 に なり ます から
ランダム な 書き込み が 多い 状況 多い よう な 環境 多い よう な ビジネス アプリケーション で は
書き込み の ボトルネック に すぐ 当たる こと に なり ます
イメージ し て 欲しい ん です けれど も 常 に データ が
フリー クエント に 書き込み さ れ たり 削除 さ れ たり する 時 に は 常 に こう バランス さ れ た 状態 に 保た なきゃ いけ ない の で
ノード スプリット と か ノード バージョン が 頻発 し て 怒っ て しまう と
な の で 常 に 機構 像 が ダイナミック に 動い て いる よう な 状況 です ね
こう し た ページ の リライト に よる 書き込み が 増幅 する 現象 を
新しい キーワード と し て は ライト アンプリ フィケーション 書き込み が 増幅 する と いう 現象 だ と 呼ば れ て い まし た
はい また b 3 で は もう 一 つ 問題 が あり まし た ね
ランダム な 書き込み データ の 書き込み が 行わ れる たび に
ノード の スプリット と か ノード マージョン を し て い たら キリ が ない の で
それぞれ の ノード に は です ね その 中間 ノード で リーフ ノード ある 程度 の
空き 要領 を バッファー と し て 取っ て おく と いう の が ポイント でし た
これ は 逆 に 言う と です ね 使う か どう か わから ない の に
ディスク 領域 を 常 に 確保 し て おか なく ちゃ いけ ない と いう まあ データ 構造 が 本質 的 に 抱える
欠点 と いう の も あり まし た これ は スペース アンプリ フィケーション と いう 問題 で も 呼ば れ て い まし た ね
はい と いう こと で この b 3 の 基本 的 な 課題
ライト アンプリ フィケーション と スペース アンプリ フィケーション と いう の が あっ た と いう こと です ね はい
B3の解決策
なので この 章 で 紹介 さ れ て いる b 3 の アッシュ と いう の は これ ら の 課題 を
なん と か し て 克服 しよう と し て いる もの に なっ て い ます と
で 本 章 で 紹介 さ れ て いる b 3 を 一 つ 一 つ ね あの 詳細 に
やっ て い たら まあ 本 章 の 丸写し に なっ て しまう の で
ちょっと ピック アップ し て いく つ か 紹介 し て いこう か なぁ と 思い ます はい
で は まず
ライト アンプリ フィケーション 書き込み の 増幅 の 場合 に つい て 見 て いき ましょう
ランダム な 書き込み が ある ため に です ね
素直 に b 3 を 都度 更新 し て い たら
書き込み が フリークエント な 環境 で は b 3 が 常に 更新 さ れ て いる こと に なる の で そこ が ボトルネックになる
ボトルネック に なる と いう 話 でし た ね
で は
それ を どう やっ て 解決 する の か
じゃあ ちょっと スモール クエスチョン です けど リスナー の 皆 さん だっ たら その よう な 状況 で
どう し たら 解決 できる と 思い ます か ね
書き込み が 例えば 毎 秒 当たり 100 件 発生 する と し ます よ ね
その 都度 b 3 を 最悪 の ケース へ バランス さ せ なきゃ いけ ない と する と
秒間 当たり
バッファリングの基本
最悪 の ケース で 100 回 の ノード マージ もしく は ノード スプリット が 起き て しまう 可能 性 が あり ます と
それ は 避け たい
では どう する か
まず 思い つく の は 書き込み を まとめ て しまえ と いう 発想 です ね
要 する に バッファリング と 呼ば れる テクニック です
秒間 当たり に 100 件 起こる と する なら ば 例えば
100 件 書き込み が 溜まっ た タイミング で その 100 件 を 一 つ の バッチ と し て 扱い ツリー を 更新 する
それ なら 毎 秒 当たり ツリー を 更新 すれ ば 良く なり ます よ ね 更新 回数 が 100 回 から 1 回 200 分 の 1 に
減る
これ を この アイデア を 素直 に 実現 し た と し て 紹介 さ れる の が
ワイヤード タイガー と 呼ば れる 実装 で これ は mongodb の ストレージ エンジン と し て も 使わ れ て います
で この b 3 の 各 ノード に です ね この ワイヤード タイガー どの よう に バッファリング を 実装 し て いる か と いう 話 を し ます か
b 3 の 機構 像 を イメージ し て ください ルート ノード が あっ て
そこ から 中間 ノード が 伸び て 一番 下 に リーフ ノード が あり まし た よ ね
ワイヤード タイガー の 場合 は その 各 ノード に
アップデート バッファー と 呼ば れる リスト を ノード の 脇っちょ に 置い て おき ます と
で まぁ ちょっと また 僕 の 好き な アナロジー で 考え て みよう と 思い ます
はい で は ちょっと です ね 週末 の 朝 に
オフィス の 中 で 書類 を 整理 し て いる と いう シチュエーション で 考え て み て ください
はい じゃあ オフィス の 本壇 の 中 に は です ね 大きな バインダー と あと
今週 溜まっ た 届い た 開封 中 の 手紙 が たくさん ある と し ます ね
で 今 やっ て いる こと と し て は その 開封 中 の 手紙 を
バインダー の 中 の 適切 な 場所 に 一 つ 一 つ 閉じ て いく と いう ところ です
で まあ バインダー が B3 で 今朝 届い た 開封 中 の 手紙 が 書き込み だ と し ます ね
で それ を です ね アップデート バッファー に 入れる と いう こと は 手書き
手紙 を です ね 一 つ 一 つ 開封 し て
バインダー に 閉じ て い たら 効率 が 悪い の で まず は
手紙 を 一気 に 開け て しまえ と 手紙 を 一気 に 開け て 机 の 上 に ある アップデート バッファー に
並び直し て から
バインダー に 正しい 順番 で 一気 に 閉じ て いく と いう イメージ です ね
まあ これ が 素直 に 考え た 時 の バッファリング の アナロジー の イメージ に なり ます はい
さて
データ構造の最適化
で この 素直 に アップデート バッファー の 実装 し た
と し て も これ は これ で ちょっと まだまだ
改善 の 内 が あり ます と
これ の 問題 は 何 か と いう と です ね 読み込み です ね
アップデート バッファー に まだ 書き込み が ある と いう こと は
ツリー の 状態 は 最新 で は ない と いう こと です ね
な の で データ を 読み込む 時 に は
アップデート バッファー に まだ 開封 中 の 手紙 が ある か どう か を 確認 し なく て は いけ ませ ん
まだ 処理 が 終わっ て ない 状態 の こと を ダーティ ページズ
まあ えっと 汚れ て いる ページズ と 呼ぶ ん です けれど も
まさに この アナロジー で 言う と こう しっちゃかめっちゃか 手紙 が アップデート バッファー に ある よう な 状況 です よ ね
ダーティ ページズ の 場合 は です ね ツリー の 状態 と この アップデート バッファー の 状態 を ガッチャンコ と 合わせ て
返し て あげる 必要 が あり ます
です ね ツリー に ある
状態 と アップデート バッファー に ある 中途半端 の 状態 それ を 二 つ 合わせ ない と
最終 的 に 見せる べき 理由 が 表現 でき ない と いう ところ です よ ね
さっき の アナロジー で 考え て みる と 例えば こう バインダー に 整理 しよう と 思っ て
朝 1 番 に 手紙 を 開封 し て いる 間 に
同僚 から 電話 が かかっ て き て バインダー の 内容 に つい て 問い合わせ が あっ た と し ましょう
例えば
そうですね その バインダー に は 自分 が 経営 し て いる 会社 の 会計 情報 に つい て の 情報 が 記録
さ れ て いる と し ます
そこ から 必要 な 情報 を 抜き取っ て 答え て あげ たい わけ です ね 同僚 は ちょっと 先月 の 決算 に つい て
尋ね て き まし た と で も もし 今朝 届い た 手紙 の 中 に
先月 の クレジット カード の ステートメント と か
入金 や 出勤 の 情報 が あっ た と する と
バインダー の 情報 だけ で 答え て しまう と 最新 の 情報 を 押さえ
押さえ て ない ちょっと 古い データ に なっ て しまい ます よ ね だ から
同僚 の 電話 に 答える ため に は バインダー の 情報 と
アップデート バッファー つまり その
手紙 の 机 の 上 に まだ しっちゃかめっちゃか に なっ て いる 今朝 届い た 手紙 の 情報 を どっち も 理解 し て
マージ し て 最適 な 答え を 返し て あげる 必要 が あり ます
な の で この アップデート バッファー を 使っ た 実装 の 時 は 読み込み の 時 に
この マージ 作業 が 発生 する よう に なっ て い ます
そして この
アップデート バッファー を ノード ごと に 持つ と いう 設計 の もう 一 つ の 問題 は です ね
アップデート バッファー が ノードごとに たくさん あり すぎる と 読み込み の 際 に やる こと が 多く なっ て 結局
パフォーマンス が 上がっ て いる の と いう 話 に なり ます よ ね まあ ここ も その 最適 な
あの データ 構図 と いう の は 読み込み が 多い の か と か 書き込み が 多い の か と か
読み込み 書き込み が 多い 少ない に し て も どれ ぐらい の 頻度 で どれ ぐらい の 大きさ の データ を 取る の か に よっ て
もう 本当 に 変わっ て くる の で
ワイヤード タイガー の よう な データ を アップデート バッファー を ノード ごと に
置く って いう シンプル な その ビーツリー を ちょっと 変え た 別 の 形 も あり ます で これ が
ちょっと し た 最適 化 を 加え た の が
新しい ツリー です ね レイジー アダプティブ トリー
レイジー アダプティブ トリー と 呼ば れる 別 の ツリー 構造 に なっ て ます
で この アップデート バッファー を 置く と いう 発想 と し て は 同じ な ん です けれど も じゃあ ワイヤード タイガー の 実装 と この レイジー アダプティブ トリー の 違い は 何か と いう と
ここ です ね ノード ごと に アップデート バッファー を 用意 する の で は なく て
いく つ か の サブ ツリー ごと に アップデート バッファー を 用意 する と いう の が 違い ます
わかり ます か ね その
ツリー 全体 の 構造 が あっ た 時 ノード 一 つ 一 つ に アップデート バッファー を 置く ん じゃ なく て
いく つ か の サブ ツリー ごと に 分解 し て ちょっと 大きな グルーピング に し て アップデート バッファー を それぞれ 用意 する と いう こと に なっ て い ます
ちょっと さっき の
さっき の アナロジー を 拡張 し て 考え て み たい か なぁ と 思い ます
例えば ワイヤード 大会 だっ たら
バインダー ごと に アップデート バッファー みたい な こう
百均 と か 大層 で 買っ た トレイ を 準備 し て おく よう な イメージ です ね
まあ アイキア と か で も 買っ た バインダー に その トレイ を 一 つ 一 つ 並べる と いう 感じ です
で も バインダー は 例えば じゃあ 本棚 に 100 個 ぐらい 並べ て いる と し ましょう
バインダー に も いろんな 種類 が あり ます
会社 の 会計 に つい て まとめ た バインダー 群 も あれ ば
会社 の HR 情報 人事 情報 に つい て まとめ た バインダー も ある と し ます よ ね
そう する と レイジー アダプティブ ツリー で は その
バインダー の サブ ツリー ごと に アップデート バッファー を 持っ て おく イメージ です
手紙 を 開封 する 時 に です ね 例えば これ は クレジット カード の ステートメント だ から 会社 の 会計 に つい て の
情報 だ な と いう 時 は その 情報 を 持っ て いる バインダー の 近く に
つまり その アップデート バッファー に 置く と いう ところ です ね
で 一方 例えば 誰 か の 退職 届け が 来 てる な と いう 時 は
会社 の 人事 情報 に つい て の ドキュメント は その 近く の バインダー つまり その サブ ツリー の アップデート
バッファー に 置く と いう イメージ に なっ て い ます
これ に よっ て その アップデート バッファー と いう 中間 データ を 置く こと に よっ て 生じ た デメリット で ある
その コンピュテーショナル コスト を
完璧 に は 解決 でき ない ん です けど 少し で も 軽減 しよう と いう 形 です ね
バッファリング の 単位 を さらに バッチング し て いる みたい な 感じ に なっ て い ます はい
と いう こと で ワイヤード タイガー と レイジー アダプティブ ツリー の
実装 を ちょっと 簡単 に 紹介 し て き まし た が いかが でしょう か
次の課題への移行
書き込み 内容 を ですね バッファリング する こと に よっ て これ ら の ツリー が
パフォーマンス を 上げよう と し て いる 努力 が 見え まし た と
バインダー の アナロジー も 紹介 し ながら 話し て み た ん です けれど も リスナー の 皆 さん 少し は
イメージ でき まし た でしょう か
はい じゃあ さて
次 は です ね 少し バッファリング から 離れ て みよう と 思い ます
冒頭 で は B3 に メジャー な 問題 が 2 つ ある と いう 話 を し まし た ね 1 つ が
Right Amplification
で これ は バッファリング に よっ て 解決 さ れ て いる と いう 話 を し まし た
もう 一 つ の 課題 皆 さん 覚え て い ます でしょう か
Right Amplification の もう 一 つ の 課題 は
Space Amplification でし た ね で 実 は バッファリング する こと に よっ て Space Amplification も まぁ 結果 と し て ある 程度 解決 できる ん です ね
Space Amplification の 問題 と いう の が
バッファリングとFDツリー
書き込み を する ため に
いつ 書き込み が あっ て も 良い よう に ある 程度 余分 な スペース を 取っ て いく 必要 が ある と いう こと でし た ね
で これ に よっ て ディスク から 読み取る する 読み取り を する ページ の 中 に ほぼ 常 に
エンプティー スペース が 存在 する こと に なる の で まぁ これ が ちょっと 無駄 な な と いう こと でし た
で 書き込み の ステップ を バッファリング に 任せる こと に よっ て 結果 と し て
Space Amplification を 軽減 さ せる こと が できる と いう ロジック の 流れ に なっ て い まし た
はい ちょっと ここ で えっと 一 休憩 入れ つつ
さて レイジー ツリー の 次 は です ね また 別 の 機構 像 を 見 て いこう か なぁ と 思い ます
で また 戻っ て この バッファリング の 議論 を もう 少し 進め て み ましょう
レイジー B ツリー の アイデア は ノード ごと もしくは
サブ ツリー ごと に 書き込み 処理 を まとめる と いう もの でし た ね
じゃあ この バッファリング の スコープ を もう ちょっと 変え て もう ちょっと 広げ て み ましょう
サブ ツリー ごと で は なく て
そもそも ツリー 全体 へ の 書き込み を 1 箇所 で バッファリング し て み て は どう でしょう
実 は これ が 次 に 紹介 する フラッシュ ディスク ツリー FD ツリー と 呼ば れる ツリー の 発想 の 厳選 と なっ て い ます
また 実 は この アイデア は 次回 の チャプター 7 で 紹介 する 予定 の LSM ツリー
ログ ストラクチャー マーゼ ツリー の
アイデア と も 似 て い て 実 は その LSM ツリー と いう の は この FD ツリー に インスパイア さ れ た もの です
この FD ツリー と いう の です ね
結構 割と 古く て 記憶 が 正しけれ ば
1970 年代 中盤 か 後半 に 論文 が 発表 さ れ て い ます
で 名前 も まあ フラッシュ ディスク と あり ます から ちょっと 年代 を 感じ ます よ ね で
FD ツリー の 肝 と し て は
なん と 言っ て も その 書き込み の バッファー みたい な 領域 に 置く データ レコード です ね
イミュー タブル
な もの と し て 扱う と いう こと です はい 出てき まし た イミュー タブル つまり その 変更 でき ない
変更 不 可能 な データ レコード と し て 扱う
で それ を 相当 さ れ た 順序 で 管理 し て いく
そして 必要 な タイミング で その 反映 結果 を
ミュー タブル な ツリー 構造 に 反映 さ せ て いく と いう この 日本 仕立て に なっ て ます
わかり ます か ね ちょっと あの もう 1 回 繰り返し ます ね その それぞれ の 書き込み の データ レコード って いう の は
変更 不 可能 な イミュー タブル な もの でし た で それ を 相当 さ れ た 順序 で 管理 し て いく と
それ を 必要 な タイミング で
ミュー タブル まあ その ツリー 構造 自体 は ダイナミック に 変わっ て いく の で その ツリー 構造 に
反映 さ せ て いく と いう こと です ね はい
もし 現 時点 で すでに リスナー の 方 で です ね lsm ツリー を ご 存知 の 方 が いれ ば
親近 感 の ある アーキテクチャ だ と 思い ます よ ね
そう あの ss テーブル ソーティット スティング テーブル と メモ テーブル に よる アーキテクチャ と 実 は そっくり そのまま な ん です ね
まあ fd 3 の 場合 は ソーティット ランズ と 呼ば れる
ソーティット フラン イミュー タブル な データ レコード の リスト です ね これ が アペンド オン リー
要する に 書き込み あの お尻 に どんどん どんどん データ コード を
追加 し て いく だけ の アペンド 追記 し て いく だけ の データ 構造 です
b3ツリーの課題
はい で この fd 3 の この 発想 は
何 が 画期 的 な の か
これ を ちょっと あの 語っ て み たい ん です けれど も 少し
オリジナル の b 3 に 戻っ て み ましょう
b 3 の 場合 に
書き込み が あっ た 場合
それ を どこ に 書き込む の か と いう もの を まず は 探す 必要 が あり まし た
な の で こう ランダム の 書き込み に 弱い と 言わ れる の は その ルック アップ の コンピューター し
なる コスト も かかる ん です よ ね 実 は これ が 結構 コスト で
やっぱり その
アペンド オン リー な 場所 を 使う と いう こと は 書き込み が ある ため に まあ まず その ただ ただ 一方 的 に
どんどん どんどん スタック し て いけ ば いい だけ な の で
一方 的 に 追記 し て いく だけ の データ 構造 を 使え ば 実 は 書き込み の ため に
書き込み の ターゲット を 見つける 処理 が 必要 ない ん です ね
で free 3 の さらなる 実装 の 詳細 に つい た 実 は 僕 も
完璧 に キャッチ アップ でき た と いう わけ で は ない の で
例えば その キーワード と し て は 本 書 で は
ファクショナル カスケーリング
ファクショナル カスケーリング と 呼ば れる テクニック と か
あとはロガリズミックランツ
これ も どちら も その ペーパー に 書か れ て いる テクニック な ん です けど
まあ そう いっ た 手法 に つい て 紹介 さ れ て い ます
現 時点 で 僕 は 十分 に 理解 し た と 言え ない の で これ 以上 の 言及 を 留め ます けれど も もし
リスナー の 方 で free 3 に 興味 が ある 方 が いらっしゃい まし たら ぜひ ふかぼっ て み て ください
もし ブログ 記事 など アウトプット し た 方 が い たら ぜひ お 便り の の で 教え て ください ね
はい と いう こと で じゃあ その fd 釣り あの lsm 釣り の
あの インスピレーション の 厳正 と もらっ た fd 釣り に つい て 紹介 し て いき まし た はい
まあ
b 3 の 厳正 林 b 3 フォレスト は こう なかなか 奥 が 深い と いう こと が リスナー の 皆 さん も わかっ て き た か な と 思う ん です けれど も
せっかく なので あの 本 書 で 紹介 が あっ た もう 一 つ の b 3 の 足 を 紹介 し て いこう か な と 思い ます
で そう です ね 今 まで の 議論 の 流れ と し て は
バッファリング を 中心 と し た b 3 の 足 を 紹介 し て き まし た
バッファリング に よっ て ライト アンプ リクエーション と スペース アンプ リクエーション と いう 課題 を 克服 できる と いう こと が わかり まし た ね
はい
さて
実 は b 3 の メジャー な 問題 と いう の が 実 は もう 一 つ 3 つ 目
あり まし た これ は あの 冒頭 で は はっきり と 言及 し て い なかっ た の で ここ で 初めて 出し ます が
3 つ 目 の b 3 の 課題 と いう の が これ は です ね
コンカレンシー です ね はい
コンカレンシー b 3 が バランス さ れ て いる 間 は
b 3 の 状態 は 最新 で は ない の で 例えば 書き込み が 発送 し て いる 間 に
別 の プロセス が 読み込み を し に 来 た 場合
マチ が 発生 し て しまう ん です よ ね その
ツリー 構造 が ダイナミック に 変化 し て いる 状況 に 読み込む と する と
古い 状態 を 与え て しまう 可能 性 が ある の で
書き込み が 発生 し て いる 間 は 別 の プロセス は 待っ て しまい ます
コンカレント な アクセス を 達成 する ため に は バッファリング と また 全く 別 の テクニック を 持ち入れ 必要 が ある ん です ね
Buzzword Treeの紹介
コンカレント で ある ため に は アトミック な 操作 で b 3 を ロックフリー
ロック が 必要 ない 状況 に する 必要 が ある ん です けれど も これ を 実現 し た の が
bw ツリー で バース ワールド ツリー と 呼ば れる もの です これ が なかなか 面白い ちょっと 簡単 に 紹介 し て いこう と 思い ます
バズ ワード ツリー 自体 は 結構 興味 深い アプローチ です ね ラッチ フリー な マルチ コア を 意識 し た データ 構造 でし て
2013 年 に です ね マイクロソフト の 開発 チーム から 論文 が 出さ れ て いる ん です ね
実際 の プロダクト で どこ まで 実装 が 持ち入れ られ て いる の か と いう の は ちょっと わから なかっ
た ん です けれど も もしか し たら アズール の データ ベース の プロダクト と か で も 使わ れ て いる の か な
で まあ ラッチ フリー
ちょっと 新しい キー を 出し まし た けど ラッチ フリー で ある と いう こと は どう いう こと か と いう と まあ その
2013 年 で ちょっと イメージ し て 欲しい ん です けど マルチ コア
前提 と し た プロセス と いう か まあ ハードウェア の 進化 に 伴っ て
マルチ コア を 前提 と し た 環境 で データ ベース を
パフォーマンス を 上げ つつ 動かし たい と いう 要望 が 出 て き た 時期 だっ た と 思い ます
その マルチ コア を 前提 と し た プロセス で データ ベース を 動かし た と する と やっぱり その
コア の 数 に 応じ て スケール する と いう の が
利益 が 大きい です よ ね
結局 例えば その コア の 数 を 1 個 から 4 個 4 個 から 8 個 8 個 から 16 個 に 増やし た と
し て も データ ベース の B3 の 書き込み 操作 の ところ で
ロック を 取ら なく て は いけ ない と いう なら ば
その データ ペース と いう 観点 で 言う と マルチ コア の ベネフィット を 受け られ ませ ん
なので その CPU の プロセス
数 を 増やす の で は なく 例えば メモリ を 増やす と か
まあ そう いっ た ところ で 垂直 に スケール する しか なく なっ て しまい ます よ ね
で この その フラッシュ レイヤー の 上 に あの
マッピング テーブル と いう インメモリ の マッピング を 管理 する データ 構造 を キャッシュ レイヤー と して 実装 し て いる ん です から
あの この マッピング テーブル が キー な の か な と 思っ て い ます
この Buzzword Tree が ページ の
実際 の ディスク 上 の 場所 を その キャッシュ レイヤー に ある マッピング テーブル と いう
メモリ 上 に ある その 論理 的 な データ 構造 です ね ここ に
あの キャッシュ レイヤー と いう 抽象 例 を 挟む こと で 分離 し て
マッピングテーブルの役割
この マッピング テーブル と いう の は つまり その 論理 的 な ページ の 場所 その アプリケーション に 返す 論理 的 な ページ の 場所 と
ディスク 上 の
実際 の 物理 的 な ページ の 場所 と の マッピング を 管理 し て い ます で この 抽象 例 を 挟み
こと に よっ て アプリケーション 側 と その 実際 の ディスク の その ページ の 場所 と いう の を
セパレート し てる ん です ね
これ の メリット は 何 か と いう と 書き込み に よっ て ページ を 動かさ ない と いけ ない と いう 時 で も
物理 的 に は どこ で も 書ける ところ に 置い とい て
マッピング テーブル は メモリ に あり ます から マッピング テーブル の マップ 情報 だけ 更新 すれ ば いい の で
書き込み が すなわち ライト アプリケーション に なる と いう こと で は あり ませ ん でし た つまり その 問題 が 発生
し ない わけ で は ない ん です けど この 問題 が 発生 する
バウンダリー を 作っ て い ます つまり エリア を 分離 し て いる ん です ね
はい そして その マッピング テーブル に
ページ へ の ポインター を 書き込む 際 の 相達 と いう の を キャス インスラクション
キャス CAS です ね
コンペア エンド スワップ と 呼ば れる あの アトミック な 操作 で 実装 し て いる と いう の が 肝 な の か な と 思っ て ます
アトミック で ある と いう こと か と いう と その キャス で 実行 し た 結果 の メモリ は 正しい 状態 で ある
と いう こと が cpu レベル で 保証 さ れ て いる と いう こと です ね
これ を 中心 に マッピング テーブル を 操作 する と いう こと は
マルチ コア から アクセス さ れ た と し て も
それぞれ の マッピング テーブル の 更新 は アトミック で ある と いう こと を 保証 さ れ て いる こと に なっ て ます
で この キャス 命令 自体 って いう の は まあ 補足 です けれど も
あの cpu の 特別 な メール セット の 一 つ です あの コンペア アンド スワップ
比較 し て スワップ する と いう こと の で ある メモリ の アドレス に ある 内容 を
指定 さ れ た 値 と 比較 し て もし 比較 等しけれ ば その メモリ に
別 の 値 を 格納 する
つまり コンペア し て スワップ する まあ もう その まま な ん です けど 一 連 の 操作 な ん です けど
この 一 連 の 比較 の コンペア と スワップ が
合わせ て アトミック です よ と いう こと が cpu レベル と 保証 さ れ て いる 命令 な の で
で まあ これ マルチ コア で は これ が なく て 話 に なら ない もの です よ ね
なので これ を 利用 し て この マッピング テーブル に おける 操作 を
マルチ コア の 環境 で スケール さ せる と いう 前提 を 置き つつ も アトミック な 操作 を
ギャレンティ えっと 保証 し て いる こと に よっ て データ 構造 を
もう リノベート し た と いう か 作り直し た と か もう 0 から マルチ コア 環境 に 合う よう な
ビーツリー 構造 を 作り直し た と いう ところ で なんか 結構
まあ ワクワク する 面白い あの 発想 だ な と 思っ て い ます
コピーオンライト手法とLMDB
僕 も 完全 に ちょっと あの わかりきっ て ない ところ も 多い バス ワード ツリー です し その プロダクト 環境 に おける その
普及 率 も ちょっと わかん ない ん です けど
おそらく 一番 の イノベーション ポイント と し て は cpu の 命令 セット の レベル から
マルチ コア 環境 で も パフォーマンス が 出る dbms の ため の b ツリー を 最低 技 し た と いう こと な の か も 知れ ませ ん
まあ また あの 個人 的 に 追っ て いく の で 新しい 情報 が わかり 次第
別 の 収録 と か で アップデート を 提供 し て いき たい と 思い ます
他 に も 今回 の 収録 で は ちょっと 僕 の 方 から 深掘り し ませ ん です けれど も
コピー オン ライト と 呼ば れる 手法 と それ を 利用 し た lmdb と 呼ば れる データ ベース
あと また 最近 アカデミック 界 で 研究 が 進ん で いる らしい
キャッシュ オブリビアス b ツリー と いう バリアント に つい て も 紹介 が あり まし た
興味 が ある 方 は ぜひ 本書 を 手 に 取っ て み て ください
はい と いう こと で
どう だっ た でしょう か なかなか b ツリー の 原生 林 b ツリー フォレスト 奥 が 深い かっ た ん じゃ ない か な と 思い ます
僕 も あの ね 今回 の 方 を 読み ながら ちょっと 分け 行っ て み まし た けれど も ちょっと 装備 足ら ず と いう こと で 一旦 折り返し と いう こと で
あの まあ あの 森 の 入り口 に 戻っ て き まし た けれど も
せっかく ブック クラブ で やっ て いる と いう こと で あの ブック クラブ で 盛り上がっ た 観点 も 簡単 に 紹介 しよう か な と 思い ます
今回 は です ね タイム ゾーン と し て は
ノース アメリカ と エイ パック 会 だっ た の で 僕 は 同日 参加 でき なかっ て き ませ ん でし た
はい あの 回し て くださっ た 皆 さん ありがとう ござい ます
コメント を 読む 感じ です と です ね ワイヤード 対外 の ソース コード を 読ん で み たり
あと は 外部 の ドキュメント を 参照 する 方 が 多かっ た です ね
やっぱり それぞれ の バリアンス に つい て は 最小 限 の 説明 だっ た の で
本 書 だけ で 理解 しよう と する と 難しかっ た ん じゃ ない か なぁ と 思い ます
あと は ラッチ トローク の 違い に つい て 学ん でる か と 思い まし た ね
面白い な と 思っ た の は コピー オン ライト の ところ で 出 て くる LMDB に つい て
レコメンデーション エンジン を 使っ て い た 時 に
作っ て い た 時 に プロダクション 環境 で 使っ た こと が ある よ と いう 方 が いた の が 結構 参考 に なり まし た ね
参加 者 の バック クラウンド が まあ いつ も 言っ て ます けど とても 多様 な の で
まさか ちょっと LMDB の 利用 者 が 今回 いる と は ちょっと 想像 座 に し て い ませ ん でし た の で すごい
面白かっ た です はい
次回のLSM3について
と いう こと で チャプター 6 の 振り返り でし た けれど も いかが だっ た でしょう か
時間 に 向け て 簡単 に 最後 に クロージング も 兼ね て 次回 の ショー を 紹介 しよう と 思い ます
次回 は いよいよ
LSM 3 に つい て 学ん で いき ます はい LSM 3 は です ね あの
まあ 最近 の モダン な
ディストリビューティッド データ ベース を 触る なら 避け て は 通れ ない 程度 コード と いう こと で
もし コンピューター サイエンス を
あの かじっ た こと が ある 人 は B3 は 聞い た こと ある か も 知れ ない ん です けど も ぜひ その
場合 は この 本 章 を ね 手 に 取り ながら この エピソード ロンド テクトク の ブック クラブ の
レコーディング と 一緒 に LSM 3 も 一緒 に 学ん で いき たい な と 思い ます
LSM 3 は
簡単 に 言う と まあ FD3 の ところ で も 触れ まし た けれど も
イミュータブル で
アペンド オンリー な ストレージ に シークエンシャル に 書き込む の で ディスク で も 書き込み が 早い と
ただ その まま だ と 読み込み が 遅い ん です けれど も
メモ テーブル と 呼ば れる もの と か ブルーム フィルター と 呼ば れる テクニック を 駆使 し て
ランダム な 読み込み も 早く し た 実装 が データ 構造 が LSM 3 に なっ て ます
メモ テーブル と か ブルーム フィルター に つい て 次 の ね あの 収録 で 一緒 に 読ん で いこう と 思い ます
実際 の プロダクト と し て も
ロックス DB と か
カサンドラ と か
コクローチ DB など 数々 の DBMS が 実装 し て い まし て まぁ BSLeader 有名 な その
リレーショナル データ ベース
マネジメント システム で も
ストレージ エンジン の 部分 を
ロックス DB に 置き換え た 実験 プロジェクト も 多数 あり ます ね
例えば MySQL でもロックス DB に ストレージ エンジン を 置き換えたマイロックス なんて 実装 が あっ たり し ます
で まぁ 最近 の データ ベース に つい て 学ん で い たら 目 に する こと も 多い LSM3 の 内容 に つい て
深掘り し て いき ます し
パート 1 の 最後 の 章 に も なっ て いる の で
一番 業務 で 役に立つ 内容 と なる ん じゃ ない でしょう か
次 も ね 難しい です けれど も リスナー の 皆 さん と
ブック クラブ の 参加 者 の 皆 さん と ぜひ 一緒 に 読ん で いき たい なぁ と 思い ます
はい と いう こと で
振り返り は 以上 に しよう と 思い ます 今回 は チャプター 6
P3 バリアンス に つい て 振り返り まし た
次 は チャプター 7 の 振り返り 収録 で お 会い し ましょう
それ で は
Have a nice day!
