Reading: A Fast, Minimal Memory, Consistent Hash Algorithm

pdf

Consistent Hashing の嬉しくない点

Consistent Hashing と比べて嬉しい点

アルゴリズムの詳細

Karger の Consistent Hashing の改良版で以下のアルゴリムで hash value を計算する。

std::int32_t JumpConsistentHash(std::int64_t key, std::int32_t num_buckets)
{
  std::int64_t b = -1, j = 0;

  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }

  return b;
}

j の計算に使う (double(1LL << 31) / double((key >> 33) + 1)) は 0 から 1 の一様分布している乱数を生成すればなんでもよい。

Comments

comments powered by Disqus