DBMをRDBMS風に使うためにセカンダリインデックスを使いたくなる場合もあるかもしれない。その設計と実装について考えてみたい。
key-valueストレージの一種であるDBMは、 RDB（リレーショナルデータベース）の文脈で言うと、主キーでしか検索できないデータベースだ。その不便さを補うには、セカンダリインデックスを実装すればよい。突き詰めると、リレーショナルデータベースのストレージエンジンもDBMと同じような実装なのだ。主キーを検索キーにしてその他のデータをシリアライズしたレコードをファイル上に保存する機能が絶対に必要だ。これを便宜的にメインデータベースと呼ぼう。主キー以外で検索したり、完全一致以外の条件で検索するためには、メインデータベースを先頭から末尾までスキャンして、該当のレコードの情報を返すことになる。それだと遅いので、検索条件で利用する属性を使ってセカンダリインデックスを作るのが通常だ。セカンダリインデックスの構築や保守を暗黙的に行い、そしてメインデータベースとセカンダリインデックスを組み合わせた複雑な検索アルゴリズムをオプティマイザが自動的に案出してくれるのが、RDBMS（リレーショナルデータベースマネジメントシステム）の本質的な機能の一つだ。もちろん他にも、複数のテーブルに対する更新でトランザクションのACID性をゴニョゴニョみたいな高度な機能をRDBMSは備えるので、DBMがRDBMSの代替になるなんてのは全く無理な話だ。ただ、DBMでRDBMSのストレージエンジンを実装することは実際にできる。MySQLのストレージエンジンとかを調べるとなかなか面白い。
セカンダリインデックスのデータ構造はいろいろ考えられるが、最も率直なのは、検索キーを第一キー、主キーを第二キーにした、キーだけの順序集合である。つまりstd::setだ。検索キーがstringで主キーがintであれば、std::set< std::pair< string, int>> として表現できる。検索キーがintで主キーもintなら、std::set< std::pair< int, int>> でOK。検索キーを第一キーに持つことで、当然それで検索ができる。主キーを第二キーに持つことで、ユニーク性が保証される。std::multimapを使って重複を許した検索キーと主キーの連想配列を作ればいいじゃないかという人もいるだろう。それも可能な解の一つではあるが、そこから特定の主キーを含むレコードを消す処理の効率がよくない。主キーもキーの一部であった方が一撃で消せて都合がいいし、同じ検索キーのレコードの並びが主キーによって決定的になることも利点だ。ということで、std::setをラップしてスレッドセーフにするためのクラステンプレートMemIndexを提供する。
template <typename KEYTYPE, typename VALUETYPE,
typename CMPTYPE = std::less<std::pair<KEYTYPE, VALUETYPE>>>
class MemIndex final {
public:
class Iterator {
public:
void First();
void Last();
void Jump(const KEYTYPE& key, const VALUETYPE& value = VALUETYPE());
bool Get(KEYTYPE* key = nullptr, VALUETYPE* value = nullptr);
void Next();
void Previous();
};
bool Check(const KEYTYPE& key, const VALUETYPE& value);
std::vector<VALUETYPE> GetValues(const KEYTYPE& key, size_t max = 0);
void Add(const KEYTYPE& key, const VALUETYPE& value);
void Remove(const KEYTYPE& key, const VALUETYPE& value);
std::unique_ptr<Iterator> MakeIterator();
};検索キーと主キーが両方intの場合、MemIndex< int, int> というクラスが定義できる。中身はstd::set< std::pair< int, int>>だ。そのオブジェクトに対して検索キーと主キーを与えてAddで追加し、Checkで存在確認し、Removeで削除することができる。GetValuesメソッドに検索キーを与えると、それに該当する主キーのリストを返してくれる。MakeIteratorでイテレータを作り任意の範囲検索をすることもできる。
このMemIndexとハッシュデータベースを使ったRDB風のユースケースを考えてみよう。一つのテーブル（＝メインデータベース）と一つのセカンダリインデックスという単純な構成だ。社員データベースというのを想定する。主キーは社員番号で、属性として名前と所属部署のIDを持つものとしよう。DBMに格納するデータば全て文字列にする必要があるので、主キーと属性はそれぞれシリアライズする。主キーは十進数列に変換すればよい。属性は、名前の文字列と所属部署IDの十進数列をタブで区切ったTSV文字列として表現する。現実のアプリケーションではProtocol Buffersとかを使うことが推奨されるが、今回は簡単にTSVで。サンプルデータをテーブルとして表せば以下のようになるかな。
| 社員番号 | 名前 | 所属部署ID |
| 10001 | Anne | 301 |
| 10002 | Marilla | 301 |
| 10003 | Matthew | 301 |
| 10004 | Diana | 401 |
| 10005 | Gilbert | 501 |
この社員データベースのレコードを構造体として実装しよう。シリアライズとデシリアライズの機能はメソッドとしてつける。デモ用にプリント関数もつけよう。
struct Employee {
int32_t employee_id = 0; // 社員番号
std::string name; // 名前
int32_t division_id = 0; // 所属部署ID
// シリアライズ。構造体を文字列に。
std::string Serialize() const {
return StrCat(employee_id, "\t", name, "\t", division_id);
}
// デシリアライズ。文字列から構造体に。
void Deserialize(const std::string_view& serialized) {
const std::vector<std::string> fields = StrSplit(serialized, "\t");
if (fields.size() < 3) {
Die("Deserialize failed");
}
employee_id = StrToInt(fields[0]);
name = fields[1];
division_id = StrToInt(fields[2]);
}
// 構造体の中身を標準出力する。
void Print() {
std::cout << "employee_id=" << employee_id << " name=" << name
<< " division_id=" << division_id << std::endl;
}
};これでDBMに構造化データを入れる準備は整った。次に、所属部署IDにセカンダリインデックスを張って、部署毎のメンバーの一覧を簡単に見られるようにしたい。MemIndexはオンメモリのインデックスなので、メインデータベースがロードされた時にその内容を全て反映させる必要がある。セカンダリインデックスはクリティカルなデータではないので、ファイルに保存する必要はない。いつだってメインデータベースから復元できるのだ。内部イテレータを使って全てのレコードをスキャンする実装はこんな感じになる。
// 検索キーも主キーも整数のセカンダリインデックス。
typedef MemIndex<int32_t, int32_t> DivisionIndex;
// メインインデックスをスキャンして所属部署IDのインデックスにデータを投入する。
void LoadIndexRecords(DBM* dbm, DivisionIndex* division_index) {
class IndexBuilder : public DBM::RecordProcessor {
public:
explicit IndexBuilder(DivisionIndex* division_index)
: division_index_(division_index) {}
// レコード毎にこの関数が呼ばれる。
std::string_view ProcessFull(
std::string_view key, std::string_view value) override {
const int32_t key_num = StrToInt(key);
Employee employee;
employee.Deserialize(value);
division_index_->Add(employee.division_id, key_num);
return NOOP;
}
private:
DivisionIndex* division_index_;
} index_builder(division_index);
dbm->ProcessEach(&index_builder, false).OrDie();
}メインデータベースの従業員情報が変更された場合、それに同期して所属部署ID用のセカンダリインデックスも更新される必要がある。ここで、アトミックにレコード操作を行うRecordProcessorが活躍する。
// 従業員情報を更新する。
// もし名前が空文字列であれば、そのレコードは削除される。
void UpdateEmployee(const Employee& employee, DBM* dbm,
DivisionIndex* division_index) {
const std::string& primary_key = ToString(employee.employee_id);
class Updater : public DBM::RecordProcessor {
public:
Updater(const Employee& employee, DivisionIndex* division_index)
: employee_(employee), division_index_(division_index) {
}
// 既存のレコードがある場合に呼ばれる。
std::string_view ProcessFull(
std::string_view key, std::string_view value) override {
const int32_t key_num = StrToInt(key);
Employee old_record;
old_record.Deserialize(value);
// セカンダリインデックスの古いエントリを消す。
if (old_record.division_id > 0) {
division_index_->Remove(old_record.division_id, key_num);
}
// もし名前が空文字列なら、この従業員のレコードを消す。
if (employee_.name.empty()) {
return REMOVE;
}
// セカンダリインデックスに新しいエントリを入れる。
if (employee_.division_id > 0) {
division_index_->Add(employee_.division_id, key_num);
}
// メインデータベースを更新する。
new_value_ = employee_.Serialize();
return new_value_;
}
// 既存のレコードがない場合に呼ばれる
std::string_view ProcessEmpty(std::string_view key) override {
const int32_t key_num = StrToInt(key);
// もし名前が空文字列なら、何もしない。
if (employee_.name.empty()) {
return NOOP;
}
// セカンダリインデックスに新しいエントリを入れる。
if (employee_.division_id > 0) {
division_index_->Add(employee_.division_id, key_num);
}
// メインデータベースを更新する。
new_value_ = employee_.Serialize();
return new_value_;
}
private:
const Employee& employee_;
DivisionIndex* division_index_;
std::string new_value_;
} updater(employee, division_index);
dbm->Process(primary_key, &updater, true).OrDie();
}これで全ての準備が整った。あとはユースケースを見てみよう。
int main(int argc, char** argv) {
// DBMを作る。
HashDBM dbm;
// 所属部署IDからメンバーを探すためのセカンダリインデックスを準備する
DivisionIndex division_index;
// メインデータベースを開く
dbm.Open("casket.tkh", true, File::OPEN_TRUNCATE).OrDie();
// メインデータベースを開いた後は、セカンダリインデックスをロードする。
// とはいえ、現時点では従業員が登録されていないので、何も起こらない。
LoadIndexRecords(&dbm, &division_index);
// 従業員を何人か登録する。
const std::vector<Employee> employees = {
{10001, "Anne", 301}, {10002, "Marilla", 301}, {10003, "Matthew", 301},
{10004, "Diana", 401},
{10005, "Gilbert", 501},
};
for (const Employee& employee : employees) {
UpdateEmployee(employee, &dbm, &division_index);
}
// 本当は必要はないが、テストのためにデータベースを閉じる。
dbm.Close().OrDie();
// 閉じたので、開ける。
dbm.Open("casket.tkh", true).OrDie();
// メインデータベースを開いた後は、セカンダリインデックスをロードする。
LoadIndexRecords(&dbm, &division_index);
// 従業員情報を更新する。
const std::vector<Employee> updates = {
{10001, "Anne", 501}, // アンはギルバートの部署に移った
{10003, "", 0}, // 残念だがマシューは退社した。
{10006, "Minnie May", 401}, // 新しい仲間達。
{10007, "Davy", 301}, {10008, "Dora", 301},
};
for (const Employee& employee : updates) {
UpdateEmployee(employee, &dbm, &division_index);
}
// 部署毎にメンバーをプリントする。
for (const int32_t division_id : {301, 401, 501}) {
std::cout << "-- Division " << division_id << " --" << std::endl;
for (int32_t employee_id : division_index.GetValues(division_id)) {
Employee employee;
employee.Deserialize(dbm.GetSimple(ToString(employee_id)));
employee.Print();
}
}
// データベースを閉じる。
dbm.Close().OrDie();
return 0;
}こんな感じで、DBMだけでもRDBっぽく構造化データを扱うことができる。メインデータベースは性能に定評のあるハッシュデータベースなので爆速。セカンダリインデックスはオンメモリなので爆速。なので全体的にもかなり高いスループットを出せるはずだ。データベースのロード時に全レコードをスキャンしなきゃならないのが欠点と言えば欠点だが、それが許容できるなら面白い構成だとだろう。そうはいってもインデックスもファイルで実現したいという人のためには、ほぼ同じAPIを備えつつファイル上でセカンダリインデックスをFileIndexというクラスも提供される。これはツリーデータベースのキーとして検索キーと主キーを連結したものを使うことで実現できる。FileIndexを使った場合は起動時に全データを読み込む処理を省略できる。
ただ、このコードをメンテするのは結構大変だと思う。確かに高速に動作するだろうけども、こうまでして単一マシンのスループットを上げなきゃいけないユースケースというのは限られるだろう。もう一段抽象化して、任意の属性にセカンダリインデックスを張れるスキーマレスデータベースみたいなフレームワークを作るのも一興だ。オブジェクトデータベースみたいなフレームワークにもできるかもしれない。ただ、下手をすると、RDBMSの仕事をプログラマがやるというなかなかシュールな事態になるだけだ。それでもやりたい場合は、是非こちら側に。
