00:03
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。
Londonからお届けしています、Ken Wakatomoです。
B3の基本概念
本日は、【Database Internals】 Bookclub 第2回の振り返りについて、ソロ収録で収録していこうと思います。
今回は、Chapter 2のB3 Basicsを取り上げていきます。
データベースの話をしていると、必ずと言っていいほど、B3は出てくるんじゃないかと思っています。
皆さんも、インデックスの話をしたり、データベースのパフォーマンスをチューニングしたり、オンラインの記事を見たときに、B3という話を耳にしたり聞いたことがある方は多いんじゃないでしょうか。
でも、どうしてB3というのがDBMSでそんなに使われるのか、例えば単純なバイナリーサイスリーじゃダメなのかという疑問を持った方はいるんじゃないでしょうか。
そもそも、今回データベースインターナルズで扱っているデータベースマネジメントシステムDBMSというのは、大量のデータを安価に保存しながら高速に検索であったり更新できるような仕組みが求められます。
なので、ディスクベースのDBMSの場合ですけれども、データはディスクに格納されるわけですけれども、ディスクってメモリほど早くないんですよね。
特にランダムアクセスというのはめちゃくちゃ遅い。
だからこそデータの局所性、データローカリティというんですけれどもを高めつつディスクアクセスの回数を減らすようなデータ構造が必要になるわけですね。
この要件を満たすというのがB3です。
正確にはBプラス3なんですけれども、このハイファンアウトでローハイトな構造を実現していることによってディスクのシーク回数を抑えながら、ディスクアイを抑えながら検索とか更新を効率的に行えるようになっています。
なのでこのチャプター2を読むと、どうして特にディスクベースDBMSの世界においてB3がこんなに出てくるのかというのがわかります。
そのためにはB3の基本操作、あとは基本構造についてもこの書で掘り下げられています。
例えば、検索のときにセパレーターキーズを使って効率よく目的のデータにどうやってたどり着くのかであったり、キーが送筆されていることによってレンジクエリによって必要なデータを丸と取ってくれるような仕組みであったりとか、
あとは新しいデータを追加したり削除したりするときに、B3というのはバランスの状態である必要があるんですけれども、そのバランス状態を維持するためにノードをスプリットしたりマージしたり分割したり統合したりというのも必要になってきます。
こうしたB3の基本操作というのをメンタルモデルとして理解するのが今回のショーのゴールかなと思っています。
少人数での議論
ということで、今日は本章のチャプター2、B3、Basicsの簡単な内容を振り返りつつ、どういった議論が盛り上がったかというのをお伝えしていこうかなと思います。
今回はEMEAとノースアメリカのメンバーで参加しました。
APACチームは非同期で参加するという形になりまして、今回はAPACチームが一番参加者が多いので、EMEAとノースアメリカというのが一番人数が少ない時間帯の会になるんですね。
初回はAPACとEMEAでブッククラブを行ったんですけれども、その時はすごい人数が多くて熱気にあふれているというか、初回ということもあったんですけれども、
これから難しい本を読んでいくぞみたいなすごいアップワードな雰囲気があったかなと思います。
一方、今回はすごい少人数で全員参加できて7人かな。今回はお二人参加できなかったので、5人で参加したんですけれども、少人数のブッククラブもいいですね。
なごやかなというか、一人一人がしゃべる時間というのもすごいたっぷり与えられるし、流れていく雰囲気も5時、6時ぐらいの大学の夕暮れ時の校舎でみんなでゼミみたいな感じで論文読み合っているみたいな、難しけどのどかな雰囲気みたいな感じが流れていて、
そんな雰囲気の、全然回によって雰囲気が違うんだなというのが個人的な発見で面白かったですね。なので今回は結構B3について深く議論できたかなと思います。
B3の操作と理解
今回の第2章の個人的に考えている最低限を抑えたいポイントというのがイントロでもお伝えしたんですけれども、どうしてB3が好まれるのかというのを理解できたら、この章を読んだゴール達成できたかなと思います。
そもそもやっぱりデータベースマネジメントシステムというのは大量のデータを安価に保存する必要があるので、ハードディスクとかSSDにおいていかにデータを格納しつつ早い読み書きを実現できるかというところで、まず2つ重要なキーワードがありましたね。
1つがハイファンアウトということで、これはデータローカリティーが優れているというのが1つポイントなんですね。
というのも書き込みというのはランダムに書き込まれていくので、関連性に応じて近くに保存していくということが必要です。
かつ読み書きの回数を抑えるためにディスク回数の回数も抑えていきたいので、
木構造にしたときの木の高さが例で紹介しますけど、試行実験としてこの本でも紹介されているんですけど、データをBSTで保存するか、あとはB3で保存するかというのを比べたときに、
そのバイナリーサーチツリーというのは1つのノードに対して2つのチルドレンコノードが付くんですね。
なので例えば大量のデータを保存するとなると木の高さというのがすごい高くなってしまいますと。
DBMSは木のノードごとにデータブロックとしてページとして保存するので、木の構造が高くて木を何回もたどらなきゃいけないということはそれだけディスクから読み込まなきゃいけないということなんですね。
DBMSの操作において一番遅いのはディスクからページを持ってくるところなので、基本的な発想としてはディスクの回数を抑えたい。
そのためには1つのノードに対してバイナリーサーチツリーのように2つのだけのチルドレンコノードが付くのではなくて複数のチルドレンコノードが付くようにすると木の高さというのがぎゅっと圧縮されるんですね。
これはローハイトになります。
そのローハイトを実現することによってディスクシークの回数を抑えられるようなデータ構造になるという形になっています。
なのでこのハイファンアウトというのはチルドレンコノードの数が多くてファンアウトが広がっていくということですね。
このハイファンアウトを実現するということはローハイトを実現するということと表裏一体なんですけれども、
これによってディスクフレンドリーというかディスクローカリティが優れていてディスクシークの回数を抑えられるようなデータレイアウトが実現できるというところが〇〇チャプターを通して書かれています。
B3の基本操作というのも主に2つ理解できるといいかなと思っていて、
まず1つがルックアップですね。
サーチ、ゲット。
要するに情報を読み取りに行くということですね。
自分の頭の中でB3上にデータを保存してみて、
このキーがおくえりが来たときにこのキー構造をどういうふうにたどっていくと目的のノードにたどり着くことができるのかというのを何となくビジュアライズしながら理解できるといいんじゃないかなと思います。
この本を読むという手法だけですとですね、ここら辺の動的な動きというのはすごいビジュアライズしづらいので、
これは参加者の方が共有してくれたんですけれども、
CMU、カーネギーメロンユニバーシティの有名なデータベース関連の講義のYouTube動画が上がっているんですけれども、
その中の一つにB3について詳細に話された講義の回がありまして、
そこにノードスプリットとかノード回しとかルックアップするときのビジュアライズされた簡易的なアニメーション、スライドで表現されているアニメーションがあって、
それを見るとビジュアライズに視覚的に理解することができるので、
ここら辺は例えばYouTubeとかショーノートにもリンク貼ろうと思うんですけれども、
そういったB3のルックアップするときには機構像の中をこういう風にたどっていくような例であったり、
ノードスプリットノードマージをするときにはこういう風に再期的にノードをスプリットしたり投稿したりするんだなということが視覚的に理解するといいんじゃないかなと思います。
あともう一つはこれも他の参加者の方が共有してくれたんですけど、
ウェブアプリでおそらく全てJavaScriptで表現されているのかな、
自分でどのデータを入れるかっていうのをテキストフィールドでインプットして、
インプットし続けるとウェブブラウザ上に実際の機構像、B3を表現できるっていうウェブアプリもあるみたいで、
こういうのも自分で好きなデータ、例えば1とか2とか3とか順番にインテージャーとかを入れてみて、
こういう風に機構像が動くんだね、
実際にデータを消したときにここがこういう風に分かれているんだねっていうのをテストしながらより深く理解できるようになるんじゃないかなと思います。
こちらも教えてもらったリンクは書のとおりに貼りたいなと思っています。
基本的にパート1の前半はB3を深く理解するというところにページ数が割かれていますね。
チャプター3とかチャプター4もこのチャプター2の基本的なB3の操作を理解した上で話が進んでいくので、
ここはぜひ時間をかけてYouTubeとかウェブアプリみたいな外部のリソースも自分の学習スタイルに合わせて適宜応用しつつ理解するといいんじゃないかなと思います。
結構議論も盛り上がりまして、いくつかピックアップしようかな。
まずチャプター2の前半で結構ディスクについての説明がありました。
そもそもハードディスクドライブとかSSDとかについてブロックレベルでどう動くのかとか、そもそもディスクシークって何みたいなのがありまして、
例えばこれもハードディスクドライブをもしかしたらここ数年でコンピューターの世界に入られた方はハードディスクを使ったことがない方もいるかもしれません。
僕は一応ハードディスクドライブが主流だった時期にコンピューターの世界に入っているので最初のコンピューターはハードディスクとかでしたけれども、
最近のMacとか買うと基本SSDなので、ハードディスクが実はディスク型でディスクシークというのが針とディスクがこういうふうに動いて、
というのをもしかしたら知らない方もいると思うので、これはぜひイメージとかYouTubeとかでハードディスクというものはどういうふうに動くのかというのを初見の方はぜひ見てもらいたいなと思います。
そうするとどうしてDBMSがこんなにディスクシークの回数を減らさなきゃいけないのかというのが納得できると思います。
というのもディスクシークするのを特にハードディスクドライブで表現しようとするのはめちゃくちゃ時間がかかる操作なんですね。
なので基本的にここがボトルネックになってしまうので、いかにハードディスク上でディスクシークを抑えるかというのをまずふに落とすというところがこのチャプターを読む前に必要な前提知識というかマインドセットかなと思います。
B3とその最適化
そこがあまりふに落ちていないとどうしてこんなにデータベースエンジニアは頑張ってB3を最適化しようとするのかという、
そもそも論のところに入れない、気持ちが理解できないと思うので、
ぜひハードディスクドライブでできればSSDのところも簡単にでいいので抑えておくと、この本の著者の気持ちがわかると思います。
そしてその後でB3というのも最初は確か1970年かなオリジナルのB3というのが発表されましたが、
その後でいろんなアッシュがというかバリアンスが発表されてきました。
ブリンクツリーであったりBプラスツリーであったり、本当にそのベースのB3を元に例えば書き込みのパフォーマンスを上げるためのライトオプティマイズバランスB3であったりとか、
あと同じレベルのノード間の移動をシブリングポインターで移動しやすいようにちょっと変えたB3、いろんなアッシュが出てきましたが、
ここで抑えたいポイントというのは、大体マイシークルとかポスグレみたいなDBMSの世界でB3と呼ばれたときには、
競技の意味でのB3を話しているのか、抗議の意味でのB3を話しているのか、どっちの話をしているのかというのをまず理解する必要があります。
競技のB3というのが1970年の論文で発表されたものですけれども、
オンライン上とかドキュメンテーションでB3というときにこっちを指していることはあんまりないんじゃないかなと思います。
アカデミズムの世界とか特定の論文を指している場合でない限り。
基本的にはB3というのはよく使われるのがBプラス3なんですけれども、
これはB3との違いでいうと、データブロックと小ノードへのポインターをどこに格納するかどうかの違いですね、平たく言うと。
もともとのB3というのが中間ノード、だから機構像で考えたときの一番上のルートノードと一番下のリーフノード、
その間にある中間ノードがあったときに、中間ノードにもデータを格納する前提で考案されたのがもともとのB3なんですけれども、
その後でデータをリーフノードにだけ格納した方がパフォーマンスが上がるよねっていう風に提案されたのが1973年だったかな。
Bプラス3です。
なので基本的にはDBMSの世界でBプラス3について話されているんだなということがなんとなく理解できるといいんじゃないかなと思っています。
この2つかな。
ハードディスクSSDの気持ちを踏まえた上で、なぜB3をこんなに最適化みんなしているのかというのがまず分かった上で、
B3にもいろんなアシュがあってBプラス3について話されているんだな、
そしてB3の基本的な操作を理解すると、この章を読んだ目標は達成できたんじゃないかなと思います。
MySQLの利用と課題
ここの基本を押さえた上で、あとは自分が使っているデータベースマネジメントシステムでは、
どんなインデックス、どのあるデータ構造、そのB3のアシュをサポートしているんだなというのを調べてみたりであったり、
ハードディスクとかSSDの動きについてもうちょっと詳しく調べてみたりであったり、
ここから先は個人の好みとか興味・関心によってもう一歩深掘る方向性はいろいろありました。
違っていたかなと思います。
個人的にはこの章を読んで、B3の基本的な、昔読んだデータ構造の本の中身をリフレッシュするみたいな感じで読みましたね。
こんなところかな。
ここはもう本当にイントロでもお伝えしたんですけども、ここは大事な章なので、
例えばこの本後半になっていくと、LSMツリー、ログストラクチャマジツリーとか、
結構最近の実アプリケーション、Metaが作っているOxDBとかでも使われているような、
あとはTime Series Databaseでも使われているような、別のデータ構造というのが出てくるんですね。
LSMツリーとか、そこで使われているSSテーブルみたいなのを理解するためには、
そもそもその前、データベースの長い歴史の中で、最初は、最初というか、
LSMツリーとかSSテーブルみたいなものが出てくる前は、B3という世界で頑張っていたということを理解すると、
他の発展的なデータ構造とか、その次の流れとかに行けると思います。
あと最後に一つ、面白いというか、これの章を読んでいて、今回僕がちょっと詳しく調べてみたものがありまして、
例えばMySQLってありますよね。
RDBMSのディスクベースの基本的にはディスクベースのDBMSというのがあります。
このMySQLを使っている企業も世の中にはたくさんありまして、
いろんなあの手この手で最適化しようとしています。
デフォルトで使うと、おそらくストレージエンジンの実装としてはinnoDBと言われるものが使われて、
ここではB3インデックスベースの実装を使うことになると思うんですけれども、
ここのこのB3を基本的に理解すると、
例えばある程度のスケールまではライトパフォーマンスが上がるんだけれども、
一定以上のスケール、そうですね、
例えばFacebookレベルとか大企業というかグローバルで使われるようなレベル、
YouTubeとかもかな、なると必ずどこかでボトルネックが出てくるので、
そこをどういうふうに改善し、他の企業を改善しているんだろうというのは、
いろんなこのホリジョンタルスケールを達成することでリードを増やしたりだとか、
いろんな方法あるんですけど、その一つの面白い、
これは結構もう2067年ぐらいに多分公開されているので、
知っている方もいるかと思うんですけれども、
FacebookでMyLocksという実装がありましてですね、
これはどういうことかというと、まずどこから話そう。
デフォルトで使われるInnoDBのストレージエンジンを、
LocksDBという全然別のキーバリューストアで丸っと切り替えちゃったというプロジェクトなんですね。
LocksDBというのはシープラプラで書かれた、
これもFacebookから出ているオープンソースの実装で、
ロゴ、プーマかな、ヒョウかな、ちょっと確認しなかったんですけど、
要するに速く走っている動物のロゴのLocksDBなので見たことがある方もいるかもしれません。
これがLSMと呼ばれるLog Structured Merged Tree SSTable実装ベースのキーバリューストアなんですね。
ライトのパフォーマンスをすごい高めたかったという事例があったので、
今までのInnoDBベースのB-treeのインデックスで頑張るのではなく、
そこのインデックスレベルの実装も丸っと全く別のものに置き換えることによって、
特定のユースケースに合うような、
全然別のMyLocksというものを発表しましたよというのが、
これ公開されているんですけども、
MyLocksの登場
そういった事例もあったりしますと。
そういったMyLocksも個人的に面白いなと思ったんですけど、
そこらへん、そもそもなぜFacebookレベルのスケールでアプリケーションを動かさなければいけない人たちが
デフォルトのInnoDBではなぜ対応できなかったかというのも、
裏側でB-treeというものを使っていて、
それがどういう動きでどういう構造になっていて、
どういう場面でパフォーマンスボトルネックにぶち当たるのかというのを理解しておくと、
だからMyLocksDBというかLocksDBのような冷静にツリーベースの書き換えが必要だったんだなというのがピンとくると思います。
なので、データベースのオンライン記事とか他社の取り組みとかを理解するときにも、
データベースの裏側にあるインターナルゾーン、それこそ仕組みというのを理解する。
基本を理解するというのは本当に大事なポイントかなと思うので、
この本をですね、ブッククラブと並行して一緒に読んでくれているリスナーの方もいらっしゃると思うんですけども、
途中で挫折してもいいので、この章だけはぜひ、
B-tree知らないよという方はぜひ、この章だけでも頑張って読んでみると絶対生きてくると思うので、
一緒に頑張りましょうということで、
今回はチャプター2、B-treeベイビー6の振り返りをソロ収録で収録しました。
皆さんありがとうございました。またチャプター3でお会いしましょう。
