8/8から8/12に行われたセキュリティキャンプ2022のデータベースゼミに参加してきました. このゼミでは, データベースの中でもトランザクションを中心に学び, 実装しました. 講師の星野さん(@starpoz), ありがとうございました.
ゼミの講義資料がGitHubで公開されたので貼っておきます. Releaseページからpdfをダウンロードできます.
https://github.com/starpos/develop-transaction-system
Rust製のサーバクライアントモデルのkvsです.
サーバはgrpcを使っているのでgrpcurlからも使えますが, セッションのTTL管理やbase64エンコードが大変なのでリポジトリに入っているcliクライアントを使った方が便利です.
$ tkvs-client https://tkvs.kgtkr.net
> get key1
ok: value1
> put key1 hoge
ok
> range [a,z]
key1:hoge
x:value
xx:hoge
> commit
ok
$ grpcurl -d @ tkvs.kgtkr.net:443 kgtkr.tkvs.Tkvs/StartSession <<"EOD"
{}
EOD
{
"sessionId": "xMBEVysIoKLIoHNRoR3SMMAlewSZEI3A",
"ttl": "60"
}
$ grpcurl -d @ tkvs.kgtkr.net:443 kgtkr.tkvs.Tkvs/Get <<"EOD"
{
"session_id": "xMBEVysIoKLIoHNRoR3SMMAlewSZEI3A",
"key": "a2V5MQ=="
}
EOD
{
}
$ grpcurl -d @ tkvs.kgtkr.net:443 kgtkr.tkvs.Tkvs/Put <<"EOD"
{
"session_id": "xMBEVysIoKLIoHNRoR3SMMAlewSZEI3A",
"key": "a2V5MQ==",
"value": "dmFsdWUx"
}
EOD
{
}
$ grpcurl -d @ tkvs.kgtkr.net:443 kgtkr.tkvs.Tkvs/Get <<"EOD"
{
"session_id": "xMBEVysIoKLIoHNRoR3SMMAlewSZEI3A",
"key": "a2V5MQ=="
}
EOD
{
"value": "dmFsdWUx"
}
$ grpcurl -d @ tkvs.kgtkr.net:443 kgtkr.tkvs.Tkvs/Commit <<"EOD"
{
"session_id": "xMBEVysIoKLIoHNRoR3SMMAlewSZEI3A"
}
EOD
{
}
ACID特性を満たすデータベースを実装することが目的です. 最小の実装はインプロセスで動き, インメモリ, 同時に1つのトランザクションしか動かせないget / put / delete / commit / abortができるkvsあたりになります. その後に機能を拡張していくことになります. 今回は拡張する機能として, 並行でトランザクションを動かせるようにする, サーバクライアントモデルにする, rangeクエリの実装を選択しました. isolationは複数のisolation levelが考えられますが, 今回は最も厳しいserializableを選びます. serializableというのは並列で動いているトランザクションの実行結果と一致するような, 直列なトランザクションの実行順が存在するというisolation levelです.
最小構成の実装だと複数のトランザクションが同時に動くことはないので, 独立性は自動的に満たされます. よって, abortできる仕組みの実装と, atomicな永続化が主な部分となります.
この構成では, DBのデータ構造は以下のようになります.
struct DB {
values: BTreeMap<Bytes, Bytes>
write_set: BTreeMap<Bytes, Option<Bytes>>
}
values はコミット済みの確定したデータ, write_set はまだコミットしていないデータです. write_set は「未確定の削除」を表す必要があるので値は Option になります. get / delete は write_set を操作し, get は write_set に値が存在すればそこから, 存在しなければ values から値を読み込むことになります. こうすることで abort したい時は write_set をクリアするだけで行うことができます. commit は後述する方法で永続化を行った後, write_set の内容を values に反映させ, write_set をクリアします.
永続化はログファイルに追記によって行いますが, 突然マシンがクラッシュしてもデータが壊れないようにするため, atomicなファイルへの追記を行う仕組みが必要です. そこで, 各レコード(DBのレコードではなくログファイルの1レコード)にハッシュ値を付与し bodyのサイズ,bodyのハッシュ値,body というバイナリ形式で保存します. 読み込み時にハッシュ値をチェックすることで途中までしか書き込めなかったレコードは捨てます. これによって, 追記がatomicなものになります. このDBではログファイルの1レコードは1トランザクションの write_set である BTreeMap<Bytes, Option<Bytes>> になります. 1トランザクションのデータをatomicに永続化することでトランザクションの原子性を保証できます. このデータのエンコード形式は本質ではないのでserde+bincodeを使いました. また永続化が終わってからコミットに成功したと通知することで永続性も満たされます. トランザクションの完了通知の前にバッファのflushやfsyncを忘れないようにしましょう.
これで永続化は一応できますが, ログファイルへの追記だけだと更新や削除された古い値がいつまでも残り, ストレージを圧迫するので適当なタイミングでスナップショットを取りましょう. これはcommit済みデータである values をatomicに永続化します. これは, よく使われるtmpファイルに書き込んで, renameする方法です. これが終わったらログファイルを削除または, truncateします. DBの起動時にはスナップショットファイルの中身を読んだ後に, ログファイルの各トランザクションのデータを1つずつ適用することで状態を復元します. もしスナップショットの永続化が完了したが, ログファイルの削除が終わっていないタイミングでクラッシュしても, ログファイルの適用は少し考えると冪等であることが分かるので問題ないです.
最初の拡張として, トランザクションを並行に動かせるようにします. 今回実装したものは, DB本体, 各トランザクション同士がメッセージパッシングによってやり取りを行い, それぞれは直列に動いているという設計です. DB本体と, 各トランザクション同士は並列に動いていますが, あまりCPUを生かせている実装とは言えません. しかし, データ構造の排他処理を考えなくてよくなるのでこうしました. それでも, トランザクションの排他処理は必要です.
例えばpostgresだとread committedがデフォルトなのでnon repeatable readが許されています. non repeatable readは以下のような動作です.
trx1.get("key1") // x
trx2.put("key1", "y")
trx2.commit()
trx1.get("key1") // y
このように1つのトランザクションで複数回getした結果が, 他のトランザクションがcommitしたデータによって結果が変わることがあります. しかし, serializableだとこれは許されないので何らかの排他制御が必要です.
例えば, 一度読んだデータをトランザクションが保持し, 以降のgetではそのデータを読む, コミット時に持っている読んだデータと, DBのデータを比較し, 変化があれば直列化エラーでコミットを失敗させるという楽観的な方法です. ただ, こちらの方法はあまりに実装が自明で面白くなさそうだったので, 悲観的なロックを取る方法で実装しました. SS2PLという方法がベースになっています. この方法では, readロック同士は共存可能だが, writeロックは排他的, ロックの解放はトランザクション終了時に行います. 実装は各レコードが現在のロック状態と, ロックを持っているトランザクションの一覧(readロックなら複数個がありえる)と, readロックを待っているトランザクションの集合と, writeロックを待っているトランザクションのキューを持ちます. そしていい感じにread lock, write lock, unlockの処理を実装します. この実装はコーナーケースに気をつけてひたすら分岐するといったものになります. 例えばコーナーケースとしては, 既にreadロックを持っているトランザクションがwriteロックを取ろうとした時に, 他のトランザクションがreadロックを持っているかによって, 待つか, writeロックに昇格させるかが変わったり, readロックのunlock時に他にreadロックを持っているトランザクションがあるかによって処理が変わったりといったものがあります.
そして悲観的ロックということは当然デッドロックも存在します. 今回はトランザクション同士の待機関係を依存関係グラフにし, 閉路を検出することでデッドロックが発生するようなロックは拒否するという設計にしました. これは重い計算なので効率は悪いですが, タイムアウトといった方法より面白そうだったのでこの方法にしました.
次にrangeクエリの実装です HashMap ではなく BTreeMap を使っていたのはこのためです.
rangeクエリは BTreeMap::range を使えば終わり…ではありません. 何故ならisolation levelがserializableだからです. read committedや, それより1段階厳しいrepeatable readであればこれで終わりですが, serializableではphanom readと呼ばれる以下のような動作を防がなければいけません.
trx1.range("a", "z") // b=1, p=2
trx2.put("d", "3")
trx2.commit()
trx1.range("a", "z") // b=1, d=3, p=2
trx1の2回のrangeの結果のキー集合が違いますね. もし, b や p の値が違えばこれはnon repeatable readなので既にロック機構によって防がれていますが, d という新たなキーが追加されるというのは別の話です. 悲観的な方法では, 範囲ロックを行い, ロック範囲を分割したり統合したりを上手くやってとなるのでしょうが, 複雑すぎて実装できる気がしなかったので, ここに関しては次のような楽観的な方法で妥協しました(以下に書くようにpostgresも楽観的な方法であると書いてあったので妥協する後押しになった). rangeクエリの結果のkey集合を記憶しておき, commit時にもう一度rangeを行い結果が一致するかを確認して一致しなければ直列化エラーにします. rangeクエリでは複数回の実行の結果が異なることはありえますが, commit時に直列化エラーになるという設計です. こういう設計なので, コミットするまで結果を信じてはいけません. ちなみに存在するキーに関してはgetと同じように悲観的なロックがかけられます. getは存在しないキーに関しても悲観的なロックを行うので, getが完全にrangeの特殊な場合とはなっていません.
実際、この分離レベルは、（ある時点で）逐次実行可能なすべてのトランザクションにおいて、シリアライザブルトランザクションの同時実行の組が一貫性のないような振る舞いをしていないか監視することを除き、リピータブルリードと全く同じ動きをします。 この監視では、リピータブルリードが示すものを越えてブロックすることはありませんが、監視によりいくらかのオーバーヘッドがあり、直列化異常を引き起こすような状態の検知は、直列化の失敗を引き起こすでしょう。
https://www.postgresql.jp/document/9.4/html/transaction-iso.html (13.2.3. シリアライザブル分離レベル)
クラッシュした時にデータが消失しないかのテストを書きました. 電源断をシミュレートするテストはDockerなどのコンテナよりVMを使うべきとのことだったので, qemu-system上で行いました. イメージは arch linux のcloud image を使っています. 理由は手動での初期設定が不要(完全に自動テストが可能), かつターミナル上にカーネルの起動ログが出せる(CIで実行可能), UEFIバイナリを用意しなくても動くといったメリットがあるからです. まずvmを起動し, クロスコンパイルしたlinux向けバイナリを転送, 起動, その後grpc経由でホストマシンから大量のランダムデータを挿入, ランダムな時間経過後にqemuのプロセスをkillし, 再起動した後にcommit済みデータが問題なく永続化されているかを確認します. このテストでは, ハッシュ値のチェックロジックや, fsyncを行うコードを削除するとテストが落ちるが, 現在のコードでは成功することを確認しました.
注意点として, 正しいデータの集合が1通りに定まるとは限らない場合があります. 例えば以下のような場合を考えます.
put a x
put b y
commit <- 成功
put a z
commit <- 電源断によって失敗
この時, a=x, b=y でも a=z, b=y でも正しいです. 何故なら2つ目のコミットの失敗は, 永続化には成功したが, レスポンスを返す前に電源が落ち, クライアントには失敗と通知されている可能性が考えられるからです.
使っているイメージの問題なのか, 初回起動時はopensshサーバが起動してくれず, ある程度の初期化が終わった段階で再起動しないと動かないという問題が発生しCIでテストを動かす時にハマりました. Dockerはある程度使い慣れていますが, qemuはほとんど使ったことがないので使い方が分からず大変でしたね.
ファイルシステムや, データベースが何をどこまで保証してくれているかということをある程度理解できました.
WebのAPIサーバだと, 基本的に状態はDBに永続化するので, ファイルシステムへの永続化で気をつけるべきことというのは少し話を聞いたことがある程度の理解でした. しかし, 実際に触ってみると思っていた以上に気をつけるべきことが多いので, 基本的にDBに永続化, ファイルを扱う時はある程度高レベルなatomicなファイル操作のライブラリを使うべきだと思いました.
DBはそれなりに使っているにも関わらず, 特にisolationの理解が適当で, isolation levelを知らなかったので「複数のトランザクションを並列に実行しても直列に実行した結果と一致するようにしてくれるらしいけど, そんなものを効率良く実装できる魔法のようなアルゴリズムってあるのだろうか」という軽い疑問はありましたが, 深く調べたことがあったわけでもなく, 事前課題で少し調べて, そんな魔法のようなものはやっぱりなかったと知った時は驚きましたし, もっと気をつけて使うべきだと感じました. こういう薄い理解で魔法のようだと思っていたものが, そうじゃなかったと分かる瞬間って楽しいですね.
またtokioの今まで使ったことなかった機能を使う機会になったのも大きかったです. こちらもAPIサーバだと状態はDBが持ち, ジョブキューも外部のシステムを使い…といった感じでなるべくステートレスに実装することが多いので, そうでない並列なアプリケーションを実装するいい機会になりました.
ここまでセキュキャンで作ったものに関する解説をしましたが, 最後に日記的なものも書いておきます.
セキュキャンの存在は前から知っていましたが, 毎年応募締め切り直前にやっぱ来年でいいかを繰り返し, 気づいたら参加できる最後の年になっていました. DBゼミを選んだのは, 1人ではできなさそうかつ, トランザクションシステムはどうやってあんな「いい感じ(よく分かっていない)」に動いてくれるのかという興味, Webシステムを作る上でももっとしっかり理解しておきたいというのがあったからですね. 応募課題は1つだとなんとかなる重さですが, 第3希望まで出せるので3つやるのはかなり大変でした.
6月終わりから事前学習が始まり, 少しずつ資料を読み進めたり, 実装をしました. しかし7月後半は期末期間だったので実装はそれが終わってからでしたね. 分からないところの相談をしたりしながら, クラッシュテストとrangeクエリ以外の実装を事前に終わらせました.
セキュキャン本番は5日間あり, 中3日は8:30〜20:30までの12時間です. そして月曜日と金曜日は開閉会式やLT会があるのでゼミの時間は全くありません. 水曜日も協賛企業イベントが4時間あります. 意外と実装に使える時間がないですね. そして夏休みに入り9時に寝て18時に起きるみたいな生活をしていたので, 午前中に頭が働くはずもなく実装はあまり進みませんでした. 体力がなかったり夜型の人は事前になるべく終わらせておきましょう(やっておいてよかった). そんな状態でしたが, なんとかクラッシュテストとrangeクエリの実装を終わらせることができました. ちなみにこれを書いているのはセキュキャン次の日ですが, 18:30に起きました. 生活習慣を戻すのは難しいですね.
ゼミの時間以外は他のクラスの人も含めた活動があります. LT会では自分が全く知らない分野の話を聞けたりしてよかったです. こんな感じで, 朝はめちゃくちゃつらかったのですが楽しいイベントでした. 運営の方ありがとうございました.