📚

Database Internalsを輪読している話

2020/12/23に公開

この記事は自作DBMS Advent Calendar 2020の23日目です。このアドカレは全国100万人のDB自作勢がノウハウを共有してくれるものですが、当記事では「将来的に自分もDBを開発したい！」という方向けに（？）役立ちそうな書籍を紹介します。

Database Internalsとはどんな本か？

タイトル通り、データベースの内部構造に関する本です（2020年の年末時点では翻訳版は未発売）。

著者の書籍紹介ページにあるように、データベースの基本的な概念を解説することに焦点が当てられており、DBMSの開発者や知識欲が旺盛なDBエンジニアを対象読者としています。

This book’s main intention is to introduce you to the cornerstone concepts and help you understand how databases work.（訳：この本の主な目的は、基本的な概念を紹介し、データベースがどのように機能するかを理解するのに役立つことです。）

ただし、基本的＝簡単ということでは全くありません。
例えば、良くデータベースのインデックス構造として紹介されるB-Tree（またはB+Tree）が、どのような論文に基づいていて、各DBMSでどのように実装されているかを知っているでしょうか。
少なくとも私はデータ構造として概念を把握していたものの、アカデミックな視点や実装面で深く知ろうとはしてきませんでした。

この本では以下の構成で、その名の通り、Database Internalsに深く切り込みます。

Part1. Storage Engines
データベースが物理的にデータを保存するためのもろもろの機能をストレージエンジンと呼びますが、その中で使われている様々な技術が紹介されています。
過去からリレーショナルなDBMSで使われてきたB-Tree、そしてNoSQLなどで使われることで注目を浴びたLSM-Treeまで詳細な解説がされており、データ構造だけでなくトランザクションやリカバリとの関係も併せて説明されます。

Part2. Distributed Systems
現代のデータベースでは単一ホストで必要な処理量を捌くことが難しく、分散DBの形で提供されることが多くなってきています。各クラウドベンダから提供されるDBaaSはその典型と言えるでしょう。
そうした分散DBの理論的背景となる、分散システムの基本的な仕組みについて順を追って解説し、最終的に分散トランザクションやコンセンサスの概念の詳説に至ります。

前述の著者ページにあるように、このDatabase Internalsでは100を超える論文やデータベース界隈では著名な書籍へのリファレンスが載っています。実際に読んでいく中で理解が不足した部分はそうした原著にあたることが出来るというのも、この書籍の醍醐味の一つになるでしょう。

輪読会をしています

この本は翻訳されておらず、さらにデータベースに馴染みのあるエンジニアでも簡単に読みこなせる内容ではありません。

そこで2020年の5月から輪読会という形式で、30人程度が集まって少しずつ読み進めてきました。（輪読会の募集ページはこちら）

コロナ禍によりオンラインでの開催となりましたが、この書籍をお持ちの方であればどなたでも参加可能です。細かいルールは余り設けず、以下のようなことだけ決めて1月に2度ほど開催しています。

想定する参加者

データベースの内部構造に深い関心のある方
分散データベースを学びたい方
データベース管理や開発・設計の実務経験がある方
データベースの開発・研究・調査に従事されている方
「データ指向アプリケーションデザイン」等でデータストアについて関心を持った方

進め方

各自でDatabase Internals（紙 or 電子書籍）を準備し、その日の対象章を読んでおいて下さい。
各回ごとに1章、または2章ずつ読み進め、議論をしていきます。
1章ごとに発表者を1名立てます。難解な章については2名に分けることも考えます。
発表後に疑問点や気になる点について議論を行います。
発表、議論は基本的に日本語で行います。

2020年は13回開催し、11章まで輪読を終えました（全部で14章の書籍です）。

発表者は都度募っていますが、どの方も意欲が高く、各自の専門知識に根ざした素晴らしい発表をしてくれています。現在のスケジュールですと、残りの3章を読み終えるのが3月頃になりそうです。約1年間、18回程度の開催ということになるでしょう。

※なお、著作権を侵害しないよう、輪読会の発表資料は原則公開していません。

Part1.の内容を少しだけ

書籍の内容については、目次を見るだけでも雰囲気は掴めると思います。
ただ、輪読会の雰囲気を掴んで頂くためにPart1.の各章について、簡単な解説をしておきます。

B-Tree Basics

二分探索から始まり、B-Treeの基本的な構造を学んでいきます。

B-Treeはディスク上のデータ構造として古い歴史があり、学生時代に学んだ方も多いと思います。そのような基礎をおさらいする意味で、B-Treeのlookupやデータのinsert・deleteなどのアルゴリズムと、それに伴って発生するノードのsplitとmergeといったオペレーションが紹介されています。

File Formats

この章では、データベースでバイナリデータをストレージ構造としてどのように表現するかの説明から入り、それらを組み合わせてレコード（cell）、ページと徐々に大きく組成していく構成が解説されています。

データベースにとって、可変長のデータを効率的に扱うのは難しい問題です。この章ではOracleやPostgreSQLでも見られるSlotted Pageの概念が紹介され、データへのポインタと実データをどのように構成していくかについて学んでいきます。

Implementing B-Tree

この章では、実際にB-Treeを開発するにあたってどのような実装が必要かを説明しています。
例えば、以下のように細かい話題が展開されます。

ページヘダーをどう構成するか
B-Treeのノードを昇順―降順―隣接でどのように辿るか
1ページに納まらないレコードをどのように扱うか

さらにパフォーマンスにも影響を与えるリバランスやガベージコレクション（いわゆるVacuum）なども、どのように実装すべきかが示されます。

Transaction Processing & Recovery

トランザクション処理とリカバリはデータベースでも難しい（ゆえに面白い）部分の一つです。この章では単一ノード内のトランザクションに限定して、過去の論文から基本的な考え方を解説してくれます。

こちらのblogで紹介されているARIESや、様々な同時実行制御の方式が整理されていますが、個人的に目から鱗が落ちたのは以下の表現です。

ロック：論理整合性を担保し、キー単位で獲得される
ラッチ：物理整合性を担保し、ページ(ブロック)単位で獲得される

この辺りが好きな方には読むほどに味わい深い章だと思います。

B-Tree Variants

この章ではB-Treeの亜種として以下が紹介されています。

Copy-on-WriteなB-Tree（LMDB)
Lazy B-Tree（Wired Tiger）
FD-Tree
Bw-Tree
Cache-Oblivious B-Tree

これだけ見ても私も何のことだか分かりませんでしたが、それぞれが伝統的なB-Treeのどのようなデメリットを改善しようとしているのか、順を追って説明されています。
また、この章の発表をして頂いたtom_boさんのblogにも解説がありますので、こちらもご覧ください。

Log-Structured Storage

第一部の最終章はLog-Structuredなデータ構造の紹介になります。
CassandraやRocksDBで著名なLSM-Treeの構造、その長所やなぜ現在広く使われるに至ったかを大きく紙幅を割いて、詳細に解説しています。

特に私の好みの部分として、SSDのFTL（Flash Translation Layer）やOpen-Channel SSDについても、Log-Structuredと関連する技術として紹介されており、そうしたデバイスをデータベースで使いたい方には垂涎の内容となっています。

また、「Don't Stack Your Log on My Log」（日本語での紹介はこちらのスライドなど）の問題についても言及しており、今後Log-Structuredなストレージがどのような用途で使われるかについても、思いを馳せることが出来ます。

これまで見てきたように、第一部のStorage Enginesだけでも他の書籍にあまり見られない、データベースの内容を深く理解するにあたって、実用的な知識・ノウハウが数多く紹介されています。

第一部で議論した内容をいくつか紹介

輪読会では、RDBやNoSQLの開発者やそれらの有識者、ファイルシステムやSSDなどのデバイスに詳しい方など、多様な参加者が集まっているため、本論から離れた議論も魅力の一つです。

ここではいくつか輪読会中で議論となったトピックを上げておきましょう。もちろんこれらは何かしらの回答を出すものではありませんが、経験に裏打ちされた意見として（個人的に）非常に参考になりました。

そもそもDBを選ぶ時の基準ってなんなの？

某ベンダに所属していたので販売しているDBを使っていた。昔はそんなに選択肢もなかった。
どのDBを扱う技術者がいるのかという観点もあるし、顧客の要望もある。
業務要件がまずあって、それを満たすものを選定するのが理想。
書き込みが非常に多いケースではRDBが厳しい。その場合、Cassandraなどで捌く例も見てきた。
1種類のDBに拘泥する必要もない。用途に応じて使い分けるのが正解と思われる。

SSDについて

SSD自身が追記型で、ガベージの必要性などLSM Treeに近い構造に見える。
一時期、SSDの一部にSLCをキャッシュとして使う構成が流行ったこともある。
OpenChannel SSDはFTLなしの特殊なデバイス。
SSDでは、電荷が抜けた状態で長時間置いておくと次回の書込み時に化ける可能性がある。そのため、不要になってもすぐにデータを消さず、書く直前にブロックを消去する。

DBのキャッシュ設定について

キャッシュの容量ってどれぐらいあると良いのか？物理メモリの何%とか基準があるか。
DBMSごとに違いがある。postgresはカーネルキャッシュも必要なので25%などとドキュメントに記載がある。
HugePagesなどとも関連がある。
過去のLinuxカーネルでは共有メモリの上限に到達して、物理メモリをいくら積んでもPostgreSQLの共有バッファが増やせないケースがあった。

PostgreSQLには何故O_DIRECTのサポートがないのか

端的にいうと、だれもそうしたパッチを書いてないから。
PostgreSQLのストレージエンジンが物理レイヤまで理解しなくても良いようにしている。
ただ、最近はコミッタがO_DIRECTや非同期IOを積極的に使う話をしている。
現状あがっているのはio_uringとのこと。

その他にも紹介しきれないほど様々な議論があったのですが、今回はここまでとさせて下さい。

まとめ

さて、ここまで見てきたようにDatabase Internalsは基礎的な概念をとても深く掘り下げた、データベース開発者・エンジニアにとてもお勧めな内容になっています。年末年始のお休みに挑戦してみるのは如何でしょうか。

もし、Database Internalsを読んだうえで「この章については私も言いたい/聞きたいことがある！」という方は、ぜひ輪読会にお越しください。
現在進行中の会は残り数回ですが、もしかしたら第2ラウンドもあるかもしれませんよ？

余談

今回の輪読会はTwitter上で
「やってみようかな？」⇒いいね多数⇒「やりましょう！」
となったのですが、その中でDatabase Internalsの著者の方にも応援を頂きました（！）。
結果、著者の方から当書籍のステッカーをたくさんもらったのですが、オンライン開催となったこともあり、まだ1枚も配れていません。ぜひ来年はこれを皆さんにお渡ししたいですね。

また、英語の原著を読むことに関してですが、これは正直言って私もとても苦手です。それでも輪読会をこなすことで、1冊まるまる読み切ることが出来ました。
参加者の皆さまにはこの場を借りて、御礼申し上げます。