Consistent Hashingを極めたい
memcachedで採用になって一躍有名になったコンシシテント・ハッシングの計算を極めようと思って,libmemcachedのソースを見てみました.
デフォルトのハッシュ計算の,メイン関数はこれですね.ってか,これだけ...
static uint32_t internal_generate_hash(const char *key, size_t key_length) { const char *ptr= key; uint32_t value= 0; while (key_length--) { uint32_t val= (uint32_t) *ptr++; value += val; value += (value << 10); // value += value *= 2^10 value ^= (value >> 6); } value += (value << 3); value ^= (value >> 11); value += (value << 15); return value == 0 ? 1 : (uint32_t) value; }
memcachedサーバの配置も,データをストア・リードする時も,この関数が呼ばれています.
これだけじゃ何も分かりません...ビットシフトしたり足したり排他的論理和を取ったり,色々やって32ビットのハッシュを計算していることしか...もっと調べます.