豪鬼メモ

一瞬千撃

ハッシュデータベースの互換的フォーマット変更

HashDBMの信頼性向上と性能向上を図るためにデータベースフォーマットを変更したのだが、後方互換性を持たせつつフォーマットを変更するのには苦労した。それをどうやって進めたかという話。ユーザにとっては、すげー地味でどうでもいい話ではあるが、開発者視点では、1ビットも無駄のない戦いが行われていた。
f:id:fridaynight:20210626015222p:plain


今回の変更でやりたいことは2つだ。

まず、マジックナンバーだが、前回の記事に書いた実験で確認した通り、6ビットのチェックサムを埋め込むと、検出率98.3%のエラー検出機能が付加される。1/61の確率で偽陰性が発生するが、無いよりはマシだ。CRCを別途付加した場合の偽陰性発生率をさらに1/61にする効果もあるため、安心を強化するという意味で有効だ。

従来、レコード毎のヘッダの最初のバイトは、0xFF、0xFE、0xFDのどれかで、フリーブロックか、値のあるレコードか、削除されたレコードかを区別するものであった。それ以外の値が来れば、ファイルが壊れているとみなされる。

新フォーマットでは、上位2ビットを使って3つの状態を表現して、下位6ビットを使ってチェックサムを表現したい。しかし、旧フォーマットでは、上位4ビットは常に0xFで、その次の2ビットが0x1か0x2か0x3で、最後の2ビットは常に0x3であるため、互換性がない。実際に利用しているビットが中間にあるので、上位ビットのみや下位ビットのみを別の用途に使うことはできない。かといって、6ビットを4ビットと2ビットに分けて扱うというのは気持ち悪すぎる。

よって、既存のマジックナンバーと区別がつくように新しいマジックナンバーを設計する。マジックナンバーが0xFFか0xFEか0xFDであれば旧フォーマットとみなし、それ以外であれば新フォーマットとみなせばよい。新フォーマットでは、上位2ビットを状態切り替えに使い、0x3<<6、0x2<<6、0x1<<6の3つを定義する。0x0<<6はエラーとみなす。残りの6ビットには、前回議論したChecksum6を用いる。これは61をモジュロとした関数なので、変域は0から60である。16進数で言えば0x0から0x3Cである。つまり、上位2ビットと下位6ビットを合成しても、旧フォーマットの0xFF、0xFE、0xFDとはギリギリ被らない。最大値である(0x3<<6)|0x3Cは0xFCであることで確認できる。モジュロに61を選んだのは64未満の最大の素数だからに過ぎないが、0x3<<6と合成した際の最大値が0xFD未満であったのは幸運だ。

次に、パディングのフォーマットを変更する話に移る。パディングとは、レコードのサイズが一定になるようにレコードの末尾に埋められるデータだ。パディングがあるおかげで、任意の長さ以下の領域にレコードを記録することができる。レコードのアラインメントもパディングがあってこそだ。

従来、パディングのサイズは、レコードのヘッダに含まれる1バイトのメタデータで管理していた。1バイトでは最大255バイトまでしか表現できない。そこで、238(0xEE)バイト未満の場合はその1バイトのみでパディングのサイズを表現するが、それ以上の場合にはメタデータに0xEEと書いておいて、パディングの先頭4バイトにパディングのサイズを書き込んでいた。

レコードのキーや値の長さは、Protocol Buffersなどと同じく128進数の可変長バイナリ(base 128 varintとかbyte delta encodingなどとも呼ぶ)で記録しているのに、なぜパディングの長さだけ変わった方法で管理していたのか。パディングのサイズは、書き込むべき領域の長さからヘッダとキーと値の長さを引いて求めねばならない。もしヘッダに含まれるパディングの長さのメタデータがパディングの長さによって決まるとすれば、依存関係がループしてしまう。よって、ヘッダに含まれるメタデータは必ず1バイトということにして、それで不十分な場合にはパディング自身に長さを持たせるという妥協案を採用した。

この方法で動作に問題はないのだが、性能上の問題があった。レコード全体の長さを知るためにはキーと値とパディングの長さを合算する必要があるが、パディングの長さがパディング自身に書かれていると、レコードの先頭だけではなく、末尾も読まねばならない。さて、Setメソッドでレコードを上書きする場合、レコードの長さだけわかれば既存のデータを読み込む必要はない。それにもかかわらず、パディングのせいで、全体を読まねばならないことがあるのだ。レコードが大きいほどに読み込みの負荷は大きくなるが、大きいレコードほどパディングも大きくなる傾向にあるので、高い確率で無駄な負荷が発生することになる。

そこで、パディングの長さも128進数可変長バイナリでヘッダの中に表現することにした。そうすれば、ヘッダだけ読めば全体の長さがわかるので、更新時の読み込み負荷が減らせる。ただし、ヘッダの長さがパディングの長さによって変わってしまうのは厄介だ。固定長で表現する案もあったが、多くの場合1バイトか2バイトで済むメタデータを4バイトで保持するのは最適ではない。考えた結果、パディングのサイズは、パディングのサイズのメタデータが1バイトであると仮定して算出し、それを元にメタデータを記録することにした。実際のパディングのサイズは、長さが128バイト未満であればそのままの値を使い、128バイト以上16384バイト未満であれば1バイト減らし、16384バイト以上2097152バイト未満であれば2バイト減らし、それ以上であれば3バイト減らす。

パディングのフォーマットの変更も後方互換ではない。しかも、128進数可変長バイナリは0xEEをパターンに含むので、区別することもできない。そこで、マジックナンバーの変更と同じタイミングで行うことにした。マジックナンバーが旧フォーマットである場合、パディングも旧フォーマットで扱う。マジックナンバーが新フォーマットである場合、パディングも新フォーマットで扱う。これでどちらのフォーマットでも問題なく動作するようになる。

旧フォーマットのデータベースを読み込んで更新したレコードを書き込んだ場合、そのレコードは新フォーマットで書かれる。よって、更新のある運用を続けると、いずれ新フォーマットの割合が上がってくるはずだ。既存のデータベースのレコードを全て新フォーマットに変えたい場合、Rebuildメソッドやtkrzw_dbm_util rebuildコマンドで再構築処理をかけるのが簡単だ。繰り返しになるが、新フォーマットの利点は、障害などによるデータ損失の検出率が上がることと、Setメソッドなどの更新操作の性能が向上することである。とはいえ実運用上の利点はそれほど大きくないので、必ず再構築を推奨するというほどでもない。

パディングの書式変更によって特に恩恵を受けるのは、TreeDBMのランダムアクセスによる更新である。B+木の更新は平均6000バイトくらいのページ単位で行われるが、旧フォーマットでは古いページのデータ全体を読み込んでから新しいページのデータを書き込んでいた。それが、新フォーマットでは古いページのヘッダのみを読み込めば、新しいページの書き込みができるようになった。

性能測定を行う。ページキャッシュを1000ページに制限し、かつ敢えて遅いファイル実装PostionalAtomicFileクラスを使って、400万レコードのランダム更新を4スレッドで行う。

$ tkrzw_dbm_perf sequence --random_key --path casket.tkt --iter 1000000 --set_only --max_cached_pages 1000 --threads 4 --file pos-atom

従来のバージョン(0.9.32)では、106629 QPSであった。新バージョン(0.9.33)では、117080 QPSであった。少し早くなっている。チェックサムの処理を入れた分、HashDBMではスループットが1%くらい下がるのだが、TreeDBMのランダムアクセスは9%くらい高速化するという結果になった。チェックサムの計算はCPUパワーは使うが、ストレージの速度とは関係ない。一方で、パディングの最適化はストレージへのアクセスを減らすので、ストレージが遅いほどに、今回の変更は有利に働くだろう。


まとめ。HashDBMのレコードにチェックサムを入れて信頼性を向上させるとともに、パディングのフォーマットもいじって更新性能を向上させた。データの後方互換性を保つために、内部的にはビットをコネコネ、バイトをコネコネして工夫している。