前回までの議論で、Tkrzwを追記更新モードで運用した場合、トランザクションのACID特性を満たすデータベースとして機能することを確かめた。Synchronizeした時に状態が決定してファイルに固定され、次にSynchronizeするまでにプロセスが死んだなら、直前にSynchronizeした状態に自動的にロールバックしてくれる。その意味で、Tkrzwは壊れないデータベースと言える。今回は、Synchronizeしないで運用した場合に、ベストエフォートで、できるだけ多くのレコードを取り出す機能について検討する。
上の図は、前回と同じく追記更新モードの模式図だ。レコードを更新する際には、常に新しいデータがファイルの末尾に追加され、それが成功したならば、新しいレコードのアドレスをハッシュ表に登録する。その上でSynchronizeメソッドを呼ぶと、新しいレコードのサイズを含めたファイルサイズが記録され、状態が確定する。Synchronizeを呼ぶ前にシステムが死んだなら、前回記録したファイルサイズ以後のレコードを無視することで、状態のロールバックが成立する。データベースを開く際にRESTORE_SYNCオプションをつけたなら、前回の異常終了を検知したら、このロールバック処理が自動的に発動する。レコードの状態に何らかの一貫性の制約があるデータベースの場合、この運用方法が望ましい。ただし、Synchronizeを頻繁に呼ぶ必要があるので、スループットは下がる。
一方、デフォルト（RESTORE_DEFAULT）設定でデータベースを開いたなら、前回の異常終了を検知したら、最後にSynchronizeを呼んだ後に追加されたレコードも、できる限り復活させる。ミッションクリティカルでないデータを最大のスループットで処理したい場合にはこれが便利である。SNSにおける足跡とか最終ログイン時刻とかいった、異常に更新頻度が高いデータを管理する場合が典型的である。そういったデータは、事故の際に一部が消えてもそれほど迷惑をかけないが、とはいえオンメモリでキャッシュ的に扱って気軽に消えていいものでもない。なので、Synchronizeを呼ばないで運用してスループットを最大化しつつ、障害時にはベストエフォートでデータを復旧したい。
できるだけ多くのレコードを復旧させると言っても、更新途中の中途半端なレコードを復旧させたくはない。値のサイズが100バイトのレコードを記録しようとしたとして、50バイトまで書き込んだ時に死んだとしたら、それを50バイトの値を持つレコードとして復旧させてはならない。レコード単位の更新のAtomicityとConsistencyはデフォルトでも保証したい。実際には保証はできないのだが、できるだけ頑張りたい。
さて、書き込み途中であることをどうやって検出するかが問題となる。Synchronizeを呼ばないということは、ファイル全体のメタデータは更新されないということなので、ファイルのどの位置までが信頼できるかという情報は利用できない。
ところで、サイズを持ったバイト列をレコードとして扱う場合、大きく分けて二つの方法がある。メタデータ方式と番兵方式である。メタデータ方式は、サイズを専用の領域に記録しておく方法だ。典型的には先頭に記録するので、尖兵方式と言っても良い。一方、番兵方式では、データの末尾に、データの内部に含まれないパターンを置き、それが出現するまでをレコードとして扱う。メタデータ方式の良いところは、実データを読まなくてもサイズがわかるので、読み出しバッファの確保が楽なところだ。悪いところは、固定長でメタデータを表現すると最大値に合わせてメタデータのサイズを決めなければならず、可変長にすると実データの開始位置も変わるので実装が複雑になるところだ。番兵方式の良いところは、ヌル文字などの簡潔な異常値が定義できるなら空間効率が高いことだが、任意のバイナリには適用できない。また、読み出しバッファのサイズを予め決められないところも面倒くさい。Tkrzwは任意のバイナリを格納するデータベースなので、番兵方式は使えず、メタデータ方式を使っている。また、メタデータが固定長だと空間効率が良くないので、可変長にしている。なので、レコードの読み書きに関するコードがかなり複雑になっているのだが、まあ仕方ない。
さて、書き込みが完了したかどうか判定するという話題になると、番兵方式を使いたくなる誘惑に駆られる。番兵まで読み込めたならレコード全体が読めたということになるからだ。しかし、任意のバイナリには番兵と同じパターンが出てくる可能性があるため、番兵を使うならエスケープ処理が必要となる。それは空間効率の悪化を意味する。
更新は常にファイル末尾で行うとなると、ファイルの末尾が番兵として働くじゃないかと考える人もいるかもしれない。しかし、更新は並列に行われるので、必ずしも書き込み完了時にそのレコードが末尾である保証はないのだ。例えば、現在のファイルサイズが1000バイトだとして、100バイトのレコードAと50バイトのレコードBを同時に書き込む時に、両者のスレッドは新規データのアドレスをアトミックに取得する。結果として、レコードAは1000バイトから始まり、レコードBは1100バイトから始まると決定される。そして、それぞれのスレッドは自身が予約した領域に並列に書き込みを始める。並列なので、レコードBの書き込みの方がレコードAよりも早く終わるかもしれないし、その状態でレコードAの書き込みが途中なのにプロセスが死ぬかもしれない。そうすると、レコードAは、ファイルの途中なのに、書き込みが中途半端な状態になり得る。その場合、後半がヌルコードで埋められた状態になる。
ならば、メタデータを使ってさらに番兵も併用すればどうか。書き込み途中で死んだら後半がヌルコードになるということは、ヌルコード以外の番兵を定義して、メタデータで管理する領域の1つ先のバイトに番兵があるならば、書き込みが成功しているとみなせばよい。レコードあたりのフットプリントが1バイト増えるだけで、書き込み未完了が検出できるのだ。しかし、本来ならメタデータだけでサイズを管理できるはずなのに、正常系では全く役立たずな番兵を足すのは理想的ではない。たった1バイトと言っても、100万レコードあたり1MB食うわけで、チリツモだ。
世田谷公園を走りながら解決法を思いついた。Synchronizeしない運用でも、ハッシュ表のバケットは更新される。バケットが更新されるのは、レコード本体の書き込みが終わった時だけだ。ということは、ハッシュ表が該当のレコードを指している場合には、そのレコードの書き込みは完了していると言える。実際には、同じバケットに該当する複数のレコードが存在する可能性があるため、バケットから連結リストを辿ってそのレコードに到達できるならば、そのレコードのデータは信用できるとみなす。
ただし、厳密に言えば、この方法も完璧ではない。アプリケーション層で書き込んだ順序がデバイスと同期する順序と同じである保証はないからだ。レコードのデータを書き込んでからバケットを更新したとしても、レコードがあるブロックがデバイスに書き込まれるよりも先にバケットがあるブロックがデバイスに書き込まれるかもしれない。Synchronizeの中でfsyncかmsyncシステムコールを呼ばない限り、何も保証はないのだ。たとえ番兵を使ったとしても、この書き込み順序の問題が尾を引く。番兵があるブロックが途中のブロックよりも先に書き込まれるかもしれないからだ。つまり、デバイスの同期の問題を言い出すと、Synchronizeを呼ばなければ何も保証出来ないということになる。
別領域のデータを完了フラグとみなすのも駄目、番兵も駄目。となると、CRCなどのフィンガープリントを持たせるという手が残る。レコードのヘッダ部分に書いたフィンガープリントと実データから算出したフィンガープリントが同じである場合には信用することにすれば、高い確率で書き込み失敗を検出できる。しかし、フィンガープリントと言っても数え切れないくらいの手法がある。CRCでも32/16/8のそれぞれに亜種がたくさんあり、Adler32やMD5などの選択肢もある。それぞれに検出率や空間効率や動作速度の特徴があり、どれが最適かはユーザに選ばせたい。もっと言えば、フィンガープリントによる破壊検出はアプリケーション層で実装してもらえばよい。例えば、格納するレコードの値の先頭2バイトに、キーと値にCRC-16をかけたフィンガープリントを置けばよい。そのようなアプリケーションを支援すべく、ユーティリティとして以下の関数を提供することにした。
- HashCRC32 : RFC 1952互換のCRC32
- HashCRC16 : CCITTのCRC-16
- HashCRC8 : CRC-8。特に規格化されていないっぽいが、最も標準的と思われる式を利用
結論としては、データベース層では、バケットから到達可能なレコードを信用するという方針にする。Synchronizeしないで運用した場合、OSが突然死した際のConsistencyはデータベース層では保証できないが、必要であればアプリケーション層でCRC等による検査をしてもらうことにする。Synchronizeを前提としない運用のデータベースは「壊れにくい」だけであって「壊れない」わけではない。「壊れ得る」といっても、データベース全体が失われるわけではなく、ごく一部のレコードの一貫性がなくなるかもしれないというだけだ。ベストエフォートということなので、そのあたりが落とし所だろう。実際には更新中に電源を引っこ抜いてもレコード単位の不整合はそうそう起こらない。テストケースが書けなくて困っているくらいなのだから。
