前回はハッシュデータベースの大まかな構造を述べたが、今回はデータフォーマットの形式を完全に詰める。
ハッシュデータベースは以下の5つのセクションからなる。
メタデータセクションは、メタデータを記録する。データベース全体にまつわる情報である。データベースが開かれた際にファイルから読み込まれてメモリ上に展開され、データベースが閉じられる際に書き戻される。以下のフィールドを持つ。
- マジックデータ
- オフセット0から10バイト。"TkrzwHDB\n" とその後ろのヌルコードからなる。
- パッケージのメジャーバージョン
- オフセット10から1バイトの整数。
- パッケージのマイナーバージョン
- オフセット11から1バイトの整数
- 静的フラグ
- オフセット12から1バイトの整数
- オフセット幅
- オフセット13から 1バイトの整数
- アラインメントパワー
- オフセット14から 1バイトの整数
- クロージャフラグ
- オフセット15から1バイトの整数
- バケット数
- オフセット16から8バイトのビッグエンディアン整数
- レコード数
- オフセット24から8バイトのビッグエンディアン整数
- 実効データサイズ
- オフセット32から8バイトのビッグエンディアン整数
- ファイルサイズ
- オフセット40から8バイトのビッグエンディアン整数
- 最終更新タイムスタンプ
- オフセット48から8バイトのビッグエンディアン整数
- データベースタイプ
- オフセット56から4バイトのビッグエンディアン整数
- オペイクデータ
- オフセット64から64バイトの任意の文字列
マジックデータはハッシュデータベースファイルかどうかを認識するためのものだ。fileコマンドとかでも認識できるようにわかりやすい文字列であるべき。パッケージバージョンは特に使い道はないのだが、将来的に互換性などを考える時に使うかもしれない。
静的フラグはデータベースの寿命の中で変化しないフラグだ。0x1はインプレース更新モードを示し、0x2は追記更新モードを示す。
オフセット幅とアラインメントパワーはレコードのアドレス（＝先頭からのオフセット）をどうやって表現するかを設定する。アラインメントパワーは2の指数として指定する。
クロージャフラグは、データベースがきちんとクローズされたかどうかを管理する。データベースが開いた直後に0が書き込まれ、データベースを閉じる直前に1が書き込まれる。つまり、この値が0のファイルは、きちんと閉じられていないということを示唆している。最終更新時刻はデータベースが閉じる際に更新される。
バケット数はハッシュテーブル内のバケットの数を示す。レコード数は生きているレコードの数を示す。実効データサイズは全てのレコードのキーと値のサイズの合計を示す。この値とファイルサイズの比較をすることで再構築の必要性を判断する。
データベースタイプは、特に使い道がないのだが、任意の整数をユーザが保存できるようにしてある。同様にして、オペイクデータは任意の文字列をユーザが保存できるようにしてある。オペイクデータの方はハッシュテーブルデータベースの上に構築されるB+木データベースのメタデータを格納するのにも使われる。
バケットセクションは、オフセット128からバケット数にオフセット幅を掛けた長さのところまでを占める。デフォルトではバケット数は1,048,583でオフセット幅は4なので、128から4,194,460までを占める。各々のバケットはバケット幅のビッグエンディアン整数だが、実際の値はアラインメントパワーで右シフトしたものになる。値はそのバケットに属する連結リストの最初のレコードのオフセットを示すが、該当するレコードがない場合には0になる。
レコードセクションはバケットセクションの終端に1024を足した位置と同じかそれ以降で4096にアラインする最初の位置から始まり、ファイルの末尾までを占める。アラインメントパワーが12より大きい場合にはそれにもアラインさせる。各レコードは以下のフィールドを持つ。
- マジックデータ
- 1バイトの整数
- 子レコードのオフセット
- オフセット幅のビッグエンディアン整数
- キーのサイズ
- 可変長整数
- 値のサイズ
- 可変長整数
- パディングサイズ
- 1バイトの整数
- キーのデータ
- 任意の文字列
- 値のデータ
- 任意の文字列
- パディング
- 構造化データ
マジックデータはそのレコードの操作を示す。0xFFだと、そのレコードに値を持たせる操作を示す。0xFEは、そのレコードを削除する操作を示す。0xFDは、何もしないことを示す。
子レコードのオフセットは、連結リストの次の要素となるレコードのオフセットを示す。新しいレコードが追加される時、そのレコードは連結リストの先頭に来る。子レコードがない場合には0になる。
キーのサイズと値のサイズは可変長整数として保持される。MSBの1ビットは次のバイトを読むかを決め、残り7ビットでビッグエンディアンの整数値を表す。パディングのサイズは1バイト整数なので256までしか表現できない。なので、0xEE以上の場合は、パディングデータ内の先頭4バイトをビッグエンディアン整数とみなして、パディングのサイズを決める。0xFFでないのはマジックデータと被らないようにするためだ。サイズ用のメタデータを除いたパディングの最初のバイトは0xDDであり、それ以外の領域は0で埋める。
レコードセクションの直前の16バイトは、レコードヘッダセクションである。それは "TkrzwREC\n" のマジックデータで始まる。それに続き、1バイトのオフセット幅と1バイトのアラインメントパワーを記録する。これらは万が一メタデータが壊れた場合の保険である。
レコードヘッダセクションの直前1008バイトは、フリーブロックプールセクションである。データベースが閉じられる際に、フリーブロックプールをシリアライズして保存する。それぞれのフリーブロックはオフセット幅のビッグエンディアン整数でオフセットを表したデータ、4バイトのビッグエンディアン整数で表したデータのペアである。1008バイトに納まらない場合、小さいフリーブロックから捨てられる。
これでいけるだろう。多分。KCのフォーマットを参考にしつつ設計したので、まあ妥当なところに落ち着いていると思う。連結リストに特化しているあたりとか、マジックデータとパディングの扱いとかはKCと異なっている。
レコードのマジックデータのところで、「操作」と書いたのだが、これは意味がある。追記更新を念頭に置くと、全てのレコードは、空の集合に対する集合演算操作のログであるとみなせる。その文脈では、通常のレコードは、そのキーと値のレコードを加えるという操作とみなせる。削除マークがついたレコードは、そのキーのレコードを消すという操作であるとみなせる。無効マークがついたレコードは、何もしない操作とみなせる。LightroomがRAWデータに対する操作ログを紐づけることで非破壊編集を実現しているのと同じノリだ。
追記更新のデータベースでは、レコードを前から順に読んで「操作」を再現していくことで、その操作を登録した時点でのデータベースの状態を完全に復元できる。MacのTime Machineと同じノリだ。メタデータにファイルサイズを記録しているのはそれをうまく活用するためだ。最後にファイルを閉じるか「Synchronize」メソッドを発行した時にメタデータに記録されたファイルサイズのメタデータは更新される。ということは、そのファイルサイズ以前の操作ログを再生することで、最後に一貫性を確認できたところまで状態を遡ることができる。というか、ある時点でのファイルサイズさえ知っていれば、その時点でのデータベースの状態を再現できる。もちろん、実際のファイルサイズまで出来高払いで操作ログを再生することも可能だ。最後のレコードが書き込み途中だと困るわけだが、サイズを計算するためのメタデータを先頭に集めているので、そのサイズに満たなければ無視することでレコード単位のアトミック性は確保できる。
クロージャフラグ。開いたものを閉じるというエンジニアの責務がきちんと果たされているかどうかを調べるフラグだ。実際には、たとえCloseを呼ばなくてもデストラクタでCloseされるのでプログラムのミスでCloseされないということは稀であり、それよりはむしろ機械の故障とか運用のミスとかその他の予期せぬ要因でプロセスが死んだ場合にデータベースの閉じ損ねが発生する。いずれにせよ、閉じ損ねを検出した場合、データベースの整合性が取れている保証がないので、それ以上の事故を防ぐために、データベースは「unhealthy」状態になり、強制的に読み取り専用になる。元に戻すには、データベースをリストアする専用のメソッドを発行してもらうことになる。それはデータベースの再構築を伴うので相応の時間がかかるのだが、必要なことだ。とはいえ、クラッシュしたその瞬間に不整合を起こしうる更新操作が行われているとは限らないので、リストアをせずに「healthy」状態に戻す裏技も提供はする。でもそれはあまり使って欲しくないので、変なメソッド名にしよう。「MakeItHealthyByAnyMeans」とかそんな感じ。
