豪鬼メモ

一瞬千撃

再構築しない復旧処理

データベースファイルを開いたプロセスが突然死した場合、次回にそのファイルを開いた際には自動的に復旧処理が走るようになっている。従来のバージョンでは、復旧に際して、データベース内の全レコードをスキャンして、データベースを再構築するのが専らであった。これは確実な方法だが、データベースの規模に応じた時間がかかってしまう。実際にはファイルを閉じなくても不整合は起きないことが多いので、その場合には再構築をしなくても復旧できる。よって、整合性の検査をした上で復旧処理を省略して高速化する機能を追加した。
f:id:fridaynight:20210701230246p:plain


データベースファイルを開いているプロセスが死んだとしても、あるいはOSが突然死したとしても、多くの場合、実際にはデータベースの内容は壊れていない。死んだその瞬間にデータベースの更新処理が行われていた場合、該当のレコードのデータは壊れるかもしれない。しかし、個々のレコードの更新処理はメチャクチャ速いので、死んだ時にたまたまデータベースが更新中である可能性はそんなに高くない。アプリケーション側の処理中に死んだならば、少なくともそのスレッドに関してはレコードの更新途中ではないことになる。停電やOSレベルの暴走の場合には、プロセスがいつ巻き込まれて死ぬかわからないけれど、アプリケーションのバグや暴走はデータベースの処理と時間的に分離されて起こることが多い。

ともかく、壊れていないのなら、直す必要もない。なので、実際に復旧処理を行う前に、データベースの整合性の検査を行って、合格すれば復旧処理は省略するのが効率的だ。整合性の検査方法は、インプレース更新モードと追記更新モードで異なる。

ここで、インプレース更新モードと追記更新モードについておさらいする。インプレース更新モードでは、既存のレコードの値を書き換える際に、可能であれば既存のレコードの領域をそのまま書き換える。また、消されたり移動されたりしてフリーブロックになった領域を再利用して、可能であればそこにレコードのデータを書き込む。一方で、追記更新モードでは、それら二つの工夫を禁止し、最新の値を持ったレコードが常にファイルの末尾に追記される。追記されたレコードのアドレスはハッシュ表のバケットに書かれ、既存のレコードの値は追記されたレコードの子供として連結リストに入れられる。これによって、最新の値が常に先に発見される。レコードの削除は削除フラグを持ったレコードの追記として実現される。

インプレース更新モードの整合性検査では、データベース内のレコードを最初から最後まで調べる必要がある。インプレース更新モードの場合、データベース内のどこが更新されていたかが分からないからだ。インプレース更新では、既存の領域を書き換えるので、書き換え途中にプロセスが死んだなら、そのレコードが不正な状態になる可能性がある。また、レコード本体の書き込みが成功したとしても、そのレコードを検索可能にするための連結リストの更新に失敗する可能性がある。その場合、そのレコードが検索できないことになる。

そこで、個々のレコードの本体のチェックサムCRCが整合していることを確認した上で、ハッシュ表のバケットから辿る検索処理を行い、そこに到達できるかどうかを確認する。また、連結リスト上の子供がいる場合、子供のレコードが存在して読み出しができるかどうかも調べる。全てのレコードがそれらの検査に合格したなら、データベースは壊れていないと言えるので、復旧処理は省略できる。

一方、追記更新モードの整合性検査では、最後にSynchronizeを呼んだ時のファイルサイズの位置から後ろだけを調べればよい。なぜなら、Synchronizeした時に、そのファイルの完全性は保証され、その後に既存の領域は変更されないからだ。

追記更新モードでも、ハッシュ表のバケットの更新は起こる。新しい更新は常に連結リストの先頭に来るため、該当のレコードに到達するには、ハッシュ表のバケットから直接到達するか、自分より後のレコードを経由して到達することになる。すなわち、ハッシュ表の該当バケットを調べて、その値が自分か、自分より後ろのレコードを指し示している場合には、その時点で経路の検査は合格とみなすことができる。後のレコードへの到達経路も後で検査されるので、後続の全てが整合しているなら、自分も整合しているとみなせる。同じ理屈で、最後にSynchronizeした後の領域が整合しているなら、全ての領域が整合しているとみなせる。

なお、ファイルの末尾にある最後のレコード本体のみが壊れていて、追記更新モードである場合、そのレコードはなかったものとみなして、再構築を省略できる。レコード本体を書き込んでいる最中に死んだということは、該当するバケットはまだ更新していない。追記更新モードであるということは、追記されるレコードはその時点では連結リストの上に存在していない。よって、そのレコードを無視すれば、ハッシュ表と連結リストの一貫性に問題は起こらない。とはいえ、この理屈が成り立つのは、アプリケーション層での書き込みの順序とストレージへの書き込みの順序が逆転しない場合に限られる。OSが突然死した場合には、後に実行された書き込みのみが反映され、先に実行された書き込みは反映されないという事態は起こりうる。

しかし、それを言い出すと、msyncやfsyncを呼ばない運用では、そもそも何も保証などない。更新された領域がmsyncやfsyncをされずにOSが死んだ場合、その領域のデータが更新されているのかされていないのかは、わからない。更新されているかされていないかというバイナリではなく、更新されている場所もところどころあれば、そうでない場所もところどころあるという可能性があるので、何も信用はできない。信用できないデータを読んで復旧作業を進めるのだから、確率的な事しか言えない。レコード本体のチェックサムCRCが合致しているなら、そのレコードは壊れていないとみなす。たまたまチェックサムCRCが一致する確率は十分に低い。そして、個々のレコードが検索で到達できるなら、ハッシュ表や連結リストも壊れていないとみなす。壊れたアドレスを参照していたとしても、そこから読み出したレコードのキーのハッシュ値がたまたま一致する可能性も十分に低い。

ここまでで、個々のレコードのデータが整合性を保っていて、検索可能であるということを確認する手順が明らかになった。しかし、もう少し問題がある。データベース全体のメタデータはSynchronizeした時にのみファイルに書き込まれるので、つまりSynchronizeした後の情報は反映されていない。もし、データベースを更新する度にメタデータを更新すると、性能や並列性の上で不利になってしまうので、それはできない。よって、個々のレコードを読んでメタデータを復旧する手段を考えねばならない。ここで言うメタデータとは、全てのレコードの数を数えた「レコード数」と、レコードのキーと値のサイズの合計値である「実効データサイズ」の二つだ。

インプレース更新モードの整合性検査は、全てのレコードを調べるので、その際にレコード数と実効データサイズを算出しなおせばよい。一方で、追記更新モードの場合は、そうはいかない。最後にSynchronizeした場所以降しか調べないからだ。これについては、データベースフォーマットに少し手を入れて対応する必要があった。

追記更新で書かれるレコードは更新ログとみなせるが、従来は、VOID、SET、REMOVEという3種類があった。VOIDは、何もしないという意味だ。これはインプレース更新モードのデータベースで生じたフリーブロックを追記更新モードで扱うためのものだ。SETは、レコードのキーと値を属性として保持していて、新しいレコードを追加したり、既存のレコードの値を変更したりする機能を持つ。REMOVEは、キーを属性として保持していて、既存のレコードを削除する機能を持つ。これらをファイルの先頭から再生すると、データベースの過去または現在の任意の状態が再現できるというわけだ。

レコード数を復旧する際に問題となるのは、SETが、新規レコードの追加と既存レコードの更新の両方に用いられていることだ。そうすると、SETの数とREMOVEの数を調べるだけでは、レコードの数がわからないのだ。連想配列でキー毎に数えればレコード数を調べることは可能だが、それに必要なメモリ空間はデータベースの規模に比例するので、許容できない。よって、SETの役割を二つに分離して、既存レコードの更新を行うSETと、新規レコードの追加を行うADDにする。そうすると、ADDとREMOVEの差を取ればレコード数が分かる。ちなみに、前回の記事で議論したが、ログの種類は2ビットで表現しているので、同一フォーマットのまま、4種類を表現できる。よって、第4の種類であるADDを無事に追加できる。

実効データサイズを復旧するには、REMOVEとSETに、その操作以前の値のサイズを記録しておく必要がある。さもなくば、やはり連想配列を使ってキーの単位で集計をする必要が生じるが、それは空間コストの理由で許容できない。しかし、障害復旧のためだけに、REMOVEとSETの空間効率を悪化させるのも気が引ける。Tkrzwの追記モードのコンセプトは、REDOログであって、UNDOログではない。もし障害復旧の効率を重視するのであれば、サイズだけでなく値の内容も記録した完全なUNDOログにして、レコード本体の効率的なロールバックもできるようにするだろう。ということで、割り切って、実効データサイズは復旧できなくてもよいことにする。レコード数はアプリケーションロジックの上で重要なデータになりうるが、実効データサーズは主にチューニングや運用上の指針に使うだけなので、障害時に多少ずれても問題ないだろう。

復旧の方法によってどのくらいかかる時間が違うのかを調べてみよう。キーと値が8バイトずつのレコードを1000万個格納したデータベースファイルを作っておく。ファイルサイズは300MBである。950万個を格納した時点でSynchronizeを呼び、残り50万個はその後に追加されるようにしておく。同様にして、レコードを1億個格納して、9500万個の時点でSyncronizeを呼び、残り500万個をその後に追加したファイルも作っておく。ファイルサイズは3GBである。それらを復旧するのに、どれだけ時間がかかるのか。単位は秒。

1000万レコード 1億レコード
全体の再構築 7.960 358.728
インプレース更新モードの全体検査 5.856 68.469
追記更新モードの一部の検査 0.611 6.573

1000万レコードくらいだと、全体の再構築とインプレースモードの全体検査の時間はそんなに変わらない。しかし、1億レコードになると、全体検査で済ませた方が圧倒的に速く終わる。検査でも再構築でも全体をスキャンしているのだが、やはり読み込みだけで済むのと書き込みも行うのでは速度が違う。小規模の場合はCPUの負荷が物を言うので検査と再構築の差は小さいが、大規模の場合にはI/Oの負荷が物を言うので、差が大きくなる。

追記更新モードで検査対象が絞り込まれた場合は、当然その分だけ高速化する。定期的にSynchronizeする運用であれば、ほぼ一瞬で障害復旧できることが多いということだ。追記更新モードは一見効率が悪そうで、実運用上の利点は多い。

ここまでの工夫は、全て暗黙裡に行われる。アプリケーション側では、単にOpenメソッドでデータベースを開けばよい。もし前回の利用時のプロセスが突然死していたとしても、最善と思われる手段が勝手に選択されて実行される。自動的な復旧処理が行われていたか知りたい場合には、IsAutoRestoredメソッドを呼べば良い。

整合性の検査をした結果として、不整合が検出された場合には、全体の再構築が行われる。その場合、整合性検査をしなかった場合よりも復旧に時間がかかることにはなる。とはいえ、多くの場合で不整合は起きないので、デフォルトで整合性の検査を行う。もしそれを嫌って、最悪復旧時間の低減を目指すのであれば、明示的に再構築処理を呼び出すこともできる。RESTORE_READ_ONLYモードでデータベース開けば自動復旧は行われない。そうすると、前回の利用時に問題があった場合にはIsHealthyメソッドが偽を返すので、データベースを閉じてから、RestoreDatabaseメソッドで再構築処理を行えばよい。


まとめ。データベースファイルがきちんと閉じられなかった場合の復旧処理に際して、従来のバージョンでは必ずデータベース全体の再構築を行っていた。多くの場合は実際には不整合は起きていなくて再構築は必要ないので、整合性を検査して再構築を省略する処理を実装した。結果として、1億件の規模では復旧時間が大幅に短くなることが確認できた。特に追記更新モードで定期的にSynchronizeを呼んでいる場合、差分だけの検査で済むので、非常に効率的に復旧処理が完了する。