00:03
リスナーのみなさん、こんにちは。London Tech Talkへようこそ。
イギリスのロンドンからお届けしています、Ken Wakatomoです。 本日は、London Tech Talkの【Bookclub】
LSMツリーの基礎
【Database Internals】の振り返りを収録していきます。 今回は、Chapter 7
ログストラクチャードマージツリー、 通称LSMツリーについて、振り返っていこうと思います。
今回のショーの目玉は、前回学んだBツリーとは全く異なる設計思想を持つ、
現代のモダンなデータベースのもう一つの主役と言っても過言ではない、 LSMツリーの世界に深く飛び込んでいくことです。
軽く前回の第6回目の振り返り収録のおさらいからいきましょう。 Chapter 6では、Bツリーという機能をいかにして、
変わりゆくビジネス要件に対応させるか、という品種改良の話をしてきました。 FGツリーとか、Lazy Adaptiveツリー、
バズワードツリーのようなBツリーの亜種について紹介しました。 しかし今回説明するLSMツリーというのは、
品種改良というよりはむしろ全く別の種、別の種という考える方がしっくりくるかもしれません。
Bツリーが言うなれば、がっしりとした構造の整った日本庭園のような樹木だとすると、
LSMツリーはこう、もっと野生的というか生命力あふれる竹林のようなイメージですね。
竹というのは、まず細い竹の子として地面にちょこっと顔を出して、ものすごい速さで成長していきますよね。
そして次々新しい竹が生まれていきます。 そして古くなった竹は自然と淘汰されていくんですけれども、
このLSMツリーには実は後から説明する2つのアペンドンリー、ツイキとマージアンドコンパクションという性質があるんですけれども、
僕の頭のイメージの中ではまさにLSMツリーの本質を捉えているようなアナロジーじゃないかなと思いました。
今回の章を読む目的はこれですね。 なぜBツリーのような更新モデル、
インプレースに更新していくモデルだけでは不十分だったのか。 なぜLSMツリーというツイキ型のアーキテクチャが発明され、
モダンなデータベースで採用されるに至ったのか、という歴史の流れを理解することです。
特に書き込みが非常に多いEコマースのようなワークロードであったり、例えばSNSのタイムラインであったり、
IoTデバイスからのセンサーデータとかアプリケーションのログ収集といったシナリオでは、
Bツリーの書き込み時のロックとかページのマージ、ノードスプリット、ノードマージといったオーバーヘッドがボトルネックになりますね。
一方、LSMツリーではこの書き込み性能を最大化するために、読み込みの性能をある程度犠牲にするという大胆なトレードオフを選択しました。
今回はその賢いすくみとアーキテクチャを、ちくりんの成長を観測するような気持ちで一緒に見ていきましょう。
MemTableとSSテーブル
では簡単に内容を振り返っていこうと思います。
まず、LSMツリーが解決しようとした課題なんですけれども、Bツリーはデータを更新する際にディスク上の特定の場所にあるデータを直接書き換えて機構像をバランスさせた状態にする必要がありましたよね。
これはとても大きなベネフィットがありまして、読み込みの際にはデータが常に一箇所にまとまっているのでレンジクエルのように効率的にデータを取得することができたんですけれども、
書き込みの度にランダムなディスクIoが発生してしまうというのが大きな問題でした。
機構像をバランスさせた状態に維持するためにノードマージやノードスプリートといった操作が必要になるため、書き込み性能に限界がありました。
以前の振り返り収録ではこれをライトアンプリフィケーションという問題と呼びましたね。
さて、LSM3はこの問題を解決するために全く別の発想します。
それは全ての書き込みをセクエンシャルにするというものです。
ディスクへのランダムアクセスが遅いなら常にディスクの最後に追記していくだけのセクエンシャルアクセスにしてしまえばいいという、至って非常にシンプルなアイデアと言えるかもしれません。
このアーキテクチャを実現するために主要なコンポーネントが2つあります。キーワードが2つ出てきましたね。
もしこれがテストならここをよく押さえておいてねって先生が言うところですね。
まず1つ目、MemTable、メモリーテーブル。
2つ目がSortedStringTable、SSテーブルというものです。
じゃあこの2つのキーとなる概念についてまたアナロジーで紹介していこうと思いますね。
ロンドンテックトークのブッククラブの振り返り収録ではまあだんだんおなじみとなってきたんですけれども、アナロジーを用いて難しい概念を説明していこうと思います。
今回はそうですね前回のアナロジーとも似てるんですけど、オフィスのデスクで新しいタスク仕事を処理する様子をイメージしてみてください。
じゃあまずMemTableというのはメモリ上のテーブルなんですけども、
新しいタスクが、新しくやることがいけない仕事が舞い込んでくるとします。
これは一種書き込みデータだと思ってもらっていいんですけれども、まずは机の上のToDoリスト、メモ帳に書き留めていきます。
これが実質のMemTableですね。
MemTableはメモリ上にある相当されたデータ構造、スキーマリストとかなので非常に高速に書き込みができます。
とりあえず同僚とかマネージャーとかにこういう仕事を頼まれたら忘れないうちに、とりあえずテーブルの上にデスクの上にあるToDoリストに書き込むという状況ですね。
さて、そうやってこうToDoリストを書いていくとですね、メモ帳がどんどんどんどんいっぱいになってしまいますと。
メモ帳がいっぱいになったらどうするのか。
そのページをですね、一種オーガナイズしていく必要がありますけれども、そのページを破って、例えば日付順にやったもの、やってないもののタスクを分けて、処理済み、まだやっているものと書かれたファイルボックスにどんどんしまっていくような感じですね。
これがいわゆるSSテーブルですと。
メモテーブルがいっぱいになると、その内容というのはソートされた、イミュータブル、また出てきましたね、この変更不可能なファイルとしてディスクに書き出されます。
この二段構造になっていますね。
このファイルがSSテーブル、Sorted String Tableです。
Sorted並び替えたストリング文字テーブルということになっています。
この書き出し処理は、メモテーブルからSSテーブルに行くときに一度にまとめて行われるシークエンシャルな書き込みなので、非常に高速です。
さて、このアーキテクチャのメリットは明らかで、書き込みが非常に早いことですね。
リードアンプリフィケーションとコンパクション
もちろんデメリットもあります。
先ほどのディスクの例で考えてみましょう。
例えば特定のタスクについて、あれ、あの件どうなったんだっけ、みたいな感じで同僚に聞かれたときに、
これは一種データの読み込みリクエストのこと、アナロジーなんですけど、
あなたはどうしますでしょうか。
まず今書いてある、今デスクの上にあるメモ帳を確認し、次に処理済みのファイルボックスも確認し、
新しいものから順々に探していって、同僚とかマネージャーから問い合わせがあったタスクの状態について確認しなきゃいけないですよね。
最悪の場合、ファイルボックスにまとめたフォルダの中を全部開けて確認しなきゃいけないかもしれません。
これがLSMツリーにおけるリードアンプリフィケーションの問題ですね。
書き込みを早くするが故に、メモテーブルとエッセステーブルという見る場所を2つに分けなくてはいけませんでした。
もちろんここで終わらないのが、LSMツリーを発明した人々の賢いところなんですけど、
このリードアンプリフィケーション読み込みの遅さを解消するために、
LSMツリーはいくつかのスマートな仕組みを実装しています。
この一つ目が、ここもキーワードですけれども、ブルームフィルターです。
ブルームフィルター、これはデータ構造とかアルゴリズムの勉強をしている方は聞いたことがあったり、実装したことがある方もいるかもしれません。
これはですね、確率的データ構造とも言われるんですけれども、
イメージとしてはそれぞれのエッセステーブルに付随する一種、
魔法の作品みたいなイメージですね。
なぜ魔法というかというと、これはちょっと面白いんですけど、このブルームフィルターを使うと、例えばこのファイルボックスに、
例えばそうですね、この仕事を終わらせる、この仕事プロジェクトに関するメモは絶対に入っていない、
ということを非常に拘束に判定できます。イメージとしてはこのファイルボックスにシールでも貼ってあって、
ここには会計情報は絶対ないとか、HR人事情報は絶対ないみたいに書いてないものは確実にわかる。
これにより無駄なファイルオープンを減らすことができますね。
なのでブルームフィルターを使うことによって、このディスクは見なくて良いということが確実にわかります。
このブルームフィルターの面白いところは、この入っていないということは100%保証できるんですけども、
その逆、入っているかもしれないという、いわゆるフォルスポジティブですね。
間違って入っているかもしれないよ、でも実際見に行ったら入っていないと答えることもあるんですね。
この場合は実際にファイルの中身を見に行く必要があります。
このブルームフィルターの実際については紹介しないんですけども、これはなかなか面白いのでぜひ気になる方は見てみてください。
なのでそのブルームフィルターはどこのファイルに、フォルダー、ファイルボックスにデータがあるかというところまでは教えないんですけども、
一つ一つのファイルを見るときにここは見なくていいよっていうところは間違いなく教えてくれるということで、
実際のトータルの読み込みの遅さを軽減してくれています。
そしてもう一つ、LSM3のコアの機能と言えるのがコンパクションですね。
例えばアナロジーの続きで説明すると、ファイルボックスがメモであふれ返ってくると、同じタスクに関する古いメモと新しい、さっき書いたばっかりのメモが混在していて、とても効率が悪いですよね。
コンパクションプロセスの理解
そこで、例えば週末土曜日の朝に時間を見つけて、複数のファイルボックスの中身を一つにまとめて、
重複しているタスクだったり完了したタスクのメモを捨てて整理整頓して、ファイルボックスの中身をギュッと圧縮する、整理整頓するイメージです。
まさにこれがコンパクションです。
このコンパクション、ディスク上での働きとしては具体的にどう実装されているかというと、
複数の小さなSSテーブルがどんどんどんどんできていくんですね。
メモテーブルからディスクに書き込むときに、メモテーブルの中身をシュッとSSテーブルに書き込んでいきます。
それを長くデータベースを動かしていると、複数の小さなSSテーブルがどんどんどんどんできてしまうんですけれども、
これを定期的なタイミングでギュッとマージして、より大きな新しいSSテーブルを作成していくイメージです。
このプロセスで削除されたデータとか、更新されて古くなったデータとかも物理的にデータとして落としてしまうので、
そのSSテーブルの数も減るし、結果として読み込み性能が向上する。
もちろんディスクスペースも節約できるということになっています。
ということで、このコンパクションはもちろん定期的にしたいんですけれども、
聞いててあれ?と思った方はいるかもしれません。
Postgresとかで実装されているMVCCベースの時に必要なバキュームと似ているプロセスですよね。
僕もそう思います。バキュームみたいに定期的にコンパクションしなきゃいけないですね。
このコンパクションの処理自体というのもディスクの読み書きを発生させてしまいますよね。
要するにそのSSテーブルを読んで、中身を読んで、マージして書き込むみたいなところが発生するので、
これはLSM3における新たなライトアンプリケーションの現世となっていたりします。
なので読み込みを、書き込みを速くするためにメモテーブルとSSテーブルに分けた。
それだと遅くなるので読み込みを速くするためにコンパクションを実装した。
しかしコンパクションを雑にやってしまうと、今度はコンパクションによって書き込みのライトアンプリケーションが起こってしまうので、
そのコンパクションをどんなストラテジーでしていくかというのも、
これはまた一つ面白いチューニングポイントになってきますね。
ロックスDBの開発経緯
具体的にはそのコンパクションの流度であったり、コンパクションの頻度であったりするんですけども、ここら辺はちょっと後で説明していこうと思います。
本書ではですね、このLSM3を実装している代表的なデータベースとして、
これは調べていただくとたくさんあるんですけども、
GoogleのレベルDBからメタのFacebook、元FacebookのロックスDB、ここら辺は有名ですね。
そして分散データベースのCassandraなどが紹介されていました。
この特にメタエンジニアリングチームが作ったロックスDBというのは、
他のいろんなストレージエンジンを置き換えるプロジェクトとしても使われています。
例えばMySQLのストレージエンジン部分をB3じゃなくてロックスDBにガラッと置き換えたMyLocksプロジェクトなんかも同じくFacebookから出されていたりしますので、
多くのモダンデータベースのバックエンドとして採用されている重要なデータベースになっています。
一旦ここまででLSM3の簡単なまとめでした。いかがだったでしょうか。
書き込みを高速化するために、まずメモリで受け止めて、ディスクには後からまとめてバッチングして書き出すと。
その結果遅くなってしまう読み込みはブルームフィルターとかコンパクションといった工夫でカバーするというこのLSM3の賢いトレードオフの構造が少しはイメージできましたでしょうか。
さてここで一つ具体的なプロジェクターについて見ていこうと思います。
先ほども説明したロックスTVというのはいろんなところでデータベースを触っていると見るキーバリウスソワーだと思うので、これについて説明していこうかなと思います。
もちろんロックスTV自体は深掘りしようとすると1本2本シリーズものを取れるような面白いキーバリウスソワーなんですけれども、このLSM3という文脈に限って紹介していこうと思いますね。
まずロックスTVの歴史から見ていこうと思います。
ロックスTVというのはもともと別のレベルDBというGoogleが開発した組み込みデータベースをベースにされたものです。
レベルDBというのは非常に他のデータベースと比べるとシンプルで効率的なLSM3の実装として知られていたんですけれども、
当時のFacebookが社内の大規模なデータ処理の要件とかSNSのビジネス要件を満たすためにさらなる機能拡充や性能改善が必要だったということで、
レベルDBをフォークしてFacebookのワークロードに最適化された形として開発を進めたのがロックスTVです。
このロックスTVが多分2010年代前半かな、2012年中3くらいだと思うんですけど、
本格的に開発が始まって、公式ブログとかエンジニアリングブログとかでも公開され始めて、メッセージングサービスとか写真系のサービスで使われたと書いてありました。
その後オープンソース化されて、その後いろんなデータベースのバックエンドストレージとしても使われるようになった。
このロックスTVというのがレベルDBの思想を受け継ぎつつ、よりエンタープライズな、特にこのFacebookのようなスケールで使われる利用を想定された性能改善が施された進化系だと言っても過言ではないんじゃないでしょうか。
メトリクス監視とチューニング
せっかくなのでSREをやっている僕がお話しさせてもらっているので、ちょっとSRE観点でこういったロックスTVとかASMツリーを見ていこうと思うんですけど、
SRE観点でどういうメトリクスとかどういうことを気をつけてロックスTVを運用するかということですね。
ロックスTVはアプリケーションに組み込まれることが多いので、その内部状態を適切に監視することが非常に重要となってきます。
まず基本的なところで言うと、もちろん書き込みのスループット、write per secondとか、読み込みのスループット、read per secondはRPSとか必須ですけど、これはどのデータベースでもちろんどれぐらいの書き込みが来てますかとか、どれぐらいの読み込みクエリが来てますかみたいなのを理解するのにベースとなるメトリクスですよね。
レイテンシーとかももちろん重要となってきますよね。
例えば、putとかgetとかいろんな操作が入ってくるときに、それぞれのアベレージとかp99%でのレイテンシーってどれぐらいになってますかということで、データベースのクライアントへの影響を把握できますよね。
ここら辺はベースですと。
ディスク関連で言うと、ディスクIOのスループットとかレイテンシーかな。
LockCBっていうのはLSMベースなので、コンパクションによるディスクの書き込みっていうのが頻繁に発生します。
そのコンパクションも基本的にはオートマティックでメンテナンス、ものによりますけど発生してるので、バックグラウンドで。
それがユーザーのワークロードに影響がない形で行われているかみたいなところで、ディスクのメトリクスはもちろん重要となってきます。
それからここら辺からちょっとLSMツリーに特化したメトリクスになっていきますね。
まずSSテーブルについて見ていきましょう。
SSテーブルのファイルの数とか合計サイズというのはこれも監視対象ですね。
特にSSテーブルどんどんどんどん作られていくので、SSテーブルのファイルのスパイクと言いますか増加というのはコンパクションが追いついていないということを示すので、
読み込み性能の折下とか、Ioの増加とかディスク利用量の圧迫につながるので、SSテーブルの作られ方についても見ていく必要がありますよね。
部屋の中にどんどんどんどんフォルダーが作られて、いつの間にか気づいたら部屋の中がしっちゃかめっちゃかになってしまっていたみたいなのを避けたいので、
すでに部屋の中に置いてある本棚を超えそうなぐらいフォルダーを作らなきゃいけないとなったら早めにアラートされたいですね。
それからメモテーブル側ですね。メモテーブル。メモリ関連で言うと、メモテーブルがどれくらい使われているか、あとはそのキャッシュのヒット率とか、あとはバファプールのサイズとかですかね。
メモテーブルがあふれているというのはディスク書き込みをどんどん誘発しますから、例えばそこがあえて低い場合はディスクから読み込みが増えてしまうということで、
例えばメモテーブルに使っているメモリが足りないのかなとかそういったそのコンフィグレーションのチューニングポイントになってくるので、メモテーブル自体ももちろん見ていきます。
最後にメジャーなところで言うとコンパクションですね。
コンパクションのキューのサイズとか実行時間というのもこれも重要なメトリックスになってきます。
コンパクションというのは先ほども説明した通り、LSMツリーの読み込みと書き込みのバランスを保つすごい重要なチューニングポイントで、ここら辺のバックグラウンドで起こっているコンパクションがヘルシーに、健康的にというか問題なく動いているということを確認する必要があります。
せっかくROCKS.TVの説明をしているので、このROCKS.TVのLSMツリーの中でも特に重要なイノベーティブなというか考え方を説明しようと思うんですけど、先ほどSSテーブルの話をしたんですけど、ROCKS.TVがペーパーでおそらく僕の理解では初めてROCKS.TV側かな、入れたのかな、もしかしたらレベルDBかもしれません。間違ってたらごめんなさい。
少なくともROCKS.TVで実装されている概念としてあるのがレベルドSSテーブルです。レベルドSSテーブル。レベルドというのは階層化されたという意味ですね。RPGのレベルと一緒です。
これはどういうことかというと、SSテーブルをデスデータとしてディスクに書き込むときに複数のレベルに分けて格納するということですね。
具体的には新しいデータをまずメモテーブルから一定のサイズにするとディスクにフラッシュされるとなりました。このときにレベルはゼロです。
ROCKSDBとLSMツリーの分析
このレベルゼロのSSテーブルというのはどんどんどんどんコンパクションをしていくたびにレベル1,レベル2というより大きなSSテーブルにどんどんコンパクションされていくんですね。
このレベルごとによってSSテーブルの大きさとか中に入っているキーのフレッシュネスが違ってくるので、これを活用することによって例えばコンパクションするときとか読み込みするときとかに効率的にSSテーブルを整理したり活用することができるとなっています。
このレベルドな構造とかコンパクションの仕組みというのがROCKSDBが高い書き込み性能とか効率的な読み込みを両立させる肝となっています。
このROCKSDBですけれども、なかなかいい意味で枯れた技術となってきているんじゃないでしょうか。
Facebookだけではなくていろんな大きなエンタープライズ企業でバチバチにプロダクションレベルで戦ってきたデータベースなので、その高性能とか柔軟性とかレジリエンシーの観点から他のいろいろなオープンソースとかエンタープライズプロダクトの基盤として採用されています。
さっきもチラッと言ったように、MySQLのストレージエンジンとしてROCKSDBを総合した、これも同じくFacebookから出ているMyROCKSはなかなか有名ですね。
これはそのB2DベースのinnoDBと比較してストレージ使用量を大幅に削減して書き込みスループと向上させるぞということで、ROCKSDBをベースで使ってみたというところで、これと同じ発想のものがいろいろ使われています。
例えば、代表的な例としては、分散SQLデータベースとして最近名前をよく聞くTIDBっていうのもROCKSDBをストレージエンジンとして利用していますね。
確かTyKBだったかな。ROCKSDBはキーバリューストアなので基本的にはキーとバリューでやりとりするんですけども、TIDBのストレージエンジンのベースとしてもTyKBは確かROCKSDBで使われているはずです。
TIDBはMySQL互換の分散型データベースなんですけども、おそらくROCKSあたりから発想を得たんじゃないでしょうか。
もちろんMySQLだけではなくて、Postgres互換のクエリエンジンを提供している別のものとしてはUGByteDBというのもあります。
UGByteDBもROCKSDBをストレージ層に採用していて、このUGByteDBの創業者というのは確か元Facebookのエンジニア2人だったんじゃないかなと思います。
確かROCKSDB、それこそ開発メンバーだったんじゃないかなと思います。
UGByteのDocsのどこかに書いてた気がしますけれども、これも全く同じようなTIDBと同じようなアーキテクチャですよね。
ストレージエンジンをROCKSDBに置き換えてディストリビューティッドなデータベースとして、
クエリエンジンのレイヤーをよく使われるMySQLとかPostgres互換でやってますってことですよね。
他にもいろんなところで使われているROCKSDBなので、ROCKSDB組み込みとしては単なるデータベースだけではなく、
なかなか使えるコンポーネントとして知っておくといいんじゃないかなと思います。
ということで、LSMツリーのサマリと、それを実際に使っているプロダクトとしてのROCKSDBについて簡単に紹介してきました。
最後にですね、BookClubで盛り上がった観点を紹介して終わろうかなと思います。
今回のBookClubでも非常に活発な議論が交わされましたね。
特に前半、データベースインターナルズは第一部と第二部に分かれているんですけれども、第一部の一番最後の章でした。
第一部は振り返ると単体のノードで動くデータベースのコンポーネントということで、B3の実装とかLSMツリーについて話してきたんですけれども、
最初はB3を学び、B3のプロダクションでの使い方とか、B3のAshを学び、
B3では解決できなかった課題を解こうとしているLSMツリーを学ぶということで、
かなりいろんなデータ構造とかアルゴリズムを学んできたんじゃないかなと思います。
いきなりLSMツリーを読んでも分からないんですけれども、データベースインターナルズを第一章からゆっくり読むことで、
LSMツリーが出てこざるを得なかったこの歴史というのを納得してもらったリスナーの参加者の方が多かったんじゃないかなと思います。
やっぱり一番のトピックとしては、B3とLSMツリーのトレードオフに関する議論でしたね。
自分が担当しているサービスのワークロードはRead HeavyなのかWrite Heavyなのかとか、
それだったらどっちのベースとしたデータベースが使われるのかみたいなところに考えながら議論できたところは良かったかなと思います。
実践的な視点での意見交換が多かったんじゃないかなと思います。
あとは、LSMツリーの実装について多かったので、コンパクションについてちょっと詳しく見てみましたとか、
自分が使っているアプリケーションと絡めて調べてみたりみたいな方も多かったですね。
さて、次回に向けてです。
第1部終わりました。
Database Internalsをこの収録と一緒に読んでくれていた参加者の皆さんは一旦、小休止ということでお疲れ様でした。
第1部読み切ったところで一旦達成感をぜひ味わってもらって、50%読んだのでここで小休止しつつ、
次回チャプター8の簡単な紹介についてしていこうかなと思います。
チャプター8は第2部の最初の章ですね。
これまでBツリーとかLSMツリーとかデータを効率的に管理するためのデータ構造について学んできたんですけれども、
次はちょっとガラッと変わります。
Distributed Systems Introduction and Overviewということで、分散システムの紹介と外観って感じかな。
というところで、第2部がDistributed Systemsの内容になっていくので、分散システムにおけるハイレベルな議論となってますね。
ビザンチン将軍の問題とか、トゥージェネラル問題とか、分散システムの落とし穴、どういったフェーラーモードがあるかみたいなところになってくるので、
ぜひぜひ一緒に引き続きチャプター8も読んでいきましょう。
はい、ということで振り返りは以上にしようと思います。
今回はチャプター7、LSMツリーについて、その基本的なアーキテクチャとBツリーとの対話を交えながら振り返りました。
分散システムの紹介
ROCKS TVについても紹介しました。
じゃあ次はチャプター8の振り返り収録でお会いしましょう。
それでは皆さん、Have a nice day.
I think I like it, but I, but I don't want it.
Can't open all this, all this, and I can't be here for all this time.
I'd rather not be left alone.
