データベースにレコード単位のCRCを内蔵することで、データが破損した際の検出率を高められるようにした。ハッシュ関数の性能測定とそれを組み込んだ際のデータベースの性能測定もして、実用になることを確かめた。
これにより、Synchronizeを呼ばない運用でも、レコード単位の一貫性を向上させることができる。アプリケーションの責任でCRCをレコードのデータに付随させれば良いとも考えたが、面倒なことはやらない人が多いだろう。なので、やはりデータベース側で面倒を見ることにした。PostgreSQLやMySQLなどでもCRCは内蔵しているので、データベース側で一貫性の向上策を持つのは一般的とも言える。「はじめてのDBM」スライドにCRCを使った運用についても書いておいたので、ご覧いただきたい。
前回までの議論で、障害復旧時の方法が二つあることを示した。最後にSynchronize（またはClose）メソッドを呼んだ時点の状態にロールバックして復旧させるRESTORE_SYNCモードと、ロールバックせずにできるだけ最新の更新まで復旧しようとするRESTORE_DEFAULTモードだ。RESTORE_SYNCモードの場合、Synchronizeとその中で呼ばれるmsync/fsyncシステムコールで整合性が保証されたデータしか復旧しないので、一貫性が失われることはない。
一方で、RESTORE_DEFAULTモードの場合、msync/fsyncでデバイスと同期せずにシステムが死んだ領域を読み込むので、一貫性の保証ができないのだ。msync/fsyncを呼ばないのが前提なら、書き込みの順序が保証されないので、レコード毎のメタデータや番兵では書き込み完了が保証できない。たとえwrite-aheadログを書いたとしても、msync/fsyncを呼ばなければ、write-ahead（レコード本体よりも先にログを書く）という性質が保証されないのだから、意味がない。なので、RESTORE_DEFAULTを使うなら「保証」という概念は諦めて、「ベストエフォート」を考えるべきだ。
なるべく多くのレコードを復旧させたいが、壊れたレコードは復旧させたくない。つまりこれは判定問題である。破損の検出という観点で見た場合、以下の判定機構が働く。
- レコードの先頭のマジックデータが存在するかどうか
- これがあるということは、レコードを書き始めた時点ではシステムが生きていたということ
- レコードの末尾にパディングがある場合、その先頭のマジックデータが存在するかどうか
- これがあるということは、レコードを書き終えた時点ではシステムが生きていたということ
- ハッシュ表の該当バケットからそのレコードに到達できるかどうか
- これが可能ということは、バケットを更新した時点ではシステムが生きていたということ
しかし、既に何度も述べたが、上記で得られる順序の保証はアプリケーション層のものであり、プロセスのクラッシュ時には信用できるが、OSのクラッシュ時には信用できない。OSがデバイスに書き込む順序は、逐次msync/fsyncを呼ばない限り、保証されないからだ。
よって、これにさらにCRCによる判定機構を加えられるようにする。CRC（Cyclic Redundancy Check＝巡回冗長性検査）とは、任意のバイト列を対象にして数値を算出するハッシュ関数の一種であり、対象のバイト列の変更を検出するために用いられる。CRCには亜種が数え切れないほどあるが、主に値のビット数で検出率と空間効率のトレードオフを調整することになる。よって、チューニングパラメータにrecord_crcというのを加えて、ユーザに選択してもらう。デフォルトはRECORD_CRC_NONEで、今までと同様にCRCをつけない挙動になる。RECORD_CRC_8だとCRC-8、RECORD_CRC_16だとCRC-16、RECORD_CRC_32だとCRC-32をレコードのメタデータとしてつけるようになる。
追記更新モードの場合、レコードの破損を検出しても、そのレコードが消えるわけではなく、更新がなかったことになるというのがポイントだ。つまりレコードの更新前の値が依然として有効になるということだ。よって、更新の不整合が十分な確率で検出できるなら、追記更新モードを使えば、RESTORE_DEFAULTモードの運用でも、「かなり」信用できるデータベースになる。マーフィーの法則（失敗する余地があるなら、失敗する）を鑑みても、前提となる母数が小さいことを考えれば、おそらくハードウェアの故障率より低いレベルになるので問題ないだろう。インプレイス更新モードの場合、不整合を検出したレコードは、削除される。
CRC-8は1バイトなので、衝突率は1/256だ。破損判定機構として考えた場合、偽陽性はないので精度は100%だが、偽陰性が1/256の確率で起こるので、再現率は99.6%ということになる。CRC-16は2バイトで、衝突率は1/65536なので、再現率99.9984%になる。CRC-32は4バイトで、衝突率は1/4294967296なので、再現率は99.999999976%になる。一貫性判定機構として考えるなら、衝突率が偽陽性発生率になるので、上述の再現率を精度に読み替えればよい。
この判定が必要な頻度は高くない。システムがクラッシュして、かつその時点で更新していたレコードのデータが複数のブロックにまたがって配置されていて、かつそのデバイスへの書き込み順序がアプリケーションからの書き込み順序と一致せず、かつ先頭と末尾は書き終えていて中間部分を書き終える前に停止した場合にのみ、破損の可能性がある。実際問題として、あまり起こらない条件であり、意図的に起こすのもなかなか難しい。よって、カジュアルな運用ではそもそもCRCは必要ない。
それを踏まえた上で、何バイトで安心を追加しますかという話になる。一貫性の喪失が何よりも恐ろしいというユースケースであれば、CRC-32を使うだろうが、それでも完璧にはならないのがもどかしい。というか一貫性を重視するユースケースではそもそもRESTORE_SYNCモードを使うだろう。それにさらにCRCを加えることもできるが、実用的な意味はない。あくまで4バイトで安心を買うという位置づけだ。
RESTORE_DEFAULTモードで運用する場合は、一貫性の要求がより緩やかで、それより処理効率への要求に応えるのに苦労していることだろう。SLA（サービスレベルアグリーメント）でデータの保護や一貫性の保証を謳わないが、ベストエフォートでデータを保護してユーザ満足度に貢献したいという感じか。もしデータが失われても、ゴメンで済む案件ということだ。データが失われたらゴメンで済むが、変なデータを復旧したらもっとややこしくなるので、それをなるべく回避したいと。そんな場合は、CRC-8やCRC-16を付けるのが現実的だろう。1バイトや2バイトの追加で買える99.6%ないし99.998%の安心。
なお、ツリーデータベースはハッシュデータベースの上でページ管理を行うので、ツリーデータベースにCRCを付加した場合、6000バイトくらいのページ単位でCRCが付加される。よって、レコードあたりのフットプリントが小さくなるので、CRCを付加するなら、CRC-32が良いだろう。とはいえ、破損を検出したらそのページに関わる全ての更新が無視されるので、それで嬉しいかどうかは場合によるだろう。ツリーデータベースのレコード単位でCRCをつける機能は今のところ実装していないし、おそらく将来的にもしないだろう。
ファイルフォーマットの互換性は、CRCの追加によっても保たれる。データベースファイルのヘッダにCRC用のフラグが立てられ、それによってCRCの有無とサイズが判定される。過去のバージョンで作ったデータベースはCRCなしで運用されるだけだ。既存のデータベースにCRCを追加したり、既存のCRCを削除したり、サイズを変えたりしたい場合には、C++でRebuildメソッドを呼ぶか、tkrzw_util rebuildコマンドを実行すればよい。
CRCは、キーと値を連結したデータに対して算出される。例えば、キーが "japan" で値が "tokyo" であれば、"japantokyo" のCRCを算出する。CRCを生成する関数はバイト単位でデータを入力しながら更新できるようになっているので、実際にデータを連結することなく、連結した場合のCRCを算出することができる。キーが "japa" で値が "ntokyo" のレコードも同じCRCを持つことになるが、レコード間の比較をするわけじゃないので問題ない。OSの突然死によるヌルコードへの置き換えを検出するのが主目的なのだ。
CRCの算出は、Setメソッドなどでレコードが更新される度に行われる。よって、空間効率だけでなく時間効率にも影響する。とはいえ、CRCの生成関数はテーブルルックアップで最適化されているので、そこそこ速いはずだ。ただし、書き込むデータが増大することによる時間効率への影響はあるだろう。一方、参照の際にCRCの検証をすることはない。CRCは障害復旧の際にのみ用いられる。しかし、Getメソッドのスループットも、読み出しデータが増加する分だけ低下するはずだ。
CRC算出関数の速度を測ってみよう。ハッシュ表の検索に使っているMurmur Hash 3と、シャーディングに使っているFNV-64も比較する。ランダムに生成した100バイトのレコードを対象とした値の生成を1億回行うのにかかる時間を測る。
| time | throughput | |
| CRC-8 | 13.23 | 7,558,578 |
| CRC-16 | 21.03 | 4,755,111 |
| CRC-32 | 19.08 | 5,254,860 |
| Murmur 3 | 1.29 | 77,519,379 |
| FNV-64 | 8.38 | 11,933,174 |
8バイトずつ処理するMurmur Hash 3が最速で、1バイト毎に掛け算1回とXORで済むFNV-64が次点 で、1バイト毎にテーブルルックアップとXORが必要なCRC系の実装は遅い。実際のコードを見れば納得できるはずだ。とはいえ、データベース全体の処理から考えると、CRC関数の遅さはボトルネックになるほどではないことが確かめられた。
CRCよりもMurmurの方が高速なので、Murmurの値の一部を一貫性の検査に使うという手も考えられる。しかし、CRCは限られたビット数で誤り検出符号としての性能を最大化するように設計されているので、速度だけで優劣を決めるべきではない。CRCはエラー検出率の点では他のハッシュ関数を32ビットや16ビットや8ビットに折り返したものよりも優れているらしい。とはいえ、やはりCRCは遅いので、zlibではより高速なAdler32を使っていたりする。CRCも4バイト毎とかで計算すればもっと早くなるらしいが。いずれにせよ、この話題をこれ以上追求する知識も意欲も私にはないので、とりあえず現状のCRC実装で良いことにする。
実際にデータベースで利用する際には、ハッシュ関数のオーバーヘッドに加えて読み書きが増える分のオーバーヘッドが加わる。1000万レコードのSetとGetで影響を確かめてみる。キーと値はそれぞれ8バイトだ。
| Set throughput | Get throughput | File size | |
| none | 1,338,104 | 1,619,424 | 320,003,072 |
| CRC-8 | 1,233,552 | 1,590,882 | 330,003,072 |
| CRC-16 | 1,246,759 | 1,606,532 | 340,003,072 |
| CRC-32 | 1,252,381 | 1,616,344 | 360,003,072 |
ということで、CRCをデータベースに追加することでの性能への影響は軽微または許容範囲であることが確かめられた。これで安心が買えるなら、CRCを使いたくなるという人も一定数いることだろう。
繰り返しになるが、通常運用時には、CRCは更新時に設定されるだけで、参照時には全く検査されない。データベースファイルに不整合を検出した時にのみ、レコードの精査に使われる。すなわち、アンヘルシーなデータベースファイル（前回開いた時に閉じずにプロセスが死んだ）を開こうとした場合に自動的に行われる復旧処理にて、CRCが一致しない更新を無効化してくれる。実際にそうなることはテストコード tkrzw_dbm_hash_test.ccを見て確認いただきたい。
まとめ。Tkrzwのデータベースにおいて、各レコードにCRCを付加する機能を実装した。障害復旧時にCRCを調べ、不整合のある更新をロールバックしてくれる。Synchronizeしない運用でも、レコード単位の一貫性は実用的に問題ないレベルで高められる。それでいて、空間効率と時間効率への影響は軽微だ。
CRCは障害発生時にしか役に立たない機能であり、障害発生時にすらCRCがなくても大丈夫なことが多いように設計しているので、あまり積極的に利用したくなるものでもない。ただ、オンライン系で運用する際には安全性は最重要課題なので、念の為CRCをつけて運用するというのは心の健康のためにも良いことだろう。
