← ./posts
· yuta

RDBMSを自作して学ぶ：第1章 データベースとは何か

#database#rdbms#go

RDBMSを自作しながら仕組みを学ぶシリーズを始めます。実装コードを書く前に、まず「データベースがなぜ必要なのか」「RDBMSの内部はどんなコンポーネントで構成されているのか」という全体像を押さえておきたいので、初回はその整理からまとめます。

データベースが解決する問題

ファイルに直接書けばいいのでは？

アプリケーションがデータを永続化したいとき、最も単純な方法はファイルに書き込むことです。たとえばユーザー情報をCSVファイルに保存するとします。

id,name,email
1,Alice,alice@example.com
2,Bob,bob@example.com

小規模であればこれで十分ですが、次のような要求が加わると途端に困難になります。

① 大量データへの高速アクセス

1,000万件のユーザーから特定のメールアドレスを探すとき、CSVを先頭から読んでいては時間がかかりすぎます。データベースはインデックス構造を使い、大量データでも高速に検索できます。

② 複数プロセスからの同時アクセス

Webサービスでは何十・何百ものリクエストが同時に発生します。複数のプロセスが同じファイルを同時に書き込むと、データが壊れる可能性があります。データベースはロック機構によってこれを防ぎます。

③ クラッシュ時のデータ保護

書き込みの途中でサーバーがクラッシュしたら、中途半端な状態のデータが残ります。データベースはトランザクションとリカバリ機構によって、クラッシュ後も一貫した状態に復元します。

④ 複雑なデータ操作の記述しやすさ

複数のテーブルを組み合わせた集計や絞り込みを自前で実装するのは大変です。データベースはSQLという宣言的な言語で複雑な操作を簡潔に記述できます。

データベースが提供するもの

まとめると、データベースは次の4つの問題を解決します。

問題 データベースの解決策
大量データへの低速アクセス インデックス（B+木など）
同時書き込みによるデータ破壊 ロック・同時実行制御
クラッシュ時のデータ消失 WAL・リカバリ
複雑なデータ操作の実装コスト SQL・クエリエンジン

これらの問題を解決するために、データベースは複数の専門的なコンポーネントに分かれています。次の節で全体像を見ていきます。

RDBMSのアーキテクチャ概要

RDBMSは大きく3つの層（レイヤー）で構成されています。

┌─────────────────────────────────────┐
│          クライアント（アプリ）         │
└──────────────┬──────────────────────┘
               │  SQL文
┌──────────────▼──────────────────────┐
│           SQL エンジン               │
│  ┌──────────┐  ┌──────────────────┐ │
│  │  Parser  │  │  Planner/Executor│ │
│  └──────────┘  └──────────────────┘ │
└──────────────┬──────────────────────┘
               │  内部API
┌──────────────▼──────────────────────┐
│       Transaction Manager           │
│  ┌──────────┐  ┌──────────────────┐ │
│  │   Lock   │  │   Log/Recovery   │ │
│  └──────────┘  └──────────────────┘ │
└──────────────┬──────────────────────┘
               │
┌──────────────▼──────────────────────┐
│         Storage Engine              │
│  ┌──────────┐  ┌──────────────────┐ │
│  │  Buffer  │  │   Disk Manager   │ │
│  │  Pool    │  │   + B+Tree       │ │
│  └──────────┘  └──────────────────┘ │
└─────────────────────────────────────┘
               │
          ディスク（ファイル）

上図はコンポーネント間の依存関係を示す概念図であり、実際の呼び出し順序（Executorがどの順番でLock/Log/Storageを呼ぶか）を厳密に表したものではありません。特にTransaction ManagerのLock/Log/Recoveryは、Executorがページやレコードにアクセスするたびに横断的に呼び出される仕組みで、SQL EngineとStorage Engineの間に一律に挟まる直列の中継層ではない点に注意してください。

Storage Engine（ストレージエンジン）

ストレージエンジンはデータの物理的な読み書きを担います。図中では省略していますが、HeapFileもDiskManagerが管理するページ上に構築される、テーブルデータの実体です。

SQL Engine（SQLエンジン）

SQLエンジンはクライアントから受け取ったSQL文を解析し、実行計画を立てて実行します。

Transaction Manager（トランザクションマネージャ）

トランザクションマネージャは、複数の操作をひとまとまりの単位として安全に実行するための仕組みを提供します。

実装する範囲と省略する範囲

このシリーズではRDBMSのコア部分をGoで実装していきます。実際のプロダクションDBと比べると省略している部分もあるので、最初に線引きをしておきます。

実装する範囲

コンポーネント 内容
DiskManager ファイルへのページ単位の読み書き
BufferPoolManager LRUキャッシュ
HeapFile / SlottedPage レコードの格納
B+木インデックス 等値・範囲検索
Lexer / Parser SELECT（WHERE・JOIN）/ INSERT / CREATE TABLE / BEGIN・COMMIT・ROLLBACK
Planner / Executor SeqScan, IndexScan, Filter, Projection, Nested Loop Join
Catalog テーブル定義の管理と永続化
TransactionManager BEGIN / COMMIT / ROLLBACK
LockManager テーブル単位のS/Xロック、厳格2相ロック（2PL）、デッドロック検出
LogManager WAL（Write-Ahead Logging）
RecoveryManager REDO / UNDOリカバリ、チェックポイント
CLI 対話的にSQLを実行するインターフェース

省略する範囲（発展的な内容）

省略する内容 理由
MVCC（Multi-Version Concurrency Control） 実装が複雑なため。概念は後の回で解説予定
クエリオプティマイザ（コストベース） 統計情報の管理が必要で規模が大きい
ネットワーク層（クライアント接続） DBの本質とは別の関心事
レプリケーション 分散システムの領域
UPDATE / DELETE 書き込みをINSERTに絞り、トランザクションとリカバリの仕組みに集中するため
NULL値 3値論理などで実装量が増えるため。型はINTとVARCHARだけを扱う

省略した機能については、シリーズの後半（第14章）で実際のOSSとの比較を交えながら触れる予定です。

参考にするOSS（SQLite・PostgreSQL）

実装の設計は以下のOSSを参考にしています。

PostgreSQL

PostgreSQLは高機能なオープンソースRDBMSです。コードベースは大きいですが、コンポーネントの分離が明確でアーキテクチャを学ぶのに適しています。

このシリーズのデータの持ち方は、PostgreSQLに近い設計です。特に以下の点を参考にしています。

SQLite

SQLiteはサーバープロセス不要で動く組み込み型RDBMSです。単一ファイルにすべてのデータを格納するシンプルな設計でありながら、本格的なRDBMSの機能を備えています。

SQLiteからは、主に次の点を参考にしています。

一方で、SQLiteはテーブルのデータそのものをB木に格納し、WALモードではページ全体をログに書くなど、このシリーズとは違う設計も多く採用しています。こうした違いは、シリーズの後半で比較します。

参考文献

まとめ

次回はGoのプロジェクトをセットアップし、実装を始めるための準備を書く予定です。