豪鬼メモ

一瞬千撃

DBMの設計と実装 その4 ハッシュデータベースの構造

ハッシュテーブルを使ったデータベースの構造について大いに語ってみよう。基本的な構造について述べてから、インプレース更新と追記更新の違いについて明らかにする。


HashDBMというクラスはハッシュテーブルを使ったデータベースをファイル上で実現する実装として提供されるのだが、その構造について詳細に定義する。まずはこの図を見られたい。
f:id:fridaynight:20200519155246p:plain

ファイルの冒頭には、ハッシュテーブルがある。ハッシュ表とも言う。ハッシュテーブルは整数の配列であり、個々の要素をバケットと呼ぶ。要素数はデータベース作成時に決められるが、それをバケット数と呼ぶことにしよう。データベースに追加される各々のレコードに対してはそのキーにハッシュ関数を適用して、キーのバイト列に対して一意に決まる64ビットの整数値を算出する。そのハッシュ値バケット数で割った余りで、そのレコードがどのバケットに属するかが決まる。各バケットの値は、そのバケットに属するレコードの先頭アドレスである。複数のレコードが同じバケットに属することもあるわけだが、その場合、単方向連結リストとして管理される。すなわち、一つ目のレコードのメタデータとして、二つ目のレコードのアドレスが格納されている。この方式を連鎖法とかチェーン法とか言う。

レコードを検索する際には、与えられたキーからハッシュ値を算出して、そのバケットを特定して、連結リストを辿る。個々のレコードを読み込んで、キーが同一のレコードがあれば、その値を返す。

さあ、ここで新しいレコードを追加しよう。新しいレコードのハッシュ値を算出した結果、それが属すべきレコードには既に2つのレコードが存在していたとする。
f:id:fridaynight:20200519160306p:plain

バケットの値は、新しいレコードのアドレスとなる。新しいレコードの子レコードとして、既存の連結リストの先頭レコードのアドレスが記載される。つまり、新しいレコードが連結リストの先頭になる。そうすると、既存のレコードの領域に対しては全く書き換えをぜずに、新しいレコードを追加できる。バケットだけは更新される。ここまでは、インプレース更新モードでも、追記更新モードでも同じである。

二つの更新モードの違いは、同じキーのレコードの値を更新する時に明らかになる。インプレース更新では、既存の領域の値の部分を書き換える。追記更新では、同じキーのレコードをファイルの末尾に追記する。連結リスト内ではレコードは新しい順に並んでいるので、先に見つかったレコードの値を返せば、既存のレコードを上書きしたとみなせるわけだ。よって、既存のレコードを書き換える場合、インプレース更新ではデータベースのサイズは増加しないが、追記更新では増加する。

インプレース更新では既存の領域を書き換えるので、書き換え途中にプロセスが死ぬと、その領域が不完全な状態になりうる。データの書き換え途中のシステムコールが停止させられた場合にその領域がどうなるかは実装依存なので定義できない。レコードの前半が新しい状態で後半が古い状態になる可能性が少なくともあり、それはそのレコードの破壊を意味する。一方で、追記更新では既存のレコードを書き換えないので、既存のレコードのデータが失われることは決してない。ハッシュテーブルはどんどん書き換えられるので壊れる可能性があるが、レコード本体さえ残っていれば復元できる。追記更新は空間効率が悪いという欠点はあるが、この究極の永続性(durability)は追記型データベースならではである。

インプレース更新に話を戻す。既存のレコードを書き換える場合にも、元の値よりも新しい値の方がサイズが大きい場合には、元の領域には書き切れないので、新しいレコードがファイル末尾に追記される。既存の領域には削除マークが付けられるとともに、連結リストも書き換えられる。つまり、既存の親は新しいレコードを指し、新しいレコードは既存の子を指すようになる。そして、無効マークが付けられた領域はフリーブロックと呼ばれ、フリーブロックプールという集合に登録される。フリーブロックプールは、個々のフリーブロックのサイズをキー、アドレスを値にした std::map だ。新しいレコードを追加する際にはまずフリーブロックプールが参照され、新しいレコードを格納するのに十分なサイズの最小のフリーブロックプールを見つけて、あればその領域を再利用する。そうして再利用された領域のレコードは、元々の領域よりも小さいことがあり、余った部分にはパディングとしてゼロ文字が埋められる。このパディングは無駄なようだが、見方を変えれば、パディングの分だけ既存のレコードを移動させずに大きくできるバッファであるとも言える。

レコードが任意のサイズの値に断続的に書き換えられることを考えると、むしろ積極的にパディングを使いたい。そのためにアラインメントという機構がある。アラインメントパワーというパラメータをデータベースに設定すると、それをPとしたら、全てのレコードのアドレスが2^Pの倍数になるようにパディングが埋められる。P=0なら2^0で1の倍数(つまりアラインメントなし)で、P=3なら2^3で8の倍数になる。この設定は、後にこのハッシュデータベースを基盤としてB+木のデータベースを構築した時に重要となるのだ。P=12にすると全てのレコードがOSのページサイズ4096バイトにアラインメントされるようになるので、I/Oの効率が最大化される。ちなみに、追記更新の場合には、領域の再利用をしないので、アラインメントを設定する意味は全くない。

レコードの削除は、既に述べたレコードが移動する際の手順と同じで、既存のレコードの領域に無効マークをつけて、連結リストの書き換えを行う。親レコードの子レコードを自分から自分の子に挿げ替えるということだ。ところで、連結リストだけ書き換えれば、無効化されたレコードは到達不能になるので、無効マークをつける必要はない。しかし、実際にはそうしている。それは、全ての既存レコードを順に操作するイテレータのためだ。ファイルを前から読んでいき、無効マークのレコードを読み飛ばせば、シーケンシャルアクセスだけで全てのレコードに到達できる。

追記更新に話を移そう。既に述べたように、既存レコードの上書きは、ファイル末尾に新レコードを追加することで行う。レコードを削除する際には、削除マークがついたレコードを追加する。検索時に先に削除マークが見つかれば、そのレコードは存在しないと報告される。インプレース更新と比較した追記更新の特徴を列挙すると以下のようになる。

  • 既存レコードの領域は決して書き換えない。無効マークの書き込みもしない。
  • 既存レコードの値の更新は新しい値を持った新規レコードの登録で行う。
  • 既存レコードの削除は削除マークを持った新規レコードの登録で行う。
  • フリーブロックプールは利用しない。

逆に考えれば、上記以外は双方で共通だ。ということで、実はインプレース更新と追記更新のデータベースのデータ構造は全く同じにでき、フラグを読んでアルゴリズムの振る舞いをちょっと変えるようにするだけで、双方をサポートした実装になるはずだ。削除マークの処理だけはちょっと面倒になるが、まあなんとかなるだろう。

追記更新のデータベースでは、インプレース更新の時のように、ファイルを前から読んでいくイテレータは使えない。なぜなら、各レコードの最新の状態は、該当のバケットの連結リストを先頭から辿らないとわからないからだ。よって、イテレータバケットを一つずつ訪れて、それに所属するレコードを一気に読み出すという形で実装される。これはランダムアクセスになるので、追記更新のデータベースのイテレータはインプレース更新のイテレータより遅くなってしまう。一方で、追記更新のデータベースへの書き込みは常にファイル先頭のハッシュテーブルかファイル末尾に集中する。ファイルシステムのページ単位で考えると、ハッシュテーブルは常に同じページ群としてキャッシュ上に存在し、末尾はシーケンシャルアクセスになるので、ダーティページの発生とその書き戻しの頻度を最小限に抑える効果がある。なので、書き込みのスループットはインプレース更新より追記更新の方が高くなることも多い。空間効率の悪い追記更新の方がスループットが高いことがあるというのは面白くはないだろうか。

最後にめっちゃ細かい話をすると、レコードのアドレスを何バイトで表現するかも意外に重要だ。アドレス幅は個々のバケットのサイズと同義なので、アドレス幅はできれば小さい方が良いが、一方でアドレス幅はファイルの最大サイズを制限するので、小さ過ぎてもダメだ。デフォルトは4バイトにしよう。すなわち2^(8*4)で4GBまでのアドレスを扱えるので、つまりファイルの最大サイズは4GBということになる。これは21世紀の基準だとちと小さすぎるかもしれない。なので、アドレスの幅は任意に設定できるようにしたい。3バイトなら16MBまで、4バイトなら4GBまで、5バイトなら1TBまで、6バイトなら256TBまでのファイルが扱える。ところで、アラインメントが設定された場合、アラインメント以下の下位ビットは常にゼロになることが保証されるので、その分だけビットシフトした値を保存しても情報欠損がない。つまり、デフォルトのP=3で8バイトアラインメントの場合、3ビットシフトしたアドレスを保存できるので、変域も8倍になる。なので、デフォルトのアドレス幅は4バイトだが、32GBまでのファイルが扱える。

詳細に定義するといいながら概要だけで長くなってしまったので、詳細については次回。