B-Treeの基本と実装
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。イギリスのロンドンからお届けしています、Ken Wakatomoです。
本日は、London Tech Talk名物Bookclub第四弾、Database Internalsの振り返りを収録していきます。
今回は、Chapter 4について振り返っていこうと思います。
まずは、本章の簡単な振り返りからご紹介しますね。第4チャプターは、タイトルが【Implementing B-Trees】 ということでした。
簡単に過去第3章を振り返ると、第1章の【Introduction and Overview】で、ざっくりとデータベースマネジメントシステムはどういうことかということを学習した上で、第2章で【B-Tree Basics】ということで、
データベースマネジメントシステムでよく使われるデータ構造であるB-Treeの基本的な操作について学習しました。
その次の第3章、ファイルフォーマットのところでは、B-Treeのディスク上のレイアウトであったりとか、あと実際に実装する上でのテクニックについて紹介されてきました。
これらの第3章を通して、読者の皆さん、リスナーの皆さんはB-Treeの基本的なこと、そしてそれがなぜデータベースマネジメントシステムで使われるのかという、
いわゆるB-Treeの一般教養のようなものは理解できたのではないでしょうか。
それらを踏まえた上で、今回の第4章、Implementing B-Treesでは、タイトルにもある通り、インプリメンテーション、実際の実装というところにフォーカスを当てています。
この本書は、アパチカ・サンドラと呼ばれるデータベースマネジメントシステムのコミッターの一人が書いたんですけれども、
実際に論文とか教科書で紹介されているようなB-Treeのことはわかったと。
じゃあ実際に使われているデータベースマネジメントシステムにおいてB-Treeを利用するときには、
具体的にどのようなテクニックが使われているのかであったり、
パフォーマンスを実際に上げるためにどのようなテクニックがあるのか、どのような制限があるのかというところを、
実際にそのテクニックの名前であったりとか、気にすべき制限であったりを一つ一つ紹介していくという章になっていました。
簡単に本章で紹介されているテクニックについて挙げていくと、
例えばメタデータをどこに置くのか、ページヘッダーに置くのかという話であったりとか、
Sibling Linksという兄弟ノードに移るためにポインターのようなものを使うことで、
どのようなパフォーマンスの向上が見られるのかであったり、
あと大きめのデータをディスクに保存するときにはOverflow Pageというものが使われる。
あとはB3にたくさんデータが書き込まれたり削除されたりするときに、
データの機構像をバランスさせる必要があるんですけれども、
そのリバランスというのはどのようなタイミングで起こるのか、
そのリバランスを可能な限り回数を抑えるためにはどのようなことを気をつけるのかについて書かれていましたね。
あとはRight Only Appendと呼ばれる単調増加する連番のような場合には常に右端に追加されるので、
リバランシングを避けるためには条件付きなんですけれども、
Right Only Appendのようなテクニックが使われる場合もあるよというような紹介であったり、
あとは一つ一つデータを書き込むのではなく、
その都度B3がバランスされているかどうかを検査する必要がないバルクローニングのようなテクニックがあるという紹介もされていました。
ショーの最後の方ではいわゆるガベッジコレクションということで、
いわゆるポストグレスとかで呼ばれるバキュームのプロセスなんですけれども、
データが削除されることになったときに、
実際にディスク上からデータを物理的に削除するプロセス、
どのように動くのか、動作するのかについても紹介されていました。
第4章の個人的な印象なんですけれども、
テクニックとパフォーマンス向上
B3を実装するにあたって大事な概念がつまみ食いできるような感じで紹介されていたので、
おすすめの読み方というのを事前にこのDiscordのチャンネルとか収録とかでも話したんですけれども、
今回は、例えば初めて第4章を読む方は全てのテクニックを完全に把握しようと最初から最後まで読むというよりは、
1つから2つ、余裕のある方は3つぐらいここで紹介されている概念とか、
気になるテクニックを自分でピックアップして確実に理解するという方が良いかなと思います。
なので実際にその6章メモを皆さんに書いてもらったんですけれども、
とある人はGarbage Collectionについてソースコードを見に行くレベルで深掘りしていったりですとか、
とある方は例えばOverflowページについて自分が普段使っているデータベースではどのようなコンフィグレーションがあるのか、
どのようなチューニングポイントがあるのかというふうに深掘りしていった方もいました。
また他のおすすめの読み方としては、
この本書は割とポストグレとかカサンドラの例が使われることが多いんですけれども、
ここで紹介されているテクニックを知った上で自分が普段使っている全く別のデータベースではどのような似たような最適化であったり、
似たようなテクニックが実装されているのかというのを調べるのも業務と関連させる形で本書の内容を知識を応用できるので、
すごいおすすめの読み方かなと思います。
BookClubの振り返り
実際にそうやって自分が業務で使っているデータベースと関連して読書メモを書いてくださっている方もいましたね。
チャプターの簡単なサマリーはこれぐらいかな。
実際にBookClubの当日のことも振り返りたいと思うんですけれども、
今回は第4回目ということで、
タイムゾーンを今回3つのタイムゾーンに分けてやっていて、
それが3つのタイムゾーンから2つピックアップして、
ロテーションで回していくという感じでしたね。
1回目が最初はAPACとEMEA、
次がEMEAとノースアメリカ、
その次がノースアメリカとAPAC。
このロテーションを回していくという形で、
今回第4回目なので一通り一巡した上でまた2回目のロテーションという感じなので、
結構その参加者同士の方のお互いも顔も知って、
議論も盛り上がってきたので、
割と温まった空気感の中で、
緊張もほどけてきたような中で、
すごい議論が盛り上がったショーかなと思います。
今回はAPACとEMEAだったので、
参加者の方も比較的このロテーションの中では多めで、
すごいいろんな観点が掘り下げられたかなと思います。
次に個人的に興味深かったテクニックを1つか2つピックアップして紹介していこうと思います。
まず1つ目がショーの後半で書かれていたガベッジコレクション、
バキュームのプロセスですね。
ポストグレスを結構運用されてきた方にとっては、
バキュームというのは頭痛の種じゃないですけど、
悩みの種の1つなんじゃないかなと思いますが、
まず簡単にちょっとおさらいしますね。
まずポストグレスのようなデータベースでは、
マルチバージョンコンカルシーコントロール、MVCCと呼ばれるんですけども、
MVCCと呼ばれるトランザクションのアイソレーションの仕組みを実装されています。
これはどういうことかというと、
簡単に言うとデータって更新されたり削除されたりしますよね。
例えば自分のユーザーアカウントテーブルがあったとき、
自分のユーザーアカウントのハンドルネームを変えたいであったり、
あとは新しいSNSみたいなものを創造したときに新しいポストを投稿したりとか、
あとはポストの内容をエディットしたりみたいなときにどんどんデータが書き換えられるというのは、
どの業務アプリケーション、どのユーザーアプリケーションでもあると思うんですけれども、
その書き込みがあるたびに別々のスナップショットというものを取っておきます。
これがMVCCのマルチバージョンと呼ばれる理由なんですけれども、
そのいくつかのスナップショットを取っておくことで、
MVCCの基本的なアイデアとしてはトランザクションのアイソレーションということなんですけれども、
ライトとリードのロックを取り合う可能性を可能な限り避けるということなんですね。
具体的には最新のバージョンにおいては書き込みが必ず反映されるようにするんですけれども、
少し遅めの、少し古めのかな、スナップショットに対しても実際のリードが読み込みができるようにしておくと、
これはそのコンシスタンシー、整合性が壊れない限りで古いスナップショットもデータを読み込みにできるようにしておくと、
バキュームとデータ削除のメカニズム
例えばその最新のバージョンにアクセスする必要がある書き込みは最新のスナップショットをロックを取って書き込まなきゃいけないんですけれども、
例えば書き込みが発生しているときにやってきた他のプロセスからの読み込み、リクエストというのは待たなきゃいけなかったんですけれども、
MVCCの基本的なコンセプトがうまく機能している限りは、
整合性が壊れない限りの古いバージョンを読み込むことで、
書き込みが発生しているときに来ている読み込みのワークロードもロックせずに読み取ることができるという基本的なアイデアでした。
問題になってくるのは、このようなマルチバージョンのようなスナップショットをいくつか取っておくような実装にしておくと、
具体的に実際に削除が起こったときにデータをディスク上、物理的にディスク上からいつ削除するのかというのが問題になってくるわけですね。
デリートリクエストだけじゃなくてアップデートもそうなんですけれども、
例えば行の中身をアップデートしたときに古いデータって発生しますよね。
その古いデータというのは読み込む必要がないので削除したいんですけれども、
マルチバージョン、MVCCの場合はデリートとかアップデートが起こったときに、
すぐにその古いデータ、削除すべきデータがディスク上から消えるわけではありません。
それがデッドタブルとか呼ばれたりするんですけれども、
このデータはもう必要ないですよ、読み取るべきではないですよというふうにバイナリーのフラグを立てておいて、
後で非同期、もしくはフルバキュームのような形で削除してあげることが求められますね。
トーストの概念と実装
このフラグというのがビジビリティマップ、VMとか呼ばれたりするんですけれども、
このバキュームというガベッジコレクションのプロセスは、
そういったすでに不要になった、インビジブルになったデータ、デッドタブルを削除してあげるプロセスのことですね、バキューム。
例えばPoseGreyのバキュームというのは2つプロセスがありまして、
1つはインクリメンタルに発生するオートバキュームというプロセスで、
これを基本的には有効にしている人がほとんどじゃないかなと思うんですけれども、
オートバキュームというのはバキュームのオペレーションを自動的にバックグラウンドで発生させますと。
一方で、例えばメンテナンスが必要なときにバキュームフルと呼ばれるコマンドを発行することで、
テーブルにあるすべてのデッドタブルを削除する、もしくはディスクをコンパクトにするというオペレーションが求められたりします。
自分のSRE人生を振り返ったときに最初にバキュームという言葉に知ったときに、
なぜバキュームが必要なのかというのは裏側の仕組みから理解することは当時はできていなかったんですけれども、
今回データベースの裏側の仕組みを理解することでバキュームが具体的に何をやっているのかとか、
そこに例えばビジビリティマップとかデッドタブルがどのように関わってくるのかを改めてソースコードと一緒に理解するいいきっかけになりましたね。
個人的に気になった2つ目のポイントが今回の章でいうと、オーバーフローページなんですけれども、
要するにオーバーサイズドのデータを入れるときにどうやって入れるのかという話ですね。
例えば、これもポスグレの例になるんですけれども、ポスグレではトーストと呼ばれるテクニックがあります。
トーストというのはT-O-A-S-T、これは短縮名なんですけれども、
元の名前がThe Oversized Attribute Storage Techniqueということで、
オーバーサイズドアトリビュートなので、サイズを超えた要素をストレージなので保存するテクニックのことをトーストと呼ばれています。
これどういうことかと言いますと、ポスグレというのは大体ブロックサイズと呼ばれるコンフィギュレーションで設定できるページサイズというのが決められていて、
これはデフォルトで確か8KBだったんですけれども、これがデータストレージ、HDDとかSSDにディスクを入れるときのページのサイズです。
ページのデフォルトが8KBなんですね。
問題は大きめのイメージファイルであったり、あとはJSONBみたいな感じで非構造データのJSONを入れたいみたいなときに、そのデータが8KBを超えるとしますと。
8KBを超える、デフォルトのブロックサイズを超えるデータを保存したいってなったときに、
ポスグレはデータベース側としてはそれをどう扱うのかという問題ですよね。
一つナイーブに考えられるのが、デフォルトで指定したブロックサイズを超えたら、それを保存できないっていうふうにエラーを返しちゃう。
これはありかもしれませんですけれども、できれば透過的に扱いたいですよね。
そのユーザーアプリケーションの観点から言うと、ブロックサイズを超えたデータが保存しようとしても裏側でいい感じにページを分割してくれて、
32KBだろうがそれを超えたデータだろうが、いくつかのブロックに分けて保存するようにしてほしいと。
いわゆる典型的なスキャッター&ギャザーストラテジーというか、保存するときに内側でシャーディングのようにデータを分けて保存して、
取ってくるときにはそれをまとめて、必要なデータを全部まとめてユーザーに返してあげる。
それのデータベースを使うユーザーアプリケーションの観点から言うと、裏側で分割されているという、
透過的に分からず、いい感じにデータを保存してまとめて返してくれるというテクニックなんですね。
というテクニックがありますと、トーストと言いますと、ポストグレーの場合は。
この仕組みも知っておくと、裏側で何をしているのかというのを簡単に書かれていて、
そのトーストというのはデータとブロックサイズを超えた別々のチャンクを、
トーストテーブルという別のテーブルにマッピングを保存しておくんですね。
ブロックサイズを超えたデータを分割しなくちゃいけないので、
トーストのパフォーマンスへの影響
どのページがどの元々のオリジナルのデータの何番目なのかというのを保存しなきゃいけないですね。
このマッピングというのが、ポストグレーのシステムテーブルの中のトーストテーブルと呼ばれるところに、
チャンクのIDとデータチャンクというのを保存する形になっています。
これはどういうことかというと、ブロックサイズを超えたような大きなデータを保存するときに、
実は裏側で2つのテーブルを参照しなきゃいけないというんですね。
もともとのデータを保存している、例えばイメージテーブルとしましょう。
そのイメージテーブルに大きめのイメージを保存したと、
プロファイルイメージでも何でもいいんだけど保存して、
そのでも実際のデータは複数のブロックにチャンクとして分散されていると。
ユーザーにプロファイルイメージをくださいと言われたときには、
いくつかの複数のページを集めて、それを一つにコンバイン、統合して返してあげるんだけど、
それがどこのマッピングになっているかというのを取りに行くのに、
別の逃走テーブルを取りに行かなきゃいけないということなんですね。
なので、オーバーヘッドがかかるわけですよね。
別のテーブルにマッピングを見に行かなくちゃいけないし、
複数のページにアクセスしなきゃいけないので、
ディスクIOの数ももちろん増えます。
なので、ユーザーの観点からすると、ブロックサイズを超えた大きめのデータでも、
いい感じに保存してくれるということなんだけど、
例えばこれがかなりスケールの大きい規模とか、
リクエストパーミニッツの高いハイレテンシーで、
すごいフリークエントにリクエストが来るようなサービスで、
トーストテーブル、トーストのテクニックが使われすぎちゃうと、
これはクエリパフォーマンスとかデータベースのパフォーマンスに影響してしまうというのが
一つインプリケーションというか、リスクとしてあるわけですよね。
なんでかというと、トーストテーブルのマッピングも取りに行かなくちゃいけないし、
複数のページもディスクIO発生してしまうので、
例えばこれがフルバキュームが発生している状況で、
その中にトーストテーブルにアクセスするようなデータがいくつかあったりすると、
そこでコンテンションが起こってしまい、ディスクIOが跳ねてしまったりであったりとか、
あとはサービスのピークタイム時にユーザーが求めるようなレイテンシー、
SLOでデータベースがレスポンスしなくなってしまったりとか、
そういった可能性があるので、
例えばトーストという機能があっても、それをただ使うわけじゃなくて、
必要なメトリクスを入れて、ちゃんとメトリクスで監視しようであったりとか、
テイカーウェイの重要性
必要なアラートを入れて運用しようみたいなところに議論がつながっていくのかなと思うので、
今回、改めてトーストの仕組みとか裏側の仕組みについて振り返るいい機会になったので、
個人的にはかなりテイカーウェイが多かったなと思っています。
2つですね、1つ目が個人的な振り返りとしては、
ガベッジコレクション、バキュームとトーストのところを振り返って勉強するいい機会になりました。
実際に最後にブッククラブでどのような議論が盛り上がっているのかというのも、
簡単に思いつく限りで紹介したいんですけれども、
第4章にもなってきたので、結構皆さんそれぞれ自分に合う読み方であったり、
自分が気になるポイントというのも結構見えてきたんじゃないかなというのがすごい分かりましたね。
例えばモバイルエンジニアの方とかだったら、
なじみのあるSQLiteについて結構深掘って見てくれた方もいましたし、
あとはGUILDでPOSGREを使っている方は、
結構ガンガンPOSGREのソースコードとかREADMEとか見に行って、
こういうことを発見しましたっていうのをリンクで貼ってくれたりしたので、
これすごいいいなと思って、個人的にも勉強しながら読んでいましたね。
僕自身は今回この本を読みながらPOSGREを結構深掘りしながら読んでいるんですけれども、
その他のデータベースでどういうコンフィギュレーション設定があるのかとか、
どういうテクニックがあるのかというのも、
合わせて皆さんが持ち込んでくれるので、
本当に他のデータベースと比較しながら同じペースで読めているというのがすごい楽しいなと思っています。
本章で紹介されている例えばリバランシングとかに関しても、
そもそもリバランシングってどういうときに必要なんだっけ、
なんでリバランシングを避けなきゃいけないんだっけみたいな、
ちゃんと本質を理解しながらみんなで議論しながら読めたとか、
そこもすごい良かったかなと思います。
一人で読んでおくと、こういうものがあるんだなと思って、
分かって気になってどんどん章を飛ばしがちになっちゃうかもしれないですけど、
本を読んだ上で議論しなきゃいけないので、
ちょっと分かんないなっていうところを気軽に聞き合えるというか、
突っ込んで他の人の突っ込みに答えられるぐらいにはちゃんと理解しなきゃいけないという、
程よい緊張感もありながら、
みんなで同じ目標に向かって読めているという雰囲気が引き続きあるのがすごい良いかなと思っています。
データベースの具体例
自分はPOSGREを中心に読んでいると言いましたけれども、
個人的にモバイルとかエッジコンピューティングとかで使われることも多いSQライトとかも気になっているので、
そこら辺もつまみ食いしながら個人的には読んでいきたいかなと思っていますね。
今回はソロでの振り返り収録なので、
サクッとこれぐらいでそろそろクロージングに向かっていこうと思うんですけれども、
このデータベースインターナルズ、4章、5章、6章が結構好き嫌いが分かれるというか、
一つの二つ目の山かなと思っています。
実際のコミュニケーションが書いているので、
実装するときの具体的なテクニックとかソースコードのリンクとか、
データ構造アルゴリズムの名前が結構バラバラ出てくるので、
一貫性があるかというと、そんなに一貫性があるわけでもないかなと思っているんですよね。
トピックごとにチャプターはうまく分かれているんだけど、
じゃあなんで今回とか、ライトモーストポインター、スノードハイキーの後にオーバーフローページが来て、
その後にバックローディングが説明されてみたいなのは、
別にすごい一貫性があるわけじゃないので、
ちょっと冒頭にも言ったんですけれども、
各章1つか2つ自分が気になるテクニックを見つけて、
そこのソースコードを読んだり、
チャットGPTとインタラクティブにしながら理解してみたり、
あとはいくつか記事を読んでみたりみたいな、
読み方を第5章、第6章もしていくのがいいかなと思っています。
簡単に第5章の端末をつまみ食いをすると、
次ちょっと個人的に重めかなと思っていて、
トランザクションプロセッシング&リカバリーというんですけれども、
データベースの醍醐味というか、
重要な機能の1つというのが、
ノードがプロセスがクラッシュしても、
データが保存されるというところなんですよね。
そのトランザクションのリカバリーというところを、
具体的にどのようなテクニックを使って、
データベースが保存しているのかというのとかが、
第5章で分かってきますし、
第6章はB3バリアントなので、
B3のアッシュについて結構紹介していきます。
なのでここはB3の基本、
第2章で紹介されたB3の基本と、
第4章のB3のテクニックを抑えた上での第6章になっていくので、
ここら辺に行くにつれて、
何回か第2章とか第4章とか行ったり来たりしながら、
読んでいく感じになるんじゃないかなと、
個人的には思っています。
そして個人的には第7章のLSM Tree、
Log Structures, Merged TreeとかSS Tableとかは、
これはホットというか、
ぜひモダンなデータベースで抑えておきたいキーワードなので、
ここまでは何とか、
今一緒に読んでくれているリスナーの方も、
Book Clubに参加している方も一緒に、
7章まではきちんとまずやっていきたいなと思っています。
まずは折り返し地点向けて、
一緒に頑張っていきたいなと思っています。
ということで、
データベースインターナルズブッククラブの第4章、
Implementing B-Treesの振り返りは以上にしようと思います。
また次の振り返り収録でお会いしましょう。
さようなら。
