← ./posts
· yuta

RDBMSを自作して学ぶ：第15章 さらに学ぶために

#database#rdbms#go

前回は、作ったデータベースをPostgreSQL・SQLite・MySQL（InnoDB）と比べ、対応関係と省略した機能を整理しました。今回はシリーズの最終回です。ここまでの内容をさらに深めるための書籍・講義・論文、実際のデータベースのソースコードを読むときの道しるべ、そして分散データベースの世界へ進むための道筋を紹介します。

書籍と講義

Database Internals（Alex Petrov、O’Reilly、2019年）

ストレージエンジンと分散システムの2部構成で、データベースの内部を解説した本です。第1部では、B木の実装上の工夫、バッファ管理、WALとリカバリ、LSM木などを扱っていて、本シリーズの第3〜6章と第12章の内容をさらに掘り下げられます。第2部では、レプリケーション・合意形成・分散トランザクションを扱っているので、分散データベースに進む準備にもなります。日本語訳は『詳説 データベース』（オライリー・ジャパン）です。

Designing Data-Intensive Applications（Martin Kleppmann、O’Reilly、2017年）

データを扱うシステム全体の設計を、データモデル、ストレージ、レプリケーション、パーティショニング、トランザクション、ストリーム処理まで幅広く解説した本です。第7章のトランザクションの章は、分離レベルごとに起きる異常を具体例でていねいに説明していて、本シリーズの第10・11章と合わせて読むと理解が深まります。日本語訳は『データ指向アプリケーションデザイン』（オライリー・ジャパン）です。

Database System Concepts（Silberschatz・Korth・Sudarshan、McGraw-Hill）

データベースの定番の教科書です。関係代数とSQL、問い合わせの処理と最適化、トランザクション、同時実行制御、リカバリ（ARIESを含む）までが体系的にまとまっています。本シリーズで「本シリーズでは省略します」と書いた部分の多くは、この本で理論から学べます。

CMU 15-445/645 Database Systems

カーネギーメロン大学の、データベースの内部構造を扱う講義です。講義動画と資料が公開されています。バッファプール、B+木、クエリの実行、同時実行制御、リカバリと、本シリーズとほぼ同じ順番で進みます。課題では、BusTubという教育用のデータベース（C++）に、これらのコンポーネントを実装していきます。本シリーズをGoで一通り作った後にBusTubの課題に挑戦すると、同じテーマを別の設計で実装し直すことになり、よい復習になります。

Architecture of a Database System（Hellerstein・Stonebraker・Hamilton、2007年）

プロセスモデル、パーサ、オプティマイザ、ストレージ、トランザクションといった、実際のデータベースを構成する要素を1本の論文で概観した解説です。本シリーズで作った部品が、実際のデータベースの中でどう組み合わされているかを俯瞰するのに向いています。

論文

本シリーズで扱ったテーマの原典や、重要な論文を紹介します。どれも、データベースの教科書で必ず参照される論文です。

ストレージとインデックス

クエリ処理

トランザクションとリカバリ

OSSのソースコードを読む

自分でデータベースを作った後は、実際のデータベースのソースコードが格段に読みやすくなっています。「バッファプールはどこだろう」「ページLSNはどう使われているだろう」と、探すべきものがわかっているからです。

SQLite

SQLiteはC言語で書かれた、小さく読みやすいデータベースです。公式のソースコードはFossilというバージョン管理システムで管理されていますが、GitHubにもミラー（https://github.com/sqlite/sqlite）があります。

ファイル 内容 本シリーズとの対応
src/btree.c B+木（テーブルとインデックス） 第5・6章
src/pager.c ページキャッシュ、ロールバックジャーナル、トランザクション 第4・12章
src/wal.c WALモード 第12章
src/parse.y SQLの文法（パーサ生成器Lemonで処理される） 第7章
src/where.c クエリプランナ（WHERE句の解析とインデックスの選択） 第8章
src/vdbe.c バイトコードを実行する仮想マシン 第8章

SQLiteは、設計ドキュメントも充実しています。

PostgreSQL

PostgreSQLは規模の大きいプロジェクトですが、ディレクトリの構成が機能ごとに整理されていて、目的のコードを探しやすくなっています。こちらもGitHubにミラー（https://github.com/postgres/postgres）があります。

ディレクトリ・ファイル 内容 本シリーズとの対応
src/backend/storage/smgr/md.c ファイルへのページの読み書き 第3章
src/backend/storage/buffer/bufmgr.c、freelist.c 共有バッファとクロックスイープ 第4章
src/backend/storage/page/bufpage.c ページと行ポインタの操作 第5章
src/backend/access/heap/heapam.c ヒープへの挿入・削除・更新 第5章
src/backend/access/nbtree/ B+木（nbtree） 第6章
src/backend/parser/gram.y SQLの文法（Bison） 第7章
src/backend/optimizer/ コストベースのプランナ 第8章
src/backend/executor/nodeSeqscan.c、nodeIndexscan.c、nodeNestloop.c 各オペレータ 第8章
src/backend/storage/lmgr/lock.c、deadlock.c ロックとデッドロック検出 第11章
src/backend/access/transam/xlog.c、xlogrecovery.c WALとリカバリ 第12章

PostgreSQLのソースコードには、ディレクトリごとに設計を解説した README が置かれていることがあります。例えば src/backend/access/nbtree/README はB+木の並行制御、src/backend/storage/lmgr/README はロックマネージャ、src/backend/access/transam/README はトランザクションとWALの設計を説明していて、コードを読む前の地図として非常に役立ちます。

コードリーディングのコツ

1. 知っている機能から入る

いきなり全体を読もうとせず、「INSERTしたときにページのどこにタプルが入るか」のように、本シリーズで実装した機能に対応する部分から読み始めます。自分の実装と比べながら読むと、「なぜこうしているのか」という疑問が自然に湧き、それが理解の手がかりになります。

2. テストとドキュメントから逆引きする

SQLiteは test/ ディレクトリに大量のテストを持っています。関数がどう使われるかは、テストから逆引きするとわかりやすいことがあります。

3. 変更の履歴をたどる

コードがなぜ今の形になったのかは、変更の履歴に残っています。PostgreSQLのコミットメッセージは、変更の理由がていねいに書かれていることが多いです。

git log -p --follow src/backend/access/nbtree/nbtsearch.c   # ファイルの変更履歴
git blame src/backend/access/nbtree/nbtsearch.c             # 各行を最後に変更したコミット

4. デバッガで処理を追う

デバッグ用にビルドして、デバッガで実際の処理の流れを追うのが、最も確実な理解の方法です。例えばSQLiteなら次のようにします（macOSでは gdb の代わりに lldb を使います）。

./configure --enable-debug
make
gdb --args ./sqlite3 test.db "INSERT INTO t VALUES (1)"
(gdb) break sqlite3BtreeInsert
(gdb) run

次のステップ ── 分散データベースへ

1台のマシンを超えるときに起きる問題

本シリーズのデータベースは1台のマシンで動きます。現代のWebサービスでは、データを複数のサーバーに複製したり分割したりすることが一般的で、そこでは1台のときにはなかった問題が現れます。

レプリケーション（複製）

同じデータを複数のサーバーに持たせ、1台が故障してもサービスを続けられるようにします。PostgreSQLのストリーミングレプリケーションは、第12章で実装したWALを別のサーバーに送り、そこでREDOすることで複製を作っています。

プライマリ                      スタンバイ
  │ WALを書く                     │
  └──── WALを送る ──────────────▶│ WALをREDOする

複製が複数あると、「どのサーバーが最新か」「書き込みをどのサーバーで受け付けるか」をサーバー同士で合意する必要が出てきます。これが**合意形成（コンセンサス）**の問題で、PaxosやRaftといったアルゴリズムが使われます。

シャーディング（分割）

1台に収まらないほどデータが増えたら、テーブルをキーの範囲などで分割し、別々のサーバーに置きます。すると、複数のサーバーにまたがるトランザクションを原子的にコミットする必要が生じます。代表的な方法が**2相コミット（2PC: Two-Phase Commit）**です。第11章の2相ロック（2PL）とは名前が似ていますが、まったく別の仕組みです。

CAP定理

ネットワークが分断されたとき、分散システムは「すべてのノードが一貫したデータを返す（Consistency）」と「すべてのリクエストに応答し続ける（Availability）」を同時には満たせない、という定理です。分断耐性（Partition tolerance）の頭文字と合わせてCAP定理と呼ばれます。分散データベースは、分断が起きたときにどちらを優先するかを選んで設計されています。

学習ロードマップ

本シリーズ（単一ノードのRDBMS）
  │
  ▼
LSM木とキーバリューストア（RocksDB、Pebble）
  │
  ▼
レプリケーションと合意形成（Raft）
  │
  ▼
分散トランザクション（2PC）とシャーディング
  │
  ▼
NewSQL（Spanner、CockroachDB、TiDB）のアーキテクチャ

読んでおきたいOSSと論文

OSS

CockroachDB・etcd・Pebble・TiDBのSQL層はGoで書かれているので、本シリーズを読み通した方にとっては、コードを読み始めるハードルが低いはずです。

論文

シリーズを振り返って

本シリーズでは、Goでリレーショナルデータベースを一から実装してきました。

部 章 作ったもの
第1部 基礎 第1・2章 全体像の整理、プロジェクトの準備
第2部 ストレージエンジン 第3〜6章 DiskManager、BufferPoolManager、ヒープファイル、B+木
第3部 SQLエンジン 第7〜9章 Lexer・Parser、Planner・Executor、カタログ
第4部 トランザクション 第10〜12章 TransactionManager、LockManager、WALとリカバリ
第5部 まとめと発展 第13〜15章 CLI、ベンチマーク、実際のデータベースとの比較

WriteAt でファイルにページを書くところから始めて、最後には、kill -9 で強制終了してもコミットしたデータが失われないデータベースが完成しました。

業務でデータベースを使うときの見え方も、きっと変わっているはずです。COMMIT が返ってくるまでの数ミリ秒の間にWALのfsyncが行われていること。EXPLAIN に出てくる Seq Scan と Index Scan が、第8章で作ったSeqScanとIndexScanと同じ考え方であること。主キーで検索すると速いのは、B+木が数回のページ読み込みで目的の行にたどり着けるからであること。デッドロックのエラーが返ってきたとき、データベースの中では待機グラフの閉路が見つかっていること。

データベースは「魔法のブラックボックス」ではありません。一つひとつは、ここまで自分の手で作ってきたような、理解できる仕組みの積み重ねです。このシリーズが、データベースの内側に興味を持つきっかけになれば幸いです。最後まで読んでいただき、ありがとうございました。