TkrzwのMac対応とSetAndGet

要望があったので、データベースライブラリTkrzwを久しぶりに更新して0.9.5をリリースした。Macでビルドできないという不具合を修正して、SetAndGetというマニアックな機能をつけた。瑣末な話だが、メモがてら経緯を書いておこう。
f:id:fridaynight:20210422103914p:plain

Macでどうしてビルドできなかったかというと、Linux独自のmremapというシステムコールを使うようになっていたからだった。mremapはメモリマップのリサイズを一撃で行うという、めっちゃいけてるシステムコールなんだけども、POSIX標準には含まれておらず、Macでは実装されていない。よって、Linuxとそれ以外で実装を分けるプリプロセス分岐を書いて対処した。

#if defined(_SYS_LINUX_)

void* tkrzw_mremap(
    void *old_address, size_t old_size, size_t new_size, int fd) {
  return mremap(old_address, old_size, new_size, MREMAP_MAYMOVE);
}

#else

void* tkrzw_mremap(
    void *old_address, size_t old_size, size_t new_size, int fd) {
  if (munmap(old_address, old_size) != 0) {
    return MAP_FAILED;
  }
  return mmap(0, new_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
}

#endif

Linux以外では、メモリマップのリサイズをする度にマップの解除と再作成をしているので、効率が悪い。だからこそLinuxではmremapがあるのだ。しかし、そもそもこのリサイズ処理は極力呼ばれないように、新しい領域は既存領域の2倍を確保するように工夫している。よって、std::stringのキャパシティ確保の方法と同じように、たとえリサイズの計算量がO(N)だとしても、全体の償却計算量はO(N)で済むようになっている。

ところで、Macだとmemmemも未定義でエラーになっていた。それらのPOSIX標準ではないがGNU標準であるところのユーティリティ関数は、Macだと_POSIX_C_SOURCEの値が900000L以上でないと有効にならないという謎仕様らしい。POSIX標準APIの最終更新は200809Lだそうで、以前は_POSIX_C_SOURCEの値にはそれを採用していた。Macではなぜかその値がPOSIX非標準のAPIの見え方にも影響を与えるらしく、900000L未満だと少なくともmemmemは隠される。GNUのFeature Test Macros文書によると、大きい値を設定しておけば未来の標準も見えるようにしてくれるそうで、999999Lを設定しておくことで対処した。

まあそんなわけで、Mac上でもTkrzwが利用できるようになった。Kyoto Cabinetよりもだいぶ高速に動作するっぽい。IOをmmap前提にしたのとスレッド回りの最適化にめちゃ頑張ったのが奏功したかな。Windows対応もやろうやろうと思いつつ、開発環境の準備が億劫でやっていない。

ついでに、SetAndGetなる機能をつけた。レコードの更新と、更新前のレコードの値の取得を同時に行う機能だ。同様に、レコードの削除と削除前のレコードの値の取得を同時に行うRemoveAndGetもつけた。

一般的には、データベースのアクセスは、データの取得と更新を別々の操作で行うことが多い。例えば、ユーザのIDに紐づけてニックネームを管理するデータベースがあったとして、既にニックネームが登録されていればそれを使い、そうでなければ新しいニックネームを登録するという処理を考えてみよう。

# 既存のニックネームをDBから取得する。
nickname = dbm.Get(user_id)
# ニックネームがなければ、作って、DBに登録する。
if not nickname:
  nickname = MakeNickname()
  dbm.Set(user_id, nickname)
# そのニックネームで挨拶する
print("こんにちは" + nickname + "さん")

そもそも、上記の実装はレースコンディションがあるのがいただけない。複数スレッドで同じユーザIDに処理が走るとニックネームの上書きが起きうる。よって、既存の値の更新には失敗するフラグを使ってそれを抑止する。

# とりあえずニックネームを作る。
nickname = MakeNickname()
# DBに登録しようとするが、既存値があれば失敗する
if not dbm.Set(user_id, nickname, False).IsOK():
  # 失敗した場合、DB内の既存の値を取得する
  nickname = dbm.Get(user_id)
# そのニックネームで挨拶する
print("こんにちは" + nickname + "さん")

とりあえずニックネームを作るというのが無駄な感じもするが、計算量がO(1)であれば構わない。それよりも、比較的にコストが高いと考えられるデータベースアクセスを無駄に2回もやっているのがダサい。よって、既存値を取得しようとするとともに、なければ新規の値を設定するという処理を一撃でやってしまいたい。

# とりあえずニックネームを作る。
nickname = MakeNickname()
# DBに登録しようとするが、既存値があれば失敗しつつ、既存値を取得する
status_value = dbm.SetAndGet(user_id, nickname, False)
if not status_value[0].IsOK():
  nickname = status_value[1]
# そのニックネームで挨拶する
print("こんにちは" + nickname + "さん")

データベースのAPIは1回しか呼んでいないし、データベース内部でもレコードの検索処理は1回しかしない。排他制御の点でも性能の点でも完璧な方法である。いかにも恣意的に考えたユースケースに見えるかもしれないが、わざわざDBMを使うということは、これに類する最適化を追求したいということなのだ。2回アクセスするより1回のアクセスで済ませる方が高速だというのは自明だ。

さらに細かいどうでもいい話になるが、C++で同じようなAPIを実現することは簡単ではない。最新版では、Setメソッドが拡充されて、以下のようになっている。

Status Set(string_view key, string_view value, bool overwrite = true,
           string* old_value = nullptr);

省略可能なold_valueというパラメータが追加され、その値がnullptrでなければ、その文字列オブジェクトに既存の値を代入するようになった。ただ、これには問題がある。overwriteフラグが偽で上書き禁止の場合には、既存値があれば戻り値にエラーコードが設定されるので、既存の値の有無がわかる。しかし、overwriteフラグが真で既存値の上書きを行う場合、既存値があっても成功が戻り値になるので、既存値があるかどうかを区別できないのだ。このシグネチャでは、呼び出された側からはold_valueにnullptrを設定することはできない。考えられる代案は二つだ。既存値があるかどうかを報告するための変数ポインタのパラメータを追加するか、戻り値を構造化するかだ。

Status Set(string_view key, string_view value, bool overwrite = true,
           string* old_value = nullptr, bool* hit = nullptr);

std::pair<Status, std::unique_ptr<string>> Set(
  string_view key, string_view value, bool overwrite = true);

結論としては、どちらの代案も採用していない。なんか煩雑でダサいので。それよりは、多くの場合で、元々の案のシグネチャの方が使いやすいだろう。関数を呼び出す前にold_valueに元からDB内で有り得ない値を設定しておけば、それが変更されているか調べることで既存値の有無を判定できるからだ。空文字列が禁止されているなら空文字列でいいし、そうでないなら "\x7f" のような異常なダミー文字列でも良い。ただし、任意のバイナリを処理するにはそれだと困る。JavaとPythonとRubyのインターフェイスを実装するための基盤としては、ユースケースに勝手な前提をつけるわけにはいかない。

なので、C++の標準の「ユーティリティAPI」としては元々の不完全な機能性の関数を提供しつつ、Java/Python/Rubyのインターフェイスでは、コールバックを使った最適な実装をしている。もちろん、C++のアプリケーションでも同じことはできる。

// コールバック用のクラス
class Processor final : public tkrzw::DBM::RecordProcessor {
 public:
  // コンストラクタ。エラーコードを格納するオブジェクト、キー、新規の値、
  // オーバーライドするかのフラグ、既存値を受け取る変数のポインタ、
  // 既存値の有無を受け取る変数のポインタを設定。
  Processor(tkrzw::Status* status, std::string_view value, bool overwrite,
            std::string* old_value, bool* hit)
      : status_(status), value_(value), overwrite_(overwrite),
        old_value_(old_value), hit_(hit) {}
  // 既存値がある場合に呼ばれるコールバック。
  std::string_view ProcessFull(std::string_view key, std::string_view value) override {
    *old_value_ = value;
    *hit_ = true;
    if (overwrite_) {
      return value_;
    }
    status_->Set(tkrzw::Status::DUPLICATION_ERROR);
    return NOOP;
  }
  // 既存値がない場合に呼ばれるコールバック。
  std::string_view ProcessEmpty(std::string_view key) override {
    return value_;
  }
 private:
  tkrzw::Status* status_;
  std::string_view value_;
  bool overwrite_;
  std::string* old_value_;
  bool* hit_;
};

// コールバック用のオブジェクトを作成。
tkrzw::Status impl_status(tkrzw::Status::SUCCESS);
std::string old_value;
bool hit = false;
Processor proc(&impl_status, value.Get(), overwrite, &old_value, &hit);

// データベースにアクセスし、該当レコードでコールバックを発動
// エラーコードは論理和として記録。
tkrzw::Status status = dbm->Process(key.Get(), &proc, true);
status |= impl_status;

// 既存値があれば、それを利用する。
if (old_value != nullptr && hit) {
  std::cout << *old_value << std::endl;
}

追記：0.9.6から、同じことをラムダ式を使って簡潔に書けるようにしてみた。ラムダ式の外部の変数がキャプチャできるのは本当に楽で、JavaScriptっぽいノリで書くことができる。

std::string old_value;
bool hit = false;
tkrzw::Status status = dbm->Process(key.Get(),
  [&](std::string_view rec_key, std::string_view rec_value) -> std::string_view {
    if (rec_value == tkrzw::DBM::RecordProcessor::NOOP || overwrite) {
      return value.Get();
    }
    old_value = rec_value;
    hit = true
  }, true);
if (hit) {
  status |= tkrzw::Status::DUPLICATION_ERROR;
}

てなわけで、お気楽なユースケースでは直感的にコードが書けるようにするとともに、変態的に最適化したユースケースにも対応できるようにしている。

正直、DBMの実装なんてのは、全く革新的でもなんでもない地味な作業だ。でも、これがあると、高負荷なデータ管理とか膨大なデータ集計が簡単に実現できるようになる。下の層から地道に積み上げていけば、便利なポップアップ辞書がフルスクラッチで実装できたりもするのだ。てことで、DBMはもうちょい流行ってもいいと思う。

豪鬼メモ

一瞬千撃

TkrzwのMac対応とSetAndGet