自作RDBMSやろうぜ!（Zenn出張版）
Zenn
🗂️

自作RDBMSやろうぜ!（Zenn出張版）

2022/05/27に公開
Database
DB
RDBMS
自作
tech

Disclamer

  • 本記事は自作DBMSやろうぜ！ のページの 22/05/27 JST 22:38 の時点での内容をZenn記事向けに修正して作成したものです
  • 元コンテンツのライセンスについては以下をご参照ください
  • 元コンテンツの方は更新が継続されていますので、よろしければそちらもご覧ください

この記事の目的

  • RDBMS（いわゆるリレーショナルデータベース）というものはプログラミング言語の処理系や、OSなどと同様に、世の中で広く使われているソフトウェアであるにも関わらず、いざ自作してみようと思うと日本語で記述されている必要な情報・情報源がまとまったサイトやブログ記事がないことに気づきました
  • そこで、叩き台として、筆者および数名のコミッタで開発している自作RDBMSである SamehadaDB が軌道に乗るまでの経験をベースに、自作RDBMSに関する情報をある程度整理して書き記してみました
    • 各々の情報・情報源はあいかわらず多くが英語で記述されていますが、その点はご容赦下さい
  • なお、本記事は技術的な解説を提供するのではなく、適切と思われる情報・情報源をポイントするに留めます

ハードコース

  • 英語スラスラ読めるし、とっかかりさえあれば自分でどうにかできるという方はこちら
  • 以下のページに Database System について学ぶための情報源がリストされているので、適宜参照しながら進められると良いでしょう
  • 以下の書籍で丸っとDatabase Systemに関する基礎知識と実装まで押さえるというのもよいと思います

段階的に進んでいこうコース（= おおむね筆者が歩んだ道）

  • いきなり英語とか辛いので日本語なサイトや書籍等で基本を押さえてから段階的に進んでいきます

自作RDBMSしてる方々のブログ記事などを読んで雰囲気を感じよう

Database Systemのアーキテクチャの概要などについて解説されている記事も含め、入門者にはありがたい情報がたくさんです

日本語の書籍で（Relational) Database System の基本について押さえよう

  • 北川 博之著 『データベースシステム 改訂2版』
    • 大学の情報系の講義などで用いられる教科書といった感じの書籍です
    • 実装寄りかと言えばそうでもないですが、基本を押さえておけば英語の情報にあたった時もなんとかなります
    • なお、筆者は後述の日本語な情報源の存在を知ったタイミングの関係から、本書のうちの、実装段階でひとまず必要そうな所に一通り目を通したところで次のステップに進みました
  • Alex Petrov 著、小林隆浩 監訳、成田昇司 訳『詳説 データベース -- ストレージエンジンと分散データシステムの仕組み』
    • タイトルからも分かるように全体としては分散データベースや分散ストレージエンジンにフォーカスした書籍です
    • しかしながら、全体の約半分を占める第I部は "分散していないデータベース" でもおおむね共通の内容に見えるので、分散DBMSにトライしようという方でなくても読んでおいて損はないと思われます
    • オライリーのサイトから電子版（pdfフォーマット）が購入可能です
  • KOBA789著 『WEB+DB PRESS Vol. 122 "特集3 作って学ぶ RDBMS のしくみ"』
    • 特集のタイトルの通り実装を追いながらRDBMSについて解説しています
    • rellyというシンプルなRDBMS実装について解説しており、コードはGitHubにあります
    • 日本語で書かれているという点で、大変貴重な記事なのですが、実装がRustなため、Rust経験者でない場合、コードの読解は少し苦労するかもしれません
    • WEB+DB PRESSは上のリンクから vol.122 だけのKindle版が購入できます
  • 筆者が自作RDBMSするにあたっていろいろとアドバイスをいただいている方の一人が kumagi氏 ですが、以下のようなものを書いてたりするので、読んでおくと、後でああ、あの話かーという感じで役に立つかもしれません

オープンコースウェア（※）を活用して本格的な RDBMS の実装について学ぼう

  • ※：大学や大学院などの高等教育機関で正規に提供された講義とその関連情報を、インターネットを通じて無償で公開する活動 (Wikipediaより）
  • ここについては以下のGitHubリポジトリにまとめておいたので、ひとまずそちらをご参照下さい
  • 筆者および数名のコミッタは、前出ですが、自作RDBMSとして SamehadaDB というものをちまちまと開発していますが、これは現状、上記のCMUの講義で扱っている教育用RDBMS実装 BusTubを C++ から Go言語にポーティングすることが主な作業となっています
    • brunocalza氏が先だって brunocalza/go-bustub というプロジェクトを進めていたため、全てのポーティングを筆者らが行ったわけではありません
    • なお、brunocalza氏は、時間が取れなくなったそうで、go-bustub プロジェクトは筆者らが fork するしばらく前から更新されておらず、今後更新できる見込みも無いとのこと
      • 現状、やっている作業がgo-bustubのやろうとしていたことに類似しているだけであって、プロジェクトを引き継いだわけではありません
    • 本家BusTubは講義の課題として実装の穴埋めをさせるように作られているため、歯抜けになっていますが、brunocalza氏及び筆者らはそれらの部分を埋める形でポーティングを行ったため、全てではないですが一応、一通り実装が行われています
    • 従って、手前味噌ですが、BusTub相当の機能までであれば、SamehadaDBのコードベースを参考にしていただくのも良いのではないかと思います
    • (Go言語にポーティングしているのは写経的な意味と、個人的にC++のまま拡張していくの辛いな・・・と思ったためです)

アドバンスドなところも実装していこう

  • BusTubには残念ながら planner/optimizer に相当するところの実装やフロントエンドの実装がありません
    • サーバとして動作させたいのであれば、DBコネクタ（DBドライバ）や REST API 等の、NW越しにクエリを投げて結果取得できるインタフェースも必要ですが、フロントがないのでこれも当然ありません
  • awesome-database-learning を参照して気合で実装するのも良いかもしれませんが、なかなか大変らしいです（管理人らもまだそこまで達していない）
  • というわけで、ハードコースの方で既出、かつ英語ではありますが、以下の書籍を参考に実装するとよいらしいです

戦いはさらに続く

  • ここまでに挙げたものは基本的なところを、比較的一般的かつ、さほど難度の高くない手法で実装している認識ですが、RDBMSをより良いものにしようと思えば、やれることは際限なくあります
  • 例えば、logging/recoveryにおける snapshot で ARIES などの fuzzy snapshot を実装してみるというのもよいでしょう
  • 実用を意識した場合、アクセス認証なども必要でしょうが、どのような方式に対応するか、認証データの保持周りの設計はどうすべきか、など考えてみると奥が深そうです
  • そのあたりは awesome-database-learning など参照して各自追求していきましょう（一緒に）
  • あと、自作 (R)DBMSの世界で定番？なコンテンツとして通称redbook（赤本）と呼ばれる 『Readings in Database Systems』というものがありまして、その内容は押さえておくとよいのだろうと思います

余談

  • インデックスの実装にB+木が広く利用されているということで、ここまでに挙げた書籍でも採用されていることが多いですが、レコードの削除・更新および並行トランザクション実行における排他制御までサポートしようとすると途端に難易度が跳ね上がるそうです
    • それもあり、SamehadaDBでは 木構造ベースなインデックスの実装は後回しとする判断をしていたりします（2022/05/10 時点）
  • 従って、B+木でインデックスを実装してみるというのは学習という観点では良いことだと考えていますが、実用に耐えうるとは言わないまでも、基本的なSQLが通り、かつ、あきらかな手抜き箇所がないものに仕上げようと思った際は地獄が待っているかもしれない、ということは念頭に置いておくとよいかもしれません
    • 排他制御に関してはテーブル単位で丸っとロックするといった対処も可能ですが、スループットは（少なくとも、同一テーブルのおおむね同一のレコード群に触る参照系と更新系の混ざった並列トランザクション実行では、）落ちます
  • ちなみに、B木（とその亜種）ベースのインデックスないしその手のものの設計・実装には様々なバリエーションがあるそうで、それらの解説だけで専門書が1冊存在するくらいです

その他の自作RDBMSに役立ちそうな情報源

  • MITのDATABASE SYSTEMS
    • MITのデータベースをスクラッチから作ってみようという講義
    • 2010年のもので時代を感じるが講義資料は公開されているし実装もあるように見える
    • Optimizerに関してもSelingerだけどちゃんと説明と実装があって良さそう

Database System に関連する情報源

  • ここでは、自作RDBMSというところからは離れてるかもーというものをリストしています
  • DBSJ最強データベース講義
    • 日本のデータベースシステム研究者の方々がおおむね自身の研究分野を講義風に整理して説明している動画が公開されています
    • どういう位置づけとして捉えるかは微妙ですが、Database Systemの世界も研究分野としては様々な方向性があるのだなー、というのを感じるには良いコンテンツのように思います
  • Database of Databases
    • 名前はわざとひねりをつけてこうしてあるのだろうと思いますが、要は Database System の Database（データ・情報の方）です
    • "オープンコースウェアを活用して本格的な RDBMS の実装について学ぼう" のセクションで紹介した講義の公開なども行っている Carnegie Mellon Database Group が運営しているサイトのようです
    • 誰しも知るプロダクトから、hobbyで開発されたようなものまで幅広く情報がインデックスされています
    • 各々がどのような設計をとっているか、機能をサポートしているかといった情報も（入力されていれば）あるようなので、何かの用事で比較が必要な場合は便利そうです
    • 自作(R)DBMS勢であればただダラダラ眺めても面白いかもしれません

交流の場（Discord）

  • 同好の士で交流を持てればと思い、『自作DBMS Discord』というものを作ってみました
  • 自作（R）DBMSやってる方、やってみたいと考えている方などなど、ご興味があればご参加ください
  • ROM専も可です
  • 招待リンク

enjoy！

Discussion