豪鬼メモ

一瞬千撃

DBMの設計と実装 その15 スキップデータベースの検索

スキップデータベースを検索するアルゴリズムの要点について考えてみる。メモリ確保の戦略が重要になってくる。


一般論として、効率的に動作する実装を追求するにあたり、以下の点を気を付けるべきだ。重要な順に並べる。

  1. 最適なアルゴリズムを選択する。
  2. 外部リソースにアクセスする頻度をできるだけ減らす。ディスクアクセスやネットワークアクセスがそれにあたる。
  3. スレッドがロックされる頻度をできるだけ減らす。
  4. システムコールを呼び出す頻度をできるだけ減らす。
  5. newやmallocによる動的メモリ確保の頻度をできるだけ減らす。

以上を念頭におきつつ、スキップデータベースの検索操作について考えよう。毎回の検索をするにあたって、log2(N)回のレコード読み込みが発生するのが通常であるから、例えば100万個のレコードを格納したデータベースであれば、20回くらいのレコード読み込みが発生する。このアルゴリズムは前提かつ最善だ。よって、毎回のレコード読み込みをいかに高速化させるかが重要になる。さて、レコードの読み込みには当然、ファイルを読まないといけない。素直に考えると、読み込み操作にはディスクアクセスを伴うし、システムコールも呼び出さねばならない。しかし、実際にはそうではない。ファイルを読み込んだらファイルシステム様がページ単位でキャッシュしてくれるので、毎回の読み込み操作でディスクアクセスが発生することはない。そして、今回の場合、抽象化されたファイルとしてメモリマップを使うので、システムコールを呼び出すことなくファイルの読み書きができる。そして、読み取り操作の際にかけるreader-writerロックの共有ロックは互いをブロックしないので、スレッドがロックすることもない。となると、動的メモリ確保のコストが最も大きい敵になる。それを踏まえて、スキップデータベースのレコードは以下のようなクラスで表現する。データメンバにだけ着目されたい。

class SkipRecord {
 public:
   Status Read(int64_t offset, int64_t index, ...);

 private:
  static constexpr int32_t READ_BUFFER_SIZE = 256;
  char buffer_[READ_BUFFER_SIZE];
  char* body_buf_;
  const char* key_ptr_;
  const char* value_ptr_;
  int32_t key_size_;
  int32_t value_size_;
  std::vector<int64_t> skip_list_;
};

256バイトのバッファがクラスに内包されている。このクラスのオブジェクトをスタックオブジェクトとして生成した段階で、スタックに256バイトのバッファが確保されるということだ。Readメソッドを呼ぶとファイルを読み込んで、クラスの各データメンバを初期化して利用可能にする。利用とは、キーや値を参照したり、スキップリストの飛び先のオフセットを参照したりすることだ。読み込み操作をするにあたり、レコードの大きさが事前にわかるわけではないので、とりあえず適当な長さのデータをファイルから読み込む。その投機的な読み込みが256バイトのバッファを使って行われるのだ。それで必要なデータを全て読み込めれば、動的メモリ確保をすることなくレコードオブジェクトの構築を完了させることができる。その初回の読み込みで最低限取得せねばならないのは、レコードのメタデータである。そのレコードのサイズが少なくとも分かるようにならなくてはいけない。初回の読み込みでキーや値の本体を読み込めなかったとしても、全体のサイズが分かっていれば、それを使って二回目の読み込みで確実に初期化を完了させることができる。その際に必要なバッファが256バイト以上だった場合にのみ、newでメモリを確保して、それがbody_bufというメンバに代入される。その領域を解放はデストラクタが担う。

初回の投機的な読み込みで実際に読み込む長さは、レコードのインデックスから計算したレベルによって変える。スキップリスト全体を読み込むとともに、あわよくばキーと値も読み込みたい。シリアライズされたスキップリストの長さはレベルにオフセット幅の4を掛けた値で、レベルの最大値は32ということにしているので、その場合は最大128バイトである。オフセット幅は7まで設定できるが、その場合は192バイトだ。さらにキーと値の本体を投機的に読み込みたいので、32バイトを余計に読み込みたい、192と32を足すと256。典型的には、レベル0であるレコードが多いので、32バイトだけを読み込むことになる。マジックデータとキーの長さと値の長さのフットプリントが3バイトだから、残り29バイトにキーと値の長さの合計が収まれば、初回の読み込みでレコードの初期化は完了できる。多くの場合はこのパターンに当てはまるだろう。

「典型的な場合に高速で、そのパターンに当てはまらなくてもちょっと遅いけどちゃんと動く」が最適化の基本だ。ハッシュデータベースのレコードでも同じような投機的な読み込みを実装するだろう。もっと言えば、メモリマップIOに限定した最適化を行うことも考えられる。ファイルの中身をメモリとして参照できるのだから、バッファにデータをコピーすることなく、アドレスを直接指定してキーや値のstring_viewを構築すれば良いのだ。ただ、その最適化は最初は導入しないでおく。最適化バージョンと通常バージョンの二種類の実装をメンテするのがだるいからだ。切り札は最後までとっておこう。

ファイル読み込みに最善の実装を施すとして、もっと高速化できないものかと考える。できるのだ。キャッシュを使えば、そもそも読み込みなんてしなくていい。キャッシュというと過去のアクセスパターンから対象を選定するLRU的なアルゴリズムを思い浮かべる人が多いかもしれないが、スキップリストの場合はそうではない。レベルが高いノードほど利用率が高いという前提知識を利用できるからだ。キャッシュ内のデータは配列として管理できるので、ルックアップのためにハッシュテーブルを用意する必要もない。例えば、ステップユニットが4で、レベル2以上のレコードをキャッシュすると決めたなら、インデックスが16で割り切れるレコードはキャッシュすることになる。キャッシュの配列は全レコード数を16で割った要素数を持つようにしておいて、個々のレコードのキャッシュはインデックスを16で割った添字で格納すればいい。レベル2以上がキャッシュされている状態では、レベル1の最近傍ノードを特定するのに最大4回の読み取りが発生し、レベル0の該当ノードを特定するのに最大4回の読み取りが発生するので、最大8回の読み取りで検索が完了することになる。100万レコードのデータベースであれば、1/16の62500レコードをキャッシュすると、読み取り回数が20回から8回に減ることになる。レベル1以上を全部キャッシュするなら、250000レコードがキャッシュされ、読み取り回数は4回になる。全部キャッシュすれば当然100万レコードがキャッシュされて読み取り回数は0回になる。とはいえ、全部のレコードを何度も検索するのでなければ、さすがに全部キャッシュするのは無駄だ。しかし、小さめのデータベースなら、レベル1以上をキャッシュするという設定は普通にありだと思う。

レコードをキャッシュするにあたって、SkipRecordオブジェクトをそのまま複製してキャッシュするわけにはいかない。なぜなら、奴は256バイトのバッファを抱えてしまっているので、空間効率が悪くなりすぎてしまう。よって、必要なデータだけをシリアライズしてキャッシュに保持することが求められる。スキップリストとキーと値をシリアライズするだけなので、難しくはないだろう。

前々回の議論でも少し触れたが、スキップリストの二分探索は極めて単純に実装できる。以下の手順を追えば良い。

  1. インデックス0のレコードを現在位置にする。
  2. 自分のレベルをインデックスから計算し、最大レベルのスキップ先から順にレコードを取り出していく。3で述べる終点以後のスキップ先は無視する。
  3. 検索キーよりも大きいスキップ先のレコードが見つかれば、そのオフセットを終点として登録する
  4. 検索キーよりも小さいスキップ先のレコードが見つかれば、そのレコードを現在位置にして、1に戻る。
  5. 現在位置のレコードが検索キーと一致していれば、そのレコードを返す。
  6. 現在位置のレコードのサイズを現在位置に足して、次のレコードまで進み、4に戻る。
  7. ファイルの最後か、検索途中に見つけた終点に到達していたら、見つからなかったことを報告する

要点は、検索キーより小さいレコードが見つかった場合に位置を進めて始点とするとともに、検索キーより大きいレコードが見つかった場合にそれを検索範囲の終点として記憶しておくことである。二分探索とはそういうものだ。ところで、スキップデータベースはキーの重複を許す仕様であることを思い出してほしい。もし重複を許さないとしたら、検索キーと同じキーのレコードが見つかった時点でそれを返すという手順を加えることができた。しかし、重複を許す場合、該当キーの最初のレコードを報告しないといけないので、「検索キーより小さい場合にのみ進む」という、より保守的な手順になる。