Riki Otaki Blog

Content Management System written in bash

このエントリーをはてなブックマークに追加

振り返り (2021 3-9)

半年を振り返る。研究とかデータベースマネジメントシステム(DBMS)について。

3月

SimpleDBというJavaで書かれた教育用のDBMSをC++で実装していた。DBMSの全体像を把握したいという理由から実装していた。DBMSはQuery Executer, Index, Transaction, Loggerなど様々な部品から成り立つが、それらの部品がどのように作用し、全体としてどのような設計で実装されているかに興味があった。一度きれいに実装されたものを再実装することで理解を深めることができると思った。自分で0から設計を考えたわけではないので完全理解に至った感じはしなかったが、DBMSの全体像を把握するのに十分役に立ったように思う。SimpleDBの実装記録(?)は別のブログに書いた。最近自作DBMSと検索してみたらこの記事がトップに出てきてびっくりした。

4月

SimpleDBを実装し終わった後、DBMS、とくにトランザクションの並行制御についてもっと深く理解したいと思った。もともと並列で動くシステムのアルゴリズム、例えばCache Coherency Protocolとかを考えることが好きだった。並列に何かを考えることは大抵難しいのだがその難しさが逆に面白い。トランザクションの並列制御もそのような興味の対象の一つだった。並行制御を研究するには、まず理論の理解が必要だと思い、王道らしいWeikum本の1-5章あたりを二週間くらい書けてざっくり写経してざっくり理解した。腕がもげそうだったが、ここで一度この本を読んで、メモを残していたのは後に十分役に立ったので今考えると英断だった。
4月の中旬、ちょうどWeikum本を一通り読みおわったあたりで、Cybozu labs youthに採択され、DBMSの研究や開発をメンターに指導していただけることになった。こちらについてはまたいつか詳細な記事を書く。
4月の後半は、In-Memory CCの論文を読んでいた。分野の全体像がまだつかめておらず、H-StoreやHyPerなどの少し古めな論文を読んでいた。この時点では論文を読んでも細かい実装方針がわかるだけで大局的な理解が得られていなかったが、分野の雰囲気、例えばMethodは何を議論するか、Evaluationではどのベンチマークを利用しているかなどをつかめた気がする。今だったらどの論文から最初に読むか、と少し考えてみたがそれはよくわからない。

5月

教科書を読んだり論文を読んだりすることはOutputをうまないので、そろそろ手を動かして何か実装したい気分になった。メンターと相談し、TPC-Cというベンチマークを開発することにした。TPC-Cはトランザクションの処理性能を計測するのによく利用される。同時並行処理の論文では、TPC-Cを使った性能指標を載せることがほぼマストであるが、良い設計のC++の実装が存在しなかったので実装するに至った。一ヶ月くらいかけて実装した。はじめはC++をうまく扱えず悶々していたこともあったが、メンターの方にいろいろと教わり、それなりにわかるようになった。concept, constexpr, templateなどは今まで曖昧にしか理解していなかったが、それらを適切に用いてプログラムをかけるようになった。TPC-Cを作った後は、とりあえずシングルスレッドで動くトランザクションエンジンを実装し、ベンチマークが正しく動くことを確認した。実装が終わりに近づくにつれ、リファクタリングを通してプログラムの設計がどんどん明快になっていくのを感じた。これは実装対象のドメイン知識が蓄積されていったことに起因していると思う。プログラムの設計は全てがスタティックに定まるものではなく、手を動かしながらダイナミックに模索することも必要であるという学びを得た。

6月

ベンチマークの実装が完了したので、ベンチマーク対象の同時並行制御プロトコルを実装しようと考えた。実装するには、並列にデータの出し入れが可能なIndexが必要である。王道はB+TreeやConcurrent Hashなどであるが、それ以外にもBwTree, ART, Masstreeなど様々なデータ構造が発明されている。まずはそれらConcurrent Indexに関する論文を読んだ。実装予定のプロトコルではRange QueryをサポートしたいのでHash系のインデックスではなくTree系のインデックスを利用したいと考えた。実装が公開されている既存のプロトコル(Silo, Cicada)などは、Masstreeを利用しているので、自分もMasstreeをベースに、その上に同時並行制御プロトコルを実装しようと考えた。しかし、Masstreeは簡単に利用可能なインターフェイスをもっていなかったため、まずは良いインターフェイスを持つWrapperを作るところから始めることになった。いずれSiloなどのプロトコルを実装することを想定していたため、Indexには基本的な操作(Read, Update, Insert, Delete)だけでなくPhantom Protectionも簡単にできるようなインターフェイスが必要だったので色々工夫が必要だった。ここで十分汎用的なインターフェイスを作れたのが後々役に立った。関連して、6月の頭から海外のDBMSの研究室でリモートインターンをさせてもらえることになった。こちらについてもまたいつか記事を書くかもしれない。

7月

同時並行制御プロトコルをなにか実装したかったので、まずはSiloを実装しようと考えた。Siloは他の(Multi-VersionやDeadlock検出)プロトコルと比べるとアルゴリズムが単純で、またよくスケールすると言われているので、一番始めに実装することにした。まずはSiloの論文を精読した。SiloのキモはRead->Lock->SID->Verify->Write+Unlockという形のCommitプロトコルであることを理解した。これを理解するには、R->W, W->W, W->Rのコンフリクトを持つ2つのトランザクションがどのように排他されているのかを図を書いて確認するのが役立った。Commitプロトコルを理解した後は、ReadSetとWriteSetのセマンティクスを考えた。これが結構大変だった覚えがある。状態遷移図を用いて、各ノードはReadSetに存在、WriteSetに存在、両方に存在、両方に存在しない、(実際にはもっと複雑)などを表し、エッジはRead, Insert, Update, Deleteで、状態が閉じているかどうかを一度紙に書いて確認した。あとはEpochの挙動を確認した。SiloはEpochベースでLoggingやGCをするのでEpochの理解が超重要である。Logging関連では、理論の理解が足りてないと感じたのでWeikum本の11章を読みRecoveryに関する知識を得た。4月に読んだはずの5章までの内容も忘れていたのでまとめて復習した。復習するときになにかメモがあると安心感があるので、メモを残しておいて良かったと思った。教科書を一から読むと思うと覚悟が必要に感じるが、自分のメモを読むのは気楽にできる気がする。もちろん汚い字と対峙する必要はあるが。復習したことでSerializabilityへの理解がだいぶ深まり、メンターとviewやversion orderに関する議論ができるようになった。7月はこんな感じでそこまで手を動かさず論文を読みプログラムの設計をしていた。

8月

事務作業に追われ8月のはじめは研究ができていなかった。中旬から本格的にSiloを実装し始めた。実装の計画は7月に書いていたのでそれを元に実装するだけなのでそこまで大変ではなかった。はじめはRead時にもRecordデータをCopyするような実装をしていたが、そうするとパフォーマンスが悪かったのでRead時にはRecordのポインタをとってくるだけの実装に改めた。Siloの実装が一通り完了すると、x軸がThread数, y軸がThroughputで、性能がほぼ線形に伸びていくようなグラフの描画が可能となり、目標としていたことを一つ達成できた。Siloを実装した後は、比較対象としてPessimisticなプロトコルを実装したいと思った。S2PLのNoWaitは比較的単純なアルゴリズムなので実装しようと思った。Siloを実装し、並行制御プロトコルの実装手順を一通り理解したのでNoWaitの実装は簡単にできた。NoWaitはSiloとは異なりPhantom ProtectionをNode Verify方式ではなく、Next Key Lockを用いて実装する必要があり、それが大変かなと思ったがそうでもなかった。あとはMulti-Version系の実装が欲しいなという気分になった。

9月

2つのプロトコルの実装をしたところ、メンターにテストがあったほうがいいよねと言われた。SiloもNoWaitも理論的に正しい(Serializableである)ことが証明されているが、実装レベルでSerializableなスケジュールを生成できているのかどうかを確かめているプロジェクトは少なくとも研究開発用(≠商用)のコードでは見たことがなかった。各RecordにWriteしたトランザクションのIDを埋め込み、W->W, W->R, R->Wの依存関係を検出し、コンフリクトグラフを作る。グラフがトポロジカルソートができれば、(サイクルがないので)スケジュールがConflict Serializableであり、またトポロジカルソートした結果がSerialでなスケジュールとなる。Siloに関してはテストを書き、実装した。実装がまだきれいではないのでmaster branchにはmergeしていないが、結果(とりあえずW-R, W-Wのエッジのみ)は以下のようになった。

その後Muti-version系のプロトコルの実装をしたいという気持ちになったので、Muti-Version Timestamp Ordering(MVTO)を実装することにした。MVTOではトランザクションのはじめにuniqueで単調増加なTimestampを発行するが、これを共有カウンタのatomic fetch addで実装するとマルチスレッドではスケールしない。そのためDistributed Timestampの実装が必要になる。実際にはCicada論文で述べられている方法を少し自分なりに改造して実装することにした。その他は普通のMVTOを実装した。はじめはLock FreeなVersion Chainをしたいと考えていたが、まずは簡単なものから実装したほうが良いと思ったので、Version ChainはLockしてからアクセスするような設計にした。あと注意したこととしては、Phantom Protectionを実装するためにMasstreeのLeaf NodeにTimestampを埋め込む必要が合ったこととかだろう。
さらにその後TPC-C以外にもマイクロベンチマークがほしいという気分になり、YCSBを実装した。TPC-Cに比べると実装ははるかに楽で、すぐ終わった。YCSBはBlind WriteとRead Modify Writeを区別しているので、あらたにBlind Writeという操作をプロトコルに付け足す必要が合った。実験用スクリプトを書き、実験結果は以下のようになった。






自分でこのグラフを出力したい人がいれば以下のレポジトリにソースコードがある。

https://github.com/wattlebirdaz/tpcc-runner

感想

振り返ってみると、8,9月はたくさん実装した気がする。とくに9月がやばい。疲れた。

Future Work

  • S2PLのWoundWaitやWaitDie, Deadlock Detectionなどを実装する
  • Cicadaに代表されるようなLock FreeなMulti-Versionプロトコルを実装する
  • IC3のようなChoppingを利用するプロトコルを実装する
  • プロトコルのSerializabilityのテストをmasterにmergeする
  • eBPFを使えないか考える

Article Info

created: Wed Sep 22 22:57:41 JST 2021
modified:
views: 215
keywords:
prev:Siloを実装した next:振り返り (2021 3-9)

Social Links