豪鬼メモ

一瞬千撃

トランザクションのACID特性と自動リストア機能

Tkrzwにトランザクション機能を実装したので、ACID特性について確認しておきたい。AとCとIは正常系のみを検討するのであれば容易に達成されるのだが、問題はDだ。Durability=耐久性=耐障害性がちゃんと確保されているかどうか、仕様を説明しながら確認してみる。
f:id:fridaynight:20210605021155p:plain


一般論として、トランザクションとは、一連のデータベース操作に関して以下の条件を満たすものである。これを総称してACID特性などと呼ぶ。ここで言う操作主体とは、アプリケーションのスレッドやプロセスのことである。

  • Atomicity(原子性)
    • トランザクションの成否に関わらず、更新をしている途中の状態が、他の操作主体から観測されてはいけない。例えばレコードAに「1234」と書き込むとして、「12」だけ書かれた状態は観測されてはいけない。複数レコードを使うトランザクションの場合、例えばレコードAとレコードBを更新するとして、レコードAが更新後でレコードBが更新前の状態である状態は観測されていはいけない。
  • Consistency(一貫性)
    • トランザクションの成否に関わらず、アプリケーション側が要求するデータベースの整合性を保たねばならない。例えば自然数のレコードに負数を格納してはいけない。また、同じ条件で同じ操作を行ったなら、必ず同じ結果にならねばならない。
  • Isolation(独立性)
    • トランザクションを複数並行に実行しても、逐次で実行した場合と同じ結果になる。つまり、レースコンディションを起こしてはならない。
  • Durability(耐久性)

ここでまず大事なのは、トランザクションは失敗しても良いということだ。ただし、失敗するのであれば、トランザクション開始前の状態を維持しなければならない。また、成功するのであれば、トランザクション終了後の結果を維持しなければならない。Consistencyは、単に正常系として動作し続けることを要請していて、Durabilityは、それが耐障害性を持つことを要請している。Isolationは、並列処理環境においてもConsistencyが維持されるという要請であり、AtomicityはConsistencyとIsolationを達成するための前提条件となる。

完全なDurabilityを期待するのは現実的ではない。Durabilityは程度問題である。ストレージが壊れてもデータを維持するには複数のストレージにデータを複製しておく必要がある。マシンが壊れてもデータを維持にするには複数のマシンにデータを複製しておく必要がある。テロや大震災に耐えるには、複数のデータセンターにまたがってデータを複製しておく必要がある。核戦争に耐えるには、大陸にまたがってデータを分散させねばならない。

プロセス内で動作するデータベースライブラリに期待されるDurabilityは、プロセスやOSが突然死してもデータが失われないという程度に限定される。ストレージデバイスやマシンそのものが壊れる事態には絶対に対応できないので、想定しない。一方、プロセスやOSが突然死することは普通に起こりうる事象として想定する。何らかの理由で停電するかもしれないし、電源ケーブルに足を引っ掛けるドジっ子オペレータがいるかもしれないし、メモリ不足などでプロセスがkillされることもあろう。

Atomicityは二つの文脈で捉えるべきだ。ひとつは、更新途中にシステムが死んでも、更新途中の状態が残らないようにすることだ。トランザクション中に死んだならトランザクション前の状態で復帰すべきだし、トランザクション後に死んだならトランザクション後の状態で復帰すべきだ。

もうひとつは、並列処理の排他制御についてである。この文脈で考えると、AtomicityとIsolationはほぼ同じことを要請している。Atomicityを満たせばIsolationも満たされる。Atomicityを達成する方法の一つは、トランザクションに関わるレコードをロックすることである。もう一つは、Copy-on-Write的に、更新前を持ち続けて、他のスレッドには更新前の状態にアクセスさせることである。更新を確定させる際には、Compare-and-Swapで、トランザクション間の競合の有無を確認して、競合が検出されたら失敗または再試行すればよい。Tkrzwは両方をサポートする。

プロセス内で動作するデータベースに期待されるAtomicityは、当然スレッド間の排他制御をきちんと行うということである。レコード単体のAtomicityに関しては、たとえトランザクション対応を謳わないデータベースでも、スレッドセーフを謳うならば当然確保すべき機能だ。Tkrzwでは複数レコードにまたがるトランザクションのAtomicityも保証し、ひいてはIsolationとConsistencyも保証する。


TkrzwのHashDBM(ファイルハッシュデータベース)におけるACID対応状況について考えてみる。ここでは追記更新モードでの運用を想定する。まず、単一レコードのConsistencyに関しては、スキーマがあるわけじゃないので、非常に単純だ。SetしたレコードのデータはそのままGetで取得できる必要があるし、RemoveしたレコードのデータはGetで取得できてはならない。これが満たされなければ、データベースが壊れていると言うしかない。逆に言えば、データベースが壊れていなければ単一レコードのConsistencyは達成されていると言える。また、以前に述べたマルチレコードトランザクション機能を使うことで、スレッド間のIsolationが達成され、ひいてはマルチレコードのAtomicityとConsistencyも達成される。実際にキーや値にどんなデータを入れるかはアプリケーション側の責任である。

Durabilityに着目する。Tkrzwでは、更新系のクエリのDurabilityは、デフォルトでは保証されない。どのI/Oモードであっても、更新系のクエリが成功を返したとしても、新しいデータがストレージデバイスに書き込まれている保証はない。例えばSetが成功を返した直後にシステムの電源が落ちたら、そのデータがファイルに書かれているとは限らず、次回起動時にはなかったことになる可能性がある。それでは困るという場合、Synchronizeメソッドを呼ぶ。これは、データベースオブジェクト内、ファイルオブジェクト内、ファイルシステム内、デバイスドライバ内の全てのキャッシュで下層との同期を行う。したがって、Setした後にさらにSynchronizeを呼んで、それが成功を返した時点で、OSの突然死に対してのDurabilityは確保される。言い換えれば、毎回の更新クエリの後に必ずSynchronizeを呼び、その成功をもってトランザクション成功とみなすとすれば、ACIDのDは満たされるということだ。

異常系でのAtomicityに着目する。レコードのデータをファイルに書き込んでいる最中にシステムが死ぬとどうなるだろうか。例えば、メモリマップI/Oでmemcpyをしている途中や、通常I/Oでpwriteが実行されている途中にプロセスが死んだとする。1KBのレコードがあったとして、それを800バイト目まで書いた状態で死んだとする。その事態は次回起動時に検出される。Synchronizeした際にメタデータとして書き込まれるファイルサイズよりも実際のファイルサイズが大きい場合、余った部分は最後にSynchronizeした後に書き込まれたということを意味する。よって、それはトランザクション完了前のデータなので、復旧時に無視すれば良い。Synchronize中に死んだとしても、Synchronizeの最後にメタデータを更新する手順になっているので、メタデータを更新する前に死んだのであればトランザクション前の状態で復帰するし、メタデータを更新した後に死んだのであればトランザクション後の状態で復帰する。

追記モードにおいては、更新の過程のどこでシステムが死んだとしても、デバイスファイルシステムが壊れていないならば、既存のレコードの情報は失われない。データベースの更新はREDOログをファイル末尾に追記する操作と同義だ。個々のログは、ヘッダに自身のサイズを持つ。よって、個々のログを追記している途中でシステムが死んだなら、個々のログのヘッダが短すぎるか、ヘッダに記載されたログのサイズよりも実際のログのサイズが短いことになる。壊れたログは読み出し時に検出し、破棄できる。ログを書き終わったら、該当のログの位置を対応するバケットに書き込む。バケットを更新する前や更新している途中にシステムが死んだなら、バケットは空であるか、そのバケットに連なるログのトランザクション前の最新のものを指し示す。

ちなみに、個々のバケットのサイズ(バケット幅)のデフォルトは4で、それは512や4096の約数なので、個々のバケットがブロック境界やページ境界をまたがることはなく、バケットのデータが不整合を起こすことは稀である。ただ、バケット幅は5や6に変えられるので、バケットは壊れるものとみなしている。いずれにせよ、バケットが最新のレコードを指している保証はないので、システムが途中で死んだ場合のバケットは信用しない。バケットが壊れてもレコードが壊れているわけではなく、レコードが生きていればバケットは復元できるので、問題ない。

バケットの更新が終わったなら、最後にファイルのメタデータを更新し、トランザクションは完了する。メタデータの更新前に死んだならトランザクションは無効化され、トランザクションより前の状態で復旧する。メタデータの更新後に死んだならトランザクション完了後の状態で復旧する。ここにAtomicityの根拠がある。では、メタデータの更新中に死んだらどうなるか。それ以前に、メタデータの更新中に死んだことをどうやって検出するのか。有効なファイルサイズを示す8バイトの数値がメタデータの本体なのだが、上位4バイトを書いた後で、下位4バイトを書く前の状態で死ぬ確率はゼロではない。実際問題として下層のストレージはブロック単位でアトミックであることは期待できるが、保証はされていない。したがって、メタデータが壊れることも想定はせねばならない。メタデータの破壊の検出に関しては、サイクリックマジックデータと呼ぶ仕組みが担当する。メタデータの先頭に、毎回の同期処理の度に増加する1バイトの数値を記録し、メタデータの末尾に同じ数値を記録する。メタデータを読み込んだ際に、先頭のサイクリックマジックデータと末尾のそれが同じ値である場合、メタデータの更新がアトミックに行われていたことが保証される。そうでない場合、メタデータは信用できないので、破棄する。

メタデータの更新は、レコードやバケットの更新が行われた後に、Synchronizeでデバイスと同期した上で、ファイル全体をロックしてアトミックに行われる。メタデータを更新しているということは、その他の更新は正常であることが保証される。つまり、メタデータが破損しているということは、ファイル全体のその他の部分は破損していないということだ。よって、メタデータの破損を検出したら、メタデータを無視してファイル全体のREDOログを再生すればよい。レコードが壊れたならメタデータを見て修復でき、メタデータが壊れたならレコードを見て修復できる。両者の更新は同時には実行されないので、両者が同時に壊れることはない。この二重化にDurabilityの本質がある。トランザクションの成否がメタデータの更新完了(サイクリックマジックデータの末尾1バイトの書き込み完了)の瞬間に決定することにAtomicityの本質がある。

インプレースモードでは、既存のレコードの領域を上書きすることが多い。レコードの領域はブロック境界をまたぐので、書き込みが途中まで成功したが後ろの方は失敗して古いデータのままであるということは普通に起こリ得る。しかも、レコードを書き込んでいる途中で死んだのか、もともとそういうレコードなのかは、後からは判別できない。よって、復旧処理によって変なレコードが取り出される可能性がある。とはいえ、壊れているレコードが途中にあっても、データベース全体が壊れるわけではない。メタデータの整合性を調べて、その先のレコードを探して復旧作業を続けることで、書き込み途中だった場所以外のレコードは復元できる。実際問題として、インプレースモードでも、プロセスが死んだくらいではレコードが壊れる確率は低い。ただし、低くても観測可能な確率があるならば、それはミッションクリティカルなデータを置くに値する方法にはならない。


Durabilityとファイル内キャッシュの関係について補足しておく。以前に述べたファイル内キャッシュのおかげで、ダイレクトI/Oの処理がバッチ化されて、性能が飛躍的に向上した。一方で、キャッシュするということは、書き込みが遅延されるということなので、Durabilityが低下しないように特別な配慮が必要となる。

追記モードにおいて、トランザクションの成功はメタデータの書き込み成功の時点で保証される。メタデータの書き込み成功に到達しなかったトランザクションは、なかったことにせねばならない。ということは、トランザクションの内容である更新レコード(=REDOログ)は、メタデータがストレージに書き込まれるより前に、ストレージに書き込まれている必要がある。そのためには、トランザクション内のレコードの操作が完了した時に一度Synchronizeを呼んで、その成功を確認してからメタデータを書いて、さらにSynchronizeを呼ぶ。

メモリマップI/Oでは、msyncシステムコールにより、ページごとにデバイスとの同期処理を行える。しかし、通常I/Oでは、標準のfsyncシステムコールを使うと、ファイル全体でしか同期処理が行えない。そのため、Linuxでは、sync_file_rangeという独自のシステムコールを実装している。これはmsyncと同様にページ単位で同期処理を行えるものだ。Linuxではsync_file_rangeを活用し、それ以外ではfsyncを用いる。

データベースファイルは、大きく分けて冒頭のメタデータセクションと、それ以外のレコードセクションに分けられる。レコードセクションは必ず4096バイトのページ境界から始まる仕様になっている。したがって、Atomicityを確保するための同期処理の際には、レコードセクションが始まるページ以降に先に同期させてから、メタデータを更新し、その後、メタデータセクションのみを同期させる手順となる。

なお、TreeDBM(ファイルツリーデータベース)はHashDBMの上に構築されているので、追記モードも利用することができ、その際のDurabilityは同等である。TreeDBMはB+木のノードをオンメモリでキャッシュするので、上述のファイル内キャッシュと同様に、遅延書き込みによるリスクがある。対処法も全く同様で、B+木のキャッシュを下層のデータベースと同期させてから、下層のデータベースとデバイスを同期させ、最後にメタデータの更新と同期を行えばよい。

しつこいようだが、キャッシュとは、遅延書き込みのリスクを背負うことで性能向上を図る仕組みである。突然電源が切れた場合、キャッシュにしか乗っていない更新内容はなかったことになってしまう。この宿命は、データベース内のキャッシュでも、ファイル内のキャッシュでも、ファイルシステム内のキャッシュでも、デバイス内のキャッシュでも変わらない。よって、明示的に同期処理=Synchronizeメソッドを呼ばない限り、更新内容のDurabilityは保証されない。よって、トランザクション毎のACID特性を保証したいならば、当然毎回のトランザクション毎にSynchronizeを呼ぶ必要がある。チャットシステムのレコードなど、それほど厳格なデータ保護が必要ではなく、だいたいのレコードがベストエフォートで保護されればいいという程度であれば、定期的にSynchronizeを呼ぶような運用方法でも良いだろう。性能と復旧率のトレードオフは同期の頻度で調整することになる。

Synchronizeメソッドは、ハードモードとソフトモードがある。ハードモードでは、データベース内およびファイル内のキャッシュをファイルに書き出した上で、fsyncシステムコールやmsyncシステムコールを呼んで、デバイスにファイルの内容を同期させる。ソフトモードでは、それらシステムコールの呼び出しを省略する。つまり、ソフトモードではOS層のキャッシュは同期されない。したがって、突然の電源切断に耐えるにはハードモードを使う必要がある。ソフトモードはプロセスのクラッシュには耐えるが、OSのクラッシュには耐えない。ここでも性能とDurabilityのトレードオフがある。データの重要性に応じて、毎回ハードモードで同期するもよし、ソフトモードだけにするもよし、双方を組み合わせるもよし。


今まで、データベースの破壊が疑われる事態では、つまりデータベースオブジェクトを適切に閉じずにプロセスが終了して、そのデータベースファイルを次回開いた時には、データベースは読み取り専用モードになっていた。アプリケーション側の責任でリストア用のRestoreDatabaseメソッドを呼んでもらうという仕様だった。

しかし、「壊れたのを直す」という運用を明示的にやらなきゃいけないのは、ユーザの不安を煽ってしまう。壊れたら直すに決まってるんだから、自動的に直しちゃった方が良さそうだ。そうすれば、障害復旧の手順なんて把握していなくても、気軽にデータベースを使い始められる。見かけ上は、壊れないデータベースに見えることになる。畢竟、壊れているのかどうか、つまり正常系なのか異常系なのかは、認識の問題にすぎない。ウイルスに感染しても発病しないなら風邪じゃない。たとえ内部で復旧処理が行われていたとしても、ユーザがそれに気づかないのであれば、正常系と言える。

ということで、HashDBMのチューニングパラメータに、restore_modeというのを追加した。それを継承したTreeDBMでも利用できる。デフォルト値はRESTORE_DEFAULTで、その場合は、ベストエフォートで、できるだけ多くのレコードを復旧する。カジュアルなユースケースではこのモードが最も使いやすいだろう。値をRESTORE_SYNCにすると、最後にSynchornizeを呼んだ時点の状態に復旧してくれる。トランザクションのACID特性が重要である場合にはこのモードで運用するべきだろう。値がRESTORE_NOOPの場合、従来と同じように、復旧処理を省略して読み取り専用になる。明示的に復旧作業をしたい場合にはこれが有用だろう。

この復旧処理は、正直言って遅い。例えるなら、EXT系のファイルシステムfsckをかけているのと同じようなもので、データベースの規模に応じた時間がかかってしまう。ただし、追記モードとSynchronizeを併用して運用している場合、復旧処理は省略できることもある。メタデータが示すサイズと実際のファイルサイズが一致している場合、データベースの整合性は完全であることを示している。なぜなら、全ての更新処理はファイルサイズを増大させ、そしてメタデータがそれに追従しているということは、一連のトランザクションが完了しているはずだからだ。トランザクションの途中でシステムが死んだ場合には、やはり復旧処理が必要になる。

復旧処理を完全に不要にするには、ジャーナリングを実装するしかない。ファイルの既存領域を書き換える際に、書き換える前のデータを読み込んだ上でどこかに保存して、それに成功した場合にのみ書き換えを行うのだ。書き込みに失敗したならその退避データを使って元に戻すので、退避データはUNDOログと呼ぶこともできる。本番の書き込みの前にログを記録するので、その観点ではWAL(write-ahead log)と呼ぶこともできる。退避データは一時ファイルを作って保存して、本番の書き込みに成功したら消せばよい。ハッシュロックと統合してWALを記録すれば並列化したジャーナリング機能を実装できるだろう。しかし、面倒なのでやっていない。というか、正常系の性能を犠牲にして異常系の性能を上げるというのに、どれくらいの需要があるのか不明だ。明確なユースケースがあればいずれ真面目に考える。


まとめ。Tkrzwのデータベースは、追記モードを利用することで、ACID特性を満たしたトランザクショナルなデータベースとして運用することができる。自動リストアモードのおかげで、明示的にリストアの作業を行う必要もなくなった。