データベースにエラー検出符号を組み込んだはいいが、実際にどの程度の確率でエラーを検出できるだろうか。単純なチェックサムとAdlerチェックサムとCRCを比較してみた。実際にランダムに文字列を書き換えて、それがきちんと検出できるかどうかの統計を取った。以下は、各種エラー検出符号の、エラーの長さ（バイト数）とエラー検出率のグラフである。
ファイルにデータを記録したとして、ストレージのエラーやシステムの暴走などが理由で、記録したはずのデータと異なるものが読み出される可能性がある。ネットワークでデータを転送した場合も、途中の経路のエラーにより、送信したはずのデータと異なるものが受信される可能性がある。そういったデータの破損または改変を検知するために、データのハッシュ値を添付しておいて、それと比較することで確率的に一貫性を調べる手法が多数ある。エラー検出符号とか誤り検出符号とか呼ばれるものだ。データベースに記録するレコードにもエラー検出符号をつけておくことで、入出力のエラーを検出して、トランザクションの信頼性を高めることができる。
今回は、以下のエラー検出符号を実装して、それぞれのエラー検出率を比較した。短い符号のものはいくつか組み合わせるとどうなるかも調べた。
- Checksum-6 : 各バイトの32ビットのチェックサムを61で割った値。
- Checksum-8 : 各バイトの32ビットのチェックサムを251で割った値。
- Adler-6 : Adler-32の上位ビットと下位ビットを3ビットにし、モジュロ7で計算したもの。
- Adler-8 : Adler-32の上位ビットと下位ビットを4ビットにし、モジュロ13で計算したもの。
- Adler-16 : Adler-32の上位ビットと下位ビットを8ビットにし、モジュロ251で計算したもの。
- Adler-32 : 元来のAdler-32。16ビットのモジュロ65521で計算する。
- CRC-4 : 4ビットのCRC。ITU準拠。多項式は0x0C。
- CRC-8 : 8ビットのCRC。多項式は0x07。
- CRC-16 : 16ビットのCRC。XMODEM準拠。多項式は0x1021。
- CRC-32 : 32ビットのCRC。IEEE 802.3準拠。多項式は0xEDB88320。
チェックサムとは、単に各バイトの値を足して最後に適当な数で割る方式である。クレジットカードやマイナンバーのチェックディジットと同じ仕組みだ。最後の除算を素数でやると検出性能が上がるらしい。今回は6ビットと8ビットのものを実装した。
Adler-32は、deflateにつけられる、チェックサムのちょっと賢い実装だ。下位16ビットでモジュロ65521のチェックサムを計算しつつ、各ステップのチェックサムのチェックサムを上位16ビットで算出して検出率を高める。これは一般化できる。全体をNビットとすると、下位N/2ビットで、2^(N/2)未満の最大の素数をモジュロにしたチェックサムを算出し、各ステップのチェックサムのチェックサムを上位N/2ビットで算出すればよい。今回は6、8、16、32ビットのものを実装した。
CRCは、入力のビット列を1ビットずつずらしながら多項式とのXORを算出していく方法だ。実際には各バイトの値毎の256種類の結果を事前計算してテーブルを作っておいて、そのテーブルを引きながら処理を進める。CRCは結果のビットの幅以下の連続した誤りを確実に検知できるという重要な利点がある。しかし、チェックサム方式に比べて遅いのが玉に瑕だ。
実験の入力データは、1000バイトのバイナリデータとした。内容はランダムで、毎回の試行で異なるものが生成される。この入力シーケンスに対して、ランダムな位置から、一定の長さでデータの改変を引き起こす。長さは1バイト、4バイト、16バイト、256バイトで個別に実験する。エラーパターンには以下のものを設定する。
- Zero : バイトの値を0にする。元々0のバイトは1にする。
- Random : バイトの値をランダムに書き換える。
この実験の目的は、データベースのレコードに付随させるエラー検出コードにふさわしい設定を調べることにある。したがって、ファイル入出力で起きがちなエラーを高い確率で検出できそうなものを試したい。ファイル入出力で最も起きやすいエラーは、ビット単位や数バイト単位のノイズが混じるエラーではない。書き込み途中でプロセスやOSが死に、レコード内の広い範囲がヌルコードや古いデータのままになるエラーである。ファイルの末尾にデータを記録している途中に死んでヌルコードが残るのが「Zero」パターンであり、ファイルの既存領域にデータを記録している途中に死んで既存のゴミデータが残るのが「Random」パターンである。
結果は以下のようになった。試行は各設定で300万回ずつ行った。
| Zero-1 | Zero-4 | Zero-16 | Zero-256 | Rand-1 | Rand-4 | Rand-16 | Rand-256 | |
| Checksum-6 | 0.984329 | 0.983603 | 0.98358 | 0.983565 | 0.987349 | 0.983664 | 0.983759 | 0.983606 |
| Checksum-8 | 0.996111 | 0.99603 | 0.996 | 0.996034 | 0.999835 | 0.995999 | 0.995989 | 0.996014 |
| Adler-6 | 0.859419 | 0.979549 | 0.979531 | 0.979685 | 0.86135 | 0.98069 | 0.979823 | 0.979785 |
| Adler-8 | 0.926138 | 0.994103 | 0.994108 | 0.994071 | 0.926739 | 0.994707 | 0.994083 | 0.994125 |
| Adler-16 | 0.996106 | 0.999984 | 0.999984 | 0.999993 | 0.999845 | 1 | 0.999982 | 0.999984 |
| Adler-32 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| CRC-4 | 0.941851 | 0.937494 | 0.937364 | 0.937485 | 0.941449 | 0.937275 | 0.9373 | 0.937444 |
| CRC-8 | 1 | 0.996117 | 0.996107 | 0.996112 | 0.999997 | 0.996057 | 0.996084 | 0.996136 |
| CRC-16 | 1 | 0.999986 | 0.999987 | 0.999983 | 1 | 1 | 0.999991 | 0.999984 |
| CRC-32 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Checksum-6+CRC-8 | 1 | 0.999923 | 0.999931 | 0.999941 | 1 | 0.999945 | 0.999936 | 0.999928 |
| Checksum-6+CRC-16 | 1 | 0.999999 | 0.999931 | 1 | 1 | 1 | 1 | 0.999999 |
| Checksum-8+CRC-8 | 1 | 0.999982 | 0.99999 | 0.999987 | 1 | 0.999978 | 0.999981 | 0.999983 |
| Checksum-8+CRC-16 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Adler-6+CRC-8 | 1 | 0.999927 | 0.999919 | 0.999925 | 1 | 0.999934 | 0.999918 | 0.999913 |
| Adler-6+CRC-16 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Adler-8+CRC-8 | 1 | 0.999977 | 0.999976 | 0.999976 | 1 | 0.999976 | 0.999973 | 0.999973 |
| Adler-8+CRC-16 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| CRC-4+CRC-8 | 1 | 0.999751 | 0.99975 | 0.999748 | 1 | 0.999976 | 0.999743 | 0.999765 |
| CRC-4+CRC-16 | 1 | 0.999999 | 0.999999 | 0.999999 | 1 | 1 | 0.999998 | 0.999999 |
| CRC-8+CRC-16 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
まずCRCの結果に着目しよう。理論通り、エラーの長さがCRCのビット長以下である場合には、検出率は100%になる。長さがそれを超えると、これも理論通り、ハッシュの変域に反比例するように偽陰性が発生するようだ。とはいえ300万件程度の試行では、CRC-32で偽陰性が発生することはなかった。よって、この中では、CRC-32は最善だと言える。とはいえ、CRC-32もAdler-32も偽陰性がゼロなので、より高速に動作するAdler-32でも実用上は十分だ。ビット長以下のエラーを重視しないデータベースでの利用であれば、CRC系もAdler系も大差ないとも言える。
32ビットあれば、ほとんど偽陰性は発生しない。では、16ビットではどうか。エラーの長さが4バイト以上の結果を見ると、CRC-16もAdler-16も99.999%付近だ。双方の差は誤差の範囲だろう。8ビットになると、CRC-8が99.6%、Adler-8が99.4%で、有意な差が出ている。CRC系の方がAdler系よりもほんの少し信頼性が高いような気はする。とはいえ、ほんのちょっとだ。Checksum-8は99.5%の検出率だ。8ビットまでビット数を落としてしまうと、どの方式も目くそ鼻くそ状態である。Adler系で1バイトのエラー検出率が低いのは、モジュロが256未満だからだ。4ビットずつとかで処理すればこの問題は緩和できるが、遅くなるので存在意義が怪しくなってしまう。そもそも、偽陰性が0.5%も出るシステムは、信頼するというレベルではない。障害時に一貫性損失が起きることを覚悟した運用の中で、損失の程度を抑制するという位置づけになる。だったら、単純な方式で十分であり、Adler-8でもChecksum-8でも実用上の精度の恩恵は変わらない。
ところで、6ビットのような中途半端な実装が実験対象に含まれているのには理由がある。実はこの実験の本命はこちらなのだ。TkrzwのHashDBMの各レコードにおいて、先頭の1バイトはマジックデータとして使われている。これはVOID、SET、REMOVEという3つの状態を切り替えるフラグとして機能している。3つの状態は2ビットあれば表現できるので、残り6ビットは使われていない。これをエラー検出に活用できないかと思った次第である。なので、6ビットの実装に着目すると、Checksum-6は安定して98.3%とかの検出率を示している。Adler-6は1バイトのエラーの検出率が86%くらいと低いが、それ以上の長さになると98%くらいになる。CRC-4も一応実装してみたが、94%くらいの検出率になるようだ。
98%とかの検出率って意味あんのかと思う人も多いだろう。しかし、単純なチェックサムはCRCよりも圧倒的に速いので、時間コスト的にはほぼタダだ。しかも、データを余った場所に埋め込めるなら、空間コストもタダだ。タダで信頼性が少しでも上がるなら、やって損はないだろう。しかし、信頼性を真面目に考えるなら、ちゃんとCRCをつけて運用するだろう。そこで興味が出てくるのが、チェックサムとCRCを合わせると検出率は少しでも上がるのかどうかだ。それが理由で、6ビットや8ビットの簡易実装群とCRCを組み合わせた実験を入れている。CRC-8単体だと検出率99.4%なのが、Checksum-6+CRC-8だと99.993%に上がっている。つまり、それなりに意味があるとは言えそうだ。今回の実験では完璧だったCRC-32も理論的には完璧ではないので、その潜在的なリスクも6ビットなりには減らしてくれるだろう。
時間コストの話が出たので、各実装のスループットも測っておこう。1000バイトのテキストを300万件処理する時間を改めて計測した。
| Murmur | 0.387791 |
| FNV | 2.979561 |
| Checksum-6 | 0.217775 |
| Checksum-8 | 0.240691 |
| Adler-6 | 1.231650 |
| Adler-8 | 1.224273 |
| Adler-16 | 1.218244 |
| Adler-32 | 1.219949 |
| CRC-4 | 1.90402 |
| CRC-8 | 1.908613 |
| CRC-16 | 6.759725 |
| CRC-32 | 1.921234 |
CRC系の実装には、CRC-16以外は最適化を入れてある。zlibに習って、テーブルを4つ作って、4バイトずつ処理するように変更したのだ。そうすると4倍まではいかずとも、3倍くらい早くなる。それでもやはりAdler系の方が高速で、それよりさらにChecksum系の方が高速である。足し算しかしていないので当然だ。
結局のところ、それなりの長さのエラーが発生した場合、偽陰性発生率はハッシュ値のビット数で決まる。アルゴリズムの詳細はあまり関係ない。入力データがランダムであると仮定するなら、それがヌルコードになる変化もランダムな差分を発生させる。ランダムなデータを挿入するのも当然ランダムな差分を発生させる。そうなると、ハッシュ値がどう変化するかもランダムになる。したがって、ハッシュの衝突率がハッシュ値の変域の逆数に収束するのは当然の帰結だ。
まとめ。障害時の信頼性を追求するなら、エラー検出符号にはCRC-32を使うのが妥当だ。CRC-64やそれ以上のビット数のエラー検出符号を使う実装も多い。とはいえ、敢えてDBMを使うようなユースケースでは、よりコスト意識が高いと考えられる。潜在コストは障害時の損失に障害発生率を掛けて計算され、それが運用コストを上回るかどうかで、最適な対処が判断される。障害発生率を十分に低くできるなら、限りなくゼロにする必要はない。その意味では、CRC-32は、ほとんどのユースケースで十分だ。もっと言えば、99.998%の検出率を持つCRC-16や、99.6%の検出率を持つCRC-8がベストバランスに近いケースもあるだろう。
6ビットの実装をいくつか比較してみたところ、Checksum-6がそこそこ有用だとわかった。単体で98%以上のエラー検出率を示し、別途CRCを付加した場合にもそれと相乗的に機能する。6ビットで済むなら現状の余った場所に埋められるので、空間コストはタダだ。Checksum-6は100バイトの文字列では1億QPSくらい出るので、ファイルI/Oの文脈では、時間コストもほぼタダだ。損がないなら、やるべきだ。よって、Tkrzwの将来のバージョンでは、Checksum-6を埋め込む方法で検討していきたい。
