DBMの設計と実装 その1 ハッシュ関数

個々のレコードがハッシュテーブル内のどのバケットに属するかはハッシュ関数で決める。入力値の種類によらずハッシュ値がうまいことばらけて衝突が起こりにくい関数が良い。今回は定番のMurmur hashを採用した。Rubyの文字列型のハッシュ関数もこれだ。

Murmur hashの値に対してバケット数で剰余を取れば十分なハッシュ関数として機能する。しかし、以前にそれで実装したソースを公開していたら、Murmur hashの作者から直に連絡があり、下位ビットだけ使うのは最善ではないと指摘された。32ビット以下のハッシュ関数が必要な場合、XORを使って上位ビットの折返しをした上で、剰余を取るべきだと。したがって、バケット数に応じたハッシュ関数の実装は以下のようになる。

uint64_t PrimaryHash(std::string_view data, uint64_t num_buckets) {
  uint64_t hash = HashMurmur(data);
  if (num_buckets <= UINT32MAX) {
    hash = (((hash & 0xffff000000000000ULL) >> 48) |
            ((hash & 0x0000ffff00000000ULL) >> 16)) ^
           (((hash & 0x000000000000ffffULL) << 16) |
            ((hash & 0x00000000ffff0000ULL) >> 16));
  }
  return hash % num_buckets;
}

いちおう、ランダムな文字列を与えると値が期待通りにばらけるかを調べてみたい。1,000,000個のランダムな文字列を生成して1,000個のバケットに振り分ける。ランダムな文字列とはaからzまでの文字をランダムに選択した長さ8文字の文字列である。複数の文字列が同じになる確率は1/(26^8)なので無視できる。

TEST(DBMImplTest, PrimaryHash) {
  constexpr int32_t num_records = 100000;
  constexpr int32_t num_buckets = 100;
  constexpr double mean_count = num_records * 1.0 / num_buckets;
  std::vector<int32_t> buckets(num_buckets, 0);
  for (int32_t i = 0; i < num_records; i++) {
    const std::string& text = MakeRandomCharacterText(8, i, 'a', 'z');
    const int64_t bucket_index = PrimaryHash(text, num_buckets);
    EXPECT_LT(bucket_index, num_buckets);
    buckets[bucket_index]++;
  }
  int32_t min_count = INT32MAX;
  int32_t max_count = 0;
  double variance = 0;
  for (const auto count : buckets) {
    min_count = std::min(min_count, count);
    max_count = std::max(max_count, count);
    variance += std::pow(count - mean_count, 2);
  }
  variance /= num_buckets;
  const double stddev = std::sqrt(variance);
  EXPECT_GT(min_count, mean_count * 0.8);
  EXPECT_LT(max_count, mean_count / 0.8);
  EXPECT_LT(stddev, mean_count * 0.1);
}

各バケットで1000回の頻度になるのが期待値である。それに対し最小値は924、最大値1108、標準偏差30.76という結果になった。いずれの数値を見ても、なかなか良い分布になっていると理解できる。"0" から "1000000" の十進数文字列を入力してもほぼ同じ結果になった。同じ実験をより単純なFNV hashでもやってみたところ、最小値909、最大値1105、標準偏差32.12だ。この数値だけ見るとあんまり変わらないというのが正直なところだ。とりあえずMurmurでもFNVでも一般的なユースケースでは問題ないということはわかる。Murmurの方がちょっと優勢なような気がしなくもないが、こんな基本的な統計値だけで最善を判断するのは早計だろう。長いものに巻かれてMurmurを使うことにはするけども。

バケット数の選択も重要だ。衝突をリンクリストで管理するチェイン法を用いる場合、個々のレコードを操作するための平均計算量はレコード数Nとバケット数Mに大してO(N/M)であり、MがNに対して十分大きい場合にのみO(1)とみなせる。基本的にはレコード数と同じくらいのバケット数で良い。入力されるレコード数は事前にはわからないので、具体的な値はユーザに指定してもらうことになる。

ところで、シャーディングを考えるとこの問題はもうちょい複雑になる。単一の巨大なファイルでデータベースを構築すると、再構築の際の記憶領域の管理やバックアップの際に面倒だし、再構築や並列分散処理もしにくい。その場合、シャーディングを行うのが普通だ。ファイルを複数に分割して、どのレコードがどのファイルに属するかを別のハッシュ関数で決めることになる。シャーディングにハッシュ関数を使う場合には、ファイル内のハッシュ関数と無関係に見える振る舞いをすることが望ましい。シャーディング側のハッシュ関数の実装はここでは定義しないが、この時点でひとつ言えるのは、シャード数と個々のファイルのバケット数は互いに素であることが望ましいということだ。そうすれば、たとえ同じ実装を使ったとしても、ファイル内のバケット利用の分布が異常に偏るという事態は避けられる（例えばシャード数が10でファイル内バケット数が100の場合、個々のファイルで利用されるバケットインデックスの下一桁は常に同じになってしまう）。普通はシャード数は個々のファイルのバケット数よりも小さい。となると、個々のファイルのバケット数が素数であれば、互いに素であることが保証される。個々のファイルのバケットの分布だけを考えても、バケット数が素数であることはなんか良さそうな気がする。ということで、単純な素数判定関数を書き、さらに、バケット数がユーザに指定された際には、指定された数以上の最初の素数を実際のバケット数にすることにした。

uint64_t IsPrimeNumber(uint64_t num) {
  if (num < 2) {
    return false;
  }
  if (num == 2) {
    return true;
  }
  if (num % 2 == 0) {
    return false;
  }
  const uint64_t sq = std::sqrt(num);
  for (uint64_t d = 3; d <= sq; d += 2) {
    if (num % d == 0) {
      return false;
    }
  }
  return true;
}

int64_t GetHashBucketSize(int64_t min_size) {
  int64_t num = min_size;
  while (num < INT64MAX) {
    if (IsPrimeNumber(num)) {
      return num;
    }
    num++;
  }
  return min_size;
}

素数判定の計算量が√Nなので、バケット数判定の平均計算量は、N以上で素数が連続して現れない区間長の期待値に√Nを掛けたものになるはずだ。素数定理によるとN以下の素数の出現数の近似は1/log(N)てことなので、N近傍なら傾向は同じだろうから、逆数のlog(N)が区間長の期待値ってことでいいのかな。もしそうなら全体の計算量はO(√N *log(N))になる。最悪を考えると、チェビシェフの定理により、Nから2Nのまでの間に次の素数があるはずなので、計算量はO(√N*N)ということになる。実際に2^62を与えて動かしてみると、14秒かかって4,611,686,018,427,388,039という結果が得られた。2^48だと129ミリ秒で281,474,976,710,677。2^32だと1ミリ秒以下で4,294,967,311。バケット数の設定はハッシュテーブルを作る際に1回行うだけなので、多少遅くても問題ない。

ハッシュ関数ひとつ取っても意外に奥が深い。千里の道も一歩から。