以下の内容はhttps://thinkami.hatenablog.com/entry/2024/12/14/223947より取得しました。

書籍「Database Design and Implementation」の SimpleDB をベースに、必要最低限の機能を持つ RDBMS を Ruby で実装してみた

Ruby

2024年はカンファレンスや個人ブログにて自作RDBMSの話をよく見かけたこともあり、昔からあった「いつかはRDBMSを作りたい」という気持ちがさらに高まった年でした。

　

そんな中、会社の合宿で行うLTの募集がありました。「LTに向けて締切駆動開発することで、RDBMSを作り切れるのでは」と考えて、RDBMSを作ることにしました。

そこで、RDBMSを必要最低限の機能で作ったところ、なんとか1ヶ月で形にできました*1。

　
ただ、初めての自作RDBMSだったこともあり、色々考えたり調べたりしたことがあったことから、メモを残します。

　

目次

　

環境

  • WSL2
  • Ruby 3.3.5
    • 当時、RubyMineがRuby 3.3.6 だとうまくデバッグできなかったことから、3.3.5を使いました

　

RDBMSを作る前に読んだ資料

まずはKaigi on Rails 2024のスライド「作って理解する RDBMSのしくみ」を読みました。図が多用されていて分かりやすかく、RDBMSに必要な機能の全体像をつかむことができました。
作って理解する RDBMSのしくみ - Speaker Deck

　
次に「自作RDBMSやろうぜ!」のサイトを読みました。
自作RDBMSやろうぜ! | 　

RDBMSを自作するときに必要な資料がまとまっていて、とても参考になりました。ありがとうございました。

　
この「自作RDBMSやろうぜ!」サイトでは色々なRDBMSの実装が紹介されていました。自分の場合は

  • 「理論→実装」のような形で解説があるもの
  • 自分が読めるコードで書かれているもの

で実装されているRDBMSが良さそうと感じました。

そこで、Edward Sciore著「Database Design and Implementation Second Edition」(以降、SimpleDB本) をベースに実装することにしました。
Database Design and Implementation: Second Edition | SpringerLink

　

SimpleDB本は、

  1. 一般的なRDBMSにおける構造・機能
  2. SimpleDBで採用した構造・機能
  3. SimpleDBの実装

という流れが繰り返されて説明が進むことから、理論から知りたい身にとってはとてもわかりやすく感じました。

また、著者のサイトからSimpleDBのソースコードをダウンロードできるのも良かったです。
The SimpleDB Database System

ソースコードにはSimpleDBの実装に加え、動作確認用のコードも含まれています。そのため、IDEで実装・動作を確認しながら読み進めることができました。

　
一方、

  • SimpleDB本は458ページほどある
  • SimpleDB本の動作確認用コードにはassertionが含まれないため、たとえ動作したとしても正しく動作しているか分からない

ということもあり、LTまでにすべてを実装し切るのは難しそうでした。

　
そこで、より小さなRDBMS実装を探してみたところ、WEB+DB Press Vol 122 の relly がありました。

　
規模的に relly を再実装することも考えました。その場合、雑誌では使うだけだった B+Tree インデックスを実装する必要があり、これはこれで時間がかかりそうでした。

　

今回作るRDBMSの実装方針について

ここまで見てきた通り、「2つのRDBMS実装のどちらかを、そのまま再実装してみる」というのは時間的に厳しそうでした。

そこで今回は

  • SimpleDB本をベースの実装にする
  • 「自分が欲しい最低限の機能」以外は削る
    • 削り方については relly を参考にする

という方針で実装することにしました。

　
では、「自分が欲しい最低限の機能」とは何かを考えたところ、以下のSQLが実行できることでした。

  • CREATE TABLE できる
  • INSERT できる
  • UPDATE できる
    • SimpleDB本同様、1項目のみ
  • SELECT できる
    • JOINなしで良い
  • WHERE で絞り込みできる
    • SimpleDB本同様、完全一致のみ

　
また、最低限の機能ということであれば、普通のRDBMSに求められるACID特性やパフォーマンスも気にせずに済みそうです。

ということは、

などの実装も不要として良さそうです。

　
ここまででだいぶ身軽になったため、後は実装を進めることにしました。

　

何の言語でRDBMSを作るか

実装する機能の範囲が決まったので、次は何の言語で作るかを決めます。

SimpleDB本の実装はJavaですが、調べてみたところ、他にも複数の言語実装がありました。

　
これらの実装はいずれも静的型付け言語です。一方で、動的型付け言語でもRDBMSは実装できそうと考えました。

そこで今回は Ruby で実装することにしました。

　
また、Rubyで実装するからには

  • irb (REPL) で動かす
  • gem化する
  • Minitestでテストコードを書く

も実現してみることにしました。

　 　

SimpleDBの機能をRubyで実装したときのメモ

以降では、Rubyで実装したときのメモや、SimpleDB本と比べて制限した内容などをメモしていきます。

　

Disk and File Management

このレイヤは relly をベースに実装しました。

そのため、

  • SimpleDBの FileMgr クラスがない代わりに、 DiskManager クラスが存在する
  • FileMgr クラスでは複数ファイルを扱えたが、 DiskManagerクラスでは1ファイルしか扱えない
    • この違いにより、今回のRDBMSで扱うファイルが増えれば増えるほど、DiskManagerクラスのインスタンスが必要になる
  • FileMgr はブロック・ページという概念でのアクセスだが、DiskManagerは 4096バイト固定のページという単位でのアクセスとなる

となっています。

　
また、今回、Rubyでファイルを操作する場合は

としました。

　

Memory Management

このレイヤも relly ベースの実装です。

そのため、

となっています。

　

Transaction Management

rellyの実装に寄せた都合上、トランザクションに関係するものは、いずれも実装していません。

そのため、SimpleDB本にあった

  • Transaction
  • RecoveryMgr
  • ConcurrencyMgr

をはじめとするクラス群 ( tx ディレクトリ内にあるクラス群) はありません。

　

Record Management

これ以降のレイヤはSimpleDB本の実装をベースとしました。

今回は

  • SimpleDB本にあった Slot という概念は取り入れていない
    • 1ページを複数 Slot には分けず、1ページを1レコードとして扱う
      • ページをあふれたときのことは気にしない
  • SimpleDB本同様、Homogeneous 形式とする
    • 1ファイルには同じテーブルのレコードしか保存しない

という実装としました。

　

また、このレイヤにて、Rubyの型(IntegerやString) とバイナリ間でデータ変換を行っています。

そのため、SimpleDBのJava実装と比べると、IntegerやStringの取得・設定系のメソッドは以下の実装のような小細工をしています。

なお、SimpleDBのJava実装と比較しやすいよう、わざとRubyっぽくないメソッド名としています。

def get_int(field_name)
  field_position = layout.offset(field_name)

  buffer = buffer_pool_manager.fetch_page(page_id)
  v = buffer.page[field_position...field_position + layout.integer_byte_length]
  v.pack('C*').unpack1('C*')
end

def get_string(field_name)
  field_position = layout.offset(field_name)
  field_length = layout.schema.field_length(field_name)

  buffer = buffer_pool_manager.fetch_page(page_id)
  v = buffer.page[field_position...field_position + field_length]

  # ゼロ埋めしてあると適切な文字にならないので、末尾の0を削除
  v.pop while v.last == 0
  v.pack('C*')
end

def set_int(field_name, value)
  field_position = layout.offset(field_name)

  buffer = buffer_pool_manager.fetch_page(page_id)
  buffer.page[field_position...field_position + layout.integer_byte_length] = [value].pack('C*').bytes
  buffer.is_dirty = true
end

def set_string(field_name, value)
  field_position = layout.offset(field_name)
  field_length = layout.schema.field_length(field_name)

  buffer = buffer_pool_manager.fetch_page(page_id)

  new_value = Array.new(field_length)
  new_value[0...value.bytes.size] = value.bytes

  # values.byteの長さが足りない場合全体が縮まってしまうので、不足分だけ末尾に要素 0 を追加する
  buffer.page[field_position...field_position + field_length] = new_value.map { |v| v.nil? ? 0 : v }
  buffer.is_dirty = true
end

　
ちなみに、小細工をしている都合上、 int型の項目は 0 - 255 の範囲のみ設定可能です。範囲を超えると不具合が発生します。

また、今まで利用したことのないメソッド

が利用できたのは良い経験でした。

　

Metadata Management

SimpleDB本では

  • Table Metadata
  • View Metadata
  • Index Metadata
  • Statistical Metadata

などのMetadataを管理していましたが、今回は Table Metadata のみ必要でした。

また、Record Management で Slot を実装しなかったことから、今回は Table Metadata のうち、各テーブルの各項目の定義を持つMetadata (Field Catalog) のみ実装しました。

　

Query Processing

このレイヤはSimpleDB本と同等の機能を実装しました。

　

Parsing

このレイヤもSimpleDB本と同等の機能を実装しました。

字句解析のところで、SimpleDB本はJavaの StreamTokenizer を使っていました。

一方、今回の実装ではRubyの StringScanner を使って実装しました。 StringScanner を使うのは初めてだったため、メモは別記事に残しました。
RubyのStringScannerを使って、文字列をスキャンしてみた - メモ的な思考的な

　
また、getterとsetterしかないクラスがあったため、RubyのDataクラスを用いて実装しました。
class Data (Ruby 3.3 リファレンスマニュアル)

今回はモジュール階層を持つクラスとしたかったため、以下のような実装となりました。

# frozen_string_literal: true

module SimpleRubyDb
  module Parse
    CreateTableData = Data.define(:table_name, :schema)
  end
end

　

Planning

インデックスなどを実装していないため、ベーシックなPlanのみ実装しています。

そのため、SimpleDB本の OptimizedProductPlan は実装していません。

　

テストコード

今回、なるべくgemを追加せずに実装したかったことから、テストコードは Minitest で実装しました。

また、前述の通り、SimpleDB本の動作確認コードにはassertionがなく、テストコードとしては不十分です。

そこで、assertionを含むテストコードが実装されていたGoやRustのリポジトリを参考にしながら、 Minitest のテストコードを実装しました。

　

Gem化する

パーフェクトRuby 改訂2版を参考に、Gem化しました。
改訂2版 パーフェクトRuby：書籍案内｜技術評論社

　

動作確認

Gem化したRDBMSをインストールし、irbで起動して動作確認してみます。

　
irb を起動します。

001で require し、 006で CREATE TABLE しています。

　
次にINSERTでデータを登録します。

今回は200件のデータを登録します。 a 列には index の 1/10 を設定するため、各レコードの a 列の値は 0 から 19 の範囲になります。

　
INSERT結果を確認します。WHERE句で a = 10 のレコードに絞ると、想定通りの内容が表示されました。

　
続いて、 a = 10 のレコードを更新します。今回は b 列に updated という値を設定します。

　
UPDATE結果を確認します。a 列が 10 のレコードは、いずれも b 列が更新されていました。良さそうです。

　

おわりに

SimpleDB本を通読し、必要最低限のRDBMSを実装したことで、RDBMSの内部構造に少しだけ詳しくなりました。

せっかく作ったので、今後も少しずつ機能を追加できればと思います。

　

ソースコード

GitHubに上げました。
https://github.com/thinkAmi-sandbox/simple_ruby_db

今回のプルリクはこちら。
https://github.com/thinkAmi-sandbox/simple_ruby_db/pull/1

*1:ちなみに、この記事はそのLT向けに作ったスライドをベースにしています



以上の内容はhttps://thinkami.hatenablog.com/entry/2024/12/14/223947より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14