SecurityCamp2022

本ページは、セキュリティキャンプ2022全国大会の、集中コースにおけるデータベースゼミ募集要項の補足ページです。

データベースゼミに興味がある方は是非、本ページを読んでもらって、応募をご検討ください。

セキュリティキャンプ2018/2019/2020/2021全国大会でも同じゼミを同じ講師が担当しています。

これまで 11 名が本ゼミを受講してくれました。また、私の知る限り独学で本ゼミの内容を勉強してくれた方が 1 名います。

データベースシステムとは

データベースは、データの集まりで、特に整理整頓されているものを指すことが多いです。

データベースの操作とは、その中に含まれるデータを検索したり、追加、編集、削除したり、まとめて集計加工をしたりすることです。

データベースシステムとは、データベースの管理やユーザおよびアプリケーションによる操作を受け負うソフトウェアのことを指します。ひとりで使うデータベースであれば、Excel などの表計算ソフトでも足りることが多いと思います。これもデータベースシステムと呼べるでしょう。一方、複数人で共有したいデータベースの場合、同時に同じデータを更新したらデータが壊れたりおかしくなったりしないか気になりますね。そのような心配をしなくていいのが典型的なデータベースシステムです。

データベースシステムといったとき、皆さんは具体的にどんなソフトウェアを思い浮べるでしょうか？オープンソースのデータベースシステムだけとっても、MySQL、PostgreSQL など、商用だと Oracle、DB2、SQL Server、Google Spannar、Amazon Aurora など、たくさんあります。これらは SQL という操作インターフェースを供えており、トランザクション処理が可能です。また、大量のデータを加工、集計する処理も、規模や状況によりますが可能です。

もう少し広い範囲でも見てみることにします。

Hadoop や Spark などは、細かい単位でのデータ操作が苦手で、とりわけトランザクション処理には対応していない代わりに、SQL SELECT 文の実行、つまり、データを大量に加工、集計する用途に特化しています。また、ひとつのホストでは保持できない程の大量のデータを扱えるように、複数のホストをまたがって動作する分散システムです。etcd は、設定情報を分散システムで安全に共有する目的で使われることが多いデータベースシステムですが、Key-value store に分類されます。Key-value store は、主に key を指定して、value を検索、操作するという、SQL よりも単純なインターフェースを持っています。Key-value store に分類される memcached や Redis は、データの永続化をある程度犠牲にしてでも、高速に処理したいデータを扱う目的で使われることが多いようです。

以上のように、目的、用途に応じて様々なデータベースシステムがあります。

トランザクション処理

本ゼミは、上記で紹介した様々なデータベースシステムの一部が持っている機能であるトランザクション処理を対象とします。トランザクション処理は、世の中になくてはならない処理のひとつです。皆さんが銀行 ATM でお金を入出金したり、送金したりする度に、裏でトランザクションが実行されます。ATM での操作が「きちんと」実行されないと困りますよね。また、皆さんがインターネット上の販売サイトで何かを購入するときに、決済(支払い)の画面で、決済ボタンを押す度に、裏でトランザクションが実行されます。これらの操作も「きちんと」処理してくれないと困りますよね。お金のやりとりにはほぼ必須ですが、それに限らず様々なやりとりでトランザクション処理は必要とされています。世の中には「きちんと」処理してくれないと困るデータが多いからです。「きちんと」がどういう意味を持つかについて理解するには、ACID 特性の理解が必要となります。興味を持った方は自分で調べてみてください。

トランザクション処理の重要性について書きましたが、本ゼミが開講されている一番の理由は、講師である私が、トランザクション処理をおもしろい、と思っているからです。

トランザクション処理を学ぶべき人

アルゴリズムとデータ構造を学ぶのがおもしろいと思う方は、トランザクション処理もおもしろいと感じる適性が間違いなくあると思います。何故ならトランザクション処理は、メモリ上、ディスク上で、様々なデータ構造を必要とし、その操作に伴うアルゴリズムを必要とするからです。並列プログラミングが大好きな人も、トランザクション処理の性能を高めるために、それを駆使する必要があるので、楽しいと思います。CPU やメモリ、ストレージデバイス、ネットワークデバイスなどのハードウェアに興味がある人にも、トランザクション処理(に限らずデータ処理全般)はハードウェアの機能や特性をいかに活用するかという側面がありますので、楽しめると思います。分散システムに興味がある人も、通信遅延やノード故障が起きる中、良い性質と性能が必要とされるトランザクション処理もあるため、楽しめると思います。

データベースゼミの目的

本ゼミを通じて、データベースシステムの仕組みを理解し、作る側になれる人を増やしたいと思っています。

セキュリティという観点では、SQL インジェクションはトピックのひとつかと思いますが、本ゼミでは SQL を扱いません。データベース操作言語といえば SQL というくらい普及していますが、SQL はデータベースシステムを操作するインターフェースのひとつであって、本ゼミで注力したいトランザクション処理には直接関係ないからです。

SQL についての情報はたくさんあります。本もたくさん出ています。それはデータベースシステムを使う人に必要な知識で、データベースシステムを使う人はたくさんいるからです。また、トランザクションを伴うアプリケーションを設計実装する人達は、ひとまとめにしたい複数のデータベース操作をひとつのトランザクションにまとめるだけで済むことが多いと思います。それほどトランザクションという概念のもたらす抽象化は良く出来ており、使う側にとっては便利な道具だと思います。一方で、その皺寄せがトランザクション処理を実行するデータベースシステムに来ているのです。

データベースシステムを作れるであろう人は、私が思うに少ないです。もちろん、使う人ほど多くなくていいですが、作る人がもっといて欲しいなと思います。さらに、データベースシステムの作り方を教える人も少ないと思います。というわけで、微力ではありますが多少の心得がある私が本ゼミを担当することになり、応募を検討されている皆さんに向けてこの文章を書いているというわけです。

データベースゼミで学んでもらうこと

本ゼミでは、トランザクションを処理する仕組みについて実際にプログラムを作ることを通して学んでもらいます。

トランザクションを実行するのに必要な主な仕組みは、メモリ上およびディスク上でデータに効率良くアクセスするためのアクセスメソッド(インデクス構造)、効率的に更新データの永続化を行うためのログ先行書き込み (Write-ahead logging, WAL)、およびトランザクションを同時にたくさん実行するための並行実行制御(Concurrency Control) です。

私がおもしろく、そして難しいと思うところは、トランザクションを並列に実行するための、様々な仕組みで、Concurrency Control はそのひとつです。ただ、Concurrency Control をデータベースシステム上で実現するにあたって、本当に複数の CPU コアを使って複数のスレッド/プロセスでトランザクションを並列に実行する場合、複数スレッド/プロセスからひとつのデータ構造にアクセスするので、並列プログラミングと言われている技術が必要になります。具体的には lock や latch などデータの適切な排他を行う仕組みが、場合によっては、lock-free だとか mutex-free と呼ばれているような技術もです。

本ゼミに与えられた時間でそこまで到達するのは簡単ではないと思っています。そこで、並列処理にチャレンジする前に到達して欲しいマイルストーンとして、シングルスレッドで、基本的なトランザクション処理ができるデータベースシステムが動くことを目指して欲しいと思います。シングルスレッドプログラムに対象を絞ったときは、初めに、ディスク、つまり永続ストレージの特性と操作について、次にデータ構造(主にアクセスメソッドとしてのインデクス)、そして WAL (と checkpointing) について学んでもらいます。ここまでを実装すると、クラッシュリカバリができるようになり、最低限のトランザクション処理ができるデータベースシステムですよといえるようになります。

次なるステップとして、Concurrency Control について学んでもらおうと思っています。これには、2 つのアプローチがあります。ひとつめは、カーネルスレッドではなく、ユーザースレッドもしくはそれに準ずる手法を用いて、Concurrency Control の仕組みを実装し、動かしながら学んでもらうアプローチです。このアプローチの良いところは、スレッドセーフなデータ構造を使ったり並列プログラミングの技法を駆使しなくても Concurrency Control を動かせることです。ふたつめは、既存のスレッドセーフなデータ構造ライブラリを使って、複数のカーネルスレッドで動かすことを前提に Concurrency Control の手法を実装するアプローチです。こちらは、Concurrency Control 実装に並列プログラミングが必要となります。ここまでで、一通りトランザクション処理の要素技術の基本は学べます。

セキュリティキャンプの期間中には難しいかも知れませんが、これらの経験を積んだ後、是非皆さんの興味が強いテーマを深欲りして欲しいと思います。たとえば、インデクス構造を自作したり、スレッドセーフにしたり、性能を追求するとか。WAL の仕組みを改善してみるとか、並列化してみるとか、Checkpointing を頑張ってみるとか。異なる Concurrency Control 手法を実装してみるとか。よりハードウェアの性能を活用できるような方法を考えてみるとか。

前提となる知識と経験

プログラミングをまったくやったことがない方は本ゼミへの応募をご遠慮願います。本ゼミでは、いちからコードを書いて動かしてもらいますので、プログラムを書いたことがない人には荷が重いからです。事前学習ではトランザクション処理の理解や必要な部品の開発に時間を使ってもらいたいので、プログラミングそのものを学ぶ時間はあまりありません。プログラミングをやったことがない方でも、ここまで読んだのに応募できないなんて、、、と残念に思う必要はありません。今こそ絶好の機会だと思ってプログラミングを始めましょう。

知識について、基本的なアルゴリズムとデータ構造について理解していれば、足りないということはありません。Balanced tree と Hash table の特性の違いだとか、Search と Sort アルゴリズムだとか。分からなければ、必要に応じて学べば良いです。必要な知識を皆さんが効率良く得られることを目的とした資料を用意しています。

開発に用いるプログラミング言語について

データベースシステムは、C/C++ などのメモリや CPU を直接扱いやすい言語で書いてあることが多いですし、最近ですと、Go や Java で書かれているものもあるようです。過去 4 回の開講でもそうしましたが、本ゼミは、使うプログラミング言語を特に制限しないです。もちろんアドバイスを求められれば私の知る限りコメントしますが、使う言語は皆さん自身に決めてもらいます。これまでの実績では、C, C++, Java, Rust, Go が使われています。私は C、C++、Java、Python あたりは一応読めますが、Go や Rust はあまり自信がありません。本ゼミで設計やコードのレビューをするときは、主に受講生の方に説明してもらいながら質問およびコメントをする形式になると思います。そのため、私があまり慣れていない言語だとしても適宜説明して頂ければ問題はないです。どんな言語を使おうが、設計の大枠や、アルゴリズム、そして、CPU やメモリやディスクなどのハードウェアが力を発揮できるようお願いをする、ということは変わりません。

応募を考えている皆さんへ

皆さんには、本ゼミで学んだことを生かして、いずれ、是非オリジナルの特徴を持ったデータベースシステムの開発にチャレンジしていただきたいですし、実用的なデータベースシステムを作る側の人になって活躍して欲しいです。もちろん、データベースシステムを使う側の人になったとしても、ここで得た知識は多いに役立つでしょう。どのような仕組みになっているかを知らないで使うのと、知っていて使うのでは、大きな差が出ます。例えば、データベースシステムが苦手な処理をそうと知らずに大量に実行してしまい、性能障害を引き起こしてしまうなどです。是非、データベースシステムの気持ちを分かる人になって欲しいと思います。また、研究領域でもまだまだ課題はたくさんあり、それらを解決に向かわせる新しい手法を探求していって欲しいとも思います。

データベースシステムは、秘密にしなければならないデータを格納することも多いので、データの漏洩や改竄をされないように厳重に守らなければなりません。その第一歩は、バグを出来るだけ少なくするような設計実装であることはいうまでもありませんが、データベースシステムそのものだけでなく、周辺環境、使う人達のことも含めて、セキュリティを十分意識して頂きたいと思います。

本ページを読んだ上で、おもしろそうだ、是非やってみたい、と思った皆さん、ご応募お待ちしています。

Changelog

2022-03-31 2021 版を修正