セキュキャン2019 参加記 (データベースゼミ)

8/13〜17に行われていたセキュリティ・キャンプ全国大会で、集中開発コースのX-III データベースゼミに参加してきました*1

事前学習からキャンプ期間中を通して経験したさまざまなことを、時系列順に振り返っていこうと思います。

事前学習

講師の方から講義資料をいただいていたのでそれを読みつつ、講師の方から一番最初のマイルストーンとして指定されていたごく単純なDBを実装しました。内容としては、

  • key-valueストア(Relational Databaseでなくてよい)
  • データの永続化、耐障害性はちゃんと実装する
  • インデクス構造は最初はC++のデータ構造(std::mapなど)を使って良い

というものです。 この最初のマイルストーンを達成した後は、自分の興味に応じて好きな方向にDBを拡張させていって良いという感じになっており、代表的な選択肢としては

  • トランザクションの並行並列実行を実現する
  • インデクス構造を自作する(B+木、ハッシュマップ等)
  • relational databaseに拡張する

などがありました。当初は自分はインデクス構造をやろうかなと考えていて、講師の方との事前のSkypeミーティングではそういっていたのですが、実装したり資料を読んだりしていくうちに並行並列制御の方が楽しそうという気持ちになりました。

1日目

開会式や共通講義、LT大会、グループワークなどがありました。

一番楽しかったのはグループワークです。今年のテーマは、同じ目標を持つキャンパー同士でチームを組み、キャンプ後の活動目標を立てるというものでした。私は普段は言語処理系やプログラムの静的解析などに興味があるのですが、Y-IIのCコンパイラゼミの受講生で似たような興味を持つ人が複数いたので、その人たちとチームを組みました。最近人気が増してきているCコンパイラゼミに合格するだけあってとても優秀な人が多く、お話ししていてとても刺激を受けました。セキュリティ・キャンプに来て言語処理系の話ができる友達がこんなにたくさんできるとは思っていなかったのでかなり嬉しかったです。

2日目

2日目からゼミの開発が始まりました。この日はトランザクションの並行制御に向けて、実装のデザインを大幅に変えました。

データベースゼミで自作DBを発展させる方向性の1つとして、トランザクションの並行並列実行制御があると述べましたが、その中での マイルストーンとして、

  1. 同時に複数のトランザクションが存在しないという仮定のもとで動く (事前学習で達成していたレベル)
  2. 並行制御: 同時に複数のトランザクションが存在するが、各瞬間は1つだけが動くという仮定のもとで動く
  3. 並列制御: 同時に複数のトランザクションが存在して、同時に動きうるという仮定でも動く

という3つがあります。図にしてみるとこんな感じです(緑の部分が今回実装した部分です):

f:id:momohatt:20190830013255p:plain:w500

1.から2.に拡張するためにはトランザクションの機能をデータベースから分離させ、かつ複数のトランザクションを平等に動かすためのスケジューラを用意することが必要になってきます。この日は丸1日かけて、これらの設計を(講師の方に教えていただきながら)考え、実装しました。

並行制御の場合、green threadを使えば各瞬間に動くスレッドが1つであることが何もしなくても保証されるので実装が少し楽なのですが、C++にはgreen threadがないため、mutexやconditional variableを使いながら模擬green threadを書く必要があり少し大変でした。また、参考にできる実装や擬似プログラムなどがなく、講師の方と議論しながら決めたふわっとした感じの設計を実際のコードに落とし込む必要があり、プログラムの大枠ができてくるまではかなり混乱していました。

3日目

2日目に新しい設計の下地はできていたものの、スケジューリングの機能が適切でなく、複数のトランザクションが存在している場合でも、1つのトランザクションのみに優先的に実行権限を与えるような偏ったスケジューリングをしていたのでそれを直し、ラウンドロビン方式のスケジューラを書きました。 これによって、複数のトランザクションからの命令がバラバラに動くようになり、複数のトランザクションからバラバラに命令が来るという現実的な設定を模した状況を作り出せるようになり、トランザクションの並行実行制御を考える準備がようやく整ったことになりました。

その後、各トランザクションの命令の実行順序を適切に制御して、実行結果がトランザクションが直列実行*2された場合と等価になるようにスケジュールする必要があります。この「等価性」の定義には様々なものがあるのですが、今回はconflict serializabilityを採用し、conflict serializableな実行履歴を生成する非常に単純なスケジューリングプロトコルである2PLプロトコルを実装しました。

2PLプロトコルでは、実行するトランザクションの内容によっては途中でデッドロックすることが知られているのですが、今回はこの状況を再現することもできました。デッドロックができて講師の方がとても嬉しそうだったのですが、デッドロックを起こして喜んでいる人を見たのは初めてだなぁと思いました。

conflict serializabilityや2PLについては、講師の方が公開されているスライドを見るとイメージがつかめると思います。

トランザクションの並行実行制御 rev.2

4日目

講義最終日のこの日は、夕方にXトラック内での発表会がありました。午前中は発表スライドを作り、午後は細々とした修正やリファクタリングなどをしました。

夕方の発表会の直前まで作業をしていて話す練習があまりできていなかったことと、発表スライドに時間をかけすぎて内容がやや長くなっていたこと、発表本番で緊張してしどろもどろになってしまったことから、制限時間が3分のところをかなり超過してしまい、皆さんに申し訳なかったです...

発表スライドを置いておきます: docs.google.com

夜にラストナイトイベントというものがあり、「リンカ・ローダ実践開発テクニック」という本をいただきました。選ぶ順番が運良く最初の方だったため、割と面白い本が残っている中から選ぶことができ良かったです。

夜に自室に戻ってからは、明日の全体発表会で失敗しないよう、スライドを練り直したり話すことを書き下して練習したりしていました。

5日目

全トラックの最終発表会と閉会式がありました。最終発表会ではかなり大人数の前で話しましたが、練習のおかげで無難に乗り越えられたかなと思います。

他のゼミの発表では、X-I 言語自作ゼミとY-II Cコンパイラゼミの発表が興味深かったです。前者では、シェルのコマンドをつなげたときの読みにくさ・書きにくさを解消するための新しい言語Workflowを実装した発表が印象に残っています。オリジナルの言語を作ることにおいて、アイデアを得る段階がとても難しいと感じていましたが、参考になりました。 また後者では、最適化をとても真面目に頑張った人の発表が印象的で、去年学校の課題で最適化の課題をやった時も自分はここまでできなかったな...と思うなどしました。

帰宅後

2PLで生成したスケジュールからトランザクションのconflict graphを構成して可視化する作業をちょっとやるなどしました。dot便利ですね。

f:id:momohatt:20190830012227p:plain:w100

もっと大きな例で動かしてみたいなという気持ちにもなっていて、講師の人に教えていただいたYCSBを使ってみたい...と思いつつ、ずるずる先延ばしにしています… やらないとなぁ…

というわけで現在の実装はこんな感じです

github.com

まとめると

データベースゼミでは、キャンプ期間中にトランザクションの並行制御を実装するところまで持っていくことができました。Software Transactional Memoryに触れたことがきっかけで並行計算やトランザクションになんとなく興味を持ち、データベースゼミに応募していましたが、ちょうど自分が学びたかったようなことが吸収できたのではないかと思っています。

またグループワーク等を通じて、自分と同じような興味を持ちながら、技術力・実装力が自分の常識を覆すほど高い人に会うことができ、刺激をもらいました。 夏休み前までなぜか*3何に対してもモチベーションが低めな状態が続いていたのですが、キャンプやらインターンやらで尊敬する人に沢山出会っていく中で徐々に回復してきた気がしていて、頑張るぞ〜〜〜となりました。

*1:終了直後から院試やらインターンやらがあったので記事を書くのが遅くなってしまいました…

*2:トランザクションがまとまってatomicに実行されること

*3:振り返れば院試が憂鬱だったせいな気もする