Database Design and Implementation を Go で実装した

DBMSフルスクラッチで作る Database Design and Implementation: Second Edition1 を読みながら、この本で作る DBMS(SimpleDB) を Go で実装しました。始めてからちょうど5ヶ月くらいかかりました。

去年も DBMS を自作していましたが、当時は DBMS の理論を学ばずに「この SQL が投げられたときにこういう結果を返すにはこういう実装にすればとりあえずそれっぽい動きをしてくれそう」という感じに実装していて理論的なところは何も学んでいませんでしたが、今回はちゃんと本に沿って実装したので理論・実装を体系だって学べました。

github.com

私はこの本を Riki Otaki さんの「自作DBMSとおすすめ書籍2」という記事で知りました。

自作コンパイラ、自作 OS に関する書籍は数多あれど自作 DBMS の本も存在していたのか!いつかやりたいなぁと思いつつ当時はペーパーバック版が6000~7000円くらいしたのでとりあえず欲しい物リストに入れるだけで放置していました。Springer の本は為替とか関係なく急に高くなったり安くなったりしますが、あるとき3600円弱まで下がったのでそのタイミングで買いました。

元実装Java ですが、私は Java の書き方をよく知らないので Go で実装しました。やる前は class のない Go で書きなおすのは結構辛いかもしれないと思っていましたが、元実装では継承などをあまり使っていなかったので Go に書き直すのでも特別難しいという感じはしませんでした。

元実装と変えたところとして11章でやる JDBC の実装は行わず、代わりに Go の標準ライブラリである database/sqlPostgreSQL wire protocol に対応しました。 自作 DBMS に使いやすい CLI mode を実装するのは結構大変なのでそちらに注力したくない場合は PostgreSQLMySQL などのメジャーな DBMSプロトコルに乗っかるとすでにあるものを使い回せるのでおすすめです。ただし MySQLプロトコルはパケットの構造が複雑で parse するの面倒なので個人的には PostgreSQLプロトコルのほうがおすすめです。10種類くらいのパケット構造が理解できればとりあえず psql とは通信できます。

goropikari.hatenablog.com

この本の良いところ

標準ライブラリのみで実装されている

サードパーティ製のライブラリを使ったほうが実装が楽になる部分はおそらくたくさんあった(parser とか)と思いますが、それらを使うと動く仕組みがブラックボックス化して理解できた気になれないので、自作〇〇をするときは極力標準ライブラリのみで実装したいというのが私の趣味なのですが、この本の実装は標準ライブラリのみで実装されているので曖昧なところが出ずに実装できたのはよかったです。

フルスクラッチ実装

大学の講義の課題で作る DBMS だとある程度型が出来上がっているところに足りないパーツを実装するといった穴埋め方式がよくあると思います。穴埋め方式の利点として重点を置きたい場所に集中できるという点がありますが、逆に自分で作っていない部分はブラックボックスに感じてしまいます。自分で実装していない部分も読めばいいかもしれませんが、それらのコードは講義のレベルを超えるから学生には実装させなかったりしているので読んで理解するというのもなかなか骨の折れる作業です。この本は穴埋め方式でなくフルスクラッチ方式だったのでこのパーツは一体何をしているのか?という疑問を持たずに進めることができました。

この本の辛いところ

元実装のコードが読みづらい

マジックナンバーが出てきたり、副作用のある method が多くコードだけを読んでいると結構辛いなというところが多々ありました。package が循環参照している箇所もあり、全体的な構成としてわかりづらさを感じました。

この本を進めている途中で UC Berkeley CS186 の課題の RookieDB という DB の存在を知りましたがこちらのほうが読みやすく、アーキテクチャも良さそうに見えました(隣の芝生が青く見えただけかもしれません)

Lock manager RookieDB の Lock manager

Overview - CS186 Projects

12章以降写経だけでは作ったものが動かない

内容が理解できずともとりあえず写経すれば動いていた11章までとは打って変わって、12章以降は本に載っている実装を写経するだけではパーツが結合されない部分が出てきます。

12章では index を実装しますが、UPDATE, INSERT, DELETE のときに index に更新をかける処理は入る一方、SELECT のときに index を使うようにする修正は入らないのでこの時点で index を使った SELECT に対応させたい場合は自分で実装する必要があります。幸い15章の実装で index を使った SELECT ができるようになりますが、一方でその実装だとそれまで使えていた view が使えなくなります。

13章では集約関数や GROUP BY に対応するためのコードを書きますが、これだけでは動かなくて自力で Lexer, Parser に修正を加える必要があります。こちらは index のときと違い後半の章が終わっても結合されません。

14章も書いただけでは結合されず、15章の実装をすると結合されます。

一応15章までたどり着くと13章を除き色々解決されますが、12章はじめから15章終わりまでには140ページ近くあるので、そこまでモチベを落とさないようにするのはなかなか大変だなぁと思い、私は合間合間で独自修正を入れました。

おわりに

以前、自作 DBMS 界隈では有名な CMU の講義動画 を見て、講義の課題である DBMS 実装をやろうと思ったものの講義の序盤の方で早々に挫折した経験がありますが、この本は無事に終わらせることができました。私同様 CMU の講義が難しいと感じた方はこの本で勉強してみると良いかもしれません。


  1. 第2版は2020年出版ですが、「現在主流の HDD の容量は 40 GB」みたいなことが書かれていて第1版と変わっているのかな?と思うところはありました。

  2. 現在はブログは閉じられてしまったようです。Internet Archive では閲覧可(2022/8/7)

Go のカバレッジ計測結果を GitHub Pages にデプロイする

github.com

coveralls や codecov を使わずにローカルでもカバレッジを見たい、ついでにそれをそのまま GitHub Pages をつかって見れるようにしたいと思ったのでやってみたログ。

Go 標準機能のカバレッジレポートをデプロイする

Go の標準機能の範疇でやる設定は以下のよう

site ディレクトリに HTML を生成して、それをそのまま GitHub Pages に持っていく

# Makefile
.PHONY: coverage
coverage:
  go test -cover ./... -coverprofile=coverage.out
  go tool cover -html=coverage.out -o site/gocoverage.html
# .github/workflows/pages.yml
name: GitHub Pages

on:
  push

jobs:
  deploy:
    runs-on: ubuntu-20.04
    concurrency:
      group: ${{ github.workflow }}-${{ github.ref }}
    steps:
      - uses: actions/checkout@v3

      - name: Set up Go
        uses: actions/setup-go@v3
        with:
          go-version: 1.18

      - name: coverage
        run: make coverage

      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        with:
          github_token: ${{ secrets.GITHUB_TOKEN }}
          publish_dir: ./site

実際に生成されるページはこんな感じ

https://goropikari.github.io/lcov_pages_sample/gocoverage.html

LCOV を使う

Go 標準のカバレッジツールで生成される HTML は見やすくないので LCOV を使うようにする場合は以下のよう

# Makefile
SHELL = /bin/bash

ROOT_DIR = $(shell pwd)
GOBIN = $(ROOT_DIR)/bin
export PATH := $(ROOT_DIR)/bin:$(PATH)

.PHONY: tools
tools:
  GOBIN=$(GOBIN) go install github.com/jandelgado/gcov2lcov@v1.0.5

.PHONY: coverage
coverage:
  # lcov
  go test -cover ./... -coverprofile=coverage.out
  bin/gcov2lcov -infile=coverage.out -outfile=coverage.lcov
  genhtml coverage.lcov -o site
  # go coverage
  go tool cover -html=coverage.out -o site/gocoverage.html
name: GitHub Pages

on:
  push

jobs:
  deploy:
    runs-on: ubuntu-20.04
    concurrency:
      group: ${{ github.workflow }}-${{ github.ref }}
    steps:
      - uses: actions/checkout@v3

      - name: Set up Go
        uses: actions/setup-go@v3
        with:
          go-version: 1.18

      - name: lcov
        run: sudo apt-get update && sudo apt-get install -y lcov

      - name: tools
        run: make tools

      - name: coverage
        run: |
          percent=$(make coverage | grep lines | sed -r 's/[^0-9]*(.*\.[0-9]*)%.*/\1/' | sed -e 's/%/%25/')
          int=${percent%.*}
          if [ $int -gt 90 ]; then
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-green
          elif [ $int -gt 75 ]; then
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-yellow
          else
            curl -o site/coverage.svg https://img.shields.io/badge/coverage-${percent}%25-red
          fi

      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        with:
          github_token: ${{ secrets.GITHUB_TOKEN }}
          publish_dir: ./site

実際に生成されるページはこんな感じ

https://goropikari.github.io/lcov_pages_sample/index.html

README に貼り付ける用のこんな badge coverage も欲しかったので shields.io から画像をダウンロードして、それを GitHub Pages 用の branch に一緒にデプロイしてます。

↓のように raw content のリンクを README に貼り付けておけばとりあえずそれっぽくなります。

[![coverage](https://raw.githubusercontent.com/goropikari/lcov_pages_sample/gh-pages/coverage.svg)](https://goropikari.github.io/lcov_pages_sample/)

VSCode Remote Container 間を 172.17.0.1 経由で通信する

TL;DR

~/.config/Code/User/settings.json

"remote.localPortHost": "allInterfaces"

を追加すると 172.17.0.1 でコンテナ間の通信ができる。

github.com

Remote Container だと 172.17.0.1 で他のコンテナに接続できない

普通に Docker を使っているときはコンテナの中から他のコンテナへのアクセスは 172.17.0.1 を使えばできました。

# コンテナ1
$ docker run --rm -p 9000:9000 python:3 python -m http.server 9000
172.17.0.1 - - [23/Feb/2022 06:59:03] "GET / HTTP/1.1" 200 -

# コンテナ2
$ docker run --rm alpine/curl http://172.17.0.1:9000
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100   987  100   987    0     0   647k      0 --:--:-- --:--:-- --:--:--  963k
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".dockerenv">.dockerenv</a></li>
<li><a href="bin/">bin/</a></li>
<li><a href="boot/">boot/</a></li>
<li><a href="dev/">dev/</a></li>
<li><a href="etc/">etc/</a></li>
<li><a href="home/">home/</a></li>
<li><a href="lib/">lib/</a></li>
<li><a href="lib64/">lib64/</a></li>
<li><a href="media/">media/</a></li>
<li><a href="mnt/">mnt/</a></li>
<li><a href="opt/">opt/</a></li>
<li><a href="proc/">proc/</a></li>
<li><a href="root/">root/</a></li>
<li><a href="run/">run/</a></li>
<li><a href="sbin/">sbin/</a></li>
<li><a href="srv/">srv/</a></li>
<li><a href="sys/">sys/</a></li>
<li><a href="tmp/">tmp/</a></li>
<li><a href="usr/">usr/</a></li>
<li><a href="var/">var/</a></li>
</ul>
<hr>
</body>
</html>

Remote Container を2つ立ち上げて同じようにすると Connection refused になってしまいました。 172.17.0.1 だとつながりませんが、コンテナに割り振られた IP address である 172.17.0.2 だと接続できました。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...

# remote container 2
vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.1:8000
curl: (7) Failed to connect to 172.17.0.1 port 8000: Connection refused

vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.2:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

ちなみにローカルから Remote Container で動かしているコンテナにはアクセスできます。 これがアクセスできるなら 172.17.0.1 からも接続できそうなものですができません。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...
127.0.0.1 - - [23/Feb/2022 07:20:40] "GET / HTTP/1.1" 200 -

# ローカル
~ $ curl http://localhost:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

違い

ss 使って remote container の場合とそうでない場合を比較してみます。

# remote container で python -m http.server 8000 を動かした場合
$ ss -atn
State  Recv-Q Send-Q Local Address:Port    Peer Address:Port Process
LISTEN 0      511        127.0.0.1:8000         0.0.0.0:*
...

# docker run --rm -p 8000:8000 python:3 python -m http.server 8000 で動かした場合
$ ss -atn | grep 8000
LISTEN    0      4096         0.0.0.0:8000        0.0.0.0:*           
LISTEN    0      4096            [::]:8000           [::]:*

remote container だと 127.0.0.1 になっていて 0.0.0.0 でない。どうやらここが原因のようです。

調べてみると VSCode 側の設定でデフォルトだと 0.0.0.0 でなく localhost で listen する設定になっているとのこと。

stackoverflow.com

設定を変えると無事に remote container 間で 172.17.0.1 経由で通信することができました。

# remote container 1
vscode ➜ /workspaces/exp $ python -m http.server 8000
Serving HTTP on 0.0.0.0 port 8000 (http://0.0.0.0:8000/) ...
127.0.0.1 - - [23/Feb/2022 08:20:34] "GET / HTTP/1.1" 200 -

# remote container 2
vscode ➜ /workspaces/exp_ubuntu $ curl http://172.17.0.1:8000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Directory listing for /</title>
</head>
<body>
<h1>Directory listing for /</h1>
<hr>
<ul>
<li><a href=".devcontainer/">.devcontainer/</a></li>
</ul>
<hr>
</body>
</html>

Python 風の自作言語を作ってみた

最近 Crafting Interpreters という interpreter を作る本を読んでいて、とりあえず本通りにやって Lox という言語の tree-walk interpreter を作りました。 作り終わって、この手の言語処理系を作る本では大抵ブロックを { } で表現するけれど Python のようにインデントでブロックを表現する言語の場合、Lexer, Parser はどう作ればよいのかなという疑問が生じました。また文末の ; もなくしてみたいと思い Lox interpreter の実装を元に自作言語に挑戦してみました。

元実装は Java 製でしたが私は Java でのテストの書き方をよく知らないので Go で書きなおしました。

ちなみに、Python のようにインデントでブロックを表現することを Off-side rule というらしいです。

github.com

文法

とりあえずまずは完成形をば。作った言語の文法は以下のような感じです。Python 風味なのはインデントをブロックとして扱っているくらいで、あとはもとの Lox 言語を踏襲しています。 keyword も Python と同じにすればより Python 風になったと思いますが、あくまで  off-side rule の言語の処理系が作りたいのであって、Python 処理系を作りたいわけではなかったのでそこはあまりこだわりませんでした。

// declare variable
var x = 10; // terminal ';' is optional

var こんにちは = "Hello World"
print(こんにちは) // => Hello World

// if statement
if expr:
  statements
elseif expr:
  statements
else:
  statements

// while loop
while expr:
  statements

// for loop
for var i = 0; i < 5; i = i + 1:
  print(i)

// function
fun fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)

// closure
fun makeCounter():
  var i = 0
  fun count():
    i = i + 1
    return i
  return count

var counter = makeCounter()
print(counter()) // => 1
print(counter()) // => 2

// class
// there is no class variable
class Hoge:
  pass

class Hoge:
  hoge(x, y):
    pass

class Hoge:
  init(x, y):
    this.x = x
    this.y = y

class Hoge:
  piyo(x, y):
    print(x + y)

var h = Hoge()
h.name = "hoge piyo" // instance variable can define anytime
print(h.name) // => hoge piyo

// inheritance
class A:
  method():
    return "a"

class B(A):
  method():
    return "b"
  methodA():
    return super.method()

class C(B):
  pass

print(C().methodA()) // => a

// include another file
include "another.tlps" // path is relative path from the file which describe include statement

// indentation can be used for if branch, loop body and function body
var x = 1
  var y = 1  // indentation error

インデントをブロックとして扱う

手始めに Python の挙動を調べてみました。 今まで Python を書くときはスペース4つで表現してきたものの、2つでも書けるしこの辺の個数に何か制限はあるのかな?と。 試してみるとスペースが1つだろうが3つだろうが深さのレベルさえ同じならば個数に依存しなさそうということがわかりました。 スペース2個が { に対応するとかだったら話が簡単なのになと思っていたのですが的が外れました。

インデントをブロックとして扱う方法を自力では思いつかなかったので調べてみると以下の記事を見つけました。

lemniscus.hatenablog.com

行頭の空白の数の増減をスタックで管理しながら INDENT ({ に相当) だったり DEDENT (} に相当)を Token として生成すると。なるほど確かにその方法だと空白の数に制限をかけずに済みそうです。またこの方式から unindent does not match any outer indentation level という error は Lexer の時点で出すのが良さそうということもわかりました。

/tmp $ cat ex.py
def hoge():
    x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 3
    y = 2
         ^
IndentationError: unindent does not match any outer indentation level

この情報から実際に実装してみたのがこの辺。Go の標準ライブラリには stack がなさそうだったので slice 使って自作しました。

https://github.com/goropikari/tlps/blob/423b76f03000e26273d74e52180f73b41fcce4cd/scanner.go#L232-L268

ブロックが使えるところに制限をかける

Python の場合、下記のプログラムの例のようにブロックを使える部分には制限があります。

/tmp $ cat ex.py
x = 1
  y = 2

/tmp $ python ex.py
  File "/tmp/ex.py", line 2
    y = 2
IndentationError: unexpected indent

Python の言語仕様を参考に自作言語では if や def のように : を使うものはブロックとして NEWLINE INDENT statements DEDENT を使うという制限をかけました。

block:
    | NEWLINE INDENT statements DEDENT 
    | simple_stmt

Python のブロック 10. Full Grammar specification — Python 3.9.7 documentation

また、ブロックを parse するときは for のブロックなのか if のブロックなのかということを区別するタグをつけるようにしました。ブロックが許されていないところでブロックが作られた場合は None というタグをつけました。そして interpreter がそのブロックオブジェクトを評価するときに None ならばエラーで落とすという仕様にしました。interpreter の処理を書いている途中で評価するときでなく parse 時点でエラーで落としてよかったなと思いましたが、まぁいいかととりあえずそのままにしました。

tlps/parser.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub

ブロックを使うところに制限をかけてみると if, else に加えて elif のようなものもないと、if 文がネストの深い書き方になってしまうことに気付きました。

if (aaa) {
  xxx
} else if (bbb) {
  yyy
} else if (ccc) {
  zzz
}

: のあとにはブロックがくるとしたせいで、{} を使った↑と等価なことをしたい場合、↓のような書き方を強いることになってしまいました。 elif のような keyword を追加するか、else if xxx: のような書き方を許し else のあとに : がくるか if が来るかを判定する方法の2種類が考えられましたが、いろいろな言語が elif のような keyword を持っているのでそちらに合わせました。(Julia が好きなので elseif にしましたが)

if aaa:
  xxx
else:
    if bbb:
      yyy
    else:
      if ccc:
        zzz

文末の ; をなくす

元々の Lox 言語は print 123; のように文末を ; で終えるようになっていたのでこれを省略できるようにしてみました。簡単のために文は複数行にはならないと言う制限をかけ、; の代わりに \n を文の区切りとして使うことにしました。 元々の Lox 言語はスペースや \n といったいわゆる空白文字はすべて無視する仕様だったのでまずは \n を意味のある文字として Token にすることにしました。

ただ全ての \n を意味のあるものとする必要はなく、空白行の \n (コメントだけの行も含めて)は無視していいというか残したままだと parser 側の処理が面倒になりそうだったので無視するようにしました。

文末の ; を省略するのはこの程度の対応で実現することができました。

tlps/scanner.go at 423b76f03000e26273d74e52180f73b41fcce4cd · goropikari/tlps · GitHub

さいごに

インデントを使ってブロックを表現するにはどうしたらいいのかという疑問から初めた自作言語ですが、当初の目的以上に学ぶことが多くやってみてよかったです。

今 crafting interpreters の後半の VM を作る章を読み始めたところなので、読み終わったら自作言語の処理系も VM 方式にしてみたいと思います。

Graph Database を読んだ

最近 Graph Database に興味を持ったので Graph Databases: New Opportunities for Connected Data を読んだ。graph db の一つである Neo4j のサイトから PDF をダウンロードできる。

neo4j.com

Neo4j のサイトからダウンロードできることからわかる通り、サンプルは Neo4j を使ったものだったけれど、そこまでサンプルが多いわけでもなかったので、概念を学びつつ実際に軽く試しながら学ぶというのにちょうどよい塩梅だった。

この手の薄い本だと終始ツールの使い方になっていることが多々あると思うものの、この本はそういう感じではなく、Graph Database の内部構造のざっくりとした解説もあり Graph Database は RDBMS とどう違うのかというのがわかってよかった。