LoginSignup
45
40

More than 1 year has passed since last update.

@ryo_grid(Ryo Kanbayashi)

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

Last updated at Posted at 2022-05-10

ご無沙汰しています。
ryo_gridです。

Disclamer

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

この記事の目的

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

ハードコース

  • 英語スラスラ読めるし、とっかかりさえあれば自分でどうにかできるという方はこちら
  • 以下のページに Database System について学ぶための情報源がリストされているので、適宜参照しながら進められると良いでしょう
  • 以下の書籍で丸っと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氏 ですが、以下のようなものを執筆しているので、読んでおくと、後でああ、あの話かーという感じで役に立つかもしれません

オープンコースウェアで本格的なデータベースシステムの実装について学ぼう

  • ここについては以下の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 に相当するところの実装やフロントエンドの実装がありません
  • awesome-database-learning を参照して気合で実装するのも良いかもしれませんが、なかなか大変らしいです（筆者らもまだそこまで達していない）
  • というわけで、英語ではありますが以下の書籍を参考に実装するとよいらしいです

戦いはさらに続く

  • ここまでに挙げたものは基本的なところを、比較的一般的かつ、さほど難度の高くない手法で実装している認識ですが、RDBMSをより良いものにしようと思えば、やれることは際限なくあります
  • 例えば、logging/recoveryにおけるsnapshotにARIESなどを採用するというのもよいでしょう
  • そのあたりは awesome-database-learning など参照して各自追求していきましょう（一緒に）
  • あと、自作 (R)DBMSの世界で定番？なコンテンツとして通称redbook（赤本）と呼ばれる 『Readings in Database Systems』というものがありまして、その内容は押さえておくとよいのだろうと思います

余談

  • インデックスの実装にB+木が広く利用されているということで、ここまでに挙げた書籍でも採用されていることが多いですが、レコードの削除・更新および並行トランザクション実行における排他制御までサポートしようとすると途端に難易度が跳ね上がるそうです
    • それもあり、SamehadaDBでは 木構造ベースなインデックスの実装は後回しとする判断をしていたりします（2022/05/10 時点）
  • 従って、B+木でインデックスを実装してみるというのは学習という観点では良いことだと考えていますが、実用に耐えうるとは言わないまでも、基本的なSQLが通るものに仕上げようと思った際には地獄が待っているかもしれない、ということは念頭に置いておくとよいかもしれません
    • 排他制御に関してはテーブル単位で丸っとロックするといった対処も可能ですが、パフォーマンスは当然落ちます

交流の場（Slack）

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

enjoy！

45
40
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
45
40