kawasin73のブログ

技術記事とかいろんなことをかくブログです

Go でトランザクションをフルスクラッチで実装した

Go Database 作ったもの

一歩ずつ一歩ずつ前へ進んでいく、確実に。どうも、かわしんです。

到底 1 記事に収まるような内容ではなく長いので、トランザクションの作り方に興味のない方は途中の「なぜ Go なのか」まで読んでいただければ嬉しいです。

この記事は、Go2 Advent Calendar 2019 の 7 日目と セキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2019 の 7 日目を兼用しています。

さて、僕の興味は必要になったライブラリやミドルウェアなどを自作して、作りたいプロダクトを完成させることです。必要なコンポーネントがないからといってプロダクトを作るのを諦めたり妥協したりはしたくありません。

多くのアプリケーションではデータベースは重要なコンポーネントです。大抵のアプリケーションは MySQL や Postgres、Redis など既存のデータベースシステムで対応することができますが、既存のデータベースシステムでは対応できないような場合に備えてデータベースシステムを作れる力をつけておきたいと思っていました。

そこで、今回はデータベースシステムを作る前哨戦として トランザクション を実装します。出来上がったものはこちらです。

github.com

僕は、今年の セキュリティ・ネクストキャンプ に参加したのですが、同時開催されていたセキュリティキャンプのデータベースゼミの講師である 星野さん にお願いして講座で利用された教科書をいただき、キャンプが終わってからその教科書を参考に設計と実装を行いました。

どんなトランザクションを作るのか

トランザクションとは ACID を満たして複数のデータの書き込みや読み込みをできるようにする仕組みだと僕は認識しています。

ACID は、A (Atomicity : 不可分性)、C (Consistency : 一貫性) 、I (Isolation : 独立性)、D (Durability : 永続性) ですね。

ここでは詳しくは説明しないので、以下の資料を読むといいかと思います。

qiita.com

マジモンのトランザクションをガチ実装するのは初心者の僕には大変なので、実装しやすいように色々制約をつけたトランザクションを作ります。

  • KVS (Key Value Store) にする
    • シンプルな操作 INSERT UPDATE READ DELETE COMMIT ABORT の操作だけに対応します。SQL などはありません。
  • 範囲検索はしない
    • インデックスの実装をサボるために範囲検索はスコープ外としています。（あと、S2PL でも助けられます）
  • インメモリデータベースとする
    • 全てのデータはメモリに載る前提です。それより大きなデータには対応しません。
    • Buffer Pool などをサボることができます。(あと、undo ログをサポートしなくてもよくなります)
  • non-deterministic DBMS を想定します
    • deterministic DBMS とはあらかじめトランザクションの処理内容がわかっているものです。例えばストアドプロシージャとかでしょうか。
    • 逆に non-deterministic ではトランザクション内で次にどの処理命令がくるかがわかりません。いつ COMMIT されるのか ABORT されるのかもわかりません。普通はこちらが使われてると思います。
    • non-deterministic DBMS ではトランザクションは ACID の I を担保するために頑張る必要があります。
  • WAL を使う
    • Write Ahead Log の略です。データベースに対する何らかの更新（Write）を行う前にその操作の内容をログとして追記し、更新が反映する途中でプロセスが死んだ場合でもその更新を再開したりロールバックできるようにして、ACID の A と D を実現するための仕組みです。
    • ログは COMMIT ログが永続化された変更は永続化されたとして確定し、プロセスが死んで再開された後に復旧されます（Crash Recovery）。
    • COMMIT ログが永続化される前にプロセスが死んだ場合は WAL ログに書かれた更新の内容は失敗したとして破棄されたり書き戻されたりします。
    • つまり、WAL に COMMIT ログが書かれて初めてクライアントにトランザクションの更新が成功したと返信することができます。
    • 参考 : バッファ管理とWAL - Qiita
    • ログには undo ログと redo ログの 2 種類がありますが、今回は redo ログのみを使います。
  • チェックポイントの作成は起動時と終了時のみ
    • トランザクションが動いているときにチェックポイントを書き出すのはややこしいので今回はサボります。
    • プロセスの終了が遅くなってしまいますが許容します。

このような制約がありつつも、マルチスレッドで ACID を守って正しく動くトランザクションを作ります。

どうやってトランザクションを作るのか

何を作る時でも同じですが、「まず遅くてもいいから正しく動くものを愚直に作り、それに最適化を施すことによって効率的に速く動くようにしていく」 という作り方が鉄則です。

今回は以下の３ステップに分けて実装していきます。

Step 1 は、Trivial Scheduler と呼ぶそうです。同時に1つのトランザクションしか動かないので排他制御も必要ありません。ただ、愚直に実装するのみです。ただし、今後はこの実装に積み重ねていくのでインターフェイスなどはちゃんと考えて、正しく振る舞うように実装します。

Step 2 では、複数のトランザクションが同時に動くので 並行制御 をする必要があります。並行制御アルゴリズムには様々なものがありますが、初心者向けとして S2PL (Strict Two Phase Lock) が教科書で勧められていたのでこれを採用します。

Step 3 では、Step 2 の実装をマルチスレッドで動くようにします。インデックスやデータストアや WAL などは同時にアクセスによるデータ競合を防ぐために 排他制御 をする必要が出てきます。

なぜ Go なのか

今回は Go で実装していくわけですが、その一番大きな理由は goroutine の存在です。

Step 2 の並行制御をするためには並行スケジューラが必要になります。しかし、goroutine は I/O と自動で連携したコルーチンであり、Go のランタイムに並行スケジューラが実装されているため、Go を使うことでこのトランザクションの中で一番大変と思われる 並行スケジューラの実装をサボる ことができるのです。

むしろ、並行スケジューラを実装しないでトランザクションの実装を勉強したと言えるのかどうか怪しいところではありますが、それは C や C++ で実装するときにやるので勘弁して欲しいです。今回はトランザクションの概観をざっくり知るために作っているので。

また、Step 3 でマルチスレッド化するわけですが、goroutine ベースで作るとランタイムが 自動でスレッド間で適切に分散してスケジューリング してくれます。正直あっけないくらい簡単にマルチスレッド対応できてしまいました。

また、Go はミドルウェアなどを プロトタイピングするのに向いている言語 だと思っています。

goroutine もそうですが、map やスライスなど必要なコンポーネントが言語自体や標準ライブラリに含まれていますし、GC がついているので雑にメモリを確保することができます。また、バイト列が []byte として柔軟に扱える上に、多くのインターフェイスで []byte を利用することが想定されている (io.Reader など) ため、ファイル操作やバイナリ処理をするようなミドルウェアの開発に向いています。さらに、そこそこ速いため速さを求められないようなプロダクトではそのままプロダクションで使えてしまいます。

トランザクションを作っていく！

ここでは順を追ってどうやって実装していったかを紹介していきます。全て main.go の１ファイルに収まる 1000 行に満たない小さな実装なので、ぜひコードを読んでみてください。それぞれのステップでブランチがきられています。

Step 1 : シングルスレッドで同時に１トランザクションのみが動く

GitHub - kawasin73/txngo at trivial_scheduler

まず Go で シングルスレッド を実現しなくてはなりません。Go は M:N 方式 (1, 2) で動くため厳密にシングルスレッドでは動きません。しかし、goroutine を実行する主体である processor を 1 つだけに限定すればシングルスレッドと同じように 1 つの goroutine のみが同時に動き、データ競合も発生しません。

// execute on single thread
runtime.GOMAXPROCS(1)

トランザクションは同時に1つしか動かないため入出力インターフェイスも1つだけで十分です。そこで、標準入出力 を使ってターミナルから柔軟にクエリを流し込めるようにしました。

さて、トランザクションは以下のような構成で実現しています。

f:id:kawasin73:20191206180322p:plain

起動時に CheckPoint ファイルから永続化されている 全てのデータが DB に読み込まれ ます。DB は map[string]Record で表されたハッシュマップで、キーからレコードを高速に引いてくることができ、インデックスの役割も兼ねています。

トランザクションの更新した変更は途中で ABORT されて変更が全て破棄される可能性があります。もし COMMIT される前に更新内容を DB に反映していた場合はその内容を元に戻す必要があります。さらに、今後複数トランザクションを同時に動かす時には、MVCC などを導入しないと確定していないデータを他のトランザクションに読まれてしまうダーティリードになってしまいます。

この課題を解決するために トランザクションの更新した変更は Write Set に保存して、COMMIT された後に DB に書き戻す ようにします。

更新処理の中で以下のように key を処理しているのを不思議に思うかもしれません。これは引数で渡された文字列 key が別の文字列の一部であった時、key が DB に保存されることで元の文字列が GC されなくなってしまうことを防ぐためです。明示的に key 文字列のメモリを確保し直して、外部のメモリへの参照を発生させないようにしています。

// reallocate string
key = string(key)

READ ではトランザクション内での変更結果を読む必要があるため、まず Write Set を検査して、なかった場合に初めて DB を読みにいくようにします。READ での検索を高速にするために Write Set は map[string]RecordCache で表されたハッシュマップで実現します。レコードが削除された場合でも DB にはレコードはあるので Write Set に削除されたフラグを持った RecordCache を保持します。

COMMIT 時にトランザクションでの 更新履歴を全てログとして一度に WAL に書き出し ます。本当は更新時に逐一 WAL に書き出して COMMIT 時には COMMIT ログだけを永続化することが望ましいのですが、次のステップで複数のトランザクションから同時に WAL に更新ログを書き込むとログの順序が割り込まれてしまうため、一度に書き出すようにしました。（トランザクション ID を使えば解決しますが、ID の払い出しを考えたくなかったのでこの方法にしています。また、ABORT される内容を WAL に書かないのでちょっと効率的かなとか思ってます）

また、Write Set のハッシュマップでは更新した順番がわからないため、ログの履歴を保持するスライス Logs ([]RecordLog) を用意し、その内容を WAL に書き出します。

ABORT するときは、Write Set の中身と Logs をクリアするだけでトランザクションの変更内容は全て破棄されます。

プロセスの終了時に DB に保存された内容を全て CheckPoint ファイルに書き出します。しかし、ファイルの上書き中にプロセスが突然死すると元々の CheckPoint ファイルの内容が壊れてしまいます。そこで一時ファイルに内容を書き出した後に os.Rename() してアトミックにファイルを差し替えて CheckPoint ファイルを更新します。上書きされたファイルの内容は自動で削除されます。

CheckPoint ファイルへの書き出しが永続化されたら WAL ファイルの内容は全て必要なくなります。（WAL の中の全ての更新履歴が CheckPoint ファイルに反映されているため）そのため、WAL ファイルを os.Truncate() してクリアします。

起動時に WAL ファイルの中身があるときは前回のプロセスが異常終了したことを表します。（正常終了では必ず WAL ファイルはクリアされているため）そのときは Crash Recovery を行います。WAL ファイルの更新履歴を COMMIT ログがあるところまで再実行して CheckPoint ファイルの内容を更新します。

やっていることはこれだけです。これだけの処理をするだけで ACID を守ったトランザクションが出来上がってしまいます。

Step 2 : シングルスレッドで同時に複数のトランザクションが並行に動く

GitHub - kawasin73/txngo at S2PL-single-thread

まず、複数のトランザクションに同時にクエリを送信するために、インターフェイスは標準入出力の他に TCP コネクション をサポートするようにしました。telnet で接続すると標準入出力と同じやり取りを複数同時に行えるようになります。TCP コネクションごとにトランザクション実行主体が作成されます。

複数のトランザクションを並行に動かすために並行制御アルゴリズムである S2PL を導入します。トランザクションはそれぞれ goroutine のなかで並行に動いています。

S2PL とは Two Phase Lock を発展させたもので、あるレコードへの排他ロック（Write Lock）または共有ロック（Read Lock）の獲得を成長相のみで行い、トランザクションの完了（WAL への COMMIT ログの書き込み）後に排他ロックを解放するというものです。共有ロックはトランザクションの完了前に解放することが許されますが、排他ロック・共有ロックのどちらのロックも解放したあとは縮退相となりロックの獲得はできなくなります。

この S2PL を導入するためにそれぞれの操作に以下の処理を追加します。

  • READ するときは Read Lock を獲得
  • INSERT, UPDATE, DELETE をするときは Write Lock を獲得
  • COMMIT するときは以下の順番で処理
    1. 獲得した全ての Read Lock を解放
    2. WAL の書き込みと永続化
    3. Write Set の中身を DB に反映
    4. 獲得した全ての Write Lock を解放
    5. Write Set と Logs をクリア
  • ABORT するときは獲得した全ての Lock を解放

ここで１つ課題が発生します。READ したレコードを更新する場合 の処理は自明ではなく、明確に決める必要があります。

すでに Write Lock を獲得した後は READ をする場合でも更新処理をする場合でも新たにロックを取ることはありません。しかし、Read Lock を獲得した後に更新する場合はそれを Write Lock に変換する必要があります。

Go には、sync.RWMutex という Read Lock と Write Lock が可能な Mutex コンポーネントがありますが、残念ながら Read Lock を Write Lock に変換する方法は提供していません。もし、Read Lock を解放して Write Lock を獲得し直すと別の goroutine で Write Lock 待ちしていたトランザクションにロックを横取りされてしまう可能性があります。

ここで僕が考えた解決策は以下の2つです。

前者は、標準ライブラリの sync.RWMutex だけで実現できるため簡単に実装できます。しかし、ユーザはトランザクション開始時に明示的に Read-Write か Read-Only であるかを宣言する必要があります。正直これは使い勝手が悪いです。そのくらい自動で判別してほしい。

処理パフォーマンスの高速化やデッドロックの回避を理由にしてこの手法を採用するのであればいいのですが、コンポーネント自作が難しいからという理由でユーザに不自由を押し付けることはしたくありません 。

そこで後者の昇格可能な RWMutex を自作する手法を選択して github.com/kawasin73/umutex を自作しました。詳しくは以下の記事で紹介しています。

kawasin73.hatenablog.com

昇格可能な RWMutex では、Read Lock を獲得した goroutine 同士が昇格しようとすると デッドロック を起こしてしまうという課題がありますが、この umutex ではデッドロックを検知する仕組みが備わっています。

f:id:kawasin73:20191206203651p:plain

ロックはレコードごとに獲得できるようにするために Locker というコンポーネントを追加しました。S2PL では範囲スキャンをした時にロックの穴あきによる予期せぬアクセスを防ぐため、範囲ロックを工夫しないといけないのですが、今回のトランザクションは範囲スキャンをサポートしていないのでシンプルな map[string]*lock で実現しています。レコードごとに複数の Read Lock が起こり得るため参照カウントを持ち不必要なロックオブジェクトを削除しています。

各トランザクションでは Write Set にあるレコードは全て Write Lock を獲得していることを表します。同様に Read Lock を獲得していることを表現するために Read Set も追加しました。

Step 1 では、更新内容は Logs と Write Set の両方に保存していましたが冗長であることに気づいたので、Write Set には Logs のインデックス番号だけを保存するように最適化しました。

COMMIT 処理でのログの書き込み中に他のトランザクションの COMMIT 処理が割り込まれるとデータが壊れてしまいます。goroutine は厳密なシングルスレッドではないため、goroutine が COMMIT 処理中にコンテキストスイッチを起こして別の goroutine の COMMIT 処理が割り込まれる可能性があります。3 そのため、COMMIT 処理全体を sync.Mutex によって排他制御するようにしました。

S2PL を導入するために昇格可能な RWMutex を実装するだけで、並行制御されたトランザクションが実装できてしまいました。goroutine の強力さのおかげです。

Step 3 : マルチスレッドで同時に複数のトランザクションが並行に動く

GitHub - kawasin73/txngo at S2PL-multi-thread

最終ステップとしてマルチスレッドで動かすために、runtime.GOMAXPROCS(1) を消します。

あとは、複数のスレッドから同時アクセスされそうな所に排他制御を導入するだけです。Locker と DB へのアクセスをするときに map の更新で競合する場合があるので sync.Mutex と sync.RWMutex で保護するようにしました。

まさかのマルチスレッド対応が一瞬で終わってしまいました。goroutine にのっかるだけで同じロジックでマルチスレッドで動くというのはすごいことです。

最後に

無事、マルチスレッドで動く S2PL で並行制御されたトランザクションを完成させることができました。こんなにあっさりできてしまったのは goroutine のおかげです。

ただ、最初に述べたように色々制約をつけてサボっているところが多いです。インデックスにデータ構造を適用したりとか、バッファプールを追加したりとか、チェックポイントの作成を定期的に行ったりとか、WAL をロックを取らずに書き込んだりとか色々改善の余地はあります。

しかし、Go はメモリが枯渇することを想定しない 4 言語である上に、メモリ管理が GC と密に結合しているのでメモリ枯渇への対応であるバッファプールを実装するのはちょっと辛いです。（[]byte から特定の型へ unsafe.Pointer などを使ってキャストしても GC の対象外となる）

次は、そういう改善点と並行スケジューラの実装を含めて柔軟な言語である C や C++ で実装してみたいと思っています。

最後になりますが、今回の試みはセキュリティキャンプで教科書を提供していただき、途中でレビューをしてくださった 星野さん のご協力なしには実現できないものでした。改めて感謝申し上げまして、この記事を終わりたいと思います。

  1. GoConで発表してきたのでついでにruntime以下の知識をまとめていく #golang - niconegoto Blog↩

  2. The Go scheduler - Morsing's blog↩

  3. goroutineがスイッチされるタイミング - Qiita↩

  4. メモリアロケーションに対する罪悪感 - kawasin73のブログ↩